mirror of
https://github.com/hanzoai/graph.git
synced 2026-10-30 18:35:37 +00:00
zeekay
f5aaeb712e
Derived from Dgraph (github.com/dgraph-io/dgraph) at commit 64804bd2, Apache-2.0. See NOTICE. WHAT THIS IS. The graph engine as a Go library: posting lists, the DQL parser, the type and tokenizer system, the index and schema layers, and the wire types. 39,170 lines of the upstream's 166,337. THE STORE is github.com/luxfi/zapdb, a Badger fork that kept the package name, the subpackages (options, pb, y) and the API — Open, OpenManaged, DB, Options — so the 74 import sites are aliased rather than rewritten. THE CODEC is ZAP. zapdb serializes with ZAP, not protobuf: its pb package builds the ZAP types by default and the protobuf ones only under `-tags grpc`, a path that does not compile (table/builder.go calls pb.Marshal, which that tag removes). One call site in posting needed converting; every other type here is Hanzo's own protobuf and is untouched. NO TRANSPORT. An embedded engine dials nothing, so nothing here imports google.golang.org/grpc. Removed: 20 transport functions in x, the generated service stubs for Raft, Zero and Worker (1,657 lines), and the JWT helper — identity belongs to IAM. The core called none of them. NOT KEPT: worker, conn, raftwal, the cluster commands, the GraphQL layer and the test harnesses. `query`, the DQL execution engine, went with them because it depends on worker; parsing DQL is available here, executing it is not. The history of the upstream project lives at github.com/dgraph-io/dgraph. This repository begins at the derivation because three quarters of that history describes code this fork does not carry.
101 lines
1.9 KiB
Go
101 lines
1.9 KiB
Go
/*
|
|
* SPDX-FileCopyrightText: © 2017-2026 Istari Digital, Inc.
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*/
|
|
|
|
package types
|
|
|
|
// Below functions are taken from go's sort library zsortinterface.go
|
|
// https://go.dev/src/sort/zsortinterface.go
|
|
func insertionSort(data byValue, a, b int) {
|
|
for i := a + 1; i < b; i++ {
|
|
for j := i; j > a && data.Less(j, j-1); j-- {
|
|
data.Swap(j, j-1)
|
|
}
|
|
}
|
|
}
|
|
|
|
func order2(data byValue, a, b int) (int, int) {
|
|
if data.Less(b, a) {
|
|
return b, a
|
|
}
|
|
return a, b
|
|
}
|
|
|
|
func median(data byValue, a, b, c int) int {
|
|
a, b = order2(data, a, b)
|
|
b, _ = order2(data, b, c)
|
|
_, b = order2(data, a, b)
|
|
return b
|
|
}
|
|
|
|
func medianAdjacent(data byValue, a int) int {
|
|
return median(data, a-1, a, a+1)
|
|
}
|
|
|
|
// [shortestNinther,∞): uses the Tukey ninther method.
|
|
func choosePivot(data byValue, a, b int) (pivot int) {
|
|
const (
|
|
shortestNinther = 50
|
|
maxSwaps = 4 * 3
|
|
)
|
|
|
|
l := b - a
|
|
|
|
var (
|
|
i = a + l/4*1
|
|
j = a + l/4*2
|
|
k = a + l/4*3
|
|
)
|
|
|
|
if l >= 8 {
|
|
if l >= shortestNinther {
|
|
// Tukey ninther method, the idea came from Rust's implementation.
|
|
i = medianAdjacent(data, i)
|
|
j = medianAdjacent(data, j)
|
|
k = medianAdjacent(data, k)
|
|
}
|
|
// Find the median among i, j, k and stores it into j.
|
|
j = median(data, i, j, k)
|
|
}
|
|
|
|
return j
|
|
}
|
|
|
|
func partition(data byValue, a, b, pivot int) int {
|
|
partitionIndex := a
|
|
data.Swap(pivot, b)
|
|
for i := a; i < b; i++ {
|
|
if data.Less(i, b) {
|
|
data.Swap(i, partitionIndex)
|
|
partitionIndex++
|
|
}
|
|
}
|
|
data.Swap(partitionIndex, b)
|
|
return partitionIndex
|
|
}
|
|
|
|
func quickSelect(data byValue, low, high, k int) {
|
|
var pivotIndex int
|
|
|
|
for {
|
|
if low >= high {
|
|
return
|
|
} else if high-low <= 8 {
|
|
insertionSort(data, low, high+1)
|
|
return
|
|
}
|
|
|
|
pivotIndex = choosePivot(data, low, high)
|
|
pivotIndex = partition(data, low, high, pivotIndex)
|
|
|
|
if k < pivotIndex {
|
|
high = pivotIndex - 1
|
|
} else if k > pivotIndex {
|
|
low = pivotIndex + 1
|
|
} else {
|
|
return
|
|
}
|
|
}
|
|
}
|