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 30663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#define vgPlain_memmove memmove 31663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 32663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng// Crudely replace some functions (in m_xarray.c, but not needed for 33663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng// this unit test) by (hopefully) failing asserts. 34663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#define vgPlain_ssort(a,b,c,d) assert(a) 35663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#define vgPlain_vcbprintf(a,b,...) assert(a == b) 36663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#include "coregrind/m_xarray.c" 37663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#undef vgPlain_ssort 38663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#undef vgPlain_vcbprintf 39663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng#include "coregrind/m_poolalloc.c" 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "coregrind/m_oset.c" 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define NN 1000 // Size of OSets being created 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Consistent random number generator, so it produces the 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown same results on all platforms. */ 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define random error_do_not_use_libc_random 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt seed = 0; 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic UInt myrandom( void ) 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = (1103515245 * seed + 12345); 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return seed; 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void* allocate_node(HChar* cc, SizeT szB) 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ return malloc(szB); } 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic void free_node(void* p) 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ return free(p); } 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Word example 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This example shows that an element can be a single value (in this 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// case a Word), in which case the element is also the key. 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char *wordToStr(void *p) 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown static char buf[32]; 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sprintf(buf, "%ld", *(Word*)p); 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return buf; 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Word wordCmp(void* vkey, void* velem) 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return *(Word*)vkey - *(Word*)velem; 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 85663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengvoid example1singleset(OSet* oset, char *descr) 86ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 87ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word v, prev; 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word* vs[NN]; 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word *pv; 91ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 95ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 96ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 97ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 98ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 99ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some elements, with gaps (they're all even) but no dups, 100ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // and shuffle them randomly. 101ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 102ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word)); 103ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown *(vs[i]) = 2*i; 104ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 105ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 106ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 107ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r1 = myrandom() % NN; 108ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r2 = myrandom() % NN; 109ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word* tmp= vs[r1]; 110ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 111ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 112ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 113ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 114ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 115ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetGen_Size)(oset) ); 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetGen_Contains)(oset, vs[i]) ); 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 127ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below, within (odd 128ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // numbers), and above the inserted elements. 129ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = -1; 130ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 131ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 132ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = *(vs[i]) + 1; 133ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 134ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 135ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = NN*2; 136ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &v) ); 137ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 138ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, and the right values 139ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are returned. 140ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 141ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) ); 142ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 143ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 144ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 145ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 146ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 147ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = NULL; 148ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = -1; 149ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(oset); 150ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( (pv = VG_(OSetGen_Next)(oset)) ) { 151ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word curr = *pv; 152ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev < curr); 153ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 154ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 155ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 156ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 157ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 158ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 159ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 160ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements, and that their values 161ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are as expected. 162ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 163ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); 164ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 165ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 166ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 167ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 168ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 169ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 170ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 171ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 172ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL) ); 173ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 174ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 175ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 176ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 177ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 178ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, vs[i]) ); 179ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 180ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 181ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements, and that 182ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // their values are as expected. 183ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 184ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv = VG_(OSetGen_Remove)(oset, vs[i]) ); 185ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( pv == vs[i] ); 186ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 187ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 188ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 189ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 190ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 191ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 192ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 193ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 194ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 195ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Free a few elements 196ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[0]); 197ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[1]); 198ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_FreeNode)(oset, vs[2]); 199ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 200ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert remaining elements, to give OSetGen_Destroy something to 201ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // work with. 202ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 3; i < NN; i++) { 203ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 204ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 205ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 206ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Print the list 207663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng OSet_Print(oset, descr, wordToStr); 208663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 209663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 210663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 211663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengvoid example1(void) 212663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 213663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng OSet *oset, *oset_empty_clone; 214663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 215663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // Create a static OSet of Ints. This one uses fast (built-in) 216663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // comparisons. 217663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 218663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // First a single oset, no pool allocator. 219663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng oset = VG_(OSetGen_Create)(0, 220663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng NULL, 221663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng allocate_node, "oset_test.1", free_node); 222663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng example1singleset(oset, "single oset, no pool allocator"); 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Destroy)(oset); 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 227663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // Then same, but with a group allocator 228663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng oset = VG_(OSetGen_Create_With_Pool)(0, 229663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng NULL, 230663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng allocate_node, "oset_test.1", 231663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng free_node, 232663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 101, sizeof(Word)); 233663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng example1singleset(oset, "single oset, pool allocator"); 234663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 235663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // Destroy the OSet 236663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(OSetGen_Destroy)(oset); 237663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 238663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 239663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // Then two sets, sharing a group allocator. 240663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng oset = VG_(OSetGen_Create_With_Pool) 241663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng (0, 242663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng NULL, 243663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng allocate_node, "oset_test.1", free_node, 244663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 101, sizeof(Word)); 245663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng oset_empty_clone = VG_(OSetGen_EmptyClone) (oset); 246663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng example1singleset(oset, "oset, shared pool"); 247663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng example1singleset(oset_empty_clone, "cloned oset, shared pool"); 248663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng // Destroy both OSet 249663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 250663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(OSetGen_Destroy)(oset_empty_clone); 251663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng VG_(OSetGen_Destroy)(oset); 252663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 253663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng} 254ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 255ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid example1b(void) 256ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 257ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 258ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word v = 0, prev; 259ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word vs[NN]; 260ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 261ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create a static OSet of Ints. This one uses fast (built-in) 262ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // comparisons. 263ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* oset = VG_(OSetWord_Create)(allocate_node, "oset_test.2", free_node); 264ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 265ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 266ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 267ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 268ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 269ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 270ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 271ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some elements, with gaps (they're all even) but no dups, 272ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // and shuffle them randomly. 273ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 274ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = 2*i; 275ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 276ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 277ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 278ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r1 = myrandom() % NN; 279ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word r2 = myrandom() % NN; 280ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word tmp = vs[r1]; 281ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 282ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 283ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 284ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 285ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 286ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 287ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Insert)(oset, vs[i]); 288ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 289ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 290ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 291ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetWord_Size)(oset) ); 292ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 293ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted 294ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 295ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 296ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 297ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 298ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below, within (odd 299ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // numbers), and above the inserted elements. 300ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = -1; 301ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 302ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 303ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = vs[i] + 1; 304ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 305ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 306ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown v = NN*2; 307ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, v) ); 308ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 309ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted. 310ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 311ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 312ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 313ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 314ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 315ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 316ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 317ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = -1; 318ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_ResetIter)(oset); 319ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( VG_(OSetWord_Next)(oset, &v) ) { 320ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word curr = v; 321ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev < curr); 322ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 323ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 324ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 325ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 326ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 327ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 328ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 329ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements. 330ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 331ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 332ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 333ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 334ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 335ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetWord_Size)(oset) ); 336ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 337ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 338ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 339ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 340ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 341ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 342ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 343ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 344ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetWord_Contains)(oset, vs[i]) ); 345ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 346ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 347ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements. 348ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 349ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 350ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 351ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 352ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 353ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 354ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 355ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetWord_Next)(oset, &v) ); 356ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 357ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 358ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert remaining elements, to give OSetWord_Destroy something to 359ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // work with. 360ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 3; i < NN; i++) { 361ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Insert)(oset, vs[i]); 362ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 363ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 364ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Print the list 365ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet_Print(oset, "oset1b", wordToStr); 366ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 367ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 368ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetWord_Destroy)(oset); 369ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 370ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 371ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 372ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 373ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// Struct example 374ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--------------------------------------------------------------------------- 375ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 376ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// This element shows that a key can be in the middle of the element, and 377ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// be of arbitrary size and even span multiple (contiguous) fields. It 378ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// also demonstrates how an OSet can be used to implement a list of 379ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// non-overlapping intervals. 380ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 381ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct { 382ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int b1; 383ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr first; 384ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr last; 385ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int b2; 386ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 387ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBlock; 388ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 389ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown__attribute__((unused)) 390ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Char *blockToStr(void *p) 391ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 392ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown static char buf[32]; 393ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* b = (Block*)p; 394ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown sprintf(buf, "<(%d) %lu..%lu (%d)>", b->b1, b->first, b->last, b->b2); 395ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return buf; 396ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 397ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 398ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic Word blockCmp(const void* vkey, const void* velem) 399ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 400ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr key = *(const Addr*)vkey; 401ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown const Block* elem = (const Block*)velem; 402ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 403ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(elem->first <= elem->last); 404ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (key < elem->first) return -1; 405ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown if (key > elem->last) return 1; 406ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 407ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 408ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 409ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid example2(void) 410ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 411ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int i, n; 412ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Addr a; 413ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* vs[NN]; 414ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block v, prev; 415ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block *pv; 416ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 417ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create a dynamic OSet of Blocks. This one uses slow (custom) 418ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // comparisons. 419ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first), 420ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown blockCmp, 421ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown allocate_node, "oset_test.3", free_node); 422ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 423ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some operations on an empty OSet to ensure they don't screw up. 424ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 425ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 426ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 427ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 428ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 429ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 430ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but 431ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // no dups, and shuffle them randomly. 432ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 433ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block)); 434ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->b1 = i; 435ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->first = i*10 + 1; 436ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->last = vs[i]->first + 2; 437ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[i]->b2 = i+1; 438ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 439ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown seed = 0; 440ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 441ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r1 = myrandom() % NN; 442ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Int r2 = myrandom() % NN; 443ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block* tmp = vs[r1]; 444ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r1] = vs[r2]; 445ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vs[r2] = tmp; 446ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 447ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 448ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Insert the elements 449ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 450ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 451ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 452ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 453ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 454ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN == VG_(OSetGen_Size)(oset) ); 455ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 456ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, within the full range 457ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // of each Block. 458ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 459ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) ); 460ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) ); 461ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) ); 462ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 463ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 464ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find elements we did not insert, below and above the 465ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // ranges of the inserted elements. 466ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = 0; 467ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( ! VG_(OSetGen_Contains)(oset, &a) ); 468ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 469ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 470ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 471ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 472ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 473ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find all the elements we inserted, and the right values 474ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are returned. 475ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 476ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 477ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 478ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 479ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) ); 480ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 481ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 482ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can iterate over the OSet elements in sorted order, and 483ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // there is the right number of them. 484ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n = 0; 485ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown pv = NULL; 486ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev.last = 0; 487ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_ResetIter)(oset); 488ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown while ( (pv = VG_(OSetGen_Next)(oset)) ) { 489ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Block curr = *pv; 490ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(prev.last < curr.first); 491ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown prev = curr; 492ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown n++; 493ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 494ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown assert(NN == n); 495ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 496ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 497ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 498ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove half of the elements, and that their values 499ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // are as expected. 500ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 501ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 502ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 503ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 504ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check the size 505ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 506ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 507ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we can find the remaining elements (with the right values). 508ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 509ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 510ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 511ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 512ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 513ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 514ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check we cannot find any of the elements we removed. 515ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i += 2) { 516ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 517ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 518ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 519ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 520ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 521ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Check that we can remove the remaining half of the elements, and that 522ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // their values are as expected. 523ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 1; i < NN; i += 2) { 524ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 525ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 526ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 527ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Try some more operations on the empty OSet to ensure they don't screw up. 528ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 529ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 530ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 531ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( ! VG_(OSetGen_Next)(oset) ); 532ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 533ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 534ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Re-insert all elements, to give OSetGen_Destroy something to work with. 535ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown for (i = 0; i < NN; i++) { 536ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Insert)(oset, vs[i]); 537ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown } 538ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 539ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown // Destroy the OSet 540ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown VG_(OSetGen_Destroy)(oset); 541ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 542ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 543ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//----------------------------------------------------------------------- 544ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown// main() 545ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//----------------------------------------------------------------------- 546ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 547ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownint main(void) 548ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 549ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example1(); 550ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example1b(); 551ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown example2(); 552ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return 0; 553ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 554