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