17b880bcceda3972a98d6dc7844df6743bd1a278anjn 27b880bcceda3972a98d6dc7844df6743bd1a278anjn#include <assert.h> 37b880bcceda3972a98d6dc7844df6743bd1a278anjn#include <stdio.h> 47b880bcceda3972a98d6dc7844df6743bd1a278anjn#include <stdlib.h> 57b880bcceda3972a98d6dc7844df6743bd1a278anjn#include <string.h> 67b880bcceda3972a98d6dc7844df6743bd1a278anjn 77b880bcceda3972a98d6dc7844df6743bd1a278anjn#include "pub_core_basics.h" 87b880bcceda3972a98d6dc7844df6743bd1a278anjn#include "pub_core_libcbase.h" 97b880bcceda3972a98d6dc7844df6743bd1a278anjn#include "pub_core_libcassert.h" 107b880bcceda3972a98d6dc7844df6743bd1a278anjn#include "pub_core_libcprint.h" 117b880bcceda3972a98d6dc7844df6743bd1a278anjn 127b880bcceda3972a98d6dc7844df6743bd1a278anjn// I need this to avoid some signedness warnings, not sure why 13b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// #define Char char 14b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// jrs 19 Aug 2005: m_oset.c relies on Char being a signed char. 15b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// It appears that plain 'char' on ppc32 is unsigned and so the 16b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// above #define screws up the AVL tree balancing logic and 17b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// leads to segfaults. Commenting it out and using the standard 18b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// definition of Char from pub_core_basics.h seems a good solution 19b1e123a126bda31fbbc3b74efbd4f39f6d67a1b2sewardj// as that has the same signedness on all platforms. 207b880bcceda3972a98d6dc7844df6743bd1a278anjn 217b880bcceda3972a98d6dc7844df6743bd1a278anjn// Crudely redirect various VG_(foo)() functions to their libc equivalents. 227b880bcceda3972a98d6dc7844df6743bd1a278anjn#undef vg_assert 237b880bcceda3972a98d6dc7844df6743bd1a278anjn#define vg_assert(e) assert(e) 247b880bcceda3972a98d6dc7844df6743bd1a278anjn#undef vg_assert2 257b880bcceda3972a98d6dc7844df6743bd1a278anjn#define vg_assert2(e, fmt, args...) assert(e) 267b880bcceda3972a98d6dc7844df6743bd1a278anjn 277b880bcceda3972a98d6dc7844df6743bd1a278anjn#define vgPlain_printf printf 287b880bcceda3972a98d6dc7844df6743bd1a278anjn#define vgPlain_memset memset 297b880bcceda3972a98d6dc7844df6743bd1a278anjn#define vgPlain_memcpy memcpy 30291849fb0285e0998b4c9e33eb153eb3373c4a88sewardj#define vgPlain_memmove memmove 31ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes#define vgPlain_strcmp strcmp 327b880bcceda3972a98d6dc7844df6743bd1a278anjn 336643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe// Crudely replace some functions (in m_xarray.c, but not needed for 346643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe// this unit test) by (hopefully) failing asserts. 356643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#define vgPlain_ssort(a,b,c,d) assert(a) 366643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#define vgPlain_vcbprintf(a,b,...) assert(a == b) 376643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#include "coregrind/m_xarray.c" 386643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#undef vgPlain_ssort 396643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#undef vgPlain_vcbprintf 406643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe#include "coregrind/m_poolalloc.c" 417b880bcceda3972a98d6dc7844df6743bd1a278anjn#include "coregrind/m_oset.c" 427b880bcceda3972a98d6dc7844df6743bd1a278anjn 437b880bcceda3972a98d6dc7844df6743bd1a278anjn#define NN 1000 // Size of OSets being created 447b880bcceda3972a98d6dc7844df6743bd1a278anjn 453d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 463d8dcf8fa06e96edd02025fbc785fde56658042dsewardj/* Consistent random number generator, so it produces the 473d8dcf8fa06e96edd02025fbc785fde56658042dsewardj same results on all platforms. */ 483d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 493d8dcf8fa06e96edd02025fbc785fde56658042dsewardj#define random error_do_not_use_libc_random 503d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 513d8dcf8fa06e96edd02025fbc785fde56658042dsewardjstatic UInt seed = 0; 523d8dcf8fa06e96edd02025fbc785fde56658042dsewardjstatic UInt myrandom( void ) 533d8dcf8fa06e96edd02025fbc785fde56658042dsewardj{ 543d8dcf8fa06e96edd02025fbc785fde56658042dsewardj seed = (1103515245 * seed + 12345); 553d8dcf8fa06e96edd02025fbc785fde56658042dsewardj return seed; 563d8dcf8fa06e96edd02025fbc785fde56658042dsewardj} 573d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 5854fe2021b87b9e5edb8ec8070f47b86d5cafb8aaflorianstatic void* allocate_node(const HChar* cc, SizeT szB) 59672a82dc61923ed27182779b532a968ef8920935bart{ return malloc(szB); } 60672a82dc61923ed27182779b532a968ef8920935bart 61672a82dc61923ed27182779b532a968ef8920935bartstatic void free_node(void* p) 62672a82dc61923ed27182779b532a968ef8920935bart{ return free(p); } 633d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 643d8dcf8fa06e96edd02025fbc785fde56658042dsewardj 657b880bcceda3972a98d6dc7844df6743bd1a278anjn//--------------------------------------------------------------------------- 66548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian// Word example 677b880bcceda3972a98d6dc7844df6743bd1a278anjn//--------------------------------------------------------------------------- 687b880bcceda3972a98d6dc7844df6743bd1a278anjn 696792df3d231866b25f59348733c77c636a66feddsewardj// This example shows that an element can be a single value (in this 706792df3d231866b25f59348733c77c636a66feddsewardj// case a Word), in which case the element is also the key. 717b880bcceda3972a98d6dc7844df6743bd1a278anjn 727b880bcceda3972a98d6dc7844df6743bd1a278anjn__attribute__((unused)) 73ee0d0e9cd0351721260f8b079495ed9d5ecf5fafflorianstatic const HChar *wordToStr(const void *p) 747b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 75548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian static HChar buf[32]; 766792df3d231866b25f59348733c77c636a66feddsewardj sprintf(buf, "%ld", *(Word*)p); 777b880bcceda3972a98d6dc7844df6743bd1a278anjn return buf; 787b880bcceda3972a98d6dc7844df6743bd1a278anjn} 797b880bcceda3972a98d6dc7844df6743bd1a278anjn 807b880bcceda3972a98d6dc7844df6743bd1a278anjn__attribute__((unused)) 816792df3d231866b25f59348733c77c636a66feddsewardjstatic Word wordCmp(void* vkey, void* velem) 827b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 836792df3d231866b25f59348733c77c636a66feddsewardj return *(Word*)vkey - *(Word*)velem; 847b880bcceda3972a98d6dc7844df6743bd1a278anjn} 857b880bcceda3972a98d6dc7844df6743bd1a278anjn 866643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid example1singleset(OSet* oset, char *descr) 877b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 886792df3d231866b25f59348733c77c636a66feddsewardj Int i, n; 89a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord v, prev; 90a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord* vs[NN]; 91a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord *pv; 92a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord sorted_elts[NN]; // Used to test VG_(OSetGen_ResetIterAt) 937b880bcceda3972a98d6dc7844df6743bd1a278anjn 947b880bcceda3972a98d6dc7844df6743bd1a278anjn // Try some operations on an empty OSet to ensure they don't screw up. 95e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 96e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 97e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 98e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 99e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 1007b880bcceda3972a98d6dc7844df6743bd1a278anjn 1017b880bcceda3972a98d6dc7844df6743bd1a278anjn // Create some elements, with gaps (they're all even) but no dups, 1027b880bcceda3972a98d6dc7844df6743bd1a278anjn // and shuffle them randomly. 1037b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 104e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Word)); 105a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe *(vs[i]) = 2*(i+1); 106a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe sorted_elts[i] = *(vs[i]); 1077b880bcceda3972a98d6dc7844df6743bd1a278anjn } 108e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn seed = 0; 1097b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 110a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord r1 = myrandom() % NN; 111a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord r2 = myrandom() % NN; 112a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord* tmp= vs[r1]; 1136792df3d231866b25f59348733c77c636a66feddsewardj vs[r1] = vs[r2]; 1146792df3d231866b25f59348733c77c636a66feddsewardj vs[r2] = tmp; 1157b880bcceda3972a98d6dc7844df6743bd1a278anjn } 1167b880bcceda3972a98d6dc7844df6743bd1a278anjn 1177b880bcceda3972a98d6dc7844df6743bd1a278anjn // Insert the elements 1187b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 119e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Insert)(oset, vs[i]); 1207b880bcceda3972a98d6dc7844df6743bd1a278anjn } 1217b880bcceda3972a98d6dc7844df6743bd1a278anjn 1227b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check the size 123e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN == VG_(OSetGen_Size)(oset) ); 1247b880bcceda3972a98d6dc7844df6743bd1a278anjn 1257b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find all the elements we inserted 1267b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 127e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetGen_Contains)(oset, vs[i]) ); 1287b880bcceda3972a98d6dc7844df6743bd1a278anjn } 1297b880bcceda3972a98d6dc7844df6743bd1a278anjn 130a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe#define FULLCHECKEVERY 20 131a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // Check VG_(OSetGen_ResetIterAt) works before, at, and after each element. 132a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // For some elements, we check all the successive elements. 133a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe for (i = 0; i < NN; i++) { 134a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord k; 135a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord *pval; 136a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe Int j; 137a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe 138a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // check ResetIterAt just before an elt gives this elt. 139a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe k = sorted_elts[i] - 1; 140a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe VG_(OSetGen_ResetIterAt) (oset, &k); 141a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // Check all elts till the end 142a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe for (j = i; j < NN; j++) { 143a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe pval = VG_(OSetGen_Next)(oset); 144a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert (*pval == sorted_elts[j]); 145a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe if (i % FULLCHECKEVERY != 0) break; 146a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } 147a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe 148a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // check ResetIterAt at an elt gives this elt. 149a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe k = sorted_elts[i]; 150a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe VG_(OSetGen_ResetIterAt) (oset, &k); 151a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // Check all elts till the end 152a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe for (j = i; j < NN; j++) { 153a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe pval = VG_(OSetGen_Next)(oset); 154a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert (*pval == sorted_elts[j]); 155a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe if (i % FULLCHECKEVERY != 0) break; 156a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } 157a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe 158a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // check ResetIterAt after an elt gives the next elt or nothing 159a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // when we reset after the last elt. 160a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe k = sorted_elts[i] + 1; 161a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe VG_(OSetGen_ResetIterAt) (oset, &k); 162a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe if (i < NN - 1) { 163a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe for (j = i+1; j < NN; j++) { 164a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe pval = VG_(OSetGen_Next)(oset); 165a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert (*pval == sorted_elts[j]); 166a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe if (i % FULLCHECKEVERY != 0) break; 167a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } 168a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } else { 169a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe pval = VG_(OSetGen_Next)(oset); 170a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert (pval == NULL); 171a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } 172a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe 173a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe } 174a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe 1757b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we cannot find elements we did not insert, below, within (odd 1767b880bcceda3972a98d6dc7844df6743bd1a278anjn // numbers), and above the inserted elements. 177a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe v = 0; 178e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetGen_Contains)(oset, &v) ); 1797b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 1807b880bcceda3972a98d6dc7844df6743bd1a278anjn v = *(vs[i]) + 1; 181e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetGen_Contains)(oset, &v) ); 1827b880bcceda3972a98d6dc7844df6743bd1a278anjn } 183a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe v = 2*(NN+1); 184e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetGen_Contains)(oset, &v) ); 1857b880bcceda3972a98d6dc7844df6743bd1a278anjn 1867b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find all the elements we inserted, and the right values 1877b880bcceda3972a98d6dc7844df6743bd1a278anjn // are returned. 1887b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 189e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( vs[i] == VG_(OSetGen_Lookup)(oset, vs[i]) ); 1907b880bcceda3972a98d6dc7844df6743bd1a278anjn } 1917b880bcceda3972a98d6dc7844df6743bd1a278anjn 1927b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can iterate over the OSet elements in sorted order, and 1937b880bcceda3972a98d6dc7844df6743bd1a278anjn // there is the right number of them. 1947b880bcceda3972a98d6dc7844df6743bd1a278anjn n = 0; 1957b880bcceda3972a98d6dc7844df6743bd1a278anjn pv = NULL; 196a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe prev = 0; 197e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_ResetIter)(oset); 198e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn while ( (pv = VG_(OSetGen_Next)(oset)) ) { 199a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord curr = *pv; 2007b880bcceda3972a98d6dc7844df6743bd1a278anjn assert(prev < curr); 2017b880bcceda3972a98d6dc7844df6743bd1a278anjn prev = curr; 2027b880bcceda3972a98d6dc7844df6743bd1a278anjn n++; 2037b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2047b880bcceda3972a98d6dc7844df6743bd1a278anjn assert(NN == n); 205e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 206e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 2077b880bcceda3972a98d6dc7844df6743bd1a278anjn 2087b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can remove half of the elements, and that their values 2097b880bcceda3972a98d6dc7844df6743bd1a278anjn // are as expected. 2107b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i += 2) { 211ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes pv = VG_(OSetGen_Remove)(oset, vs[i]); 212ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes assert( pv ); 2137b880bcceda3972a98d6dc7844df6743bd1a278anjn assert( pv == vs[i] ); 2147b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2157b880bcceda3972a98d6dc7844df6743bd1a278anjn 2167b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check the size 217e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 2187b880bcceda3972a98d6dc7844df6743bd1a278anjn 2197b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find the remaining elements (with the right values). 2207b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 1; i < NN; i += 2) { 221ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes pv = VG_(OSetGen_LookupWithCmp)(oset, vs[i], NULL); 222ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes assert( pv ); 2237b880bcceda3972a98d6dc7844df6743bd1a278anjn assert( pv == vs[i] ); 2247b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2257b880bcceda3972a98d6dc7844df6743bd1a278anjn 2267b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we cannot find any of the elements we removed. 2277b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i += 2) { 228e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetGen_Contains)(oset, vs[i]) ); 2297b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2307b880bcceda3972a98d6dc7844df6743bd1a278anjn 2317b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can remove the remaining half of the elements, and that 2327b880bcceda3972a98d6dc7844df6743bd1a278anjn // their values are as expected. 2337b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 1; i < NN; i += 2) { 234ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes pv = VG_(OSetGen_Remove)(oset, vs[i]); 235ed39800a83baf5bffbe391f3974eb2af0f415f80Elliott Hughes assert( pv ); 2367b880bcceda3972a98d6dc7844df6743bd1a278anjn assert( pv == vs[i] ); 2377b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2387b880bcceda3972a98d6dc7844df6743bd1a278anjn 2397b880bcceda3972a98d6dc7844df6743bd1a278anjn // Try some more operations on the empty OSet to ensure they don't screw up. 240e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 241e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 242e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 243e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 244e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 2457b880bcceda3972a98d6dc7844df6743bd1a278anjn 2467b880bcceda3972a98d6dc7844df6743bd1a278anjn // Free a few elements 247e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_FreeNode)(oset, vs[0]); 248e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_FreeNode)(oset, vs[1]); 249e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_FreeNode)(oset, vs[2]); 2507b880bcceda3972a98d6dc7844df6743bd1a278anjn 251e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Re-insert remaining elements, to give OSetGen_Destroy something to 252e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // work with. 2537b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 3; i < NN; i++) { 254e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Insert)(oset, vs[i]); 2557b880bcceda3972a98d6dc7844df6743bd1a278anjn } 2567b880bcceda3972a98d6dc7844df6743bd1a278anjn 2577b880bcceda3972a98d6dc7844df6743bd1a278anjn // Print the list 2586643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe OSet_Print(oset, descr, wordToStr); 2596643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2606643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 2616643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2626643e96a72e8530a7c8830c02ffb2fb4aee74c88philippevoid example1(void) 2636643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe{ 2646643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe OSet *oset, *oset_empty_clone; 2656643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 266a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // Create a static OSet of UWords. This one uses fast (built-in) 2676643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // comparisons. 2686643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2696643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // First a single oset, no pool allocator. 2706643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe oset = VG_(OSetGen_Create)(0, 2716643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe NULL, 2726643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe allocate_node, "oset_test.1", free_node); 2736643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe example1singleset(oset, "single oset, no pool allocator"); 2747b880bcceda3972a98d6dc7844df6743bd1a278anjn 2757b880bcceda3972a98d6dc7844df6743bd1a278anjn // Destroy the OSet 276e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Destroy)(oset); 277e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 2786643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // Then same, but with a group allocator 2796643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe oset = VG_(OSetGen_Create_With_Pool)(0, 2806643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe NULL, 2816643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe allocate_node, "oset_test.1", 2826643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe free_node, 283548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian 101, sizeof(Word)); 2846643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe example1singleset(oset, "single oset, pool allocator"); 2856643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2866643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // Destroy the OSet 2876643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(OSetGen_Destroy)(oset); 2886643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2896643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 2906643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // Then two sets, sharing a group allocator. 2916643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe oset = VG_(OSetGen_Create_With_Pool) 2926643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe (0, 2936643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe NULL, 2946643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe allocate_node, "oset_test.1", free_node, 295548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian 101, sizeof(Word)); 2966643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe oset_empty_clone = VG_(OSetGen_EmptyClone) (oset); 2976643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe example1singleset(oset, "oset, shared pool"); 2986643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe example1singleset(oset_empty_clone, "cloned oset, shared pool"); 2996643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe // Destroy both OSet 3006643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 3016643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(OSetGen_Destroy)(oset_empty_clone); 3026643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe VG_(OSetGen_Destroy)(oset); 3036643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe 3046643e96a72e8530a7c8830c02ffb2fb4aee74c88philippe} 305e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 306e2a9ad3b71e0eccca6115349192d5e844be4eb0anjnvoid example1b(void) 307e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn{ 308e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn Int i, n; 309a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord v = 0, prev; 310a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord vs[NN]; 311e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 312a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe // Create a static OSet of UWords. This one uses fast (built-in) 313e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // comparisons. 3149c606bd8634cd6b67bb41fa645b5c639668cfa2dsewardj OSet* oset = VG_(OSetWord_Create)(allocate_node, "oset_test.2", free_node); 315e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 316e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Try some operations on an empty OSet to ensure they don't screw up. 317e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 318e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 319548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian vg_assert( ! VG_(OSetWord_Next)(oset, (UWord *)&v) ); 320e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 321e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 322e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Create some elements, with gaps (they're all even) but no dups, 323e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // and shuffle them randomly. 324e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 325e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vs[i] = 2*i; 326e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 327e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn seed = 0; 328e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 329a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord r1 = myrandom() % NN; 330a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord r2 = myrandom() % NN; 331a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord tmp = vs[r1]; 332e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vs[r1] = vs[r2]; 333e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vs[r2] = tmp; 334e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 335e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 336e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Insert the elements 337e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 338e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetWord_Insert)(oset, vs[i]); 339e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 340e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 341e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check the size 342e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN == VG_(OSetWord_Size)(oset) ); 343e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 344e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check we can find all the elements we inserted 345e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 346e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 347e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 348e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 349e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check we cannot find elements we did not insert, below, within (odd 350e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // numbers), and above the inserted elements. 351a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe v = 0xffffffff; 352e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetWord_Contains)(oset, v) ); 353e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 354e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn v = vs[i] + 1; 355e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetWord_Contains)(oset, v) ); 356e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 357e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn v = NN*2; 358e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetWord_Contains)(oset, v) ); 359e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 360e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check we can find all the elements we inserted. 361e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i++) { 362e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 363e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 364e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 365e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check that we can iterate over the OSet elements in sorted order, and 366e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // there is the right number of them. 367e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn n = 0; 368a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe prev = 0; 369e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetWord_ResetIter)(oset); 370548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian while ( VG_(OSetWord_Next)(oset, (UWord *)&v) ) { 371a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe UWord curr = v; 372a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe if (n == 0) 373a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert(prev == curr); 374a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe else 375a388ee4c84b6c08eba5dbc9441587a492d74b8cfphilippe assert(prev < curr); 376e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn prev = curr; 377e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn n++; 378e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 379e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert(NN == n); 380548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian vg_assert( ! VG_(OSetWord_Next)(oset, (UWord *)&v) ); 381548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian vg_assert( ! VG_(OSetWord_Next)(oset, (UWord *)&v) ); 382e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 383e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check that we can remove half of the elements. 384e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i += 2) { 385e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 386e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 387e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 388e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check the size 389e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN/2 == VG_(OSetWord_Size)(oset) ); 390e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 391e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check we can find the remaining elements (with the right values). 392e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 1; i < NN; i += 2) { 393e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetWord_Contains)(oset, vs[i]) ); 394e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 395e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 396e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check we cannot find any of the elements we removed. 397e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 0; i < NN; i += 2) { 398e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetWord_Contains)(oset, vs[i]) ); 399e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 400e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 401e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Check that we can remove the remaining half of the elements. 402e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 1; i < NN; i += 2) { 403e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( VG_(OSetWord_Remove)(oset, vs[i]) ); 404e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 405e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 406e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Try some more operations on the empty OSet to ensure they don't screw up. 407e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetWord_Contains)(oset, v) ); 408e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetWord_Remove)(oset, v) ); 409548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian vg_assert( ! VG_(OSetWord_Next)(oset, (UWord *)&v) ); 410e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetWord_Size)(oset) ); 411e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 412e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Re-insert remaining elements, to give OSetWord_Destroy something to 413e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // work with. 414e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn for (i = 3; i < NN; i++) { 415e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetWord_Insert)(oset, vs[i]); 416e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn } 417e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 418e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Print the list 419e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn OSet_Print(oset, "oset1b", wordToStr); 420e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn 421e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Destroy the OSet 422e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetWord_Destroy)(oset); 4237b880bcceda3972a98d6dc7844df6743bd1a278anjn} 4247b880bcceda3972a98d6dc7844df6743bd1a278anjn 4257b880bcceda3972a98d6dc7844df6743bd1a278anjn 4267b880bcceda3972a98d6dc7844df6743bd1a278anjn//--------------------------------------------------------------------------- 4277b880bcceda3972a98d6dc7844df6743bd1a278anjn// Struct example 4287b880bcceda3972a98d6dc7844df6743bd1a278anjn//--------------------------------------------------------------------------- 4297b880bcceda3972a98d6dc7844df6743bd1a278anjn 4307b880bcceda3972a98d6dc7844df6743bd1a278anjn// This element shows that a key can be in the middle of the element, and 4317b880bcceda3972a98d6dc7844df6743bd1a278anjn// be of arbitrary size and even span multiple (contiguous) fields. It 4327b880bcceda3972a98d6dc7844df6743bd1a278anjn// also demonstrates how an OSet can be used to implement a list of 4337b880bcceda3972a98d6dc7844df6743bd1a278anjn// non-overlapping intervals. 4347b880bcceda3972a98d6dc7844df6743bd1a278anjn 4357b880bcceda3972a98d6dc7844df6743bd1a278anjntypedef struct { 4367b880bcceda3972a98d6dc7844df6743bd1a278anjn Int b1; 4377b880bcceda3972a98d6dc7844df6743bd1a278anjn Addr first; 4387b880bcceda3972a98d6dc7844df6743bd1a278anjn Addr last; 4397b880bcceda3972a98d6dc7844df6743bd1a278anjn Int b2; 4407b880bcceda3972a98d6dc7844df6743bd1a278anjn} 4417b880bcceda3972a98d6dc7844df6743bd1a278anjnBlock; 4427b880bcceda3972a98d6dc7844df6743bd1a278anjn 4437b880bcceda3972a98d6dc7844df6743bd1a278anjn__attribute__((unused)) 444548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florianstatic HChar *blockToStr(void *p) 4457b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 446548a3bc6fe6bae9c549ba078b9d1aaa5d5e441e6florian static HChar buf[32]; 4477b880bcceda3972a98d6dc7844df6743bd1a278anjn Block* b = (Block*)p; 4487b880bcceda3972a98d6dc7844df6743bd1a278anjn sprintf(buf, "<(%d) %lu..%lu (%d)>", b->b1, b->first, b->last, b->b2); 4497b880bcceda3972a98d6dc7844df6743bd1a278anjn return buf; 4507b880bcceda3972a98d6dc7844df6743bd1a278anjn} 4517b880bcceda3972a98d6dc7844df6743bd1a278anjn 4521d090eb80982fedfebc43ce00ce1dc75824eb6fetomstatic Word blockCmp(const void* vkey, const void* velem) 4537b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 4541d090eb80982fedfebc43ce00ce1dc75824eb6fetom Addr key = *(const Addr*)vkey; 4551d090eb80982fedfebc43ce00ce1dc75824eb6fetom const Block* elem = (const Block*)velem; 4567b880bcceda3972a98d6dc7844df6743bd1a278anjn 4577b880bcceda3972a98d6dc7844df6743bd1a278anjn assert(elem->first <= elem->last); 4587b880bcceda3972a98d6dc7844df6743bd1a278anjn if (key < elem->first) return -1; 4597b880bcceda3972a98d6dc7844df6743bd1a278anjn if (key > elem->last) return 1; 4607b880bcceda3972a98d6dc7844df6743bd1a278anjn return 0; 4617b880bcceda3972a98d6dc7844df6743bd1a278anjn} 4627b880bcceda3972a98d6dc7844df6743bd1a278anjn 4637b880bcceda3972a98d6dc7844df6743bd1a278anjnvoid example2(void) 4647b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 4657b880bcceda3972a98d6dc7844df6743bd1a278anjn Int i, n; 4667b880bcceda3972a98d6dc7844df6743bd1a278anjn Addr a; 4677b880bcceda3972a98d6dc7844df6743bd1a278anjn Block* vs[NN]; 4687b880bcceda3972a98d6dc7844df6743bd1a278anjn Block v, prev; 4697b880bcceda3972a98d6dc7844df6743bd1a278anjn Block *pv; 4707b880bcceda3972a98d6dc7844df6743bd1a278anjn 4717b880bcceda3972a98d6dc7844df6743bd1a278anjn // Create a dynamic OSet of Blocks. This one uses slow (custom) 4727b880bcceda3972a98d6dc7844df6743bd1a278anjn // comparisons. 473e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn OSet* oset = VG_(OSetGen_Create)(offsetof(Block, first), 474b8b79addf04dd5d0b558916e26df0b1927cbd758sewardj blockCmp, 4759c606bd8634cd6b67bb41fa645b5c639668cfa2dsewardj allocate_node, "oset_test.3", free_node); 4767b880bcceda3972a98d6dc7844df6743bd1a278anjn 4777b880bcceda3972a98d6dc7844df6743bd1a278anjn // Try some operations on an empty OSet to ensure they don't screw up. 478e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 479e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 480e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 481e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 482e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 4837b880bcceda3972a98d6dc7844df6743bd1a278anjn 4847b880bcceda3972a98d6dc7844df6743bd1a278anjn // Create some inputs, with gaps -- intervals are 1..3, 11..13, ... -- but 4857b880bcceda3972a98d6dc7844df6743bd1a278anjn // no dups, and shuffle them randomly. 4867b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 487e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vs[i] = VG_(OSetGen_AllocNode)(oset, sizeof(Block)); 4887b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[i]->b1 = i; 4897b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[i]->first = i*10 + 1; 4907b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[i]->last = vs[i]->first + 2; 4917b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[i]->b2 = i+1; 4927b880bcceda3972a98d6dc7844df6743bd1a278anjn } 493e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn seed = 0; 4947b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 4953d8dcf8fa06e96edd02025fbc785fde56658042dsewardj Int r1 = myrandom() % NN; 4963d8dcf8fa06e96edd02025fbc785fde56658042dsewardj Int r2 = myrandom() % NN; 4977b880bcceda3972a98d6dc7844df6743bd1a278anjn Block* tmp = vs[r1]; 4987b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[r1] = vs[r2]; 4997b880bcceda3972a98d6dc7844df6743bd1a278anjn vs[r2] = tmp; 5007b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5017b880bcceda3972a98d6dc7844df6743bd1a278anjn 5027b880bcceda3972a98d6dc7844df6743bd1a278anjn // Insert the elements 5037b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 504e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Insert)(oset, vs[i]); 5057b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5067b880bcceda3972a98d6dc7844df6743bd1a278anjn 5077b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check the size 508e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN == VG_(OSetGen_Size)(oset) ); 5097b880bcceda3972a98d6dc7844df6743bd1a278anjn 5107b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find all the elements we inserted, within the full range 5117b880bcceda3972a98d6dc7844df6743bd1a278anjn // of each Block. 5127b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 513e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 0; assert( VG_(OSetGen_Contains)(oset, &a) ); 514e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 1; assert( VG_(OSetGen_Contains)(oset, &a) ); 515e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 2; assert( VG_(OSetGen_Contains)(oset, &a) ); 5167b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5177b880bcceda3972a98d6dc7844df6743bd1a278anjn 5187b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we cannot find elements we did not insert, below and above the 5197b880bcceda3972a98d6dc7844df6743bd1a278anjn // ranges of the inserted elements. 5207b880bcceda3972a98d6dc7844df6743bd1a278anjn a = 0; 521e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( ! VG_(OSetGen_Contains)(oset, &a) ); 5227b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 523e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first - 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 524e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 3; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 5257b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5267b880bcceda3972a98d6dc7844df6743bd1a278anjn 5277b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find all the elements we inserted, and the right values 5287b880bcceda3972a98d6dc7844df6743bd1a278anjn // are returned. 5297b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 530e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 531e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 532e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 533e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn assert( vs[i] == VG_(OSetGen_LookupWithCmp)(oset, &a, blockCmp) ); 5347b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5357b880bcceda3972a98d6dc7844df6743bd1a278anjn 5367b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can iterate over the OSet elements in sorted order, and 5377b880bcceda3972a98d6dc7844df6743bd1a278anjn // there is the right number of them. 5387b880bcceda3972a98d6dc7844df6743bd1a278anjn n = 0; 5397b880bcceda3972a98d6dc7844df6743bd1a278anjn pv = NULL; 5407b880bcceda3972a98d6dc7844df6743bd1a278anjn prev.last = 0; 541e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_ResetIter)(oset); 542e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn while ( (pv = VG_(OSetGen_Next)(oset)) ) { 5437b880bcceda3972a98d6dc7844df6743bd1a278anjn Block curr = *pv; 5447b880bcceda3972a98d6dc7844df6743bd1a278anjn assert(prev.last < curr.first); 5457b880bcceda3972a98d6dc7844df6743bd1a278anjn prev = curr; 5467b880bcceda3972a98d6dc7844df6743bd1a278anjn n++; 5477b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5487b880bcceda3972a98d6dc7844df6743bd1a278anjn assert(NN == n); 549e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 550e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 5517b880bcceda3972a98d6dc7844df6743bd1a278anjn 5527b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can remove half of the elements, and that their values 5537b880bcceda3972a98d6dc7844df6743bd1a278anjn // are as expected. 5547b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i += 2) { 555e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 5567b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5577b880bcceda3972a98d6dc7844df6743bd1a278anjn 5587b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check the size 559e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( NN/2 == VG_(OSetGen_Size)(oset) ); 5607b880bcceda3972a98d6dc7844df6743bd1a278anjn 5617b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we can find the remaining elements (with the right values). 5627b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 1; i < NN; i += 2) { 563e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 0; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 564e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 1; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 565e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 2; assert( vs[i] == VG_(OSetGen_Lookup)(oset, &a) ); 5667b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5677b880bcceda3972a98d6dc7844df6743bd1a278anjn 5687b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check we cannot find any of the elements we removed. 5697b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i += 2) { 570e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 0; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 571e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 1; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 572e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first + 2; assert( ! VG_(OSetGen_Contains)(oset, &a) ); 5737b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5747b880bcceda3972a98d6dc7844df6743bd1a278anjn 5757b880bcceda3972a98d6dc7844df6743bd1a278anjn // Check that we can remove the remaining half of the elements, and that 5767b880bcceda3972a98d6dc7844df6743bd1a278anjn // their values are as expected. 5777b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 1; i < NN; i += 2) { 578e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn a = vs[i]->first; assert( vs[i] == VG_(OSetGen_Remove)(oset, &a) ); 5797b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5807b880bcceda3972a98d6dc7844df6743bd1a278anjn 5817b880bcceda3972a98d6dc7844df6743bd1a278anjn // Try some more operations on the empty OSet to ensure they don't screw up. 582e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Contains)(oset, &v) ); 583e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Lookup)(oset, &v) ); 584e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Remove)(oset, &v) ); 585e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( ! VG_(OSetGen_Next)(oset) ); 586e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn vg_assert( 0 == VG_(OSetGen_Size)(oset) ); 5877b880bcceda3972a98d6dc7844df6743bd1a278anjn 588e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn // Re-insert all elements, to give OSetGen_Destroy something to work with. 5897b880bcceda3972a98d6dc7844df6743bd1a278anjn for (i = 0; i < NN; i++) { 590e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Insert)(oset, vs[i]); 5917b880bcceda3972a98d6dc7844df6743bd1a278anjn } 5927b880bcceda3972a98d6dc7844df6743bd1a278anjn 5937b880bcceda3972a98d6dc7844df6743bd1a278anjn // Destroy the OSet 594e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn VG_(OSetGen_Destroy)(oset); 5957b880bcceda3972a98d6dc7844df6743bd1a278anjn} 5967b880bcceda3972a98d6dc7844df6743bd1a278anjn 5977b880bcceda3972a98d6dc7844df6743bd1a278anjn//----------------------------------------------------------------------- 5987b880bcceda3972a98d6dc7844df6743bd1a278anjn// main() 5997b880bcceda3972a98d6dc7844df6743bd1a278anjn//----------------------------------------------------------------------- 6007b880bcceda3972a98d6dc7844df6743bd1a278anjn 6017b880bcceda3972a98d6dc7844df6743bd1a278anjnint main(void) 6027b880bcceda3972a98d6dc7844df6743bd1a278anjn{ 6037b880bcceda3972a98d6dc7844df6743bd1a278anjn example1(); 604e2a9ad3b71e0eccca6115349192d5e844be4eb0anjn example1b(); 6057b880bcceda3972a98d6dc7844df6743bd1a278anjn example2(); 6067b880bcceda3972a98d6dc7844df6743bd1a278anjn return 0; 6077b880bcceda3972a98d6dc7844df6743bd1a278anjn} 608