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