author | Michael Krelin <hacker@klever.net> | 2004-07-05 01:53:09 (UTC) |
---|---|---|
committer | Michael Krelin <hacker@klever.net> | 2004-07-05 01:53:09 (UTC) |
commit | 885f8cc426a8840ae61023b75f3f0e4a1e268082 (patch) (unidiff) | |
tree | 5e942d450c97ca0bf0f9cfb80aa0fefb486535d9 /shared-code/BTreendex.h | |
download | kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.zip kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.gz kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.bz2 |
initial commit into svn repository
git-svn-id: http://svn.klever.net/kin/kinsole/trunk@1 fe716a7a-6dde-0310-88d9-d003556173a8
-rw-r--r-- | shared-code/BTreendex.h | 595 |
1 files changed, 595 insertions, 0 deletions
diff --git a/shared-code/BTreendex.h b/shared-code/BTreendex.h new file mode 100644 index 0000000..88109ab --- a/dev/null +++ b/shared-code/BTreendex.h | |||
@@ -0,0 +1,595 @@ | |||
1 | #ifndef__BTREENDEX_H | ||
2 | #define__BTREENDEX_H | ||
3 | |||
4 | #include "Dynamide.h" | ||
5 | |||
6 | namespace Klever { | ||
7 | |||
8 | template<class key,class value,int treeOrder,int cluster> | ||
9 | class CBTreendex : public CObject{ | ||
10 | public: | ||
11 | typedef LONG CBTPageRef; | ||
12 | struct CBTRecordRef { | ||
13 | CBTPageRef m_Page; | ||
14 | INT m_Offset; | ||
15 | CBTRecordRef(CBTPageRef page=-1,INT offset=-1) : m_Page(page), m_Offset(offset) {} | ||
16 | }; | ||
17 | class CBTRecord : public CObject { | ||
18 | public: | ||
19 | CBTPageRef m_ptrLeft; | ||
20 | CBTPageRef m_ptrRight; | ||
21 | key m_Key; | ||
22 | value m_Value; | ||
23 | CBTRecord() : m_ptrLeft(-1), m_ptrRight(-1) {} | ||
24 | CBTRecord(key& _key,value& _value,CBTPageRef left=-1,CBTPageRef right=-1) : m_Key(_key), m_Value(_value), m_ptrLeft(left), m_ptrRight(right) {} | ||
25 | CBTRecord(CBTRecord& r) : m_Key(r.m_Key), m_Value(r.m_Value), m_ptrLeft(r.m_ptrLeft), m_ptrRight(r.m_ptrRight) {} | ||
26 | |||
27 | CBTRecord& operator=(CBTRecord& r) {m_Key=r.m_Key, m_Value=r.m_Value, m_ptrLeft=r.m_ptrLeft, m_ptrRight=r.m_ptrRight;return *this;} | ||
28 | |||
29 | void Serialize(CArchive& ar) { | ||
30 | if(ar.IsStoring()){ | ||
31 | ar << m_ptrLeft; | ||
32 | ar << m_ptrRight; | ||
33 | }else{ | ||
34 | ar >> m_ptrLeft; | ||
35 | ar >> m_ptrRight; | ||
36 | } | ||
37 | SerializeElements(ar,&m_Key,1); | ||
38 | SerializeElements(ar,&m_Value,1); | ||
39 | } | ||
40 | }; | ||
41 | class CBTPage : public CArray<CBTRecord,CBTRecord&> { | ||
42 | public: | ||
43 | void Serialize(CArchive& ar) { | ||
44 | int nCount = -1; | ||
45 | if(ar.IsStoring()){ | ||
46 | nCount = GetSize(); | ||
47 | ar << nCount; | ||
48 | }else{ | ||
49 | nCount = 0; | ||
50 | ar >> nCount; | ||
51 | RemoveAll(); | ||
52 | SetSize(nCount); | ||
53 | } | ||
54 | for(int tmp=0;tmp<nCount;tmp++) | ||
55 | ElementAt(tmp).Serialize(ar); | ||
56 | } | ||
57 | }; | ||
58 | typedef CDynamide<256,cluster> CBTDyna; | ||
59 | typedef CBTDyna::CDynaFile CBTDynaFile; | ||
60 | typedef CArray<CBTRecordRef,CBTRecordRef&> CBTRStack; | ||
61 | |||
62 | CBTDyna m_BT; | ||
63 | struct_btCrap { | ||
64 | BOOL m_bRootSet; | ||
65 | CBTPageRef m_Root; | ||
66 | } *m_BTCrap; | ||
67 | BOOL m_bRO; | ||
68 | CBTRStack m_btStack; | ||
69 | CBTPage m_stackTop; | ||
70 | |||
71 | CBTreendex() {} | ||
72 | ~CBTreendex() { Close(); } | ||
73 | BOOL Attach(CFile* file,BOOL bAutodelete) { | ||
74 | m_bRO = FALSE; | ||
75 | if(!m_BT.Attach(file,bAutodelete)) | ||
76 | return FALSE; | ||
77 | return Attach(); | ||
78 | } | ||
79 | BOOL Open(LPCTSTR file,BOOL bReadOnly) { | ||
80 | if(!m_BT.Open(file,bReadOnly)) | ||
81 | return FALSE; | ||
82 | m_bRO = bReadOnly; | ||
83 | return Attach(); | ||
84 | } | ||
85 | BOOL Create(LPCTSTR file) { | ||
86 | try{ | ||
87 | CFile* f = new CFile(file,CFile::modeCreate|CFile::modeReadWrite|CFile::shareDenyRead|CFile::shareDenyWrite|CFile::typeBinary); | ||
88 | ASSERT(f); | ||
89 | return Attach(f,TRUE); | ||
90 | }catch(CException* e){ | ||
91 | e->Delete(); | ||
92 | return FALSE; | ||
93 | } | ||
94 | } | ||
95 | BOOL Attach() { | ||
96 | ASSERT(m_BT.IsOpened()); | ||
97 | m_BTCrap = (_btCrap*)m_BT.m_FB.crap; | ||
98 | if(!m_BTCrap->m_bRootSet){ | ||
99 | m_BTCrap->m_Root = AllocatePage(); | ||
100 | if(m_BTCrap->m_Root<0) | ||
101 | return FALSE; | ||
102 | m_BTCrap->m_bRootSet = TRUE; | ||
103 | m_BT.Write1stBlock(); | ||
104 | } | ||
105 | return TRUE; | ||
106 | } | ||
107 | BOOL Close() { | ||
108 | m_BT.Close(); | ||
109 | return TRUE; | ||
110 | } | ||
111 | BOOL IsOpened() { | ||
112 | return m_BT.IsOpened(); | ||
113 | } | ||
114 | |||
115 | BOOL Lookup(key& _key,value& value) { | ||
116 | if(!IsOpened()) | ||
117 | return FALSE; | ||
118 | ASSERT(m_BTCrap->m_bRootSet); | ||
119 | if(!SeekToPage(_key)) | ||
120 | return FALSE; | ||
121 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
122 | if(rr.m_Offset<0) | ||
123 | return FALSE; | ||
124 | ASSERT(rr.m_Offset<m_stackTop.GetSize()); | ||
125 | if(_key != m_stackTop[rr.m_Offset].m_Key) | ||
126 | return FALSE; | ||
127 | value = m_stackTop[rr.m_Offset].m_Value; | ||
128 | return TRUE; | ||
129 | } | ||
130 | BOOL Add(key& _key,value& _value) { | ||
131 | if(!IsOpened()) | ||
132 | return FALSE; | ||
133 | ASSERT(m_BTCrap->m_bRootSet); | ||
134 | if(!SeekToPage(_key)) | ||
135 | return FALSE; | ||
136 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
137 | CBTRecord nuRecord(_key,_value); | ||
138 | if(rr.m_Offset<0){ | ||
139 | if(m_stackTop.GetSize()) | ||
140 | nuRecord.m_ptrLeft = m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight; | ||
141 | }else if(rr.m_Offset==0){ | ||
142 | nuRecord.m_ptrRight = m_stackTop[0].m_ptrLeft; | ||
143 | }else{ | ||
144 | nuRecord.m_ptrLeft = m_stackTop[rr.m_Offset-1].m_ptrRight; | ||
145 | nuRecord.m_ptrRight = m_stackTop[rr.m_Offset].m_ptrLeft; | ||
146 | } | ||
147 | // ASSERT(rr.m_Offset==0 || (m_stackTop[rr.m_Offset-1].m_Key<_key && m_stackTop[rr.m_Offset-1].m_ptrRight<0)); | ||
148 | // ASSERT(rr.m_Offset<0 || m_stackTop[rr.m_Offset].m_Key>=_key && m_stackTop[rr.m_Offset].m_ptrLeft<0); | ||
149 | if(rr.m_Offset>=0 && m_stackTop[rr.m_Offset].m_Key==_key){ | ||
150 | // Exact match found - just replace. | ||
151 | m_stackTop[rr.m_Offset].m_Value = _value; | ||
152 | if(!SavePage(rr.m_Page,m_stackTop)) | ||
153 | return FALSE; | ||
154 | return TRUE; | ||
155 | } | ||
156 | // Split the page and propagate the split if needed.. | ||
157 | // Insert new element at rr.m_Offset.. | ||
158 | BOOL nuisnew = TRUE; | ||
159 | for(int sp=m_btStack.GetUpperBound();sp>=0;sp--){ | ||
160 | CBTPageRef opr = m_btStack[sp].m_Page; | ||
161 | int iAt = m_btStack[sp].m_Offset; | ||
162 | CBTPage op; | ||
163 | VERIFY(LoadPage(opr,op)); | ||
164 | if(iAt<0) | ||
165 | iAt = op.GetSize(); | ||
166 | else{ | ||
167 | if(op[iAt].m_Key<nuRecord.m_Key) | ||
168 | iAt++; | ||
169 | ASSERT(iAt==op.GetSize() || op[iAt].m_Key > nuRecord.m_Key); | ||
170 | } | ||
171 | op.InsertAt(iAt,nuRecord); | ||
172 | if(iAt>0) | ||
173 | op[iAt-1].m_ptrRight=nuRecord.m_ptrLeft; | ||
174 | if(iAt<op.GetUpperBound()) | ||
175 | op[iAt+1].m_ptrLeft=nuRecord.m_ptrRight; | ||
176 | if(op.GetSize()<=treeOrder*2){ | ||
177 | // This isn't causing overflow | ||
178 | VERIFY(SavePage(opr,op)); | ||
179 | return TRUE; | ||
180 | } | ||
181 | TRACE0("Split\n"); | ||
182 | ASSERT(op.GetSize()==(treeOrder*2+1)); | ||
183 | CBTPageRef npr = AllocatePage(); | ||
184 | ASSERT(npr>=0); | ||
185 | CBTPage np; | ||
186 | ASSERT(LoadPage(npr,np)); | ||
187 | ASSERT(!np.GetSize()); | ||
188 | nuRecord = op[treeOrder]; | ||
189 | if(iAt==treeOrder){ | ||
190 | // We're inserting central element! - drop out the stack top if this is still new one | ||
191 | for(int tmp=0;tmp<treeOrder;tmp++) | ||
192 | np.InsertAt(tmp,op[tmp]); | ||
193 | op.RemoveAt(0,treeOrder+1); | ||
194 | nuRecord.m_ptrLeft = npr; | ||
195 | nuRecord.m_ptrRight = opr; | ||
196 | if(nuisnew) | ||
197 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
198 | }else{ | ||
199 | if(iAt<treeOrder){ | ||
200 | // We're inserting in the left subtree. | ||
201 | // Make newpage the right one and forget it. | ||
202 | for(int tmp=0;tmp<treeOrder;tmp++) | ||
203 | np.InsertAt(tmp,op[tmp+treeOrder+1]); | ||
204 | op.RemoveAt(treeOrder,treeOrder+1); | ||
205 | nuRecord.m_ptrLeft = opr; | ||
206 | nuRecord.m_ptrRight = npr; | ||
207 | }else{ | ||
208 | // We're inserting in the right subtree. | ||
209 | // Make newpage the left one, forget it, but also adjust offset in the stack | ||
210 | for(int tmp=0;tmp<treeOrder;tmp++) | ||
211 | np.InsertAt(tmp,op[tmp]); | ||
212 | op.RemoveAt(0,treeOrder+1); | ||
213 | nuRecord.m_ptrLeft = npr; | ||
214 | nuRecord.m_ptrRight = opr; | ||
215 | m_btStack[sp].m_Offset-=treeOrder+1; | ||
216 | } | ||
217 | // Note that we're not inserting new element anymore. | ||
218 | nuisnew = FALSE; | ||
219 | } | ||
220 | // Do, excessive sanity checks and save pages | ||
221 | ASSERT(op.GetSize()); | ||
222 | ASSERT(np.GetSize()); | ||
223 | VERIFY(SavePage(opr,op)); | ||
224 | VERIFY(SavePage(npr,np)); | ||
225 | } | ||
226 | // Here we have root page overflow, which means that we're simply putting new | ||
227 | // record in this brand new root page and also inserting this page on the bottom of the stack | ||
228 | CBTPageRef nuroot = AllocatePage(); | ||
229 | ASSERT(nuroot>=0); | ||
230 | CBTPage nurpa; | ||
231 | ASSERT(LoadPage(nuroot,nurpa)); | ||
232 | ASSERT(!nurpa.GetSize()); | ||
233 | nurpa.Add(nuRecord); | ||
234 | VERIFY(SavePage(nuroot,nurpa)); | ||
235 | m_btStack.InsertAt(0,CBTRecordRef(nuroot,0)); | ||
236 | m_BTCrap->m_Root = nuroot; | ||
237 | m_BT.Write1stBlock(); | ||
238 | return TRUE; | ||
239 | } | ||
240 | BOOL Delete(key& _key) { | ||
241 | if(!IsOpened()) | ||
242 | return FALSE; | ||
243 | ASSERT(m_BTCrap->m_bRootSet); | ||
244 | value _value; | ||
245 | if(!Lookup(_key,_value)) | ||
246 | return FALSE; | ||
247 | // Found key, check if it's a leaf | ||
248 | { | ||
249 | CBTRecordRef* rr = &m_btStack[m_btStack.GetUpperBound()]; | ||
250 | int rrIdx = m_btStack.GetUpperBound(); | ||
251 | if(m_stackTop[rr->m_Offset].m_ptrLeft>=0){ | ||
252 | ASSERT(m_stackTop[rr->m_Offset].m_ptrRight>=0); | ||
253 | // It isn't - scan for the _next_ key and do dirty deeds | ||
254 | m_btStack.Add(CBTRecordRef(m_stackTop[rr->m_Offset].m_ptrRight,0)); | ||
255 | for(;;){ | ||
256 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
257 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
258 | return FALSE; | ||
259 | if(m_stackTop[0].m_ptrLeft<0) | ||
260 | break; | ||
261 | m_btStack.Add(CBTRecordRef(m_stackTop[0].m_ptrLeft,0)); | ||
262 | } | ||
263 | // We have a leaf node here, replace victim with the first element and kill it. | ||
264 | CBTPage uppage; | ||
265 | rr = &m_btStack[rrIdx]; | ||
266 | if(!LoadPage(rr->m_Page,uppage)) | ||
267 | return FALSE; | ||
268 | uppage[rr->m_Offset].m_Key=m_stackTop[0].m_Key; uppage[rr->m_Offset].m_Value=m_stackTop[0].m_Value; | ||
269 | m_stackTop.RemoveAt(0); | ||
270 | if(!(SavePage(rr->m_Page,uppage) && SavePage(m_btStack[m_btStack.GetUpperBound()].m_Page,m_stackTop))) | ||
271 | return FALSE; | ||
272 | }else{ | ||
273 | ASSERT(m_stackTop[rr->m_Offset].m_ptrRight<0); | ||
274 | m_stackTop.RemoveAt(rr->m_Offset); | ||
275 | if(!SavePage(rr->m_Page,m_stackTop)) | ||
276 | return FALSE; | ||
277 | } | ||
278 | } | ||
279 | // We have a page to check for underflow at the top of the stack now. | ||
280 | for(;;){ | ||
281 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
282 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
283 | return FALSE; | ||
284 | if(m_stackTop.GetSize()>=treeOrder || m_btStack.GetSize()==1) | ||
285 | return TRUE; | ||
286 | CBTRecordRef& rr1 = m_btStack[m_btStack.GetUpperBound()-1]; | ||
287 | CBTPage daddy; | ||
288 | if(!LoadPage(rr1.m_Page,daddy)) | ||
289 | return FALSE; | ||
290 | CBTPageRef nPage = daddy[rr1.m_Offset].m_ptrRight; | ||
291 | BOOL bRight=TRUE; | ||
292 | if(nPage<0 || nPage==rr.m_Page){ | ||
293 | nPage = daddy[rr1.m_Offset].m_ptrLeft; | ||
294 | bRight = FALSE; | ||
295 | } | ||
296 | ASSERT(nPage>=0 && nPage!=rr.m_Page); | ||
297 | CBTPage neighbor; | ||
298 | if(!LoadPage(nPage,neighbor)) | ||
299 | return FALSE; | ||
300 | // Here we have possibly two cases: | ||
301 | // 1. Neighboring page can share some data with use, then do share and leave | ||
302 | // 2. Neighboring page is of treeorder in size, then merge and propagate | ||
303 | if(neighbor.GetSize()>treeOrder){ | ||
304 | TRACE0("Redistributing..\n"); | ||
305 | // Borrow some data from there. | ||
306 | int toBorrow = neighbor.GetSize()-treeOrder; | ||
307 | toBorrow=toBorrow/2+1; | ||
308 | ASSERT(toBorrow); | ||
309 | if(bRight) | ||
310 | m_stackTop.Add(CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight,neighbor[0].m_ptrLeft)); | ||
311 | else | ||
312 | m_stackTop.InsertAt(0,CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,neighbor[neighbor.GetUpperBound()].m_ptrRight,m_stackTop[0].m_ptrLeft)); | ||
313 | for(toBorrow--;toBorrow;toBorrow--){ | ||
314 | if(bRight){ | ||
315 | m_stackTop.Add(neighbor[0]); | ||
316 | neighbor.RemoveAt(0); | ||
317 | }else{ | ||
318 | m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]); | ||
319 | neighbor.RemoveAt(neighbor.GetUpperBound()); | ||
320 | } | ||
321 | } | ||
322 | daddy[rr1.m_Offset].m_Key = neighbor[bRight?0:neighbor.GetUpperBound()].m_Key; daddy[rr1.m_Offset].m_Value = neighbor[bRight?0:neighbor.GetUpperBound()].m_Value; | ||
323 | neighbor.RemoveAt(bRight?0:neighbor.GetUpperBound()); | ||
324 | if(!(SavePage(rr1.m_Page,daddy) && SavePage(nPage,neighbor) && SavePage(rr.m_Page,m_stackTop))) | ||
325 | return FALSE; | ||
326 | rr.m_Offset = -1;// *** Point to the next?? | ||
327 | return TRUE; | ||
328 | } | ||
329 | TRACE0("Merging..\n"); | ||
330 | // We need to merge pages here.. | ||
331 | // We will merge them at stacktop, then we'll discard neighbor guy.. | ||
332 | if(bRight) | ||
333 | m_stackTop.Add(CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight,neighbor[0].m_ptrLeft)); | ||
334 | else | ||
335 | m_stackTop.InsertAt(0,CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,neighbor[neighbor.GetUpperBound()].m_ptrRight,m_stackTop[0].m_ptrLeft)); | ||
336 | if(bRight){ | ||
337 | while(neighbor.GetSize()){ | ||
338 | m_stackTop.Add(neighbor[0]); | ||
339 | neighbor.RemoveAt(0); | ||
340 | } | ||
341 | }else{ | ||
342 | while(neighbor.GetSize()){ | ||
343 | m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]); | ||
344 | neighbor.RemoveAt(neighbor.GetUpperBound()); | ||
345 | } | ||
346 | } | ||
347 | if(rr1.m_Offset>0) | ||
348 | daddy[rr1.m_Offset-1].m_ptrRight=rr.m_Page; | ||
349 | if(rr1.m_Offset<daddy.GetUpperBound()) | ||
350 | daddy[rr1.m_Offset+1].m_ptrLeft=rr.m_Page; | ||
351 | daddy.RemoveAt(rr1.m_Offset); | ||
352 | if(!(SavePage(rr1.m_Page,daddy) && SavePage(rr.m_Page,m_stackTop))) | ||
353 | return FALSE; | ||
354 | VERIFY(DeallocatePage(nPage)); | ||
355 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
356 | } | ||
357 | return FALSE; | ||
358 | } | ||
359 | BOOL GoFirst() { | ||
360 | if(!IsOpened()) | ||
361 | return FALSE; | ||
362 | ASSERT(m_BTCrap->m_bRootSet); | ||
363 | m_btStack.RemoveAll(); | ||
364 | m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1)); | ||
365 | for(;;){ | ||
366 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
367 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
368 | return FALSE; | ||
369 | if(!m_stackTop.GetSize()){ | ||
370 | ASSERT(m_btStack.GetSize()==1); | ||
371 | return FALSE; | ||
372 | } | ||
373 | rr.m_Offset = 0; | ||
374 | if(m_stackTop[rr.m_Offset].m_ptrLeft<0) | ||
375 | return TRUE; | ||
376 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1)); | ||
377 | } | ||
378 | } | ||
379 | BOOL GoLast() { | ||
380 | if(!IsOpened()) | ||
381 | return FALSE; | ||
382 | ASSERT(m_BTCrap->m_bRootSet); | ||
383 | m_btStack.RemoveAll(); | ||
384 | m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1)); | ||
385 | for(;;){ | ||
386 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
387 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
388 | return FALSE; | ||
389 | if(!m_stackTop.GetSize()){ | ||
390 | ASSERT(m_btStack.GetSize()==1); | ||
391 | return FALSE; | ||
392 | } | ||
393 | rr.m_Offset = m_stackTop.GetUpperBound(); | ||
394 | if(m_stackTop[rr.m_Offset].m_ptrRight<0) | ||
395 | return TRUE; | ||
396 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1)); | ||
397 | } | ||
398 | } | ||
399 | BOOL GoNext() { | ||
400 | if(!IsOpened()) | ||
401 | return FALSE; | ||
402 | if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0)) | ||
403 | return FALSE; | ||
404 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
405 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
406 | return FALSE; | ||
407 | ASSERT(rr.m_Offset<m_stackTop.GetSize()); | ||
408 | if(m_stackTop[rr.m_Offset].m_ptrRight>=0){ | ||
409 | // Advance pointer in this page and dive into subtree | ||
410 | // going left and left until we have nowhere to go. | ||
411 | // TRACE1("Dive into page %lu",m_stackTop[rr.m_Offset].m_ptrRight); | ||
412 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,0)); | ||
413 | for(;;){ | ||
414 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
415 | ASSERT(rr.m_Offset==0); | ||
416 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
417 | return FALSE; | ||
418 | if(m_stackTop[rr.m_Offset].m_ptrLeft<0) | ||
419 | break; | ||
420 | // TRACE1(", %lu",m_stackTop[rr.m_Offset].m_ptrLeft); | ||
421 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,0)); | ||
422 | } | ||
423 | // TRACE0("\n"); | ||
424 | return TRUE; | ||
425 | }else if(rr.m_Offset<m_stackTop.GetUpperBound()){ | ||
426 | rr.m_Offset++; | ||
427 | return TRUE; | ||
428 | } | ||
429 | // We're at the end of page go up until we're done or we have data. | ||
430 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
431 | // TRACE0("Go up"); | ||
432 | while(m_btStack.GetSize()){ | ||
433 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
434 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
435 | return FALSE; | ||
436 | if(rr.m_Offset<m_stackTop.GetSize()){ | ||
437 | // TRACE0("\n"); | ||
438 | return TRUE; | ||
439 | } | ||
440 | // TRACE0(", up"); | ||
441 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
442 | } | ||
443 | // TRACE0("\nBtree is done\n"); | ||
444 | return FALSE; | ||
445 | } | ||
446 | BOOL GoPrev() { | ||
447 | if(!IsOpened()) | ||
448 | return FALSE; | ||
449 | if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0)) | ||
450 | return FALSE; | ||
451 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
452 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
453 | return FALSE; | ||
454 | ASSERT(rr.m_Offset<m_stackTop.GetSize()); | ||
455 | if(m_stackTop[rr.m_Offset].m_ptrLeft>=0){ | ||
456 | // Dive in and go right and right from the rightmost until | ||
457 | // we have nowhere to go. | ||
458 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1)); | ||
459 | for(;;){ | ||
460 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
461 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
462 | return FALSE; | ||
463 | rr.m_Offset = m_stackTop.GetUpperBound(); | ||
464 | if(m_stackTop[rr.m_Offset].m_ptrRight<0) | ||
465 | return TRUE; | ||
466 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1)); | ||
467 | } | ||
468 | return TRUE; | ||
469 | }else if(rr.m_Offset>0){ | ||
470 | rr.m_Offset--; | ||
471 | return TRUE; | ||
472 | } | ||
473 | // We're at the leftmost element in page - go up and left until we're | ||
474 | // done or we have data. | ||
475 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
476 | while(m_btStack.GetSize()){ | ||
477 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
478 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
479 | return FALSE; | ||
480 | rr.m_Offset--; | ||
481 | if(rr.m_Offset>=0) | ||
482 | return TRUE; | ||
483 | m_btStack.RemoveAt(m_btStack.GetUpperBound()); | ||
484 | } | ||
485 | // No more data - we were at the first element in tree. | ||
486 | return FALSE; | ||
487 | } | ||
488 | BOOL GetThis(key& _key,value& _value) { | ||
489 | if(!IsOpened()) | ||
490 | return FALSE; | ||
491 | // *** MORE CHECKING | ||
492 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
493 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
494 | return FALSE; | ||
495 | _key = m_stackTop[rr.m_Offset].m_Key; | ||
496 | _value = m_stackTop[rr.m_Offset].m_Value; | ||
497 | return TRUE; | ||
498 | } | ||
499 | |||
500 | BOOL SeekToPage(const key& _key) { | ||
501 | ASSERT(IsOpened()); | ||
502 | ASSERT(m_BTCrap->m_bRootSet); | ||
503 | m_btStack.RemoveAll(); | ||
504 | m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1)); | ||
505 | for(;;){ | ||
506 | CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()]; | ||
507 | if(!LoadPage(rr.m_Page,m_stackTop)) | ||
508 | return FALSE; | ||
509 | ASSERT(m_stackTop.GetSize() || !m_btStack.GetUpperBound()); | ||
510 | if(!m_stackTop.GetSize()){ | ||
511 | rr.m_Offset=-1; | ||
512 | return TRUE; | ||
513 | } | ||
514 | for(rr.m_Offset=0;rr.m_Offset<m_stackTop.GetSize();rr.m_Offset++){ | ||
515 | if(_key == m_stackTop[rr.m_Offset].m_Key) | ||
516 | return TRUE; | ||
517 | if(_key < m_stackTop[rr.m_Offset].m_Key){ | ||
518 | ASSERT(rr.m_Offset==0 || m_stackTop[rr.m_Offset].m_ptrLeft==m_stackTop[rr.m_Offset-1].m_ptrRight); | ||
519 | if(m_stackTop[rr.m_Offset].m_ptrLeft<0) | ||
520 | return TRUE; | ||
521 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1)); | ||
522 | break; | ||
523 | } | ||
524 | if(rr.m_Offset==m_stackTop.GetUpperBound()){ | ||
525 | if(m_stackTop[rr.m_Offset].m_ptrRight<0){ | ||
526 | rr.m_Offset=-1; | ||
527 | return TRUE; | ||
528 | } | ||
529 | m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrRight,-1)); | ||
530 | break; | ||
531 | } | ||
532 | } | ||
533 | } | ||
534 | } | ||
535 | |||
536 | BOOL LoadPage(CBTPageRef ref,CBTPage& page) { | ||
537 | CFile* pageFile = m_BT.OpenFile(ref); | ||
538 | if(!pageFile) | ||
539 | return FALSE; | ||
540 | BOOL rv = TRUE; | ||
541 | try{ | ||
542 | CArchive ar(pageFile,CArchive::load); | ||
543 | page.Serialize(ar); | ||
544 | if(m_bRO) | ||
545 | page.FreeExtra();// ** ??? | ||
546 | ar.Close(); | ||
547 | }catch(CException* e){ | ||
548 | e->Delete(); | ||
549 | rv = FALSE; | ||
550 | } | ||
551 | delete pageFile; | ||
552 | return rv; | ||
553 | } | ||
554 | BOOL SavePage(CBTPageRef ref,CBTPage& page) { | ||
555 | CFile* pageFile = m_BT.OpenFile(ref); | ||
556 | if(!pageFile) | ||
557 | return FALSE; | ||
558 | BOOL rv = TRUE; | ||
559 | try{ | ||
560 | CArchive ar(pageFile,CArchive::store); | ||
561 | page.Serialize(ar); | ||
562 | ar.Close(); | ||
563 | }catch(CException* e){ | ||
564 | e->Delete(); | ||
565 | rv = FALSE; | ||
566 | } | ||
567 | delete pageFile; | ||
568 | return rv; | ||
569 | } | ||
570 | CBTPageRef AllocatePage() { | ||
571 | CBTDynaFile* pageFile = m_BT.CreateFile(); | ||
572 | if(!pageFile) | ||
573 | return -1; | ||
574 | CBTPage nothing; | ||
575 | CBTPageRef rv = pageFile->GetFile(); | ||
576 | try{ | ||
577 | CArchive ar(pageFile,CArchive::store); | ||
578 | nothing.Serialize(ar); | ||
579 | ar.Close(); | ||
580 | }catch(CException* e){ | ||
581 | e->Delete(); | ||
582 | rv = -1; | ||
583 | } | ||
584 | delete pageFile; | ||
585 | return rv; | ||
586 | } | ||
587 | BOOL DeallocatePage(CBTPageRef ref) { | ||
588 | return m_BT.DeleteFile(ref); | ||
589 | } | ||
590 | |||
591 | }; | ||
592 | |||
593 | }; | ||
594 | |||
595 | #endif// __BTREENDEX_H | ||