helgrind/hg_wordset.c

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