summaryrefslogtreecommitdiffabout
path: root/shared-code/BTreendex.h
authorMichael Krelin <hacker@klever.net>2004-07-05 01:53:09 (UTC)
committer Michael Krelin <hacker@klever.net>2004-07-05 01:53:09 (UTC)
commit885f8cc426a8840ae61023b75f3f0e4a1e268082 (patch) (unidiff)
tree5e942d450c97ca0bf0f9cfb80aa0fefb486535d9 /shared-code/BTreendex.h
downloadkinsole-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
Diffstat (limited to 'shared-code/BTreendex.h') (more/less context) (ignore whitespace changes)
-rw-r--r--shared-code/BTreendex.h595
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
6namespace Klever {
7
8template<class key,class value,int treeOrder,int cluster>
9 class CBTreendex : public CObject{
10public:
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