sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 9eecbbb | 2010-05-03 21:37:12 +0000 | [diff] [blame] | 11 | Copyright (C) 2007-2010 OpenWorks LLP |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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" |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 41 | #include "pub_tool_threadstate.h" |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 42 | #include "pub_tool_wordfm.h" |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 43 | |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 44 | #include "hg_basics.h" |
| 45 | #include "hg_wordset.h" /* self */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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]; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 66 | UWord dynMax; /* 1 .. N_WCACHE_STAT_MAX inclusive */ |
| 67 | UWord inUse; /* 0 .. dynMax inclusive */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 { \ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 81 | UWord _i; \ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 */ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 134 | UWord* words; |
| 135 | UWord size; /* Really this should be SizeT */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 { |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 144 | void* (*alloc)(HChar*,SizeT); |
| 145 | HChar* cc; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 146 | void (*dealloc)(void*); |
| 147 | WordFM* vec2ix; /* WordVec-to-WordSet mapping tree */ |
| 148 | WordVec** ix2vec; /* WordSet-to-WordVec mapping array */ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 149 | UWord ix2vec_size; |
| 150 | UWord ix2vec_used; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 177 | static WordVec* new_WV_of_size ( WordSetU* wsu, UWord sz ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 178 | { |
| 179 | WordVec* wv; |
| 180 | tl_assert(sz >= 0); |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 181 | wv = wsu->alloc( wsu->cc, sizeof(WordVec) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 182 | wv->owner = wsu; |
| 183 | wv->words = NULL; |
| 184 | wv->size = sz; |
| 185 | if (sz > 0) { |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 186 | wv->words = wsu->alloc( wsu->cc, (SizeT)sz * sizeof(UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | } |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 199 | static void delete_WV_for_FM ( UWord wv ) { |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 200 | delete_WV( (WordVec*)wv ); |
| 201 | } |
| 202 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 203 | static Word cmp_WordVecs_for_FM ( UWord wv1W, UWord wv2W ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 204 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 205 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 206 | WordVec* wv1 = (WordVec*)wv1W; |
| 207 | WordVec* wv2 = (WordVec*)wv2W; |
sewardj | 0937c0f | 2011-03-07 19:13:33 +0000 | [diff] [blame] | 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++) { |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | } |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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; |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 239 | new_vec = wsu->alloc( wsu->cc, new_sz * sizeof(WordVec*) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 276 | UWord/*Set*/ ix_old = -1; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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); |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 281 | have = VG_(lookupFM)( wsu->vec2ix, |
sewardj | b5f2964 | 2007-11-16 12:02:43 +0000 | [diff] [blame] | 282 | (Word*)&wv_old, (Word*)&ix_old, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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; |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 297 | VG_(addToFM)( wsu->vec2ix, (Word)wv_new, (Word)wsu->ix2vec_used ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 306 | WordSetU* HG_(newWordSetU) ( void* (*alloc_nofail)( HChar*, SizeT ), |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 307 | HChar* cc, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 308 | void (*dealloc)(void*), |
| 309 | Word cacheSize ) |
| 310 | { |
| 311 | WordSetU* wsu; |
| 312 | WordVec* empty; |
| 313 | |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 314 | wsu = alloc_nofail( cc, sizeof(WordSetU) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 315 | VG_(memset)( wsu, 0, sizeof(WordSetU) ); |
| 316 | wsu->alloc = alloc_nofail; |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 317 | wsu->cc = cc; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 318 | wsu->dealloc = dealloc; |
sewardj | f98e1c0 | 2008-10-25 16:22:41 +0000 | [diff] [blame] | 319 | wsu->vec2ix = VG_(newFM)( alloc_nofail, cc, |
sewardj | 9c606bd | 2008-09-18 18:12:50 +0000 | [diff] [blame] | 320 | dealloc, cmp_WordVecs_for_FM ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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); |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 338 | VG_(deleteFM)( wsu->vec2ix, delete_WV_for_FM, NULL/*val-finalizer*/ ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 362 | Bool HG_(isSingletonWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 371 | UWord HG_(cardinalityWS) ( WordSetU* wsu, WordSet ws ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 380 | UWord HG_(anyElementOfWS) ( WordSetU* wsu, WordSet ws ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 390 | UWord HG_(cardinalityWSU) ( WordSetU* wsu ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 391 | { |
| 392 | tl_assert(wsu); |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 393 | return wsu->ix2vec_used; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 394 | } |
| 395 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 396 | void HG_(getPayloadWS) ( /*OUT*/UWord** words, /*OUT*/UWord* nWords, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 418 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 435 | Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 436 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 437 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 447 | WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 469 | WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 482 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 498 | VG_(printf)(" addTo %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 499 | wsu->n_add, wsu->n_add_uncached); |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 500 | VG_(printf)(" delFrom %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 501 | wsu->n_del, wsu->n_del_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 502 | VG_(printf)(" union %10lu\n", wsu->n_union); |
sewardj | 896f6f9 | 2008-08-19 08:38:52 +0000 | [diff] [blame] | 503 | VG_(printf)(" intersect %10lu (%lu uncached) " |
| 504 | "[nb. incl isSubsetOf]\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 505 | wsu->n_intersect, wsu->n_intersect_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 506 | VG_(printf)(" minus %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 507 | wsu->n_minus, wsu->n_minus_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame] | 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); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 514 | } |
| 515 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 516 | WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 517 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 518 | UWord k, j; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 557 | WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 558 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 559 | UWord i, j, k; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 610 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 680 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 761 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 838 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | /*--------------------------------------------------------------------*/ |