summaryrefslogtreecommitdiff
path: root/coregrind/.svn/text-base/m_wordfm.c.svn-base
diff options
context:
space:
mode:
Diffstat (limited to 'coregrind/.svn/text-base/m_wordfm.c.svn-base')
-rw-r--r--coregrind/.svn/text-base/m_wordfm.c.svn-base984
1 files changed, 984 insertions, 0 deletions
diff --git a/coregrind/.svn/text-base/m_wordfm.c.svn-base b/coregrind/.svn/text-base/m_wordfm.c.svn-base
new file mode 100644
index 0000000..a10ea90
--- /dev/null
+++ b/coregrind/.svn/text-base/m_wordfm.c.svn-base
@@ -0,0 +1,984 @@
+
+/*--------------------------------------------------------------------*/
+/*--- 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-2009 Julian Seward
+ jseward@acm.org
+
+ This code is based on previous work by Nicholas Nethercote
+ (coregrind/m_oset.c) which is
+
+ Copyright (C) 2005-2009 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)( HChar*, SizeT );
+ 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:
+ tl_assert(0);
+ }
+ root->balance=0;
+}
+
+/* Find size of a non-NULL tree. */
+static UWord size_avl_nonNull ( 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: tl_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;
+ }
+ tl_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: tl_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;
+ }
+ tl_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];
+ tl_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: tl_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:
+ tl_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];
+ tl_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: tl_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:
+ tl_assert(0);
+ }
+ avl_swl( &((*rootp)->child[0]) );
+ avl_swr( rootp );
+ avl_nasty( *rootp );
+ return True;
+ }
+ }
+ else {
+ tl_assert(cmpres == 0);
+ tl_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 ( 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;
+ tl_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)
+{
+ tl_assert(fm->stackTop < WFM_STKMAX);
+ tl_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)
+{
+ tl_assert(fm->stackTop <= WFM_STKMAX);
+
+ if (fm->stackTop > 0) {
+ fm->stackTop--;
+ *n = fm->nodeStack[fm->stackTop];
+ *i = fm-> numStack[fm->stackTop];
+ tl_assert(1 <= *i && *i <= 3);
+ fm->nodeStack[fm->stackTop] = NULL;
+ fm-> numStack[fm->stackTop] = 0;
+ return True;
+ } else {
+ return False;
+ }
+}
+
+static
+AvlNode* avl_dopy ( AvlNode* nd,
+ UWord(*dopyK)(UWord),
+ UWord(*dopyV)(UWord),
+ void*(alloc_nofail)(HChar*,SizeT),
+ HChar* cc )
+{
+ AvlNode* nyu;
+ if (! nd)
+ return NULL;
+ nyu = alloc_nofail(cc, sizeof(AvlNode));
+ tl_assert(nyu);
+
+ 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 );
+ if (nd->key != 0 && nyu->key == 0)
+ return NULL; /* oom in key dcopy */
+ } else {
+ /* copying assumedly unboxed keys */
+ nyu->key = nd->key;
+ }
+
+ /* Copy val */
+ if (dopyV) {
+ nyu->val = dopyV( nd->val );
+ if (nd->val != 0 && nyu->val == 0)
+ return NULL; /* oom in val dcopy */
+ } 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[0])
+ return NULL;
+ }
+ if (nyu->child[1]) {
+ nyu->child[1] = avl_dopy( nyu->child[1], dopyK, dopyV,
+ alloc_nofail, cc );
+ if (! nyu->child[1])
+ return NULL;
+ }
+
+ return nyu;
+}
+
+/* Initialise a WordFM. */
+static void initFM ( WordFM* fm,
+ void* (*alloc_nofail)( HChar*, SizeT ),
+ 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)( HChar*, SizeT ),
+ HChar* cc,
+ void (*dealloc)(void*),
+ Word (*kCmp)(UWord,UWord) )
+{
+ WordFM* fm = alloc_nofail(cc, sizeof(WordFM));
+ tl_assert(fm);
+ 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) ( 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)( 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) ( 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)( WordFM* fm )
+//{
+// return fm->root ? False : True;
+//}
+
+// set up FM for iteration
+void VG_(initIterFM) ( WordFM* fm )
+{
+ tl_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 */
+
+ tl_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.
+ tl_assert(i == 2);
+ stackPush(fm, n, 3);
+ // the stack looks like {2, 2, ..., 2, 3}
+ }
+}
+
+// get next key/val pair. Will tl_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;
+
+ tl_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:
+ tl_assert(0);
+ }
+ }
+
+ // Stack empty, iterator is exhausted, return NULL
+ return False;
+}
+
+// clear the I'm iterating flag
+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 */
+ tl_assert(fm->stackTop == 0);
+
+ nyu = fm->alloc_nofail( fm->cc, sizeof(WordFM) );
+ tl_assert(nyu);
+
+ *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;
+}
+
+// admin: what's the 'common' allocation size (for tree nodes?)
+SizeT VG_(getNodeSizeFM)( void )
+{
+ return sizeof(AvlNode);
+}
+
+//------------------------------------------------------------------//
+//--- 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)( HChar*, SizeT ),
+ 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)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ VG_(addToFM)(bag->fm, w, count+1);
+ } else {
+ VG_(addToFM)(bag->fm, w, 1);
+ }
+}
+
+UWord VG_(elemBag) ( WordBag* bag, UWord w )
+{
+ UWord key, count;
+ if (VG_(lookupFM)( bag->fm, &key, &count, w)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ return count;
+ } else {
+ return 0;
+ }
+}
+
+UWord VG_(sizeUniqueBag) ( WordBag* bag )
+{
+ return VG_(sizeFM)( bag->fm );
+}
+
+static UWord sizeTotalBag_wrk ( AvlNode* nd )
+{
+ /* unchecked pre: nd is non-NULL */
+ UWord w = nd->val;
+ tl_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)( 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)) {
+ tl_assert(key == w);
+ tl_assert(count >= 1);
+ if (count > 1) {
+ VG_(addToFM)(bag->fm, w, count-1);
+ } else {
+ tl_assert(count == 1);
+ VG_(delFromFM)( bag->fm, NULL, NULL, w );
+ }
+ return True;
+ } else {
+ return False;
+ }
+}
+
+Bool VG_(isEmptyBag)( WordBag* bag )
+{
+ return VG_(sizeFM)(bag->fm) == 0;
+}
+
+Bool VG_(isSingletonTotalBag)( WordBag* bag )
+{
+ AvlNode* nd;
+ if (VG_(sizeFM)(bag->fm) != 1)
+ return False;
+ nd = bag->fm->root;
+ tl_assert(nd);
+ tl_assert(!nd->child[0]);
+ tl_assert(!nd->child[1]);
+ return nd->val == 1;
+}
+
+UWord VG_(anyElementOfBag)( 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;
+ tl_assert(nd); /* if this fails, 'bag' is empty - caller is in error. */
+ tl_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 ---*/
+/*--------------------------------------------------------------------*/
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-18 05:45:46 +0000