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