ops.mx raw
1 package lattice
2
3 func (t *Tree) Walk(branch Branch, key Key) (nodeIdx uint32, pos int, found bool) {
4 idx := t.Roots[branch]
5 for {
6 node := t.getNode(idx)
7 k := node.KeyCount()
8 p := 0
9 for p < k && keyLess(node.Keys[p], key) {
10 p++
11 }
12 if p < k && keyEqual(key, node.Keys[p]) {
13 return idx, p, true
14 }
15 if node.IsLeaf() {
16 return idx, p, false
17 }
18 child := node.Children[p]
19 if child == NullIndex {
20 return idx, p, false
21 }
22 idx = child
23 }
24 }
25
26 func (t *Tree) Insert(branch Branch, key Key, rec Record) uint32 {
27 root := t.Roots[branch]
28 if t.getNode(root).KeyCount() == C {
29 t.splitRoot(branch)
30 }
31 rIdx := t.allocRecord()
32 r := t.getRecord(rIdx)
33 *r = rec
34 t.markRecDirty(rIdx)
35 t.RecKey[rIdx] = key
36 return t.insertNonFull(t.Roots[branch], branch, key, rIdx)
37 }
38
39 // InsertRec inserts rec at key in branch and returns the record index (not
40 // the node index). Use this when you need to index side-data by record index.
41 func (t *Tree) InsertRec(branch Branch, key Key, rec Record) uint32 {
42 root := t.Roots[branch]
43 if t.getNode(root).KeyCount() == C {
44 t.splitRoot(branch)
45 }
46 rIdx := t.allocRecord()
47 r := t.getRecord(rIdx)
48 *r = rec
49 // Always reset links to NullRec after copy.
50 r.Link[0] = NullRec
51 r.Link[1] = NullRec
52 t.markRecDirty(rIdx)
53 t.RecKey[rIdx] = key
54 t.insertNonFull(t.Roots[branch], branch, key, rIdx)
55 return rIdx
56 }
57
58 func (t *Tree) insertNonFull(idx uint32, branch Branch, key Key, recIdx uint32) uint32 {
59 for {
60 node := t.getNode(idx)
61 k := node.KeyCount()
62 p := 0
63 for p < k && keyLess(node.Keys[p], key) {
64 p++
65 }
66 if p < k && keyEqual(key, node.Keys[p]) {
67 return idx
68 }
69 if node.IsLeaf() {
70 for i := k; i > p; i-- {
71 node.Keys[i] = node.Keys[i-1]
72 node.RecPtrs[i] = node.RecPtrs[i-1]
73 }
74 node.Keys[p] = key
75 node.RecPtrs[p] = recIdx
76 node.SetCount(k + 1)
77 node.SetBranch(branch)
78 node.Mult = 1
79 t.markNodeDirty(idx)
80 return idx
81 }
82 childIdx := node.Children[p]
83 if t.getNode(childIdx).KeyCount() == C {
84 median := t.splitChild(idx, p)
85 node = t.getNode(idx)
86 if keyEqual(key, median) {
87 for pp := 0; pp < node.KeyCount(); pp++ {
88 if keyEqual(node.Keys[pp], key) {
89 return idx
90 }
91 }
92 }
93 if keyLess(median, key) {
94 p++
95 }
96 childIdx = t.getNode(idx).Children[p]
97 }
98 idx = childIdx
99 }
100 }
101
102 func (t *Tree) splitChild(parentIdx uint32, childPos int) Key {
103 fullIdx := t.getNode(parentIdx).Children[childPos]
104 full := *t.getNode(fullIdx)
105
106 // For C=8: median is at index C/2=4.
107 // Left node gets keys [0..3] (4 keys), right gets keys [5..7] (3 keys).
108 const mid = C / 2
109 median := full.Keys[mid]
110 medianRec := full.RecPtrs[mid]
111
112 rightIdx := t.allocNode()
113 right := t.getNode(rightIdx)
114 rightCount := C - mid - 1 // keys after the median
115 for i := 0; i < rightCount; i++ {
116 right.Keys[i] = full.Keys[mid+1+i]
117 right.RecPtrs[i] = full.RecPtrs[mid+1+i]
118 }
119 right.SetCount(rightCount)
120 right.SetBranch(full.GetBranch())
121 right.Mult = full.Mult
122 if !full.IsLeaf() {
123 for i := 0; i <= rightCount; i++ {
124 right.Children[i] = full.Children[mid+1+i]
125 }
126 }
127 t.markNodeDirty(rightIdx)
128
129 left := t.getNode(fullIdx)
130 leftCount := mid
131 for i := 0; i < leftCount; i++ {
132 left.Keys[i] = full.Keys[i]
133 left.RecPtrs[i] = full.RecPtrs[i]
134 }
135 for i := leftCount; i < C; i++ {
136 left.Keys[i] = KeyZero
137 left.RecPtrs[i] = NullRec
138 }
139 left.SetCount(leftCount)
140 if !full.IsLeaf() {
141 for i := 0; i <= leftCount; i++ {
142 left.Children[i] = full.Children[i]
143 }
144 for i := leftCount + 1; i <= C; i++ {
145 left.Children[i] = NullIndex
146 }
147 } else {
148 for i := range left.Children {
149 left.Children[i] = NullIndex
150 }
151 }
152 t.markNodeDirty(fullIdx)
153
154 parent := t.getNode(parentIdx)
155 pk := parent.KeyCount()
156 for i := pk; i > childPos; i-- {
157 parent.Keys[i] = parent.Keys[i-1]
158 parent.RecPtrs[i] = parent.RecPtrs[i-1]
159 }
160 parent.Keys[childPos] = median
161 parent.RecPtrs[childPos] = medianRec
162 for i := pk + 1; i > childPos+1; i-- {
163 parent.Children[i] = parent.Children[i-1]
164 }
165 parent.Children[childPos+1] = rightIdx
166 parent.SetCount(pk + 1)
167 t.markNodeDirty(parentIdx)
168
169 return median
170 }
171
172 func (t *Tree) splitRoot(branch Branch) {
173 rootIdx := t.Roots[branch]
174 leftIdx := t.allocNode()
175 *t.getNode(leftIdx) = *t.getNode(rootIdx)
176 t.markNodeDirty(leftIdx)
177
178 root := t.getNode(rootIdx)
179 *root = Node{}
180 initNodeChildren(root)
181 root.Children[0] = leftIdx
182 root.SetBranch(branch)
183 root.Mult = 1
184 t.markNodeDirty(rootIdx)
185
186 t.splitChild(rootIdx, 0)
187 }
188
189 func (t *Tree) Lookup(branch Branch, key Key) *Record {
190 idx, pos, found := t.Walk(branch, key)
191 if !found {
192 return nil
193 }
194 node := t.getNode(idx)
195 if node.IsDeleted() {
196 return nil
197 }
198 recIdx := node.RecPtrs[pos]
199 if recIdx == NullRec {
200 return nil
201 }
202 return t.getRecord(recIdx)
203 }
204
205 func (t *Tree) Delete(branch Branch, key Key) bool {
206 idx, pos, found := t.Walk(branch, key)
207 if !found {
208 return false
209 }
210 node := t.getNode(idx)
211 if node.IsDeleted() {
212 return false
213 }
214 recIdx := node.RecPtrs[pos]
215 if recIdx != NullRec {
216 rec := t.getRecord(recIdx)
217 for li := 0; li < 2; li++ {
218 partnerRI := rec.Link[li]
219 if partnerRI == NullRec {
220 continue
221 }
222 pRec := t.getRecord(partnerRI)
223 for pi := 0; pi < 2; pi++ {
224 if pRec.Link[pi] == recIdx {
225 pRec.Link[pi] = NullRec
226 t.markRecDirty(partnerRI)
227 }
228 }
229 }
230 rec.Link[0] = NullRec
231 rec.Link[1] = NullRec
232 t.markRecDirty(recIdx)
233 }
234 delete(t.RecKey, recIdx)
235 node.SetDeleted()
236 node.Children[0] = t.FreeHead
237 t.FreeHead = idx
238 t.FreeCount++
239 t.markNodeDirty(idx)
240 return true
241 }
242
243 func (t *Tree) InsertTriple(nounKey, verbKey, modKey Key, nRec, vRec, mRec Record) {
244 t.Insert(Bnoun, nounKey, nRec)
245 t.Insert(Bverb, verbKey, vRec)
246 t.Insert(Bmodifier, modKey, mRec)
247 nri := t.LookupRecIdx(Bnoun, nounKey)
248 vri := t.LookupRecIdx(Bverb, verbKey)
249 mri := t.LookupRecIdx(Bmodifier, modKey)
250 nr := t.getRecord(nri)
251 nr.Link = [2]uint32{vri, mri}
252 nr.Branch = uint8(Bnoun)
253 t.markRecDirty(nri)
254 vr := t.getRecord(vri)
255 vr.Link = [2]uint32{nri, mri}
256 vr.Branch = uint8(Bverb)
257 t.markRecDirty(vri)
258 mr := t.getRecord(mri)
259 mr.Link = [2]uint32{nri, vri}
260 mr.Branch = uint8(Bmodifier)
261 t.markRecDirty(mri)
262 }
263