2 /*--------------------------------------------------------------------*/
3 /*--- An ordered set implemented using an AVL tree. m_oset.c ---*/
4 /*--------------------------------------------------------------------*/
7 This file is part of Valgrind, a dynamic binary instrumentation
10 Copyright (C) 2005-2017 Nicholas Nethercote
13 This program is free software; you can redistribute it and/or
14 modify it under the terms of the GNU General Public License as
15 published by the Free Software Foundation; either version 2 of the
16 License, or (at your option) any later version.
18 This program is distributed in the hope that it will be useful, but
19 WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 General Public License for more details.
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
28 The GNU General Public License is contained in the file COPYING.
31 //----------------------------------------------------------------------
32 // This file is based on:
34 // ANSI C Library for maintenance of AVL Balanced Trees
35 // (C) 2000 Daniel Nagy, Budapest University of Technology and Economics
36 // Released under GNU General Public License (GPL) version 2
37 //----------------------------------------------------------------------
39 // This file implements a generic ordered set using an AVL tree.
41 // Each node in the tree has two parts.
42 // - First is the AVL metadata, which is three words: a left pointer, a
43 // right pointer, and a word containing balancing information and a
44 // "magic" value which provides some checking that the user has not
45 // corrupted the metadata. So the overhead is 12 bytes on 32-bit
46 // platforms and 24 bytes on 64-bit platforms.
47 // - Second is the user's data. This can be anything. Note that because it
48 // comes after the metadata, it will only be word-aligned, even if the
49 // user data is a struct that would normally be doubleword-aligned.
51 // AvlNode* node -> +---------------+ V
54 // void* element -> +---------------+ ^
56 // keyOff -> | key | elemSize
57 // +---------------+ v
59 // Users have to allocate AvlNodes with OSetGen_AllocNode(), which allocates
60 // space for the metadata.
62 // The terminology used throughout this file:
63 // - a "node", usually called "n", is a pointer to the metadata.
64 // - an "element", usually called "e", is a pointer to the user data.
65 // - a "key", usually called "k", is a pointer to a key.
67 // The helper functions elem_of_node and node_of_elem do the pointer
68 // arithmetic to switch between the node and the element. The node magic is
69 // checked after each operation to make sure that we're really operating on
72 // Each tree also has an iterator. Note that we cannot use the iterator
73 // internally within this file (eg. we could implement OSetGen_Size() by
74 // stepping through with the iterator and counting nodes) because it's
75 // non-reentrant -- the user might be using it themselves, and the
76 // concurrent uses would screw things up.
78 #include "pub_core_basics.h"
79 #include "pub_core_libcbase.h"
80 #include "pub_core_libcassert.h"
81 #include "pub_core_libcprint.h"
82 #include "pub_core_oset.h"
83 #include "pub_core_poolalloc.h"
85 /*--------------------------------------------------------------------*/
86 /*--- Types and constants ---*/
87 /*--------------------------------------------------------------------*/
89 typedef struct _OSetNode OSetNode
;
91 // Internal names for the OSet types.
93 typedef OSetNode AvlNode
;
95 // The padding ensures that magic is right at the end of the node,
96 // regardless of the machine's word size, so that any overwrites will be
102 Char padding
[sizeof(void*)-sizeof(Char
)-sizeof(Short
)];
106 #define STACK_MAX 32 // At most 2**32 entries can be iterated over
107 #define OSET_MAGIC 0x5b1f
109 // An OSet (AVL tree). If cmp is NULL, the key must be a UWord, and must
110 // be the first word in the element. If cmp is set, arbitrary keys in
111 // arbitrary positions can be used.
113 SizeT keyOff
; // key offset
114 OSetCmp_t cmp
; // compare a key and an element, or NULL
115 Alloc_Fn_t alloc_fn
; // allocator
116 const HChar
* cc
; // cost centre for allocator
117 Free_Fn_t free_fn
; // deallocator
118 PoolAlloc
* node_pa
; // (optional) pool allocator for nodes.
119 SizeT maxEltSize
; // for node_pa, must be > 0. Otherwise unused.
120 UInt nElems
; // number of elements in the tree
121 AvlNode
* root
; // root node
123 AvlNode
* nodeStack
[STACK_MAX
]; // Iterator node stack
124 Int numStack
[STACK_MAX
]; // Iterator num stack
125 Int stackTop
; // Iterator stack pointer, one past end
128 /*--------------------------------------------------------------------*/
129 /*--- Helper operations ---*/
130 /*--------------------------------------------------------------------*/
132 // Given a pointer to the node's element, return the pointer to the AvlNode
133 // structure. If the node has a bad magic number, it will die with an
134 // assertion failure.
136 AvlNode
* node_of_elem(const void *elem
)
138 AvlNode
* n
= (AvlNode
*)((Addr
)elem
- sizeof(AvlNode
));
139 vg_assert2(n
->magic
== OSET_MAGIC
,
140 "bad magic on node %p = %x (expected %x)\n"
142 " - node not allocated with VG_(OSetGen_AllocNode)()?\n"
143 " - node metadata corrupted by underwriting start of element?\n",
144 n
, n
->magic
, OSET_MAGIC
);
148 // Given an AvlNode, return the pointer to the element.
150 void* elem_of_node(const AvlNode
*n
)
152 vg_assert2(n
->magic
== OSET_MAGIC
,
153 "bad magic on node %p = %x (expected %x)\n"
155 " - node metadata corrupted by overwriting end of element?\n",
156 n
, n
->magic
, OSET_MAGIC
);
157 return (void*)((Addr
)n
+ sizeof(AvlNode
));
160 // Like elem_of_node, but no magic checking.
162 void* elem_of_node_no_check(const AvlNode
*n
)
164 return (void*)((Addr
)n
+ sizeof(AvlNode
));
168 void* slow_key_of_node(const AvlTree
* t
, const AvlNode
* n
)
170 return (void*)((Addr
)elem_of_node(n
) + t
->keyOff
);
174 void* fast_key_of_node(const AvlNode
* n
)
176 return elem_of_node(n
);
179 // Compare the first word of each element. Inlining is *crucial*.
180 static inline Word
fast_cmp(const void* k
, const AvlNode
* n
)
182 UWord w1
= *(const UWord
*)k
;
183 UWord w2
= *(const UWord
*)elem_of_node(n
);
184 // In previous versions, we tried to do this faster by doing
185 // "return w1 - w2". But it didn't work reliably, because the
186 // complete result of subtracting two N-bit numbers is an N+1-bit
187 // number, and what the caller is interested in is the sign of
188 // the complete N+1-bit result. The branching version is slightly
189 // slower, but safer and easier to understand.
190 if (w1
> w2
) return 1;
191 if (w1
< w2
) return -1;
195 // Compare a key and an element. Inlining is *crucial*.
197 inline Word
slow_cmp(const AvlTree
* t
, const void* k
, const AvlNode
* n
)
199 return t
->cmp(k
, elem_of_node(n
));
203 // Swing to the left. Warning: no balance maintenance.
204 static void avl_swl ( AvlNode
** root
)
207 AvlNode
* b
= a
->right
;
213 // Swing to the right. Warning: no balance maintenance.
214 static void avl_swr ( AvlNode
** root
)
217 AvlNode
* b
= a
->left
;
223 // Balance maintenance after especially nasty swings.
224 static void avl_nasty ( AvlNode
* root
)
226 switch (root
->balance
) {
228 root
->left
->balance
= 0;
229 root
->right
->balance
= 1;
232 root
->left
->balance
=-1;
233 root
->right
->balance
= 0;
236 root
->left
->balance
= 0;
237 root
->right
->balance
= 0;
243 // Clear the iterator stack.
244 static void stackClear(AvlTree
* t
)
248 for (i
= 0; i
< STACK_MAX
; i
++) {
249 t
->nodeStack
[i
] = NULL
;
255 // Push onto the iterator stack.
256 static inline void stackPush(AvlTree
* t
, AvlNode
* n
, Int i
)
258 vg_assert(t
->stackTop
< STACK_MAX
);
259 vg_assert(1 <= i
&& i
<= 3);
260 t
->nodeStack
[t
->stackTop
] = n
;
261 t
-> numStack
[t
->stackTop
] = i
;
265 // Pop from the iterator stack.
266 static inline Bool
stackPop(AvlTree
* t
, AvlNode
** n
, Int
* i
)
268 vg_assert(t
->stackTop
<= STACK_MAX
);
270 if (t
->stackTop
> 0) {
272 *n
= t
->nodeStack
[t
->stackTop
];
273 *i
= t
-> numStack
[t
->stackTop
];
274 vg_assert(1 <= *i
&& *i
<= 3);
275 t
->nodeStack
[t
->stackTop
] = NULL
;
276 t
-> numStack
[t
->stackTop
] = 0;
283 /*--------------------------------------------------------------------*/
284 /*--- Creating and destroying AvlTrees and AvlNodes ---*/
285 /*--------------------------------------------------------------------*/
287 // The underscores avoid GCC complaints about overshadowing global names.
288 AvlTree
* VG_(OSetGen_Create
)(PtrdiffT keyOff
, OSetCmp_t cmp
,
289 Alloc_Fn_t alloc_fn
, const HChar
* cc
,
294 // Check the padding is right and the AvlNode is the expected size.
295 vg_assert(sizeof(AvlNode
) == 3*sizeof(void*));
300 if (!cmp
) vg_assert(0 == keyOff
); // If no cmp, offset must be zero
302 t
= alloc_fn(cc
, sizeof(AvlTree
));
305 t
->alloc_fn
= alloc_fn
;
307 t
->free_fn
= free_fn
;
309 t
->maxEltSize
= 0; // Just in case it would be wrongly used.
317 AvlTree
* VG_(OSetGen_Create_With_Pool
)(PtrdiffT keyOff
, OSetCmp_t cmp
,
318 Alloc_Fn_t alloc_fn
, const HChar
* cc
,
325 t
= VG_(OSetGen_Create
) (keyOff
, cmp
, alloc_fn
, cc
, free_fn
);
327 vg_assert (poolSize
> 0);
328 vg_assert (maxEltSize
> 0);
329 t
->maxEltSize
= maxEltSize
;
330 t
->node_pa
= VG_(newPA
)(sizeof(AvlNode
)
331 + VG_ROUNDUP(maxEltSize
, sizeof(void*)),
336 VG_(addRefPA
) (t
->node_pa
);
341 AvlTree
* VG_(OSetGen_EmptyClone
) (const AvlTree
* os
)
347 t
= os
->alloc_fn(os
->cc
, sizeof(AvlTree
));
348 t
->keyOff
= os
->keyOff
;
350 t
->alloc_fn
= os
->alloc_fn
;
352 t
->free_fn
= os
->free_fn
;
353 t
->node_pa
= os
->node_pa
;
355 VG_(addRefPA
) (t
->node_pa
);
356 t
->maxEltSize
= os
->maxEltSize
;
364 AvlTree
* VG_(OSetWord_Create
)(Alloc_Fn_t alloc_fn
, const HChar
* cc
,
367 return VG_(OSetGen_Create
)(/*keyOff*/0, /*cmp*/NULL
, alloc_fn
, cc
, free_fn
);
370 // Destructor, frees up all memory held by remaining nodes.
371 void VG_(OSetGen_Destroy
)(AvlTree
* t
)
376 has_node_pa
= t
->node_pa
!= NULL
;
379 * If we are the only remaining user of this pool allocator, release all
380 * the elements by deleting the pool allocator. That's more efficient than
381 * deleting tree nodes one by one.
383 if (!has_node_pa
|| VG_(releasePA
)(t
->node_pa
) > 0) {
390 stackPush(t
, t
->root
, 1);
392 /* Free all the AvlNodes. This is a post-order traversal, because we */
393 /* must free all children of a node before the node itself. */
394 while (stackPop(t
, &n
, &i
)) {
398 if (n
->left
) stackPush(t
, n
->left
, 1);
402 if (n
->right
) stackPush(t
, n
->right
, 1);
406 VG_(freeEltPA
) (t
->node_pa
, n
);
413 vg_assert(sz
== t
->nElems
);
416 /* Free the AvlTree itself. */
420 void VG_(OSetWord_Destroy
)(AvlTree
* t
)
422 VG_(OSetGen_Destroy
)(t
);
425 // Allocate and initialise a new node.
426 void* VG_(OSetGen_AllocNode
)(const AvlTree
* t
, SizeT elemSize
)
429 Int nodeSize
= sizeof(AvlNode
) + elemSize
;
430 vg_assert(elemSize
> 0);
432 vg_assert(elemSize
<= t
->maxEltSize
);
433 n
= VG_(allocEltPA
) (t
->node_pa
);
435 n
= t
->alloc_fn( t
->cc
, nodeSize
);
437 VG_(memset
)(n
, 0, nodeSize
);
438 n
->magic
= OSET_MAGIC
;
439 return elem_of_node(n
);
442 void VG_(OSetGen_FreeNode
)(const AvlTree
* t
, void* e
)
445 VG_(freeEltPA
) (t
->node_pa
, node_of_elem (e
));
447 t
->free_fn( node_of_elem(e
) );
450 /*--------------------------------------------------------------------*/
451 /*--- Insertion ---*/
452 /*--------------------------------------------------------------------*/
454 static inline Word
cmp_key_root(const AvlTree
* t
, const AvlNode
* n
)
457 ? slow_cmp(t
, slow_key_of_node(t
, n
), t
->root
)
458 : fast_cmp( fast_key_of_node( n
), t
->root
);
461 // Insert element e into the non-empty AVL tree t.
462 // Returns True if the depth of the tree has grown.
463 static Bool
avl_insert(AvlTree
* t
, AvlNode
* n
)
465 Word cmpres
= cmp_key_root(t
, n
);
468 // Insert into the left subtree.
470 // Only need to set the used fields in the subtree.
471 AvlTree left_subtree
;
472 left_subtree
.root
= t
->root
->left
;
473 left_subtree
.cmp
= t
->cmp
;
474 left_subtree
.keyOff
= t
->keyOff
;
475 if (avl_insert(&left_subtree
, n
)) {
476 switch (t
->root
->balance
--) {
477 case 1: return False
;
480 if (t
->root
->left
->balance
< 0) {
482 t
->root
->balance
= 0;
483 t
->root
->right
->balance
= 0;
485 avl_swl(&(t
->root
->left
));
490 t
->root
->left
=left_subtree
.root
;
495 if (t
->root
->balance
--) return False
;
499 } else if (cmpres
> 0) {
500 // Insert into the right subtree
501 if (t
->root
->right
) {
502 // Only need to set the used fields in the subtree.
503 AvlTree right_subtree
;
504 right_subtree
.root
= t
->root
->right
;
505 right_subtree
.cmp
= t
->cmp
;
506 right_subtree
.keyOff
= t
->keyOff
;
507 if (avl_insert(&right_subtree
, n
)) {
508 switch (t
->root
->balance
++) {
509 case -1: return False
;
512 if (t
->root
->right
->balance
> 0) {
514 t
->root
->balance
= 0;
515 t
->root
->left
->balance
= 0;
517 avl_swr(&(t
->root
->right
));
522 t
->root
->right
=right_subtree
.root
;
527 if (t
->root
->balance
++) return False
;
532 vg_assert2(0, "OSet{Word,Gen}_Insert: duplicate element added");
536 // Insert element e into the AVL tree t. This is just a wrapper for
537 // avl_insert() which doesn't return a Bool.
538 void VG_(OSetGen_Insert
)(AvlTree
* t
, void* e
)
544 // Initialise. Even though OSetGen_AllocNode zeroes these fields,
545 // we should do it again in case a node is removed and then
546 // re-added to the tree.
552 // Insert into an empty tree
560 t
->stackTop
= 0; // So the iterator can't get out of sync
563 void VG_(OSetWord_Insert
)(AvlTree
* t
, UWord val
)
565 Word
* node
= VG_(OSetGen_AllocNode
)(t
, sizeof(UWord
));
567 VG_(OSetGen_Insert
)(t
, node
);
570 /*--------------------------------------------------------------------*/
572 /*--------------------------------------------------------------------*/
574 // Find the *node* in t matching k, or NULL if not found.
575 static AvlNode
* avl_lookup(const AvlTree
* t
, const void* k
)
578 AvlNode
* curr
= t
->root
;
583 if (curr
== NULL
) return NULL
;
584 cmpres
= slow_cmp(t
, k
, curr
);
585 if (cmpres
< 0) curr
= curr
->left
;
586 else if (cmpres
> 0) curr
= curr
->right
;
590 // Fast-track special case. We use the no-check version of
591 // elem_of_node because it saves about 10% on lookup time. This
592 // shouldn't be very dangerous because each node will have been
593 // checked on insertion.
594 UWord w1
= *(const UWord
*)k
;
597 if (curr
== NULL
) return NULL
;
598 w2
= *(UWord
*)elem_of_node_no_check(curr
);
599 if (w1
< w2
) curr
= curr
->left
;
600 else if (w1
> w2
) curr
= curr
->right
;
606 // Find the *element* in t matching k, or NULL if not found.
607 void* VG_(OSetGen_Lookup
)(const AvlTree
* t
, const void* k
)
611 n
= avl_lookup(t
, k
);
612 return ( n
? elem_of_node(n
) : NULL
);
615 // Find the *element* in t matching k, or NULL if not found; use the given
616 // comparison function rather than the standard one.
617 void* VG_(OSetGen_LookupWithCmp
)(AvlTree
* t
, const void* k
, OSetCmp_t cmp
)
619 // Save the normal one to the side, then restore once we're done.
625 e
= VG_(OSetGen_Lookup
)(t
, k
);
630 // Is there an element matching k?
631 Bool
VG_(OSetGen_Contains
)(const AvlTree
* t
, const void* k
)
633 return (NULL
!= VG_(OSetGen_Lookup
)(t
, k
));
636 Bool
VG_(OSetWord_Contains
)(const AvlTree
* t
, UWord val
)
638 return (NULL
!= VG_(OSetGen_Lookup
)(t
, &val
));
641 /*--------------------------------------------------------------------*/
643 /*--------------------------------------------------------------------*/
645 static Bool
avl_removeroot(AvlTree
* t
);
647 // Remove an already-selected node n from the AVL tree t.
648 // Returns True if the depth of the tree has shrunk.
649 static Bool
avl_remove(AvlTree
* t
, const AvlNode
* n
)
652 Word cmpres
= cmp_key_root(t
, n
);
655 AvlTree left_subtree
;
656 // Remove from the left subtree
657 vg_assert(t
->root
->left
);
658 // Only need to set the used fields in the subtree.
659 left_subtree
.root
= t
->root
->left
;
660 left_subtree
.cmp
= t
->cmp
;
661 left_subtree
.keyOff
= t
->keyOff
;
662 ch
= avl_remove(&left_subtree
, n
);
663 t
->root
->left
= left_subtree
.root
;
665 switch (t
->root
->balance
++) {
666 case -1: return True
;
667 case 0: return False
;
669 switch (t
->root
->right
->balance
) {
672 t
->root
->balance
= -1;
673 t
->root
->left
->balance
= 1;
677 t
->root
->balance
= 0;
678 t
->root
->left
->balance
= 0;
681 avl_swr(&(t
->root
->right
));
689 } else if (cmpres
> 0) {
690 // Remove from the right subtree
691 AvlTree right_subtree
;
692 vg_assert(t
->root
->right
);
693 // Only need to set the used fields in the subtree.
694 right_subtree
.root
= t
->root
->right
;
695 right_subtree
.cmp
= t
->cmp
;
696 right_subtree
.keyOff
= t
->keyOff
;
697 ch
= avl_remove(&right_subtree
, n
);
698 t
->root
->right
= right_subtree
.root
;
700 switch (t
->root
->balance
--) {
702 case 0: return False
;
704 switch (t
->root
->left
->balance
) {
707 t
->root
->balance
= 1;
708 t
->root
->right
->balance
= -1;
712 t
->root
->balance
= 0;
713 t
->root
->right
->balance
= 0;
716 avl_swl(&(t
->root
->left
));
725 // Found the node to be removed.
726 vg_assert(t
->root
== n
);
727 return avl_removeroot(t
);
731 // Remove the root of the AVL tree t.
732 // Returns True if the depth of the tree has shrunk.
733 static Bool
avl_removeroot(AvlTree
* t
)
738 if (!t
->root
->left
) {
739 if (!t
->root
->right
) {
743 t
->root
= t
->root
->right
;
746 if (!t
->root
->right
) {
747 t
->root
= t
->root
->left
;
750 if (t
->root
->balance
< 0) {
751 // Remove from the left subtree
753 while (n
->right
) n
= n
->right
;
755 // Remove from the right subtree
757 while (n
->left
) n
= n
->left
;
759 ch
= avl_remove(t
, n
);
760 n
->left
= t
->root
->left
;
761 n
->right
= t
->root
->right
;
762 n
->balance
= t
->root
->balance
;
764 if (n
->balance
== 0) return ch
;
768 // Remove and return the element matching the key 'k', or NULL
770 void* VG_(OSetGen_Remove
)(AvlTree
* t
, const void* k
)
772 // Have to find the node first, then remove it.
773 AvlNode
* n
= avl_lookup(t
, k
);
777 t
->stackTop
= 0; // So the iterator can't get out of sync
778 return elem_of_node(n
);
784 Bool
VG_(OSetWord_Remove
)(AvlTree
* t
, UWord val
)
786 void* n
= VG_(OSetGen_Remove
)(t
, &val
);
788 VG_(OSetGen_FreeNode
)(t
, n
);
795 /*--------------------------------------------------------------------*/
797 /*--------------------------------------------------------------------*/
799 // The iterator is implemented using in-order traversal with an explicit
800 // stack, which lets us do the traversal one step at a time and remember
801 // where we are between each call to OSetGen_Next().
803 void VG_(OSetGen_ResetIter
)(AvlTree
* t
)
808 stackPush(t
, t
->root
, 1);
811 void VG_(OSetWord_ResetIter
)(AvlTree
* t
)
813 VG_(OSetGen_ResetIter
)(t
);
816 void* VG_(OSetGen_Next
)(AvlTree
* t
)
823 // This in-order traversal requires each node to be pushed and popped
824 // three times. These could be avoided by updating nodes in-situ on the
825 // top of the stack, but the push/pop cost is so small that it's worth
826 // keeping this loop in this simpler form.
827 while (stackPop(t
, &n
, &i
)) {
831 /* if (n->left) stackPush(t, n->left, 1); */
832 if (n
->left
) { n
= n
->left
; goto case_1
; }
836 return elem_of_node(n
);
838 /* if (n->right) stackPush(t, n->right, 1); */
839 if (n
->right
) { n
= n
->right
; goto case_1
; }
844 // Stack empty, iterator is exhausted, return NULL
848 Bool
VG_(OSetWord_Next
)(AvlTree
* t
, UWord
* val
)
850 UWord
* n
= VG_(OSetGen_Next
)(t
);
859 // set up 'oset' for iteration so that the first key subsequently
860 // produced VG_(OSetGen_Next) is the smallest key in the map
861 // >= start_at. Naturally ">=" is defined by the comparison
862 // function supplied to VG_(OSetGen_Create).
863 void VG_(OSetGen_ResetIterAt
)(AvlTree
* oset
, const void* k
)
866 Word cmpresS
; /* signed */
867 UWord cmpresU
; /* unsigned */
875 // We need to do regular search and fill in the stack.
879 if (t
== NULL
) return;
882 cmpresS
= (Word
)slow_cmp(oset
, k
, t
);
884 cmpresS
= fast_cmp(k
, t
);
887 /* Switch the sense of the comparison, since the comparison
888 order of args (k vs t) above is opposite to that of the
889 corresponding code in hg_wordfm.c. */
890 if (cmpresS
< 0) { cmpresS
= 1; }
891 else if (cmpresS
> 0) { cmpresS
= -1; }
894 // We found the exact key -- we are done.
895 // The iteration should start with this node.
896 stackPush(oset
, t
, 2);
897 // The stack now looks like {2, 2, ... ,2, 2}
900 cmpresU
= (UWord
)cmpresS
;
901 cmpresU
>>=/*unsigned*/ (8 * sizeof(cmpresU
) - 1);
902 vg_assert(cmpresU
== 0 || cmpresU
== 1);
904 // Push this node only if we go to the left child.
905 stackPush(oset
, t
, 2);
907 t
= cmpresU
==0 ? t
->left
: t
->right
;
911 /*--------------------------------------------------------------------*/
912 /*--- Miscellaneous operations ---*/
913 /*--------------------------------------------------------------------*/
915 UInt
VG_(OSetGen_Size
)(const AvlTree
* t
)
921 Word
VG_(OSetWord_Size
)(const AvlTree
* t
)
923 return VG_(OSetGen_Size
)(t
);
926 static void OSet_Print2( const AvlTree
* t
, const AvlNode
* n
,
927 const HChar
*(*strElem
)(const void *), Int p
)
929 // This is a recursive in-order traversal.
931 if (NULL
== n
) return;
932 if (n
->right
) OSet_Print2(t
, n
->right
, strElem
, p
+1);
933 while (q
--) VG_(printf
)(".. ");
934 VG_(printf
)("%s\n", strElem(elem_of_node(n
)));
935 if (n
->left
) OSet_Print2(t
, n
->left
, strElem
, p
+1);
938 __attribute__((unused
))
939 static void OSet_Print( const AvlTree
* t
, const HChar
*where
,
940 const HChar
*(*strElem
)(const void *) )
942 VG_(printf
)("-- start %s ----------------\n", where
);
943 OSet_Print2(t
, t
->root
, strElem
, 0);
944 VG_(printf
)("-- end %s ----------------\n", where
);
947 /*--------------------------------------------------------------------*/
949 /*--------------------------------------------------------------------*/