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 | 4d474d0 | 2008-02-11 11:34:59 +0000 | [diff] [blame] | 11 | Copyright (C) 2007-2008 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" |
| 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 | |
| 50 | typedef |
| 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 |
| 62 | typedef |
| 63 | struct { |
| 64 | WCacheEnt ent[N_WCACHE_STAT_MAX]; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 65 | UWord dynMax; /* 1 .. N_WCACHE_STAT_MAX inclusive */ |
| 66 | UWord inUse; /* 0 .. dynMax inclusive */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 { \ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 80 | UWord _i; \ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 130 | typedef |
| 131 | struct { |
| 132 | WordSetU* owner; /* for sanity checking */ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 133 | UWord* words; |
| 134 | UWord size; /* Really this should be SizeT */ |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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. */ |
| 142 | struct _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 */ |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 147 | UWord ix2vec_size; |
| 148 | UWord ix2vec_used; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 175 | static WordVec* new_WV_of_size ( WordSetU* wsu, UWord sz ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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) { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 184 | wv->words = wsu->alloc( (SizeT)sz * sizeof(UWord) ); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 185 | } |
| 186 | return wv; |
| 187 | } |
| 188 | |
| 189 | static 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 | } |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 197 | static void delete_WV_for_FM ( UWord wv ) { |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 198 | delete_WV( (WordVec*)wv ); |
| 199 | } |
| 200 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 201 | static Word cmp_WordVecs_for_FM ( UWord wv1W, UWord wv2W ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 202 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 203 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 204 | WordVec* wv1 = (WordVec*)wv1W; |
| 205 | WordVec* wv2 = (WordVec*)wv2W; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 206 | UWord common = wv1->size < wv2->size ? wv1->size : wv2->size; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 232 | static 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. */ |
| 254 | static 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 | */ |
| 274 | static WordSet add_or_dealloc_WordVec( WordSetU* wsu, WordVec* wv_new ) |
| 275 | { |
| 276 | Bool have; |
| 277 | WordVec* wv_old; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 278 | UWord/*Set*/ ix_old = -1; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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, |
sewardj | b5f2964 | 2007-11-16 12:02:43 +0000 | [diff] [blame] | 284 | (Word*)&wv_old, (Word*)&ix_old, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 308 | WordSetU* 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 | |
| 333 | void 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 | |
| 343 | WordSet HG_(emptyWS) ( WordSetU* wsu ) |
| 344 | { |
| 345 | return wsu->empty; |
| 346 | } |
| 347 | |
| 348 | Bool 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 361 | Bool HG_(isSingletonWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 370 | UWord HG_(cardinalityWS) ( WordSetU* wsu, WordSet ws ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 379 | UWord HG_(anyElementOfWS) ( WordSetU* wsu, WordSet ws ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 389 | UWord HG_(cardinalityWSU) ( WordSetU* wsu ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 390 | { |
| 391 | tl_assert(wsu); |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 392 | return wsu->ix2vec_used; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 393 | } |
| 394 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 395 | void HG_(getPayloadWS) ( /*OUT*/UWord** words, /*OUT*/UWord* nWords, |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 406 | Bool 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 | |
| 414 | Bool HG_(saneWS_SLOW) ( WordSetU* wsu, WordSet ws ) |
| 415 | { |
| 416 | WordVec* wv; |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 417 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 434 | Bool HG_(elemWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 435 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 436 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 446 | WordSet HG_(doubletonWS) ( WordSetU* wsu, UWord w1, UWord w2 ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 468 | WordSet HG_(singletonWS) ( WordSetU* wsu, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 469 | { |
| 470 | return HG_(doubletonWS)( wsu, w, w ); |
| 471 | } |
| 472 | |
| 473 | WordSet HG_(isSubsetOf) ( WordSetU* wsu, WordSet small, WordSet big ) |
| 474 | { |
| 475 | wsu->n_isSubsetOf++; |
| 476 | return small == HG_(intersectWS)( wsu, small, big ); |
| 477 | } |
| 478 | |
| 479 | void HG_(ppWS) ( WordSetU* wsu, WordSet ws ) |
| 480 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 481 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 494 | void HG_(ppWSUstats) ( WordSetU* wsu, HChar* name ) |
| 495 | { |
| 496 | VG_(printf)(" WordSet \"%s\":\n", name); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame^] | 497 | VG_(printf)(" addTo %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 498 | wsu->n_add, wsu->n_add_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame^] | 499 | VG_(printf)(" delFrom %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 500 | wsu->n_del, wsu->n_del_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame^] | 501 | VG_(printf)(" union %10lu\n", wsu->n_union); |
| 502 | VG_(printf)(" intersect %10lu (%lu uncached) [nb. incl isSubsetOf]\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 503 | wsu->n_intersect, wsu->n_intersect_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame^] | 504 | VG_(printf)(" minus %10lu (%lu uncached)\n", |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 505 | wsu->n_minus, wsu->n_minus_uncached); |
bart | a0b6b2c | 2008-07-07 06:49:24 +0000 | [diff] [blame^] | 506 | VG_(printf)(" elem %10lu\n", wsu->n_elem); |
| 507 | VG_(printf)(" doubleton %10lu\n", wsu->n_doubleton); |
| 508 | VG_(printf)(" isEmpty %10lu\n", wsu->n_isEmpty); |
| 509 | VG_(printf)(" isSingleton %10lu\n", wsu->n_isSingleton); |
| 510 | VG_(printf)(" anyElementOf %10lu\n", wsu->n_anyElementOf); |
| 511 | VG_(printf)(" isSubsetOf %10lu\n", wsu->n_isSubsetOf); |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 512 | } |
| 513 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 514 | WordSet HG_(addToWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 515 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 516 | UWord k, j; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 555 | WordSet HG_(delFromWS) ( WordSetU* wsu, WordSet ws, UWord w ) |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 556 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 557 | UWord i, j, k; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 606 | WordSet HG_(unionWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) |
| 607 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 608 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 676 | WordSet HG_(intersectWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) |
| 677 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 678 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 757 | WordSet HG_(minusWS) ( WordSetU* wsu, WordSet ws1, WordSet ws2 ) |
| 758 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 759 | UWord i1, i2, k, sz; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | |
| 833 | static __attribute__((unused)) |
| 834 | void show_WS ( WordSetU* wsu, WordSet ws ) |
| 835 | { |
sewardj | 250ec2e | 2008-02-15 22:02:30 +0000 | [diff] [blame] | 836 | UWord i; |
sewardj | b411202 | 2007-11-09 22:49:28 +0000 | [diff] [blame] | 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 | /*--------------------------------------------------------------------*/ |