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