unit_oset.c revision ed07e00d438c74b7a23c01bfffde77e3968305e4
1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <assert.h> 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <stdio.h> 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <stdlib.h> 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <string.h> 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_basics.h" 8ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcbase.h" 9ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcassert.h" 10ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "pub_core_libcprint.h" 11ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 12ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// I need this to avoid some signedness warnings, not sure why 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// #define Char char 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// jrs 19 Aug 2005: m_oset.c relies on Char being a signed char. 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// It appears that plain 'char' on ppc32 is unsigned and so the 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// above #define screws up the AVL tree balancing logic and 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// leads to segfaults. Commenting it out and using the standard 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// definition of Char from pub_core_basics.h seems a good solution 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// as that has the same signedness on all platforms. 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Crudely redirect various VG_(foo)() functions to their libc equivalents. 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef vg_assert 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define vg_assert(e) assert(e) 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#undef vg_assert2 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define vg_assert2(e, fmt, args...) assert(e) 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define vgPlain_printf printf 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define vgPlain_memset memset 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define vgPlain_memcpy memcpy 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "coregrind/m_oset.c" 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define NN 1000 // Size of OSets being created 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Consistent random number generator, so it produces the 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown same results on all platforms. */ 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define random error_do_not_use_libc_random 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt seed = 0; 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt myrandom( void ) 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = (1103515245 * seed + 12345); 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return seed; 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void* allocate_node(HChar* cc, SizeT szB) 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ return malloc(szB); } 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void free_node(void* p) 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ return free(p); } 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Word example 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This example shows that an element can be a single value (in this 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// case a Word), in which case the element is also the key. 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char *wordToStr(void *p) 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown static char buf[32]; 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sprintf(buf, "%ld", *(Word*)p); 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return buf; 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Word wordCmp(void* vkey, void* velem) 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return *(Word*)vkey - *(Word*)velem; 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid example1(void) 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word v, prev; 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word* vs[NN]; 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word *pv; 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create a static OSet of Ints. This one uses fast (built-in) 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // comparisons. 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* oset = VG_(OSetGen_Create)(0, 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown NULL, 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown allocate_node, "oset_test.1", free_node); 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some elements, with gaps (they're all even) but no dups, 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // and shuffle them randomly. 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word)); 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *(vs[i]) = 2*i; 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r1 = myrandom() % NN; 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r2 = myrandom() % NN; 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word* tmp= vs[r1]; 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetGen_Size)(oset) ); 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetGen_Contains)(oset, vs[i]) ); 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below, within (odd 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // numbers), and above the inserted elements. 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = -1; 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = *(vs[i]) + 1; 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = NN*2; 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, and the right values 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are returned. 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) ); 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = NULL; 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = -1; 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(oset); 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( (pv = VG_(OSetGen_Next)(oset)) ) { 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word curr = *pv; 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev < curr); 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements, and that their values 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are as expected. 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL) ); 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, vs[i]) ); 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements, and that 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // their values are as expected. 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Free a few elements 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[0]); 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[1]); 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[2]); 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert remaining elements, to give OSetGen_Destroy something to 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // work with. 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 3; i < NN; i++) { 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Print the list 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet_Print(oset, "oset1", wordToStr); 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 207ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Destroy)(oset); 208ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 209ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 210ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 211ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid example1b(void) 212ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 213ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 214ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word v = 0, prev; 215ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word vs[NN]; 216ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 217ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create a static OSet of Ints. This one uses fast (built-in) 218ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // comparisons. 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* oset = VG_(OSetWord_Create)(allocate_node, "oset_test.2", free_node); 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some elements, with gaps (they're all even) but no dups, 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // and shuffle them randomly. 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = 2*i; 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r1 = myrandom() % NN; 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r2 = myrandom() % NN; 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word tmp = vs[r1]; 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 241ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 242ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 243ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Insert)(oset, vs[i]); 244ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 245ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 246ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 247ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetWord_Size)(oset) ); 248ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 249ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted 250ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 251ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 252ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 253ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below, within (odd 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // numbers), and above the inserted elements. 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = -1; 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = vs[i] + 1; 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = NN*2; 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted. 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = -1; 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_ResetIter)(oset); 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( VG_(OSetWord_Next)(oset, &v) ) { 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word curr = v; 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev < curr); 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements. 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetWord_Size)(oset) ); 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, vs[i]) ); 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements. 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert remaining elements, to give OSetWord_Destroy something to 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // work with. 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 3; i < NN; i++) { 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Insert)(oset, vs[i]); 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Print the list 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet_Print(oset, "oset1b", wordToStr); 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Destroy)(oset); 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Struct example 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This element shows that a key can be in the middle of the element, and 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// be of arbitrary size and even span multiple (contiguous) fields. It 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// also demonstrates how an OSet can be used to implement a list of 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// non-overlapping intervals. 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct { 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int b1; 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr first; 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr last; 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int b2; 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBlock; 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char *blockToStr(void *p) 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown static char buf[32]; 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* b = (Block*)p; 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sprintf(buf, "<(%d) %lu..%lu (%d)>", b->b1, b->first, b->last, b->b2); 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return buf; 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Word blockCmp(const void* vkey, const void* velem) 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr key = *(const Addr*)vkey; 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Block* elem = (const Block*)velem; 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(elem->first <= elem->last); 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (key < elem->first) return -1; 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (key > elem->last) return 1; 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid example2(void) 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr a; 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* vs[NN]; 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block v, prev; 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block *pv; 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create a dynamic OSet of Blocks. This one uses slow (custom) 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // comparisons. 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first), 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown blockCmp, 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown allocate_node, "oset_test.3", free_node); 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // no dups, and shuffle them randomly. 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block)); 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->b1 = i; 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->first = i*10 + 1; 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->last = vs[i]->first + 2; 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->b2 = i+1; 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r1 = myrandom() % NN; 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r2 = myrandom() % NN; 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* tmp = vs[r1]; 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetGen_Size)(oset) ); 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, within the full range 413ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // of each Block. 414ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 415ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) ); 416ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) ); 417ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) ); 418ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 419ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 420ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below and above the 421ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // ranges of the inserted elements. 422ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = 0; 423ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &a) ); 424ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 425ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 426ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 427ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 428ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 429ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, and the right values 430ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are returned. 431ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 432ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 433ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 434ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 435ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) ); 436ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 437ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 438ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 439ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 440ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 441ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = NULL; 442ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev.last = 0; 443ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(oset); 444ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( (pv = VG_(OSetGen_Next)(oset)) ) { 445ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block curr = *pv; 446ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev.last < curr.first); 447ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 448ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 449ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 450ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 451ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 452ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 453ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 454ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements, and that their values 455ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are as expected. 456ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 457ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 458ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 459ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 460ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 461ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 462ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 463ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 464ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 465ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 466ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 467ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 468ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 469ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 470ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 471ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 472ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 473ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 474ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 475ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 476ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 477ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements, and that 478ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // their values are as expected. 479ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 480ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 481ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 482ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 483ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 484ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 485ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 486ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 487ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 488ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 489ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 490ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert all elements, to give OSetGen_Destroy something to work with. 491ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 492ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 493ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 494ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 495ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 496ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Destroy)(oset); 497ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 498ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 499ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//----------------------------------------------------------------------- 500ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// main() 501ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//----------------------------------------------------------------------- 502ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 503ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownint main(void) 504ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 505ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example1(); 506ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example1b(); 507ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example2(); 508ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 509ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 510