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