1/*
2 * PROGRAM: Client/Server Common Code
3 * MODULE: tree.h
4 * DESCRIPTION: Generic In-memory B+ Tree
5 *
6 * The contents of this file are subject to the Initial
7 * Developer's Public License Version 1.0 (the "License");
8 * you may not use this file except in compliance with the
9 * License. You may obtain a copy of the License at
10 * http://www.ibphoenix.com/main.nfs?a=ibphoenix&page=ibp_idpl.
11 *
12 * Software distributed under the License is distributed AS IS,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied.
14 * See the License for the specific language governing rights
15 * and limitations under the License.
16 *
17 * The Original Code was created by Nickolay Samofatov
18 * for the Firebird Open Source RDBMS project.
19 *
20 * Copyright (c) 2004 Nickolay Samofatov <nickolay@broadviewsoftware.com>
21 * and all contributors signed below.
22 *
23 * All Rights Reserved.
24 * Contributor(s): ______________________________________.
25 *
26 *
27 *
28 */
29
30#ifndef CLASSES_TREE_H
31#define CLASSES_TREE_H
32
33#include "../common/gdsassert.h"
34#include <string.h>
35#ifdef HAVE_STDLIB_H
36#include <stdlib.h> // XPG: prototypes for malloc/free have to be in stdlib.h (EKU)
37#endif
38#include "vector.h"
39
40namespace Firebird {
41
42// This macro controls merging of nodes of all B+ trees
43// Now it merges pages only when resulting page will be 3/4 filled or less
44// Be careful while changing this expression. N=2 must always cause merge
45
46// 2009-04 Please do not make this function static, it will break xlC build!
47inline bool NEED_MERGE(size_t current_count, size_t page_count)
48{
49 return current_count * 4 / 3 <= page_count;
50}
51
52// Default tree leaf and node page sizes in bytes.
53//
54// Avoid using very small values because overhead for each page is 28-32 bytes on
55// 32-bit platforms. Node pages are optimal to be significantly larger because
56// they are modified less often, but are searched much more often.
57//
58// Values below are fine-tuned for AMD Athlon 64 3000+ with DDR400 memory.
59const int LEAF_PAGE_SIZE = 400;
60const int NODE_PAGE_SIZE = 3000;
61
62// This is maximum level of tree nesting. 10^9 elements for binary tree case
63// should be more than enough. No checks are performed in code against overflow of this value
64const int MAX_TREE_LEVEL = 30;
65
66class MallocAllocator
67{
68public:
69 void *allocate(size_t size)
70 {
71 return malloc(size);
72 }
73 void deallocate(void *p)
74 {
75 free(p);
76 }
77};
78
79enum LocType { locEqual, locLess, locGreat, locGreatEqual, locLessEqual };
80
81// Fast and simple B+ tree of simple types.
82// Tree is always accessed via accessor classes. There is default accessor
83// built into the class to simplify programming in single-threaded
84// non-reentrant access model.
85//
86// Notes:
87//
88// 1) Items in the tree MUST be unique (this is performance optimization),
89// you can always convert set of non-unique items to a set of unique items with count
90// like this:
91// struct TreeItem
92// {
93// Value value;
94// int count;
95// static const Key& generate(void *sender, const TreeItem& item)
96// {
97// return KeyOfValue::generate(sender, value);
98// }
99// }
100// Small and simple (just a few lines) template derived from BePlusTree can be created
101// for this when real need arises. It will still be much faster than allowing duplicates
102// in BePlusTree itself
103//
104// 2) We could store ultimate item count for each node and make tree accessible like
105// an indexed dynamic array without increase of algorithm calculation costs (this is one
106// more classical B+ tree feature). This is also not done to improve tree performance a little
107//
108template <typename Value, typename Key = Value, typename Allocator = MallocAllocator,
109 typename KeyOfValue = DefaultKeyValue<Value>,
110 typename Cmp = DefaultComparator<Key> >
111class BePlusTree
112{
113 static const size_t LeafCount = LEAF_PAGE_SIZE / sizeof(Value);
114 static const size_t NodeCount = NODE_PAGE_SIZE / sizeof(void*);
115public:
116 explicit BePlusTree(Allocator *_pool)
117 : pool(_pool), level(0), root(NULL), defaultAccessor(this)
118 { }
119
120 explicit BePlusTree(Allocator& _pool)
121 : pool(&_pool), level(0), root(NULL), defaultAccessor(this)
122 { }
123
124 BePlusTree(Allocator *_pool, const BePlusTree& from)
125 : pool(_pool), level(0), root(NULL), defaultAccessor(this)
126 {
127 append(from);
128 }
129
130 BePlusTree& operator =(const BePlusTree& from)
131 {
132 clear();
133 append(from);
134 return *this;
135 }
136
137 void clear()
138 {
139 defaultAccessor.curr = NULL;
140
141 // Do not deallocate root page if tree is shallow
142 if (level == 0)
143 {
144 if (root) {
145 ((ItemList*) root)->clear();
146 }
147 return;
148 }
149
150 // Find first items page
151 void *temp = root;
152 for (int i = level; i > 0; i--)
153 temp = (*(NodeList *)temp)[0];
154 ItemList *items = (ItemList *)temp;
155
156 // Delete all items pages
157 NodeList *lists = items->parent;
158 while (items)
159 {
160 ItemList *t = items->next;
161 items->~ItemList();
162 pool->deallocate(items);
163 items = t;
164 }
165
166 // Delete all upper layers of tree
167 while (lists)
168 {
169 NodeList *list = lists;
170 lists = lists->parent;
171 while (list)
172 {
173 NodeList *t = list->next;
174 list->~NodeList();
175 pool->deallocate(list);
176 list = t;
177 }
178 }
179
180 // Initialize fields to make tree usable again
181 root = NULL;
182 level = 0;
183 }
184
185 ~BePlusTree()
186 {
187 clear();
188 pool->deallocate(root);
189 }
190
191 bool isEmpty() const
192 {
193 return root == NULL || (level == 0 && ((ItemList*) root)->getCount() == 0);
194 }
195
196 bool add(const Value& item) { return defaultAccessor.add(item); }
197
198 class ConstAccessor;
199 class Accessor;
200 // If item already exists method sets accessor's current position
201 // to found item's location and returns false.
202 // If item not exists method will add it to the tree and return true,
203 // not touching accessor's current position.
204 bool add(const Value& item, Accessor* accessor);
205
206 // Remove item. Current position moves to next item after this call.
207 // If next item doesn't exist method returns false
208 bool fastRemove() { return defaultAccessor.fastRemove(); }
209
210 bool isPositioned(const Key& key) const { return defaultAccessor.isPositioned(key); }
211
212 bool locate(const Key& key) { return defaultAccessor.locate(locEqual, key); }
213
214 bool locate(LocType lt, const Key& key) { return defaultAccessor.locate(lt, key); }
215
216 bool getFirst() { return defaultAccessor.getFirst(); }
217
218 bool getLast() { return defaultAccessor.getLast(); }
219
220 bool getNext() { return defaultAccessor.getNext(); }
221
222 bool getPrev() { return defaultAccessor.getPrev(); }
223
224 Value& current() const { return defaultAccessor.current(); }
225
226 // Returns true if this tree appears to contain more elements than the other
227 bool seemsBiggerThan(const BePlusTree& other) const
228 {
229 if (level != other.level)
230 return level > other.level;
231
232 if (level == 0)
233 {
234 if (root == NULL)
235 return other.root == NULL;
236 if (other.root == NULL)
237 return true;
238 return ((ItemList*) root)->getCount() > ((ItemList*) other.root)->getCount();
239 }
240
241 return ((NodeList*) root)->getCount() > ((NodeList*) other.root)->getCount();
242 }
243
244 // Compute approximate number of leafs in the tree
245 size_t approxCount() const
246 {
247 if (!root)
248 return 0;
249
250 if (level == 0)
251 return ((ItemList*) root)->getCount();
252
253 // Tree is large. Roughly estimate number of leaf nodes using number of
254 // items in root list and depth of the tree. Theoretically possible fill
255 // factor range for the tree on each level for current NEED_MERGE routine
256 // is [0.375, 1]. We take 3/5 = 0.6 as most probable case and
257 // play from there.
258 size_t items_per_node = LeafCount * 3 / 5;
259 for (int i = 1; i < level; i++)
260 items_per_node *= NodeCount * 3 / 5;
261
262 fb_assert(items_per_node);
263 return ((NodeList*)root)->getCount() * items_per_node;
264 }
265
266 // Compute approximate memory consumption for tree in bytes
267 size_t approxSize() const
268 {
269 if (!root)
270 return 0;
271
272 if (level == 0)
273 return sizeof(ItemList);
274
275 // Tree is large. Roughly estimate memory consumption using number
276 // of items in root list and depth of the tree. Approach to approximation
277 // is the same as in approxCount() routine above
278 size_t bytes_per_node = sizeof(ItemList);
279 for (int i = 1; i < level; i++)
280 bytes_per_node *= NodeCount * 3 / 5;
281
282 fb_assert(bytes_per_node);
283 return ((NodeList*)root)->getCount() * bytes_per_node;
284 }
285
286 void append(const BePlusTree& from)
287 {
288 // This is slow approach especially when used for assignment.
289 // Optimize it when need arises.
290 ConstAccessor accessor(&from);
291 if (accessor.getFirst())
292 {
293 do {
294 add(accessor.current());
295 } while (accessor.getNext());
296 }
297 }
298
299private:
300 BePlusTree(Allocator *_pool, void *rootPage) : pool(_pool), level(0),
301 root(new(rootPage) ItemList()), defaultAccessor(this) {}
302
303 class NodeList;
304
305 class ItemList : public SortedVector<Value, LeafCount, Key, KeyOfValue, Cmp>
306 {
307 public:
308 NodeList* parent;
309 ItemList* next;
310 ItemList* prev;
311
312 // Adds newly created item to doubly-linked list
313 ItemList(ItemList* items)
314 : parent(NULL)
315 {
316 if ((next = items->next))
317 next->prev = this;
318 prev = items;
319 items->next = this;
320 }
321 // Create first item in the linked list
322 ItemList() : parent(NULL), next(NULL), prev(NULL) {}
323
324 friend class BePlusTree;
325#ifndef _MSC_VER
326 friend class BePlusTree::NodeList;
327 friend class BePlusTree::Accessor;
328#endif
329 };
330
331 class NodeList : public SortedVector<void*, NodeCount, Key, NodeList, Cmp>
332 {
333 public:
334 // Adds newly created item to the doubly-linked list
335 NodeList(NodeList* items)
336 : parent(NULL)
337 {
338 if ((next = items->next))
339 next->prev = this;
340 prev = items;
341 items->next = this;
342 }
343 // Create first item in the linked list
344 NodeList() : parent(NULL), next(NULL), prev(NULL) {}
345
346 int level;
347 NodeList *parent;
348 NodeList *next, *prev;
349 static const Key& generate(const void *sender, void *item)
350 {
351 for (int lev = ((NodeList *)sender)->level; lev > 0; lev--)
352 item = *((NodeList *)item)->begin();
353
354 // ItemList reference below is ISO C++ compliant.
355 // If your compiler has broken name lookup sequence then conditionally
356 // add ItemList typedef for you compiler with whichever syntax it likes
357 return KeyOfValue::generate(item, *((ItemList *)item)->begin());
358 }
359 static void setNodeParentAndLevel(void* node, const int level, NodeList* parent)
360 {
361 if (level)
362 {
363 ((NodeList *)node)->parent = parent;
364 ((NodeList *)node)->level = level - 1;
365 }
366 else
367 ((ItemList *)node)->parent = parent;
368 }
369 static void setNodeParent(void* node, const int level, NodeList* parent)
370 {
371 if (level)
372 ((NodeList*) node)->parent = parent;
373 else
374 ((ItemList*) node)->parent = parent;
375 }
376 };
377
378public:
379 class ConstAccessor
380 {
381 public:
382 explicit ConstAccessor(const BePlusTree* in_tree) :
383 curr(NULL), curPos(0), tree(in_tree)
384 {}
385
386 bool locate(const Key& key)
387 {
388 return locate(locEqual, key);
389 }
390
391 // Position accessor on item having LocType relationship with given key
392 // If method returns false position of accessor is not defined.
393 bool locate(const LocType lt, const Key& key)
394 {
395 // Inlining is efficient here because LocType will be known in most cases
396 // and compiler will be able to eliminate most of code
397 void *list = tree->root;
398 if (!list)
399 return false; // Uninitialized tree
400
401 for (int lev = tree->level; lev; lev--)
402 {
403 size_t pos;
404 if (!((NodeList *)list)->find(key, pos))
405 {
406 if (pos > 0)
407 pos--;
408 }
409 list = (*(NodeList *)list)[pos];
410 }
411
412 curr = (ItemList *)list;
413 const bool found = curr->find(key, curPos);
414 switch (lt)
415 {
416 case locEqual:
417 return found;
418 case locGreatEqual:
419 if (curPos == curr->getCount())
420 {
421 curr = curr->next;
422 curPos = 0;
423 }
424 return found || curr;
425 case locLessEqual:
426 if (found)
427 return true;
428 // NOTE: fall into next case statement
429 case locLess:
430 if (curPos == 0)
431 {
432 curr = curr->prev;
433 if (!curr)
434 return false;
435 curPos = curr->getCount() - 1;
436 }
437 else
438 curPos--;
439 return true;
440 case locGreat:
441 if (found)
442 curPos++;
443 if (curPos == curr->getCount())
444 {
445 curr = curr->next;
446 curPos = 0;
447 }
448 return curr != 0;
449 }
450 return false;
451 }
452 // If method returns false it means list is empty and
453 // position of accessor is not defined.
454 bool getFirst()
455 {
456 void* items = tree->root;
457 if (!items)
458 return false; // Uninitialized tree
459
460 for (int i = tree->level; i > 0; i--)
461 items = (*(NodeList*) items)[0];
462 curr = (ItemList*) items;
463 curPos = 0;
464 return ((ItemList*) items)->getCount() != 0;
465 }
466 // If method returns false it means list is empty and
467 // position of accessor is not defined.
468 bool getLast()
469 {
470 void *items = tree->root;
471 if (!items)
472 return false; // Uninitialized tree
473
474 for (int i = tree->level; i > 0; i--)
475 items = (*(NodeList*) items)[((NodeList*) items)->getCount() - 1];
476 curr = (ItemList *)items;
477 if (((ItemList*) items)->getCount())
478 {
479 curPos = ((ItemList*) items)->getCount() - 1;
480 return true;
481 }
482 return false;
483 }
484 // Accessor position must be established via successful call to getFirst(),
485 // getLast() or locate() before you can call this method
486 bool getNext()
487 {
488 curPos++;
489 if (curPos >= curr->getCount())
490 {
491 if (curr->next)
492 {
493 curr = curr->next;
494 curPos = 0;
495 }
496 else
497 {
498 // If we reached end of the list just return false and do not invalidate position
499 curPos--;
500 return false;
501 }
502 }
503 return true;
504 }
505 // Accessor position must be established via successful call to getFirst(),
506 // getLast() or locate() before you can call this method
507 bool getPrev()
508 {
509 if (curPos == 0)
510 {
511 if (curr->prev)
512 {
513 curr = curr->prev;
514 curPos = curr->getCount() - 1;
515 }
516 else
517 {
518 // If we reached beginning of the list just return false and do not invalidate position
519 curPos = 0;
520 return false;
521 }
522 }
523 else
524 curPos--;
525 return true;
526 }
527
528 const Value& current() const { return (*curr)[curPos]; }
529
530 protected:
531
532 // Returns true if current position is valid and already points to the given key.
533 // Note that we can't guarantee validity of current position if tree is accessed
534 // by different Accessor's. Therefore this method is private and can be used only
535 // via tree::defaultAccessor.
536 bool isPositioned(const Key& key) const
537 {
538 return (curr && curPos < curr->getCount() && KeyOfValue::generate(this, current()) == key);
539 }
540
541 ItemList* curr;
542 size_t curPos;
543
544 private:
545 const BePlusTree* tree;
546
547 friend class BePlusTree;
548 }; // class ConstAccessor
549
550 class Accessor : public ConstAccessor
551 {
552 public:
553 explicit Accessor(BePlusTree* in_tree) :
554 ConstAccessor(in_tree), tree(in_tree)
555 {}
556
557 bool add(const Value& item)
558 {
559 return tree->add(item, this);
560 }
561
562 // Remove item. Current position moves to next item after this call.
563 // If next item doesn't exist method returns false
564 bool fastRemove()
565 {
566 // invalidate current position of defaultAccessor
567 // if i'm not a defaultAccessor
568 if (this != &tree->defaultAccessor)
569 tree->defaultAccessor.curr = NULL;
570
571 if (!tree->level)
572 {
573 this->curr->remove(this->curPos);
574 return this->curPos < this->curr->getCount();
575 }
576 if (this->curr->getCount() == 1)
577 {
578 // Only one node left in the current page. We cannot remove it directly
579 // because is would invalidate our tree structure
580 fb_assert(this->curPos == 0);
581 ItemList* temp;
582 if ((temp = this->curr->prev) && NEED_MERGE(temp->getCount(), LeafCount))
583 {
584 temp = this->curr->next;
585 tree->_removePage(0, this->curr);
586 this->curr = temp;
587 return this->curr;
588 }
589 if ((temp = this->curr->next) && NEED_MERGE(temp->getCount(), LeafCount))
590 {
591 tree->_removePage(0, this->curr);
592 this->curr = temp;
593 return true;
594 }
595 if ((temp = this->curr->prev))
596 {
597 (*this->curr)[0] = (*temp)[temp->getCount() - 1];
598 temp->shrink(temp->getCount() - 1);
599 this->curr = this->curr->next;
600 return this->curr;
601 }
602 if ((temp = this->curr->next))
603 {
604 (*this->curr)[0] = (*temp)[0];
605 temp->remove(0);
606 return true;
607 }
608 // It means the tree is broken
609 fb_assert(false);
610 return false;
611 }
612 this->curr->remove(this->curPos);
613 ItemList *temp;
614 if ((temp = this->curr->prev) &&
615 NEED_MERGE(temp->getCount() + this->curr->getCount(), LeafCount))
616 {
617 // After join upper levels of the tree remain stable because join doesn't change
618 // key of the page. The same applies to lower case too.
619 this->curPos += temp->getCount();
620 temp->join(*this->curr);
621 tree->_removePage(0, this->curr);
622 this->curr = temp;
623 // The code below will adjust current position if needed
624 }
625 else
626 {
627 if ((temp = this->curr->next) &&
628 NEED_MERGE(temp->getCount() + this->curr->getCount(), LeafCount))
629 {
630 this->curr->join(*temp);
631 tree->_removePage(0, temp);
632 return true;
633 }
634 }
635 if (this->curPos >= this->curr->getCount())
636 {
637 fb_assert(this->curPos == this->curr->getCount());
638 this->curPos = 0;
639 this->curr = this->curr->next;
640 return this->curr;
641 }
642 return true;
643 }
644
645 Value& current() const { return (*this->curr)[this->curPos]; }
646
647 private:
648 BePlusTree* tree;
649
650 friend class BePlusTree;
651 }; // class Accessor
652
653private:
654 Allocator* pool;
655 int level;
656 void* root;
657 Accessor defaultAccessor;
658
659 void _removePage(int level, void *node);
660
661 friend class MemoryPool;
662 friend class NodeList;
663 friend class Accessor;
664};
665
666// ************************ BePlusTree implementation ******************
667
668template <typename Value, typename Key, typename Allocator, typename KeyOfValue, typename Cmp>
669bool BePlusTree<Value, Key, Allocator, KeyOfValue, Cmp>::add(const Value& item, Accessor* accessor)
670{
671 // Finish initialization of the tree if necessary
672 if (!root)
673 root = new (pool->allocate(sizeof(ItemList))) ItemList();
674
675 // Find leaf page for our item
676 void *vList = this->root;
677 const Key& key = KeyOfValue::generate(NULL, item);
678 for (int lev = this->level; lev > 0; lev--)
679 {
680 size_t pos;
681 if (!((NodeList *)vList)->find(key, pos))
682 {
683 if (pos > 0)
684 pos--;
685 }
686 vList = (*(NodeList *)vList)[pos];
687 }
688
689 ItemList *leaf = (ItemList *)vList;
690
691 size_t pos;
692 if (leaf->find(key, pos))
693 {
694 if (accessor)
695 {
696 accessor->curr = leaf;
697 accessor->curPos = pos;
698 }
699 return false;
700 }
701
702 if (leaf->getCount() < LeafCount)
703 {
704 leaf->insert(pos, item);
705 return true;
706 }
707
708 // Page is full. Look up nearby pages for space if possible
709 ItemList *temp;
710 // Adding items to the next page is cheaper in most cases that
711 // is why it is checked first
712 if ((temp = leaf->next) && temp->getCount() < LeafCount)
713 {
714 // Found space on the next page
715 if (pos == LeafCount)
716 {
717 // This would be ok if items were unique: temp->insert(0, item);
718 // The same applies to all simular cases below
719 temp->insert(0, item);
720 }
721 else
722 {
723 // Maybe splitting array by half would make things faster ?
724 // It should do it in case of random size items.
725 // It would make things slower in case of sequental items addition.
726 // Let's leave it as is now.
727 temp->insert(0, (*leaf)[LeafCount - 1]);
728 leaf->shrink(LeafCount - 1);
729 leaf->insert(pos, item);
730 }
731 return true;
732 }
733
734 if ((temp = leaf->prev) && temp->getCount() < LeafCount)
735 {
736 // Found space on the previous page
737 if (pos == 0) {
738 temp->insert(temp->getCount(), item);
739 }
740 else
741 {
742 temp->insert(temp->getCount(), (*leaf)[0]);
743 leaf->remove(0);
744 leaf->insert(pos - 1, item);
745 }
746 return true;
747 }
748
749 // Nearby pages are also full. We need to add one more leaf page to the list
750 // This shouldn't happen very often. Traverse tree up trying to add node
751
752 // No re-enterance allowed !!!
753 // Since we haven't done anything with tree yet, thus we don't need to recover
754 // anything in case of error thrown at this allocation here
755 ItemList *newLeaf = new(this->pool->allocate(sizeof(ItemList))) ItemList(leaf);
756
757 // Start building recovery map.
758 // This array contains index of the element we try to add on page of each level
759 // MAP_NEW_PAGE means that element is on new page
760 // In case of low memory condition we use this data to recover to innocent state
761 size_t recovery_map[MAX_TREE_LEVEL];
762 const size_t MAP_NEW_PAGE = ~((size_t) 0);
763
764 if (pos == LeafCount)
765 {
766 newLeaf->insert(0, item);
767 recovery_map[0] = MAP_NEW_PAGE;
768 }
769 else
770 {
771 newLeaf->insert(0, (*leaf)[LeafCount - 1]);
772 leaf->shrink(leaf->getCount() - 1);
773 leaf->insert(pos, item);
774 recovery_map[0] = pos;
775 }
776
777 void *newNode = newLeaf;
778 NodeList *nodeList = leaf->parent;
779 int curLevel = 0;
780 try {
781 while (nodeList)
782 {
783 // Easy case. We've got some space on the node page
784 if (nodeList->getCount() < NodeCount)
785 {
786 NodeList::setNodeParentAndLevel(newNode, curLevel, nodeList);
787 nodeList->add(newNode);
788 return true;
789 }
790
791 // Page is full. Look up nearby pages for space if possible
792 nodeList->find(NodeList::generate(nodeList, newNode), pos);
793 NodeList *list;
794
795 if ((list = nodeList->next) && list->getCount() < NodeCount)
796 {
797 // Found space on the next page
798 if (pos == NodeCount)
799 {
800 NodeList::setNodeParentAndLevel(newNode, curLevel, list);
801 list->insert(0, newNode);
802 }
803 else
804 {
805 void *t = (*nodeList)[NodeCount - 1];
806 NodeList::setNodeParent(t, curLevel, list);
807 list->insert(0, t);
808 nodeList->shrink(NodeCount - 1);
809 NodeList::setNodeParentAndLevel(newNode, curLevel, nodeList);
810 nodeList->insert(pos, newNode);
811 }
812 return true;
813 }
814
815 if ((list = nodeList->prev) && list->getCount() < NodeCount)
816 {
817 // Found space on the previous page
818 if (pos == 0)
819 {
820 NodeList::setNodeParentAndLevel(newNode, curLevel, list);
821 list->insert(list->getCount(), newNode);
822 }
823 else
824 {
825 void *t = (*nodeList)[0];
826 NodeList::setNodeParent(t, curLevel, list);
827 list->insert(list->getCount(), t);
828 nodeList->remove(0);
829 NodeList::setNodeParentAndLevel(newNode, curLevel, nodeList);
830 nodeList->insert(pos - 1, newNode);
831 }
832 return true;
833 }
834
835 // No space found. Allocate NodeList page and climb up the tree
836
837 // No re-enterance allowed !!!
838 // Exceptions from this point
839 // are cleaned up lower
840 NodeList *newList = new(this->pool->allocate(sizeof(NodeList))) NodeList(nodeList);
841
842 if (pos == NodeCount)
843 {
844 NodeList::setNodeParentAndLevel(newNode, curLevel, newList);
845 newList->insert(0, newNode);
846 recovery_map[curLevel + 1] = MAP_NEW_PAGE;
847 }
848 else
849 {
850 void *t = (*nodeList)[NodeCount - 1];
851 NodeList::setNodeParent(t, curLevel, newList);
852 newList->insert(0, t);
853 nodeList->shrink(NodeCount - 1);
854 NodeList::setNodeParentAndLevel(newNode, curLevel, nodeList);
855 nodeList->insert(pos, newNode);
856 recovery_map[curLevel + 1] = pos;
857 }
858 newNode = newList;
859 nodeList = nodeList->parent;
860 curLevel++;
861 }
862
863 // This is the worst case. We reached the top of tree but were not able to insert node
864 // Allocate new root page and increase level of our tree
865 nodeList = new(this->pool->allocate(sizeof(NodeList))) NodeList();
866 nodeList->level = this->level;
867 nodeList->insert(0, this->root);
868 NodeList::setNodeParentAndLevel(newNode, this->level, nodeList);
869 NodeList::setNodeParent(this->root, this->level, nodeList);
870 nodeList->add(newNode);
871 this->root = nodeList;
872 this->level++;
873 }
874 catch (const Firebird::Exception&)
875 {
876 // Recover tree to innocent state
877 while (curLevel)
878 {
879 NodeList *itemL = reinterpret_cast<NodeList*>(newNode);
880 void *lower;
881 if (recovery_map[curLevel] == MAP_NEW_PAGE) {
882 lower = (*itemL)[0];
883 }
884 else
885 {
886 lower = (*itemL->prev)[recovery_map[curLevel]];
887 itemL->prev->remove(recovery_map[curLevel]);
888 itemL->prev->insert(itemL->prev->getCount(), (*itemL)[0]);
889 NodeList::setNodeParent((*itemL)[0], curLevel - 1, itemL->prev);
890 }
891 itemL->~NodeList();
892 this->pool->deallocate(newNode);
893 newNode = lower;
894 curLevel--;
895 }
896 ItemList *itemL2 = reinterpret_cast<ItemList*>(newNode);
897 if (recovery_map[0] != MAP_NEW_PAGE)
898 {
899 itemL2->prev->remove(recovery_map[0]);
900 itemL2->prev->insert(itemL2->prev->getCount(), (*itemL2)[0]);
901 }
902 itemL2->~ItemList();
903 this->pool->deallocate(newNode);
904 throw;
905 }
906 return true;
907}
908
909template <typename Value, typename Key, typename Allocator, typename KeyOfValue, typename Cmp>
910void BePlusTree<Value, Key, Allocator, KeyOfValue, Cmp>::_removePage(const int nodeLevel, void *node)
911{
912 NodeList *list;
913 // Get parent and adjust the links
914 if (nodeLevel)
915 {
916 NodeList *temp = (NodeList *)node;
917 if (temp->prev)
918 temp->prev->next = temp->next;
919 if (temp->next)
920 temp->next->prev = temp->prev;
921 list = temp->parent;
922 }
923 else
924 {
925 ItemList *temp = (ItemList *)node;
926 if (temp->prev)
927 temp->prev->next = temp->next;
928 if (temp->next)
929 temp->next->prev = temp->prev;
930 list = temp->parent;
931 }
932
933 if (list->getCount() == 1)
934 {
935 // Only one node left in the list. We cannot remove it directly
936 // because is would invalidate our tree structure
937 NodeList *temp;
938 if ((temp = list->prev) && NEED_MERGE(temp->getCount(), NodeCount)) {
939 _removePage(nodeLevel + 1, list);
940 }
941 else
942 if ((temp = list->next) && NEED_MERGE(temp->getCount(), NodeCount)) {
943 _removePage(nodeLevel + 1, list);
944 }
945 else
946 if ((temp = list->prev))
947 {
948 NodeList::setNodeParent(((*list)[0] = (*temp)[temp->getCount() - 1]), nodeLevel, list);
949 temp->shrink(temp->getCount() - 1);
950 }
951 else
952 if ((temp = list->next))
953 {
954 NodeList::setNodeParent(((*list)[0] = (*temp)[0]), nodeLevel, list);
955 temp->remove(0);
956 }
957 else
958 {
959 // It means the tree is broken
960 fb_assert(false);
961 }
962 }
963 else
964 {
965 size_t pos;
966#ifndef DEV_BUILD
967 list->find(NodeList::generate(list, node), pos);
968#else
969 const bool found = list->find(NodeList::generate(list, node), pos);
970 fb_assert(found);
971#endif
972 list->remove(pos);
973
974 if (list == root && list->getCount() == 1)
975 {
976 // We reached the top of the tree and were asked to modify root
977 // page so only one node will be left in this case.
978 // Reduce the level of the tree
979 root = (*list)[0];
980 level--;
981 NodeList::setNodeParent(root, level, NULL);
982 list->~NodeList();
983 pool->deallocate(list);
984 }
985 else
986 {
987 NodeList *temp;
988 if ((temp = list->prev) && NEED_MERGE(temp->getCount() + list->getCount(), NodeCount))
989 {
990 // After join upper levels of the tree remain stable because join doesn't change
991 // key of the page. The same applies to lower case too.
992 temp->join(*list);
993 for (size_t i = 0; i < list->getCount(); i++)
994 NodeList::setNodeParent((*list)[i], nodeLevel, temp);
995 _removePage(nodeLevel + 1, list);
996 }
997 else
998 if ((temp = list->next) && NEED_MERGE(temp->getCount() + list->getCount(), NodeCount))
999 {
1000 list->join(*temp);
1001 for (size_t i = 0; i < temp->getCount(); i++)
1002 NodeList::setNodeParent((*temp)[i], nodeLevel, list);
1003 _removePage(nodeLevel + 1, temp);
1004 }
1005 }
1006 }
1007
1008 if (nodeLevel)
1009 ((NodeList *)node)->~NodeList();
1010 else
1011 ((ItemList *)node)->~ItemList();
1012 pool->deallocate(node);
1013}
1014
1015} // namespace Firebird
1016
1017#endif // CLASSES_TREE_H
1018
1019