Kind Pure package
Name v0
Namespace nt / bptree
Exported functions n/a — not supported for pure packages by the node (vm/qfuncs)
Module gno.land/p/nt/bptree/v0
gno 0.9 node.gno gno
⧉
1 package bptree 2 3 // node is the interface satisfied by both inner and leaf nodes. 4 type node interface { 5 isLeaf() bool 6 nodeSize() int // total leaf entries in subtree 7 not supported for pure packages by the node (vm/qfuncs)
Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.
minKey()
string
8 }
9
10 //----------------------------------------
11 // leafNode
12
13 type leafNode struct {
14 keys [] string
15 values []* any // each value is a separate object for lazy loading
16 }
17
18 func newLeafNode(fanout int ) *leafNode {
19 return &leafNode{
20 keys: make([] string , 0 , fanout),
21 values: make([]* any , 0 , fanout),
22 }
23 }
24
25 func (n *leafNode) isLeaf() bool { return true }
26 func (n *leafNode) nodeSize() int { return len(n.keys) }
27 func (n *leafNode) minKey() string { return n.keys[ 0 ] }
28
29 // find returns the index where key is or would be inserted,
30 // and whether an exact match was found.
31 func (n *leafNode) find(key string ) ( int , bool ) {
32 lo, hi := 0 , len(n.keys)
33 for lo < hi {
34 mid := lo + (hi-lo)/ 2
35 if n.keys[mid] < key {
36 lo = mid + 1
37 } else {
38 hi = mid
39 }
40 }
41 if lo < len(n.keys) && n.keys[lo] == key {
42 return lo, true
43 }
44 return lo, false
45 }
46
47 // insertAt inserts a key-value pair at the given position.
48 func (n *leafNode) insertAt(pos int , key string , value * any ) {
49 n.keys = append(n.keys, "" )
50 copy(n.keys[pos+ 1 :], n.keys[pos:])
51 n.keys[pos] = key
52
53 n.values = append(n.values, nil )
54 copy(n.values[pos+ 1 :], n.values[pos:])
55 n.values[pos] = value
56 }
57
58 // removeAt removes the entry at the given position and returns the removed key and value.
59 func (n *leafNode) removeAt(pos int ) ( string , * any ) {
60 key := n.keys[pos]
61 value := n.values[pos]
62
63 copy(n.keys[pos:], n.keys[pos+ 1 :])
64 n.keys[len(n.keys)- 1 ] = ""
65 n.keys = n.keys[:len(n.keys)- 1 ]
66
67 copy(n.values[pos:], n.values[pos+ 1 :])
68 n.values[len(n.values)- 1 ] = nil
69 n.values = n.values[:len(n.values)- 1 ]
70
71 return key, value
72 }
73
74 //----------------------------------------
75 // innerNode
76
77 type innerNode struct {
78 keys [] string // separator keys; keys[i] = minKey of children[i+1]
79 children []node
80 sizes [] int // sizes[i] = total leaf entries in children[i]
81 }
82
83 func newInnerNode(fanout int ) *innerNode {
84 return &innerNode{
85 keys: make([] string , 0 , fanout- 1 ),
86 children: make([]node, 0 , fanout),
87 sizes: make([] int , 0 , fanout),
88 }
89 }
90
91 func (n *innerNode) isLeaf() bool { return false }
92 func (n *innerNode) nodeSize() int {
93 sum := 0
94 for _, s := range n.sizes {
95 sum += s
96 }
97 return sum
98 }
99 func (n *innerNode) minKey() string { return n.children[ 0 ].minKey() }
100
101 // findChild returns the child index for the given key.
102 func (n *innerNode) findChild(key string ) int {
103 // Binary search: find the rightmost i where keys[i] <= key.
104 lo, hi := 0 , len(n.keys)
105 for lo < hi {
106 mid := lo + (hi-lo)/ 2
107 if n.keys[mid] <= key {
108 lo = mid + 1
109 } else {
110 hi = mid
111 }
112 }
113 return lo
114 }
115
116 // insertChildAt inserts a new child with its separator key at the given position.
117 // The separator key is placed at keys[pos-1] (since keys[i] = minKey of children[i+1]).
118 func (n *innerNode) insertChildAt(pos int , sep string , child node, sz int ) {
119 // Insert separator at keys[pos-1].
120 keyPos := pos - 1
121 n.keys = append(n.keys, "" )
122 copy(n.keys[keyPos+ 1 :], n.keys[keyPos:])
123 n.keys[keyPos] = sep
124
125 // Insert child at children[pos].
126 n.children = append(n.children, nil )
127 copy(n.children[pos+ 1 :], n.children[pos:])
128 n.children[pos] = child
129
130 // Insert size at sizes[pos].
131 n.sizes = append(n.sizes, 0 )
132 copy(n.sizes[pos+ 1 :], n.sizes[pos:])
133 n.sizes[pos] = sz
134 }
135
136 // removeChildAt removes the child at pos and its associated separator key.
137 func (n *innerNode) removeChildAt(pos int ) {
138 // Determine which separator to remove.
139 // keys[i] separates children[i] from children[i+1].
140 // Removing children[pos]: if pos > 0, remove keys[pos-1]; else remove keys[0].
141 keyPos := pos
142 if pos > 0 {
143 keyPos = pos - 1
144 }
145 if len(n.keys) > 0 {
146 copy(n.keys[keyPos:], n.keys[keyPos+ 1 :])
147 n.keys[len(n.keys)- 1 ] = ""
148 n.keys = n.keys[:len(n.keys)- 1 ]
149 }
150
151 copy(n.children[pos:], n.children[pos+ 1 :])
152 n.children[len(n.children)- 1 ] = nil
153 n.children = n.children[:len(n.children)- 1 ]
154
155 copy(n.sizes[pos:], n.sizes[pos+ 1 :])
156 n.sizes = n.sizes[:len(n.sizes)- 1 ]
157 }
158