Mercurial > hg > xemacs-beta
annotate src/hash.c @ 2367:ecf1ebac70d8
[xemacs-hg @ 2004-11-04 23:05:23 by ben]
commit mega-patch
configure.in: Turn off -Winline and -Wchar-subscripts.
Use the right set of cflags when compiling modules.
Rewrite ldap configuration to separate the inclusion of lber
(needed in recent Cygwin) from the basic checks for the
needed libraries.
add a function for MAKE_JUNK_C; initially code was added to
generate xemacs.def using this, but it will need to be rewritten.
add an rm -f for junk.c to avoid weird Cygwin bug with cp -f onto
an existing file.
Sort list of auto-detected functions and eliminate unused checks for
stpcpy, setlocale and getwd.
Add autodetection of Cygwin scanf problems
BETA: Rewrite section on configure to indicate what flags are important
and what not.
digest-doc.c, make-dump-id.c, profile.c, sorted-doc.c: Add proper decls for main().
make-msgfile.c: Document that this is old junk.
Move proposal to text.c.
make-msgfile.lex: Move proposal to text.c.
make-mswin-unicode.pl: Convert error-generating code so that the entire message will
be seen as a single unrecognized token.
mule/mule-ccl.el: Update docs.
lispref/mule.texi: Update CCL docs.
ldap/eldap.c: Mule-ize.
Use EXTERNAL_LIST_LOOP_2 instead of deleted EXTERNAL_LIST_LOOP.
* XEmacs 21.5.18 "chestnut" is released.
---------------------------------------------------------------
MULE-RELATED WORK:
---------------------------------------------------------------
---------------------------
byte-char conversion
---------------------------
buffer.c, buffer.h, insdel.c, text.c: Port FSF algorithm for byte-char conversion, replacing broken
previous version. Track the char position of the gap. Add
functions to do char-byte conversion downwards as well as upwards.
Move comments about algorithm workings to internals manual.
---------------------------
work on types
---------------------------
alloc.c, console-x-impl.h, dump-data.c, dump-data.h, dumper.c, dialog-msw.c, dired-msw.c, doc.c, editfns.c, esd.c, event-gtk.h, event-msw.c, events.c, file-coding.c, file-coding.h, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-shared.c, glyphs-x.c, glyphs.c, glyphs.h, gui.c, hpplay.c, imgproc.c, intl-win32.c, lrecord.h, lstream.c, keymap.c, lisp.h, libsst.c, linuxplay.c, miscplay.c, miscplay.h, mule-coding.c, nas.c, nt.c, ntheap.c, ntplay.c, objects-msw.c, objects-tty.c, objects-x.c, print.c, process-nt.c, process.c, redisplay.h, select-common.h, select-gtk.c, select-x.c, sgiplay.c, sound.c, sound.h, sunplay.c, sysfile.h, sysdep.c, syswindows.h, text.c, unexnt.c, win32.c, xgccache.c: Further work on types. This creates a full set of types for all
the basic semantics of `char' that I have so far identified, so that
its semantics can always be identified for the purposes of proper
Mule-safe code, and the raw use of `char' always avoided.
(1) More type renaming, for consistency of naming.
Char_ASCII -> Ascbyte
UChar_ASCII -> UAscbyte
Char_Binary -> CBinbyte
UChar_Binary -> Binbyte
SChar_Binary -> SBinbyte
(2) Introduce Rawbyte, CRawbyte, Boolbyte, Chbyte, UChbyte, and
Bitbyte and use them.
(3) New types Itext, Wexttext and Textcount for separating out
the concepts of bytes and textual units (different under UTF-16
and UTF-32, which are potential internal encodings).
(4) qxestr*_c -> qxestr*_ascii.
lisp.h: New; goes with other qxe() functions. #### Maybe goes in a
different section.
lisp.h: Group generic int-type defs together with EMACS_INT defs.
lisp.h: * lisp.h (WEXTTEXT_IS_WIDE)
New defns.
lisp.h: New type to replace places where int occurs as a boolean.
It's signed because occasionally people may want to use -1 as
an error value, and because unsigned ints are viral -- see comments
in the internals manual against using them.
dynarr.c: int -> Bytecount.
---------------------------
Mule-izing
---------------------------
device-x.c: Partially Mule-ize.
dumper.c, dumper.h: Mule-ize. Use Rawbyte. Use stderr_out not printf. Use wext_*().
sysdep.c, syswindows.h, text.c: New Wexttext API for manipulation of external text that may be
Unicode (e.g. startup code under Windows).
emacs.c: Mule-ize. Properly deal with argv in external encoding.
Use wext_*() and Wexttext. Use Rawbyte.
#if 0 some old junk on SCO that is unlikely to be correct.
Rewrite allocation code in run-temacs.
emacs.c, symsinit.h, win32.c: Rename win32 init function and call it even earlier, to
initialize mswindows_9x_p even earlier, for use in startup code
(XEUNICODE_P).
process.c: Use _wenviron not environ under Windows, to get Unicode environment
variables.
event-Xt.c: Mule-ize drag-n-drop related stuff.
dragdrop.c, dragdrop.h, frame-x.c: Mule-ize.
text.h: Add some more stand-in defines for particular kinds of conversion;
use in Mule-ization work in frame-x.c etc.
---------------------------
Freshening
---------------------------
intl-auto-encap-win32.c, intl-auto-encap-win32.h: Regenerate.
---------------------------
Unicode-work
---------------------------
intl-win32.c, syswindows.h: Factor out common options to MultiByteToWideChar and
WideCharToMultiByte. Add convert_unicode_to_multibyte_malloc()
and convert_unicode_to_multibyte_dynarr() and use. Add stuff for
alloca() conversion of multibyte/unicode.
alloc.c: Use dfc_external_data_len() in case of unicode coding system.
alloc.c, mule-charset.c: Don't zero out and reinit charset Unicode tables. This fucks up
dump-time loading. Anyway, either we load them at dump time or
run time, never both.
unicode.c: Dump the blank tables as well.
---------------------------------------------------------------
DOCUMENTATION, MOSTLY MULE-RELATED:
---------------------------------------------------------------
EmacsFrame.c, emodules.c, event-Xt.c, fileio.c, input-method-xlib.c, mule-wnnfns.c, redisplay-gtk.c, redisplay-tty.c, redisplay-x.c, regex.c, sysdep.c: Add comment about Mule work needed.
text.h: Add more documentation describing why DFC routines were not written
to return their value. Add some other DFC documentation.
console-msw.c, console-msw.h: Add pointer to docs in win32.c.
emacs.c: Add comments on sources of doc info.
text.c, charset.h, unicode.c, intl-win32.c, intl-encap-win32.c, text.h, file-coding.c, mule-coding.c: Collect background comments and related to text matters and
internationalization, and proposals for work to be done, in text.c
or Internals manual, stuff related to specific textual API's in
text.h, and stuff related to internal implementation of Unicode
conversion in unicode.c. Put lots of pointers to the comments to
make them easier to find.
s/mingw32.h, s/win32-common.h, s/win32-native.h, s/windowsnt.h, win32.c: Add bunches of new documentation on the different kinds of
builds and environments under Windows and how they work.
Collect this info in win32.c. Add pointers to these docs in
the relevant s/* files.
emacs.c: Document places with long comments.
Remove comment about exiting, move to internals manual, put
in pointer.
event-stream.c: Move docs about event queues and focus to internals manual, put
in pointer.
events.h: Move docs about event stream callbacks to internals manual, put
in pointer.
profile.c, redisplay.c, signal.c: Move documentation to the Internals manual.
process-nt.c: Add pointer to comment in win32-native.el.
lisp.h: Add comments about some comment conventions.
lisp.h: Add comment about the second argument.
device-msw.c, redisplay-msw.c: @@#### comments are out-of-date.
---------------------------------------------------------------
PDUMP WORK (MOTIVATED BY UNICODE CHANGES)
---------------------------------------------------------------
alloc.c, buffer.c, bytecode.c, console-impl.h, console.c, device.c, dumper.c, lrecord.h, elhash.c, emodules.h, events.c, extents.c, frame.c, glyphs.c, glyphs.h, mule-charset.c, mule-coding.c, objects.c, profile.c, rangetab.c, redisplay.c, specifier.c, specifier.h, window.c, lstream.c, file-coding.h, file-coding.c: PDUMP:
Properly implement dump_add_root_block(), which never worked before,
and is necessary for dumping Unicode tables.
Pdump name changes for accuracy:
XD_STRUCT_PTR -> XD_BLOCK_PTR.
XD_STRUCT_ARRAY -> XD_BLOCK_ARRAY.
XD_C_STRING -> XD_ASCII_STRING.
*_structure_* -> *_block_*.
lrecord.h: some comments added about
dump_add_root_block() vs dump_add_root_block_ptr().
extents.c: remove incorrect comment about pdump problems with gap array.
---------------------------------------------------------------
ALLOCATION
---------------------------------------------------------------
abbrev.c, alloc.c, bytecode.c, casefiddle.c, device-msw.c, device-x.c, dired-msw.c, doc.c, doprnt.c, dragdrop.c, editfns.c, emodules.c, file-coding.c, fileio.c, filelock.c, fns.c, glyphs-eimage.c, glyphs-gtk.c, glyphs-msw.c, glyphs-x.c, gui-msw.c, gui-x.c, imgproc.c, intl-win32.c, lread.c, menubar-gtk.c, menubar.c, nt.c, objects-msw.c, objects-x.c, print.c, process-nt.c, process-unix.c, process.c, realpath.c, redisplay.c, search.c, select-common.c, symbols.c, sysdep.c, syswindows.h, text.c, text.h, ui-byhand.c: New macros {alloca,xnew}_{itext,{i,ext,raw,bin,asc}bytes} for
more convenient allocation of these commonly requested items.
Modify functions to use alloca_ibytes, alloca_array, alloca_extbytes,
xnew_ibytes, etc. also XREALLOC_ARRAY, xnew.
alloc.c: Rewrite the allocation functions to factor out repeated code.
Add assertions for freeing dumped data.
lisp.h: Moved down and consolidated with other allocation stuff.
lisp.h, dynarr.c: New functions for allocation that's very efficient when mostly in
LIFO order.
lisp.h, text.c, text.h: Factor out some stuff for general use by alloca()-conversion funs.
text.h, lisp.h: Fill out convenience routines for allocating various kinds of
bytes and put them in lisp.h. Use them in place of xmalloc(),
ALLOCA().
text.h: Fill out the convenience functions so the _MALLOC() kinds match
the alloca() kinds.
---------------------------------------------------------------
ERROR-CHECKING
---------------------------------------------------------------
text.h: Create ASSERT_ASCTEXT_ASCII() and ASSERT_ASCTEXT_ASCII_LEN()
from similar Eistring checkers and change the Eistring checkers to
use them instead.
---------------------------------------------------------------
MACROS IN LISP.H
---------------------------------------------------------------
lisp.h: Redo GCPRO declarations. Create a "base" set of functions that can
be used to generate any kind of gcpro sets -- regular, ngcpro,
nngcpro, private ones used in GC_EXTERNAL_LIST_LOOP_2.
buffer.c, callint.c, chartab.c, console-msw.c, device-x.c, dialog-msw.c, dired.c, extents.c, ui-gtk.c, rangetab.c, nt.c, mule-coding.c, minibuf.c, menubar-msw.c, menubar.c, menubar-gtk.c, lread.c, lisp.h, gutter.c, glyphs.c, glyphs-widget.c, fns.c, fileio.c, file-coding.c, specifier.c: Eliminate EXTERNAL_LIST_LOOP, which does not check for circularities.
Use EXTERNAL_LIST_LOOP_2 instead or EXTERNAL_LIST_LOOP_3
or EXTERNAL_PROPERTY_LIST_LOOP_3 or GC_EXTERNAL_LIST_LOOP_2
(new macro). Removed/redid comments on EXTERNAL_LIST_LOOP.
---------------------------------------------------------------
SPACING FIXES
---------------------------------------------------------------
callint.c, hftctl.c, number-gmp.c, process-unix.c: Spacing fixes.
---------------------------------------------------------------
FIX FOR GEOMETRY PROBLEM IN FIRST FRAME
---------------------------------------------------------------
unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by
release 1.5.12 of Cygwin].
toolbar.c: bug fix for problem of initial frame being 77 chars wide on Windows.
will be overridden by my other ws.
---------------------------------------------------------------
FIX FOR LEAKING PROCESS HANDLES:
---------------------------------------------------------------
process-nt.c: Fixes for leaking handles. Inspired by work done by Adrian Aichner
<adrian@xemacs.org>.
---------------------------------------------------------------
FIX FOR CYGWIN BUG (Unicode-related):
---------------------------------------------------------------
unicode.c: Add workaround for newlib bug in sscanf() [should be fixed by
release 1.5.12 of Cygwin].
---------------------------------------------------------------
WARNING FIXES:
---------------------------------------------------------------
console-stream.c: `reinit' is unused.
compiler.h, event-msw.c, frame-msw.c, intl-encap-win32.c, text.h: Add stuff to deal with ANSI-aliasing warnings I got.
regex.c: Gather includes together to avoid warning.
---------------------------------------------------------------
CHANGES TO INITIALIZATION ROUTINES:
---------------------------------------------------------------
buffer.c, emacs.c, console.c, debug.c, device-x.c, device.c, dragdrop.c, emodules.c, eval.c, event-Xt.c, event-gtk.c, event-msw.c, event-stream.c, event-tty.c, events.c, extents.c, faces.c, file-coding.c, fileio.c, font-lock.c, frame-msw.c, glyphs-widget.c, glyphs.c, gui-x.c, insdel.c, lread.c, lstream.c, menubar-gtk.c, menubar-x.c, minibuf.c, mule-wnnfns.c, objects-msw.c, objects.c, print.c, scrollbar-x.c, search.c, select-x.c, text.c, undo.c, unicode.c, window.c, symsinit.h: Call reinit_*() functions directly from emacs.c, for clarity.
Factor out some redundant init code. Move disallowed stuff
that had crept into vars_of_glyphs() into complex_vars_of_glyphs().
Call init_eval_semi_early() from eval.c not in the middle of
vars_of_() in emacs.c since there should be no order dependency
in the latter calls.
---------------------------------------------------------------
ARMAGEDDON:
---------------------------------------------------------------
alloc.c, emacs.c, lisp.h, print.c: Rename inhibit_non_essential_printing_operations to
inhibit_non_essential_conversion_operations.
text.c: Assert on !inhibit_non_essential_conversion_operations.
console-msw.c, print.c: Don't do conversion in SetConsoleTitle or FindWindow to avoid
problems during armageddon. Put #errors for NON_ASCII_INTERNAL_FORMAT
in places where problems would arise.
---------------------------------------------------------------
CHANGES TO THE BUILD PROCEDURE:
---------------------------------------------------------------
config.h.in, s/cxux.h, s/usg5-4-2.h, m/powerpc.h: Add comment about correct ordering of this file.
Rearrange everything to follow this -- put all #undefs together
and before the s&m files. Add undefs for HAVE_ALLOCA, C_ALLOCA,
BROKEN_ALLOCA_IN_FUNCTION_CALLS, STACK_DIRECTION. Remove unused
HAVE_STPCPY, HAVE_GETWD, HAVE_SETLOCALE.
m/gec63.h: Deleted; totally broken, not used at all, not in FSF.
m/7300.h, m/acorn.h, m/alliant-2800.h, m/alliant.h, m/altos.h, m/amdahl.h, m/apollo.h, m/att3b.h, m/aviion.h, m/celerity.h, m/clipper.h, m/cnvrgnt.h, m/convex.h, m/cydra5.h, m/delta.h, m/delta88k.h, m/dpx2.h, m/elxsi.h, m/ews4800r.h, m/gould.h, m/hp300bsd.h, m/hp800.h, m/hp9000s300.h, m/i860.h, m/ibmps2-aix.h, m/ibmrs6000.h, m/ibmrt-aix.h, m/ibmrt.h, m/intel386.h, m/iris4d.h, m/iris5d.h, m/iris6d.h, m/irist.h, m/isi-ov.h, m/luna88k.h, m/m68k.h, m/masscomp.h, m/mg1.h, m/mips-nec.h, m/mips-siemens.h, m/mips.h, m/news.h, m/nh3000.h, m/nh4000.h, m/ns32000.h, m/orion105.h, m/pfa50.h, m/plexus.h, m/pmax.h, m/powerpc.h, m/pyrmips.h, m/sequent-ptx.h, m/sequent.h, m/sgi-challenge.h, m/symmetry.h, m/tad68k.h, m/tahoe.h, m/targon31.h, m/tekxd88.h, m/template.h, m/tower32.h, m/tower32v3.h, m/ustation.h, m/vax.h, m/wicat.h, m/xps100.h: Delete C_ALLOCA, HAVE_ALLOCA, STACK_DIRECTION,
BROKEN_ALLOCA_IN_FUNCTION_CALLS. All of this is auto-detected.
When in doubt, I followed recent FSF sources, which also have
these things deleted.
author | ben |
---|---|
date | Thu, 04 Nov 2004 23:08:28 +0000 |
parents | a8d8f419b459 |
children | de9952d2ed18 |
rev | line source |
---|---|
428 | 1 /* Hash tables. |
2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. | |
1292 | 3 Copyright (C) 2003 Ben Wing. |
428 | 4 |
5 This file is part of XEmacs. | |
6 | |
7 XEmacs is free software; you can redistribute it and/or modify it | |
8 under the terms of the GNU General Public License as published by the | |
9 Free Software Foundation; either version 2, or (at your option) any | |
10 later version. | |
11 | |
12 XEmacs is distributed in the hope that it will be useful, but WITHOUT | |
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 for more details. | |
16 | |
17 You should have received a copy of the GNU General Public License | |
18 along with XEmacs; see the file COPYING. If not, write to | |
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
20 Boston, MA 02111-1307, USA. */ | |
21 | |
22 /* Synched up with: Not in FSF. */ | |
23 | |
1292 | 24 /* Author: Lost in the mists of history. At least back to Lucid 19.3, |
25 circa Sep 1992. */ | |
26 | |
428 | 27 #include <config.h> |
28 #include "lisp.h" | |
29 #include "hash.h" | |
30 | |
1204 | 31 #define NULL_ENTRY ((void *) 0xdeadbeef) /* -559038737 base 10 */ |
428 | 32 |
33 #define COMFORTABLE_SIZE(size) (21 * (size) / 16) | |
34 | |
35 #define KEYS_DIFFER_P(old, new, testfun) \ | |
36 (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new)))) | |
37 | |
665 | 38 static void rehash (hentry *harray, struct hash_table *ht, Elemcount size); |
428 | 39 |
665 | 40 Hashcode |
41 memory_hash (const void *xv, Bytecount size) | |
428 | 42 { |
665 | 43 Hashcode h = 0; |
442 | 44 unsigned const char *x = (unsigned const char *) xv; |
428 | 45 |
46 if (!x) return 0; | |
47 | |
48 while (size--) | |
49 { | |
665 | 50 Hashcode g; |
428 | 51 h = (h << 4) + *x++; |
52 if ((g = h & 0xf0000000) != 0) | |
53 h = (h ^ (g >> 24)) ^ g; | |
54 } | |
55 | |
56 return h; | |
57 } | |
58 | |
665 | 59 Hashcode |
442 | 60 string_hash (const char *xv) |
61 { | |
665 | 62 Hashcode h = 0; |
442 | 63 unsigned const char *x = (unsigned const char *) xv; |
64 | |
65 if (!x) return 0; | |
66 | |
67 while (*x) | |
68 { | |
665 | 69 Hashcode g; |
442 | 70 h = (h << 4) + *x++; |
71 if ((g = h & 0xf0000000) != 0) | |
72 h = (h ^ (g >> 24)) ^ g; | |
73 } | |
74 | |
75 return h; | |
76 } | |
77 | |
428 | 78 /* Return a suitable size for a hash table, with at least SIZE slots. */ |
665 | 79 static Elemcount |
80 hash_table_size (Elemcount requested_size) | |
428 | 81 { |
82 /* Return some prime near, but greater than or equal to, SIZE. | |
83 Decades from the time of writing, someone will have a system large | |
84 enough that the list below will be too short... */ | |
665 | 85 static const Elemcount primes [] = |
428 | 86 { |
87 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, | |
88 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, | |
89 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, | |
90 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, | |
91 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, | |
92 10445899, 13579681, 17653589, 22949669, 29834603, 38784989, | |
93 50420551, 65546729, 85210757, 110774011, 144006217, 187208107, | |
94 243370577, 316381771, 411296309, 534685237, 695090819, 903618083, | |
647 | 95 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */ |
428 | 96 }; |
97 /* We've heard of binary search. */ | |
98 int low, high; | |
99 for (low = 0, high = countof (primes) - 1; high - low > 1;) | |
100 { | |
101 /* Loop Invariant: size < primes [high] */ | |
102 int mid = (low + high) / 2; | |
103 if (primes [mid] < requested_size) | |
104 low = mid; | |
105 else | |
106 high = mid; | |
107 } | |
108 return primes [high]; | |
109 } | |
110 | |
442 | 111 const void * |
112 gethash (const void *key, struct hash_table *hash_table, const void **ret_value) | |
428 | 113 { |
114 if (!key) | |
115 { | |
116 *ret_value = hash_table->zero_entry; | |
117 return (void *) hash_table->zero_set; | |
118 } | |
119 else | |
120 { | |
121 hentry *harray = hash_table->harray; | |
122 hash_table_test_function test_function = hash_table->test_function; | |
665 | 123 Elemcount size = hash_table->size; |
124 Hashcode hcode_initial = | |
428 | 125 hash_table->hash_function ? |
126 hash_table->hash_function (key) : | |
665 | 127 (Hashcode) key; |
128 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
428 | 129 hentry *e = &harray [hcode]; |
442 | 130 const void *e_key = e->key; |
428 | 131 |
132 if (e_key ? | |
133 KEYS_DIFFER_P (e_key, key, test_function) : | |
134 e->contents == NULL_ENTRY) | |
135 { | |
665 | 136 Elemcount h2 = size - 2; |
137 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
428 | 138 do |
139 { | |
140 hcode += incr; if (hcode >= size) hcode -= size; | |
141 e = &harray [hcode]; | |
142 e_key = e->key; | |
143 } | |
144 while (e_key ? | |
145 KEYS_DIFFER_P (e_key, key, test_function) : | |
146 e->contents == NULL_ENTRY); | |
147 } | |
148 | |
149 *ret_value = e->contents; | |
150 return e->key; | |
151 } | |
152 } | |
153 | |
154 void | |
155 clrhash (struct hash_table *hash_table) | |
156 { | |
157 memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size); | |
158 hash_table->zero_entry = 0; | |
159 hash_table->zero_set = 0; | |
160 hash_table->fullness = 0; | |
161 } | |
162 | |
163 void | |
164 free_hash_table (struct hash_table *hash_table) | |
165 { | |
1726 | 166 xfree (hash_table->harray, hentry *); |
167 xfree (hash_table, struct hash_table *); | |
428 | 168 } |
169 | |
170 struct hash_table* | |
665 | 171 make_hash_table (Elemcount size) |
428 | 172 { |
173 struct hash_table *hash_table = xnew_and_zero (struct hash_table); | |
174 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size)); | |
175 hash_table->harray = xnew_array (hentry, hash_table->size); | |
176 clrhash (hash_table); | |
177 return hash_table; | |
178 } | |
179 | |
180 struct hash_table * | |
665 | 181 make_general_hash_table (Elemcount size, |
428 | 182 hash_table_hash_function hash_function, |
183 hash_table_test_function test_function) | |
184 { | |
185 struct hash_table* hash_table = make_hash_table (size); | |
186 hash_table->hash_function = hash_function; | |
187 hash_table->test_function = test_function; | |
188 return hash_table; | |
189 } | |
190 | |
191 static void | |
665 | 192 grow_hash_table (struct hash_table *hash_table, Elemcount new_size) |
428 | 193 { |
665 | 194 Elemcount old_size = hash_table->size; |
428 | 195 hentry *old_harray = hash_table->harray; |
196 | |
197 hash_table->size = hash_table_size (new_size); | |
198 hash_table->harray = xnew_array (hentry, hash_table->size); | |
199 | |
200 /* do the rehash on the "grown" table */ | |
201 { | |
202 long old_zero_set = hash_table->zero_set; | |
203 void *old_zero_entry = hash_table->zero_entry; | |
204 clrhash (hash_table); | |
205 hash_table->zero_set = old_zero_set; | |
206 hash_table->zero_entry = old_zero_entry; | |
207 rehash (old_harray, hash_table, old_size); | |
208 } | |
209 | |
1726 | 210 xfree (old_harray, hentry *); |
428 | 211 } |
212 | |
213 void | |
1292 | 214 pregrow_hash_table_if_necessary (struct hash_table *hash_table, |
215 Elemcount breathing_room) | |
216 { | |
217 Elemcount comfortable_size = COMFORTABLE_SIZE (hash_table->fullness); | |
218 if (hash_table->size < comfortable_size - breathing_room) | |
219 grow_hash_table (hash_table, comfortable_size + 1); | |
220 } | |
221 | |
222 void | |
442 | 223 puthash (const void *key, void *contents, struct hash_table *hash_table) |
428 | 224 { |
225 if (!key) | |
226 { | |
227 hash_table->zero_entry = contents; | |
228 hash_table->zero_set = 1; | |
229 } | |
230 else | |
231 { | |
232 hash_table_test_function test_function = hash_table->test_function; | |
665 | 233 Elemcount size = hash_table->size; |
428 | 234 hentry *harray = hash_table->harray; |
665 | 235 Hashcode hcode_initial = |
428 | 236 hash_table->hash_function ? |
237 hash_table->hash_function (key) : | |
665 | 238 (Hashcode) key; |
239 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
240 Elemcount h2 = size - 2; | |
241 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
442 | 242 const void *e_key = harray [hcode].key; |
243 const void *oldcontents; | |
428 | 244 |
245 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) | |
246 { | |
247 do | |
248 { | |
249 hcode += incr; if (hcode >= size) hcode -= size; | |
250 e_key = harray [hcode].key; | |
251 } | |
252 while (e_key && KEYS_DIFFER_P (e_key, key, test_function)); | |
253 } | |
254 oldcontents = harray [hcode].contents; | |
255 harray [hcode].key = key; | |
256 harray [hcode].contents = contents; | |
257 /* If the entry that we used was a deleted entry, | |
258 check for a non deleted entry of the same key, | |
259 then delete it. */ | |
260 if (!e_key && oldcontents == NULL_ENTRY) | |
261 { | |
262 hentry *e; | |
263 | |
264 do | |
265 { | |
266 hcode += incr; if (hcode >= size) hcode -= size; | |
267 e = &harray [hcode]; | |
268 e_key = e->key; | |
269 } | |
270 while (e_key ? | |
271 KEYS_DIFFER_P (e_key, key, test_function): | |
272 e->contents == NULL_ENTRY); | |
273 | |
274 if (e_key) | |
275 { | |
276 e->key = 0; | |
277 e->contents = NULL_ENTRY; | |
278 } | |
279 } | |
280 | |
281 /* only increment the fullness when we used up a new hentry */ | |
282 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function)) | |
283 { | |
665 | 284 Elemcount comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness)); |
428 | 285 if (hash_table->size < comfortable_size) |
286 grow_hash_table (hash_table, comfortable_size + 1); | |
287 } | |
288 } | |
289 } | |
290 | |
291 static void | |
665 | 292 rehash (hentry *harray, struct hash_table *hash_table, Elemcount size) |
428 | 293 { |
294 hentry *limit = harray + size; | |
295 hentry *e; | |
296 for (e = harray; e < limit; e++) | |
297 { | |
298 if (e->key) | |
299 puthash (e->key, e->contents, hash_table); | |
300 } | |
301 } | |
302 | |
303 void | |
442 | 304 remhash (const void *key, struct hash_table *hash_table) |
428 | 305 { |
306 if (!key) | |
307 { | |
308 hash_table->zero_entry = 0; | |
309 hash_table->zero_set = 0; | |
310 } | |
311 else | |
312 { | |
313 hentry *harray = hash_table->harray; | |
314 hash_table_test_function test_function = hash_table->test_function; | |
665 | 315 Elemcount size = hash_table->size; |
316 Hashcode hcode_initial = | |
428 | 317 (hash_table->hash_function) ? |
318 (hash_table->hash_function (key)) : | |
665 | 319 ((Hashcode) key); |
320 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
428 | 321 hentry *e = &harray [hcode]; |
442 | 322 const void *e_key = e->key; |
428 | 323 |
324 if (e_key ? | |
325 KEYS_DIFFER_P (e_key, key, test_function) : | |
326 e->contents == NULL_ENTRY) | |
327 { | |
665 | 328 Elemcount h2 = size - 2; |
329 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
428 | 330 do |
331 { | |
332 hcode += incr; if (hcode >= size) hcode -= size; | |
333 e = &harray [hcode]; | |
334 e_key = e->key; | |
335 } | |
336 while (e_key? | |
337 KEYS_DIFFER_P (e_key, key, test_function): | |
338 e->contents == NULL_ENTRY); | |
339 } | |
340 if (e_key) | |
341 { | |
342 e->key = 0; | |
343 e->contents = NULL_ENTRY; | |
344 /* Note: you can't do fullness-- here, it breaks the world. */ | |
345 } | |
346 } | |
347 } | |
348 | |
349 void | |
350 maphash (maphash_function mf, struct hash_table *hash_table, void *arg) | |
351 { | |
352 hentry *e; | |
353 hentry *limit; | |
354 | |
355 if (hash_table->zero_set) | |
356 { | |
357 if (mf (0, hash_table->zero_entry, arg)) | |
358 return; | |
359 } | |
360 | |
361 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
362 { | |
363 if (e->key && mf (e->key, e->contents, arg)) | |
364 return; | |
365 } | |
366 } | |
367 | |
368 void | |
369 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg) | |
370 { | |
371 hentry *e; | |
372 hentry *limit; | |
373 | |
374 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg)) | |
375 { | |
376 hash_table->zero_set = 0; | |
377 hash_table->zero_entry = 0; | |
378 } | |
379 | |
380 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
381 if (predicate (e->key, e->contents, arg)) | |
382 { | |
383 e->key = 0; | |
384 e->contents = NULL_ENTRY; | |
385 } | |
386 } |