• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision120 (tree)
Time2018-09-08 15:09:29
Authorquiret

Log Message

- fixed a bug where we did not iterate over nodestack members due to a bug caused by code refactoring (while-loop, meow)
- added the ability to move AVLTree nodes memory locations without breaking things (you must obey strict validity-rules!)
- added some more unit tests to AVLTree to iron out more issues

Change Summary

Incremental Difference

--- unittests/src/avltree.cpp (revision 119)
+++ unittests/src/avltree.cpp (revision 120)
@@ -15,6 +15,20 @@
1515
1616 return ( leftItem->my_number < rightItem->my_number );
1717 }
18+
19+ static AINLINE bool IsNodeLessThanValue( const AVLNode *left, int right )
20+ {
21+ IntegerItem *leftItem = AVL_GETITEM( IntegerItem, left, node );
22+
23+ return ( leftItem->my_number < right );
24+ }
25+
26+ static AINLINE bool IsNodeGreaterThanValue( const AVLNode *left, int right )
27+ {
28+ IntegerItem *leftItem = AVL_GETITEM( IntegerItem, left, node );
29+
30+ return ( leftItem->my_number > right );
31+ }
1832 };
1933
2034 static void check_avl_sort( AVLTree <IntegerItem>& tree, bool hasSameNumbers = false )
@@ -229,4 +243,71 @@
229243 delete [] items;
230244 }
231245 printf( "ok.\n" );
246+
247+ printf( "testing AVL tree nodestack integration..." );
248+ {
249+ AVLTree <IntegerItem> tree;
250+
251+ static constexpr size_t NUM_ITEMS = 256;
252+
253+ IntegerItem *same_items = new IntegerItem[ NUM_ITEMS ];
254+
255+ for ( size_t n = 0; n < NUM_ITEMS; n++ )
256+ {
257+ same_items[n].my_number = 1524;
258+
259+ tree.Insert( &same_items[n].node );
260+ }
261+
262+ // Now check that we really have this amount of items in the tree.
263+ size_t node_count = 0;
264+
265+ tree.Walk(
266+ [&]( AVLNode *theNode )
267+ {
268+ node_count++;
269+ });
270+
271+ assert( node_count == NUM_ITEMS );
272+
273+ delete [] same_items;
274+ }
275+ printf( "ok.\n" );
276+
277+ printf( "testing AVL tree node move..." );
278+ {
279+ AVLTree <IntegerItem> tree;
280+
281+ IntegerItem one, two;
282+
283+ one.my_number = 21;
284+ two.my_number = 42;
285+
286+ tree.Insert( &one.node );
287+
288+ assert( tree.FindNode( 21 ) == &one.node );
289+
290+ // Also for fun insert some other nodes.
291+ static constexpr int NUM_RANDS = 1024;
292+
293+ IntegerItem *random_nodes = new IntegerItem[ NUM_RANDS ];
294+
295+ for ( int n = 0; n < NUM_RANDS; n++ )
296+ {
297+ random_nodes[n].my_number = n * 10;
298+
299+ tree.Insert( &random_nodes[n].node );
300+ }
301+
302+ // Now perform the move.
303+ two.my_number = one.my_number;
304+ two.node.moveTo( std::move( one.node ) );
305+
306+ assert( tree.FindNode( 21 ) == &two.node );
307+
308+ tree.Validate();
309+
310+ delete [] random_nodes;
311+ }
312+ printf( "ok.\n" );
232313 }
\ No newline at end of file
--- common/sdk/AVLTree.h (revision 119)
+++ common/sdk/AVLTree.h (revision 120)
@@ -34,6 +34,115 @@
3434 // TODO: find a way to segregate the AVL default fields from the nodestack field so that
3535 // it is easier to maintain this thing.
3636
37+ // WARNING: only use this method if you know that a node (right) is part of a tree.
38+ // Otherwise you perform undefined behavior.
39+ // Calling this method does destroy the tree ownership of "right", so make sure you
40+ // remove the condition that casts it into a tree.
41+ // WARNING: make sure that you have taken over the same value to the new object from
42+ // the moved-from object or else the tree will be wrecked.
43+ inline void moveTo( AVLNode&& right )
44+ {
45+ AVLNode *parent = right.parent;
46+
47+ // Are we a nodestack member?
48+ if ( parent == &right )
49+ {
50+ this->parent = this;
51+ this->nodestack_owner = right.nodestack_owner;
52+
53+ AVLNode *next_listnode = right.next;
54+
55+ // Because we have a linked-list that loops back to the first nodestack item
56+ // all pointers to members are not nullptr.
57+ // So fix up the links.
58+ next_listnode->prev = this;
59+
60+ this->next = next_listnode;
61+
62+ AVLNode *prev_listnode = right.prev;
63+
64+ prev_listnode->next = this;
65+
66+ this->prev = prev_listnode;
67+ }
68+ else
69+ {
70+ if ( parent != nullptr )
71+ {
72+ // Depends on if we are left or right of the node.
73+ if ( parent->left == &right )
74+ {
75+ parent->left = this;
76+ }
77+ else if ( parent->right == &right )
78+ {
79+ parent->right = this;
80+ }
81+ else
82+ {
83+ assert( 0 );
84+ }
85+ }
86+
87+ this->parent = parent;
88+
89+ // Fix up the children.
90+ AVLNode *left_node = right.left;
91+
92+ if ( left_node != nullptr )
93+ {
94+ assert( left_node->parent == &right );
95+
96+ left_node->parent = this;
97+ }
98+
99+ this->left = left_node;
100+
101+ AVLNode *right_node = right.right;
102+
103+ if ( right_node != nullptr )
104+ {
105+ assert( right_node->parent == &right );
106+
107+ right_node->parent = this;
108+ }
109+
110+ this->right = right_node;
111+
112+ // We have the same height, too.
113+ this->height = right.height;
114+
115+ // Fix up all nodestack items, if we are having a nodestack.
116+ AVLNode *owned_nodestack = right.owned_nodestack;
117+
118+ if ( owned_nodestack != nullptr )
119+ {
120+ AVLNode *iter = owned_nodestack;
121+
122+ do
123+ {
124+ assert( iter->nodestack_owner == &right );
125+
126+ iter->nodestack_owner = this;
127+
128+ iter = iter->next;
129+ }
130+ while ( iter != owned_nodestack );
131+ }
132+
133+ this->owned_nodestack = owned_nodestack;
134+ }
135+ }
136+
137+ // We keep the default constructor while deleting the obvious culprits for safety.
138+ inline AVLNode( void ) = default;
139+ inline AVLNode( const AVLNode& ) = delete;
140+ inline AVLNode( AVLNode&& ) = delete;
141+ inline ~AVLNode( void ) = default;
142+
143+ inline AVLNode& operator = ( const AVLNode& ) = delete;
144+ inline AVLNode& operator = ( AVLNode&& ) = delete;
145+
37146 AVLNode *parent; // if parent points to itself, then we are part of a node stack.
38147 union
39148 {
@@ -89,6 +198,9 @@
89198 }
90199
91200 inline AVLTree& operator = ( const AVLTree& right ) = delete;
201+
202+ // WARNING: a friendly reminder, that this operator trashes any previous tree nodes.
203+ // so make sure to empty the tree (dealloc nodes, etc) before moving to it!
92204 inline AVLTree& operator = ( AVLTree&& right )
93205 {
94206 this->root = right.root;
@@ -701,6 +813,7 @@
701813 this->curNode = walkNode;
702814 this->nodestack = nullptr;
703815 this->doesIterateNodestack = false;
816+ this->isEnd = ( walkNode == nullptr );
704817 }
705818 AINLINE nodestack_iterator( const nodestack_iterator& ) = default;
706819 AINLINE ~nodestack_iterator( void ) = default;
@@ -709,14 +822,7 @@
709822
710823 AINLINE bool IsEnd( void ) const
711824 {
712- if ( this->doesIterateNodestack )
713- {
714- return ( this->curNode == this->nodestack );
715- }
716- else
717- {
718- return ( this->curNode == nullptr );
719- }
825+ return this->isEnd;
720826 }
721827
722828 AINLINE void Increment( void )
@@ -728,6 +834,11 @@
728834 if ( this->doesIterateNodestack )
729835 {
730836 curNode = curNode->next;
837+
838+ if ( curNode == this->nodestack )
839+ {
840+ this->isEnd = true;
841+ }
731842 }
732843 else
733844 {
@@ -735,15 +846,20 @@
735846
736847 if ( nodestack != nullptr )
737848 {
738- this->curNode = nodestack;
849+ curNode = nodestack;
739850 this->nodestack = nodestack;
740851 this->doesIterateNodestack = true;
741852 }
742853 else
743854 {
744- this->curNode = nullptr;
855+ curNode = nullptr;
856+ this->isEnd = true;
745857 }
746858 }
859+
860+ // It has to change through iteration.
861+ // Very friendly to do so at the end aswell.
862+ this->curNode = curNode;
747863 }
748864
749865 AINLINE AVLNode* Resolve( void )
@@ -754,6 +870,7 @@
754870 AVLNode *curNode;
755871 AVLNode *nodestack;
756872 bool doesIterateNodestack;
873+ bool isEnd;
757874 };
758875
759876 // Calls the function for each node-stack member of the node.
--- common/sdk/String.h (revision 119)
+++ common/sdk/String.h (revision 120)
@@ -22,8 +22,12 @@
2222 namespace eir
2323 {
2424
25-// TODO.
25+template <typename charType, typename allocatorType>
26+struct String
27+{
2628
29+};
30+
2731 }
2832
2933 #endif //_EIR_STRING_HEADER_
\ No newline at end of file
Show on old repository browser