1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- Sets of words, with unique set identifiers. ---*/ 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- hg_wordset.h ---*/ 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 11b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Copyright (C) 2007-2011 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#ifndef __HG_WORDSET_H 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define __HG_WORDSET_H 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- WordSet ---// 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Public Interface ---// 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct _WordSetU WordSetU; /* opaque */ 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef UInt WordSet; /* opaque, small int index */ 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Allocate and initialise a WordSetU */ 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSetU* HG_(newWordSetU) ( void* (*alloc_nofail)( HChar*, SizeT ), 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown HChar* cc, 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void (*dealloc)(void*), 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown Word cacheSize ); 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Free up the WordSetU. */ 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid HG_(deleteWordSetU) ( WordSetU* ); 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 58b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* Get the number of elements in this WordSetU. Note that the dead 59b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov WordSet are included in the WordSetU number of elements. */ 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord HG_(cardinalityWSU) ( WordSetU* ); 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Show performance stats for this WordSetU. */ 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid HG_(ppWSUstats) ( WordSetU* wsu, HChar* name ); 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* Element-level operations on WordSets. Note that the WordSet 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown numbers given out are 0, 1, 2, 3, etc, and as it happens 0 always 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown represents the empty set. */ 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(emptyWS) ( WordSetU* ); 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(addToWS) ( WordSetU*, WordSet, UWord ); 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(delFromWS) ( WordSetU*, WordSet, UWord ); 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(unionWS) ( WordSetU*, WordSet, WordSet ); 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(intersectWS) ( WordSetU*, WordSet, WordSet ); 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(minusWS) ( WordSetU*, WordSet, WordSet ); 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool HG_(isEmptyWS) ( WordSetU*, WordSet ); 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool HG_(isSingletonWS) ( WordSetU*, WordSet, UWord ); 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord HG_(anyElementOfWS) ( WordSetU*, WordSet ); 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownUWord HG_(cardinalityWS) ( WordSetU*, WordSet ); 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool HG_(elemWS) ( WordSetU*, WordSet, UWord ); 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(doubletonWS) ( WordSetU*, UWord, UWord ); 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(singletonWS) ( WordSetU*, UWord ); 83ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownWordSet HG_(isSubsetOf) ( WordSetU*, WordSet, WordSet ); 84ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 85ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool HG_(plausibleWS) ( WordSetU*, WordSet ); 86b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 87b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 88ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff BrownBool HG_(saneWS_SLOW) ( WordSetU*, WordSet ); 89ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 90ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid HG_(ppWS) ( WordSetU*, WordSet ); 91b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 92ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownvoid HG_(getPayloadWS) ( /*OUT*/UWord** words, /*OUT*/UWord* nWords, 93ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown WordSetU*, WordSet ); 94ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 95b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* HG_(dieWS) indicates WordSet is not used/not referenced anymore, 96b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov and its memory can be reclaimed. 97b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov If ever a WordSet with the same content would be needed again, 98b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov a new WordSet will be reallocated. 99b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 100b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov BUG ALERT: !!! Using HG_(dieWS) on a WSU introduces a risk of 101b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov dangling references. Dangling references can be created by keeping 102b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov a ws after having marked it dead. This ws (just an index in 103b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov reality) will be re-cycled : a newly created wv can get the same 104b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov index. This implies that the wrong wv will be used if the 105b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov "old" ws has been kept. 106b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Re-using a "dead" ws will be detected if the index has not been 107b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov re-cycled yet. 108b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 109b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov Another possibility of bug is to ask for the payload of a ws, and 110b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov then have this ws marked dead while the payload is still being 111b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov examined. This is a real dangling reference in free or re-allocated 112b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov memory. */ 113b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovvoid HG_(dieWS) ( WordSetU*, WordSet ); 114b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 115b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 116ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 117ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 118ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- end WordSet ---// 119ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//--- Public Interface ---// 120ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown//------------------------------------------------------------------// 121ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 122ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif /* ! __HG_WORDSET_H */ 123ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 124ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 125ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--- end hg_wordset.h ---*/ 126ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/*--------------------------------------------------------------------*/ 127