Author: sewardj
Date: 2008-02-17 00:24:22 +0000 (Sun, 17 Feb 2008)
New Revision: 7414
Log:
* change the default ordering unboxed order from signed word (Word)
to unsigned word (UWord)
* change some size-of-the-OSet measures from Int to Word
* add a method VG_(OSetGen_ResetIterAt) to start the iterator
at a given point, analogous to hg_wordset.c:HG_(initIterAtFM)
(Konstantin Serebryany)
Modified:
branches/DATASYMS/coregrind/m_oset.c
branches/DATASYMS/include/pub_tool_oset.h
Modified: branches/DATASYMS/coregrind/m_oset.c
===================================================================
--- branches/DATASYMS/coregrind/m_oset.c 2008-02-16 02:37:03 UTC (rev
7413)
+++ branches/DATASYMS/coregrind/m_oset.c 2008-02-17 00:24:22 UTC (rev
7414)
@@ -113,7 +113,7 @@
OSetCmp_t cmp; // compare a key and an element, or NULL
OSetAlloc_t alloc; // allocator
OSetFree_t free; // deallocator
- Int nElems; // number of elements in the tree
+ Word nElems; // number of elements in the tree
AvlNode* root; // root node
AvlNode* nodeStack[STACK_MAX]; // Iterator node stack
@@ -175,8 +175,8 @@
// Compare the first word of each element. Inlining is *crucial*.
static inline Word fast_cmp(void* k, AvlNode* n)
{
- Word w1 = *(Word*)k;
- Word w2 = *(Word*)elem_of_node(n);
+ UWord w1 = *(UWord*)k;
+ UWord w2 = *(UWord*)elem_of_node(n);
// In previous versions, we tried to do this faster by doing
// "return w1 - w2". But it didn't work reliably, because the
// complete result of subtracting two N-bit numbers is an N+1-bit
@@ -189,7 +189,8 @@
}
// Compare a key and an element. Inlining is *crucial*.
-static inline Word slow_cmp(const AvlTree* t, const void* k, const AvlNode* n)
+static
+inline Word slow_cmp(const AvlTree* t, const void* k, const AvlNode* n)
{
return t->cmp(k, elem_of_node(n));
}
@@ -314,7 +315,8 @@
void VG_(OSetGen_Destroy)(AvlTree* t)
{
AvlNode* n = NULL;
- Int i = 0, sz = 0;
+ Int i = 0;
+ Word sz = 0;
vg_assert(t);
stackClear(t);
@@ -460,8 +462,9 @@
vg_assert(t);
- // Initialise. Even though OSetGen_AllocNode zeroes these fields, we should
- // do it again in case a node is removed and then re-added to the tree.
+ // Initialise. Even though OSetGen_AllocNode zeroes these fields,
+ // we should do it again in case a node is removed and then
+ // re-added to the tree.
n = node_of_elem(e);
n->left = 0;
n->right = 0;
@@ -478,9 +481,9 @@
t->stackTop = 0; // So the iterator can't get out of sync
}
-void VG_(OSetWord_Insert)(AvlTree* t, Word val)
+void VG_(OSetWord_Insert)(AvlTree* t, UWord val)
{
- Word* node = VG_(OSetGen_AllocNode)(t, sizeof(Word));
+ Word* node = VG_(OSetGen_AllocNode)(t, sizeof(UWord));
*node = val;
VG_(OSetGen_Insert)(t, node);
}
@@ -509,11 +512,11 @@
// elem_of_node because it saves about 10% on lookup time. This
// shouldn't be very dangerous because each node will have been
// checked on insertion.
- Word w1 = *(Word*)k;
- Word w2;
+ UWord w1 = *(UWord*)k;
+ UWord w2;
while (True) {
if (curr == NULL) return NULL;
- w2 = *(Word*)elem_of_node_no_check(curr);
+ w2 = *(UWord*)elem_of_node_no_check(curr);
if (w1 < w2) curr = curr->left;
else if (w1 > w2) curr = curr->right;
else return curr;
@@ -551,7 +554,7 @@
return (NULL != VG_(OSetGen_Lookup)(t, k));
}
-Bool VG_(OSetWord_Contains)(AvlTree* t, Word val)
+Bool VG_(OSetWord_Contains)(AvlTree* t, UWord val)
{
return (NULL != VG_(OSetGen_Lookup)(t, &val));
}
@@ -683,7 +686,8 @@
return False;
}
-// Remove and return the element matching the key 'k', or NULL if not present.
+// Remove and return the element matching the key 'k', or NULL
+// if not present.
void* VG_(OSetGen_Remove)(AvlTree* t, void* k)
{
// Have to find the node first, then remove it.
@@ -698,7 +702,7 @@
}
}
-Bool VG_(OSetWord_Remove)(AvlTree* t, Word val)
+Bool VG_(OSetWord_Remove)(AvlTree* t, UWord val)
{
void* n = VG_(OSetGen_Remove)(t, &val);
if (n) {
@@ -760,9 +764,9 @@
return NULL;
}
-Bool VG_(OSetWord_Next)(AvlTree* t, Word* val)
+Bool VG_(OSetWord_Next)(AvlTree* t, UWord* val)
{
- Word* n = VG_(OSetGen_Next)(t);
+ UWord* n = VG_(OSetGen_Next)(t);
if (n) {
*val = *n;
return True;
@@ -771,17 +775,81 @@
}
}
+// set up 'oset' for iteration so that the first key subsequently
+// produced VG_(OSetGen_Next) is the smallest key in the map
+// >= start_at. Naturally ">=" is defined by the comparison
+// function supplied to VG_(OSetGen_Create).
+void VG_(OSetGen_ResetIterAt)(AvlTree* oset, void* k)
+{
+ Int i;
+ AvlNode *n, *t;
+ Word cmpresS; /* signed */
+ UWord cmpresU; /* unsigned */
+
+ tl_assert(oset);
+ stackClear(oset);
+
+ if (!oset->root)
+ return;
+
+ n = NULL;
+ // We need to do regular search and fill in the stack.
+ t = oset->root;
+
+ while (True) {
+ if (t == NULL) return;
+
+ if (oset->cmp) {
+ cmpresS = (Word)slow_cmp(oset, k, t);
+ } else {
+ /* this is believed to be correct, but really needs testing
+ before the assertion is removed. */
+ vg_assert(0);
+ cmpresS = fast_cmp(k, t);
+ }
+
+ /* Switch the sense of the comparison, since the comparison
+ order of args (k vs t) above is opposite to that of the
+ corresponding code in hg_wordfm.c. */
+ if (cmpresS < 0) { cmpresS = 1; }
+ else if (cmpresS > 0) { cmpresS = -1; }
+
+ if (cmpresS == 0) {
+ // We found the exact key -- we are done.
+ // The iteration should start with this node.
+ stackPush(oset, t, 2);
+ // The stack now looks like {2, 2, ... ,2, 2}
+ return;
+ }
+ cmpresU = (UWord)cmpresS;
+ cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1);
+ vg_assert(cmpresU == 0 || cmpresU == 1);
+ if (!cmpresU) {
+ // Push this node only if we go to the left child.
+ stackPush(oset, t, 2);
+ }
+ t = cmpresU==0 ? t->left : t->right;
+ }
+ if (stackPop(oset, &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(oset, n, 3);
+ // the stack looks like {2, 2, ..., 2, 3}
+ }
+}
+
/*--------------------------------------------------------------------*/
/*--- Miscellaneous operations ---*/
/*--------------------------------------------------------------------*/
-Int VG_(OSetGen_Size)(const AvlTree* t)
+Word VG_(OSetGen_Size)(const AvlTree* t)
{
vg_assert(t);
return t->nElems;
}
-Int VG_(OSetWord_Size)(AvlTree* t)
+Word VG_(OSetWord_Size)(AvlTree* t)
{
return VG_(OSetGen_Size)(t);
}
Modified: branches/DATASYMS/include/pub_tool_oset.h
===================================================================
--- branches/DATASYMS/include/pub_tool_oset.h 2008-02-16 02:37:03 UTC (rev
7413)
+++ branches/DATASYMS/include/pub_tool_oset.h 2008-02-17 00:24:22 UTC (rev
7414)
@@ -39,9 +39,9 @@
// It has two interfaces.
//
// - The "OSetWord_" interface provides an easier-to-use interface for the
-// case where you just want to store Word-sized values. The user provides
-// the allocation and deallocation functions, and possibly a comparison
-// function.
+// case where you just want to store UWord-sized values. The user
+// provides the allocation and deallocation functions, and possibly a
+// comparison function.
//
// - The "OSetGen_" interface provides a totally generic interface, which
// allows any kind of structure to be put into the set. The user provides
@@ -81,7 +81,7 @@
typedef void (*OSetFree_t) ( void* p );
/*--------------------------------------------------------------------*/
-/*--- Creating and destroying OSets (Word) ---*/
+/*--- Creating and destroying OSets (UWord) ---*/
/*--------------------------------------------------------------------*/
// * Create: allocates and initialises the OSet. Arguments:
@@ -102,7 +102,7 @@
extern void VG_(OSetWord_Destroy) ( OSet* os );
/*--------------------------------------------------------------------*/
-/*--- Operations on OSets (Word) ---*/
+/*--- Operations on OSets (UWord) ---*/
/*--------------------------------------------------------------------*/
// In everything that follows, the parameter 'key' is always the *address*
@@ -124,8 +124,8 @@
//
// * Next: Copies the next value according to the OSet's iterator into &val,
// advances the iterator by one, and returns True; the elements are
-// visited in order. Or, returns False if the iterator has reached the
-// set's end.
+// visited in increasing order of unsigned words (UWord). Or, returns
+// False if the iterator has reached the set's end.
//
// You can thus iterate in order through a set like this:
//
@@ -141,12 +141,12 @@
// they will return False if VG_(OSetWord_Next)() is called without an
// intervening call to VG_(OSetWord_ResetIter)().
-extern Int VG_(OSetWord_Size) ( OSet* os );
-extern void VG_(OSetWord_Insert) ( OSet* os, Word val );
-extern Bool VG_(OSetWord_Contains) ( OSet* os, Word val );
-extern Bool VG_(OSetWord_Remove) ( OSet* os, Word val );
+extern Word VG_(OSetWord_Size) ( OSet* os );
+extern void VG_(OSetWord_Insert) ( OSet* os, UWord val );
+extern Bool VG_(OSetWord_Contains) ( OSet* os, UWord val );
+extern Bool VG_(OSetWord_Remove) ( OSet* os, UWord val );
extern void VG_(OSetWord_ResetIter) ( OSet* os );
-extern Bool VG_(OSetWord_Next) ( OSet* os, Word* val );
+extern Bool VG_(OSetWord_Next) ( OSet* os, /*OUT*/UWord* val );
/*--------------------------------------------------------------------*/
@@ -234,15 +234,22 @@
// they will return NULL if VG_(OSetGen_Next)() is called without an
// intervening call to VG_(OSetGen_ResetIter)().
-extern Int VG_(OSetGen_Size) ( const OSet* os );
+extern Word VG_(OSetGen_Size) ( const OSet* os );
extern void VG_(OSetGen_Insert) ( OSet* os, void* elem );
extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key );
extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key );
-extern void* VG_(OSetGen_LookupWithCmp)( OSet* os, const void* key, OSetCmp_t
cmp );
+extern void* VG_(OSetGen_LookupWithCmp)( OSet* os,
+ const void* key, OSetCmp_t cmp );
extern void* VG_(OSetGen_Remove) ( OSet* os, void* key );
extern void VG_(OSetGen_ResetIter) ( OSet* os );
extern void* VG_(OSetGen_Next) ( OSet* os );
+// set up 'oset' for iteration so that the first key subsequently
+// produced VG_(OSetGen_Next) is the smallest key in the map
+// >= start_at. Naturally ">=" is defined by the comparison
+// function supplied to VG_(OSetGen_Create).
+extern void VG_(OSetGen_ResetIterAt) ( OSet* oset, void* key );
+
#endif // __PUB_TOOL_OSET_H
/*--------------------------------------------------------------------*/
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
