btree.gno

  1package btree
  2
  3type bTree struct {
  4	degree    int
  5	size      int
  6	root      *node
  7	iterating int
  8}
  9
 10func newBTree(degree int) *bTree {
 11	if degree <= 1 {
 12		panic("degree must be greater than 1")
 13	}
 14	return &bTree{degree: degree}
 15}
 16
 17func (t *bTree) maxKeys() int { return t.degree*2 - 1 }
 18func (t *bTree) minKeys() int { return t.degree - 1 }
 19func (t *bTree) Size() int    { return t.size }
 20
 21// Set inserts or updates key/value. It returns true when key already existed.
 22func (t *bTree) Set(key key, value any) (updated bool) {
 23	t.assertNotIterating()
 24
 25	maxKeys := t.degree*2 - 1
 26	if t.root == nil {
 27		t.root = newNodeWithEntry(key, value, maxKeys)
 28		t.size = 1
 29		return false
 30	}
 31
 32	if t.root.size() >= maxKeys {
 33		if t.root.update(key, value) {
 34			return true
 35		}
 36		t.splitRoot(maxKeys, t.root.lastKey().Less(key))
 37	}
 38
 39	inserted := t.root.setNonFull(key, value, maxKeys)
 40	if inserted {
 41		t.size++
 42	}
 43	return !inserted
 44}
 45
 46func (t *bTree) splitRoot(maxKeys int, appendSplit bool) {
 47	newRoot := newNode(maxKeys)
 48	newRoot.children = []*node{t.root}
 49	newRoot.split(0, maxKeys, appendSplit)
 50	t.root = newRoot
 51}
 52
 53func (t *bTree) Get(key key) (any, bool) {
 54	if t.root == nil {
 55		return nil, false
 56	}
 57	return t.root.get(key)
 58}
 59
 60func (t *bTree) Has(key key) bool {
 61	_, ok := t.Get(key)
 62	return ok
 63}
 64
 65func (t *bTree) Remove(key key) (any, bool) {
 66	t.assertNotIterating()
 67
 68	if t.root == nil {
 69		return nil, false
 70	}
 71
 72	v, removed := t.root.remove(key, t.minKeys())
 73	if !removed {
 74		return nil, false
 75	}
 76
 77	t.size--
 78
 79	if t.root.size() == 0 && !t.root.isLeaf() {
 80		t.root = t.root.firstChild()
 81	} else if t.root.size() == 0 {
 82		t.root = nil
 83	}
 84	return v, true
 85}
 86
 87func (t *bTree) GetByIndex(index int) (key, any) {
 88	if t.root == nil || index < 0 || index >= t.size {
 89		panic("GetByIndex asked for invalid index")
 90	}
 91	return t.root.getByIndex(index)
 92}
 93
 94// Iterate visits keys in ascending order within [start, end).
 95// A nil start means no lower bound, and a nil end means no upper bound.
 96func (t *bTree) Iterate(start, end key, cb iterCbFn) bool {
 97	t.assertNotIteratingForIteration()
 98	if t.root == nil {
 99		return false
100	}
101	t.beginIteration()
102	defer t.endIteration()
103	return t.root.iterate(start, end, cb)
104}
105
106// ReverseIterate visits keys in descending order over [start, end].
107// A nil start means no lower bound, and a nil end means no upper bound.
108func (t *bTree) ReverseIterate(start, end key, cb iterCbFn) bool {
109	t.assertNotIteratingForIteration()
110	if t.root == nil {
111		return false
112	}
113	t.beginIteration()
114	defer t.endIteration()
115	return t.root.reverseIterate(start, end, cb)
116}
117
118func (t *bTree) IterateByOffset(offset int, count int, cb iterCbFn) bool {
119	t.assertNotIteratingForIteration()
120	if t.root == nil || offset < 0 || offset >= t.size || count <= 0 {
121		return false
122	}
123	seen := 0
124	visited := 0
125	t.beginIteration()
126	defer t.endIteration()
127	return t.root.iterateByOffset(offset, count, false, &seen, &visited, cb)
128}
129
130func (t *bTree) ReverseIterateByOffset(offset int, count int, cb iterCbFn) bool {
131	t.assertNotIteratingForIteration()
132	if t.root == nil || offset < 0 || offset >= t.size || count <= 0 {
133		return false
134	}
135	seen := 0
136	visited := 0
137	t.beginIteration()
138	defer t.endIteration()
139	return t.root.iterateByOffset(offset, count, true, &seen, &visited, cb)
140}
141
142func (t *bTree) beginIteration() {
143	t.iterating++
144}
145
146func (t *bTree) endIteration() {
147	t.iterating--
148}
149
150func (t *bTree) assertNotIterating() {
151	if t.iterating > 0 {
152		panic("btree mutation during iteration")
153	}
154}
155
156func (t *bTree) assertNotIteratingForIteration() {
157	if t.iterating > 0 {
158		panic("btree iteration during iteration")
159	}
160}