Mercurial > hg > xemacs-beta
annotate src/hash.c @ 5353:38e24b8be4ea
Improve the lexical scoping in #'block, #'return-from.
lisp/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el:
* bytecomp.el (byte-compile-initial-macro-environment):
Shadow `block', `return-from' here, we implement them differently
when byte-compiling.
* bytecomp.el (byte-compile-active-blocks): New.
* bytecomp.el (byte-compile-block-1): New.
* bytecomp.el (byte-compile-return-from-1): New.
* bytecomp.el (return-from-1): New.
* bytecomp.el (block-1): New.
These are two aliases that exist to have their own associated
byte-compile functions, which functions implement `block' and
`return-from'.
* cl-extra.el (cl-macroexpand-all):
Fix a bug here when macros in the environment have been compiled.
* cl-macs.el (block):
* cl-macs.el (return):
* cl-macs.el (return-from):
Be more careful about lexical scope in these macros.
* cl.el:
* cl.el ('cl-block-wrapper): Removed.
* cl.el ('cl-block-throw): Removed.
These aren't needed in code generated by this XEmacs. They
shouldn't be needed in code generated by XEmacs 21.4, but if it
turns out the packages do need them, we can put them back.
2011-01-30 Mike Sperber <mike@xemacs.org>
* font-lock.el (font-lock-fontify-pending-extents): Don't fail if
`font-lock-mode' is unset, which can happen in the middle of
`revert-buffer'.
2011-01-23 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete):
* cl-macs.el (delq):
* cl-macs.el (remove):
* cl-macs.el (remq):
Don't use the compiler macro if these functions were given the
wrong number of arguments, as happens in lisp-tests.el.
* cl-seq.el (remove, remq): Removed.
I added these to subr.el, and forgot to remove them from here.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-setq, byte-compile-set):
Remove kludge allowing keywords' values to be set, all the code
that does that is gone.
* cl-compat.el (elt-satisfies-test-p):
* faces.el (set-face-parent):
* faces.el (face-doc-string):
* gtk-font-menu.el:
* gtk-font-menu.el (gtk-reset-device-font-menus):
* msw-font-menu.el:
* msw-font-menu.el (mswindows-reset-device-font-menus):
* package-get.el (package-get-installedp):
* select.el (select-convert-from-image-data):
* sound.el:
* sound.el (load-sound-file):
* x-font-menu.el (x-reset-device-font-menus-core):
Don't quote keywords, they're self-quoting, and the
win from backward-compatibility is sufficiently small now that the
style problem overrides it.
2011-01-22 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (block, return-from): Require that NAME be a symbol
in these macros, as always documented in the #'block docstring and
as required by Common Lisp.
* descr-text.el (unidata-initialize-unihan-database):
Correct the use of non-symbols in #'block and #'return-from in
this function.
2011-01-15 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (concatenate): Accept more complicated TYPEs in this
function, handing the sequences over to #'coerce if we don't
understand them here.
* cl-macs.el (inline): Don't proclaim #'concatenate as inline, its
compiler macro is more useful than doing that.
2011-01-11 Aidan Kehoe <kehoea@parhasard.net>
* subr.el (delete, delq, remove, remq): Move #'remove, #'remq
here, they don't belong in cl-seq.el; move #'delete, #'delq here
from fns.c, implement them in terms of #'delete*, allowing support
for sequences generally.
* update-elc.el (do-autoload-commands): Use #'delete*, not #'delq
here, now the latter's no longer dumped.
* cl-macs.el (delete, delq): Add compiler macros transforming
#'delete and #'delq to #'delete* calls.
2011-01-10 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box): Correct a misplaced parenthesis
here, thank you Mats Lidell in 87zkr9gqrh.fsf@mail.contactor.se !
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* dialog.el (make-dialog-box):
* list-mode.el (display-completion-list):
These functions used to use cl-parsing-keywords; change them to
use defun* instead, fixing the build. (Not sure what led to me
not including this change in d1b17a33450b!)
2011-01-02 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (define-star-compiler-macros):
Make sure the form has ITEM and LIST specified before attempting
to change to calls with explicit tests; necessary for some tests
in lisp-tests.el to compile correctly.
(stable-union, stable-intersection): Add compiler macros for these
functions, in the same way we do for most of the other functions
in cl-seq.el.
2011-01-01 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (dolist, dotimes, do-symbols, macrolet)
(symbol-macrolet):
Define these macros with defmacro* instead of parsing the argument
list by hand, for the sake of style and readability; use backquote
where appropriate, instead of calling #'list and and friends, for
the same reason.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* x-misc.el (device-x-display):
Provide this function, documented in the Lispref for years, but
not existing previously. Thank you Julian Bradfield, thank you
Jeff Mincy.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl-seq.el:
Move the heavy lifting from this file to C. Dump the
cl-parsing-keywords macro, but don't use defun* for the functions
we define that do take keywords, dynamic scope lossage makes that
not practical.
* subr.el (sort, fillarray): Move these aliases here.
(map-plist): #'nsublis is now built-in, but at this point #'eql
isn't necessarily available as a test; use #'eq.
* obsolete.el (cl-delete-duplicates): Make this available for old
compiler macros and old code.
(memql): Document that this is equivalent to #'member*, and worse.
* cl.el (adjoin, subst): Removed. These are in C.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* simple.el (assoc-ignore-case): Remove a duplicate definition of
this function (it's already in subr.el).
* iso8859-1.el (char-width):
On non-Mule, make this function equivalent to that produced by
(constantly 1), but preserve its docstring.
* subr.el (subst-char-in-string): Define this in terms of
#'substitute, #'nsubstitute.
(string-width): Define this using #'reduce and #'char-width.
(char-width): Give this a simpler definition, it makes far more
sense to check for mule at load time and redefine, as we do in
iso8859-1.el.
(store-substring): Implement this in terms of #'replace, now
#'replace is cheap.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* update-elc.el (lisp-files-needed-for-byte-compilation)
(lisp-files-needing-early-byte-compilation):
cl-macs belongs in the former, not the latter, it is as
fundamental as bytecomp.el.
2010-12-30 Aidan Kehoe <kehoea@parhasard.net>
* cl.el:
Provde the Common Lisp program-error, type-error as error
symbols. This doesn't nearly go far enough for anyone using the
Common Lisp errors.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (delete-duplicates):
If the form has an incorrect number of arguments, don't attempt a
compiler macroexpansion.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (cl-safe-expr-p):
Forms that start with the symbol lambda are also safe.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
For these functions' compiler macros, the optimisation is safe
even if the first and the last arguments have side effects, since
they're only used the once.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (inline-side-effect-free-compiler-macros):
Unroll a loop here at macro-expansion time, so these compiler
macros are compiled. Use #'eql instead of #'eq in a couple of
places for better style.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (notany, notevery): Avoid some dynamic scope
stupidity with local variable names in these functions, when they
weren't prefixed with cl-; go into some more detail in the doc
strings.
2010-12-29 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns): #'remove, #'remq are
free of side-effects.
(side-effect-and-error-free-fns):
Drop dot, dot-marker from the list.
2010-11-17 Aidan Kehoe <kehoea@parhasard.net>
* cl-extra.el (coerce):
In the argument list, name the first argument OBJECT, not X; the
former name was always used in the doc string and is clearer.
Handle vector type specifications which include the length of the
target sequence, error if there's a mismatch.
* cl-macs.el (cl-make-type-test): Handle type specifications
starting with the symbol 'eql.
2010-11-14 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (eql): Don't remove the byte-compile property of this
symbol. That was necessary to override a bug in bytecomp.el where
#'eql was confused with #'eq, which bug we no longer have.
If neither expression is constant, don't attempt to handle the
expression in this compiler macro, leave it to byte-compile-eql,
which produces better code anyway.
* bytecomp.el (eq): #'eql is not the function associated with the
byte-eq byte code.
(byte-compile-eql): Add an explicit compile method for this
function, for cases where the cl-macs compiler macro hasn't
reduced it to #'eq or #'equal.
2010-10-25 Aidan Kehoe <kehoea@parhasard.net>
Add compiler macros and compilation sanity-checking for various
functions that take keywords.
* byte-optimize.el (side-effect-free-fns): #'symbol-value is
side-effect free and not error free.
* bytecomp.el (byte-compile-normal-call): Check keyword argument
lists for sanity; store information about the positions where
keyword arguments start using the new byte-compile-keyword-start
property.
* cl-macs.el (cl-const-expr-val): Take a new optional argument,
cl-not-constant, defaulting to nil, in this function; return it if
the expression is not constant.
(cl-non-fixnum-number-p): Make this into a separate function, we
want to pass it to #'every.
(eql): Use it.
(define-star-compiler-macros): Use the same code to generate the
member*, assoc* and rassoc* compiler macros; special-case some
code in #'add-to-list in subr.el.
(remove, remq): Add compiler macros for these two functions, in
preparation for #'remove being in C.
(define-foo-if-compiler-macros): Transform (remove-if-not ...) calls to
(remove ... :if-not) at compile time, which will be a real win
once the latter is in C.
(define-substitute-if-compiler-macros)
(define-subst-if-compiler-macros): Similarly for these functions.
(delete-duplicates): Change this compiler macro to use
#'plists-equal; if we don't have information about the type of
SEQUENCE at compile time, don't bother attempting to inline the
call, the function will be in C soon enough.
(equalp): Remove an old commented-out compiler macro for this, if
we want to see it it's in version control.
(subst-char-in-string): Transform this to a call to nsubstitute or
nsubstitute, if that is appropriate.
* cl.el (ldiff): Don't call setf here, this makes for a load-time
dependency problem in cl-macs.el
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* term/vt100.el:
Refer to XEmacs, not GNU Emacs, in permissions.
* term/bg-mouse.el:
* term/sup-mouse.el:
Put copyright notice in canonical "Copyright DATE AUTHOR" form.
Refer to XEmacs, not GNU Emacs, in permissions.
* site-load.el:
Add permission boilerplate.
* mule/canna-leim.el:
* alist.el:
Refer to XEmacs, not APEL/this program, in permissions.
* mule/canna-leim.el:
Remove my copyright, I've assigned it to the FSF.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* gtk.el:
* gtk-widget-accessors.el:
* gtk-package.el:
* gtk-marshal.el:
* gtk-compose.el:
* gnome.el:
Add copyright notice based on internal evidence.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* easymenu.el: Add reference to COPYING to permission notice.
* gutter.el:
* gutter-items.el:
* menubar-items.el:
Fix typo "Xmacs" in permissions notice.
2010-06-14 Stephen J. Turnbull <stephen@xemacs.org>
* auto-save.el:
* font.el:
* fontconfig.el:
* mule/kinsoku.el:
Add "part of XEmacs" text to permission notice.
2010-10-14 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (side-effect-free-fns):
* cl-macs.el (remf, getf):
* cl-extra.el (tailp, cl-set-getf, cl-do-remf):
* cl.el (ldiff, endp):
Tighten up Common Lisp compatibility for #'ldiff, #'endp, #'tailp;
add circularity checking for the first two.
#'cl-set-getf and #'cl-do-remf were Lisp implementations of
#'plist-put and #'plist-remprop; change the names to aliases,
changes the macros that use them to using #'plist-put and
#'plist-remprop directly.
2010-10-12 Aidan Kehoe <kehoea@parhasard.net>
* abbrev.el (fundamental-mode-abbrev-table, global-abbrev-table):
Create both these abbrev tables using the usual
#'define-abbrev-table calls, rather than attempting to
special-case them.
* cl-extra.el: Force cl-macs to be loaded here, if cl-extra.el is
being loaded interpreted. Previously other, later files would
redundantly call (load "cl-macs") when interpreted, it's more
reasonable to do it here, once.
* cmdloop.el (read-quoted-char-radix): Use defcustom here, we
don't have any dump-order dependencies that would prevent that.
* custom.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling, rely on cl-extra.el in the
former case and the appropriate entry in bytecomp-load-hook in the
latter. Get rid of custom-declare-variable-list, we have no
dump-time dependencies that would require it.
* faces.el (eval-when-compile): Don't load cl-macs when
interpreted or when byte-compiling.
* packages.el: Remove some inaccurate comments.
* post-gc.el (cleanup-simple-finalizers): Use #'delete-if-not
here, now the order of preloaded-file-list has been changed to
make it available.
* subr.el (custom-declare-variable-list): Remove. No need for it.
Also remove a stub define-abbrev-table from this file, given the
current order of preloaded-file-list there's no need for it.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-constp) Forms quoted with FUNCTION are
also constant.
(byte-compile-initial-macro-environment): In #'the, if FORM is
constant and does not match TYPE, warn at byte-compile time.
2010-10-10 Aidan Kehoe <kehoea@parhasard.net>
* backquote.el (bq-vector-contents, bq-list*): Remove; the former
is equivalent to (append VECTOR nil), the latter to (list* ...).
(bq-process-2): Use (append VECTOR nil) instead of using
#'bq-vector-contents to convert to a list.
(bq-process-1): Now we use list* instead of bq-list
* subr.el (list*): Moved from cl.el, since it is now required to
be available the first time a backquoted form is encountered.
* cl.el (list*): Move to subr.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* test-harness.el (Check-Message):
Add an omitted comma here, thank you the buildbot.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* hash-table.el (hash-table-key-list, hash-table-value-list)
(hash-table-key-value-alist, hash-table-key-value-plist):
Remove some useless #'nreverse calls in these files; our hash
tables have no order, it's not helpful to pretend they do.
* behavior.el (read-behavior):
Do the same in this file, in some code evidently copied from
hash-table.el.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* info.el (Info-insert-dir):
* format.el (format-deannotate-region):
* files.el (cd, save-buffers-kill-emacs):
Use #'some, #'every and related functions for applying boolean
operations to lists, instead of rolling our own ones that cons and
don't short-circuit.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-initial-macro-environment):
* cl-macs.el (the):
Rephrase the docstring, make its implementation when compiling
files a little nicer.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* descr-text.el (unidata-initialize-unicodedata-database)
(unidata-initialize-unihan-database, describe-char-unicode-data)
(describe-char-unicode-data):
Wrap calls to the database functions with (with-fboundp ...),
avoiding byte compile warnings on builds without support for the
database functions.
(describe-char): (reduce #'max ...), not (apply #'max ...), no
need to cons needlessly.
(describe-char): Remove a redundant lambda wrapping
#'extent-properties.
(describe-char-unicode-data): Call #'nsubst when replacing "" with
nil in the result of #'split-string, instead of consing inside
mapcar.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* x-faces.el (x-available-font-sizes):
* specifier.el (let-specifier):
* package-ui.el (pui-add-required-packages):
* msw-faces.el (mswindows-available-font-sizes):
* modeline.el (modeline-minor-mode-menu):
* minibuf.el (minibuf-directory-files):
Replace the O2N (delq nil (mapcar (lambda (W) (and X Y)) Z)) with
the ON (mapcan (lambda (W) (and X (list Y))) Z) in these files.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* cl-macs.el (= < > <= >=):
When these functions are handed more than two arguments, and those
arguments have no side effects, transform to a series of two
argument calls, avoiding funcall in the byte-compiled code.
* mule/mule-cmds.el (finish-set-language-environment):
Take advantage of this change in a function called 256 times at
startup.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* bytecomp.el (byte-compile-function-form, byte-compile-quote)
(byte-compile-quote-form):
Warn at compile time, and error at runtime, if a (quote ...) or a
(function ...) form attempts to quote more than one object.
2010-09-16 Aidan Kehoe <kehoea@parhasard.net>
* byte-optimize.el (byte-optimize-apply): Transform (apply 'nconc
(mapcar ...)) to (mapcan ...); warn about use of the first idiom.
* update-elc.el (do-autoload-commands):
* packages.el (packages-find-package-library-path):
* frame.el (frame-list):
* extents.el (extent-descendants):
* etags.el (buffer-tag-table-files):
* dumped-lisp.el (preloaded-file-list):
* device.el (device-list):
* bytecomp-runtime.el (proclaim-inline, proclaim-notinline)
Use #'mapcan, not (apply #'nconc (mapcar ...) in all these files.
* bytecomp-runtime.el (eval-when-compile, eval-and-compile):
In passing, mention that these macros also evaluate the body when
interpreted.
tests/ChangeLog addition:
2011-02-07 Aidan Kehoe <kehoea@parhasard.net>
* automated/lisp-tests.el:
Test lexical scope for `block', `return-from'; add a
Known-Bug-Expect-Failure for a contorted example that fails when
byte-compiled.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Mon, 07 Feb 2011 12:01:24 +0000 |
| parents | 88bd4f3ef8e4 |
| children | 308d34e9f07d |
| rev | line source |
|---|---|
| 428 | 1 /* Hash tables. |
| 2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. | |
|
5146
88bd4f3ef8e4
make lrecord UID's have a separate UID space for each object, resurrect debug SOE code in extents.c
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
3 Copyright (C) 2003, 2004, 2010 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 | |
|
5146
88bd4f3ef8e4
make lrecord UID's have a separate UID space for each object, resurrect debug SOE code in extents.c
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
31 #define NULL_ENTRY ((void *) 0xDEADBEEF) /* -559038737 base 10 */ |
| 428 | 32 |
| 33 #define COMFORTABLE_SIZE(size) (21 * (size) / 16) | |
| 34 | |
| 3025 | 35 #define KEYS_DIFFER_P(old, new_, testfun) \ |
| 36 (((old) != (new_)) && (!(testfun) || !(testfun) ((old),(new_)))) | |
| 428 | 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 | |
| 2515 | 59 static int |
| 60 string_equal (const void *st1, const void *st2) | |
| 61 { | |
| 62 if (!st1) | |
| 63 return st2 ? 0 : 1; | |
| 64 else if (!st2) | |
| 65 return 0; | |
| 66 else | |
| 67 return !strcmp ((const char *) st1, (const char *) st2); | |
| 68 } | |
| 69 | |
| 70 static Hashcode | |
| 71 string_hash (const void *xv) | |
| 442 | 72 { |
| 665 | 73 Hashcode h = 0; |
| 442 | 74 unsigned const char *x = (unsigned const char *) xv; |
| 75 | |
| 76 if (!x) return 0; | |
| 77 | |
| 78 while (*x) | |
| 79 { | |
| 665 | 80 Hashcode g; |
| 442 | 81 h = (h << 4) + *x++; |
| 82 if ((g = h & 0xf0000000) != 0) | |
| 83 h = (h ^ (g >> 24)) ^ g; | |
| 84 } | |
| 85 | |
| 86 return h; | |
| 87 } | |
| 88 | |
| 428 | 89 /* Return a suitable size for a hash table, with at least SIZE slots. */ |
| 665 | 90 static Elemcount |
| 91 hash_table_size (Elemcount requested_size) | |
| 428 | 92 { |
| 93 /* Return some prime near, but greater than or equal to, SIZE. | |
| 94 Decades from the time of writing, someone will have a system large | |
| 95 enough that the list below will be too short... */ | |
| 665 | 96 static const Elemcount primes [] = |
| 428 | 97 { |
| 98 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, | |
| 99 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, | |
| 100 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, | |
| 101 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, | |
| 102 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, | |
| 103 10445899, 13579681, 17653589, 22949669, 29834603, 38784989, | |
| 104 50420551, 65546729, 85210757, 110774011, 144006217, 187208107, | |
| 105 243370577, 316381771, 411296309, 534685237, 695090819, 903618083, | |
| 647 | 106 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */ |
| 428 | 107 }; |
| 108 /* We've heard of binary search. */ | |
| 109 int low, high; | |
| 110 for (low = 0, high = countof (primes) - 1; high - low > 1;) | |
| 111 { | |
| 112 /* Loop Invariant: size < primes [high] */ | |
| 113 int mid = (low + high) / 2; | |
| 114 if (primes [mid] < requested_size) | |
| 115 low = mid; | |
| 116 else | |
| 117 high = mid; | |
| 118 } | |
| 119 return primes [high]; | |
| 120 } | |
| 121 | |
| 442 | 122 const void * |
| 123 gethash (const void *key, struct hash_table *hash_table, const void **ret_value) | |
| 428 | 124 { |
| 125 if (!key) | |
| 126 { | |
| 127 *ret_value = hash_table->zero_entry; | |
| 128 return (void *) hash_table->zero_set; | |
| 129 } | |
| 130 else | |
| 131 { | |
| 132 hentry *harray = hash_table->harray; | |
| 133 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 134 Elemcount size = hash_table->size; |
| 135 Hashcode hcode_initial = | |
| 428 | 136 hash_table->hash_function ? |
| 137 hash_table->hash_function (key) : | |
| 665 | 138 (Hashcode) key; |
| 139 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 428 | 140 hentry *e = &harray [hcode]; |
| 442 | 141 const void *e_key = e->key; |
| 428 | 142 |
| 143 if (e_key ? | |
| 144 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 145 e->contents == NULL_ENTRY) | |
| 146 { | |
| 665 | 147 Elemcount h2 = size - 2; |
| 148 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 428 | 149 do |
| 150 { | |
| 151 hcode += incr; if (hcode >= size) hcode -= size; | |
| 152 e = &harray [hcode]; | |
| 153 e_key = e->key; | |
| 154 } | |
| 155 while (e_key ? | |
| 156 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 157 e->contents == NULL_ENTRY); | |
| 158 } | |
| 159 | |
| 160 *ret_value = e->contents; | |
| 161 return e->key; | |
| 162 } | |
| 163 } | |
| 164 | |
| 165 void | |
| 166 clrhash (struct hash_table *hash_table) | |
| 167 { | |
| 168 memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size); | |
| 169 hash_table->zero_entry = 0; | |
| 170 hash_table->zero_set = 0; | |
| 171 hash_table->fullness = 0; | |
| 172 } | |
| 173 | |
| 174 void | |
| 175 free_hash_table (struct hash_table *hash_table) | |
| 176 { | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
177 xfree (hash_table->harray); |
|
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
178 xfree (hash_table); |
| 428 | 179 } |
| 180 | |
| 2515 | 181 struct hash_table * |
| 665 | 182 make_hash_table (Elemcount size) |
| 428 | 183 { |
| 184 struct hash_table *hash_table = xnew_and_zero (struct hash_table); | |
| 185 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size)); | |
| 186 hash_table->harray = xnew_array (hentry, hash_table->size); | |
| 187 clrhash (hash_table); | |
| 188 return hash_table; | |
| 189 } | |
| 190 | |
| 191 struct hash_table * | |
| 2515 | 192 make_string_hash_table (Elemcount size) |
| 193 { | |
| 194 return make_general_hash_table (size, string_hash, string_equal); | |
| 195 } | |
| 196 | |
| 197 struct hash_table * | |
| 665 | 198 make_general_hash_table (Elemcount size, |
| 428 | 199 hash_table_hash_function hash_function, |
| 200 hash_table_test_function test_function) | |
| 201 { | |
| 202 struct hash_table* hash_table = make_hash_table (size); | |
| 203 hash_table->hash_function = hash_function; | |
| 204 hash_table->test_function = test_function; | |
| 205 return hash_table; | |
| 206 } | |
| 207 | |
| 208 static void | |
| 665 | 209 grow_hash_table (struct hash_table *hash_table, Elemcount new_size) |
| 428 | 210 { |
| 665 | 211 Elemcount old_size = hash_table->size; |
| 428 | 212 hentry *old_harray = hash_table->harray; |
| 213 | |
| 214 hash_table->size = hash_table_size (new_size); | |
| 215 hash_table->harray = xnew_array (hentry, hash_table->size); | |
| 216 | |
| 217 /* do the rehash on the "grown" table */ | |
| 218 { | |
| 219 long old_zero_set = hash_table->zero_set; | |
| 220 void *old_zero_entry = hash_table->zero_entry; | |
| 221 clrhash (hash_table); | |
| 222 hash_table->zero_set = old_zero_set; | |
| 223 hash_table->zero_entry = old_zero_entry; | |
| 224 rehash (old_harray, hash_table, old_size); | |
| 225 } | |
| 226 | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
227 xfree (old_harray); |
| 428 | 228 } |
| 229 | |
| 230 void | |
| 1292 | 231 pregrow_hash_table_if_necessary (struct hash_table *hash_table, |
| 232 Elemcount breathing_room) | |
| 233 { | |
| 234 Elemcount comfortable_size = COMFORTABLE_SIZE (hash_table->fullness); | |
| 235 if (hash_table->size < comfortable_size - breathing_room) | |
| 236 grow_hash_table (hash_table, comfortable_size + 1); | |
| 237 } | |
| 238 | |
| 239 void | |
| 442 | 240 puthash (const void *key, void *contents, struct hash_table *hash_table) |
| 428 | 241 { |
| 242 if (!key) | |
| 243 { | |
| 244 hash_table->zero_entry = contents; | |
| 245 hash_table->zero_set = 1; | |
| 246 } | |
| 247 else | |
| 248 { | |
| 249 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 250 Elemcount size = hash_table->size; |
| 428 | 251 hentry *harray = hash_table->harray; |
| 665 | 252 Hashcode hcode_initial = |
| 428 | 253 hash_table->hash_function ? |
| 254 hash_table->hash_function (key) : | |
| 665 | 255 (Hashcode) key; |
| 256 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 257 Elemcount h2 = size - 2; | |
| 258 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 442 | 259 const void *e_key = harray [hcode].key; |
| 260 const void *oldcontents; | |
| 428 | 261 |
| 262 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) | |
| 263 { | |
| 264 do | |
| 265 { | |
| 266 hcode += incr; if (hcode >= size) hcode -= size; | |
| 267 e_key = harray [hcode].key; | |
| 268 } | |
| 269 while (e_key && KEYS_DIFFER_P (e_key, key, test_function)); | |
| 270 } | |
| 271 oldcontents = harray [hcode].contents; | |
| 272 harray [hcode].key = key; | |
| 273 harray [hcode].contents = contents; | |
| 274 /* If the entry that we used was a deleted entry, | |
| 275 check for a non deleted entry of the same key, | |
| 276 then delete it. */ | |
| 277 if (!e_key && oldcontents == NULL_ENTRY) | |
| 278 { | |
| 279 hentry *e; | |
| 280 | |
| 281 do | |
| 282 { | |
| 283 hcode += incr; if (hcode >= size) hcode -= size; | |
| 284 e = &harray [hcode]; | |
| 285 e_key = e->key; | |
| 286 } | |
| 287 while (e_key ? | |
| 288 KEYS_DIFFER_P (e_key, key, test_function): | |
| 289 e->contents == NULL_ENTRY); | |
| 290 | |
| 291 if (e_key) | |
| 292 { | |
| 293 e->key = 0; | |
| 294 e->contents = NULL_ENTRY; | |
| 295 } | |
| 296 } | |
| 297 | |
| 298 /* only increment the fullness when we used up a new hentry */ | |
| 299 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function)) | |
| 300 { | |
| 665 | 301 Elemcount comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness)); |
| 428 | 302 if (hash_table->size < comfortable_size) |
| 303 grow_hash_table (hash_table, comfortable_size + 1); | |
| 304 } | |
| 305 } | |
| 306 } | |
| 307 | |
| 308 static void | |
| 665 | 309 rehash (hentry *harray, struct hash_table *hash_table, Elemcount size) |
| 428 | 310 { |
| 311 hentry *limit = harray + size; | |
| 312 hentry *e; | |
| 313 for (e = harray; e < limit; e++) | |
| 314 { | |
| 315 if (e->key) | |
| 316 puthash (e->key, e->contents, hash_table); | |
| 317 } | |
| 318 } | |
| 319 | |
| 320 void | |
| 442 | 321 remhash (const void *key, struct hash_table *hash_table) |
| 428 | 322 { |
| 323 if (!key) | |
| 324 { | |
| 325 hash_table->zero_entry = 0; | |
| 326 hash_table->zero_set = 0; | |
| 327 } | |
| 328 else | |
| 329 { | |
| 330 hentry *harray = hash_table->harray; | |
| 331 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 332 Elemcount size = hash_table->size; |
| 333 Hashcode hcode_initial = | |
| 428 | 334 (hash_table->hash_function) ? |
| 335 (hash_table->hash_function (key)) : | |
| 665 | 336 ((Hashcode) key); |
| 337 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 428 | 338 hentry *e = &harray [hcode]; |
| 442 | 339 const void *e_key = e->key; |
| 428 | 340 |
| 341 if (e_key ? | |
| 342 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 343 e->contents == NULL_ENTRY) | |
| 344 { | |
| 665 | 345 Elemcount h2 = size - 2; |
| 346 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 428 | 347 do |
| 348 { | |
| 349 hcode += incr; if (hcode >= size) hcode -= size; | |
| 350 e = &harray [hcode]; | |
| 351 e_key = e->key; | |
| 352 } | |
| 353 while (e_key? | |
| 354 KEYS_DIFFER_P (e_key, key, test_function): | |
| 355 e->contents == NULL_ENTRY); | |
| 356 } | |
| 357 if (e_key) | |
| 358 { | |
| 359 e->key = 0; | |
| 360 e->contents = NULL_ENTRY; | |
| 361 /* Note: you can't do fullness-- here, it breaks the world. */ | |
| 362 } | |
| 363 } | |
| 364 } | |
| 365 | |
| 366 void | |
| 367 maphash (maphash_function mf, struct hash_table *hash_table, void *arg) | |
| 368 { | |
| 369 hentry *e; | |
| 370 hentry *limit; | |
| 371 | |
| 372 if (hash_table->zero_set) | |
| 373 { | |
| 374 if (mf (0, hash_table->zero_entry, arg)) | |
| 375 return; | |
| 376 } | |
| 377 | |
| 378 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
| 379 { | |
| 380 if (e->key && mf (e->key, e->contents, arg)) | |
| 381 return; | |
| 382 } | |
| 383 } | |
| 384 | |
| 385 void | |
| 386 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg) | |
| 387 { | |
| 388 hentry *e; | |
| 389 hentry *limit; | |
| 390 | |
| 391 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg)) | |
| 392 { | |
| 393 hash_table->zero_set = 0; | |
| 394 hash_table->zero_entry = 0; | |
| 395 } | |
| 396 | |
| 397 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
| 398 if (predicate (e->key, e->contents, arg)) | |
| 399 { | |
| 400 e->key = 0; | |
| 401 e->contents = NULL_ENTRY; | |
| 402 } | |
| 403 } |