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