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