1 2 /*--------------------------------------------------------------------*/ 3 /*--- Sets of words, with unique set identifiers. ---*/ 4 /*--- hg_wordset.c ---*/ 5 /*--------------------------------------------------------------------*/ 6 7 /* 8 This file is part of Helgrind, a Valgrind tool for detecting errors 9 in threaded programs. 10 11 Copyright (C) 2007-2012 OpenWorks LLP 12 info (at) open-works.co.uk 13 14 This program is free software; you can redistribute it and/or 15 modify it under the terms of the GNU General Public License as 16 published by the Free Software Foundation; either version 2 of the 17 License, or (at your option) any later version. 18 19 This program is distributed in the hope that it will be useful, but 20 WITHOUT ANY WARRANTY; without even the implied warranty of 21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 22 General Public License for more details. 23 24 You should have received a copy of the GNU General Public License 25 along with this program; if not, write to the Free Software 26 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 27 02111-1307, USA. 28 29 The GNU General Public License is contained in the file COPYING. 30 31 Neither the names of the U.S. Department of Energy nor the 32 University of California nor the names of its contributors may be 33 used to endorse or promote products derived from this software 34 without prior written permission. 35 */ 36 37 #include "pub_tool_basics.h" 38 #include "pub_tool_libcassert.h" 39 #include "pub_tool_libcbase.h" 40 #include "pub_tool_libcprint.h" 41 #include "pub_tool_threadstate.h" 42 #include "pub_tool_wordfm.h" 43 44 #include "hg_basics.h" 45 #include "hg_wordset.h" /* self */ 46 47 // define to 1 to have (a lot of) debugging of add/re-use/die WSU entries. 48 #define HG_DEBUG 0 49 50 //------------------------------------------------------------------// 51 //--- Word Cache ---// 52 //------------------------------------------------------------------// 53 54 typedef 55 struct { UWord arg1; UWord arg2; UWord res; } 56 WCacheEnt; 57 58 /* Each cache is a fixed sized array of N_WCACHE_STAT_MAX entries. 59 However only the first .dynMax are used. This is because at some 60 point, expanding the cache further overall gives a slowdown because 61 searching more entries more than negates any performance advantage 62 from caching those entries in the first place. Hence use .dynMax 63 to allow the size of the cache(s) to be set differently for each 64 different WordSetU. */ 65 #define N_WCACHE_STAT_MAX 32 66 typedef 67 struct { 68 WCacheEnt ent[N_WCACHE_STAT_MAX]; 69 UWord dynMax; /* 1 .. N_WCACHE_STAT_MAX inclusive */ 70 UWord inUse; /* 0 .. dynMax inclusive */ 71 } 72 WCache; 73 74 #define WCache_INIT(_zzcache,_zzdynmax) \ 75 do { \ 76 tl_assert((_zzdynmax) >= 1); \ 77 tl_assert((_zzdynmax) <= N_WCACHE_STAT_MAX); \ 78 (_zzcache).dynMax = (_zzdynmax); \ 79 (_zzcache).inUse = 0; \ 80 } while (0) 81 82 #define WCache_LOOKUP_AND_RETURN(_retty,_zzcache,_zzarg1,_zzarg2) \ 83 do { \ 84 UWord _i; \ 85 UWord _arg1 = (UWord)(_zzarg1); \ 86 UWord _arg2 = (UWord)(_zzarg2); \ 87 WCache* _cache = &(_zzcache); \ 88 tl_assert(_cache->dynMax >= 1); \ 89 tl_assert(_cache->dynMax <= N_WCACHE_STAT_MAX); \ 90 tl_assert(_cache->inUse >= 0); \ 91 tl_assert(_cache->inUse <= _cache->dynMax); \ 92 if (_cache->inUse > 0) { \ 93 if (_cache->ent[0].arg1 == _arg1 \ 94 && _cache->ent[0].arg2 == _arg2) \ 95 return (_retty)_cache->ent[0].res; \ 96 for (_i = 1; _i < _cache->inUse; _i++) { \ 97 if (_cache->ent[_i].arg1 == _arg1 \ 98 && _cache->ent[_i].arg2 == _arg2) { \ 99 WCacheEnt tmp = _cache->ent[_i-1]; \ 100 _cache->ent[_i-1] = _cache->ent[_i]; \ 101 _cache->ent[_i] = tmp; \ 102 return (_retty)_cache->ent[_i-1].res; \ 103 } \ 104 } \ 105 } \ 106 } while (0) 107 108 #define WCache_UPDATE(_zzcache,_zzarg1,_zzarg2,_zzresult) \ 109 do { \ 110 Word _i; \ 111 UWord _arg1 = (UWord)(_zzarg1); \ 112 UWord _arg2 = (UWord)(_zzarg2); \ 113 UWord _res = (UWord)(_zzresult); \ 114 WCache* _cache = &(_zzcache); \ 115 tl_assert(_cache->dynMax >= 1); \ 116 tl_assert(_cache->dynMax <= N_WCACHE_STAT_MAX); \ 117 tl_assert(_cache->inUse >= 0); \ 118 tl_assert(_cache->inUse <= _cache->dynMax); \ 119 if (_cache->inUse < _cache->dynMax) \ 120 _cache->inUse++; \ 121 for (_i = _cache->inUse-1; _i >= 1; _i--) \ 122 _cache->ent[_i] = _cache->ent[_i-1]; \ 123 _cache->ent[0].arg1 = _arg1; \ 124 _cache->ent[0].arg2 = _arg2; \ 125 _cache->ent[0].res = _res; \ 126 } while (0) 127 128 129 //------------------------------------------------------------------// 130 //--- WordSet ---// 131 //--- Implementation ---// 132 //------------------------------------------------------------------// 133 134 typedef 135 struct { 136 WordSetU* owner; /* for sanity checking */ 137 UWord* words; 138 UWord size; /* Really this should be SizeT */ 139 } 140 WordVec; 141 142 /* ix2vec[0 .. ix2vec_used-1] are pointers to the lock sets (WordVecs) 143 really. vec2ix is the inverse mapping, mapping WordVec* to the 144 corresponding ix2vec entry number. The two mappings are mutually 145 redundant. 146 147 If a WordVec WV is marked as dead by HG(dieWS), WV is removed from 148 vec2ix. The entry of the dead WVs in ix2vec are used to maintain a 149 linked list of free (to be re-used) ix2vec entries. */ 150 struct _WordSetU { 151 void* (*alloc)(HChar*,SizeT); 152 HChar* cc; 153 void (*dealloc)(void*); 154 WordFM* vec2ix; /* WordVec-to-WordSet mapping tree */ 155 WordVec** ix2vec; /* WordSet-to-WordVec mapping array */ 156 UWord ix2vec_size; 157 UWord ix2vec_used; 158 WordVec** ix2vec_free; 159 WordSet empty; /* cached, for speed */ 160 /* Caches for some operations */ 161 WCache cache_addTo; 162 WCache cache_delFrom; 163 WCache cache_intersect; 164 WCache cache_minus; 165 /* Stats */ 166 UWord n_add; 167 UWord n_add_uncached; 168 UWord n_del; 169 UWord n_del_uncached; 170 UWord n_die; 171 UWord n_union; 172 UWord n_intersect; 173 UWord n_intersect_uncached; 174 UWord n_minus; 175 UWord n_minus_uncached; 176 UWord n_elem; 177 UWord n_doubleton; 178 UWord n_isEmpty; 179 UWord n_isSingleton; 180 UWord n_anyElementOf; 181 UWord n_isSubsetOf; 182 }; 183 184 /* Create a new WordVec of the given size. */ 185 186 static WordVec* new_WV_of_size ( WordSetU* wsu, UWord sz ) 187 { 188 WordVec* wv; 189 tl_assert(sz >= 0); 190 wv = wsu->alloc( wsu->cc, sizeof(WordVec) ); 191 wv->owner = wsu; 192 wv->words = NULL; 193 wv->size = sz; 194 if (sz > 0) { 195 wv->words = wsu->alloc( wsu->cc, (SizeT)sz * sizeof(UWord) ); 196 } 197 return wv; 198 } 199 200 static void delete_WV ( WordVec* wv ) 201 { 202 void (*dealloc)(void*) = wv->owner->dealloc; 203 if (wv->words) { 204 dealloc(wv->words); 205 } 206 dealloc(wv); 207 } 208 static void delete_WV_for_FM ( UWord wv ) { 209 delete_WV( (WordVec*)wv ); 210 } 211 212 static Word cmp_WordVecs_for_FM ( UWord wv1W, UWord wv2W ) 213 { 214 UWord i; 215 WordVec* wv1 = (WordVec*)wv1W; 216 WordVec* wv2 = (WordVec*)wv2W; 217 218 // WordVecs with smaller size are smaller. 219 if (wv1->size < wv2->size) { 220 return -1; 221 } 222 if (wv1->size > wv2->size) { 223 return 1; 224 } 225 226 // Sizes are equal => order based on content. 227 for (i = 0; i < wv1->size; i++) { 228 if (wv1->words[i] == wv2->words[i]) 229 continue; 230 if (wv1->words[i] < wv2->words[i]) 231 return -1; 232 if (wv1->words[i] > wv2->words[i]) 233 return 1; 234 tl_assert(0); 235 } 236 return 0; /* identical */ 237 } 238 239 static void ensure_ix2vec_space ( WordSetU* wsu ) 240 { 241 UInt i, new_sz; 242 WordVec** new_vec; 243 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size); 244 if (wsu->ix2vec_used < wsu->ix2vec_size) 245 return; 246 new_sz = 2 * wsu->ix2vec_size; 247 if (new_sz == 0) new_sz = 1; 248 new_vec = wsu->alloc( wsu->cc, new_sz * sizeof(WordVec*) ); 249 tl_assert(new_vec); 250 for (i = 0; i < wsu->ix2vec_size; i++) 251 new_vec[i] = wsu->ix2vec[i]; 252 if (wsu->ix2vec) 253 wsu->dealloc(wsu->ix2vec); 254 wsu->ix2vec = new_vec; 255 wsu->ix2vec_size = new_sz; 256 } 257 258 /* True if wv is a dead entry (i.e. is in the linked list of free to be re-used 259 entries in ix2vec). */ 260 static inline Bool is_dead ( WordSetU* wsu, WordVec* wv ) 261 { 262 if (wv == NULL) /* last element in free linked list in ix2vec */ 263 return True; 264 else 265 return (WordVec**)wv >= &(wsu->ix2vec[1]) 266 && (WordVec**)wv < &(wsu->ix2vec[wsu->ix2vec_size]); 267 } 268 /* Index into a WordSetU, doing the obvious range check. Failure of 269 the assertions marked XXX and YYY is an indication of passing the 270 wrong WordSetU* in the public API of this module. 271 Accessing a dead ws will assert. */ 272 static WordVec* do_ix2vec ( WordSetU* wsu, WordSet ws ) 273 { 274 WordVec* wv; 275 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size); 276 if (wsu->ix2vec_used > 0) 277 tl_assert(wsu->ix2vec); 278 /* If this assertion fails, it may mean you supplied a 'ws' 279 that does not come from the 'wsu' universe. */ 280 tl_assert(ws < wsu->ix2vec_used); /* XXX */ 281 wv = wsu->ix2vec[ws]; 282 /* Make absolutely sure that 'ws' is a non dead member of 'wsu'. */ 283 tl_assert(wv); 284 tl_assert(!is_dead(wsu,wv)); 285 tl_assert(wv->owner == wsu); /* YYY */ 286 return wv; 287 } 288 289 /* Same as do_ix2vec but returns NULL for a dead ws. */ 290 static WordVec* do_ix2vec_with_dead ( WordSetU* wsu, WordSet ws ) 291 { 292 WordVec* wv; 293 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size); 294 if (wsu->ix2vec_used > 0) 295 tl_assert(wsu->ix2vec); 296 /* If this assertion fails, it may mean you supplied a 'ws' 297 that does not come from the 'wsu' universe. */ 298 tl_assert(ws < wsu->ix2vec_used); /* XXX */ 299 wv = wsu->ix2vec[ws]; 300 /* Make absolutely sure that 'ws' is either dead or a member of 'wsu'. */ 301 if (is_dead(wsu,wv)) 302 wv = NULL; 303 else 304 tl_assert(wv->owner == wsu); /* YYY */ 305 return wv; 306 } 307 308 /* See if wv is contained within wsu. If so, deallocate wv and return 309 the index of the already-present copy. If not, add wv to both the 310 vec2ix and ix2vec mappings and return its index. 311 */ 312 static WordSet add_or_dealloc_WordVec( WordSetU* wsu, WordVec* wv_new ) 313 { 314 Bool have; 315 WordVec* wv_old; 316 UWord/*Set*/ ix_old = -1; 317 /* Really WordSet, but need something that can safely be casted to 318 a Word* in the lookupFM. Making it WordSet (which is 32 bits) 319 causes failures on a 64-bit platform. */ 320 tl_assert(wv_new->owner == wsu); 321 have = VG_(lookupFM)( wsu->vec2ix, 322 (Word*)&wv_old, (Word*)&ix_old, 323 (Word)wv_new ); 324 if (have) { 325 tl_assert(wv_old != wv_new); 326 tl_assert(wv_old); 327 tl_assert(wv_old->owner == wsu); 328 tl_assert(ix_old < wsu->ix2vec_used); 329 tl_assert(wsu->ix2vec[ix_old] == wv_old); 330 delete_WV( wv_new ); 331 return (WordSet)ix_old; 332 } else if (wsu->ix2vec_free) { 333 WordSet ws; 334 tl_assert(is_dead(wsu,(WordVec*)wsu->ix2vec_free)); 335 ws = wsu->ix2vec_free - &(wsu->ix2vec[0]); 336 tl_assert(wsu->ix2vec[ws] == NULL || is_dead(wsu,wsu->ix2vec[ws])); 337 wsu->ix2vec_free = (WordVec **) wsu->ix2vec[ws]; 338 wsu->ix2vec[ws] = wv_new; 339 VG_(addToFM)( wsu->vec2ix, (Word)wv_new, ws ); 340 if (HG_DEBUG) VG_(printf)("aodW %s re-use free %d %p\n", wsu->cc, (Int)ws, wv_new ); 341 return ws; 342 } else { 343 ensure_ix2vec_space( wsu ); 344 tl_assert(wsu->ix2vec); 345 tl_assert(wsu->ix2vec_used < wsu->ix2vec_size); 346 wsu->ix2vec[wsu->ix2vec_used] = wv_new; 347 VG_(addToFM)( wsu->vec2ix, (Word)wv_new, (Word)wsu->ix2vec_used ); 348 if (HG_DEBUG) VG_(printf)("aodW %s %d %p\n", wsu->cc, (Int)wsu->ix2vec_used, wv_new ); 349 wsu->ix2vec_used++; 350 tl_assert(wsu->ix2vec_used <= wsu->ix2vec_size); 351 return (WordSet)(wsu->ix2vec_used - 1); 352 } 353 } 354 355 356 WordSetU* HG_(newWordSetU) ( void* (*alloc_nofail)( HChar*, SizeT ), 357 HChar* cc, 358 void (*dealloc)(void*), 359 Word cacheSize ) 360 { 361 WordSetU* wsu; 362 WordVec* empty; 363 364 wsu = alloc_nofail( cc, sizeof(WordSetU) ); 365 VG_(memset)( wsu, 0, sizeof(WordSetU) ); 366 wsu->alloc = alloc_nofail; 367 wsu->cc = cc; 368 wsu->dealloc = dealloc; 369 wsu->vec2ix = VG_(newFM)( alloc_nofail, cc, 370 dealloc, cmp_WordVecs_for_FM ); 371 wsu->ix2vec_used = 0; 372 wsu->ix2vec_size = 0; 373 wsu->ix2vec = NULL; 374 wsu->ix2vec_free = NULL; 375 WCache_INIT(wsu->cache_addTo, cacheSize); 376 WCache_INIT(wsu->cache_delFrom, cacheSize); 377 WCache_INIT(wsu->cache_intersect, cacheSize); 378 WCache_INIT(wsu->cache_minus, cacheSize); 379 empty = new_WV_of_size( wsu, 0 ); 380 wsu->empty = add_or_dealloc_WordVec( wsu, empty ); 381 382 return wsu; 383 } 384 385 void HG_(deleteWordSetU) ( WordSetU* wsu ) 386 { 387 void (*dealloc)(void*) = wsu->dealloc; 388 tl_assert(wsu->vec2ix); 389 VG_(deleteFM)( wsu->vec2ix, delete_WV_for_FM, NULL/*val-finalizer*/ ); 390 if (wsu->ix2vec) 391 dealloc(wsu->ix2vec); 392 dealloc(wsu); 393 } 394 395 WordSet HG_(emptyWS) ( WordSetU* wsu ) 396 { 397 return wsu->empty; 398 } 399 400 Bool HG_(isEmptyWS) ( WordSetU* wsu, WordSet ws ) 401 { 402 WordVec* wv = do_ix2vec( wsu, ws ); 403 wsu->n_isEmpty++; 404 if (wv->size == 0) { 405 tl_assert(ws == wsu->empty); 406 return True; 407 } else { 408 tl_assert(ws != wsu->empty); 409 return False; 410 } 411 } 412 413 Bool HG_(isSingletonWS) ( WordSetU* wsu, WordSet ws, UWord w ) 414 { 415 WordVec* wv; 416 tl_assert(wsu); 417 wsu->n_isSingleton++; 418 wv = do_ix2vec( wsu, ws ); 419 return (Bool)(wv->size == 1 && wv->words[0] == w); 420 } 421 422 UWord HG_(cardinalityWS) ( WordSetU* wsu, WordSet ws ) 423 { 424 WordVec* wv; 425 tl_assert(wsu); 426 wv = do_ix2vec( wsu, ws ); 427 tl_assert(wv->size >= 0); 428 return wv->size; 429 } 430 431 UWord HG_(anyElementOfWS) ( WordSetU* wsu, WordSet ws ) 432 { 433 WordVec* wv; 434 tl_assert(wsu); 435 wsu->n_anyElementOf++; 436 wv = do_ix2vec( wsu, ws ); 437 tl_assert(wv->size >= 1); 438 return wv->words[0]; 439 } 440 441 UWord HG_(cardinalityWSU) ( WordSetU* wsu ) 442 { 443 tl_assert(wsu); 444 return wsu->ix2vec_used; 445 } 446 447 void HG_(getPayloadWS) ( /*OUT*/UWord** words, /*OUT*/UWord* nWords, 448 WordSetU* wsu, WordSet ws ) 449 { 450 WordVec* wv; 451 if (HG_DEBUG) VG_(printf)("getPayloadWS %s %d\n", wsu->cc, (Int)ws); 452 tl_assert(wsu); 453 wv = do_ix2vec( wsu, ws ); 454 tl_assert(wv->size >= 0); 455 *nWords = wv->size; 456 *words = wv->words; 457 } 458 459 void HG_(dieWS) ( WordSetU* wsu, WordSet ws ) 460 { 461 WordVec* wv = do_ix2vec_with_dead( wsu, ws ); 462 WordVec* wv_in_vec2ix; 463 UWord/*Set*/ wv_ix = -1; 464 465 if (HG_DEBUG) VG_(printf)("dieWS %s %d %p\n", wsu->cc, (Int)ws, wv); 466 467 if (ws == 0) 468 return; // we never die the empty set. 469 470 if (!wv) 471 return; // already dead. (or a bug ?). 472 473 wsu->n_die++; 474 475 476 wsu->ix2vec[ws] = (WordVec*) wsu->ix2vec_free; 477 wsu->ix2vec_free = &wsu->ix2vec[ws]; 478 479 VG_(delFromFM) ( wsu->vec2ix, 480 (Word*)&wv_in_vec2ix, (Word*)&wv_ix, 481 (Word)wv ); 482 483 if (HG_DEBUG) VG_(printf)("dieWS wv_ix %d\n", (Int)wv_ix); 484 tl_assert (wv_ix); 485 tl_assert (wv_ix == ws); 486 487 delete_WV( wv ); 488 489 wsu->cache_addTo.inUse = 0; 490 wsu->cache_delFrom.inUse = 0; 491 wsu->cache_intersect.inUse = 0; 492 wsu->cache_minus.inUse = 0; 493 } 494 495 Bool HG_(plausibleWS) ( WordSetU* wsu, WordSet ws ) 496 { 497 if (wsu == NULL) return False; 498 if (ws < 0 || ws >= wsu->ix2vec_used) 499 return False; 500 return True; 501 } 502 503 Bool HG_(saneWS_SLOW) ( WordSetU* wsu, WordSet ws ) 504 { 505 WordVec* wv; 506 UWord i; 507 if (wsu == NULL) return False; 508 if (ws < 0 || ws >= wsu->ix2vec_used) 509 return False; 510 wv = do_ix2vec( wsu, ws ); 511 /* can never happen .. do_ix2vec will assert instead. Oh well. */ 512 if (wv->owner != wsu) return False; 513 if (wv->size < 0) return False; 514 if (wv->size > 0) { 515 for (i = 0; i < wv->size-1; i++) { 516 if (wv->words[i] >= wv->words[i+1]) 517 return False; 518 } 519 } 520 return True; 521 } 522 523 Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w ) 524 { 525 UWord i; 526 WordVec* wv = do_ix2vec( wsu, ws ); 527 wsu->n_elem++; 528 for (i = 0; i < wv->size; i++) { 529 if (wv->words[i] == w) 530 return True; 531 } 532 return False; 533 } 534 535 WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 ) 536 { 537 WordVec* wv; 538 wsu->n_doubleton++; 539 if (w1 == w2) { 540 wv = new_WV_of_size(wsu, 1); 541 wv->words[0] = w1; 542 } 543 else if (w1 < w2) { 544 wv = new_WV_of_size(wsu, 2); 545 wv->words[0] = w1; 546 wv->words[1] = w2; 547 } 548 else { 549 tl_assert(w1 > w2); 550 wv = new_WV_of_size(wsu, 2); 551 wv->words[0] = w2; 552 wv->words[1] = w1; 553 } 554 return add_or_dealloc_WordVec( wsu, wv ); 555 } 556 557 WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w ) 558 { 559 return HG_(doubletonWS)( wsu, w, w ); 560 } 561 562 WordSet HG_(isSubsetOf) ( WordSetU* wsu, WordSet small, WordSet big ) 563 { 564 wsu->n_isSubsetOf++; 565 return small == HG_(intersectWS)( wsu, small, big ); 566 } 567 568 void HG_(ppWS) ( WordSetU* wsu, WordSet ws ) 569 { 570 UWord i; 571 WordVec* wv; 572 tl_assert(wsu); 573 wv = do_ix2vec( wsu, ws ); 574 VG_(printf)("{"); 575 for (i = 0; i < wv->size; i++) { 576 VG_(printf)("%p", (void*)wv->words[i]); 577 if (i < wv->size-1) 578 VG_(printf)(","); 579 } 580 VG_(printf)("}"); 581 } 582 583 void HG_(ppWSUstats) ( WordSetU* wsu, HChar* name ) 584 { 585 VG_(printf)(" WordSet \"%s\":\n", name); 586 VG_(printf)(" addTo %10lu (%lu uncached)\n", 587 wsu->n_add, wsu->n_add_uncached); 588 VG_(printf)(" delFrom %10lu (%lu uncached)\n", 589 wsu->n_del, wsu->n_del_uncached); 590 VG_(printf)(" union %10lu\n", wsu->n_union); 591 VG_(printf)(" intersect %10lu (%lu uncached) " 592 "[nb. incl isSubsetOf]\n", 593 wsu->n_intersect, wsu->n_intersect_uncached); 594 VG_(printf)(" minus %10lu (%lu uncached)\n", 595 wsu->n_minus, wsu->n_minus_uncached); 596 VG_(printf)(" elem %10lu\n", wsu->n_elem); 597 VG_(printf)(" doubleton %10lu\n", wsu->n_doubleton); 598 VG_(printf)(" isEmpty %10lu\n", wsu->n_isEmpty); 599 VG_(printf)(" isSingleton %10lu\n", wsu->n_isSingleton); 600 VG_(printf)(" anyElementOf %10lu\n", wsu->n_anyElementOf); 601 VG_(printf)(" isSubsetOf %10lu\n", wsu->n_isSubsetOf); 602 VG_(printf)(" dieWS %10lu\n", wsu->n_die); 603 } 604 605 WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w ) 606 { 607 UWord k, j; 608 WordVec* wv_new; 609 WordVec* wv; 610 WordSet result = (WordSet)(-1); /* bogus */ 611 612 wsu->n_add++; 613 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_addTo, ws, w); 614 wsu->n_add_uncached++; 615 616 /* If already present, this is a no-op. */ 617 wv = do_ix2vec( wsu, ws ); 618 for (k = 0; k < wv->size; k++) { 619 if (wv->words[k] == w) { 620 result = ws; 621 goto out; 622 } 623 } 624 /* Ok, not present. Build a new one ... */ 625 wv_new = new_WV_of_size( wsu, wv->size + 1 ); 626 k = j = 0; 627 for (; k < wv->size && wv->words[k] < w; k++) { 628 wv_new->words[j++] = wv->words[k]; 629 } 630 wv_new->words[j++] = w; 631 for (; k < wv->size; k++) { 632 tl_assert(wv->words[k] > w); 633 wv_new->words[j++] = wv->words[k]; 634 } 635 tl_assert(j == wv_new->size); 636 637 /* Find any existing copy, or add the new one. */ 638 result = add_or_dealloc_WordVec( wsu, wv_new ); 639 tl_assert(result != (WordSet)(-1)); 640 641 out: 642 WCache_UPDATE(wsu->cache_addTo, ws, w, result); 643 return result; 644 } 645 646 WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w ) 647 { 648 UWord i, j, k; 649 WordVec* wv_new; 650 WordSet result = (WordSet)(-1); /* bogus */ 651 WordVec* wv = do_ix2vec( wsu, ws ); 652 653 wsu->n_del++; 654 655 /* special case empty set */ 656 if (wv->size == 0) { 657 tl_assert(ws == wsu->empty); 658 return ws; 659 } 660 661 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_delFrom, ws, w); 662 wsu->n_del_uncached++; 663 664 /* If not already present, this is a no-op. */ 665 for (i = 0; i < wv->size; i++) { 666 if (wv->words[i] == w) 667 break; 668 } 669 if (i == wv->size) { 670 result = ws; 671 goto out; 672 } 673 /* So w is present in ws, and the new set will be one element 674 smaller. */ 675 tl_assert(i >= 0 && i < wv->size); 676 tl_assert(wv->size > 0); 677 678 wv_new = new_WV_of_size( wsu, wv->size - 1 ); 679 j = k = 0; 680 for (; j < wv->size; j++) { 681 if (j == i) 682 continue; 683 wv_new->words[k++] = wv->words[j]; 684 } 685 tl_assert(k == wv_new->size); 686 687 result = add_or_dealloc_WordVec( wsu, wv_new ); 688 if (wv->size == 1) { 689 tl_assert(result == wsu->empty); 690 } 691 692 out: 693 WCache_UPDATE(wsu->cache_delFrom, ws, w, result); 694 return result; 695 } 696 697 WordSet HG_(unionWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) 698 { 699 UWord i1, i2, k, sz; 700 WordVec* wv_new; 701 WordVec* wv1 = do_ix2vec( wsu, ws1 ); 702 WordVec* wv2 = do_ix2vec( wsu, ws2 ); 703 wsu->n_union++; 704 sz = 0; 705 i1 = i2 = 0; 706 while (1) { 707 if (i1 >= wv1->size || i2 >= wv2->size) 708 break; 709 sz++; 710 if (wv1->words[i1] < wv2->words[i2]) { 711 i1++; 712 } else 713 if (wv1->words[i1] > wv2->words[i2]) { 714 i2++; 715 } else { 716 i1++; 717 i2++; 718 } 719 } 720 tl_assert(i1 <= wv1->size); 721 tl_assert(i2 <= wv2->size); 722 tl_assert(i1 == wv1->size || i2 == wv2->size); 723 if (i1 == wv1->size && i2 < wv2->size) { 724 sz += (wv2->size - i2); 725 } 726 if (i2 == wv2->size && i1 < wv1->size) { 727 sz += (wv1->size - i1); 728 } 729 730 wv_new = new_WV_of_size( wsu, sz ); 731 k = 0; 732 733 i1 = i2 = 0; 734 while (1) { 735 if (i1 >= wv1->size || i2 >= wv2->size) 736 break; 737 if (wv1->words[i1] < wv2->words[i2]) { 738 wv_new->words[k++] = wv1->words[i1]; 739 i1++; 740 } else 741 if (wv1->words[i1] > wv2->words[i2]) { 742 wv_new->words[k++] = wv2->words[i2]; 743 i2++; 744 } else { 745 wv_new->words[k++] = wv1->words[i1]; 746 i1++; 747 i2++; 748 } 749 } 750 tl_assert(i1 <= wv1->size); 751 tl_assert(i2 <= wv2->size); 752 tl_assert(i1 == wv1->size || i2 == wv2->size); 753 if (i1 == wv1->size && i2 < wv2->size) { 754 while (i2 < wv2->size) 755 wv_new->words[k++] = wv2->words[i2++]; 756 } 757 if (i2 == wv2->size && i1 < wv1->size) { 758 while (i1 < wv1->size) 759 wv_new->words[k++] = wv1->words[i1++]; 760 } 761 762 tl_assert(k == sz); 763 764 return add_or_dealloc_WordVec( wsu, wv_new ); 765 } 766 767 WordSet HG_(intersectWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) 768 { 769 UWord i1, i2, k, sz; 770 WordSet ws_new = (WordSet)(-1); /* bogus */ 771 WordVec* wv_new; 772 WordVec* wv1; 773 WordVec* wv2; 774 775 wsu->n_intersect++; 776 777 /* Deal with an obvious case fast. */ 778 if (ws1 == ws2) 779 return ws1; 780 781 /* Since intersect(x,y) == intersect(y,x), convert both variants to 782 the same query. This reduces the number of variants the cache 783 has to deal with. */ 784 if (ws1 > ws2) { 785 WordSet wst = ws1; ws1 = ws2; ws2 = wst; 786 } 787 788 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_intersect, ws1, ws2); 789 wsu->n_intersect_uncached++; 790 791 wv1 = do_ix2vec( wsu, ws1 ); 792 wv2 = do_ix2vec( wsu, ws2 ); 793 sz = 0; 794 i1 = i2 = 0; 795 while (1) { 796 if (i1 >= wv1->size || i2 >= wv2->size) 797 break; 798 if (wv1->words[i1] < wv2->words[i2]) { 799 i1++; 800 } else 801 if (wv1->words[i1] > wv2->words[i2]) { 802 i2++; 803 } else { 804 sz++; 805 i1++; 806 i2++; 807 } 808 } 809 tl_assert(i1 <= wv1->size); 810 tl_assert(i2 <= wv2->size); 811 tl_assert(i1 == wv1->size || i2 == wv2->size); 812 813 wv_new = new_WV_of_size( wsu, sz ); 814 k = 0; 815 816 i1 = i2 = 0; 817 while (1) { 818 if (i1 >= wv1->size || i2 >= wv2->size) 819 break; 820 if (wv1->words[i1] < wv2->words[i2]) { 821 i1++; 822 } else 823 if (wv1->words[i1] > wv2->words[i2]) { 824 i2++; 825 } else { 826 wv_new->words[k++] = wv1->words[i1]; 827 i1++; 828 i2++; 829 } 830 } 831 tl_assert(i1 <= wv1->size); 832 tl_assert(i2 <= wv2->size); 833 tl_assert(i1 == wv1->size || i2 == wv2->size); 834 835 tl_assert(k == sz); 836 837 ws_new = add_or_dealloc_WordVec( wsu, wv_new ); 838 if (sz == 0) { 839 tl_assert(ws_new == wsu->empty); 840 } 841 842 tl_assert(ws_new != (WordSet)(-1)); 843 WCache_UPDATE(wsu->cache_intersect, ws1, ws2, ws_new); 844 845 return ws_new; 846 } 847 848 WordSet HG_(minusWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) 849 { 850 UWord i1, i2, k, sz; 851 WordSet ws_new = (WordSet)(-1); /* bogus */ 852 WordVec* wv_new; 853 WordVec* wv1; 854 WordVec* wv2; 855 856 wsu->n_minus++; 857 WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_minus, ws1, ws2); 858 wsu->n_minus_uncached++; 859 860 wv1 = do_ix2vec( wsu, ws1 ); 861 wv2 = do_ix2vec( wsu, ws2 ); 862 sz = 0; 863 i1 = i2 = 0; 864 while (1) { 865 if (i1 >= wv1->size || i2 >= wv2->size) 866 break; 867 if (wv1->words[i1] < wv2->words[i2]) { 868 sz++; 869 i1++; 870 } else 871 if (wv1->words[i1] > wv2->words[i2]) { 872 i2++; 873 } else { 874 i1++; 875 i2++; 876 } 877 } 878 tl_assert(i1 <= wv1->size); 879 tl_assert(i2 <= wv2->size); 880 tl_assert(i1 == wv1->size || i2 == wv2->size); 881 if (i2 == wv2->size && i1 < wv1->size) { 882 sz += (wv1->size - i1); 883 } 884 885 wv_new = new_WV_of_size( wsu, sz ); 886 k = 0; 887 888 i1 = i2 = 0; 889 while (1) { 890 if (i1 >= wv1->size || i2 >= wv2->size) 891 break; 892 if (wv1->words[i1] < wv2->words[i2]) { 893 wv_new->words[k++] = wv1->words[i1]; 894 i1++; 895 } else 896 if (wv1->words[i1] > wv2->words[i2]) { 897 i2++; 898 } else { 899 i1++; 900 i2++; 901 } 902 } 903 tl_assert(i1 <= wv1->size); 904 tl_assert(i2 <= wv2->size); 905 tl_assert(i1 == wv1->size || i2 == wv2->size); 906 if (i2 == wv2->size && i1 < wv1->size) { 907 while (i1 < wv1->size) 908 wv_new->words[k++] = wv1->words[i1++]; 909 } 910 911 tl_assert(k == sz); 912 913 ws_new = add_or_dealloc_WordVec( wsu, wv_new ); 914 if (sz == 0) { 915 tl_assert(ws_new == wsu->empty); 916 } 917 918 tl_assert(ws_new != (WordSet)(-1)); 919 WCache_UPDATE(wsu->cache_minus, ws1, ws2, ws_new); 920 921 return ws_new; 922 } 923 924 static __attribute__((unused)) 925 void show_WS ( WordSetU* wsu, WordSet ws ) 926 { 927 UWord i; 928 WordVec* wv = do_ix2vec( wsu, ws ); 929 VG_(printf)("#%u{", ws); 930 for (i = 0; i < wv->size; i++) { 931 VG_(printf)("%lu", wv->words[i]); 932 if (i < wv->size-1) 933 VG_(printf)(","); 934 } 935 VG_(printf)("}\n"); 936 } 937 938 //------------------------------------------------------------------// 939 //--- end WordSet ---// 940 //--- Implementation ---// 941 //------------------------------------------------------------------// 942 943 /*--------------------------------------------------------------------*/ 944 /*--- end hg_wordset.c ---*/ 945 /*--------------------------------------------------------------------*/ 946
