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