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