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 | |
40 | namespace 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! |
47 | inline 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. |
59 | const int LEAF_PAGE_SIZE = 400; |
60 | const 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 |
64 | const int MAX_TREE_LEVEL = 30; |
65 | |
66 | class MallocAllocator |
67 | { |
68 | public: |
69 | void *allocate(size_t size) |
70 | { |
71 | return malloc(size); |
72 | } |
73 | void deallocate(void *p) |
74 | { |
75 | free(p); |
76 | } |
77 | }; |
78 | |
79 | enum 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 | // |
108 | template <typename Value, typename Key = Value, typename Allocator = MallocAllocator, |
109 | typename KeyOfValue = DefaultKeyValue<Value>, |
110 | typename Cmp = DefaultComparator<Key> > |
111 | class BePlusTree |
112 | { |
113 | static const size_t LeafCount = LEAF_PAGE_SIZE / sizeof(Value); |
114 | static const size_t NodeCount = NODE_PAGE_SIZE / sizeof(void*); |
115 | public: |
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 | |
299 | private: |
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 | |
378 | public: |
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 | |
653 | private: |
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 | |
668 | template <typename Value, typename Key, typename Allocator, typename KeyOfValue, typename Cmp> |
669 | bool 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 | |
909 | template <typename Value, typename Key, typename Allocator, typename KeyOfValue, typename Cmp> |
910 | void 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 | |