aboutsummaryrefslogtreecommitdiff
path: root/libiberty
diff options
context:
space:
mode:
authorJason Merrill <jason@redhat.com>2000-03-24 21:31:22 +0000
committerJason Merrill <jason@redhat.com>2000-03-24 21:31:22 +0000
commitb4fe2683639c4ac8a5a53576d1c7e020b6b7d05e (patch)
tree277d71524916ab66b2041249e09c6cefa14bc0f6 /libiberty
parenta91f7ea9baf74ec6527944b0b69c23c9c9b238bd (diff)
downloadgdb-b4fe2683639c4ac8a5a53576d1c7e020b6b7d05e.zip
gdb-b4fe2683639c4ac8a5a53576d1c7e020b6b7d05e.tar.gz
gdb-b4fe2683639c4ac8a5a53576d1c7e020b6b7d05e.tar.bz2
merge from gcc
Diffstat (limited to 'libiberty')
-rw-r--r--libiberty/ChangeLog150
-rw-r--r--libiberty/Makefile.in22
-rw-r--r--libiberty/hashtab.c431
3 files changed, 375 insertions, 228 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog
index c59399a..c858409 100644
--- a/libiberty/ChangeLog
+++ b/libiberty/ChangeLog
@@ -1,3 +1,49 @@
+Thu Mar 16 01:33:58 2000 Jeffrey A Law (law@cygnus.com)
+
+ * Makefile.in (partition.o): Depend on config.h
+
+2000-03-14 Bernd Schmidt <bernds@cygnus.co.uk>
+
+ * hashtab.c (find_empty_slot_for_expand): New function.
+ (htab_expand): Use it instead of htab_find_slot.
+ (htab_find_with_hash): Renamed from htab_find; now accepts extra
+ argument HASH.
+ (htab_find_slot_with_hash): Likewise for htab_find_slot.
+ (htab_find): New wrapper function.
+ (htab_find_slot): Likewise.
+ (htab_traverse): Pass slot, not entry, to called function.
+
+2000-03-09 Alex Samuel <samuel@codesourcery.com>
+
+ * Makefile.in (CFILES): Add partition.c.
+ (REQUIRED_OFILES): Add partition.o.
+ (partition.o): New rule.
+ * partition.c: New file.
+
+2000-03-09 Zack Weinberg <zack@wolery.cumb.org>
+
+ * hashtab.c (htab_create): Set del_f.
+ (htab_delete, htab_empty, htab_remove_elt, htab_clear_slot):
+ Use it.
+
+2000-03-08 Zack Weinberg <zack@wolery.cumb.org>
+
+ * hashtab.c: Remove debugging variables (all_searches,
+ all_collisions, all_expansions). Delete
+ all_hash_table_collisions.
+ (create_hash_table, delete_hash_table, empty_hash_table,
+ find_hash_table_entry, remove_element_from_hash_table_entry,
+ clear_hash_table_slot, traverse_hash_table, hash_table_size,
+ hash_table_elements_number, hash_table_collisions): Rename to:
+ htab_create, htab_delete, htab_empty, htab_find_slot,
+ htab_remove_elt, htab_clear_slot, htab_traverse, htab_size,
+ htab_elements, htab_collisions.
+ (htab_find): New function, handles common case where you don't
+ plan to add or delete an entry.
+ (htab_expand): Don't create a whole new table, just a new
+ entry vector.
+ (htab_find_slot): Simplify logic.
+
1999-08-03 Ian Lance Taylor <ian@zembu.com>
* floatformat.c: Add casts to avoid signed/unsigned warnings.
@@ -21,7 +67,7 @@
2000-01-04 Mumit Khan <khan@xraylith.wisc.edu>
* pexecute.c: Conditionally include string.h.
- (fix_argv): Handle embedded whitespace in args for Mingw32.
+ (fix_argv): Handle embedded whitespace in args for Mingw32.
2000-01-04 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
@@ -100,7 +146,7 @@ Tue Nov 2 03:23:13 1999 Philippe De Muyter <phdm@macqel.be>
(demangle_qualified): Use consume_count_with_underscores.
(get_count): Tweak formatting.
(do_type): Use string_append_template_idx.
-
+
1999-10-18 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
* calloc.c: Add a public domain notice.
@@ -163,7 +209,7 @@ Wed Sep 8 20:03:28 1999 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
Tue Sep 7 23:32:18 1999 Linas Vepstas <linas@linas.org>
- * config.table: Add openedition target.
+ * config.table: Add openedition target.
* config/mh-openedition: New file.
Thu Sep 2 01:36:12 1999 Marc Espie <espie@cvs.openbsd.org>
@@ -192,7 +238,7 @@ Thu Sep 2 01:36:12 1999 Marc Espie <espie@cvs.openbsd.org>
(arm_special): Likewise.
(demangle_fund_type): Likewise.
(do_hpacc_template_const_value): Mark parameter `work' with
- ATTRIBUTE_UNUSED.
+ ATTRIBUTE_UNUSED.
(main): Constify variable `valid_symbols'.
Tue Aug 24 02:50:45 1999 Philippe De Muyter <phdm@macqel.be>
@@ -210,7 +256,7 @@ Fri Aug 6 23:32:29 1999 Daniel Jacobowitz <drow@drow.them.org>
1999-07-14 Richard Henderson <rth@cygnus.com>
- * argv.c: Include stdlib.h and string.h instead of
+ * argv.c: Include stdlib.h and string.h instead of
prototyping directly.
* choose-temp.c: Conditionally include string.h.
@@ -304,7 +350,7 @@ Sun Apr 25 01:18:21 1999 Mumit Khan <khan@xraylith.wisc.edu>
1999-04-20 Jim Blandy <jimb@zwingli.cygnus.com>
Fix from Dale Hawkins:
- * cplus-dem.c (mop_up): Set typevec_size to zero, so it'll be
+ * cplus-dem.c (mop_up): Set typevec_size to zero, so it'll be
reallocated properly if we use it again.
* cplus-dem.c (demangle_fund_type): Check for buffer overrun. Be
@@ -395,7 +441,7 @@ Sun Apr 11 23:20:59 1999 Mumit Khan <khan@xraylith.wisc.edu>
* cplus-dem.c (demangle_prefix): Don't grab all the '__' strings
when doing arm or hp style.
(demangle_nested_args): Decr forgetting_types field when done.
-
+
Thu Mar 11 01:22:58 1999 Mumit Khan <khan@xraylith.wisc.edu>
* pexecute.c (__CYGWIN32__): Rename to
@@ -429,10 +475,10 @@ Tue Feb 9 01:12:27 1999 Marc Espie <Marc.Espie@liafa.jussieu.fr>
* configure.in (funcs): Check for and conditionally add mkstemps to
the list of functions libiberty will provide.
* configure: Rebuilt.
-
+
Wed Feb 3 00:01:15 1999 Mumit Khan <khan@xraylith.wisc.edu>
- * clock.c (HZ): Define in terms of (ISO C) CLOCKS_PER_SEC on
+ * clock.c (HZ): Define in terms of (ISO C) CLOCKS_PER_SEC on
platforms that don't have HZ.
* getruntime.c (HZ): Likewise.
@@ -501,7 +547,7 @@ Fri Dec 18 17:50:18 1998 David Taylor <taylor@texas.cygnus.com>
* cplus-dem.c (demangle_arm_pt): remove declaration -- function
doesn't exist.
(do_hpacc_template_literal): remove unused variable `i'.
-
+
Fri Dec 18 16:11:43 EST 1998 Andrew MacLeod <amacleod@cygnus.com>
* cplus-dem.c (demangle_fund_type): Process CV and u codes before
@@ -607,7 +653,7 @@ Mon Nov 23 16:59:49 1998 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
1998-11-16 Benjamin Kosnik <bkoz@haight.constant.com>
- * cplus-dem.c (demangle_fund_type): Add demangling for C9x types.
+ * cplus-dem.c (demangle_fund_type): Add demangling for C9x types.
Thu Nov 19 22:15:50 1998 Jeffrey A Law (law@cygnus.com)
@@ -660,8 +706,8 @@ Sat Nov 7 16:02:10 1998 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
Mon Nov 2 15:05:33 1998 Geoffrey Noer <noer@cygnus.com>
- * configure.in: detect cygwin* instead of cygwin32*
- * configure: regenerate
+ * configure.in: detect cygwin* instead of cygwin32*
+ * configure: regenerate
Mon Nov 2 10:22:01 1998 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
@@ -751,9 +797,9 @@ Thu Oct 15 18:51:12 1998 Kaveh R. Ghazi <ghazi@caip.rutgers.edu>
Tue Oct 13 23:51:51 1998 Jeffrey A Law (law@cygnus.com)
- * mkstemp.c: Check HAVE_SYS_TIME_H before including sys/time.h
- * configure.in (AC_CHECK_HEADERS): Check for sys/time.h too.
- * config.in, configure: Rebuilt.
+ * mkstemp.c: Check HAVE_SYS_TIME_H before including sys/time.h
+ * configure.in (AC_CHECK_HEADERS): Check for sys/time.h too.
+ * config.in, configure: Rebuilt.
* getopt.c: Check HAVE_STRINGS_H before including strings.h.
* configure.in (AC_CHECK_HEADERS): Check for strings.h too.
@@ -761,7 +807,7 @@ Tue Oct 13 23:51:51 1998 Jeffrey A Law (law@cygnus.com)
Mon Oct 12 19:15:59 1998 Geoffrey Noer <noer@cygnus.com>
- * configure.in: in comment, call AC_EXEEXT instead of AM_EXEEXT
+ * configure.in: in comment, call AC_EXEEXT instead of AM_EXEEXT
Sun Oct 11 17:36:06 1998 Michael Tiemann <tiemann@holodeck.cygnus.com>
@@ -1201,8 +1247,8 @@ Fri Feb 6 01:35:17 1998 Manfred Hollstein <manfred@s-direktnet.de>
Thu Feb 5 18:48:56 1998 Geoffrey Noer <noer@cygnus.com>
- * config/mh-cygwin32: remove vasprintf.o from EXTRA_OFILES
- since it gets built automatically
+ * config/mh-cygwin32: remove vasprintf.o from EXTRA_OFILES
+ since it gets built automatically
Sun Feb 1 02:52:32 1998 Mike Stump <mrs@wrs.com>
@@ -1287,24 +1333,24 @@ Mon Sep 29 12:28:41 1997 Ian Lance Taylor <ian@cygnus.com>
Mon Sep 29 12:27:59 1997 Ian Lance Taylor <ian@cygnus.com>
- * pexecute.c: Use spawn if __CYGWIN32__.
+ * pexecute.c: Use spawn if __CYGWIN32__.
1997-08-08 Paul Eggert <eggert@twinsun.com>
- * pexecute.c: Include "config.h" first, as per autoconf manual.
+ * pexecute.c: Include "config.h" first, as per autoconf manual.
Fri Jun 27 15:20:29 1997 Scott Christley <scottc@net-community.com>
- * pexecute.c (fix_argv): New function.
- (pexecute): Win32 but not Cygwin32 needs its arguments fixed.
- Add underscore to cwait function call.
+ * pexecute.c (fix_argv): New function.
+ (pexecute): Win32 but not Cygwin32 needs its arguments fixed.
+ Add underscore to cwait function call.
Sun Sep 28 12:00:52 1997 Mark Mitchell <mmitchell@usa.net>
- * cplus-dem.c (demangle_template): Add new parameter. Handle new
- template-function mangling.
- (consume_count_with_underscores): New function.
- (demangle_signature): Handle new name-mangling scheme.
+ * cplus-dem.c (demangle_template): Add new parameter. Handle new
+ template-function mangling.
+ (consume_count_with_underscores): New function.
+ (demangle_signature): Handle new name-mangling scheme.
Wed Sep 24 00:31:59 1997 Felix Lee <flee@yin.cygnus.com>
@@ -1682,7 +1728,7 @@ Tue Jun 25 23:01:07 1996 Jason Molenda (crash@godzilla.cygnus.co.jp)
Tue Jun 25 22:50:07 1996 Jason Molenda (crash@godzilla.cygnus.co.jp)
- * Makefile.in (datadir): Set to $(prefix)/share.
+ * Makefile.in (datadir): Set to $(prefix)/share.
Thu Jun 20 21:17:52 1996 Ian Lance Taylor <ian@cygnus.com>
@@ -1728,7 +1774,7 @@ Wed Apr 17 11:17:55 1996 Doug Evans <dje@canuck.cygnus.com>
Tue Apr 16 11:27:16 1996 Jeffrey A Law (law@cygnus.com)
- * Makefile.in (lneeded-list): If alloca.o is needed, so is xmalloc.o.
+ * Makefile.in (lneeded-list): If alloca.o is needed, so is xmalloc.o.
Reverts Feb 8, 1995 change.
Mon Apr 15 12:53:26 1996 Doug Evans <dje@canuck.cygnus.com>
@@ -1982,7 +2028,7 @@ Wed Jun 28 19:13:23 1995 Jason Merrill <jason@phydeaux.cygnus.com>
* cplus-dem.c: Update from gcc.
* argv.c, dummy.c: If __STDC__, #include "alloca-conf.h" after
- <stddef.h>.
+ <stddef.h>.
* alloca-norm.h: If __STDC__, declare alloca with its parameter.
Thu Jun 22 18:57:47 1995 Stan Shebs <shebs@andros.cygnus.com>
@@ -2075,17 +2121,17 @@ Mon May 15 19:53:17 1995 Per Bothner <bothner@kalessin.cygnus.com>
Thu May 4 14:36:42 1995 Jason Merrill <jason@phydeaux.cygnus.com>
* cplus-dem.c: Use const instead of CONST. Don't include
- ansidecl.h directly.
+ ansidecl.h directly.
Wed Apr 19 01:30:27 1995 Jason Merrill <jason@phydeaux.cygnus.com>
* cplus-dem.c: Don't include libiberty.h. Do declare xmalloc and
- xrealloc.
+ xrealloc.
(-DMAIN): Don't rely on an externally-defined version number;
- instead, require the version number to be defined as a
- preprocessor macro. Handle the RS/6000 leading dot. Define
- xmalloc, xrealloc and fatal. Don't strip a leading underscore
- if we couldn't demangle the word.
+ instead, require the version number to be defined as a
+ preprocessor macro. Handle the RS/6000 leading dot. Define
+ xmalloc, xrealloc and fatal. Don't strip a leading underscore
+ if we couldn't demangle the word.
Tue Apr 4 13:03:51 1995 Stan Shebs <shebs@andros.cygnus.com>
@@ -2259,7 +2305,7 @@ Fri Aug 19 15:29:12 1994 Kung Hsu (kung@mexican.cygnus.com)
Thu Aug 18 14:37:14 1994 Kung Hsu (kung@mexican.cygnus.com)
* cplus-dem.c (demangle args): Handle ARM repeat encoding where
- the type index is greater than 9.
+ the type index is greater than 9.
Wed Aug 17 16:13:49 1994 Kung Hsu (kung@mexican.cygnus.com)
@@ -2321,7 +2367,7 @@ Thu Jun 16 17:54:01 1994 Ian Lance Taylor (ian@tweedledumb.cygnus.com)
Sun Jun 12 01:37:09 1994 Jason Merrill (jason@deneb.cygnus.com)
* cplus-dem.c (demangle_template): Separate consecutive >'s with a
- space.
+ space.
(gnu_special): Demangle template and qualified names in a vtable name.
Fri May 27 12:27:52 1994 Ken Raeburn (raeburn@cujo.cygnus.com)
@@ -2365,13 +2411,13 @@ Fri May 6 11:01:59 1994 D. V. Henkel-Wallace (gumby@rtl.cygnus.com)
Mon Apr 11 00:54:33 1994 Richard Stallman (rms@mole.gnu.ai.mit.edu)
- * getopt.c [not __GNU_LIBRARY__] [__GCC__] [not __STDC__]:
- Declare strlen to return int. Don't include stddef.h.
+ * getopt.c [not __GNU_LIBRARY__] [__GCC__] [not __STDC__]:
+ Declare strlen to return int. Don't include stddef.h.
Fri Apr 1 00:38:17 1994 Jim Wilson (wilson@mole.gnu.ai.mit.edu)
- * getopt.c: Delete use of IN_GCC to control whether
- stddef.h or gstddef.h is included.
+ * getopt.c: Delete use of IN_GCC to control whether
+ stddef.h or gstddef.h is included.
Thu Apr 14 14:00:56 1994 Kung Hsu (kung@mexican.cygnus.com)
@@ -2444,27 +2490,27 @@ Thu Feb 24 11:51:12 1994 David J. Mackenzie (djm@rtl.cygnus.com)
Thu Feb 10 14:44:16 1994 Richard Stallman (rms@mole.gnu.ai.mit.edu)
- * getopt.c [not __GNU_LIBRARY__] [__GNUC__] [not IN_GCC]:
- Test just __STDC__, not emacs.
+ * getopt.c [not __GNU_LIBRARY__] [__GNUC__] [not IN_GCC]:
+ Test just __STDC__, not emacs.
Wed Feb 9 00:14:00 1994 Richard Stallman (rms@mole.gnu.ai.mit.edu)
- * getopt.c [not __GNU_LIBRARY__] [__GNUC__] [not IN_GCC]
- [emacs] [not __STDC__]: Don't include stddef.h. Don't declare strlen.
+ * getopt.c [not __GNU_LIBRARY__] [__GNUC__] [not IN_GCC]
+ [emacs] [not __STDC__]: Don't include stddef.h. Don't declare strlen.
Fri Dec 24 19:43:00 1993 Noah Friedman (friedman@nutrimat.gnu.ai.mit.edu)
- * getopt.c (_NO_PROTO): Define before config.h is included.
+ * getopt.c (_NO_PROTO): Define before config.h is included.
Mon Sep 20 15:59:03 1993 Roland McGrath (roland@churchy.gnu.ai.mit.edu)
- * getopt.c, getopt1.c [emacs || CONFIG_BROKETS]: Include
+ * getopt.c, getopt1.c [emacs || CONFIG_BROKETS]: Include
<config.h> only under these, else "config.h".
Thu Aug 12 18:16:49 1993 Roland McGrath (roland@churchy.gnu.ai.mit.edu)
- * getopt.c, getopt1.c [HAVE_CONFIG_H]: Include
- <config.h> instead of "config.h".
+ * getopt.c, getopt1.c [HAVE_CONFIG_H]: Include
+ <config.h> instead of "config.h".
Sun Feb 20 17:17:01 1994 Ian Lance Taylor (ian@lisa.cygnus.com)
@@ -2840,7 +2886,7 @@ Fri May 21 09:53:57 1993 Jim Kingdon (kingdon@lioth.cygnus.com)
Tue May 18 17:12:10 1993 Fred Fish (fnf@cygnus.com)
- (merge changes from dlong@cse.ucsc.edu)
+ (merge changes from dlong@cse.ucsc.edu)
* cplus-dem.c (consume_count): Simplify.
* cplus-dem.c (arm_pt, demangle_class_name): New functions.
* cplus-dem.c (various): Calls to arm_pt, demangle_class_name.
diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in
index cc25df5..9aa57f0 100644
--- a/libiberty/Makefile.in
+++ b/libiberty/Makefile.in
@@ -123,21 +123,22 @@ HFILES = alloca-conf.h
# NOTE: If you add new files to the library, add them to this list
# (alphabetical), and add them to REQUIRED_OFILES or funcs in
# configure.in.
-CFILES = asprintf.c alloca.c argv.c atexit.c basename.c bcmp.c bcopy.c \
+CFILES = asprintf.c alloca.c argv.c atexit.c basename.c bcmp.c bcopy.c \
bzero.c calloc.c choose-temp.c clock.c concat.c cplus-dem.c fdmatch.c \
- fnmatch.c getcwd.c getpwd.c getopt.c getopt1.c getpagesize.c \
- getruntime.c floatformat.c hashtab.c hex.c index.c insque.c memchr.c \
- memcmp.c memcpy.c memmove.c memset.c mkstemps.c objalloc.c obstack.c \
- pexecute.c putenv.c random.c rename.c rindex.c setenv.c sigsetmask.c \
- spaces.c splay-tree.c strcasecmp.c strncasecmp.c strchr.c strdup.c \
- strerror.c strrchr.c strsignal.c strstr.c strtod.c strtol.c strtoul.c \
- tmpnam.c vasprintf.c vfork.c vfprintf.c vprintf.c vsprintf.c \
- waitpid.c xatexit.c xexit.c xmalloc.c xmemdup.c xstrdup.c xstrerror.c
+ fnmatch.c getcwd.c getpwd.c getopt.c getopt1.c getpagesize.c \
+ getruntime.c floatformat.c hashtab.c hex.c index.c insque.c memchr.c \
+ memcmp.c memcpy.c memmove.c memset.c mkstemps.c objalloc.c obstack.c \
+ partition.c pexecute.c putenv.c random.c rename.c rindex.c \
+ setenv.c sigsetmask.c spaces.c splay-tree.c strcasecmp.c \
+ strncasecmp.c strchr.c strdup.c strerror.c strrchr.c \
+ strsignal.c strstr.c strtod.c strtol.c strtoul.c tmpnam.c \
+ vasprintf.c vfork.c vfprintf.c vprintf.c vsprintf.c waitpid.c \
+ xatexit.c xexit.c xmalloc.c xmemdup.c xstrdup.c xstrerror.c
# These are always included in the library.
REQUIRED_OFILES = argv.o choose-temp.o concat.o cplus-dem.o \
fdmatch.o fnmatch.o getopt.o getopt1.o getpwd.o getruntime.o hashtab.o \
- hex.o floatformat.o objalloc.o obstack.o pexecute.o spaces.o \
+ hex.o floatformat.o objalloc.o obstack.o partition.o pexecute.o spaces.o \
splay-tree.o strerror.o strsignal.o xatexit.o xexit.o xmalloc.o \
xmemdup.o xstrdup.o xstrerror.o
@@ -271,6 +272,7 @@ floatformat.o: $(INCDIR)/floatformat.h
mkstemps.o: config.h
objalloc.o: $(INCDIR)/objalloc.h
obstack.o: config.h $(INCDIR)/obstack.h
+partition.o: config.h $(INCDIR)/partition.h
pexecute.o: config.h $(INCDIR)/libiberty.h
setenv.o: config.h
spaces.o: $(INCDIR)/libiberty.h
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 3f5b303..16c5d3e 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -46,25 +46,9 @@ Boston, MA 02111-1307, USA. */
#include "libiberty.h"
#include "hashtab.h"
-/* The following variable is used for debugging. Its value is number
- of all calls of `find_hash_table_entry' for all hash tables. */
-
-static int all_searches = 0;
-
-/* The following variable is used for debugging. Its value is number
- of collisions fixed for time of work with all hash tables. */
-
-static int all_collisions = 0;
-
-/* The following variable is used for debugging. Its value is number
- of all table expansions fixed for time of work with all hash
- tables. */
-
-static int all_expansions = 0;
-
/* This macro defines reserved value for empty table entry. */
-#define EMPTY_ENTRY NULL
+#define EMPTY_ENTRY ((void *) 0)
/* This macro defines reserved value for table entry which contained
a deleted element. */
@@ -75,19 +59,27 @@ static int all_expansions = 0;
greater than given source number. */
static unsigned long
-higher_prime_number (number)
- unsigned long number;
+higher_prime_number (n)
+ unsigned long n;
{
unsigned long i;
- for (number = (number / 2) * 2 + 3;; number += 2)
+ n |= 0x01; /* Force N to be odd. */
+ if (n < 9)
+ return n; /* All odd numbers < 9 are prime. */
+
+ next:
+ n += 2;
+ i = 3;
+ do
{
- for (i = 3; i * i <= number; i += 2)
- if (number % i == 0)
- break;
- if (i * i > number)
- return number;
+ if (n % i == 0)
+ goto next;
+ i += 2;
}
+ while ((i * i) <= n);
+
+ return n;
}
/* This function creates table with length slightly longer than given
@@ -95,26 +87,22 @@ higher_prime_number (number)
hash table entries are EMPTY_ENTRY). The function returns the
created hash table. */
-hash_table_t
-create_hash_table (size, hash_function, eq_function)
+htab_t
+htab_create (size, hash_f, eq_f, del_f)
size_t size;
- unsigned (*hash_function) PARAMS ((hash_table_entry_t));
- int (*eq_function) PARAMS ((hash_table_entry_t, hash_table_entry_t));
+ htab_hash hash_f;
+ htab_eq eq_f;
+ htab_del del_f;
{
- hash_table_t result;
+ htab_t result;
size = higher_prime_number (size);
- result = (hash_table_t) xmalloc (sizeof (*result));
- result->entries
- = (hash_table_entry_t *) xmalloc (size * sizeof (hash_table_entry_t));
+ result = (htab_t) xcalloc (1, sizeof (struct htab));
+ result->entries = (void **) xcalloc (size, sizeof (void *));
result->size = size;
- result->hash_function = hash_function;
- result->eq_function = eq_function;
- result->number_of_elements = 0;
- result->number_of_deleted_elements = 0;
- result->searches = 0;
- result->collisions = 0;
- memset (result->entries, 0, size * sizeof (hash_table_entry_t));
+ result->hash_f = hash_f;
+ result->eq_f = eq_f;
+ result->del_f = del_f;
return result;
}
@@ -122,9 +110,18 @@ create_hash_table (size, hash_function, eq_function)
Naturally the hash table must already exist. */
void
-delete_hash_table (htab)
- hash_table_t htab;
+htab_delete (htab)
+ htab_t htab;
{
+ int i;
+ if (htab->del_f)
+ for (i = htab->size - 1; i >= 0; i--)
+ {
+ if (htab->entries[i] != EMPTY_ENTRY
+ && htab->entries[i] != DELETED_ENTRY)
+ (*htab->del_f) (htab->entries[i]);
+ }
+
free (htab->entries);
free (htab);
}
@@ -132,10 +129,49 @@ delete_hash_table (htab)
/* This function clears all entries in the given hash table. */
void
-empty_hash_table (htab)
- hash_table_t htab;
+htab_empty (htab)
+ htab_t htab;
+{
+ int i;
+ if (htab->del_f)
+ for (i = htab->size - 1; i >= 0; i--)
+ {
+ if (htab->entries[i] != EMPTY_ENTRY
+ && htab->entries[i] != DELETED_ENTRY)
+ (*htab->del_f) (htab->entries[i]);
+ }
+
+ memset (htab->entries, 0, htab->size * sizeof (void *));
+}
+
+/* Similar to htab_find_slot, but without several unwanted side effects:
+ - Does not call htab->eq_f when it finds an existing entry.
+ - Does not change the count of elements/searches/collisions in the
+ hash table.
+ This function also assumes there are no deleted entries in the table.
+ HASH is the hash value for the element to be inserted. */
+static void **
+find_empty_slot_for_expand (htab, hash)
+ htab_t htab;
+ unsigned int hash;
{
- memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t));
+ size_t size = htab->size;
+ unsigned int hash2 = 1 + hash % (size - 2);
+ unsigned int index = hash % size;
+
+ for (;;)
+ {
+ void **slot = htab->entries + index;
+ if (*slot == EMPTY_ENTRY)
+ return slot;
+
+ if (*slot == DELETED_ENTRY)
+ abort ();
+
+ index += hash2;
+ if (index >= size)
+ index -= size;
+ }
}
/* The following function changes size of memory allocated for the
@@ -145,121 +181,193 @@ empty_hash_table (htab)
table entries is changed. */
static void
-expand_hash_table (htab)
- hash_table_t htab;
+htab_expand (htab)
+ htab_t htab;
{
- hash_table_t new_htab;
- hash_table_entry_t *entry_ptr;
- hash_table_entry_t *new_entry_ptr;
-
- new_htab = create_hash_table (htab->number_of_elements * 2,
- htab->hash_function, htab->eq_function);
- for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
- entry_ptr++)
- if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
- {
- new_entry_ptr = find_hash_table_entry (new_htab, *entry_ptr, 1);
- *new_entry_ptr = (*entry_ptr);
- }
- free (htab->entries);
- *htab = (*new_htab);
- free (new_htab);
+ void **oentries;
+ void **olimit;
+ void **p;
+
+ oentries = htab->entries;
+ olimit = oentries + htab->size;
+
+ htab->size = higher_prime_number (htab->size * 2);
+ htab->entries = xcalloc (htab->size, sizeof (void **));
+
+ htab->n_elements -= htab->n_deleted;
+ htab->n_deleted = 0;
+
+ p = oentries;
+ do
+ {
+ void *x = *p;
+ if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
+ {
+ void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+ *q = x;
+ }
+ p++;
+ }
+ while (p < olimit);
+ free (oentries);
}
-/* This function searches for hash table entry which contains element
- equal to given value or empty entry in which given value can be
- placed (if the element with given value does not exist in the
- table). The function works in two regimes. The first regime is
- used only for search. The second is used for search and
- reservation empty entry for given value. The table is expanded if
- occupancy (taking into accout also deleted elements) is more than
- 75%. Naturally the hash table must already exist. If reservation
- flag is TRUE then the element with given value should be inserted
- into the table entry before another call of
- `find_hash_table_entry'. */
-
-hash_table_entry_t *
-find_hash_table_entry (htab, element, reserve)
- hash_table_t htab;
- hash_table_entry_t element;
- int reserve;
+/* This function searches for a hash table entry equal to the given
+ element. It cannot be used to insert or delete an element. */
+
+void *
+htab_find_with_hash (htab, element, hash)
+ htab_t htab;
+ const void *element;
+ unsigned int hash;
{
- hash_table_entry_t *entry_ptr;
- hash_table_entry_t *first_deleted_entry_ptr;
- unsigned index, hash_value, secondary_hash_value;
+ unsigned int index, hash2;
+ size_t size;
- if (htab->size * 3 <= htab->number_of_elements * 4)
+ htab->searches++;
+ size = htab->size;
+ hash2 = 1 + hash % (size - 2);
+ index = hash % size;
+
+ for (;;)
{
- all_expansions++;
- expand_hash_table (htab);
+ void *entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY)
+ return NULL;
+ else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))
+ return entry;
+
+ htab->collisions++;
+ index += hash2;
+ if (index >= size)
+ index -= size;
}
- hash_value = (*htab->hash_function) (element);
- secondary_hash_value = 1 + hash_value % (htab->size - 2);
- index = hash_value % htab->size;
+}
+
+/* Like htab_find_slot_with_hash, but compute the hash value from the
+ element. */
+void *
+htab_find (htab, element)
+ htab_t htab;
+ const void *element;
+{
+ return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
+}
+
+/* This function searches for a hash table slot containing an entry
+ equal to the given element. To delete an entry, call this with
+ INSERT = 0, then call htab_clear_slot on the slot returned (possibly
+ after doing some checks). To insert an entry, call this with
+ INSERT = 1, then write the value you want into the returned slot. */
+
+void **
+htab_find_slot_with_hash (htab, element, hash, insert)
+ htab_t htab;
+ const void *element;
+ unsigned int hash;
+ int insert;
+{
+ void **first_deleted_slot;
+ unsigned int index, hash2;
+ size_t size;
+
+ if (insert && htab->size * 3 <= htab->n_elements * 4)
+ htab_expand (htab);
+
+ size = htab->size;
+ hash2 = 1 + hash % (size - 2);
+ index = hash % size;
+
htab->searches++;
- all_searches++;
- first_deleted_entry_ptr = NULL;
- for (;;htab->collisions++, all_collisions++)
+ first_deleted_slot = NULL;
+
+ for (;;)
{
- entry_ptr = htab->entries + index;
- if (*entry_ptr == EMPTY_ENTRY)
- {
- if (reserve)
+ void *entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY)
+ {
+ if (!insert)
+ return NULL;
+
+ htab->n_elements++;
+
+ if (first_deleted_slot)
{
- htab->number_of_elements++;
- if (first_deleted_entry_ptr != NULL)
- {
- entry_ptr = first_deleted_entry_ptr;
- *entry_ptr = EMPTY_ENTRY;
- }
+ *first_deleted_slot = EMPTY_ENTRY;
+ return first_deleted_slot;
}
- break;
- }
- else if (*entry_ptr != DELETED_ENTRY)
- {
- if ((*htab->eq_function) (*entry_ptr, element))
- break;
- }
- else if (first_deleted_entry_ptr == NULL)
- first_deleted_entry_ptr = entry_ptr;
- index += secondary_hash_value;
- if (index >= htab->size)
- index -= htab->size;
+
+ return &htab->entries[index];
+ }
+
+ if (entry == DELETED_ENTRY)
+ {
+ if (!first_deleted_slot)
+ first_deleted_slot = &htab->entries[index];
+ }
+ else
+ {
+ if ((*htab->eq_f) (entry, element))
+ return &htab->entries[index];
+ }
+
+ htab->collisions++;
+ index += hash2;
+ if (index >= size)
+ index -= size;
}
- return entry_ptr;
}
-/* This function deletes element with given value from hash table.
- The hash table entry value will be `DELETED_ENTRY' after the
- function call. Naturally the hash table must already exist. Hash
- table entry for given value should be not empty (or deleted). */
+/* Like htab_find_slot_with_hash, but compute the hash value from the
+ element. */
+void **
+htab_find_slot (htab, element, insert)
+ htab_t htab;
+ const void *element;
+ int insert;
+{
+ return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
+ insert);
+}
+
+/* This function deletes an element with the given value from hash
+ table. If there is no matching element in the hash table, this
+ function does nothing. */
void
-remove_element_from_hash_table_entry (htab, element)
- hash_table_t htab;
- hash_table_entry_t element;
+htab_remove_elt (htab, element)
+ htab_t htab;
+ void *element;
{
- hash_table_entry_t *entry_ptr;
+ void **slot;
+
+ slot = htab_find_slot (htab, element, 0);
+ if (*slot == EMPTY_ENTRY)
+ return;
+
+ if (htab->del_f)
+ (*htab->del_f) (*slot);
- entry_ptr = find_hash_table_entry (htab, element, 0);
- *entry_ptr = DELETED_ENTRY;
- htab->number_of_deleted_elements++;
+ *slot = DELETED_ENTRY;
+ htab->n_deleted++;
}
-/* This function clears a specified slot in a hash table.
- It is useful when you've already done the lookup and don't want to
- do it again. */
+/* This function clears a specified slot in a hash table. It is
+ useful when you've already done the lookup and don't want to do it
+ again. */
void
-clear_hash_table_slot (htab, slot)
- hash_table_t htab;
- hash_table_entry_t *slot;
+htab_clear_slot (htab, slot)
+ htab_t htab;
+ void **slot;
{
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
abort ();
+ if (htab->del_f)
+ (*htab->del_f) (*slot);
*slot = DELETED_ENTRY;
- htab->number_of_deleted_elements++;
+ htab->n_deleted++;
}
/* This function scans over the entire hash table calling
@@ -268,24 +376,29 @@ clear_hash_table_slot (htab, slot)
argument. */
void
-traverse_hash_table (htab, callback, info)
- hash_table_t htab;
- int (*callback) PARAMS ((hash_table_entry_t, void *));
+htab_traverse (htab, callback, info)
+ htab_t htab;
+ htab_trav callback;
void *info;
{
- hash_table_entry_t *entry_ptr;
- for (entry_ptr = htab->entries; entry_ptr < htab->entries + htab->size;
- entry_ptr++)
- if (*entry_ptr != EMPTY_ENTRY && *entry_ptr != DELETED_ENTRY)
- if (!callback (*entry_ptr, info))
- break;
+ void **slot, **limit;
+ slot = htab->entries;
+ limit = slot + htab->size;
+ do
+ {
+ void *x = *slot;
+ if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
+ if (!(*callback) (slot, info))
+ break;
+ }
+ while (++slot < limit);
}
/* The following function returns current size of given hash table. */
size_t
-hash_table_size (htab)
- hash_table_t htab;
+htab_size (htab)
+ htab_t htab;
{
return htab->size;
}
@@ -294,37 +407,23 @@ hash_table_size (htab)
hash table. */
size_t
-hash_table_elements_number (htab)
- hash_table_t htab;
+htab_elements (htab)
+ htab_t htab;
{
- return htab->number_of_elements - htab->number_of_deleted_elements;
+ return htab->n_elements - htab->n_deleted;
}
/* The following function returns number of percents of fixed
collisions during all work with given hash table. */
-int
-hash_table_collisions (htab)
- hash_table_t htab;
+double
+htab_collisions (htab)
+ htab_t htab;
{
int searches;
searches = htab->searches;
if (searches == 0)
- searches++;
- return htab->collisions * 100 / searches;
-}
-
-/* The following function returns number of percents of fixed
- collisions during all work with all hash tables. */
-
-int
-all_hash_table_collisions ()
-{
- int searches;
-
- searches = all_searches;
- if (searches == 0)
- searches++;
- return all_collisions * 100 / searches;
+ return 0.0;
+ return (double)htab->collisions / (double)searches;
}