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