Mercurial > hg > xemacs-beta
annotate src/hash.c @ 4952:19a72041c5ed
Mule-izing, various fixes related to char * arguments
-------------------- ChangeLog entries follow: --------------------
modules/ChangeLog addition:
2010-01-26 Ben Wing <ben@xemacs.org>
* postgresql/postgresql.c:
* postgresql/postgresql.c (CHECK_LIVE_CONNECTION):
* postgresql/postgresql.c (print_pgresult):
* postgresql/postgresql.c (Fpq_conn_defaults):
* postgresql/postgresql.c (Fpq_connectdb):
* postgresql/postgresql.c (Fpq_connect_start):
* postgresql/postgresql.c (Fpq_result_status):
* postgresql/postgresql.c (Fpq_res_status):
Mule-ize large parts of it.
2010-01-26 Ben Wing <ben@xemacs.org>
* ldap/eldap.c (print_ldap):
* ldap/eldap.c (allocate_ldap):
Use write_ascstring().
src/ChangeLog addition:
2010-01-26 Ben Wing <ben@xemacs.org>
* alloc.c:
* alloc.c (build_ascstring):
* alloc.c (build_msg_cistring):
* alloc.c (staticpro_1):
* alloc.c (staticpro_name):
* alloc.c (staticpro_nodump_1):
* alloc.c (staticpro_nodump_name):
* alloc.c (unstaticpro_nodump_1):
* alloc.c (mcpro_1):
* alloc.c (mcpro_name):
* alloc.c (object_memory_usage_stats):
* alloc.c (common_init_alloc_early):
* alloc.c (init_alloc_once_early):
* buffer.c (print_buffer):
* buffer.c (vars_of_buffer):
* buffer.c (common_init_complex_vars_of_buffer):
* buffer.c (init_initial_directory):
* bytecode.c (invalid_byte_code):
* bytecode.c (print_compiled_function):
* bytecode.c (mark_compiled_function):
* chartab.c (print_table_entry):
* chartab.c (print_char_table):
* config.h.in:
* console-gtk.c:
* console-gtk.c (gtk_device_to_console_connection):
* console-gtk.c (gtk_semi_canonicalize_console_connection):
* console-gtk.c (gtk_canonicalize_console_connection):
* console-gtk.c (gtk_semi_canonicalize_device_connection):
* console-gtk.c (gtk_canonicalize_device_connection):
* console-stream.c (stream_init_frame_1):
* console-stream.c (vars_of_console_stream):
* console-stream.c (init_console_stream):
* console-x.c (x_semi_canonicalize_console_connection):
* console-x.c (x_semi_canonicalize_device_connection):
* console-x.c (x_canonicalize_device_connection):
* console-x.h:
* data.c (eq_with_ebola_notice):
* data.c (Fsubr_interactive):
* data.c (Fnumber_to_string):
* data.c (digit_to_number):
* device-gtk.c (gtk_init_device):
* device-msw.c (print_devmode):
* device-x.c (x_event_name):
* dialog-msw.c (handle_directory_dialog_box):
* dialog-msw.c (handle_file_dialog_box):
* dialog-msw.c (vars_of_dialog_mswindows):
* doc.c (weird_doc):
* doc.c (Fsnarf_documentation):
* doc.c (vars_of_doc):
* dumper.c (pdump):
* dynarr.c:
* dynarr.c (Dynarr_realloc):
* editfns.c (Fuser_real_login_name):
* editfns.c (get_home_directory):
* elhash.c (print_hash_table_data):
* elhash.c (print_hash_table):
* emacs.c (main_1):
* emacs.c (vars_of_emacs):
* emodules.c:
* emodules.c (_emodules_list):
* emodules.c (Fload_module):
* emodules.c (Funload_module):
* emodules.c (Flist_modules):
* emodules.c (find_make_module):
* emodules.c (attempt_module_delete):
* emodules.c (emodules_load):
* emodules.c (emodules_doc_subr):
* emodules.c (emodules_doc_sym):
* emodules.c (syms_of_module):
* emodules.c (vars_of_module):
* emodules.h:
* eval.c (print_subr):
* eval.c (signal_call_debugger):
* eval.c (build_error_data):
* eval.c (signal_error):
* eval.c (maybe_signal_error):
* eval.c (signal_continuable_error):
* eval.c (maybe_signal_continuable_error):
* eval.c (signal_error_2):
* eval.c (maybe_signal_error_2):
* eval.c (signal_continuable_error_2):
* eval.c (maybe_signal_continuable_error_2):
* eval.c (signal_ferror):
* eval.c (maybe_signal_ferror):
* eval.c (signal_continuable_ferror):
* eval.c (maybe_signal_continuable_ferror):
* eval.c (signal_ferror_with_frob):
* eval.c (maybe_signal_ferror_with_frob):
* eval.c (signal_continuable_ferror_with_frob):
* eval.c (maybe_signal_continuable_ferror_with_frob):
* eval.c (syntax_error):
* eval.c (syntax_error_2):
* eval.c (maybe_syntax_error):
* eval.c (sferror):
* eval.c (sferror_2):
* eval.c (maybe_sferror):
* eval.c (invalid_argument):
* eval.c (invalid_argument_2):
* eval.c (maybe_invalid_argument):
* eval.c (invalid_constant):
* eval.c (invalid_constant_2):
* eval.c (maybe_invalid_constant):
* eval.c (invalid_operation):
* eval.c (invalid_operation_2):
* eval.c (maybe_invalid_operation):
* eval.c (invalid_change):
* eval.c (invalid_change_2):
* eval.c (maybe_invalid_change):
* eval.c (invalid_state):
* eval.c (invalid_state_2):
* eval.c (maybe_invalid_state):
* eval.c (wtaerror):
* eval.c (stack_overflow):
* eval.c (out_of_memory):
* eval.c (print_multiple_value):
* eval.c (issue_call_trapping_problems_warning):
* eval.c (backtrace_specials):
* eval.c (backtrace_unevalled_args):
* eval.c (Fbacktrace):
* eval.c (warn_when_safe):
* event-Xt.c (modwarn):
* event-Xt.c (modbarf):
* event-Xt.c (check_modifier):
* event-Xt.c (store_modifier):
* event-Xt.c (emacs_Xt_format_magic_event):
* event-Xt.c (describe_event):
* event-gtk.c (dragndrop_data_received):
* event-gtk.c (store_modifier):
* event-gtk.c (gtk_reset_modifier_mapping):
* event-msw.c (dde_eval_string):
* event-msw.c (Fdde_alloc_advise_item):
* event-msw.c (mswindows_dde_callback):
* event-msw.c (FROB):
* event-msw.c (emacs_mswindows_format_magic_event):
* event-stream.c (external_debugging_print_event):
* event-stream.c (execute_help_form):
* event-stream.c (vars_of_event_stream):
* events.c (print_event_1):
* events.c (print_event):
* events.c (event_equal):
* extents.c (print_extent_1):
* extents.c (print_extent):
* extents.c (vars_of_extents):
* faces.c (print_face):
* faces.c (complex_vars_of_faces):
* file-coding.c:
* file-coding.c (print_coding_system):
* file-coding.c (print_coding_system_in_print_method):
* file-coding.c (default_query_method):
* file-coding.c (find_coding_system):
* file-coding.c (make_coding_system_1):
* file-coding.c (chain_print):
* file-coding.c (undecided_print):
* file-coding.c (gzip_print):
* file-coding.c (vars_of_file_coding):
* file-coding.c (complex_vars_of_file_coding):
* fileio.c:
* fileio.c (report_file_type_error):
* fileio.c (report_error_with_errno):
* fileio.c (report_file_error):
* fileio.c (barf_or_query_if_file_exists):
* fileio.c (vars_of_fileio):
* floatfns.c (matherr):
* fns.c (print_bit_vector):
* fns.c (Fmapconcat):
* fns.c (add_suffix_to_symbol):
* fns.c (add_prefix_to_symbol):
* frame-gtk.c:
* frame-gtk.c (Fgtk_window_id):
* frame-x.c (def):
* frame-x.c (x_cde_transfer_callback):
* frame.c:
* frame.c (Fmake_frame):
* gc.c (show_gc_cursor_and_message):
* gc.c (vars_of_gc):
* glyphs-eimage.c (png_instantiate):
* glyphs-eimage.c (tiff_instantiate):
* glyphs-gtk.c (gtk_print_image_instance):
* glyphs-msw.c (mswindows_print_image_instance):
* glyphs-x.c (x_print_image_instance):
* glyphs-x.c (update_widget_face):
* glyphs.c (make_string_from_file):
* glyphs.c (print_image_instance):
* glyphs.c (signal_image_error):
* glyphs.c (signal_image_error_2):
* glyphs.c (signal_double_image_error):
* glyphs.c (signal_double_image_error_2):
* glyphs.c (xbm_mask_file_munging):
* glyphs.c (pixmap_to_lisp_data):
* glyphs.h:
* gui.c (gui_item_display_flush_left):
* hpplay.c (player_error_internal):
* hpplay.c (myHandler):
* intl-win32.c:
* intl-win32.c (langcode_to_lang):
* intl-win32.c (sublangcode_to_lang):
* intl-win32.c (Fmswindows_get_locale_info):
* intl-win32.c (lcid_to_locale_mule_or_no):
* intl-win32.c (mswindows_multibyte_to_unicode_print):
* intl-win32.c (complex_vars_of_intl_win32):
* keymap.c:
* keymap.c (print_keymap):
* keymap.c (ensure_meta_prefix_char_keymapp):
* keymap.c (Fkey_description):
* keymap.c (Ftext_char_description):
* lisp.h:
* lisp.h (struct):
* lisp.h (DECLARE_INLINE_HEADER):
* lread.c (Fload_internal):
* lread.c (locate_file):
* lread.c (read_escape):
* lread.c (read_raw_string):
* lread.c (read1):
* lread.c (read_list):
* lread.c (read_compiled_function):
* lread.c (init_lread):
* lrecord.h:
* marker.c (print_marker):
* marker.c (marker_equal):
* menubar-msw.c (displayable_menu_item):
* menubar-x.c (command_builder_operate_menu_accelerator):
* menubar.c (vars_of_menubar):
* minibuf.c (reinit_complex_vars_of_minibuf):
* minibuf.c (complex_vars_of_minibuf):
* mule-charset.c (Fmake_charset):
* mule-charset.c (complex_vars_of_mule_charset):
* mule-coding.c (iso2022_print):
* mule-coding.c (fixed_width_query):
* number.c (bignum_print):
* number.c (ratio_print):
* number.c (bigfloat_print):
* number.c (bigfloat_finalize):
* objects-msw.c:
* objects-msw.c (mswindows_color_to_string):
* objects-msw.c (mswindows_color_list):
* objects-tty.c:
* objects-tty.c (tty_font_list):
* objects-tty.c (tty_find_charset_font):
* objects-xlike-inc.c (xft_find_charset_font):
* objects-xlike-inc.c (endif):
* print.c:
* print.c (write_istring):
* print.c (write_ascstring):
* print.c (Fterpri):
* print.c (Fprint):
* print.c (print_error_message):
* print.c (print_vector_internal):
* print.c (print_cons):
* print.c (print_string):
* print.c (printing_unreadable_object):
* print.c (print_internal):
* print.c (print_float):
* print.c (print_symbol):
* process-nt.c (mswindows_report_winsock_error):
* process-nt.c (nt_canonicalize_host_name):
* process-unix.c (unix_canonicalize_host_name):
* process.c (print_process):
* process.c (report_process_error):
* process.c (report_network_error):
* process.c (make_process_internal):
* process.c (Fstart_process_internal):
* process.c (status_message):
* process.c (putenv_internal):
* process.c (vars_of_process):
* process.h:
* profile.c (vars_of_profile):
* rangetab.c (print_range_table):
* realpath.c (vars_of_realpath):
* redisplay.c (vars_of_redisplay):
* search.c (wordify):
* search.c (Freplace_match):
* sheap.c (sheap_adjust_h):
* sound.c (report_sound_error):
* sound.c (Fplay_sound_file):
* specifier.c (print_specifier):
* symbols.c (Fsubr_name):
* symbols.c (do_symval_forwarding):
* symbols.c (set_default_buffer_slot_variable):
* symbols.c (set_default_console_slot_variable):
* symbols.c (store_symval_forwarding):
* symbols.c (default_value):
* symbols.c (defsymbol_massage_name_1):
* symbols.c (defsymbol_massage_name_nodump):
* symbols.c (defsymbol_massage_name):
* symbols.c (defsymbol_massage_multiword_predicate_nodump):
* symbols.c (defsymbol_massage_multiword_predicate):
* symbols.c (defsymbol_nodump):
* symbols.c (defsymbol):
* symbols.c (defkeyword):
* symbols.c (defkeyword_massage_name):
* symbols.c (check_module_subr):
* symbols.c (deferror_1):
* symbols.c (deferror):
* symbols.c (deferror_massage_name):
* symbols.c (deferror_massage_name_and_message):
* symbols.c (defvar_magic):
* symeval.h:
* symeval.h (DEFVAR_SYMVAL_FWD):
* sysdep.c:
* sysdep.c (init_system_name):
* sysdll.c:
* sysdll.c (MAYBE_PREPEND_UNDERSCORE):
* sysdll.c (dll_function):
* sysdll.c (dll_variable):
* sysdll.c (dll_error):
* sysdll.c (dll_open):
* sysdll.c (dll_close):
* sysdll.c (image_for_address):
* sysdll.c (my_find_image):
* sysdll.c (search_linked_libs):
* sysdll.h:
* sysfile.h:
* sysfile.h (DEFAULT_DIRECTORY_FALLBACK):
* syswindows.h:
* tests.c (DFC_CHECK_LENGTH):
* tests.c (DFC_CHECK_CONTENT):
* tests.c (Ftest_hash_tables):
* text.c (vars_of_text):
* text.h:
* tooltalk.c (tt_opnum_string):
* tooltalk.c (tt_message_arg_ival_string):
* tooltalk.c (Ftooltalk_default_procid):
* tooltalk.c (Ftooltalk_default_session):
* tooltalk.c (init_tooltalk):
* tooltalk.c (vars_of_tooltalk):
* ui-gtk.c (Fdll_load):
* ui-gtk.c (type_to_marshaller_type):
* ui-gtk.c (Fgtk_import_function_internal):
* ui-gtk.c (emacs_gtk_object_printer):
* ui-gtk.c (emacs_gtk_boxed_printer):
* unicode.c (unicode_to_ichar):
* unicode.c (unicode_print):
* unicode.c (unicode_query):
* unicode.c (vars_of_unicode):
* unicode.c (complex_vars_of_unicode):
* win32.c:
* win32.c (mswindows_report_process_error):
* window.c (print_window):
* xemacs.def.in.in:
BASIC IDEA: Further fixing up uses of char * and CIbyte *
to reflect their actual semantics; Mule-izing some code;
redoing of the not-yet-working code to handle message translation.
Clean up code to handle message-translation (not yet working).
Create separate versions of build_msg_string() for working with
Ibyte *, CIbyte *, and Ascbyte * arguments. Assert that Ascbyte *
arguments are pure-ASCII. Make build_msg_string() be the same
as build_msg_ascstring(). Create same three versions of GETTEXT()
and DEFER_GETTEXT(). Also create build_defer_string() and
variants for the equivalent of DEFER_GETTEXT() when building a
string. Remove old CGETTEXT(). Clean up code where GETTEXT(),
DEFER_GETTEXT(), build_msg_string(), etc. was being called and
introduce some new calls to build_msg_string(), etc. Remove
GETTEXT() from calls to weird_doc() -- we assume that the
message snarfer knows about weird_doc(). Remove uses of
DEFER_GETTEXT() from error messages in sysdep.c and instead use
special comments /* @@@begin-snarf@@@ */ and /* @@@end-snarf@@@ */
that the message snarfer presumably knows about.
Create build_ascstring() and use it in many instances in place
of build_string(). The purpose of having Ascbyte * variants is
to make the code more self-documenting in terms of what sort of
semantics is expected for char * strings. In fact in the process
of looking for uses of build_string(), much improperly Mule-ized
was discovered.
Mule-ize a lot of code as described in previous paragraph,
e.g. in sysdep.c.
Make the error functions take Ascbyte * strings and fix up a
couple of places where non-pure-ASCII strings were being passed in
(file-coding.c, mule-coding.c, unicode.c). (It's debatable whether
we really need to make the error functions work this way. It
helps catch places where code is written in a way that message
translation won't work, but we may well never implement message
translation.)
Make staticpro() and friends take Ascbyte * strings instead of
raw char * strings. Create a const_Ascbyte_ptr dynarr type
to describe what's held by staticpro_names[] and friends,
create pdump descriptions for const_Ascbyte_ptr dynarrs, and
use them in place of specially-crafted staticpro descriptions.
Mule-ize certain other functions (e.g. x_event_name) by correcting
raw use of char * to Ascbyte *, Rawbyte * or another such type,
and raw use of char[] buffers to another type (usually Ascbyte[]).
Change many uses of write_c_string() to write_msg_string(),
write_ascstring(), etc.
Mule-ize emodules.c, emodules.h, sysdll.h.
Fix some un-Mule-ized code in intl-win32.c.
A comment in event-Xt.c and the limitations of the message
snarfer (make-msgfile or whatever) is presumably incorrect --
it should be smart enough to handle function calls spread over
more than one line. Clean up code in event-Xt.c that was
written awkwardly for this reason.
In config.h.in, instead of NEED_ERROR_CHECK_TYPES_INLINES,
create a more general XEMACS_DEFS_NEEDS_INLINE_DECLS to
indicate when inlined functions need to be declared in
xemacs.defs.in.in, and make use of it in xemacs.defs.in.in.
We need to do this because postgresql.c now calls qxestrdup(),
which is an inline function.
Make nconc2() and other such functions MODULE_API and put
them in xemacs.defs.in.in since postgresql.c now uses them.
Clean up indentation in lread.c and a few other places.
In text.h, document ASSERT_ASCTEXT_ASCII() and
ASSERT_ASCTEXT_ASCII_LEN(), group together the stand-in
encodings and add some more for DLL symbols, function and
variable names, etc.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Tue, 26 Jan 2010 23:22:30 -0600 |
| parents | facf3239ba30 |
| children | 16112448d484 |
| rev | line source |
|---|---|
| 428 | 1 /* Hash tables. |
| 2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. | |
| 2515 | 3 Copyright (C) 2003, 2004 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 | |
| 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 { | |
| 1726 | 177 xfree (hash_table->harray, hentry *); |
| 178 xfree (hash_table, struct 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 | |
| 1726 | 227 xfree (old_harray, hentry *); |
| 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 } |