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