• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision98 (tree)
Time2018-05-13 20:57:32
Authorquiret

Log Message

- added support for same values in AVLTree implementation using nodestacks
- added unittest that checks support for same values

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 97)
+++ common/sdk/AVLTree.h (revision 98)
@@ -13,6 +13,7 @@
1313 #define _AVL_TREE_IMPLEMENTATION_
1414
1515 #include <sdk/MacroUtils.h>
16+#include <sdk/rwlist.hpp>
1617 #include <assert.h>
1718 #include <algorithm>
1819
@@ -21,17 +22,35 @@
2122 // this struct because the NativeHeapAllocator is being issued with random memory
2223 // request sizes and we ought to decide fast in which free slot allocation might be
2324 // possible.
24-// YOU CANNOT STORE SAME VALUES IN AN AVL TREE!
25+// Note that this is NOT a naive implementation of AVL tree.
2526
2627 // Useful to fetch an actual struct if AVLNode is a struct-member.
2728 #define AVL_GETITEM( type, nodePtr, nodeMemb ) ( (type*)( (char*)nodePtr - offsetof(type, nodeMemb) ) )
2829
30+// TODO: we actually HAVE TO be able to store SAME VALUES inside of our AVL tree implementation.
31+// this should be managed by stacking nodes if they happen to be the same.
32+
2933 // Has to be less-than comparable, in a total order.
3034 struct AVLNode
3135 {
32- size_t height;
33- AVLNode *parent;
34- AVLNode *left, *right;
36+ // TODO: find a way to segregate the AVL default fields from the nodestack field so that
37+ // it is easier to maintain this thing.
38+
39+ AVLNode *parent; // if parent points to itself, then we are part of a node stack.
40+ union
41+ {
42+ struct
43+ {
44+ size_t height;
45+ AVLNode *owned_nodestack; // if we have a nodestack, then this member points at it.
46+ AVLNode *left, *right; // AVL structure default members.
47+ };
48+ struct
49+ {
50+ AVLNode *nodestack_owner; // if nodestack member, then this points to the nodestack holder.
51+ AVLNode *prev, *next; // double-linked list in case of node stack member.
52+ };
53+ };
3554 };
3655
3756 // Should never be thrown, but who knows?
@@ -64,13 +83,13 @@
6483 }
6584
6685 private:
67- AINLINE size_t height_func( size_t leftHeight, size_t rightHeight )
86+ static AINLINE size_t height_func( size_t leftHeight, size_t rightHeight )
6887 {
6988 // So that we can choose a specific implementation of max function.
7089 return std::max( leftHeight, rightHeight );
7190 }
7291
73- AINLINE size_t calc_height_of_node( AVLNode *firstNode, AVLNode *secondNode )
92+ static AINLINE size_t calc_height_of_node( AVLNode *firstNode, AVLNode *secondNode )
7493 {
7594 // Calculate the maximum number of nodes that are on a path to the bottom in a binary tree.
7695
@@ -340,7 +359,9 @@
340359 }
341360
342361 public:
343- inline bool Insert( AVLNode *node )
362+ // Note that we have no more failure case because our AVL tree implementation does support adding
363+ // multiple same values.
364+ inline void Insert( AVLNode *node )
344365 {
345366 // Find the position to insert our new node at.
346367 AVLNode *parent;
@@ -350,8 +371,24 @@
350371
351372 if ( iter != nullptr )
352373 {
353- // We already have found a node, so quit.
354- return false;
374+ // We already have found a node, so we have to make the new node part of the node stack!
375+ node->parent = node;
376+ node->nodestack_owner = iter;
377+
378+ AVLNode *nodestack = iter->owned_nodestack;
379+
380+ if ( nodestack == nullptr )
381+ {
382+ LIST_CLEAR( *node );
383+
384+ iter->owned_nodestack = node;
385+ }
386+ else
387+ {
388+ LIST_INSERT( *nodestack, *node );
389+ }
390+
391+ return;
355392 }
356393 }
357394
@@ -363,12 +400,11 @@
363400 node->left = nullptr;
364401 node->right = nullptr;
365402 node->parent = parent;
403+ node->owned_nodestack = nullptr;
366404
367405 // Update to the very top all trees that have been modified.
368406 // This is much more efficient than doing a recursive method.
369407 update_invalidated_tree_height( parent );
370-
371- return true;
372408 }
373409
374410 private:
@@ -395,77 +431,146 @@
395431 return curMax;
396432 }
397433
398- AINLINE void remove_node( AVLNode *node, AVLNode **nodePtr, AVLNode *parent )
434+ static AINLINE void remove_nodestack_member( AVLNode *node, AVLNode *nodestack_owner )
399435 {
400- AVLNode *leftChild = node->left;
401- AVLNode *rightChild = node->right;
436+ // Remove us from the nodestack.
437+ bool is_empty = LIST_EMPTY( *node );
402438
403- if ( leftChild == nullptr )
439+ if ( is_empty )
404440 {
405- *nodePtr = rightChild;
441+ // There is no more nodestack on the owner.
442+ assert( nodestack_owner != nullptr );
443+ assert( nodestack_owner == node->nodestack_owner );
406444
407- if ( rightChild != nullptr )
445+ nodestack_owner->owned_nodestack = nullptr;
446+ }
447+ else
448+ {
449+ // Just remove us from the nodestack.
450+ if ( nodestack_owner->owned_nodestack == node )
408451 {
409- rightChild->parent = parent;
452+ nodestack_owner->owned_nodestack = node->next;
410453 }
454+
455+ LIST_REMOVE( *node );
411456 }
412- else if ( rightChild == nullptr )
457+ }
458+
459+ static AINLINE void inplace_node_replace(
460+ size_t nodeHeight, AVLNode **nodePtr, AVLNode *leftChild, AVLNode *rightChild, AVLNode *parent, AVLNode *owned_nodestack,
461+ AVLNode *replaceBy
462+ )
463+ {
464+ // Replace nodes.
465+ replaceBy->parent = parent;
466+ replaceBy->left = leftChild;
467+ replaceBy->right = rightChild;
468+ replaceBy->height = nodeHeight;
469+ replaceBy->owned_nodestack = owned_nodestack;
470+
471+ // If we took over a live nodestack, then we have to update the nodestack owners on the members.
472+ if ( owned_nodestack != nullptr )
413473 {
414- *nodePtr = leftChild;
474+ AVLNode *curnode = owned_nodestack;
415475
416- if ( leftChild != nullptr )
476+ do
417477 {
418- leftChild->parent = parent;
478+ curnode->nodestack_owner = replaceBy;
479+
480+ curnode = curnode->next;
419481 }
482+ while ( curnode != owned_nodestack );
420483 }
421- else
484+
485+ *nodePtr = replaceBy;
486+
487+ // Update parents.
488+ if ( leftChild != nullptr )
422489 {
423- // Pretty complicated situation.
424- AVLNode **closestReplacementPtr = &node->left;
425- AVLNode *closestReplacement = FindMaxNode( leftChild, closestReplacementPtr );
490+ leftChild->parent = replaceBy;
491+ }
426492
427- // Now we perform what someone usually has to do when updating the value of a node.
428- // But this is optimized to keep the pointers valid.
493+ if ( rightChild != nullptr )
494+ {
495+ rightChild->parent = replaceBy;
496+ }
497+ }
429498
430- // Remove the closest node.
431- // We know that the node has no right child, because it is the maximum in its subtree.
499+ AINLINE void remove_node( AVLNode *node, AVLNode **nodePtr, AVLNode *parent )
500+ {
501+ // We assume that node is NOT part of a nodestack!
502+ assert( parent != node );
503+
504+ AVLNode *leftChild = node->left;
505+ AVLNode *rightChild = node->right;
506+
507+ // If we have a nodestack, then we just shedule the first member of the nodestack to be new member of the AVL tree.
508+ if ( AVLNode *new_node = node->owned_nodestack )
509+ {
510+ // Remove it from the nodestack.
511+ remove_nodestack_member( new_node, node );
512+
513+ // Set it in-place of node.
514+ inplace_node_replace(
515+ node->height, nodePtr, leftChild, rightChild, parent, node->owned_nodestack,
516+ new_node
517+ );
518+ }
519+ else
520+ {
521+ if ( leftChild == nullptr )
432522 {
433- *closestReplacementPtr = closestReplacement->left;
523+ *nodePtr = rightChild;
434524
435- update_invalidated_tree_height( closestReplacement->parent );
525+ if ( rightChild != nullptr )
526+ {
527+ rightChild->parent = parent;
528+ }
436529 }
530+ else if ( rightChild == nullptr )
531+ {
532+ *nodePtr = leftChild;
437533
438- // We need to update members because they could be out-of-date.
439- parent = node->parent;
440- leftChild = node->left;
441- rightChild = node->right;
534+ if ( leftChild != nullptr )
535+ {
536+ leftChild->parent = parent;
537+ }
538+ }
539+ else
540+ {
541+ // Pretty complicated situation.
542+ AVLNode **closestReplacementPtr = &node->left;
543+ AVLNode *closestReplacement = FindMaxNode( leftChild, closestReplacementPtr );
442544
443- nodePtr = get_node_src_ptr( parent, node );
545+ // Now we perform what someone usually has to do when updating the value of a node.
546+ // But this is optimized to keep the pointers valid.
444547
445- // Replace nodes.
446- closestReplacement->parent = parent;
447- closestReplacement->left = leftChild;
448- closestReplacement->right = rightChild;
449- closestReplacement->height = node->height;
548+ // Remove the closest node.
549+ // We know that the node has no right child, because it is the maximum in its subtree.
550+ {
551+ *closestReplacementPtr = closestReplacement->left;
450552
451- *nodePtr = closestReplacement;
553+ update_invalidated_tree_height( closestReplacement->parent );
554+ }
452555
453- // Now closestReplacement takes the role of node.
556+ // We need to update members because they could be out-of-date.
557+ parent = node->parent;
558+ leftChild = node->left;
559+ rightChild = node->right;
454560
455- // Update parents.
456- if ( leftChild != nullptr )
457- {
458- leftChild->parent = closestReplacement;
561+ nodePtr = get_node_src_ptr( parent, node );
562+
563+ inplace_node_replace(
564+ node->height, nodePtr, leftChild, rightChild, parent, nullptr,
565+ closestReplacement
566+ );
567+
568+ // Now closestReplacement takes the role of node.
459569 }
460570
461- if ( rightChild != nullptr )
462- {
463- rightChild->parent = closestReplacement;
464- }
571+ // Update height of the changed tree.
572+ update_invalidated_tree_height( parent );
465573 }
466-
467- // Update height of the changed tree.
468- update_invalidated_tree_height( parent );
469574 }
470575
471576 public:
@@ -476,21 +581,51 @@
476581
477582 AVLNode *iter = ScanForNodePosition( node, iterPtr, parent );
478583
479- if ( iter == nullptr || iter != node )
584+ if ( iter == nullptr )
480585 {
481586 return false;
482587 }
483588
589+ // Check if it is either this node or part of the node stack.
590+ if ( iter != node )
591+ {
592+ if ( AVLNode *nodestack = iter->owned_nodestack )
593+ {
594+ AVLNode *curnode = nodestack;
595+
596+ do
597+ {
598+ if ( curnode == node )
599+ {
600+ return true;
601+ }
602+
603+ curnode = curnode->next;
604+ }
605+ while ( curnode != nodestack );
606+
607+ return false;
608+ }
609+ }
610+
484611 return true;
485612 }
486-
613+
487614 inline void RemoveByNodeFast( AVLNode *node )
488615 {
489616 // A faster removal method which assumes that node does really reside inside this AVL tree.
490617 AVLNode *parent = node->parent;
491- AVLNode **iterPtr = get_node_src_ptr( parent, node );
492618
493- remove_node( node, iterPtr, parent );
619+ if ( parent == node )
620+ {
621+ remove_nodestack_member( node, node->nodestack_owner );
622+ }
623+ else
624+ {
625+ AVLNode **iterPtr = get_node_src_ptr( parent, node );
626+
627+ remove_node( node, iterPtr, parent );
628+ }
494629 }
495630
496631 inline bool RemoveByNode( AVLNode *node )
@@ -512,6 +647,26 @@
512647 if ( node != iter )
513648 {
514649 // It is not the same node!
650+ // It could still be part of its nodestack.
651+ if ( AVLNode *nodestack = iter->owned_nodestack )
652+ {
653+ AVLNode *curnode = nodestack;
654+
655+ do
656+ {
657+ if ( curnode == node )
658+ {
659+ // Found it.
660+ remove_nodestack_member( node, iter );
661+
662+ return true;
663+ }
664+
665+ curnode = curnode->next;
666+ }
667+ while ( curnode != nodestack );
668+ }
669+
515670 return false;
516671 }
517672 }
@@ -523,6 +678,25 @@
523678
524679 private:
525680 template <typename callbackType>
681+ static AINLINE void call_for_each_node_for_nodestack( AVLNode *walkNode, const callbackType& cb )
682+ {
683+ cb( walkNode );
684+
685+ if ( AVLNode *nodestack = walkNode->owned_nodestack )
686+ {
687+ AVLNode *curnode = nodestack;
688+
689+ do
690+ {
691+ cb( curnode );
692+
693+ curnode = curnode->next;
694+ }
695+ while ( curnode != nodestack );
696+ }
697+ }
698+
699+ template <typename callbackType>
526700 static AINLINE void walk_iteratively( AVLNode *walkNode, const callbackType& cb )
527701 {
528702 AVLNode *curNode = walkNode;
@@ -537,7 +711,7 @@
537711 else
538712 {
539713 // Now we can iterate this node.
540- cb( curNode );
714+ call_for_each_node_for_nodestack( curNode, cb );
541715
542716 // Iterate the right.
543717 if ( AVLNode *rightNode = curNode->right )
@@ -556,7 +730,7 @@
556730
557731 if ( curNode == parent->left )
558732 {
559- cb( parent );
733+ call_for_each_node_for_nodestack( parent, cb );
560734
561735 nextChild = parent->right;
562736 }
@@ -609,8 +783,16 @@
609783 Walk(
610784 []( AVLNode *node )
611785 {
612- if ( AVLNode *parent = node->parent )
786+ // Ignore any nodestack member.
787+ AVLNode *parent = node->parent;
788+
789+ if ( parent == node )
613790 {
791+ return;
792+ }
793+
794+ if ( parent )
795+ {
614796 if ( parent->left == node )
615797 {
616798 assert( is_node_less_than( node, parent ) == true );
--- unittests/src/avltree.cpp (revision 97)
+++ unittests/src/avltree.cpp (revision 98)
@@ -60,10 +60,7 @@
6060
6161 curItem.my_number = my_nums[n];
6262
63- bool didInsert = tree.Insert( &curItem.node );
64-
65- assert( didInsert == true );
66-
63+ tree.Insert( &curItem.node );
6764 tree.Validate();
6865 }
6966
@@ -96,11 +93,12 @@
9693
9794 my_item.my_number = (int)n;
9895
99- bool didInsert = tree.Insert( &my_item.node );
100-
101- assert( didInsert == true );
96+ tree.Insert( &my_item.node );
10297 }
10398
99+ // Validate all connections.
100+ tree.Validate();
101+
104102 size_t curHeight = tree.GetTreeHeight();
105103
106104 assert( curHeight < std::log2( NUM_ITEMS_TO_INSERT ) * 2 );
@@ -126,4 +124,63 @@
126124 delete [] items;
127125 }
128126 printf( "ok.\n" );
127+
128+ printf( "testing simple AVL tree same insertion and removal..." );
129+ {
130+ AVLTree <IntegerItem> tree;
131+
132+ IntegerItem first;
133+ first.my_number = 1;
134+
135+ IntegerItem second;
136+ second.my_number = 1;
137+
138+ tree.Insert( &first.node );
139+ tree.Insert( &second.node );
140+
141+ tree.Validate();
142+
143+ tree.RemoveByNodeFast( &first.node );
144+ tree.RemoveByNodeFast( &second.node );
145+ }
146+ printf( "ok.\n" );
147+
148+ printf( "testing massive AVL tree same insertion and removal..." );
149+ {
150+ AVLTree <IntegerItem> tree;
151+
152+ static constexpr size_t NUM_ITEMS_TO_INSERT = 1000000;
153+
154+ IntegerItem *items = new IntegerItem[ NUM_ITEMS_TO_INSERT ];
155+
156+ for ( size_t n = 0; n < NUM_ITEMS_TO_INSERT; n++ )
157+ {
158+ IntegerItem& my_item = items[n];
159+
160+ my_item.my_number = (int)( n % 1000 );
161+
162+ tree.Insert( &my_item.node );
163+ }
164+
165+ // Validate all connections.
166+ tree.Validate();
167+
168+ // Remove all items again.
169+ for ( size_t n = 0; n < NUM_ITEMS_TO_INSERT; n++ )
170+ {
171+ IntegerItem& item = items[n];
172+
173+ tree.RemoveByNodeFast( &item.node );
174+ }
175+
176+ // Should be valid.
177+ tree.Validate();
178+
179+ // And have no more height.
180+ assert( tree.GetTreeHeight() == 0 );
181+
182+ // Should be okay to just free this thing.
183+ delete [] items;
184+ }
185+ printf( "ok.\n" );
129186 }
\ No newline at end of file
Show on old repository browser