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