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 >= 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) {
 507       for (i = 0; i < wv->size-1; i++) {
 508          if (wv->words[i] >= wv->words[i+1])
 509             return False;
 510       }
 511    }
 512    return True;
 513 }
 514
 515 Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w )
 516 {
 517    UWord    i;
 518    WordVec* wv = do_ix2vec( wsu, ws );
 519    wsu->n_elem++;
 520    for (i = 0; i < wv->size; i++) {
 521       if (wv->words[i] == w)
 522          return True;
 523    }
 524    return False;
 525 }
 526
 527 WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 )
 528 {
 529    WordVec* wv;
 530    wsu->n_doubleton++;
 531    if (w1 == w2) {
 532       wv = new_WV_of_size(wsu, 1);
 533       wv->words[0] = w1;
 534    }
 535    else if (w1 < w2) {
 536       wv = new_WV_of_size(wsu, 2);
 537       wv->words[0] = w1;
 538       wv->words[1] = w2;
 539    }
 540    else {
 541       tl_assert(w1 > w2);
 542       wv = new_WV_of_size(wsu, 2);
 543       wv->words[0] = w2;
 544       wv->words[1] = w1;
 545    }
 546    return add_or_dealloc_WordVec( wsu, wv );
 547 }
 548
 549 WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w )
 550 {
 551    return HG_(doubletonWS)( wsu, w, w );
 552 }
 553
 554 WordSet HG_(isSubsetOf) ( WordSetU* wsu, WordSet small, WordSet big )
 555 {
 556    wsu->n_isSubsetOf++;
 557    return small == HG_(intersectWS)( wsu, small, big );
 558 }
 559
 560 void HG_(ppWS) ( WordSetU* wsu, WordSet ws )
 561 {
 562    UWord    i;
 563    WordVec* wv;
 564    tl_assert(wsu);
 565    wv = do_ix2vec( wsu, ws );
 566    VG_(printf)("{");
 567    for (i = 0; i < wv->size; i++) {
 568       VG_(printf)("%p", (void*)wv->words[i]);
 569       if (i < wv->size-1)
 570          VG_(printf)(",");
 571    }
 572    VG_(printf)("}");
 573 }
 574
 575 void HG_(ppWSUstats) ( WordSetU* wsu, const HChar* name )
 576 {
 577    VG_(printf)("   WordSet \"%s\":\n", name);
 578    VG_(printf)("      addTo        %10lu (%lu uncached)\n",
 579                wsu->n_add, wsu->n_add_uncached);
 580    VG_(printf)("      delFrom      %10lu (%lu uncached)\n",
 581                wsu->n_del, wsu->n_del_uncached);
 582    VG_(printf)("      union        %10lu\n", wsu->n_union);
 583    VG_(printf)("      intersect    %10lu (%lu uncached) "
 584                "[nb. incl isSubsetOf]\n",
 585                wsu->n_intersect, wsu->n_intersect_uncached);
 586    VG_(printf)("      minus        %10lu (%lu uncached)\n",
 587                wsu->n_minus, wsu->n_minus_uncached);
 588    VG_(printf)("      elem         %10lu\n",   wsu->n_elem);
 589    VG_(printf)("      doubleton    %10lu\n",   wsu->n_doubleton);
 590    VG_(printf)("      isEmpty      %10lu\n",   wsu->n_isEmpty);
 591    VG_(printf)("      isSingleton  %10lu\n",   wsu->n_isSingleton);
 592    VG_(printf)("      anyElementOf %10lu\n",   wsu->n_anyElementOf);
 593    VG_(printf)("      isSubsetOf   %10lu\n",   wsu->n_isSubsetOf);
 594    VG_(printf)("      dieWS        %10lu\n",   wsu->n_die);
 595 }
 596
 597 WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w )
 598 {
 599    UWord    k, j;
 600    WordVec* wv_new;
 601    WordVec* wv;
 602    WordSet  result = (WordSet)(-1); /* bogus */
 603
 604    wsu->n_add++;
 605    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_addTo, ws, w);
 606    wsu->n_add_uncached++;
 607
 608    /* If already present, this is a no-op. */
 609    wv = do_ix2vec( wsu, ws );
 610    for (k = 0; k < wv->size; k++) {
 611       if (wv->words[k] == w) {
 612          result = ws;
 613          goto out;
 614       }
 615    }
 616    /* Ok, not present.  Build a new one ... */
 617    wv_new = new_WV_of_size( wsu, wv->size + 1 );
 618    k = j = 0;
 619    for (; k < wv->size && wv->words[k] < w; k++) {
 620       wv_new->words[j++] = wv->words[k];
 621    }
 622    wv_new->words[j++] = w;
 623    for (; k < wv->size; k++) {
 624       tl_assert(wv->words[k] > w);
 625       wv_new->words[j++] = wv->words[k];
 626    }
 627    tl_assert(j == wv_new->size);
 628
 629    /* Find any existing copy, or add the new one. */
 630    result = add_or_dealloc_WordVec( wsu, wv_new );
 631    tl_assert(result != (WordSet)(-1));
 632
 633   out:
 634    WCache_UPDATE(wsu->cache_addTo, ws, w, result);
 635    return result;
 636 }
 637
 638 WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w )
 639 {
 640    UWord    i, j, k;
 641    WordVec* wv_new;
 642    WordSet  result = (WordSet)(-1); /* bogus */
 643    WordVec* wv = do_ix2vec( wsu, ws );
 644
 645    wsu->n_del++;
 646
 647    /* special case empty set */
 648    if (wv->size == 0) {
 649       tl_assert(ws == wsu->empty);
 650       return ws;
 651    }
 652
 653    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_delFrom, ws, w);
 654    wsu->n_del_uncached++;
 655
 656    /* If not already present, this is a no-op. */
 657    for (i = 0; i < wv->size; i++) {
 658       if (wv->words[i] == w)
 659          break;
 660    }
 661    if (i == wv->size) {
 662       result = ws;
 663       goto out;
 664    }
 665    /* So w is present in ws, and the new set will be one element
 666       smaller. */
 667    tl_assert(i < wv->size);
 668    tl_assert(wv->size > 0);
 669
 670    wv_new = new_WV_of_size( wsu, wv->size - 1 );
 671    j = k = 0;
 672    for (; j < wv->size; j++) {
 673       if (j == i)
 674          continue;
 675       wv_new->words[k++] = wv->words[j];
 676    }
 677    tl_assert(k == wv_new->size);
 678
 679    result = add_or_dealloc_WordVec( wsu, wv_new );
 680    if (wv->size == 1) {
 681       tl_assert(result == wsu->empty);
 682    }
 683
 684   out:
 685    WCache_UPDATE(wsu->cache_delFrom, ws, w, result);
 686    return result;
 687 }
 688
 689 WordSet HG_(unionWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
 690 {
 691    UWord    i1, i2, k, sz;
 692    WordVec* wv_new;
 693    WordVec* wv1 = do_ix2vec( wsu, ws1 );
 694    WordVec* wv2 = do_ix2vec( wsu, ws2 );
 695    wsu->n_union++;
 696    sz = 0;
 697    i1 = i2 = 0;
 698    while (1) {
 699       if (i1 >= wv1->size || i2 >= wv2->size)
 700          break;
 701       sz++;
 702       if (wv1->words[i1] < wv2->words[i2]) {
 703          i1++;
 704       } else
 705       if (wv1->words[i1] > wv2->words[i2]) {
 706          i2++;
 707       } else {
 708          i1++;
 709          i2++;
 710       }
 711    }
 712    tl_assert(i1 <= wv1->size);
 713    tl_assert(i2 <= wv2->size);
 714    tl_assert(i1 == wv1->size || i2 == wv2->size);
 715    if (i1 == wv1->size && i2 < wv2->size) {
 716       sz += (wv2->size - i2);
 717    }
 718    if (i2 == wv2->size && i1 < wv1->size) {
 719       sz += (wv1->size - i1);
 720    }
 721
 722    wv_new = new_WV_of_size( wsu, sz );
 723    k = 0;
 724
 725    i1 = i2 = 0;
 726    while (1) {
 727       if (i1 >= wv1->size || i2 >= wv2->size)
 728          break;
 729       if (wv1->words[i1] < wv2->words[i2]) {
 730          wv_new->words[k++] = wv1->words[i1];
 731          i1++;
 732       } else
 733       if (wv1->words[i1] > wv2->words[i2]) {
 734          wv_new->words[k++] = wv2->words[i2];
 735          i2++;
 736       } else {
 737          wv_new->words[k++] = wv1->words[i1];
 738          i1++;
 739          i2++;
 740       }
 741    }
 742    tl_assert(i1 <= wv1->size);
 743    tl_assert(i2 <= wv2->size);
 744    tl_assert(i1 == wv1->size || i2 == wv2->size);
 745    if (i1 == wv1->size && i2 < wv2->size) {
 746       while (i2 < wv2->size)
 747          wv_new->words[k++] = wv2->words[i2++];
 748    }
 749    if (i2 == wv2->size && i1 < wv1->size) {
 750       while (i1 < wv1->size)
 751          wv_new->words[k++] = wv1->words[i1++];
 752    }
 753
 754    tl_assert(k == sz);
 755
 756    return add_or_dealloc_WordVec( wsu, wv_new );
 757 }
 758
 759 WordSet HG_(intersectWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
 760 {
 761    UWord    i1, i2, k, sz;
 762    WordSet  ws_new = (WordSet)(-1); /* bogus */
 763    WordVec* wv_new;
 764    WordVec* wv1;
 765    WordVec* wv2;
 766
 767    wsu->n_intersect++;
 768
 769    /* Deal with an obvious case fast. */
 770    if (ws1 == ws2)
 771       return ws1;
 772
 773    /* Since intersect(x,y) == intersect(y,x), convert both variants to
 774       the same query.  This reduces the number of variants the cache
 775       has to deal with. */
 776    if (ws1 > ws2) {
 777       WordSet wst = ws1; ws1 = ws2; ws2 = wst;
 778    }
 779
 780    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_intersect, ws1, ws2);
 781    wsu->n_intersect_uncached++;
 782
 783    wv1 = do_ix2vec( wsu, ws1 );
 784    wv2 = do_ix2vec( wsu, ws2 );
 785    sz = 0;
 786    i1 = i2 = 0;
 787    while (1) {
 788       if (i1 >= wv1->size || i2 >= wv2->size)
 789          break;
 790       if (wv1->words[i1] < wv2->words[i2]) {
 791          i1++;
 792       } else
 793       if (wv1->words[i1] > wv2->words[i2]) {
 794          i2++;
 795       } else {
 796          sz++;
 797          i1++;
 798          i2++;
 799       }
 800    }
 801    tl_assert(i1 <= wv1->size);
 802    tl_assert(i2 <= wv2->size);
 803    tl_assert(i1 == wv1->size || i2 == wv2->size);
 804
 805    wv_new = new_WV_of_size( wsu, sz );
 806    k = 0;
 807
 808    i1 = i2 = 0;
 809    while (1) {
 810       if (i1 >= wv1->size || i2 >= wv2->size)
 811          break;
 812       if (wv1->words[i1] < wv2->words[i2]) {
 813          i1++;
 814       } else
 815       if (wv1->words[i1] > wv2->words[i2]) {
 816          i2++;
 817       } else {
 818          wv_new->words[k++] = wv1->words[i1];
 819          i1++;
 820          i2++;
 821       }
 822    }
 823    tl_assert(i1 <= wv1->size);
 824    tl_assert(i2 <= wv2->size);
 825    tl_assert(i1 == wv1->size || i2 == wv2->size);
 826
 827    tl_assert(k == sz);
 828
 829    ws_new = add_or_dealloc_WordVec( wsu, wv_new );
 830    if (sz == 0) {
 831       tl_assert(ws_new == wsu->empty);
 832    }
 833
 834    tl_assert(ws_new != (WordSet)(-1));
 835    WCache_UPDATE(wsu->cache_intersect, ws1, ws2, ws_new);
 836
 837    return ws_new;
 838 }
 839
 840 WordSet HG_(minusWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 )
 841 {
 842    UWord    i1, i2, k, sz;
 843    WordSet  ws_new = (WordSet)(-1); /* bogus */
 844    WordVec* wv_new;
 845    WordVec* wv1;
 846    WordVec* wv2;
 847
 848    wsu->n_minus++;
 849    WCache_LOOKUP_AND_RETURN(WordSet, wsu->cache_minus, ws1, ws2);
 850    wsu->n_minus_uncached++;
 851
 852    wv1 = do_ix2vec( wsu, ws1 );
 853    wv2 = do_ix2vec( wsu, ws2 );
 854    sz = 0;
 855    i1 = i2 = 0;
 856    while (1) {
 857       if (i1 >= wv1->size || i2 >= wv2->size)
 858          break;
 859       if (wv1->words[i1] < wv2->words[i2]) {
 860          sz++;
 861          i1++;
 862       } else
 863       if (wv1->words[i1] > wv2->words[i2]) {
 864          i2++;
 865       } else {
 866          i1++;
 867          i2++;
 868       }
 869    }
 870    tl_assert(i1 <= wv1->size);
 871    tl_assert(i2 <= wv2->size);
 872    tl_assert(i1 == wv1->size || i2 == wv2->size);
 873    if (i2 == wv2->size && i1 < wv1->size) {
 874       sz += (wv1->size - i1);
 875    }
 876
 877    wv_new = new_WV_of_size( wsu, sz );
 878    k = 0;
 879
 880    i1 = i2 = 0;
 881    while (1) {
 882       if (i1 >= wv1->size || i2 >= wv2->size)
 883          break;
 884       if (wv1->words[i1] < wv2->words[i2]) {
 885          wv_new->words[k++] = wv1->words[i1];
 886          i1++;
 887       } else
 888       if (wv1->words[i1] > wv2->words[i2]) {
 889          i2++;
 890       } else {
 891          i1++;
 892          i2++;
 893       }
 894    }
 895    tl_assert(i1 <= wv1->size);
 896    tl_assert(i2 <= wv2->size);
 897    tl_assert(i1 == wv1->size || i2 == wv2->size);
 898    if (i2 == wv2->size && i1 < wv1->size) {
 899       while (i1 < wv1->size)
 900          wv_new->words[k++] = wv1->words[i1++];
 901    }
 902
 903    tl_assert(k == sz);
 904
 905    ws_new = add_or_dealloc_WordVec( wsu, wv_new );
 906    if (sz == 0) {
 907       tl_assert(ws_new == wsu->empty);
 908    }
 909
 910    tl_assert(ws_new != (WordSet)(-1));
 911    WCache_UPDATE(wsu->cache_minus, ws1, ws2, ws_new);
 912
 913    return ws_new;
 914 }
 915
 916 static __attribute__((unused))
 917 void show_WS ( WordSetU* wsu, WordSet ws )
 918 {
 919    UWord i;
 920    WordVec* wv = do_ix2vec( wsu, ws );
 921    VG_(printf)("#%u{", ws);
 922    for (i = 0; i < wv->size; i++) {
 923       VG_(printf)("%lu", wv->words[i]);
 924       if (i < wv->size-1)
 925          VG_(printf)(",");
 926    }
 927    VG_(printf)("}\n");
 928 }
 929
 930 //------------------------------------------------------------------//
 931 //---                        end WordSet                         ---//
 932 //---                       Implementation                       ---//
 933 //------------------------------------------------------------------//
 934
 935 /*--------------------------------------------------------------------*/
 936 /*--- end                                             hg_wordset.c ---*/
 937 /*--------------------------------------------------------------------*/