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