|
From: <sv...@va...> - 2008-09-21 00:58:10
|
Author: sewardj
Date: 2008-09-21 01:58:00 +0100 (Sun, 21 Sep 2008)
New Revision: 8628
Log:
Start to integrate libhb more closely into Helgrind, and also
make a start on restructuring Helgrind as a whole so as to make
it more maintainable and flexible.
* remove the ability to build libhb standalone (unfortunately)
* create hg_basics.[ch], to hold very basic definitions common
to Helgrind as a whole
* remove duplicate copies of m_xarray.[ch] and m_wordfm.[ch]
from libhb_core.c
Added:
branches/YARD/helgrind/hg_basics.c
branches/YARD/helgrind/hg_basics.h
Removed:
branches/YARD/helgrind/Makefile_sa
branches/YARD/helgrind/libhb_sa.c
branches/YARD/helgrind/libhb_vg.c
Modified:
branches/YARD/helgrind/Makefile.am
branches/YARD/helgrind/hg_main.c
branches/YARD/helgrind/hg_wordset.c
branches/YARD/helgrind/libhb_core.c
Modified: branches/YARD/helgrind/Makefile.am
===================================================================
--- branches/YARD/helgrind/Makefile.am 2008-09-20 16:01:41 UTC (rev 8627)
+++ branches/YARD/helgrind/Makefile.am 2008-09-21 00:58:00 UTC (rev 8628)
@@ -70,7 +70,8 @@
$(PRELOAD_LDFLAGS_PPC64_AIX5) \
$(LIBREPLACEMALLOC_LDFLAGS_PPC64_AIX5)
-HELGRIND_SOURCES_COMMON = hg_wordset.c hg_main.c libhb_vg.c
+HELGRIND_SOURCES_COMMON = \
+ hg_basics.c hg_wordset.c libhb_core.c hg_main.c
helgrind_x86_linux_SOURCES = $(HELGRIND_SOURCES_COMMON)
helgrind_x86_linux_CPPFLAGS = $(AM_CPPFLAGS_X86_LINUX)
@@ -118,6 +119,6 @@
hginclude_HEADERS = helgrind.h
-noinst_HEADERS = hg_wordset.h
+noinst_HEADERS = hg_basics.h hg_wordset.h
-EXTRA_DIST = Makefile_sa README_MSMProp2.txt README_YARD.txt
+EXTRA_DIST = README_MSMProp2.txt README_YARD.txt
Deleted: branches/YARD/helgrind/Makefile_sa
===================================================================
--- branches/YARD/helgrind/Makefile_sa 2008-09-20 16:01:41 UTC (rev 8627)
+++ branches/YARD/helgrind/Makefile_sa 2008-09-21 00:58:00 UTC (rev 8628)
@@ -1,18 +0,0 @@
-
-CC = gcc
-CFLAGS = -g -O -Wall -Wmissing-prototypes -Wshadow \
- -Wpointer-arith -Wbad-function-cast -Wcast-qual \
- -Wcast-align -Wmissing-declarations \
- $(EXTRA_CFLAGS) -g -O -fno-strict-aliasing
-
-all: libhb.h libhb_core.c libhb_sa.c
- $(CC) $(CFLAGS) -o libhb_sa libhb_sa.c
-
-clean:
- rm -f libhb_sa
-
-tarfile:
- XYZZY=`date +\%F-\%T` ; \
- FOOBAR=`echo $$XYZZY | sed s/:/-/g` ; \
- tar cvf libhb3-$$FOOBAR.tar libhb_sa.c libhb_vg.c \
- libhb_core.c libhb.h Makefile_sa
Added: branches/YARD/helgrind/hg_basics.c
===================================================================
--- branches/YARD/helgrind/hg_basics.c (rev 0)
+++ branches/YARD/helgrind/hg_basics.c 2008-09-21 00:58:00 UTC (rev 8628)
@@ -0,0 +1,35 @@
+
+/*--------------------------------------------------------------------*/
+/*--- Basic definitions for all of Helgrind. ---*/
+/*--- hg_basics.c ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of Helgrind, a Valgrind tool for detecting errors
+ in threaded programs.
+
+ Copyright (C) 2007-2008 OpenWorks Ltd
+ in...@op...
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The GNU General Public License is contained in the file COPYING.
+*/
+
+
+/*--------------------------------------------------------------------*/
+/*--- end hg_basics.c ---*/
+/*--------------------------------------------------------------------*/
Added: branches/YARD/helgrind/hg_basics.h
===================================================================
--- branches/YARD/helgrind/hg_basics.h (rev 0)
+++ branches/YARD/helgrind/hg_basics.h 2008-09-21 00:58:00 UTC (rev 8628)
@@ -0,0 +1,41 @@
+
+/*--------------------------------------------------------------------*/
+/*--- Basic definitions for all of Helgrind. ---*/
+/*--- hg_basics.h ---*/
+/*--------------------------------------------------------------------*/
+
+/*
+ This file is part of Helgrind, a Valgrind tool for detecting errors
+ in threaded programs.
+
+ Copyright (C) 2007-2008 OpenWorks Ltd
+ in...@op...
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2 of the
+ License, or (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ The GNU General Public License is contained in the file COPYING.
+*/
+
+#ifndef __HG_BASICS_H
+#define __HG_BASICS_H
+
+#define HG_(str) VGAPPEND(vgHelgrind_,str)
+
+#endif /* ! __HG_BASICS_H */
+
+/*--------------------------------------------------------------------*/
+/*--- end hg_basics.h ---*/
+/*--------------------------------------------------------------------*/
Modified: branches/YARD/helgrind/hg_main.c
===================================================================
--- branches/YARD/helgrind/hg_main.c 2008-09-20 16:01:41 UTC (rev 8627)
+++ branches/YARD/helgrind/hg_main.c 2008-09-21 00:58:00 UTC (rev 8628)
@@ -51,9 +51,9 @@
#include "pub_tool_debuginfo.h" /* VG_(get_data_description) */
#include "pub_tool_wordfm.h"
+#include "hg_basics.h"
#include "helgrind.h"
-#define HG_(str) VGAPPEND(vgHelgrind_,str)
#include "hg_wordset.h"
#include "libhb.h"
Modified: branches/YARD/helgrind/hg_wordset.c
===================================================================
--- branches/YARD/helgrind/hg_wordset.c 2008-09-20 16:01:41 UTC (rev 8627)
+++ branches/YARD/helgrind/hg_wordset.c 2008-09-21 00:58:00 UTC (rev 8628)
@@ -40,7 +40,7 @@
#include "pub_tool_libcprint.h"
#include "pub_tool_wordfm.h"
-#define HG_(str) VGAPPEND(vgHelgrind_,str)
+#include "hg_basics.h"
#include "hg_wordset.h"
//------------------------------------------------------------------//
Modified: branches/YARD/helgrind/libhb_core.c
===================================================================
--- branches/YARD/helgrind/libhb_core.c 2008-09-20 16:01:41 UTC (rev 8627)
+++ branches/YARD/helgrind/libhb_core.c 2008-09-21 00:58:00 UTC (rev 8628)
@@ -31,22 +31,20 @@
02111-1307, USA.
The GNU General Public License is contained in the file COPYING.
-
- //////////////////////////
-
- Note .. apart from those sections of the file which are copyright
- others of course .. only WordFM I believe. Such sections will be
- moved out to separate files in due course.
*/
+#include "pub_tool_basics.h"
+#include "pub_tool_libcassert.h"
+#include "pub_tool_libcbase.h"
+#include "pub_tool_libcprint.h"
+#include "pub_tool_wordfm.h"
+#include "pub_tool_xarray.h"
+#include "pub_tool_oset.h"
+
+#include "hg_basics.h"
#include "libhb.h"
-#undef VG_
-#undef HG_
-#define VG_(_xx) libhbPlainVG_##_xx
-#define HG_(_xx) libhbPlainHG_##_xx
-
/* fwds for
Globals needed by other parts of the library. These are set
once at startup and then never changed. */
@@ -69,2013 +67,6 @@
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
// //
-// SECTION BEGIN xarray //
-// //
-/////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////
-
-/*--------------------------------------------------------------------*/
-/*--- An expandable array implementation. pub_tool_xarray.h ---*/
-/*--------------------------------------------------------------------*/
-
-/*
- This file is part of Valgrind, a dynamic binary instrumentation
- framework.
-
- Copyright (C) 2007-2008 OpenWorks LLP
- in...@op...
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
-
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307, USA.
-
- The GNU General Public License is contained in the file COPYING.
-*/
-
-#ifndef __PUB_TOOL_XARRAY_H
-#define __PUB_TOOL_XARRAY_H
-
-//--------------------------------------------------------------------
-// PURPOSE: Provides a simple but useful structure, which is an array
-// in which elements can be added at the end. The array is expanded
-// as needed by multiplying its size by a constant factor (usually 2).
-// This gives amortised O(1) insertion cost, and, following sorting,
-// the usual O(log N) binary search cost. Arbitrary element sizes
-// are allowed; the comparison function for sort/lookup can be changed
-// at any time, and duplicates (modulo the comparison function) are
-// allowed.
-//--------------------------------------------------------------------
-
-
-/* It's an abstract type. Bwaha. */
-typedef void XArray;
-
-/* Create new XArray, using given allocation and free function, and
- for elements of the specified size. Alloc fn must not fail (that
- is, if it returns it must have succeeded.) */
-extern XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
- HChar* cc,
- void(*free_fn)(void*),
- Word elemSzB );
-
-/* Free all memory associated with an XArray. */
-extern void VG_(deleteXA) ( XArray* );
-
-/* Set the comparison function for this XArray. This clears an
- internal 'array is sorted' flag, which means you must call sortXA
- before making further queries with lookupXA. */
-extern void VG_(setCmpFnXA) ( XArray*, Int (*compar)(void*,void*) );
-
-/* Add an element to an XArray. Element is copied into the XArray.
- Index at which it was added is returned. Note this will be
- invalidated if the array is later sortXA'd. */
-extern Int VG_(addToXA) ( XArray*, void* elem );
-
-/* Add a sequence of bytes to an XArray of bytes. Asserts if nbytes
- is negative or the array's element size is not 1. Returns the
- index at which the first byte was added. */
-extern Int VG_(addBytesToXA) ( XArray* xao, void* bytesV, Int nbytes );
-
-/* Sort an XArray using its comparison function, if set; else bomb.
- Probably not a stable sort w.r.t. equal elements module cmpFn. */
-extern void VG_(sortXA) ( XArray* );
-
-/* Lookup (by binary search) 'key' in the array. Set *first to be the
- index of the first, and *last to be the index of the last matching
- value found. If any values are found, return True, else return
- False, and don't change *first or *last. Bomb if the array is not
- sorted. */
-extern Bool VG_(lookupXA) ( XArray*, void* key,
- /*OUT*/Word* first, /*OUT*/Word* last );
-
-/* How elements are there in this XArray now? */
-extern Word VG_(sizeXA) ( XArray* );
-
-/* Index into the XArray. Checks bounds and bombs if the index is
- invalid. What this returns is the address of the specified element
- in the array, not (of course) the element itself. Note that the
- element may get moved by subsequent addToXAs/sortXAs, so you should
- copy it out immediately and not regard its address as unchanging.
- Note also that indexXA will of course not return NULL if it
- succeeds. */
-extern void* VG_(indexXA) ( XArray*, Word );
-
-/* Drop the last n elements of an XArray. Bombs if there are less
- than n elements in the array. */
-extern void VG_(dropTailXA) ( XArray*, Word );
-
-/* Make a new, completely independent copy of the given XArray, using
- the existing allocation function to allocate the new space.
- Returns NULL if the allocation function didn't manage to allocate
- space (but did return NULL rather than merely abort.) */
-extern XArray* VG_(cloneXA)( XArray* xa );
-
-#endif // __PUB_TOOL_XARRAY_H
-
-/*--------------------------------------------------------------------*/
-/*--- end pub_tool_xarray.h ---*/
-/*--------------------------------------------------------------------*/
-
-/*--------------------------------------------------------------------*/
-/*--- An expandable array implementation. m_xarray.h ---*/
-/*--------------------------------------------------------------------*/
-
-/*
- This file is part of Valgrind, a dynamic binary instrumentation
- framework.
-
- Copyright (C) 2007-2008 OpenWorks LLP
- in...@op...
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
-
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307, USA.
-
- The GNU General Public License is contained in the file COPYING.
-*/
-
-/* See pub_tool_xarray.h for details of what this is all about. */
-
-struct _XArray {
- void* (*alloc) ( HChar*, SizeT ); /* alloc fn (nofail) */
- HChar* cc;
- void (*free) ( void* ); /* free fn */
- Int (*cmpFn) ( void*, void* ); /* cmp fn (may be NULL) */
- Word elemSzB; /* element size in bytes */
- void* arr; /* pointer to elements */
- Word usedsizeE; /* # used elements in arr */
- Word totsizeE; /* max size of arr, in elements */
- Bool sorted; /* is it sorted? */
-};
-
-
-XArray* VG_(newXA) ( void*(*alloc_fn)(HChar*,SizeT),
- HChar* cc,
- void(*free_fn)(void*),
- Word elemSzB )
-{
- struct _XArray* xa;
- /* Implementation relies on Word being signed and (possibly)
- on SizeT being unsigned. */
- vg_assert( sizeof(Word) == sizeof(void*) );
- vg_assert( ((Word)(-1)) < ((Word)(0)) );
- vg_assert( ((SizeT)(-1)) > ((SizeT)(0)) );
- /* check user-supplied info .. */
- vg_assert(alloc_fn);
- vg_assert(free_fn);
- vg_assert(elemSzB > 0);
- xa = alloc_fn( cc, sizeof(struct _XArray) );
- vg_assert(xa);
- xa->alloc = alloc_fn;
- xa->cc = cc;
- xa->free = free_fn;
- xa->cmpFn = NULL;
- xa->elemSzB = elemSzB;
- xa->usedsizeE = 0;
- xa->totsizeE = 0;
- xa->sorted = False;
- xa->arr = NULL;
- return xa;
-}
-
-XArray* VG_(cloneXA)( XArray* xao )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- struct _XArray* nyu;
- vg_assert(xa);
- vg_assert(xa->alloc);
- vg_assert(xa->free);
- vg_assert(xa->elemSzB >= 1);
- nyu = xa->alloc( xa->cc, sizeof(struct _XArray) );
- if (!nyu)
- return NULL;
- /* Copy everything verbatim ... */
- *nyu = *xa;
- /* ... except we have to clone the contents-array */
- if (nyu->arr) {
- nyu->arr = nyu->alloc( nyu->cc, nyu->totsizeE * nyu->elemSzB );
- if (!nyu->arr) {
- nyu->free(nyu);
- return NULL;
- }
- VG_(memcpy)( nyu->arr, xa->arr, nyu->totsizeE * nyu->elemSzB );
- }
- /* We're done! */
- return nyu;
-}
-
-void VG_(deleteXA) ( XArray* xao )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(xa->free);
- if (xa->arr)
- xa->free(xa->arr);
- xa->free(xa);
-}
-
-void VG_(setCmpFnXA) ( XArray* xao, Int (*compar)(void*,void*) )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(compar);
- xa->cmpFn = compar;
- xa->sorted = False;
-}
-
-inline void* VG_(indexXA) ( XArray* xao, Word n )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(n >= 0);
- vg_assert(n < xa->usedsizeE);
- return ((char*)xa->arr) + n * xa->elemSzB;
-}
-
-static inline void ensureSpaceXA ( struct _XArray* xa )
-{
- if (xa->usedsizeE == xa->totsizeE) {
- void* tmp;
- Word newsz;
- if (xa->totsizeE == 0)
- vg_assert(!xa->arr);
- if (xa->totsizeE > 0)
- vg_assert(xa->arr);
- if (xa->totsizeE == 0) {
- /* No point in having tiny (eg) 2-byte allocations for the
- element array, since all allocs are rounded up to 8 anyway.
- Hence increase the initial array size for tiny elements in
- an attempt to avoid reallocations of size 2, 4, 8 if the
- array does start to fill up. */
- if (xa->elemSzB == 1) newsz = 8;
- else if (xa->elemSzB == 2) newsz = 4;
- else newsz = 2;
- } else {
- newsz = 2 * xa->totsizeE;
- }
- if (0)
- VG_(printf)("addToXA: increasing from %ld to %ld\n",
- xa->totsizeE, newsz);
- tmp = xa->alloc(xa->cc, newsz * xa->elemSzB);
- vg_assert(tmp);
- if (xa->usedsizeE > 0)
- VG_(memcpy)(tmp, xa->arr, xa->usedsizeE * xa->elemSzB);
- if (xa->arr)
- xa->free(xa->arr);
- xa->arr = tmp;
- xa->totsizeE = newsz;
- }
-}
-
-Int VG_(addToXA) ( XArray* xao, void* elem )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(elem);
- vg_assert(xa->totsizeE >= 0);
- vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
- ensureSpaceXA( xa );
- vg_assert(xa->usedsizeE < xa->totsizeE);
- vg_assert(xa->arr);
- VG_(memcpy)( ((UChar*)xa->arr) + xa->usedsizeE * xa->elemSzB,
- elem, xa->elemSzB );
- xa->usedsizeE++;
- xa->sorted = False;
- return xa->usedsizeE-1;
-}
-
-Int VG_(addBytesToXA) ( XArray* xao, void* bytesV, Int nbytes )
-{
- Int r, i;
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(xa->elemSzB == 1);
- vg_assert(nbytes >= 0);
- vg_assert(xa->totsizeE >= 0);
- vg_assert(xa->usedsizeE >= 0 && xa->usedsizeE <= xa->totsizeE);
- r = xa->usedsizeE;
- for (i = 0; i < nbytes; i++) {
- ensureSpaceXA( xa );
- vg_assert(xa->usedsizeE < xa->totsizeE);
- vg_assert(xa->arr);
- * (((UChar*)xa->arr) + xa->usedsizeE) = ((UChar*)bytesV)[i];
- xa->usedsizeE++;
- }
- xa->sorted = False;
- return r;
-}
-
-void VG_(sortXA) ( XArray* xao )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(xa->cmpFn);
- VG_(ssort)( xa->arr, xa->usedsizeE, xa->elemSzB, xa->cmpFn );
- xa->sorted = True;
-}
-
-Bool VG_(lookupXA) ( XArray* xao, void* key, Word* first, Word* last )
-{
- Word lo, mid, hi, cres;
- void* midv;
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(xa->cmpFn);
- vg_assert(xa->sorted);
- vg_assert(first);
- vg_assert(last);
- lo = 0;
- hi = xa->usedsizeE-1;
- while (True) {
- /* current unsearched space is from lo to hi, inclusive. */
- if (lo > hi) return False; /* not found */
- mid = (lo + hi) / 2;
- midv = VG_(indexXA)( xa, mid );
- cres = xa->cmpFn( key, midv );
- if (cres < 0) { hi = mid-1; continue; }
- if (cres > 0) { lo = mid+1; continue; }
- /* Found it, at mid. See how far we can expand this. */
- vg_assert(xa->cmpFn( key, VG_(indexXA)(xa, lo) ) >= 0);
- vg_assert(xa->cmpFn( key, VG_(indexXA)(xa, hi) ) <= 0);
- *first = *last = mid;
- while (*first > 0
- && 0 == xa->cmpFn( key, VG_(indexXA)(xa, (*first)-1)))
- (*first)--;
- while (*last < xa->usedsizeE-1
- && 0 == xa->cmpFn( key, VG_(indexXA)(xa, (*last)+1)))
- (*last)++;
- return True;
- }
-}
-
-Word VG_(sizeXA) ( XArray* xao )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- return xa->usedsizeE;
-}
-
-void VG_(dropTailXA) ( XArray* xao, Word n )
-{
- struct _XArray* xa = (struct _XArray*)xao;
- vg_assert(xa);
- vg_assert(n >= 0);
- vg_assert(n <= xa->usedsizeE);
- xa->usedsizeE -= n;
-}
-
-/*--------------------------------------------------------------------*/
-/*--- end m_xarray.c ---*/
-/*--------------------------------------------------------------------*/
-
-/////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////
-// //
-// SECTION END xarray //
-// //
-/////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////
-
-
-
-/////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////
-// //
-// SECTION BEGIN wordfm //
-// //
-/////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////
-
-/*--------------------------------------------------------------------*/
-/*--- An AVL tree based finite map for word keys and word values. ---*/
-/*--- Inspired by Haskell's "FiniteMap" library. ---*/
-/*--- hg_wordfm.h ---*/
-/*--------------------------------------------------------------------*/
-
-/*
- This file is part of Helgrind, a Valgrind tool for detecting errors
- in threaded programs.
-
- Copyright (C) 2007-2008 Julian Seward
- js...@ac...
-
- This code is based on previous work by Nicholas Nethercote
- (coregrind/m_oset.c) which is
-
- Copyright (C) 2005-2008 Nicholas Nethercote
- nj...@va...
-
- which in turn was derived partially from:
-
- AVL C library
- Copyright (C) 2000,2002 Daniel Nagy
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of
- the License, or (at your option) any later version.
- [...]
-
- (taken from libavl-0.4/debian/copyright)
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
-
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307, USA.
-
- The GNU General Public License is contained in the file COPYING.
-*/
-
-#ifndef __HG_WORDFM_H
-#define __HG_WORDFM_H
-
-//------------------------------------------------------------------//
-//--- WordFM ---//
-//--- Public interface ---//
-//------------------------------------------------------------------//
-
-/* As of r7409 (15 Feb 08), all these word-based abstractions (WordFM,
- WordSet, WordBag) now operate on unsigned words (UWord), whereas
- they previously operated on signed words (Word). This became a
- problem, when using unboxed comparisons (when kCmp == NULL), with
- the introduction of HG_(initIterAtFM), which allows iteration over
- parts of mappings. Iterating over a mapping in increasing order of
- signed Word keys is not what callers expect when iterating through
- maps whose keys represent addresses (Addr) since Addr is unsigned,
- and causes logical problems and assertion failures. */
-
-typedef struct _WordFM WordFM; /* opaque */
-
-/* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in
- the set are ordered according to the ordering specified by kCmp,
- which becomes obvious if you use VG_(initIterFM),
- VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
- sections of the map, or the whole thing. If kCmp is NULL then the
- ordering used is unsigned word ordering (UWord) on the key
- values. */
-WordFM* HG_(newFM) ( void* (*alloc_nofail)( HChar*, SizeT ),
- HChar* cc,
- void (*dealloc)(void*),
- Word (*kCmp)(UWord,UWord) );
-
-/* Free up the FM. If kFin is non-NULL, it is applied to keys before
- the FM is deleted; ditto with vFin and wFin for vals. */
-void HG_(deleteFM) ( WordFM* fm, void(*kFin)(UWord),
- void(*vFin)(UWord),
- void(*wFin)(UWord) );
-
-/* Add (k,v,w) to fm. If a binding for k already exists, it is
- updated to map to this new (v,w). In that case we should really
- return the previous (v,w) so that caller can finalise them. Oh
- well. Returns True if a binding for k already exists.*/
-Bool HG_(addToFM) ( WordFM* fm, UWord k, UWord v, UWord w );
-
-// Delete key from fm, returning associated key and vals if found
-Bool HG_(delFromFM) ( WordFM* fm,
- /*OUT*/UWord* oldK,
- /*OUT*/UWord* oldV, /*OUT*/UWord* oldW,
- UWord key );
-
-// Look up in fm, assigning found key & vals at spec'd addresses
-Bool HG_(lookupFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW,
- UWord key );
-
-// How many elements are there in fm? Note; slow; O(# elems in the fm)
-UWord HG_(sizeFM) ( WordFM* fm );
-
-// Is the fm empty? Fast (constant-time)
-Bool HG_(isEmptyFM)( WordFM* fm );
-
-// If fm is non-empty, return arbitrarily chosen key/values
-// through *res{K,V,W}, and return True. If empty return False.
-Bool HG_(anyElementOfFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW );
-
-// set up FM for iteration
-void HG_(initIterFM) ( WordFM* fm );
-
-// set up FM for iteration so that the first key subsequently produced
-// by HG_(nextIterFM) is the smallest key in the map >= start_at.
-// Naturally ">=" is defined by the comparison function supplied to
-// HG_(newFM), as documented above.
-void HG_(initIterAtFM) ( WordFM* fm, UWord start_at );
-
-// get next key/vals. Will assert if fm has been modified
-// or looked up in since initIterFM/initIterWithStartFM was called.
-Bool HG_(nextIterFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW );
-
-// clear the I'm iterating flag
-void HG_(doneIterFM) ( WordFM* fm );
-
-// Deep copy a FM. If dopyK is NULL, keys are copied verbatim.
-// If non-null, dopyK is applied to each key to generate the
-// version in the new copy. In that case, if the argument to dopyK
-// is non-NULL but the result is NULL, it is assumed that dopyK
-// could not allocate memory, in which case the copy is abandoned
-// and NULL is returned. Ditto with dopyV and dopyW for values.
-WordFM* HG_(dopyFM) ( WordFM* fm,
- UWord(*dopyK)(UWord),
- UWord(*dopyV)(UWord), UWord(*dopyW)(UWord) );
-
-//------------------------------------------------------------------//
-//--- end WordFM ---//
-//--- Public interface ---//
-//------------------------------------------------------------------//
-
-//------------------------------------------------------------------//
-//--- WordBag (unboxed words only) ---//
-//--- Public interface ---//
-//------------------------------------------------------------------//
-
-//typedef struct _WordBag WordBag; /* opaque */
-
-// FIXME! find some way to turn this back into an abstract type.
-typedef
- struct {
- void* (*alloc_nofail)( HChar*, SizeT );
- HChar* cc;
- void (*dealloc)(void*);
- UWord firstWord;
- UWord firstCount;
- WordFM* rest;
- /* When zero, the next call to HG_(nextIterBag) gives
- (.firstWord, .firstCount). When nonzero, such calls traverse
- .rest. */
- UWord iterCount;
- }
- WordBag;
-
-
-/* Initialise a WordBag and make it empty. Only do this once for each
- bag, at the start of its lifetime. */
-void HG_(initBag) ( WordBag* bag,
- void* (*alloc_nofail)( HChar*, SizeT ),
- HChar* cc,
- void (*dealloc)(void*) );
-
-/* Remove all elements from a bag, thereby making it empty, and free
- all associated memory. This can be done as many times as required,
- but only after the initial HG_(initBag) call. */
-void HG_(emptyOutBag) ( WordBag* bag );
-
-/* Add a word. */
-void HG_(addToBag)( WordBag*, UWord );
-
-/* Find out how many times the given word exists in the bag. */
-UWord HG_(elemBag) ( WordBag*, UWord );
-
-/* Delete a word from the bag. */
-Bool HG_(delFromBag)( WordBag*, UWord );
-
-/* Is the bag empty? */
-Bool HG_(isEmptyBag)( WordBag* );
-
-/* Is the bag empty, skipping all sanity checks? */
-static inline Bool HG_(isEmptyBag_UNCHECKED)( WordBag* bag ) {
- return bag->firstCount == 0;
-}
-
-/* Does the bag have exactly one element? */
-Bool HG_(isSingletonTotalBag)( WordBag* );
-
-/* Return an arbitrary element from the bag. */
-UWord HG_(anyElementOfBag)( WordBag* );
-
-/* How many different / total elements are in the bag? */
-UWord HG_(sizeUniqueBag)( WordBag* ); /* warning: slow */
-UWord HG_(sizeTotalBag)( WordBag* ); /* warning: very slow */
-
-/* Iterating over the elements of a bag. */
-void HG_(initIterBag)( WordBag* );
-Bool HG_(nextIterBag)( WordBag*, /*OUT*/UWord* pVal, /*OUT*/UWord* pCount );
-void HG_(doneIterBag)( WordBag* );
-
-//------------------------------------------------------------------//
-//--- end WordBag (unboxed words only) ---//
-//--- Public interface ---//
-//------------------------------------------------------------------//
-
-#endif /* ! __HG_WORDFM_H */
-
-/*--------------------------------------------------------------------*/
-/*--- end hg_wordfm.h ---*/
-/*--------------------------------------------------------------------*/
-
-/*--------------------------------------------------------------------*/
-/*--- An AVL tree based finite map for word keys and word values. ---*/
-/*--- Inspired by Haskell's "FiniteMap" library. ---*/
-/*--- hg_wordfm.c ---*/
-/*--------------------------------------------------------------------*/
-
-/*
- This file is part of Helgrind, a Valgrind tool for detecting errors
- in threaded programs.
-
- Copyright (C) 2007-2008 Julian Seward
- js...@ac...
-
- This code is based on previous work by Nicholas Nethercote
- (coregrind/m_oset.c) which is
-
- Copyright (C) 2005-2008 Nicholas Nethercote
- nj...@va...
-
- which in turn was derived partially from:
-
- AVL C library
- Copyright (C) 2000,2002 Daniel Nagy
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of
- the License, or (at your option) any later version.
- [...]
-
- (taken from libavl-0.4/debian/copyright)
-
- This program is free software; you can redistribute it and/or
- modify it under the terms of the GNU General Public License as
- published by the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
-
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307, USA.
-
- The GNU General Public License is contained in the file COPYING.
-*/
-
-#if 0
-#include "pub_tool_basics.h"
-#include "pub_tool_libcassert.h"
-#include "pub_tool_libcbase.h"
-
-
-#ifdef HG_WORDFM_STANDALONE // standalone compilation
-// Standalone mode (for testing).
-// On x86_64 compile like this:
-// gcc -m64 hg_wordfm.c -I../include -I../VEX/pub
-// -DVGA_amd64=1 -DHG_WORDFM_STANDALONE -g -O -Wall
-# include <assert.h>
-# include <string.h>
-# include <stdio.h>
-# include <stdlib.h>
-
-# undef tl_assert
-# define tl_assert assert
-# define vgPlain_memset memset
-
-#endif /* def HG_WORDFM_STANDALONE */
-#endif /* 0 */
-
-
-//------------------------------------------------------------------//
-//--- WordFM ---//
-//--- Implementation ---//
-//------------------------------------------------------------------//
-
-/* One element of the AVL tree */
-typedef
- struct _AvlNode {
- UWord key;
- UWord val;
- UWord wal;
- struct _AvlNode* child[2]; /* [0] is left subtree, [1] is right */
- Char balance; /* do not make this unsigned */
- }
- AvlNode;
-
-typedef
- struct {
- UWord w;
- Bool b;
- }
- MaybeWord;
-
-#define WFM_STKMAX 32 // At most 2**32 entries can be iterated over
-
-struct _WordFM {
- AvlNode* root;
- void* (*alloc_nofail)( HChar*, SizeT );
- HChar* cc;
- void (*dealloc)(void*);
- Word (*kCmp)(UWord,UWord);
- AvlNode* nodeStack[WFM_STKMAX]; // Iterator node stack
- Int numStack[WFM_STKMAX]; // Iterator num stack
- Int stackTop; // Iterator stack pointer, one past end
-};
-
-/* forward */
-static Bool avl_removeroot_wrk(AvlNode** t, Word(*kCmp)(UWord,UWord));
-
-/* Swing to the left. Warning: no balance maintainance. */
-static void avl_swl ( AvlNode** root )
-{
- AvlNode* a = *root;
- AvlNode* b = a->child[1];
- *root = b;
- a->child[1] = b->child[0];
- b->child[0] = a;
-}
-
-/* Swing to the right. Warning: no balance maintainance. */
-static void avl_swr ( AvlNode** root )
-{
- AvlNode* a = *root;
- AvlNode* b = a->child[0];
- *root = b;
- a->child[0] = b->child[1];
- b->child[1] = a;
-}
-
-/* Balance maintainance after especially nasty swings. */
-static void avl_nasty ( AvlNode* root )
-{
- switch (root->balance) {
- case -1:
- root->child[0]->balance = 0;
- root->child[1]->balance = 1;
- break;
- case 1:
- root->child[0]->balance = -1;
- root->child[1]->balance = 0;
- break;
- case 0:
- root->child[0]->balance = 0;
- root->child[1]->balance = 0;
- break;
- default:
- tl_assert(0);
- }
- root->balance=0;
-}
-
-/* Find size of a non-NULL tree. */
-static UWord size_avl_nonNull ( AvlNode* nd )
-{
- return 1 + (nd->child[0] ? size_avl_nonNull(nd->child[0]) : 0)
- + (nd->child[1] ? size_avl_nonNull(nd->child[1]) : 0);
-}
-
-/* Unsignedly compare w1 and w2. If w1 < w2, produce a negative
- number; if w1 > w2 produce a positive number, and if w1 == w2
- produce zero. */
-static inline Word cmp_unsigned_Words ( UWord w1, UWord w2 ) {
- if (w1 < w2) return -1;
- if (w1 > w2) return 1;
- return 0;
-}
-
-/* Insert element a into the AVL tree t. Returns True if the depth of
- the tree has grown. If element with that key is already present,
- just copy a->val to existing node, first returning old ->val field
- of existing node in *oldV, so that the caller can finalize it
- however it wants.
-*/
-static
-Bool avl_insert_wrk ( AvlNode** rootp,
- /*OUT*/MaybeWord* oldV,
- AvlNode* a,
- Word (*kCmp)(UWord,UWord) )
-{
- Word cmpres;
-
- /* initialize */
- a->child[0] = 0;
- a->child[1] = 0;
- a->balance = 0;
- oldV->b = False;
-
- /* insert into an empty tree? */
- if (!(*rootp)) {
- (*rootp) = a;
- return True;
- }
-
- cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key )
- : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key,
- (UWord)a->key );
-
- if (cmpres > 0) {
- /* insert into the left subtree */
- if ((*rootp)->child[0]) {
- AvlNode* left_subtree = (*rootp)->child[0];
- if (avl_insert_wrk(&left_subtree, oldV, a, kCmp)) {
- switch ((*rootp)->balance--) {
- case 1: return False;
- case 0: return True;
- case -1: break;
- default: tl_assert(0);
- }
- if ((*rootp)->child[0]->balance < 0) {
- avl_swr( rootp );
- (*rootp)->balance = 0;
- (*rootp)->child[1]->balance = 0;
- } else {
- avl_swl( &((*rootp)->child[0]) );
- avl_swr( rootp );
- avl_nasty( *rootp );
- }
- } else {
- (*rootp)->child[0] = left_subtree;
- }
- return False;
- } else {
- (*rootp)->child[0] = a;
- if ((*rootp)->balance--)
- return False;
- return True;
- }
- tl_assert(0);/*NOTREACHED*/
- }
- else
- if (cmpres < 0) {
- /* insert into the right subtree */
- if ((*rootp)->child[1]) {
- AvlNode* right_subtree = (*rootp)->child[1];
- if (avl_insert_wrk(&right_subtree, oldV, a, kCmp)) {
- switch((*rootp)->balance++){
- case -1: return False;
- case 0: return True;
- case 1: break;
- default: tl_assert(0);
- }
- if ((*rootp)->child[1]->balance > 0) {
- avl_swl( rootp );
- (*rootp)->balance = 0;
- (*rootp)->child[0]->balance = 0;
- } else {
- avl_swr( &((*rootp)->child[1]) );
- avl_swl( rootp );
- avl_nasty( *rootp );
- }
- } else {
- (*rootp)->child[1] = right_subtree;
- }
- return False;
- } else {
- (*rootp)->child[1] = a;
- if ((*rootp)->balance++)
- return False;
- return True;
- }
- tl_assert(0);/*NOTREACHED*/
- }
- else {
- /* cmpres == 0, a duplicate - replace the val, but don't
- incorporate the node in the tree */
- oldV->b = True;
- oldV->w = (*rootp)->val;
- (*rootp)->val = a->val;
- return False;
- }
-}
-
-/* Remove an element a from the AVL tree t. a must be part of
- the tree. Returns True if the depth of the tree has shrunk.
-*/
-static
-Bool avl_remove_wrk ( AvlNode** rootp,
- AvlNode* a,
- Word(*kCmp)(UWord,UWord) )
-{
- Bool ch;
- Word cmpres;
- cmpres = kCmp ? /*boxed*/ kCmp( (*rootp)->key, a->key )
- : /*unboxed*/ cmp_unsigned_Words( (UWord)(*rootp)->key,
- (UWord)a->key );
-
- if (cmpres > 0){
- /* remove from the left subtree */
- AvlNode* left_subtree = (*rootp)->child[0];
- tl_assert(left_subtree);
- ch = avl_remove_wrk(&left_subtree, a, kCmp);
- (*rootp)->child[0]=left_subtree;
- if (ch) {
- switch ((*rootp)->balance++) {
- case -1: return True;
- case 0: return False;
- case 1: break;
- default: tl_assert(0);
- }
- switch ((*rootp)->child[1]->balance) {
- case 0:
- avl_swl( rootp );
- (*rootp)->balance = -1;
- (*rootp)->child[0]->balance = 1;
- return False;
- case 1:
- avl_swl( rootp );
- (*rootp)->balance = 0;
- (*rootp)->child[0]->balance = 0;
- return True;
- case -1:
- break;
- default:
- tl_assert(0);
- }
- avl_swr( &((*rootp)->child[1]) );
- avl_swl( rootp );
- avl_nasty( *rootp );
- return True;
- }
- }
- else
- if (cmpres < 0) {
- /* remove from the right subtree */
- AvlNode* right_subtree = (*rootp)->child[1];
- tl_assert(right_subtree);
- ch = avl_remove_wrk(&right_subtree, a, kCmp);
- (*rootp)->child[1] = right_subtree;
- if (ch) {
- switch ((*rootp)->balance--) {
- case 1: return True;
- case 0: return False;
- case -1: break;
- default: tl_assert(0);
- }
- switch ((*rootp)->child[0]->balance) {
- case 0:
- avl_swr( rootp );
- (*rootp)->balance = 1;
- (*rootp)->child[1]->balance = -1;
- return False;
- case -1:
- avl_swr( rootp );
- (*rootp)->balance = 0;
- (*rootp)->child[1]->balance = 0;
- return True;
- case 1:
- break;
- default:
- tl_assert(0);
- }
- avl_swl( &((*rootp)->child[0]) );
- avl_swr( rootp );
- avl_nasty( *rootp );
- return True;
- }
- }
- else {
- tl_assert(cmpres == 0);
- tl_assert((*rootp)==a);
- return avl_removeroot_wrk(rootp, kCmp);
- }
- return 0;
-}
-
-/* Remove the root of the AVL tree *rootp.
- * Warning: dumps core if *rootp is empty
- */
-static
-Bool avl_removeroot_wrk ( AvlNode** rootp,
- Word(*kCmp)(UWord,UWord) )
-{
- Bool ch;
- AvlNode* a;
- if (!(*rootp)->child[0]) {
- if (!(*rootp)->child[1]) {
- (*rootp) = 0;
- return True;
- }
- (*rootp) = (*rootp)->child[1];
- return True;
- }
- if (!(*rootp)->child[1]) {
- (*rootp) = (*rootp)->child[0];
- return True;
- }
- if ((*rootp)->balance < 0) {
- /* remove from the left subtree */
- a = (*rootp)->child[0];
- while (a->child[1]) a = a->child[1];
- } else {
- /* remove from the right subtree */
- a = (*rootp)->child[1];
- while (a->child[0]) a = a->child[0];
- }
- ch = avl_remove_wrk(rootp, a, kCmp);
- a->child[0] = (*rootp)->child[0];
- a->child[1] = (*rootp)->child[1];
- a->balance = (*rootp)->balance;
- (*rootp) = a;
- if(a->balance == 0) return ch;
- return False;
-}
-
-static
-AvlNode* avl_find_node ( AvlNode* t, Word k, Word(*kCmp)(UWord,UWord) )
-{
- if (kCmp) {
- /* Boxed comparisons */
- Word cmpresS;
- while (True) {
- if (t == NULL) return NULL;
- cmpresS = kCmp(t->key, k);
- if (cmpresS > 0) t = t->child[0]; else
- if (cmpresS < 0) t = t->child[1]; else
- return t;
- }
- } else {
- /* Unboxed comparisons */
- Word cmpresS; /* signed */
- UWord cmpresU; /* unsigned */
- while (True) {
- if (t == NULL) return NULL; /* unlikely ==> predictable */
- cmpresS = cmp_unsigned_Words( (UWord)t->key, (UWord)k );
- if (cmpresS == 0) return t; /* unlikely ==> predictable */
- cmpresU = (UWord)cmpresS;
- cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1);
- t = t->child[cmpresU];
- }
- }
-}
-
-// Clear the iterator stack.
-static void stackClear(WordFM* fm)
-{
- Int i;
- tl_assert(fm);
- for (i = 0; i < WFM_STKMAX; i++) {
- fm->nodeStack[i] = NULL;
- fm->numStack[i] = 0;
- }
- fm->stackTop = 0;
-}
-
-// Push onto the iterator stack.
-static inline void stackPush(WordFM* fm, AvlNode* n, Int i)
-{
- tl_assert(fm->stackTop < WFM_STKMAX);
- tl_assert(1 <= i && i <= 3);
- fm->nodeStack[fm->stackTop] = n;
- fm-> numStack[fm->stackTop] = i;
- fm->stackTop++;
-}
-
-// Pop from the iterator stack.
-static inline Bool stackPop(WordFM* fm, AvlNode** n, Int* i)
-{
- tl_assert(fm->stackTop <= WFM_STKMAX);
-
- if (fm->stackTop > 0) {
- fm->stackTop--;
- *n = fm->nodeStack[fm->stackTop];
- *i = fm-> numStack[fm->stackTop];
- tl_assert(1 <= *i && *i <= 3);
- fm->nodeStack[fm->stackTop] = NULL;
- fm-> numStack[fm->stackTop] = 0;
- return True;
- } else {
- return False;
- }
-}
-
-static
-AvlNode* avl_dopy ( AvlNode* nd,
- UWord(*dopyK)(UWord),
- UWord(*dopyV)(UWord),
- UWord(*dopyW)(UWord),
- void*(alloc_nofail)(HChar*,SizeT),
- HChar* cc )
-{
- AvlNode* nyu;
- if (! nd)
- return NULL;
- nyu = alloc_nofail(cc, sizeof(AvlNode));
- tl_assert(nyu);
-
- nyu->child[0] = nd->child[0];
- nyu->child[1] = nd->child[1];
- nyu->balance = nd->balance;
-
- /* Copy key */
- if (dopyK) {
- nyu->key = dopyK( nd->key );
- if (nd->key != 0 && nyu->key == 0)
- return NULL; /* oom in key dcopy */
- } else {
- /* copying assumedly unboxed keys */
- nyu->key = nd->key;
- }
-
- /* Copy val */
- if (dopyV) {
- nyu->val = dopyV( nd->val );
- if (nd->val != 0 && nyu->val == 0)
- return NULL; /* oom in val dcopy */
- } else {
- /* copying assumedly unboxed vals */
- nyu->val = nd->val;
- }
-
- /* Copy second val */
- if (dopyW) {
- nyu->wal = dopyW( nd->wal );
- if (nd->wal != 0 && nyu->wal == 0)
- return NULL; /* oom in wal dcopy */
- } else {
- /* copying assumedly unboxed wals */
- nyu->wal = nd->wal;
- }
-
- /* Copy subtrees */
- if (nyu->child[0]) {
- nyu->child[0] = avl_dopy( nyu->child[0],
- dopyK, dopyV, dopyW, alloc_nofail, cc );
- if (! nyu->child[0])
- return NULL;
- }
- if (nyu->child[1]) {
- nyu->child[1] = avl_dopy( nyu->child[1],
- dopyK, dopyV, dopyW, alloc_nofail, cc );
- if (! nyu->child[1])
- return NULL;
- }
-
- return nyu;
-}
-
-/* Initialise a WordFM. */
-static void initFM ( WordFM* fm,
- void* (*alloc_nofail)( HChar*, SizeT ),
- HChar* cc,
- void (*dealloc)(void*),
- Word (*kCmp)(UWord,UWord) )
-{
- fm->root = NULL;
- fm->kCmp = kCmp;
- fm->alloc_nofail = alloc_nofail;
- fm->cc = cc;
- fm->dealloc = dealloc;
- fm->stackTop = 0;
-}
-
-/* --- Public interface functions --- */
-
-/* Allocate and initialise a WordFM. If kCmp is non-NULL, elements in
- the set are ordered according to the ordering specified by kCmp,
- which becomes obvious if you use VG_(initIterFM),
- VG_(initIterAtFM), VG_(nextIterFM), VG_(doneIterFM) to iterate over
- sections of the map, or the whole thing. If kCmp is NULL then the
- ordering used is unsigned word ordering (UWord) on the key
- values. */
-WordFM* HG_(newFM) ( void* (*alloc_nofail)( HChar*, SizeT ),
- HChar* cc,
- void (*dealloc)(void*),
- Word (*kCmp)(UWord,UWord) )
-{
- WordFM* fm = alloc_nofail(cc, sizeof(WordFM));
- tl_assert(fm);
- initFM(fm, alloc_nofail, cc, dealloc, kCmp);
- return fm;
-}
-
-static void avl_free ( AvlNode* nd,
- void(*kFin)(UWord),
- void(*vFin)(UWord),
- void(*wFin)(UWord),
- void(*dealloc)(void*) )
-{
- if (!nd)
- return;
- if (nd->child[0])
- avl_free(nd->child[0], kFin, vFin, wFin, dealloc);
- if (nd->child[1])
- avl_free(nd->child[1], kFin, vFin, wFin, dealloc);
- if (kFin)
- kFin( nd->key );
- if (vFin)
- vFin( nd->val );
- if (wFin)
- wFin( nd->wal );
- VG_(memset)(nd, 0, sizeof(AvlNode));
- dealloc(nd);
-}
-
-/* Free up the FM. If kFin is non-NULL, it is applied to keys before
- the FM is deleted; ditto with vFin and wFin for vals. */
-void HG_(deleteFM) ( WordFM* fm, void(*kFin)(UWord),
- void(*vFin)(UWord),
- void(*wFin)(UWord) )
-{
- void(*dealloc)(void*) = fm->dealloc;
- if (fm->root)
- avl_free( fm->root, kFin, vFin, wFin, dealloc );
- VG_(memset)(fm, 0, sizeof(WordFM) );
- dealloc(fm);
-}
-
-/* Add (k,v,w) to fm. */
-Bool HG_(addToFM) ( WordFM* fm, UWord k, UWord v, UWord w )
-{
- MaybeWord oldV;
- AvlNode* node;
- node = fm->alloc_nofail( fm->cc, sizeof(struct _AvlNode) );
- node->key = k;
- node->val = v;
- node->wal = w;
- oldV.b = False;
- oldV.w = 0;
- avl_insert_wrk( &fm->root, &oldV, node, fm->kCmp );
- //if (oldV.b && fm->vFin)
- // fm->vFin( oldV.w );
- if (oldV.b)
- fm->dealloc(node);
- return oldV.b;
-}
-
-// Delete key from fm, returning associated key and vals if found
-Bool HG_(delFromFM) ( WordFM* fm,
- /*OUT*/UWord* oldK,
- /*OUT*/UWord* oldV, /*OUT*/UWord* oldW,
- UWord key )
-{
- AvlNode* node = avl_find_node( fm->root, key, fm->kCmp );
- if (node) {
- avl_remove_wrk( &fm->root, node, fm->kCmp );
- if (oldK)
- *oldK = node->key;
- if (oldV)
- *oldV = node->val;
- if (oldW)
- *oldW = node->wal;
- fm->dealloc(node);
- return True;
- } else {
- return False;
- }
-}
-
-// Look up in fm, assigning found key & vals at spec'd addresses
-Bool HG_(lookupFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW,
- UWord key )
-{
- AvlNode* node = avl_find_node( fm->root, key, fm->kCmp );
- if (node) {
- if (resK)
- *resK = node->key;
- if (resV)
- *resV = node->val;
- if (resW)
- *resW = node->wal;
- return True;
- } else {
- return False;
- }
-}
-
-UWord HG_(sizeFM) ( WordFM* fm )
-{
- // Hmm, this is a bad way to do this
- return fm->root ? size_avl_nonNull( fm->root ) : 0;
-}
-
-Bool HG_(isEmptyFM)( WordFM* fm )
-{
- return fm->root == NULL;
-}
-
-Bool HG_(anyElementOfFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW )
-{
- if (!fm->root)
- return False;
- if (resK)
- *resK = fm->root->key;
- if (resV)
- *resV = fm->root->val;
- if (resW)
- *resW = fm->root->wal;
- return True;
-}
-
-// set up FM for iteration
-void HG_(initIterFM) ( WordFM* fm )
-{
- tl_assert(fm);
- stackClear(fm);
- if (fm->root)
- stackPush(fm, fm->root, 1);
-}
-
-// set up FM for iteration so that the first key subsequently produced
-// by HG_(nextIterFM) is the smallest key in the map >= start_at.
-// Naturally ">=" is defined by the comparison function supplied to
-// HG_(newFM), as documented above.
-void HG_(initIterAtFM) ( WordFM* fm, UWord start_at )
-{
- Int i;
- AvlNode *n, *t;
- Word cmpresS; /* signed */
- UWord cmpresU; /* unsigned */
-
- tl_assert(fm);
- stackClear(fm);
-
- if (!fm->root)
- return;
-
- n = NULL;
- // We need to do regular search and fill in the stack.
- t = fm->root;
-
- while (True) {
- if (t == NULL) return;
-
- cmpresS
- = fm->kCmp ? /*boxed*/ fm->kCmp( t->key, start_at )
- : /*unboxed*/ cmp_unsigned_Words( t->key, start_at );
-
- if (cmpresS == 0) {
- // We found the exact key -- we are done.
- // The iteration should start with this node.
- stackPush(fm, t, 2);
- // The stack now looks like {2, 2, ... ,2, 2}
- return;
- }
- cmpresU = (UWord)cmpresS;
- cmpresU >>=/*unsigned*/ (8 * sizeof(cmpresU) - 1);
- if (!cmpresU) {
- // Push this node only if we go to the left child.
- stackPush(fm, t, 2);
- }
- t = t->child[cmpresU];
- }
- if (stackPop(fm, &n, &i)) {
- // If we've pushed something to stack and did not find the exact key,
- // we must fix the top element of stack.
- tl_assert(i == 2);
- stackPush(fm, n, 3);
- // the stack looks like {2, 2, ..., 2, 3}
- }
-}
-
-// get next key/vals. Will assert if fm has been modified
-// or looked up in since initIterFM/initIterWithStartFM was called.
-Bool HG_(nextIterFM) ( WordFM* fm,
- /*OUT*/UWord* resK,
- /*OUT*/UWord* resV, /*OUT*/UWord* resW )
-{
- Int i = 0;
- AvlNode* n = NULL;
-
- tl_assert(fm);
-
- // This in-order traversal requires each node to be pushed and popped
- // three times. These could be avoided by updating nodes in-situ on the
- // top of the stack, but the push/pop cost is so small that it's worth
- // keeping this loop in this simpler form.
- while (stackPop(fm, &n, &i)) {
- switch (i) {
- case 1: case_1:
- stackPush(fm, n, 2);
- /* if (n->child[0]) stackPush(fm, n->child[0], 1); */
- if (n->child[0]) { n = n->child[0]; goto case_1; }
- break;
- case 2:
- stackPush(fm, n, 3);
- if (resK) *resK = n->key;
- if (resV) *resV = n->val;
- if (resW) *resW = n->wal;
- return True;
- case 3:
- /* if (n->child[1]) stackPush(fm, n->child[1], 1); */
- if (n->child[1]) { n = n->child[1]; goto case_1; }
- break;
- default:
- tl_assert(0);
- }
- }
-
- // Stack empty, iterator is exhausted, return NULL
- return False;
-}
-
-// clear the I'm iterating flag
-void HG_(doneIterFM) ( WordFM* fm )
-{
-}
-
-WordFM* HG_(dopyFM) ( WordFM* fm,
- UWord(*dopyK)(UWord),
- UWord(*dopyV)(UWord), UWord(*dopyW)(UWord) )
-{
- WordFM* nyu;
-
- /* can't clone the fm whilst iterating on it */
- tl_assert(fm->stackTop == 0);
-
- nyu = fm->alloc_nofail( fm->cc, sizeof(WordFM) );
- tl_assert(nyu);
-
- *nyu = *fm;
-
- fm->stackTop = 0;
- VG_(memset)(fm->nodeStack, 0, sizeof(fm->nodeStack));
- VG_(memset)(fm->numStack, 0, sizeof(fm->numStack));
-
- if (nyu->root) {
- nyu->root = avl_dopy( nyu->root,
- dopyK, dopyV, dopyW,
- fm->alloc_nofail, fm->cc );
- if (! nyu->root)
- return NULL;
- }
-
- return nyu;
-}
-
-//------------------------------------------------------------------//
-//--- end WordFM ---//
-//--- Implementation ---//
-//------------------------------------------------------------------//
-
-//------------------------------------------------------------------//
-//--- WordBag (unboxed words only) ---//
-//--- Implementation ---//
-//------------------------------------------------------------------//
-
-//struct _WordBag {
-// void* (*alloc_nofail)( SizeT );
-// void (*dealloc)(void*);
-// UWord firstWord;
-// UWord firstCount;
-// WordFM* rest;
-// /* When zero, the next call to HG_(nextIterBag) gives
-// (.firstWord, .firstCount). When nonzero, such calls traverse
-// .rest. */
-// UWord iterCount;
-//};
-
-/* Representational invariants. Either:
-
- * bag is empty
- firstWord == firstCount == 0
- rest == NULL
-
- * bag contains just one unique element
- firstCount > 0
- rest == NULL
-
- * bag contains more than one unique element
- firstCount > 0
- rest != NULL
-
- If rest != NULL, then
- (1) firstWord != any .key in rest, and
- (2) all .val in rest > 0
-*/
-
-static inline Bool is_plausible_WordBag ( WordBag* bag ) {
- if (bag->firstWord == 0 && bag->firstCount == 0 && bag->rest == NULL)
- return True;
- if (bag->firstCount > 0 && bag->rest == NULL)
- return True;
- if (bag->firstCount > 0 && bag->rest != NULL)
- /* really should check (1) and (2) now, but that's
- v. expensive */
- return True;
- return False;
-}
-
-void HG_(initBag) ( WordBag* bag,
- void* (*alloc_nofail)( HChar*, SizeT ),
- HChar* cc,
- void (*dealloc)(void*) )
-{
- bag->alloc_nofail = alloc_nofail;
- bag->cc = cc;
- bag->dealloc = dealloc;
- bag->firstWord = 0;
- bag->firstCount = 0;
- bag->rest = NULL;
- bag->iterCount = 0;
-}
-
-void HG_(emptyOutBag) ( WordBag* bag )
-{
- if (bag->rest)
- HG_(deleteFM)( bag->rest, NULL, NULL, NULL );
- /* Don't zero out the alloc and dealloc function pointers, since we
- want to be able to keep on using this bag later, without having
- to call HG_(initBag) again. */
- bag->firstWord = 0;
- bag->firstCount = 0;
- bag->rest = NULL;
- bag->iterCount = 0;
-}
-
-void HG_(addToBag)( WordBag* bag, UWord w )
-{
- tl_assert(is_plausible_WordBag(bag));
- /* case where the bag is completely empty */
- if (bag->firstCount == 0) {
- tl_assert(bag->firstWord == 0 && bag->rest == NULL);
- bag->firstWord = w;
- bag->firstCount = 1;
- return;
- }
- /* there must be at least one element in it */
- tl_assert(bag->firstCount > 0);
- if (bag->firstWord == w) {
- bag->firstCount++;
- return;
- }
- /* it's not the Distinguished Element. Try the rest */
- { UWord key, count;
- if (bag->rest == NULL) {
- bag->rest = HG_(newFM)( bag->alloc_nofail, bag->cc, bag->dealloc,
- NULL/*unboxed uword cmp*/ );
- }
- tl_assert(bag->rest);
- if (HG_(lookupFM)(bag->rest, &key, &count, NULL, w)) {
- tl_assert(key == w);
- tl_assert(count >= 1);
- HG_(addToFM)(bag->rest, w, count+1, (UWord)0/*unused*/ );
- } else {
- HG_(addToFM)(bag->rest, w, 1, (UWord)0/*unused*/ );
- }
- }
-}
-
-UWord HG_(elemBag) ( WordBag* bag, UWord w )
-{
- tl_assert(is_plausible_WordBag(bag));
- if (bag->firstC...
[truncated message content] |