| |
| /*--------------------------------------------------------------------*/ |
| /*--- An AVL tree based finite map for word keys and word values. ---*/ |
| /*--- Inspired by Haskell's "FiniteMap" library. ---*/ |
| /*--- m_wordfm.c ---*/ |
| /*--------------------------------------------------------------------*/ |
| |
| /* |
| This file is part of Valgrind, a dynamic binary instrumentation |
| framework. |
| |
| Copyright (C) 2007-2013 Julian Seward |
| jseward@acm.org |
| |
| This code is based on previous work by Nicholas Nethercote |
| (coregrind/m_oset.c) which is |
| |
| Copyright (C) 2005-2013 Nicholas Nethercote |
| njn@valgrind.org |
| |
| which in turn was derived partially from: |
| |
| AVL C library |
| Copyright (C) 2000,2002 Daniel Nagy |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of |
| the License, or (at your option) any later version. |
| [...] |
| |
| (taken from libavl-0.4/debian/copyright) |
| |
| This program is free software; you can redistribute it and/or |
| modify it under the terms of the GNU General Public License as |
| published by the Free Software Foundation; either version 2 of the |
| License, or (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program; if not, write to the Free Software |
| Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA |
| 02111-1307, USA. |
| |
| The GNU General Public License is contained in the file COPYING. |
| */ |
| |
| #include "pub_core_basics.h" |
| #include "pub_core_libcassert.h" |
| #include "pub_core_libcbase.h" |
| #include "pub_core_wordfm.h" /* self */ |
| |
| |
| //------------------------------------------------------------------// |
| //--- WordFM ---// |
| //--- Implementation ---// |
| //------------------------------------------------------------------// |
| |
| /* One element of the AVL tree */ |
| typedef |
| struct _AvlNode { |
| UWord key; |
| UWord val; |
| struct _AvlNode* child[2]; /* [0] is left subtree, [1] is right */ |
| Char balance; /* do not make this unsigned */ |
| } |
| AvlNode; |
| |
| typedef |
| struct { |
| UWord w; |
| Bool b; |
| } |
| MaybeWord; |
| |
| #define WFM_STKMAX 32 // At most 2**32 entries can be iterated over |
| |
| struct _WordFM { |
| AvlNode* root; |
| void* (*alloc_nofail)( const HChar*, SizeT ); |
| const HChar* cc; |
| void (*dealloc)(void*); |
| Word (*kCmp)(UWord,UWord); |
| AvlNode* nodeStack[WFM_STKMAX]; // Iterator node stack |
| Int numStack[WFM_STKMAX]; // Iterator num stack |
| Int stackTop; // Iterator stack pointer, one past end |
| }; |
| |
| /* forward */ |
| static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(UWord,UWord)); |
| |
| /* Swing to the left. Warning: no balance maintainance. */ |
| static void avl_swl ( AvlNode** root ) |
| { |
| AvlNode* a = *root; |
| AvlNode* b = a->child[1]; |
| *root = b; |
| a->child[1] = b->child[0]; |
| b->child[0] = a; |
| } |
| |
| /* Swing to the right. Warning: no balance maintainance. */ |
| static void avl_swr ( AvlNode** root ) |
| { |
| AvlNode* a = *root; |
| AvlNode* b = a->child[0]; |
| *root = b; |
| a->child[0] = b->child[1]; |
| b->child[1] = a; |
| } |
| |
| /* Balance maintainance after especially nasty swings. */ |
| static void avl_nasty ( AvlNode* root ) |
| { |
| switch (root->balance) { |
| case -1: |
| root->child[0]->balance = 0; |
| root->child[1]->balance = 1; |
| break; |
| case 1: |
| root->child[0]->balance = -1; |
| root->child[1]->balance = 0; |
| break; |
| case 0: |
| root->child[0]->balance = 0; |
| root->child[1]->balance = 0; |
| break; |
| default: |
| vg_assert(0); |
| } |
| root->balance=0; |
| } |
| |
| /* Find size of a non-NULL tree. */ |
| static UWord size_avl_nonNull ( const AvlNode* nd ) |
| { |
| return 1 + (nd->child[0] ? size_avl_nonNull(nd->child[0]) : 0) |
| + (nd->child[1] ? size_avl_nonNull(nd->child[1]) : 0); |
| } |
| |
| /* Unsignedly compare w1 and w2. If w1 < w2, produce a negative |
| number; if w1 > w2 produce a positive number, and if w1 == w2 |
| produce zero. */ |
| static inline Word cmp_unsigned_Words ( UWord w1, UWord w2 ) { |
| if (w1 < w2) return -1; |
| if (w1 > w2) return 1; |
| return 0; |
| } |
| |
| /* Insert element a into the AVL tree t. Returns True if the depth of |
| the tree has grown. If element with that key is already present, |
| just copy a->val to existing node, first returning old ->val field |
| of existing node in *oldV, so that the caller can finalize it |
| however it wants. |
| */ |
| static |
| Bool avl_insert_wrk ( AvlNode** rootp, |
| /*OUT*/MaybeWord* oldV, |
| AvlNode* a, |
| Word (*kCmp)(UWord,UWord) ) |
| { |
| Word cmpres; |
| |
| /* initialize */ |
| a->child[0] = 0; |
| a->child[1] = 0; |
| a->balance = 0; |
| oldV->b = False; |
| |
| /* insert into an empty tree? */ |
| if (!(*rootp)) { |
| (*rootp) = a; |
| return True; |
| } |
| |
| cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key ) |
| : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key, |
| (UWord)a->key ); |
| |
| if (cmpres > 0) { |
| /* insert into the left subtree */ |
| if ((*rootp)->child[0]) { |
| AvlNode* left_subtree = (*rootp)->child[0]; |
| if (avl_insert_wrk(&left_subtree, oldV, a, kCmp)) { |
| switch ((*rootp)->balance--) { |
| case 1: return False; |
| case 0: return True; |
| case -1: break; |
| default: vg_assert(0); |
| } |
| if ((*rootp)->child[0]->balance < 0) { |
| avl_swr( rootp ); |
| (*rootp)->balance = 0; |
| (*rootp)->child[1]->balance = 0; |
| } else { |
| avl_swl( &((*rootp)->child[0]) ); |
| avl_swr( rootp ); |
| avl_nasty( *rootp ); |
| } |
| } else { |
| (*rootp)->child[0] = left_subtree; |
| } |
| return False; |
| } else { |
| (*rootp)->child[0] = a; |
| if ((*rootp)->balance--) |
| return False; |
| return True; |
| } |
| vg_assert(0);/*NOTREACHED*/ |
| } |
| else |
| if (cmpres < 0) { |
| /* insert into the right subtree */ |
| if ((*rootp)->child[1]) { |
| AvlNode* right_subtree = (*rootp)->child[1]; |
| if (avl_insert_wrk(&right_subtree, oldV, a, kCmp)) { |
| switch((*rootp)->balance++){ |
| case -1: return False; |
| case 0: return True; |
| case 1: break; |
| default: vg_assert(0); |
| } |
| if ((*rootp)->child[1]->balance > 0) { |
| avl_swl( rootp ); |
| (*rootp)->balance = 0; |
| (*rootp)->child[0]->balance = 0; |
| } else { |
| avl_swr( &((*rootp)->child[1]) ); |
| avl_swl( rootp ); |
| avl_nasty( *rootp ); |
| } |
| } else { |
| (*rootp)->child[1] = right_subtree; |
| } |
| return False; |
| } else { |
| (*rootp)->child[1] = a; |
| if ((*rootp)->balance++) |
| return False; |
| return True; |
| } |
| vg_assert(0);/*NOTREACHED*/ |
| } |
| else { |
| /* cmpres == 0, a duplicate - replace the val, but don't |
| incorporate the node in the tree */ |
| oldV->b = True; |
| oldV->w = (*rootp)->val; |
| (*rootp)->val = a->val; |
| return False; |
| } |
| } |
| |
| /* Remove an element a from the AVL tree t. a must be part of |
| the tree. Returns True if the depth of the tree has shrunk. |
| */ |
| static |
| Bool avl_remove_wrk ( AvlNode** rootp, |
| AvlNode* a, |
| Word(*kCmp)(UWord,UWord) ) |
| { |
| Bool ch; |
| Word cmpres; |
| cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key ) |
| : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key, |
| (UWord)a->key ); |
| |
| if (cmpres > 0){ |
| /* remove from the left subtree */ |
| AvlNode* left_subtree = (*rootp)->child[0]; |
| vg_assert(left_subtree); |
| ch = avl_remove_wrk(&left_subtree, a, kCmp); |
| (*rootp)->child[0]=left_subtree; |
| if (ch) { |
| switch ((*rootp)->balance++) { |
| case -1: return True; |
| case 0: return False; |
| case 1: break; |
| default: vg_assert(0); |
| } |
| switch ((*rootp)->child[1]->balance) { |
| case 0: |
| avl_swl( rootp ); |
| (*rootp)->balance = -1; |
| (*rootp)->child[0]->balance = 1; |
| return False; |
| case 1: |
| avl_swl( rootp ); |
| (*rootp)->balance = 0; |
| (*rootp)->child[0]->balance = 0; |
| return True; |
| case -1: |
| break; |
| default: |
| vg_assert(0); |
| } |
| avl_swr( &((*rootp)->child[1]) ); |
| avl_swl( rootp ); |
| avl_nasty( *rootp ); |
| return True; |
| } |
| } |
| else |
| if (cmpres < 0) { |
| /* remove from the right subtree */ |
| AvlNode* right_subtree = (*rootp)->child[1]; |
| vg_assert(right_subtree); |
| ch = avl_remove_wrk(&right_subtree, a, kCmp); |
| (*rootp)->child[1] = right_subtree; |
| if (ch) { |
| switch ((*rootp)->balance--) { |
| case 1: return True; |
| case 0: return False; |
| case -1: break; |
| default: vg_assert(0); |
| } |
| switch ((*rootp)->child[0]->balance) { |
| case 0: |
| avl_swr( rootp ); |
| (*rootp)->balance = 1; |
| (*rootp)->child[1]->balance = -1; |
| return False; |
| case -1: |
| avl_swr( rootp ); |
| (*rootp)->balance = 0; |
| (*rootp)->child[1]->balance = 0; |
| return True; |
| case 1: |
| break; |
| default: |
| vg_assert(0); |
| } |
| avl_swl( &((*rootp)->child[0]) ); |
| avl_swr( rootp ); |
| avl_nasty( *rootp ); |
| return True; |
| } |
| } |
| else { |
| vg_assert(cmpres == 0); |
| vg_assert((*rootp)==a); |
| return avl_removeroot_wrk(rootp, kCmp); |
| } |
| return 0; |
| } |
| |
| /* Remove the root of the AVL tree *rootp. |
| * Warning: dumps core if *rootp is empty |
| */ |
| static |
| Bool avl_removeroot_wrk ( AvlNode** rootp, |
| Word(*kCmp)(UWord,UWord) ) |
| { |
| Bool ch; |
| AvlNode* a; |
| if (!(*rootp)->child[0]) { |
| if (!(*rootp)->child[1]) { |
| (*rootp) = 0; |
| return True; |
| } |
| (*rootp) = (*rootp)->child[1]; |
| return True; |
| } |
| if (!(*rootp)->child[1]) { |
| (*rootp) = (*rootp)->child[0]; |
| return True; |
| } |
| if ((*rootp)->balance < 0) { |
| /* remove from the left subtree */ |
| a = (*rootp)->child[0]; |
| while (a->child[1]) a = a->child[1]; |
| } else { |
| /* remove from the right subtree */ |
| a = (*rootp)->child[1]; |
| while (a->child[0]) a = a->child[0]; |
| } |
| ch = avl_remove_wrk(rootp, a, kCmp); |
| a->child[0] = (*rootp)->child[0]; |
| a->child[1] = (*rootp)->child[1]; |
| a->balance = (*rootp)->balance; |
| (*rootp) = a; |
| if(a->balance == 0) return ch; |
| return False; |
| } |
| |
| static |
| AvlNode* avl_find_node ( AvlNode* t, Word k, Word(*kCmp)(UWord,UWord) ) |
| { |
| if (kCmp) { |
| /* Boxed comparisons */ |
| Word cmpresS; |
| while (True) { |
| if (t == NULL) return NULL; |
| cmpresS = kCmp(t->key, k); |
| if (cmpresS > 0) t = t->child[0]; else |
| if (cmpresS < 0) t = t->child[1]; else |
| return t; |
| } |
| } else { |
| /* Unboxed comparisons */ |
| Word cmpresS; /* signed */ |
| UWord cmpresU; /* unsigned */ |
| while (True) { |
| if (t == NULL) return NULL; /* unlikely ==> predictable */ |
| cmpresS = cmp_unsigned_Words( (UWord)t->key, (UWord)k ); |
| if (cmpresS == 0) return t; /* unlikely ==> predictable */ |
| cmpresU = (UWord)cmpresS; |
| cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1); |
| t = t->child[cmpresU]; |
| } |
| } |
| } |
| |
| static |
| Bool avl_find_bounds ( const AvlNode* t, |
| /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, |
| /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, |
| UWord minKey, UWord minVal, |
| UWord maxKey, UWord maxVal, |
| UWord key, |
| Word(*kCmp)(UWord,UWord) ) |
| { |
| UWord kLowerBound = minKey; |
| UWord vLowerBound = minVal; |
| UWord kUpperBound = maxKey; |
| UWord vUpperBound = maxVal; |
| while (t) { |
| Word cmpresS = kCmp ? kCmp(t->key, key) |
| : cmp_unsigned_Words(t->key, key); |
| if (cmpresS < 0) { |
| kLowerBound = t->key; |
| vLowerBound = t->val; |
| t = t->child[1]; |
| continue; |
| } |
| if (cmpresS > 0) { |
| kUpperBound = t->key; |
| vUpperBound = t->val; |
| t = t->child[0]; |
| continue; |
| } |
| /* We should never get here. If we do, it means the given key |
| is actually present in the tree, which means the original |
| call was invalid -- an error on the caller's part, and we |
| cannot give any meaningful values for the bounds. (Well, |
| maybe we could, but we're not gonna. Ner!) */ |
| return False; |
| } |
| if (kMinP) *kMinP = kLowerBound; |
| if (vMinP) *vMinP = vLowerBound; |
| if (kMaxP) *kMaxP = kUpperBound; |
| if (vMaxP) *vMaxP = vUpperBound; |
| return True; |
| } |
| |
| // Clear the iterator stack. |
| static void stackClear(WordFM* fm) |
| { |
| Int i; |
| vg_assert(fm); |
| for (i = 0; i < WFM_STKMAX; i++) { |
| fm->nodeStack[i] = NULL; |
| fm->numStack[i] = 0; |
| } |
| fm->stackTop = 0; |
| } |
| |
| // Push onto the iterator stack. |
| static inline void stackPush(WordFM* fm, AvlNode* n, Int i) |
| { |
| vg_assert(fm->stackTop < WFM_STKMAX); |
| vg_assert(1 <= i && i <= 3); |
| fm->nodeStack[fm->stackTop] = n; |
| fm-> numStack[fm->stackTop] = i; |
| fm->stackTop++; |
| } |
| |
| // Pop from the iterator stack. |
| static inline Bool stackPop(WordFM* fm, AvlNode** n, Int* i) |
| { |
| vg_assert(fm->stackTop <= WFM_STKMAX); |
| |
| if (fm->stackTop > 0) { |
| fm->stackTop--; |
| *n = fm->nodeStack[fm->stackTop]; |
| *i = fm-> numStack[fm->stackTop]; |
| vg_assert(1 <= *i && *i <= 3); |
| fm->nodeStack[fm->stackTop] = NULL; |
| fm-> numStack[fm->stackTop] = 0; |
| return True; |
| } else { |
| return False; |
| } |
| } |
| |
| static |
| AvlNode* avl_dopy ( const AvlNode* nd, |
| UWord(*dopyK)(UWord), |
| UWord(*dopyV)(UWord), |
| void*(alloc_nofail)(const HChar*,SizeT), |
| const HChar* cc ) |
| { |
| AvlNode* nyu; |
| |
| vg_assert(nd != NULL); |
| |
| nyu = alloc_nofail(cc, sizeof(AvlNode)); |
| |
| nyu->child[0] = nd->child[0]; |
| nyu->child[1] = nd->child[1]; |
| nyu->balance = nd->balance; |
| |
| /* Copy key */ |
| if (dopyK) { |
| nyu->key = dopyK( nd->key ); |
| } else { |
| /* copying assumedly unboxed keys */ |
| nyu->key = nd->key; |
| } |
| |
| /* Copy val */ |
| if (dopyV) { |
| nyu->val = dopyV( nd->val ); |
| } else { |
| /* copying assumedly unboxed vals */ |
| nyu->val = nd->val; |
| } |
| |
| /* Copy subtrees */ |
| if (nyu->child[0]) { |
| nyu->child[0] = avl_dopy( nyu->child[0], dopyK, dopyV, |
| alloc_nofail, cc ); |
| } |
| if (nyu->child[1]) { |
| nyu->child[1] = avl_dopy( nyu->child[1], dopyK, dopyV, |
| alloc_nofail, cc ); |
| } |
| |
| return nyu; |
| } |
| |
| /* Initialise a WordFM. */ |
| static void initFM ( WordFM* fm, |
| void* (*alloc_nofail)( const HChar*, SizeT ), |
| const HChar* cc, |
| void (*dealloc)(void*), |
| Word (*kCmp)(UWord,UWord) ) |
| { |
| fm->root = 0; |
| fm->kCmp = kCmp; |
| fm->alloc_nofail = alloc_nofail; |
| fm->cc = cc; |
| fm->dealloc = dealloc; |
| fm->stackTop = 0; |
| } |
| |
| /* --- Public interface functions --- */ |
| |
| /* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in |
| the set are ordered according to the ordering specified by kCmp, |
| which becomes obvious if you use VG_(initIterFM), |
| VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over |
| sections of the map, or the whole thing. If kCmp is NULL then the |
| ordering used is unsigned word ordering (UWord) on the key |
| values. */ |
| WordFM* VG_(newFM) ( void* (*alloc_nofail)( const HChar*, SizeT ), |
| const HChar* cc, |
| void (*dealloc)(void*), |
| Word (*kCmp)(UWord,UWord) ) |
| { |
| WordFM* fm = alloc_nofail(cc, sizeof(WordFM)); |
| initFM(fm, alloc_nofail, cc, dealloc, kCmp); |
| return fm; |
| } |
| |
| static void avl_free ( AvlNode* nd, |
| void(*kFin)(UWord), |
| void(*vFin)(UWord), |
| void(*dealloc)(void*) ) |
| { |
| if (!nd) |
| return; |
| if (nd->child[0]) |
| avl_free(nd->child[0], kFin, vFin, dealloc); |
| if (nd->child[1]) |
| avl_free(nd->child[1], kFin, vFin, dealloc); |
| if (kFin) |
| kFin( nd->key ); |
| if (vFin) |
| vFin( nd->val ); |
| VG_(memset)(nd, 0, sizeof(AvlNode)); |
| dealloc(nd); |
| } |
| |
| /* Free up the FM. If kFin is non-NULL, it is applied to keys |
| before the FM is deleted; ditto with vFin for vals. */ |
| void VG_(deleteFM) ( WordFM* fm, void(*kFin)(UWord), void(*vFin)(UWord) ) |
| { |
| void(*dealloc)(void*) = fm->dealloc; |
| avl_free( fm->root, kFin, vFin, dealloc ); |
| VG_(memset)(fm, 0, sizeof(WordFM) ); |
| dealloc(fm); |
| } |
| |
| /* Add (k,v) to fm. */ |
| Bool VG_(addToFM) ( WordFM* fm, UWord k, UWord v ) |
| { |
| MaybeWord oldV; |
| AvlNode* node; |
| node = fm->alloc_nofail( fm->cc, sizeof(AvlNode) ); |
| node->key = k; |
| node->val = v; |
| oldV.b = False; |
| oldV.w = 0; |
| avl_insert_wrk( &fm->root, &oldV, node, fm->kCmp ); |
| //if (oldV.b && fm->vFin) |
| // fm->vFin( oldV.w ); |
| if (oldV.b) |
| fm->dealloc(node); |
| return oldV.b; |
| } |
| |
| // Delete key from fm, returning associated key and val if found |
| Bool VG_(delFromFM) ( WordFM* fm, |
| /*OUT*/UWord* oldK, /*OUT*/UWord* oldV, UWord key ) |
| { |
| AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); |
| if (node) { |
| avl_remove_wrk( &fm->root, node, fm->kCmp ); |
| if (oldK) |
| *oldK = node->key; |
| if (oldV) |
| *oldV = node->val; |
| fm->dealloc(node); |
| return True; |
| } else { |
| return False; |
| } |
| } |
| |
| // Look up in fm, assigning found key & val at spec'd addresses |
| Bool VG_(lookupFM) ( const WordFM* fm, |
| /*OUT*/UWord* keyP, /*OUT*/UWord* valP, UWord key ) |
| { |
| AvlNode* node = avl_find_node( fm->root, key, fm->kCmp ); |
| if (node) { |
| if (keyP) |
| *keyP = node->key; |
| if (valP) |
| *valP = node->val; |
| return True; |
| } else { |
| return False; |
| } |
| } |
| |
| // See comment in pub_tool_wordfm.h for explanation |
| Bool VG_(findBoundsFM)( const WordFM* fm, |
| /*OUT*/UWord* kMinP, /*OUT*/UWord* vMinP, |
| /*OUT*/UWord* kMaxP, /*OUT*/UWord* vMaxP, |
| UWord minKey, UWord minVal, |
| UWord maxKey, UWord maxVal, |
| UWord key ) |
| { |
| /* really we should assert that minKey <= key <= maxKey, |
| where <= is as defined by fm->kCmp. */ |
| return avl_find_bounds( fm->root, kMinP, vMinP, |
| kMaxP, vMaxP, |
| minKey, minVal, |
| maxKey, maxVal, |
| key, fm->kCmp ); |
| } |
| |
| // See comment in pub_tool_wordfm.h for performance warning |
| UWord VG_(sizeFM) ( const WordFM* fm ) |
| { |
| // Hmm, this is a bad way to do this |
| return fm->root ? size_avl_nonNull( fm->root ) : 0; |
| } |
| |
| // NB UNTESTED! TEST BEFORE USE! |
| //Bool VG_(isEmptyFM)( const WordFM* fm ) |
| //{ |
| // return fm->root ? False : True; |
| //} |
| |
| // set up FM for iteration |
| void VG_(initIterFM) ( WordFM* fm ) |
| { |
| vg_assert(fm); |
| stackClear(fm); |
| if (fm->root) |
| stackPush(fm, fm->root, 1); |
| } |
| |
| // set up FM for iteration so that the first key subsequently produced |
| // by VG_(nextIterFM) is the smallest key in the map >= start_at. |
| // Naturally ">=" is defined by the comparison function supplied to |
| // VG_(newFM), as documented above. |
| void VG_(initIterAtFM) ( WordFM* fm, UWord start_at ) |
| { |
| Int i; |
| AvlNode *n, *t; |
| Word cmpresS; /* signed */ |
| UWord cmpresU; /* unsigned */ |
| |
| vg_assert(fm); |
| stackClear(fm); |
| |
| if (!fm->root) |
| return; |
| |
| n = NULL; |
| // We need to do regular search and fill in the stack. |
| t = fm->root; |
| |
| while (True) { |
| if (t == NULL) return; |
| |
| cmpresS |
| = fm->kCmp ? /*boxed*/ fm->kCmp( t->key, start_at ) |
| : /*unboxed*/ cmp_unsigned_Words( t->key, start_at ); |
| |
| if (cmpresS == 0) { |
| // We found the exact key -- we are done. |
| // The iteration should start with this node. |
| stackPush(fm, t, 2); |
| // The stack now looks like {2, 2, ... ,2, 2} |
| return; |
| } |
| cmpresU = (UWord)cmpresS; |
| cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1); |
| if (!cmpresU) { |
| // Push this node only if we go to the left child. |
| stackPush(fm, t, 2); |
| } |
| t = t->child[cmpresU]; |
| } |
| if (stackPop(fm, &n, &i)) { |
| // If we've pushed something to stack and did not find the exact key, |
| // we must fix the top element of stack. |
| vg_assert(i == 2); |
| stackPush(fm, n, 3); |
| // the stack looks like {2, 2, ..., 2, 3} |
| } |
| } |
| |
| // get next key/val pair. Will vg_assert if fm has been modified |
| // or looked up in since initIter{,At}FM was called. |
| Bool VG_(nextIterFM) ( WordFM* fm, /*OUT*/UWord* pKey, /*OUT*/UWord* pVal ) |
| { |
| Int i = 0; |
| AvlNode* n = NULL; |
| |
| vg_assert(fm); |
| |
| // This in-order traversal requires each node to be pushed and popped |
| // three times. These could be avoided by updating nodes in-situ on the |
| // top of the stack, but the push/pop cost is so small that it's worth |
| // keeping this loop in this simpler form. |
| while (stackPop(fm, &n, &i)) { |
| switch (i) { |
| case 1: case_1: |
| stackPush(fm, n, 2); |
| /* if (n->child[0]) stackPush(fm, n->child[0], 1); */ |
| if (n->child[0]) { n = n->child[0]; goto case_1; } |
| break; |
| case 2: |
| stackPush(fm, n, 3); |
| if (pKey) *pKey = n->key; |
| if (pVal) *pVal = n->val; |
| return True; |
| case 3: |
| /* if (n->child[1]) stackPush(fm, n->child[1], 1); */ |
| if (n->child[1]) { n = n->child[1]; goto case_1; } |
| break; |
| default: |
| vg_assert(0); |
| } |
| } |
| |
| // Stack empty, iterator is exhausted, return NULL |
| return False; |
| } |
| |
| // Finish an FM iteration |
| void VG_(doneIterFM) ( WordFM* fm ) |
| { |
| } |
| |
| WordFM* VG_(dopyFM) ( WordFM* fm, UWord(*dopyK)(UWord), |
| UWord(*dopyV)(UWord) ) |
| { |
| WordFM* nyu; |
| |
| /* can't clone the fm whilst iterating on it */ |
| vg_assert(fm->stackTop == 0); |
| |
| nyu = fm->alloc_nofail( fm->cc, sizeof(WordFM) ); |
| |
| *nyu = *fm; |
| |
| fm->stackTop = 0; |
| VG_(memset)(fm->nodeStack, 0, sizeof(fm->nodeStack)); |
| VG_(memset)(fm->numStack, 0, sizeof(fm->numStack)); |
| |
| if (nyu->root) { |
| nyu->root = avl_dopy( nyu->root, dopyK, dopyV, |
| fm->alloc_nofail, fm->cc ); |
| if (! nyu->root) |
| return NULL; |
| } |
| |
| return nyu; |
| } |
| |
| //------------------------------------------------------------------// |
| //--- end WordFM ---// |
| //--- Implementation ---// |
| //------------------------------------------------------------------// |
| |
| //------------------------------------------------------------------// |
| //--- WordBag (unboxed words only) ---// |
| //--- Implementation ---// |
| //------------------------------------------------------------------// |
| |
| /* A trivial container, to make it opaque. */ |
| struct _WordBag { |
| WordFM* fm; |
| }; |
| |
| WordBag* VG_(newBag) ( void* (*alloc_nofail)( const HChar*, SizeT ), |
| const HChar* cc, |
| void (*dealloc)(void*) ) |
| { |
| WordBag* bag = alloc_nofail(cc, sizeof(WordBag)); |
| bag->fm = VG_(newFM)( alloc_nofail, cc, dealloc, NULL ); |
| return bag; |
| } |
| |
| void VG_(deleteBag) ( WordBag* bag ) |
| { |
| void (*dealloc)(void*) = bag->fm->dealloc; |
| VG_(deleteFM)( bag->fm, NULL, NULL ); |
| VG_(memset)(bag, 0, sizeof(WordBag)); |
| dealloc(bag); |
| } |
| |
| void VG_(addToBag)( WordBag* bag, UWord w ) |
| { |
| UWord key, count; |
| if (VG_(lookupFM)(bag->fm, &key, &count, w)) { |
| vg_assert(key == w); |
| vg_assert(count >= 1); |
| VG_(addToFM)(bag->fm, w, count+1); |
| } else { |
| VG_(addToFM)(bag->fm, w, 1); |
| } |
| } |
| |
| UWord VG_(elemBag) ( const WordBag* bag, UWord w ) |
| { |
| UWord key, count; |
| if (VG_(lookupFM)( bag->fm, &key, &count, w)) { |
| vg_assert(key == w); |
| vg_assert(count >= 1); |
| return count; |
| } else { |
| return 0; |
| } |
| } |
| |
| UWord VG_(sizeUniqueBag) ( const WordBag* bag ) |
| { |
| return VG_(sizeFM)( bag->fm ); |
| } |
| |
| static UWord sizeTotalBag_wrk ( const AvlNode* nd ) |
| { |
| /* unchecked pre: nd is non-NULL */ |
| UWord w = nd->val; |
| vg_assert(w >= 1); |
| if (nd->child[0]) |
| w += sizeTotalBag_wrk(nd->child[0]); |
| if (nd->child[1]) |
| w += sizeTotalBag_wrk(nd->child[1]); |
| return w; |
| } |
| UWord VG_(sizeTotalBag)( const WordBag* bag ) |
| { |
| if (bag->fm->root) |
| return sizeTotalBag_wrk(bag->fm->root); |
| else |
| return 0; |
| } |
| |
| Bool VG_(delFromBag)( WordBag* bag, UWord w ) |
| { |
| UWord key, count; |
| if (VG_(lookupFM)(bag->fm, &key, &count, w)) { |
| vg_assert(key == w); |
| vg_assert(count >= 1); |
| if (count > 1) { |
| VG_(addToFM)(bag->fm, w, count-1); |
| } else { |
| vg_assert(count == 1); |
| VG_(delFromFM)( bag->fm, NULL, NULL, w ); |
| } |
| return True; |
| } else { |
| return False; |
| } |
| } |
| |
| Bool VG_(isEmptyBag)( const WordBag* bag ) |
| { |
| return VG_(sizeFM)(bag->fm) == 0; |
| } |
| |
| Bool VG_(isSingletonTotalBag)( const WordBag* bag ) |
| { |
| AvlNode* nd; |
| if (VG_(sizeFM)(bag->fm) != 1) |
| return False; |
| nd = bag->fm->root; |
| vg_assert(nd); |
| vg_assert(!nd->child[0]); |
| vg_assert(!nd->child[1]); |
| return nd->val == 1; |
| } |
| |
| UWord VG_(anyElementOfBag)( const WordBag* bag ) |
| { |
| /* Return an arbitrarily chosen element in the bag. We might as |
| well return the one at the root of the underlying AVL tree. */ |
| AvlNode* nd = bag->fm->root; |
| vg_assert(nd); /* if this fails, 'bag' is empty - caller is in error. */ |
| vg_assert(nd->val >= 1); |
| return nd->key; |
| } |
| |
| void VG_(initIterBag)( WordBag* bag ) |
| { |
| VG_(initIterFM)(bag->fm); |
| } |
| |
| Bool VG_(nextIterBag)( WordBag* bag, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount ) |
| { |
| return VG_(nextIterFM)( bag->fm, pVal, pCount ); |
| } |
| |
| void VG_(doneIterBag)( WordBag* bag ) |
| { |
| VG_(doneIterFM)( bag->fm ); |
| } |
| |
| //------------------------------------------------------------------// |
| //--- end WordBag (unboxed words only) ---// |
| //--- Implementation ---// |
| //------------------------------------------------------------------// |
| |
| /*--------------------------------------------------------------------*/ |
| /*--- end m_wordfm.c ---*/ |
| /*--------------------------------------------------------------------*/ |
