• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
50 static UInt seed = 0;
myrandom(void)51 static UInt myrandom( void )
52 {
53   seed = (1103515245 * seed + 12345);
54   return seed;
55 }
56 
allocate_node(const HChar * cc,SizeT szB)57 static void* allocate_node(const HChar* cc, SizeT szB)
58 { return malloc(szB); }
59 
free_node(void * p)60 static 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))
wordToStr(const void * p)72 static 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))
wordCmp(void * vkey,void * velem)80 static Word wordCmp(void* vkey, void* velem)
81 {
82    return *(Word*)vkey - *(Word*)velem;
83 }
84 
example1singleset(OSet * oset,char * descr)85 void 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 
example1(void)258 void 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 
example1b(void)302 void 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 
431 typedef struct {
432    Int   b1;
433    Addr  first;
434    Addr  last;
435    Int   b2;
436 }
437 Block;
438 
439 __attribute__((unused))
blockToStr(void * p)440 static 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 
blockCmp(const void * vkey,const void * velem)448 static 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 
example2(void)459 void 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 
main(void)597 int main(void)
598 {
599    example1();
600    example1b();
601    example2();
602    return 0;
603 }
604