node.gno

  1package bptree
  2
  3// node is the interface satisfied by both inner and leaf nodes.
  4type node interface {
  5	isLeaf() bool
  6	nodeSize() int // total leaf entries in subtree
  7	minKey() string
  8}
  9
 10//----------------------------------------
 11// leafNode
 12
 13type leafNode struct {
 14	keys   []string
 15	values []*any // each value is a separate object for lazy loading
 16}
 17
 18func newLeafNode(fanout int) *leafNode {
 19	return &leafNode{
 20		keys:   make([]string, 0, fanout),
 21		values: make([]*any, 0, fanout),
 22	}
 23}
 24
 25func (n *leafNode) isLeaf() bool   { return true }
 26func (n *leafNode) nodeSize() int  { return len(n.keys) }
 27func (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.
 31func (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.
 48func (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.
 59func (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
 77type 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
 83func 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
 91func (n *innerNode) isLeaf() bool { return false }
 92func (n *innerNode) nodeSize() int {
 93	sum := 0
 94	for _, s := range n.sizes {
 95		sum += s
 96	}
 97	return sum
 98}
 99func (n *innerNode) minKey() string { return n.children[0].minKey() }
100
101// findChild returns the child index for the given key.
102func (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]).
118func (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.
137func (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}