• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
new_WV_of_size(WordSetU * wsu,UWord sz)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 
delete_WV(WordVec * wv)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 }
delete_WV_for_FM(UWord wv)208 static void delete_WV_for_FM ( UWord wv ) {
209    delete_WV( (WordVec*)wv );
210 }
211 
cmp_WordVecs_for_FM(UWord wv1W,UWord wv2W)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 
ensure_ix2vec_space(WordSetU * wsu)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). */
is_dead(WordSetU * wsu,WordVec * wv)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. */
do_ix2vec(WordSetU * wsu,WordSet ws)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. */
do_ix2vec_with_dead(WordSetU * wsu,WordSet 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 */
add_or_dealloc_WordVec(WordSetU * wsu,WordVec * wv_new)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 
HG_(newWordSetU)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 
HG_(deleteWordSetU)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 
HG_(emptyWS)395 WordSet HG_(emptyWS) ( WordSetU* wsu )
396 {
397    return wsu->empty;
398 }
399 
HG_(isEmptyWS)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 
HG_(isSingletonWS)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 
HG_(cardinalityWS)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 
HG_(anyElementOfWS)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 
HG_(cardinalityWSU)441 UWord HG_(cardinalityWSU) ( WordSetU* wsu )
442 {
443    tl_assert(wsu);
444    return wsu->ix2vec_used;
445 }
446 
HG_(getPayloadWS)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 
HG_(dieWS)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 
HG_(plausibleWS)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 
HG_(saneWS_SLOW)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 
HG_(elemWS)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 
HG_(doubletonWS)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 
HG_(singletonWS)557 WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w )
558 {
559    return HG_(doubletonWS)( wsu, w, w );
560 }
561 
HG_(isSubsetOf)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 
HG_(ppWS)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 
HG_(ppWSUstats)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 
HG_(addToWS)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 
HG_(delFromWS)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 
HG_(unionWS)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 
HG_(intersectWS)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 
HG_(minusWS)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))
show_WS(WordSetU * wsu,WordSet ws)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 /*--------------------------------------------------------------------*/
946