merge from gcc

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;
 }