|
From: <sv...@va...> - 2007-09-17 05:45:43
|
Author: njn
Date: 2007-09-17 06:45:40 +0100 (Mon, 17 Sep 2007)
New Revision: 6843
Log:
Merge r6841 (split OSet interface in two) from trunk.
Modified:
branches/MASSIF2/cachegrind/cg_main.c
branches/MASSIF2/coregrind/m_debuginfo/readelf.c
branches/MASSIF2/coregrind/m_oset.c
branches/MASSIF2/coregrind/m_redir.c
branches/MASSIF2/include/pub_tool_oset.h
branches/MASSIF2/memcheck/mc_main.c
branches/MASSIF2/memcheck/tests/oset_test.c
branches/MASSIF2/memcheck/tests/oset_test.stdout.exp
Modified: branches/MASSIF2/cachegrind/cg_main.c
===================================================================
--- branches/MASSIF2/cachegrind/cg_main.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/cachegrind/cg_main.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -173,13 +173,13 @@
// been encountered before, or dup it and put it into the string table.
static Char* get_perm_string(Char* s)
{
- Char** s_ptr = VG_(OSet_Lookup)(stringTable, &s);
+ Char** s_ptr = VG_(OSetGen_Lookup)(stringTable, &s);
if (s_ptr) {
return *s_ptr;
} else {
- Char** s_node = VG_(OSet_AllocNode)(stringTable, sizeof(Char*));
+ Char** s_node = VG_(OSetGen_AllocNode)(stringTable, sizeof(Char*));
*s_node = VG_(strdup)(s);
- VG_(OSet_Insert)(stringTable, s_node);
+ VG_(OSetGen_Insert)(stringTable, s_node);
return *s_node;
}
}
@@ -230,14 +230,14 @@
loc.fn = fn;
loc.line = line;
- lineCC = VG_(OSet_Lookup)(CC_table, &loc);
+ lineCC = VG_(OSetGen_Lookup)(CC_table, &loc);
if (!lineCC) {
// Allocate and zero a new node.
- lineCC = VG_(OSet_AllocNode)(CC_table, sizeof(LineCC));
+ lineCC = VG_(OSetGen_AllocNode)(CC_table, sizeof(LineCC));
lineCC->loc.file = get_perm_string(loc.file);
lineCC->loc.fn = get_perm_string(loc.fn);
lineCC->loc.line = loc.line;
- VG_(OSet_Insert)(CC_table, lineCC);
+ VG_(OSetGen_Insert)(CC_table, lineCC);
}
return lineCC;
@@ -443,16 +443,16 @@
// If this assertion fails, there has been some screwup: some
// translations must have been discarded but Cachegrind hasn't discarded
// the corresponding entries in the instr-info table.
- sbInfo = VG_(OSet_Lookup)(instrInfoTable, &origAddr);
+ sbInfo = VG_(OSetGen_Lookup)(instrInfoTable, &origAddr);
tl_assert(NULL == sbInfo);
// BB never translated before (at this address, at least; could have
// been unloaded and then reloaded elsewhere in memory)
- sbInfo = VG_(OSet_AllocNode)(instrInfoTable,
+ sbInfo = VG_(OSetGen_AllocNode)(instrInfoTable,
sizeof(SB_info) + n_instrs*sizeof(InstrInfo));
sbInfo->SB_addr = origAddr;
sbInfo->n_instrs = n_instrs;
- VG_(OSet_Insert)( instrInfoTable, sbInfo );
+ VG_(OSetGen_Insert)( instrInfoTable, sbInfo );
distinct_instrs++;
return sbInfo;
@@ -1039,8 +1039,8 @@
VG_(write)(fd, (void*)buf, VG_(strlen)(buf));
// Traverse every lineCC
- VG_(OSet_ResetIter)(CC_table);
- while ( (lineCC = VG_(OSet_Next)(CC_table)) ) {
+ VG_(OSetGen_ResetIter)(CC_table);
+ while ( (lineCC = VG_(OSetGen_Next)(CC_table)) ) {
Bool just_hit_a_new_file = False;
// If we've hit a new file, print a "fl=" line. Note that because
// each string is stored exactly once in the string table, we can use
@@ -1226,11 +1226,11 @@
buf4, no_debugs);
VG_(message)(Vg_DebugMsg, "cachegrind: string table size: %u",
- VG_(OSet_Size)(stringTable));
+ VG_(OSetGen_Size)(stringTable));
VG_(message)(Vg_DebugMsg, "cachegrind: CC table size: %u",
- VG_(OSet_Size)(CC_table));
+ VG_(OSetGen_Size)(CC_table));
VG_(message)(Vg_DebugMsg, "cachegrind: InstrInfo table size: %u",
- VG_(OSet_Size)(instrInfoTable));
+ VG_(OSetGen_Size)(instrInfoTable));
}
}
@@ -1256,9 +1256,9 @@
// Get BB info, remove from table, free BB info. Simple! Note that we
// use orig_addr, not the first instruction address in vge.
- sbInfo = VG_(OSet_Remove)(instrInfoTable, &orig_addr);
+ sbInfo = VG_(OSetGen_Remove)(instrInfoTable, &orig_addr);
tl_assert(NULL != sbInfo);
- VG_(OSet_FreeNode)(instrInfoTable, sbInfo);
+ VG_(OSetGen_FreeNode)(instrInfoTable, sbInfo);
}
/*--------------------------------------------------------------------*/
@@ -1403,15 +1403,18 @@
tl_assert( cachegrind_out_file[filename_szB-1] == 0 );
- CC_table = VG_(OSet_Create)(offsetof(LineCC, loc),
- cmp_CodeLoc_LineCC,
- VG_(malloc), VG_(free));
- instrInfoTable = VG_(OSet_Create)(/*keyOff*/0,
- NULL,
- VG_(malloc), VG_(free));
- stringTable = VG_(OSet_Create)(/*keyOff*/0,
- stringCmp,
- VG_(malloc), VG_(free));
+ CC_table =
+ VG_(OSetGen_Create)(offsetof(LineCC, loc),
+ cmp_CodeLoc_LineCC,
+ VG_(malloc), VG_(free));
+ instrInfoTable =
+ VG_(OSetGen_Create)(/*keyOff*/0,
+ NULL,
+ VG_(malloc), VG_(free));
+ stringTable =
+ VG_(OSetGen_Create)(/*keyOff*/0,
+ stringCmp,
+ VG_(malloc), VG_(free));
configure_caches(&I1c, &D1c, &L2c);
Modified: branches/MASSIF2/coregrind/m_debuginfo/readelf.c
===================================================================
--- branches/MASSIF2/coregrind/m_debuginfo/readelf.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/coregrind/m_debuginfo/readelf.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -516,9 +516,9 @@
TRACE_SYMTAB("\nReading (ELF, ppc64-linux) %s (%d entries)\n", tab_name,
o_symtab_sz/sizeof(ElfXX_Sym) );
- oset = VG_(OSet_Create)( offsetof(TempSym,key),
- (OSetCmp_t)cmp_TempSymKey,
- oset_malloc, oset_free );
+ oset = VG_(OSetGen_Create)( offsetof(TempSym,key),
+ (OSetCmp_t)cmp_TempSymKey,
+ oset_malloc, oset_free );
vg_assert(oset);
/* Perhaps should start at i = 1; ELF docs suggest that entry
@@ -542,7 +542,7 @@
/* Check if we've seen this (name,addr) key before. */
key.addr = sym_addr_really;
key.name = sym_name_really;
- prev = VG_(OSet_Lookup)( oset, &key );
+ prev = VG_(OSetGen_Lookup)( oset, &key );
if (prev) {
@@ -604,13 +604,13 @@
} else {
/* A new (name,addr) key. Add and continue. */
- elem = VG_(OSet_AllocNode)(oset, sizeof(TempSym));
+ elem = VG_(OSetGen_AllocNode)(oset, sizeof(TempSym));
vg_assert(elem);
elem->key = key;
elem->tocptr = sym_tocptr;
elem->size = sym_size;
elem->from_opd = from_opd;
- VG_(OSet_Insert)(oset, elem);
+ VG_(OSetGen_Insert)(oset, elem);
if (si->trace_symtab) {
VG_(printf)(" to-oset [%4d]: "
" val %010p, toc %010p, sz %4d %s\n",
@@ -629,9 +629,9 @@
build a "standard" symbol table, and nuke the oset. */
i = 0;
- VG_(OSet_ResetIter)( oset );
+ VG_(OSetGen_ResetIter)( oset );
- while ( (elem = VG_(OSet_Next)(oset)) ) {
+ while ( (elem = VG_(OSetGen_Next)(oset)) ) {
risym.addr = elem->key.addr;
risym.size = elem->size;
risym.name = ML_(addStr) ( si, elem->key.name, -1 );
@@ -651,7 +651,7 @@
i++;
}
- VG_(OSet_Destroy)( oset, NULL );
+ VG_(OSetGen_Destroy)( oset );
}
Modified: branches/MASSIF2/coregrind/m_oset.c
===================================================================
--- branches/MASSIF2/coregrind/m_oset.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/coregrind/m_oset.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -56,7 +56,7 @@
// keyOff -> | key | elemSize
// +---------------+ v
//
-// Users have to allocate AvlNodes with OSet_AllocNode(), which allocates
+// Users have to allocate AvlNodes with OSetGen_AllocNode(), which allocates
// space for the metadata.
//
// The terminology used throughout this file:
@@ -70,7 +70,7 @@
// an AvlNode.
//
// Each tree also has an iterator. Note that we cannot use the iterator
-// internally within this file (eg. we could implement OSet_Size() by
+// internally within this file (eg. we could implement OSetGen_Size() by
// stepping through with the iterator and counting nodes) because it's
// non-reentrant -- the user might be using it themselves, and the
// concurrent uses would screw things up.
@@ -85,6 +85,8 @@
/*--- Types and constants ---*/
/*--------------------------------------------------------------------*/
+typedef struct _OSetNode OSetNode;
+
// Internal names for the OSet types.
typedef OSet AvlTree;
typedef OSetNode AvlNode;
@@ -133,7 +135,7 @@
vg_assert2(n->magic == OSET_MAGIC,
"bad magic on node %p = %x (expected %x)\n"
"possible causes:\n"
- " - node not allocated with VG_(OSet_AllocNode)()?\n"
+ " - node not allocated with VG_(OSetGen_AllocNode)()?\n"
" - node metadata corrupted by underwriting start of element?\n",
n, n->magic, OSET_MAGIC);
return n;
@@ -268,8 +270,8 @@
/*--------------------------------------------------------------------*/
// The underscores avoid GCC complaints about overshadowing global names.
-AvlTree* VG_(OSet_Create)(OffT _keyOff, OSetCmp_t _cmp,
- OSetAlloc_t _alloc, OSetFree_t _free)
+AvlTree* VG_(OSetGen_Create)(OffT _keyOff, OSetCmp_t _cmp,
+ OSetAlloc_t _alloc, OSetFree_t _free)
{
AvlTree* t;
@@ -293,8 +295,13 @@
return t;
}
+AvlTree* VG_(OSetWord_Create)(OSetAlloc_t _alloc, OSetFree_t _free)
+{
+ return VG_(OSetGen_Create)(/*keyOff*/0, /*cmp*/NULL, _alloc, _free);
+}
+
// Destructor, frees up all memory held by remaining nodes.
-void VG_(OSet_Destroy)(AvlTree* t, OSetNodeDestroy_t destroyNode)
+void VG_(OSetGen_Destroy)(AvlTree* t)
{
AvlNode* n = NULL;
Int i = 0, sz = 0;
@@ -304,8 +311,8 @@
if (t->root)
stackPush(t, t->root, 1);
- // Free all the AvlNodes. This is a post-order traversal, because we
- // must free all children of a node before the node itself.
+ /* Free all the AvlNodes. This is a post-order traversal, because we */
+ /* must free all children of a node before the node itself. */
while (stackPop(t, &n, &i)) {
switch (i) {
case 1:
@@ -317,7 +324,6 @@
if (n->right) stackPush(t, n->right, 1);
break;
case 3:
- if (destroyNode) destroyNode(n);
t->free(n);
sz++;
break;
@@ -325,12 +331,17 @@
}
vg_assert(sz == t->nElems);
- // Free the AvlTree itself.
+ /* Free the AvlTree itself. */
t->free(t);
}
+void VG_(OSetWord_Destroy)(AvlTree* t)
+{
+ VG_(OSetGen_Destroy)(t);
+}
+
// Allocate and initialise a new node.
-void* VG_(OSet_AllocNode)(AvlTree* t, SizeT elemSize)
+void* VG_(OSetGen_AllocNode)(AvlTree* t, SizeT elemSize)
{
Int nodeSize = sizeof(AvlNode) + elemSize;
AvlNode* n = t->alloc( nodeSize );
@@ -340,7 +351,7 @@
return elem_of_node(n);
}
-void VG_(OSet_FreeNode)(AvlTree* t, void* e)
+void VG_(OSetGen_FreeNode)(AvlTree* t, void* e)
{
t->free( node_of_elem(e) );
}
@@ -427,19 +438,19 @@
}
} else {
- vg_assert2(0, "OSet_Insert: duplicate element added");
+ vg_assert2(0, "OSet{Word,Gen}_Insert: duplicate element added");
}
}
// Insert element e into the AVL tree t. This is just a wrapper for
// avl_insert() which doesn't return a Bool.
-void VG_(OSet_Insert)(AvlTree* t, void* e)
+void VG_(OSetGen_Insert)(AvlTree* t, void* e)
{
AvlNode* n;
vg_assert(t);
- // Initialise. Even though OSet_AllocNode zeroes these fields, we should
+ // 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;
@@ -457,6 +468,13 @@
t->stackTop = 0; // So the iterator can't get out of sync
}
+void VG_(OSetWord_Insert)(AvlTree* t, Word val)
+{
+ Word* node = VG_(OSetGen_AllocNode)(t, sizeof(Word));
+ *node = val;
+ VG_(OSetGen_Insert)(t, node);
+}
+
/*--------------------------------------------------------------------*/
/*--- Lookup ---*/
/*--------------------------------------------------------------------*/
@@ -493,7 +511,7 @@
}
// Find the *element* in t matching k, or NULL if not found.
-void* VG_(OSet_Lookup)(AvlTree* t, void* k)
+void* VG_(OSetGen_Lookup)(AvlTree* t, void* k)
{
AvlNode* n;
vg_assert(t);
@@ -503,7 +521,7 @@
// Find the *element* in t matching k, or NULL if not found; use the given
// comparison function rather than the standard one.
-void* VG_(OSet_LookupWithCmp)(AvlTree* t, void* k, OSetCmp_t cmp)
+void* VG_(OSetGen_LookupWithCmp)(AvlTree* t, void* k, OSetCmp_t cmp)
{
// Save the normal one to the side, then restore once we're done.
void* e;
@@ -511,17 +529,22 @@
vg_assert(t);
tmpcmp = t->cmp;
t->cmp = cmp;
- e = VG_(OSet_Lookup)(t, k);
+ e = VG_(OSetGen_Lookup)(t, k);
t->cmp = tmpcmp;
return e;
}
// Is there an element matching k?
-Bool VG_(OSet_Contains)(AvlTree* t, void* k)
+Bool VG_(OSetGen_Contains)(AvlTree* t, void* k)
{
- return (NULL != VG_(OSet_Lookup)(t, k));
+ return (NULL != VG_(OSetGen_Lookup)(t, k));
}
+Bool VG_(OSetWord_Contains)(AvlTree* t, Word val)
+{
+ return (NULL != VG_(OSetGen_Lookup)(t, &val));
+}
+
/*--------------------------------------------------------------------*/
/*--- Deletion ---*/
/*--------------------------------------------------------------------*/
@@ -650,7 +673,7 @@
}
// Remove and return the element matching the key 'k', or NULL if not present.
-void* VG_(OSet_Remove)(AvlTree* t, void* k)
+void* VG_(OSetGen_Remove)(AvlTree* t, void* k)
{
// Have to find the node first, then remove it.
AvlNode* n = avl_lookup(t, k);
@@ -664,15 +687,26 @@
}
}
+Bool VG_(OSetWord_Remove)(AvlTree* t, Word val)
+{
+ void* n = VG_(OSetGen_Remove)(t, &val);
+ if (n) {
+ VG_(OSetGen_FreeNode)(t, n);
+ return True;
+ } else {
+ return False;
+ }
+}
+
/*--------------------------------------------------------------------*/
/*--- Iterator ---*/
/*--------------------------------------------------------------------*/
// The iterator is implemented using in-order traversal with an explicit
// stack, which lets us do the traversal one step at a time and remember
-// where we are between each call to OSet_Next().
+// where we are between each call to OSetGen_Next().
-void VG_(OSet_ResetIter)(AvlTree* t)
+void VG_(OSetGen_ResetIter)(AvlTree* t)
{
vg_assert(t);
stackClear(t);
@@ -680,8 +714,13 @@
stackPush(t, t->root, 1);
}
-void* VG_(OSet_Next)(AvlTree* t)
+void VG_(OSetWord_ResetIter)(AvlTree* t)
{
+ VG_(OSetGen_ResetIter)(t);
+}
+
+void* VG_(OSetGen_Next)(AvlTree* t)
+{
Int i = 0;
OSetNode* n = NULL;
@@ -710,16 +749,32 @@
return NULL;
}
+Bool VG_(OSetWord_Next)(AvlTree* t, Word* val)
+{
+ Word* n = VG_(OSetGen_Next)(t);
+ if (n) {
+ *val = *n;
+ return True;
+ } else {
+ return False;
+ }
+}
+
/*--------------------------------------------------------------------*/
/*--- Miscellaneous operations ---*/
/*--------------------------------------------------------------------*/
-Int VG_(OSet_Size)(AvlTree* t)
+Int VG_(OSetGen_Size)(AvlTree* t)
{
vg_assert(t);
return t->nElems;
}
+Int VG_(OSetWord_Size)(AvlTree* t)
+{
+ return VG_(OSetGen_Size)(t);
+}
+
static void OSet_Print2( AvlTree* t, AvlNode* n,
Char*(*strElem)(void *), Int p )
{
Modified: branches/MASSIF2/coregrind/m_redir.c
===================================================================
--- branches/MASSIF2/coregrind/m_redir.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/coregrind/m_redir.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -544,7 +544,7 @@
goto bad;
}
- old = VG_(OSet_Lookup)( activeSet, &act.from_addr );
+ old = VG_(OSetGen_Lookup)( activeSet, &act.from_addr );
if (old) {
/* Dodgy. Conflicting binding. */
vg_assert(old->from_addr == act.from_addr);
@@ -559,10 +559,10 @@
/* XXXXXXXXXXX COMPLAIN if new and old parents differ */
}
} else {
- Active* a = VG_(OSet_AllocNode)(activeSet, sizeof(Active));
+ Active* a = VG_(OSetGen_AllocNode)(activeSet, sizeof(Active));
vg_assert(a);
*a = act;
- VG_(OSet_Insert)(activeSet, a);
+ VG_(OSetGen_Insert)(activeSet, a);
/* Now that a new from->to redirection is in force, we need to
get rid of any translations intersecting 'from' in order that
they get redirected to 'to'. So discard them. Just for
@@ -597,7 +597,7 @@
OSet* tmpSet;
Active* act;
Bool delMe;
- Addr* addrP;
+ Addr addr;
vg_assert(delsi);
@@ -617,13 +617,12 @@
/* Traverse the actives, copying the addresses of those we intend
to delete into tmpSet. */
- tmpSet = VG_(OSet_Create)( 0/*keyOff*/, NULL/*fastCmp*/,
- symtab_alloc, symtab_free);
+ tmpSet = VG_(OSetWord_Create)(symtab_alloc, symtab_free);
ts->mark = True;
- VG_(OSet_ResetIter)( activeSet );
- while ( (act = VG_(OSet_Next)(activeSet)) ) {
+ VG_(OSetGen_ResetIter)( activeSet );
+ while ( (act = VG_(OSetGen_Next)(activeSet)) ) {
delMe = act->parent_spec != NULL
&& act->parent_sym != NULL
&& act->parent_spec->seginfo != NULL
@@ -644,9 +643,7 @@
}
if (delMe) {
- addrP = VG_(OSet_AllocNode)( tmpSet, sizeof(Addr) );
- *addrP = act->from_addr;
- VG_(OSet_Insert)( tmpSet, addrP );
+ VG_(OSetWord_Insert)( tmpSet, act->from_addr );
/* While we have our hands on both the 'from' and 'to'
of this Active, do paranoid stuff with tt/tc. */
VG_(discard_translations)( (Addr64)act->from_addr, 1,
@@ -656,16 +653,15 @@
}
}
- /* Now traverse tmpSet, deleting corresponding elements in
- activeSet. */
- VG_(OSet_ResetIter)( tmpSet );
- while ( (addrP = VG_(OSet_Next)(tmpSet)) ) {
- act = VG_(OSet_Remove)( activeSet, addrP );
+ /* Now traverse tmpSet, deleting corresponding elements in activeSet. */
+ VG_(OSetWord_ResetIter)( tmpSet );
+ while ( VG_(OSetWord_Next)(tmpSet, &addr) ) {
+ act = VG_(OSetGen_Remove)( activeSet, &addr );
vg_assert(act);
- VG_(OSet_FreeNode)( activeSet, act );
+ VG_(OSetGen_FreeNode)( activeSet, act );
}
- VG_(OSet_Destroy)( tmpSet, NULL );
+ VG_(OSetWord_Destroy)( tmpSet );
/* The Actives set is now cleaned up. Free up this TopSpec and
everything hanging off it. */
@@ -698,7 +694,7 @@
just before translating a basic block. */
Addr VG_(redir_do_lookup) ( Addr orig, Bool* isWrap )
{
- Active* r = VG_(OSet_Lookup)(activeSet, &orig);
+ Active* r = VG_(OSetGen_Lookup)(activeSet, &orig);
if (r == NULL)
return orig;
@@ -776,10 +772,10 @@
vg_assert( VG_(next_seginfo)(NULL) == NULL );
// Initialise active mapping.
- activeSet = VG_(OSet_Create)(offsetof(Active, from_addr),
- NULL, // Use fast comparison
- symtab_alloc,
- symtab_free);
+ activeSet = VG_(OSetGen_Create)(offsetof(Active, from_addr),
+ NULL, // Use fast comparison
+ symtab_alloc,
+ symtab_free);
// The rest of this function just adds initial Specs.
@@ -1003,8 +999,8 @@
show_spec(" ", sp);
}
VG_(message)(Vg_DebugMsg, " ------ ACTIVE ------");
- VG_(OSet_ResetIter)( activeSet );
- while ( (act = VG_(OSet_Next)(activeSet)) ) {
+ VG_(OSetGen_ResetIter)( activeSet );
+ while ( (act = VG_(OSetGen_Next)(activeSet)) ) {
show_active(" ", act);
}
Modified: branches/MASSIF2/include/pub_tool_oset.h
===================================================================
--- branches/MASSIF2/include/pub_tool_oset.h 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/include/pub_tool_oset.h 2007-09-17 05:45:40 UTC (rev 6843)
@@ -36,24 +36,32 @@
// elements. It does not allow duplicates, and will assert if you insert a
// duplicate to an OSet.
//
-// The structure is totally generic. The user provides the allocation and
-// deallocation functions. Also, each element has a key, which the lookup
-// is done with. The key may be the whole element (eg. in an OSet of
-// integers, each integer serves both as an element and a key), or it may be
-// only part of it (eg. if the key is a single field in a struct). The user
-// can provide a function that compares an element with a key; this is very
-// flexible, and with the right comparison function even a (non-overlapping)
-// interval list can be created. But the cost of calling a function for
-// every comparison can be high during lookup. If no comparison function is
-// provided, we assume that keys are (signed or unsigned) words, and that
-// the key is the first word in each element. This fast comparison is
-// suitable for an OSet of Words, or an OSet containing structs where the
-// first element is an Addr, for example.
+// It has two interfaces.
//
-// Each OSet also has an iterator, which makes it simple to traverse all the
-// nodes in order. Note that the iterator maintains state and so is
-// non-reentrant.
+// - 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.
//
+// - The "OSetGen_" interface provides a totally generic interface, which
+// allows any kind of structure to be put into the set. The user provides
+// the allocation and deallocation functions. Also, each element has a
+// key, which the lookup is done with. The key may be the whole element
+// (eg. in an OSet of integers, each integer serves both as an element and
+// a key), or it may be only part of it (eg. if the key is a single field
+// in a struct). The user can provide a function that compares an element
+// with a key; this is very flexible, and with the right comparison
+// function even a (non-overlapping) interval list can be created. But
+// the cost of calling a function for every comparison can be high during
+// lookup. If no comparison function is provided, we assume that keys are
+// (signed or unsigned) words, and that the key is the first word in each
+// element. This fast comparison is suitable for an OSet containing
+// structs where the first element is an Addr, for example.
+//
+// Each OSet interface also has an iterator, which makes it simple to
+// traverse all the nodes in order. Note that the iterator maintains state
+// and so is non-reentrant.
+//
// Note that once you insert an element into an OSet, if you modify any part
// of it looked at by your cmp() function, this may cause incorrect
// behaviour as the sorted order maintained will be wrong.
@@ -63,25 +71,97 @@
/*--------------------------------------------------------------------*/
typedef struct _OSet OSet;
-typedef struct _OSetNode OSetNode;
+// - Cmp: returns -1, 0 or 1 if key is <=, == or >= elem.
+// - Alloc: allocates a chunk of memory.
+// - Free: frees a chunk of memory allocated with Alloc.
+
typedef Word (*OSetCmp_t) ( void* key, void* elem );
typedef void* (*OSetAlloc_t) ( SizeT szB );
typedef void (*OSetFree_t) ( void* p );
-typedef void (*OSetNodeDestroy_t) ( void* elem );
/*--------------------------------------------------------------------*/
-/*--- Creating and destroying OSets and OSet members ---*/
+/*--- Creating and destroying OSets (Word) ---*/
/*--------------------------------------------------------------------*/
// * Create: allocates and initialises the OSet. Arguments:
+// - alloc The allocation function used internally for allocating the
+// OSet and all its nodes.
+// - free The deallocation function used internally for freeing nodes
+// called by VG_(OSetWord_Destroy)().
+//
+// * CreateWithCmp: like Create, but you specify your own comparison
+// function.
+//
+// * Destroy: frees all nodes in the table, plus the memory used by
+// the table itself. The passed-in function is called on each node first
+// to allow the destruction of any attached resources; if NULL it is not
+// called.
+
+extern OSet* VG_(OSetWord_Create) ( OSetAlloc_t alloc, OSetFree_t free );
+extern void VG_(OSetWord_Destroy) ( OSet* os );
+
+/*--------------------------------------------------------------------*/
+/*--- Operations on OSets (Word) ---*/
+/*--------------------------------------------------------------------*/
+
+// In everything that follows, the parameter 'key' is always the *address*
+// of the key, and 'elem' is *address* of the elem, as are the return values
+// of the functions that return elems.
+//
+// * Size: The number of elements in the set.
+//
+// * Contains: Determines if the value is in the set.
+//
+// * Insert: Inserts a new element into the set. Duplicates are forbidden,
+// and will cause assertion failures.
+//
+// * Remove: Removes the value from the set, if present. Returns a Bool
+// indicating if the value was removed.
+//
+// * ResetIter: Each OSet has an iterator. This resets it to point to the
+// first element in the OSet.
+//
+// * 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.
+//
+// You can thus iterate in order through a set like this:
+//
+// Word val;
+// VG_(OSetWord_ResetIter)(oset);
+// while ( VG_(OSetWord_Next)(oset, &val) ) {
+// ... do stuff with 'val' ...
+// }
+//
+// Note that iterators are cleared any time an element is inserted or
+// removed from the OSet, to avoid possible mayhem caused by the iterator
+// getting out of sync with the OSet's contents. "Cleared" means that
+// 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 void VG_(OSetWord_ResetIter) ( OSet* os );
+extern Bool VG_(OSetWord_Next) ( OSet* os, Word* val );
+
+
+/*--------------------------------------------------------------------*/
+/*--- Creating and destroying OSets and OSet members (Gen) ---*/
+/*--------------------------------------------------------------------*/
+
+// * Create: allocates and initialises the OSet. Arguments:
// - keyOff The offset of the key within the element.
// - cmp The comparison function between keys and elements, or NULL
// if the OSet should use fast comparisons.
// - alloc The allocation function used for allocating the OSet itself;
-// it's also called for each invocation of VG_(OSet_AllocNode)().
-// - free The deallocation function used by VG_(OSet_FreeNode)() and
-// VG_(OSet_Destroy)().
+// it's also called for each invocation of
+// VG_(OSetGen_AllocNode)().
+// - free The deallocation function used by VG_(OSetGen_FreeNode)() and
+// VG_(OSetGen_Destroy)().
//
// If cmp is NULL, keyOff must be zero. This is checked.
//
@@ -91,25 +171,25 @@
// called.
//
// * AllocNode: Allocate and zero memory for a node to go into the OSet.
-// Uses the alloc function given to VG_(OSet_Create)() to allocated a node
-// which is big enough for both an element and the OSet metadata.
+// Uses the alloc function given to VG_(OSetGen_Create)() to allocated a
+// node which is big enough for both an element and the OSet metadata.
// Not all elements in one OSet have to be the same size.
//
// Note that the element allocated will be at most word-aligned, which may
// be less aligned than the element type would normally be.
//
-// * FreeNode: Deallocate a node allocated with OSet_AllocNode(). Using
+// * FreeNode: Deallocate a node allocated with OSetGen_AllocNode(). Using
// a deallocation function (such as VG_(free)()) directly will likely
// lead to assertions in Valgrind's allocator.
-extern OSet* VG_(OSet_Create) ( OffT keyOff, OSetCmp_t cmp,
- OSetAlloc_t alloc, OSetFree_t free );
-extern void VG_(OSet_Destroy) ( OSet* os, OSetNodeDestroy_t destroyNode );
-extern void* VG_(OSet_AllocNode) ( OSet* os, SizeT elemSize );
-extern void VG_(OSet_FreeNode) ( OSet* os, void* elem );
+extern OSet* VG_(OSetGen_Create) ( OffT keyOff, OSetCmp_t cmp,
+ OSetAlloc_t alloc, OSetFree_t free );
+extern void VG_(OSetGen_Destroy) ( OSet* os );
+extern void* VG_(OSetGen_AllocNode) ( OSet* os, SizeT elemSize );
+extern void VG_(OSetGen_FreeNode) ( OSet* os, void* elem );
/*--------------------------------------------------------------------*/
-/*--- Operations on OSets ---*/
+/*--- Operations on OSets (Gen) ---*/
/*--------------------------------------------------------------------*/
// In everything that follows, the parameter 'key' is always the *address*
@@ -118,6 +198,11 @@
//
// * Size: The number of elements in the set.
//
+// * Insert: Inserts a new element into the set. Note that 'elem' must
+// have been allocated using VG_(OSetGen_AllocNode)(), otherwise you will
+// get assertion failures about "bad magic". Duplicates are forbidden,
+// and will also cause assertion failures.
+//
// * Contains: Determines if any element in the OSet matches the key.
//
// * Lookup: Returns a pointer to the element matching the key, if there is
@@ -126,11 +211,6 @@
// * LookupWithCmp: Like Lookup, but you specify the comparison function,
// which overrides the OSet's normal one.
//
-// * Insert: Inserts a new element into the list. Note that 'elem' must
-// have been allocated using VG_(OSet_AllocNode)(), otherwise you will get
-// assertion failures about "bad magic". Duplicates are forbidden, and
-// will also cause assertion failures.
-//
// * Remove: Removes the element matching the key, if there is one. Returns
// NULL if no element matches the key.
//
@@ -141,27 +221,27 @@
// iterator, and advances the iterator by one; the elements are visited
// in order. Or, returns NULL if the iterator has reached the OSet's end.
//
-// You can thus iterate in order through an OSet like this:
+// You can thus iterate in order through a set like this:
//
-// VG_(OSet_ResetIter)(oset);
-// while ( (elem = VG_(OSet_Next)(oset)) ) {
+// VG_(OSetGen_ResetIter)(oset);
+// while ( (elem = VG_(OSetGen_Next)(oset)) ) {
// ... do stuff with 'elem' ...
// }
//
// Note that iterators are cleared any time an element is inserted or
// removed from the OSet, to avoid possible mayhem caused by the iterator
// getting out of sync with the OSet's contents. "Cleared" means that
-// they will return NULL if VG_(OSet_Next)() is called without an
-// intervening call to VG_(OSet_ResetIter)().
+// they will return NULL if VG_(OSetGen_Next)() is called without an
+// intervening call to VG_(OSetGen_ResetIter)().
-extern Int VG_(OSet_Size) ( OSet* os );
-extern void VG_(OSet_Insert) ( OSet* os, void* elem );
-extern Bool VG_(OSet_Contains) ( OSet* os, void* key );
-extern void* VG_(OSet_Lookup) ( OSet* os, void* key );
-extern void* VG_(OSet_LookupWithCmp)( OSet* os, void* key, OSetCmp_t cmp );
-extern void* VG_(OSet_Remove) ( OSet* os, void* key );
-extern void VG_(OSet_ResetIter) ( OSet* os );
-extern void* VG_(OSet_Next) ( OSet* os );
+extern Int VG_(OSetGen_Size) ( OSet* os );
+extern void VG_(OSetGen_Insert) ( OSet* os, void* elem );
+extern Bool VG_(OSetGen_Contains) ( OSet* os, void* key );
+extern void* VG_(OSetGen_Lookup) ( OSet* os, void* key );
+extern void* VG_(OSetGen_LookupWithCmp)( OSet* os, 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 );
#endif // __PUB_TOOL_OSET_H
Modified: branches/MASSIF2/memcheck/mc_main.c
===================================================================
--- branches/MASSIF2/memcheck/mc_main.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/memcheck/mc_main.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -387,9 +387,9 @@
tl_assert(0 == offsetof(AuxMapEnt,base));
tl_assert(sizeof(Addr) == sizeof(void*));
- auxmap_L2 = VG_(OSet_Create)( /*keyOff*/ offsetof(AuxMapEnt,base),
- /*fastCmp*/ NULL,
- VG_(malloc), VG_(free) );
+ auxmap_L2 = VG_(OSetGen_Create)( /*keyOff*/ offsetof(AuxMapEnt,base),
+ /*fastCmp*/ NULL,
+ VG_(malloc), VG_(free) );
}
/* Check representation invariants; if OK return NULL; else a
@@ -418,7 +418,7 @@
*n_secmaps_found = 0;
if (sizeof(void*) == 4) {
/* 32-bit platform */
- if (VG_(OSet_Size)(auxmap_L2) != 0)
+ if (VG_(OSetGen_Size)(auxmap_L2) != 0)
return "32-bit: auxmap_L2 is non-empty";
for (i = 0; i < N_AUXMAP_L1; i++)
if (auxmap_L1[i].base != 0 || auxmap_L1[i].ent != NULL)
@@ -429,8 +429,8 @@
AuxMapEnt *elem, *res;
AuxMapEnt key;
/* L2 table */
- VG_(OSet_ResetIter)(auxmap_L2);
- while ( (elem = VG_(OSet_Next)(auxmap_L2)) ) {
+ VG_(OSetGen_ResetIter)(auxmap_L2);
+ while ( (elem = VG_(OSetGen_Next)(auxmap_L2)) ) {
elems_seen++;
if (0 != (elem->base & (Addr)0xFFFF))
return "64-bit: nonzero .base & 0xFFFF in auxmap_L2";
@@ -458,7 +458,7 @@
/* Look it up in auxmap_L2. */
key.base = auxmap_L1[i].base;
key.sm = 0;
- res = VG_(OSet_Lookup)(auxmap_L2, &key);
+ res = VG_(OSetGen_Lookup)(auxmap_L2, &key);
if (res == NULL)
return "64-bit: _L1 .base not found in _L2";
if (res != auxmap_L1[i].ent)
@@ -544,7 +544,7 @@
key.base = a;
key.sm = 0;
- res = VG_(OSet_Lookup)(auxmap_L2, &key);
+ res = VG_(OSetGen_Lookup)(auxmap_L2, &key);
if (res)
insert_into_auxmap_L1_at( AUXMAP_L1_INSERT_IX, res );
return res;
@@ -563,11 +563,11 @@
to allocate one. */
a &= ~(Addr)0xFFFF;
- nyu = (AuxMapEnt*) VG_(OSet_AllocNode)( auxmap_L2, sizeof(AuxMapEnt) );
+ nyu = (AuxMapEnt*) VG_(OSetGen_AllocNode)( auxmap_L2, sizeof(AuxMapEnt) );
tl_assert(nyu);
nyu->base = a;
nyu->sm = &sm_distinguished[SM_DIST_NOACCESS];
- VG_(OSet_Insert)( auxmap_L2, nyu );
+ VG_(OSetGen_Insert)( auxmap_L2, nyu );
insert_into_auxmap_L1_at( AUXMAP_L1_INSERT_IX, nyu );
n_auxmap_L2_nodes++;
return nyu;
@@ -879,9 +879,9 @@
static OSet* createSecVBitTable(void)
{
- return VG_(OSet_Create)( offsetof(SecVBitNode, a),
- NULL, // use fast comparisons
- VG_(malloc), VG_(free) );
+ return VG_(OSetGen_Create)( offsetof(SecVBitNode, a),
+ NULL, // use fast comparisons
+ VG_(malloc), VG_(free) );
}
static void gcSecVBitTable(void)
@@ -896,8 +896,8 @@
secVBitTable2 = createSecVBitTable();
// Traverse the table, moving fresh nodes into the new table.
- VG_(OSet_ResetIter)(secVBitTable);
- while ( (n = VG_(OSet_Next)(secVBitTable)) ) {
+ VG_(OSetGen_ResetIter)(secVBitTable);
+ while ( (n = VG_(OSetGen_Next)(secVBitTable)) ) {
Bool keep = False;
if ( (GCs_done - n->last_touched) <= MAX_STALE_AGE ) {
// Keep node if it's been touched recently enough (regardless of
@@ -918,18 +918,18 @@
if ( keep ) {
// Insert a copy of the node into the new table.
SecVBitNode* n2 =
- VG_(OSet_AllocNode)(secVBitTable2, sizeof(SecVBitNode));
+ VG_(OSetGen_AllocNode)(secVBitTable2, sizeof(SecVBitNode));
*n2 = *n;
- VG_(OSet_Insert)(secVBitTable2, n2);
+ VG_(OSetGen_Insert)(secVBitTable2, n2);
}
}
// Get the before and after sizes.
- n_nodes = VG_(OSet_Size)(secVBitTable);
- n_survivors = VG_(OSet_Size)(secVBitTable2);
+ n_nodes = VG_(OSetGen_Size)(secVBitTable);
+ n_survivors = VG_(OSetGen_Size)(secVBitTable2);
// Destroy the old table, and put the new one in its place.
- VG_(OSet_Destroy)(secVBitTable, NULL);
+ VG_(OSetGen_Destroy)(secVBitTable);
secVBitTable = secVBitTable2;
if (VG_(clo_verbosity) > 1) {
@@ -952,7 +952,7 @@
{
Addr aAligned = VG_ROUNDDN(a, BYTES_PER_SEC_VBIT_NODE);
Int amod = a % BYTES_PER_SEC_VBIT_NODE;
- SecVBitNode* n = VG_(OSet_Lookup)(secVBitTable, &aAligned);
+ SecVBitNode* n = VG_(OSetGen_Lookup)(secVBitTable, &aAligned);
UChar vbits8;
tl_assert2(n, "get_sec_vbits8: no node for address %p (%p)\n", aAligned, a);
// Shouldn't be fully defined or fully undefined -- those cases shouldn't
@@ -966,7 +966,7 @@
{
Addr aAligned = VG_ROUNDDN(a, BYTES_PER_SEC_VBIT_NODE);
Int i, amod = a % BYTES_PER_SEC_VBIT_NODE;
- SecVBitNode* n = VG_(OSet_Lookup)(secVBitTable, &aAligned);
+ SecVBitNode* n = VG_(OSetGen_Lookup)(secVBitTable, &aAligned);
// Shouldn't be fully defined or fully undefined -- those cases shouldn't
// make it to the secondary V bits table.
tl_assert(V_BITS8_DEFINED != vbits8 && V_BITS8_UNDEFINED != vbits8);
@@ -977,7 +977,7 @@
} else {
// New node: assign the specific byte, make the rest invalid (they
// should never be read as-is, but be cautious).
- n = VG_(OSet_AllocNode)(secVBitTable, sizeof(SecVBitNode));
+ n = VG_(OSetGen_AllocNode)(secVBitTable, sizeof(SecVBitNode));
n->a = aAligned;
for (i = 0; i < BYTES_PER_SEC_VBIT_NODE; i++) {
n->vbits8[i] = V_BITS8_UNDEFINED;
@@ -987,15 +987,15 @@
// Do a table GC if necessary. Nb: do this before inserting the new
// node, to avoid erroneously GC'ing the new node.
- if (secVBitLimit == VG_(OSet_Size)(secVBitTable)) {
+ if (secVBitLimit == VG_(OSetGen_Size)(secVBitTable)) {
gcSecVBitTable();
}
// Insert the new node.
- VG_(OSet_Insert)(secVBitTable, n);
+ VG_(OSetGen_Insert)(secVBitTable, n);
sec_vbits_new_nodes++;
- n_secVBit_nodes = VG_(OSet_Size)(secVBitTable);
+ n_secVBit_nodes = VG_(OSetGen_Size)(secVBitTable);
if (n_secVBit_nodes > max_secVBit_nodes)
max_secVBit_nodes = n_secVBit_nodes;
}
@@ -4316,7 +4316,7 @@
/* If we're not checking for undefined value errors, the secondary V bit
* table should be empty. */
if (!MC_(clo_undef_value_errors)) {
- if (0 != VG_(OSet_Size)(secVBitTable))
+ if (0 != VG_(OSetGen_Size)(secVBitTable))
return False;
}
Modified: branches/MASSIF2/memcheck/tests/oset_test.c
===================================================================
--- branches/MASSIF2/memcheck/tests/oset_test.c 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/memcheck/tests/oset_test.c 2007-09-17 05:45:40 UTC (rev 6843)
@@ -77,23 +77,24 @@
// Create a static OSet of Ints. This one uses fast (built-in)
// comparisons.
- OSet* oset1 = VG_(OSet_Create)(0,
+ OSet* oset = VG_(OSetGen_Create)(0,
NULL,
(void*)malloc, free);
// Try some operations on an empty OSet to ensure they don't screw up.
- vg_assert( ! VG_(OSet_Contains)(oset1, &v) );
- vg_assert( ! VG_(OSet_Lookup)(oset1, &v) );
- vg_assert( ! VG_(OSet_Remove)(oset1, &v) );
- vg_assert( ! VG_(OSet_Next)(oset1) );
- vg_assert( 0 == VG_(OSet_Size)(oset1) );
+ vg_assert( ! VG_(OSetGen_Contains)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Remove)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( 0 == VG_(OSetGen_Size)(oset) );
// Create some elements, with gaps (they're all even) but no dups,
// and shuffle them randomly.
for (i = 0; i < NN; i++) {
- vs[i] = VG_(OSet_AllocNode)(oset1, sizeof(Word));
+ vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word));
*(vs[i]) = 2*i;
}
+ seed = 0;
for (i = 0; i < NN; i++) {
Word r1 = myrandom() % NN;
Word r2 = myrandom() % NN;
@@ -104,32 +105,32 @@
// Insert the elements
for (i = 0; i < NN; i++) {
- VG_(OSet_Insert)(oset1, vs[i]);
+ VG_(OSetGen_Insert)(oset, vs[i]);
}
// Check the size
- vg_assert( NN == VG_(OSet_Size)(oset1) );
+ vg_assert( NN == VG_(OSetGen_Size)(oset) );
// Check we can find all the elements we inserted
for (i = 0; i < NN; i++) {
- assert( VG_(OSet_Contains)(oset1, vs[i]) );
+ assert( VG_(OSetGen_Contains)(oset, vs[i]) );
}
// Check we cannot find elements we did not insert, below, within (odd
// numbers), and above the inserted elements.
v = -1;
- assert( ! VG_(OSet_Contains)(oset1, &v) );
+ assert( ! VG_(OSetGen_Contains)(oset, &v) );
for (i = 0; i < NN; i++) {
v = *(vs[i]) + 1;
- assert( ! VG_(OSet_Contains)(oset1, &v) );
+ assert( ! VG_(OSetGen_Contains)(oset, &v) );
}
v = NN*2;
- assert( ! VG_(OSet_Contains)(oset1, &v) );
+ assert( ! VG_(OSetGen_Contains)(oset, &v) );
// Check we can find all the elements we inserted, and the right values
// are returned.
for (i = 0; i < NN; i++) {
- assert( vs[i] == VG_(OSet_Lookup)(oset1, vs[i]) );
+ assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) );
}
// Check that we can iterate over the OSet elements in sorted order, and
@@ -137,70 +138,189 @@
n = 0;
pv = NULL;
prev = -1;
- VG_(OSet_ResetIter)(oset1);
- while ( (pv = VG_(OSet_Next)(oset1)) ) {
+ VG_(OSetGen_ResetIter)(oset);
+ while ( (pv = VG_(OSetGen_Next)(oset)) ) {
Word curr = *pv;
assert(prev < curr);
prev = curr;
n++;
}
assert(NN == n);
- vg_assert( ! VG_(OSet_Next)(oset1) );
- vg_assert( ! VG_(OSet_Next)(oset1) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
// Check that we can remove half of the elements, and that their values
// are as expected.
for (i = 0; i < NN; i += 2) {
- assert( pv = VG_(OSet_Remove)(oset1, vs[i]) );
+ assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) );
assert( pv == vs[i] );
}
// Check the size
- vg_assert( NN/2 == VG_(OSet_Size)(oset1) );
+ vg_assert( NN/2 == VG_(OSetGen_Size)(oset) );
// Check we can find the remaining elements (with the right values).
for (i = 1; i < NN; i += 2) {
- assert( pv = VG_(OSet_LookupWithCmp)(oset1, vs[i], NULL) );
+ assert( pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL) );
assert( pv == vs[i] );
}
// Check we cannot find any of the elements we removed.
for (i = 0; i < NN; i += 2) {
- assert( ! VG_(OSet_Contains)(oset1, vs[i]) );
+ assert( ! VG_(OSetGen_Contains)(oset, vs[i]) );
}
// Check that we can remove the remaining half of the elements, and that
// their values are as expected.
for (i = 1; i < NN; i += 2) {
- assert( pv = VG_(OSet_Remove)(oset1, vs[i]) );
+ assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) );
assert( pv == vs[i] );
}
// Try some more operations on the empty OSet to ensure they don't screw up.
- vg_assert( ! VG_(OSet_Contains)(oset1, &v) );
- vg_assert( ! VG_(OSet_Lookup)(oset1, &v) );
- vg_assert( ! VG_(OSet_Remove)(oset1, &v) );
- vg_assert( ! VG_(OSet_Next)(oset1) );
- vg_assert( 0 == VG_(OSet_Size)(oset1) );
+ vg_assert( ! VG_(OSetGen_Contains)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Remove)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( 0 == VG_(OSetGen_Size)(oset) );
// Free a few elements
- VG_(OSet_FreeNode)(oset1, vs[0]);
- VG_(OSet_FreeNode)(oset1, vs[1]);
- VG_(OSet_FreeNode)(oset1, vs[2]);
+ VG_(OSetGen_FreeNode)(oset, vs[0]);
+ VG_(OSetGen_FreeNode)(oset, vs[1]);
+ VG_(OSetGen_FreeNode)(oset, vs[2]);
- // Re-insert remaining elements, to give OSet_Destroy something to work with.
+ // Re-insert remaining elements, to give OSetGen_Destroy something to
+ // work with.
for (i = 3; i < NN; i++) {
- VG_(OSet_Insert)(oset1, vs[i]);
+ VG_(OSetGen_Insert)(oset, vs[i]);
}
// Print the list
- OSet_Print(oset1, "foo", wordToStr);
+ OSet_Print(oset, "oset1", wordToStr);
// Destroy the OSet
- VG_(OSet_Destroy)(oset1, NULL);
+ VG_(OSetGen_Destroy)(oset);
}
+void example1b(void)
+{
+ Int i, n;
+ Word v = 0, prev;
+ Word vs[NN];
+ Word *pv;
+
+ // Create a static OSet of Ints. This one uses fast (built-in)
+ // comparisons.
+ OSet* oset = VG_(OSetWord_Create)( (void*)malloc, free);
+
+ // Try some operations on an empty OSet to ensure they don't screw up.
+ vg_assert( ! VG_(OSetWord_Contains)(oset, v) );
+ vg_assert( ! VG_(OSetWord_Remove)(oset, v) );
+ vg_assert( ! VG_(OSetWord_Next)(oset, &v) );
+ vg_assert( 0 == VG_(OSetWord_Size)(oset) );
+
+ // Create some elements, with gaps (they're all even) but no dups,
+ // and shuffle them randomly.
+ for (i = 0; i < NN; i++) {
+ vs[i] = 2*i;
+ }
+ seed = 0;
+ for (i = 0; i < NN; i++) {
+ Word r1 = myrandom() % NN;
+ Word r2 = myrandom() % NN;
+ Word tmp = vs[r1];
+ vs[r1] = vs[r2];
+ vs[r2] = tmp;
+ }
+
+ // Insert the elements
+ for (i = 0; i < NN; i++) {
+ VG_(OSetWord_Insert)(oset, vs[i]);
+ }
+
+ // Check the size
+ vg_assert( NN == VG_(OSetWord_Size)(oset) );
+
+ // Check we can find all the elements we inserted
+ for (i = 0; i < NN; i++) {
+ assert( VG_(OSetWord_Contains)(oset, vs[i]) );
+ }
+
+ // Check we cannot find elements we did not insert, below, within (odd
+ // numbers), and above the inserted elements.
+ v = -1;
+ assert( ! VG_(OSetWord_Contains)(oset, v) );
+ for (i = 0; i < NN; i++) {
+ v = vs[i] + 1;
+ assert( ! VG_(OSetWord_Contains)(oset, v) );
+ }
+ v = NN*2;
+ assert( ! VG_(OSetWord_Contains)(oset, v) );
+
+ // Check we can find all the elements we inserted.
+ for (i = 0; i < NN; i++) {
+ assert( VG_(OSetWord_Contains)(oset, vs[i]) );
+ }
+
+ // Check that we can iterate over the OSet elements in sorted order, and
+ // there is the right number of them.
+ n = 0;
+ prev = -1;
+ VG_(OSetWord_ResetIter)(oset);
+ while ( VG_(OSetWord_Next)(oset, &v) ) {
+ Word curr = v;
+ assert(prev < curr);
+ prev = curr;
+ n++;
+ }
+ assert(NN == n);
+ vg_assert( ! VG_(OSetWord_Next)(oset, &v) );
+ vg_assert( ! VG_(OSetWord_Next)(oset, &v) );
+
+ // Check that we can remove half of the elements.
+ for (i = 0; i < NN; i += 2) {
+ assert( VG_(OSetWord_Remove)(oset, vs[i]) );
+ }
+
+ // Check the size
+ vg_assert( NN/2 == VG_(OSetWord_Size)(oset) );
+
+ // Check we can find the remaining elements (with the right values).
+ for (i = 1; i < NN; i += 2) {
+ assert( VG_(OSetWord_Contains)(oset, vs[i]) );
+ }
+
+ // Check we cannot find any of the elements we removed.
+ for (i = 0; i < NN; i += 2) {
+ assert( ! VG_(OSetWord_Contains)(oset, vs[i]) );
+ }
+
+ // Check that we can remove the remaining half of the elements.
+ for (i = 1; i < NN; i += 2) {
+ assert( VG_(OSetWord_Remove)(oset, vs[i]) );
+ }
+
+ // Try some more operations on the empty OSet to ensure they don't screw up.
+ vg_assert( ! VG_(OSetWord_Contains)(oset, v) );
+ vg_assert( ! VG_(OSetWord_Remove)(oset, v) );
+ vg_assert( ! VG_(OSetWord_Next)(oset, &v) );
+ vg_assert( 0 == VG_(OSetWord_Size)(oset) );
+
+ // Re-insert remaining elements, to give OSetWord_Destroy something to
+ // work with.
+ for (i = 3; i < NN; i++) {
+ VG_(OSetWord_Insert)(oset, vs[i]);
+ }
+
+ // Print the list
+ OSet_Print(oset, "oset1b", wordToStr);
+
+ // Destroy the OSet
+ VG_(OSetWord_Destroy)(oset);
+}
+
+
//---------------------------------------------------------------------------
// Struct example
//---------------------------------------------------------------------------
@@ -248,26 +368,27 @@
// Create a dynamic OSet of Blocks. This one uses slow (custom)
// comparisons.
- OSet* oset2 = VG_(OSet_Create)(offsetof(Block, first),
+ OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first),
blockCmp,
(void*)malloc, free);
// Try some operations on an empty OSet to ensure they don't screw up.
- vg_assert( ! VG_(OSet_Contains)(oset2, &v) );
- vg_assert( ! VG_(OSet_Lookup)(oset2, &v) );
- vg_assert( ! VG_(OSet_Remove)(oset2, &v) );
- vg_assert( ! VG_(OSet_Next)(oset2) );
- vg_assert( 0 == VG_(OSet_Size)(oset2) );
+ vg_assert( ! VG_(OSetGen_Contains)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Remove)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( 0 == VG_(OSetGen_Size)(oset) );
// Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but
// no dups, and shuffle them randomly.
for (i = 0; i < NN; i++) {
- vs[i] = VG_(OSet_AllocNode)(oset2, sizeof(Block));
+ vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block));
vs[i]->b1 = i;
vs[i]->first = i*10 + 1;
vs[i]->last = vs[i]->first + 2;
vs[i]->b2 = i+1;
}
+ seed = 0;
for (i = 0; i < NN; i++) {
Int r1 = myrandom() % NN;
Int r2 = myrandom() % NN;
@@ -278,36 +399,36 @@
// Insert the elements
for (i = 0; i < NN; i++) {
- VG_(OSet_Insert)(oset2, vs[i]);
+ VG_(OSetGen_Insert)(oset, vs[i]);
}
// Check the size
- vg_assert( NN == VG_(OSet_Size)(oset2) );
+ vg_assert( NN == VG_(OSetGen_Size)(oset) );
// Check we can find all the elements we inserted, within the full range
// of each Block.
for (i = 0; i < NN; i++) {
- a = vs[i]->first + 0; assert( VG_(OSet_Contains)(oset2, &a) );
- a = vs[i]->first + 1; assert( VG_(OSet_Contains)(oset2, &a) );
- a = vs[i]->first + 2; assert( VG_(OSet_Contains)(oset2, &a) );
+ a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) );
+ a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) );
+ a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) );
}
// Check we cannot find elements we did not insert, below and above the
// ranges of the inserted elements.
a = 0;
- assert( ! VG_(OSet_Contains)(oset2, &a) );
+ assert( ! VG_(OSetGen_Contains)(oset, &a) );
for (i = 0; i < NN; i++) {
- a = vs[i]->first - 1; assert( ! VG_(OSet_Contains)(oset2, &a) );
- a = vs[i]->first + 3; assert( ! VG_(OSet_Contains)(oset2, &a) );
+ a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) );
+ a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) );
}
// Check we can find all the elements we inserted, and the right values
// are returned.
for (i = 0; i < NN; i++) {
- a = vs[i]->first + 0; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
- a = vs[i]->first + 1; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
- a = vs[i]->first + 2; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
- assert( vs[i] == VG_(OSet_LookupWithCmp)(oset2, &a, blockCmp) );
+ a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
+ a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
+ a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
+ assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) );
}
// Check that we can iterate over the OSet elements in sorted order, and
@@ -315,60 +436,60 @@
n = 0;
pv = NULL;
prev.last = 0;
- VG_(OSet_ResetIter)(oset2);
- while ( (pv = VG_(OSet_Next)(oset2)) ) {
+ VG_(OSetGen_ResetIter)(oset);
+ while ( (pv = VG_(OSetGen_Next)(oset)) ) {
Block curr = *pv;
assert(prev.last < curr.first);
prev = curr;
n++;
}
assert(NN == n);
- vg_assert( ! VG_(OSet_Next)(oset2) );
- vg_assert( ! VG_(OSet_Next)(oset2) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
// Check that we can remove half of the elements, and that their values
// are as expected.
for (i = 0; i < NN; i += 2) {
- a = vs[i]->first; assert( vs[i] == VG_(OSet_Remove)(oset2, &a) );
+ a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) );
}
// Check the size
- vg_assert( NN/2 == VG_(OSet_Size)(oset2) );
+ vg_assert( NN/2 == VG_(OSetGen_Size)(oset) );
// Check we can find the remaining elements (with the right values).
for (i = 1; i < NN; i += 2) {
- a = vs[i]->first + 0; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
- a = vs[i]->first + 1; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
- a = vs[i]->first + 2; assert( vs[i] == VG_(OSet_Lookup)(oset2, &a) );
+ a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
+ a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
+ a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) );
}
// Check we cannot find any of the elements we removed.
for (i = 0; i < NN; i += 2) {
- a = vs[i]->first + 0; assert( ! VG_(OSet_Contains)(oset2, &a) );
- a = vs[i]->first + 1; assert( ! VG_(OSet_Contains)(oset2, &a) );
- a = vs[i]->first + 2; assert( ! VG_(OSet_Contains)(oset2, &a) );
+ a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) );
+ a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) );
+ a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) );
}
// Check that we can remove the remaining half of the elements, and that
// their values are as expected.
for (i = 1; i < NN; i += 2) {
- a = vs[i]->first; assert( vs[i] == VG_(OSet_Remove)(oset2, &a) );
+ a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) );
}
// Try some more operations on the empty OSet to ensure they don't screw up.
- vg_assert( ! VG_(OSet_Contains)(oset2, &v) );
- vg_assert( ! VG_(OSet_Lookup)(oset2, &v) );
- vg_assert( ! VG_(OSet_Remove)(oset2, &v) );
- vg_assert( ! VG_(OSet_Next)(oset2) );
- vg_assert( 0 == VG_(OSet_Size)(oset2) );
+ vg_assert( ! VG_(OSetGen_Contains)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Remove)(oset, &v) );
+ vg_assert( ! VG_(OSetGen_Next)(oset) );
+ vg_assert( 0 == VG_(OSetGen_Size)(oset) );
- // Re-insert all elements, to give OSet_Destroy something to work with.
+ // Re-insert all elements, to give OSetGen_Destroy something to work with.
for (i = 0; i < NN; i++) {
- VG_(OSet_Insert)(oset2, vs[i]);
+ VG_(OSetGen_Insert)(oset, vs[i]);
}
// Destroy the OSet
- VG_(OSet_Destroy)(oset2, NULL);
+ VG_(OSetGen_Destroy)(oset);
}
//-----------------------------------------------------------------------
@@ -378,6 +499,7 @@
int main(void)
{
example1();
+ example1b();
example2();
return 0;
}
Modified: branches/MASSIF2/memcheck/tests/oset_test.stdout.exp
===================================================================
--- branches/MASSIF2/memcheck/tests/oset_test.stdout.exp 2007-09-17 05:35:10 UTC (rev 6842)
+++ branches/MASSIF2/memcheck/tests/oset_test.stdout.exp 2007-09-17 05:45:40 UTC (rev 6843)
@@ -1,4 +1,4 @@
--- start foo ----------------
+-- start oset1 ----------------
.. .. .. .. .. .. .. .. .. 1998
.. .. .. .. .. .. .. .. 1996
.. .. .. .. .. .. .. .. .. .. 1994
@@ -996,4 +996,1003 @@
.. .. .. .. .. .. .. .. .. 4
.. .. .. .. .. .. .. .. 2
.. .. .. .. .. .. .. .. .. 0
--- end foo ----------------
+-- end oset1 ----------------
+-- start oset1b ----------------
+.. .. .. .. .. .. .. .. .. 1998
+.. .. .. .. .. .. .. .. 1996
+.. .. .. .. .. .. .. .. .. .. 1994
+.. .. .. .. .. .. .. .. .. 1992
+.. .. .. .. .. .. .. .. .. .. 1990
+.. .. .. .. .. .. .. 1988
+.. .. .. .. .. .. .. .. .. 1986
+.. .. .. .. .. .. .. .. .. .. 1984
+.. .. .. .. .. .. .. .. 1982
+.. .. .. .. .. .. .. .. .. .. 1980
+.. .. .. .. .. .. .. .. .. 1978
+.. .. .. .. .. .. .. .. .. .. 1976
+.. .. .. .. .. .. 1974
+.. .. .. .. .. .. .. .. .. .. 1972
+.. .. .. .. .. .. .. .. .. 1970
+.. .. .. .. .. .. .. .. .. .. 1968
+.. .. .. .. .. .. .. .. 1966
+.. .. .. .. .. .. .. .. .. .. 1964
+.. .. .. .. .. .. .. .. .. 1962
+.. .. .. .. .. .. .. 1960
+.. .. .. .. .. .. .. .. .. .. 1958
+.. .. .. .. .. .. .. .. .. 1956
+.. .. .. .. .. .. .. .. 1954
+.. .. .. .. .. .. .. .. .. .. 1952
+.. .. .. .. .. .. .. .. .. 1950
+.. .. .. .. .. .. .. .. .. .. 1948
+.. .. .. .. .. 1946
+.. .. .. .. .. .. .. .. .. 1944
+.. .. .. .. .. .. .. .. 1942
+.. .. .. .. .. .. .. 1940
+.. .. .. .. .. .. .. .. .. .. 1938
+.. .. .. .. .. .. .. .. .. 1936
+.. .. .. .. .. .. .. .. 1934
+.. .. .. .. .. .. .. .. .. 1932
+.. .. .. .. .. .. 1930
+.. .. .. .. .. .. .. .. .. 1928
+.. .. .. .. .. .. .. .. .. .. 1926
+.. .. .. .. .. .. .. .. 1924
+.. .. .. .. .. .. .. .. .. .. 1922
+.. .. .. .. .. .. .. .. .. 1920
+.. .. .. .. .. .. .. .. .. .. 1918
+.. .. .. .. .. .. .. 1916
+.. .. .. .. .. .. .. .. .. 1914
+.. .. .. .. .. .. .. .. 1912
+.. .. .. .. .. .. .. .. .. .. 1910
+.. .. .. .. .. .. .. .. .. 1908
+.. .. .. .. .. .. .. .. .. .. 1906
+.. .. .. .. 1904
+.. .. .. .. .. .. .. .. .. 1902
+.. .. .. .. .. .. .. .. 1900
+.. .. .. .. .. .. .. 1898
+.. .. .. .. .. .. .. .. .. 1896
+.. .. .. .. .. .. .. .. 1894
+.. .. .. .. .. .. .. .. .. 1892
+.. .. .. .. .. .. 1890
+.. .. .. .. .. .. .. .. .. .. 1888
+.. .. .. .. .. .. .. .. .. 1886
+.. .. .. .. .. .. .. .. .. .. 1884
+.. .. .. .. .. .. .. .. 1882
+.. .. .. .. .. .. .. .. .. 1880
+.. .. .. .. .. .. .. 1878
+.. .. .. .. .. .. .. .. 1876
+.. .. .. .. .. .. .. .. .. 1874
+.. .. .. .. .. 1872
+.. .. .. .. .. .. .. .. .. .. 1870
+.. .. .. .. .. .. .. .. .. 1868
+.. .. .. .. .. .. .. .. .. .. 1866
+.. .. .. .. .. .. .. .. 1864
+.. .. .. .. .. .. .. .. .. 1862
+.. .. .. .. .. .. .. .. .. .. 1860
+.. .. .. .. .. .. .. 1858
+.. .. .. .. .. .. .. .. .. 1856
+.. .. .. .. .. .. .. .. 1854
+.. .. .. .. .. .. .. .. .. 1852
+.. .. .. .. .. .. 1848
+.. .. .. .. .. .. .. .. .. 1846
+.. .. .. .. .. .. .. .. 1844
+.. .. .. .. .. .. .. .. .. .. 1842
+.. .. .. .. .. .. .. .. .. 1...
[truncated message content] |