diff options
author | Zack Weinberg <zack@gcc.gnu.org> | 2000-03-08 23:44:29 +0000 |
---|---|---|
committer | Zack Weinberg <zack@gcc.gnu.org> | 2000-03-08 23:44:29 +0000 |
commit | 5194cf089037ca4d68896c4452582b526f603b96 (patch) | |
tree | 6ece5cb52df1c25d061be01b92e2ce0ecdf35f8d /libiberty | |
parent | 8ebb00d547c9267af25015ef737ff393287eb36b (diff) | |
download | gcc-5194cf089037ca4d68896c4452582b526f603b96.zip gcc-5194cf089037ca4d68896c4452582b526f603b96.tar.gz gcc-5194cf089037ca4d68896c4452582b526f603b96.tar.bz2 |
hashtab.c: Remove debugging variables (all_searches, all_collisions, all_expansions).
* 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.
* hashtab.h (hash_table_t): Rename to htab_t.
(struct hash_table): Rename to struct htab. Shorten element
names. Reorder elements by size.
(htab_hash, htab_eq, htab_trav): New typedefs for the callback
function pointers.
(hash_table_entry_t): Discard; just use void * for element
type.
From-SVN: r32437
Diffstat (limited to 'libiberty')
-rw-r--r-- | libiberty/ChangeLog | 122 | ||||
-rw-r--r-- | libiberty/hashtab.c | 354 |
2 files changed, 258 insertions, 218 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index a0b4ed3..c0f59a8 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,7 +1,25 @@ +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. + 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> @@ -80,7 +98,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. @@ -143,7 +161,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> @@ -172,7 +190,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> @@ -190,7 +208,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. @@ -284,7 +302,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 @@ -375,7 +393,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 @@ -409,10 +427,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. @@ -481,7 +499,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 @@ -587,7 +605,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) @@ -640,8 +658,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> @@ -731,9 +749,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. @@ -741,7 +759,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> @@ -1181,8 +1199,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> @@ -1267,24 +1285,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> @@ -1662,7 +1680,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> @@ -1708,7 +1726,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> @@ -1962,7 +1980,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> @@ -2055,17 +2073,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> @@ -2239,7 +2257,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) @@ -2301,7 +2319,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) @@ -2345,13 +2363,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) @@ -2424,27 +2442,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) @@ -2820,7 +2838,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/hashtab.c b/libiberty/hashtab.c index 3f5b303..ea9f9d3 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,20 @@ 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) 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; { - 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; return result; } @@ -122,8 +108,8 @@ 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; { free (htab->entries); free (htab); @@ -132,10 +118,10 @@ 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; { - memset (htab->entries, 0, htab->size * sizeof (hash_table_entry_t)); + memset (htab->entries, 0, htab->size * sizeof (void *)); } /* The following function changes size of memory allocated for the @@ -145,121 +131,166 @@ 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 = htab_find_slot (htab, x, 1); + *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 (htab, element) + htab_t htab; + const void *element; { - hash_table_entry_t *entry_ptr; - hash_table_entry_t *first_deleted_entry_ptr; - unsigned index, hash_value, secondary_hash_value; + unsigned int index, hash, hash2; + size_t size; + + htab->searches++; + size = htab->size; + hash = (*htab->hash_f) (element); + hash2 = 1 + hash % (size - 2); + index = hash % size; - if (htab->size * 3 <= htab->number_of_elements * 4) + 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; +} + +/* 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 (htab, element, insert) + htab_t htab; + const void *element; + int insert; +{ + void **first_deleted_slot; + unsigned int index, hash, hash2; + size_t size; + + if (insert && htab->size * 3 <= htab->n_elements * 4) + htab_expand (htab); + + size = htab->size; + hash = (*htab->hash_f) (element); + 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). */ +/* 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; - entry_ptr = find_hash_table_entry (htab, element, 0); - *entry_ptr = DELETED_ENTRY; - htab->number_of_deleted_elements++; + slot = htab_find_slot (htab, element, 0); + if (*slot == EMPTY_ENTRY) + return; + + *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 (); *slot = DELETED_ENTRY; - htab->number_of_deleted_elements++; + htab->n_deleted++; } /* This function scans over the entire hash table calling @@ -268,24 +299,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) (x, 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 +330,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; } |