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