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