Mercurial > hg > xemacs-beta
annotate src/hash.c @ 4976:16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
-------------------- ChangeLog entries follow: --------------------
src/ChangeLog addition:
2010-02-04 Ben Wing <ben@xemacs.org>
* alloc.c (release_breathing_space):
* alloc.c (resize_string):
* alloc.c (sweep_lcrecords_1):
* alloc.c (SWEEP_FIXED_TYPE_BLOCK_1):
* alloc.c (ADDITIONAL_FREE_compiled_function):
* alloc.c (compact_string_chars):
* alloc.c (ADDITIONAL_FREE_string):
* alloc.c (sweep_strings):
* alloca.c (xemacs_c_alloca):
* alsaplay.c (alsa_play_sound_file):
* buffer.c (init_initial_directory):
* buffer.h:
* buffer.h (BUFFER_FREE):
* console-stream.c (stream_delete_console):
* console-tty.c (free_tty_console_struct):
* data.c (Fnumber_to_string):
* device-gtk.c (gtk_init_device):
* device-gtk.c (free_gtk_device_struct):
* device-gtk.c (gtk_delete_device):
* device-msw.c (mswindows_delete_device):
* device-msw.c (msprinter_delete_device):
* device-tty.c (free_tty_device_struct):
* device-tty.c (tty_delete_device):
* device-x.c (x_init_device):
* device-x.c (free_x_device_struct):
* device-x.c (x_delete_device):
* dialog-msw.c (handle_directory_dialog_box):
* dialog-x.c (dbox_descriptor_to_widget_value):
* dired-msw.c (Fmswindows_insert_directory):
* dired.c (free_user_cache):
* dired.c (user_name_completion_unwind):
* doc.c (unparesseuxify_doc_string):
* doc.c (Fsubstitute_command_keys):
* doprnt.c (emacs_doprnt_1):
* dumper.c (pdump_load_finish):
* dumper.c (pdump_file_free):
* dumper.c (pdump_file_unmap):
* dynarr.c:
* dynarr.c (Dynarr_free):
* editfns.c (uncache_home_directory):
* editfns.c (Fset_time_zone_rule):
* elhash.c:
* elhash.c (pdump_reorganize_hash_table):
* elhash.c (maphash_unwind):
* emacs.c (make_arg_list_1):
* emacs.c (free_argc_argv):
* emacs.c (sort_args):
* emacs.c (Frunning_temacs_p):
* emodules.c (attempt_module_delete):
* eval.c (free_pointer):
* event-Xt.c (unselect_filedesc):
* event-Xt.c (emacs_Xt_select_process):
* event-gtk.c (unselect_filedesc):
* event-gtk.c (dragndrop_data_received):
* event-msw.c (winsock_closer):
* event-msw.c (mswindows_dde_callback):
* event-msw.c (mswindows_wnd_proc):
* event-stream.c (finalize_command_builder):
* event-stream.c (free_command_builder):
* extents.c (free_gap_array):
* extents.c (free_extent_list):
* extents.c (free_soe):
* extents.c (extent_fragment_delete):
* extents.c (extent_priority_sort_function):
* file-coding.c (make_coding_system_1):
* file-coding.c (coding_finalizer):
* file-coding.c (set_coding_stream_coding_system):
* file-coding.c (chain_finalize_coding_stream_1):
* file-coding.c (chain_finalize):
* file-coding.c (free_detection_state):
* file-coding.c (coding_category_symbol_to_id):
* fileio.c:
* fileio.c (Ffile_name_directory):
* fileio.c (if):
* fileio.c (Ffile_symlink_p):
* filelock.c (FREE_LOCK_INFO):
* filelock.c (current_lock_owner):
* font-mgr.c (Ffc_name_unparse):
* font-mgr.c (Ffc_pattern_duplicate):
* frame-gtk.c (gtk_delete_frame):
* frame-msw.c (mswindows_delete_frame):
* frame-msw.c (msprinter_delete_frame):
* frame-x.c (x_cde_destroy_callback):
* frame-x.c (Fcde_start_drag_internal):
* frame-x.c (x_cde_transfer_callback):
* frame-x.c (x_delete_frame):
* frame.c (update_frame_title):
* frame.c (Fset_frame_pointer):
* gc.c (register_for_finalization):
* gccache-gtk.c (free_gc_cache):
* gccache-gtk.c (gc_cache_lookup):
* gccache-x.c (free_gc_cache):
* gccache-x.c (gc_cache_lookup):
* glyphs-eimage.c:
* glyphs-eimage.c (jpeg_instantiate_unwind):
* glyphs-eimage.c (gif_instantiate_unwind):
* glyphs-eimage.c (png_instantiate_unwind):
* glyphs-eimage.c (png_instantiate):
* glyphs-eimage.c (tiff_instantiate_unwind):
* glyphs-gtk.c (convert_EImage_to_GDKImage):
* glyphs-gtk.c (gtk_finalize_image_instance):
* glyphs-gtk.c (gtk_init_image_instance_from_eimage):
* glyphs-gtk.c (gtk_xpm_instantiate):
* glyphs-msw.c (convert_EImage_to_DIBitmap):
* glyphs-msw.c (mswindows_init_image_instance_from_eimage):
* glyphs-msw.c (mswindows_initialize_image_instance_mask):
* glyphs-msw.c (xpm_to_eimage):
* glyphs-msw.c (mswindows_xpm_instantiate):
* glyphs-msw.c (xbm_create_bitmap_from_data):
* glyphs-msw.c (mswindows_finalize_image_instance):
* glyphs-x.c (convert_EImage_to_XImage):
* glyphs-x.c (x_finalize_image_instance):
* glyphs-x.c (x_init_image_instance_from_eimage):
* glyphs-x.c (x_xpm_instantiate):
* gui-x.c (free_popup_widget_value_tree):
* hash.c (free_hash_table):
* hash.c (grow_hash_table):
* hash.c (pregrow_hash_table_if_necessary):
* imgproc.c (build_EImage_quantable):
* insdel.c (uninit_buffer_text):
* intl-win32.c (convert_multibyte_to_internal_malloc):
* intl.c:
* intl.c (Fset_current_locale):
* keymap.c:
* keymap.c (where_is_recursive_mapper):
* keymap.c (where_is_internal):
* lisp.h:
* lisp.h (xfree):
* lstream.c (Lstream_close):
* lstream.c (resizing_buffer_closer):
* mule-coding.c:
* mule-coding.c (iso2022_finalize_detection_state):
* nt.c:
* nt.c (mswindows_get_long_filename):
* nt.c (nt_get_resource):
* nt.c (init_mswindows_environment):
* nt.c (get_cached_volume_information):
* nt.c (mswindows_opendir):
* nt.c (mswindows_closedir):
* nt.c (mswindows_readdir):
* nt.c (mswindows_stat):
* nt.c (mswindows_getdcwd):
* nt.c (Fmswindows_long_file_name):
* ntplay.c (nt_play_sound_file):
* ntplay.c (play_sound_data_1):
* number-gmp.c (gmp_free):
* number-gmp.c (init_number_gmp):
* number-mp.c (bignum_to_string):
* number-mp.c (BIGNUM_TO_TYPE):
* number.c (bignum_print):
* number.c (bignum_convfree):
* number.c (ratio_print):
* number.c (bigfloat_print):
* number.c (bigfloat_finalize):
* objects-gtk.c (gtk_finalize_color_instance):
* objects-gtk.c (gtk_finalize_font_instance):
* objects-msw.c (mswindows_finalize_color_instance):
* objects-msw.c (mswindows_finalize_font_instance):
* objects-tty.c (tty_finalize_color_instance):
* objects-tty.c (tty_finalize_font_instance):
* objects-tty.c (tty_font_list):
* objects-x.c (x_finalize_color_instance):
* objects-x.c (x_finalize_font_instance):
* process.c:
* process.c (finalize_process):
* realpath.c:
* redisplay.c (add_propagation_runes):
* regex.c:
* regex.c (xfree):
* regex.c (REGEX_FREE_STACK):
* regex.c (FREE_STACK_RETURN):
* regex.c (regex_compile):
* regex.c (regexec):
* regex.c (regfree):
* scrollbar-gtk.c (gtk_free_scrollbar_instance):
* scrollbar-gtk.c (gtk_release_scrollbar_instance):
* scrollbar-msw.c (mswindows_free_scrollbar_instance):
* scrollbar-msw.c (unshow_that_mofo):
* scrollbar-x.c (x_free_scrollbar_instance):
* scrollbar-x.c (x_release_scrollbar_instance):
* select-gtk.c (emacs_gtk_selection_handle):
* select-msw.c (mswindows_own_selection):
* select-x.c:
* select-x.c (x_handle_selection_request):
* select-x.c (unexpect_property_change):
* select-x.c (x_handle_property_notify):
* select-x.c (receive_incremental_selection):
* select-x.c (x_get_window_property_as_lisp_data):
* select-x.c (Fx_get_cutbuffer_internal):
* specifier.c (finalize_specifier):
* syntax.c (uninit_buffer_syntax_cache):
* sysdep.c (qxe_allocating_getcwd):
* sysdep.c (qxe_lstat):
* sysdep.c (copy_in_passwd):
* sysdep.c (qxe_ctime):
* sysdep.c (closedir):
* sysdep.c (DIRSIZ):
* termcap.c (tgetent):
* termcap.c (tprint):
* tests.c (Ftest_data_format_conversion):
* text.c (new_dfc_convert_copy_data):
* text.h (eifree):
* text.h (eito_alloca):
* text.h (eito_external):
* toolbar-msw.c (mswindows_output_toolbar):
* ui-gtk.c (CONVERT_RETVAL):
* ui-gtk.c (__allocate_object_storage):
* unicode.c (free_from_unicode_table):
* unicode.c (free_to_unicode_table):
* unicode.c (free_charset_unicode_tables):
* win32.c (mswindows_read_link_1):
Rename: xfree(VAL, TYPE)->xfree(VAL)
Command used:
gr 'xfree *\((.*),.*\);' 'xfree (\1);' *.[ch]
Followed by grepping for 'xfree.*,' and fixing anything left.
Rationale: Having to specify the TYPE argument is annoying and
error-prone. It was originally put in to work around warnings
due to strict aliasing but years and years ago I rewrote it
in a way that doesn't use the TYPE argument at all and no one
has complained since then. (And anyway, XEmacs is far from
ever being in compliance with strict aliasing and would require
far-reaching changes to get that way.)
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Thu, 04 Feb 2010 07:28:14 -0600 |
| parents | facf3239ba30 |
| children | 88bd4f3ef8e4 |
| 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 { | |
|
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 } |