Mercurial > hg > xemacs-beta
annotate src/elhash.c @ 5158:9e0b43d3095c
more cleanups to object-memory-usage stuff
-------------------- ChangeLog entries follow: --------------------
lisp/ChangeLog addition:
2010-03-19 Ben Wing <ben@xemacs.org>
* diagnose.el (show-object-memory-usage-stats):
Rewrite to take into account non-lisp-storage statistics
returned by garbage-collect-1 and friends.
src/ChangeLog addition:
2010-03-19 Ben Wing <ben@xemacs.org>
* alloc.c:
* alloc.c (struct):
* alloc.c (tick_lrecord_stats):
* alloc.c (gc_sweep_1):
* alloc.c (finish_object_memory_usage_stats):
* alloc.c (object_memory_usage_stats):
* alloc.c (compute_memusage_stats_length):
Call new memory-usage mechanism at sweep time to compute extra
memory utilization for all objects. Add up the values element-by-
element to get an aggregrate set of statistics, where each is the
sum of the values of a single statistic across different objects
of the same type. At end of sweep time, call
finish_object_memory_usage_stats() to add up all the aggreggrate
stats that are related to non-Lisp memory storage to compute
a single value, and add it to the list of values returned by
`garbage-collect' and `object-memory-usage-stats'.
* buffer.c (compute_buffer_text_usage):
Don't crash on buffers without text (killed buffers?) and don't
double-count indirect buffers.
* elhash.c:
* elhash.c (hash_table_objects_create):
* elhash.c (vars_of_elhash):
* symsinit.h:
Add memory-usage method to count the size of `hentries'.
* emacs.c (main_1):
Call new functions in elhash.c, frame.c at init.
* frame.c:
* frame.c (compute_frame_usage):
* frame.c (frame_memory_usage):
* frame.c (frame_objects_create):
* symsinit.h:
Add memory-usage method to count gutter display structures,
subwindow exposures.
* gc.c (gc_finish):
* lisp.h:
Declare finish_object_memory_usage_stats(), call it in gc_finish().
* lrecord.h (struct lrecord_implementation):
* lrecord.h (INIT_MEMORY_USAGE_STATS):
New value in implementation struct to track number of non-Lisp-memory
statistics. Computed in alloc.c.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Fri, 19 Mar 2010 14:47:44 -0500 |
| parents | 88bd4f3ef8e4 |
| children | 6c6d78781d59 |
| rev | line source |
|---|---|
| 428 | 1 /* Implementation of the hash table lisp object type. |
| 2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. | |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
3 Copyright (C) 1995, 1996, 2002, 2004, 2010 Ben Wing. |
| 428 | 4 Copyright (C) 1997 Free Software Foundation, Inc. |
| 5 | |
| 6 This file is part of XEmacs. | |
| 7 | |
| 8 XEmacs is free software; you can redistribute it and/or modify it | |
| 9 under the terms of the GNU General Public License as published by the | |
| 10 Free Software Foundation; either version 2, or (at your option) any | |
| 11 later version. | |
| 12 | |
| 13 XEmacs is distributed in the hope that it will be useful, but WITHOUT | |
| 14 ANY WARRANTY; without even the implied warranty of MERCNTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
| 17 | |
| 18 You should have received a copy of the GNU General Public License | |
| 19 along with XEmacs; see the file COPYING. If not, write to | |
| 20 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
| 21 Boston, MA 02111-1307, USA. */ | |
| 22 | |
| 23 /* Synched up with: Not in FSF. */ | |
| 24 | |
| 1292 | 25 /* Author: Lost in the mists of history. At least back to Lucid 19.3, |
| 26 circa Sep 1992. Early hash table implementation allowed only `eq' as a | |
| 27 test -- other tests possible only when these objects were created from | |
| 28 the C code. | |
| 29 | |
| 30 Expansion to allow general `equal'-test Lisp-creatable tables, and hash | |
| 31 methods for the various Lisp objects in existence at the time, added | |
| 32 during 19.12 I think (early 1995?), by Ben Wing. | |
| 33 | |
| 34 Weak hash tables added by Jamie (maybe?) early on, perhaps around 19.6, | |
| 35 maybe earlier; again, only possible through the C code, and only | |
| 36 supported fully weak hash tables. Expansion to other kinds of weakness, | |
| 37 and exporting of the interface to Lisp, by Ben Wing during 19.12 | |
| 38 (early-mid 1995) or maybe 19.13 cycle (mid 1995). | |
| 39 | |
| 40 Expansion to full Common Lisp spec and interface, redoing of the | |
| 41 implementation, by Martin Buchholz, 1997? (Former hash table | |
| 42 implementation used "double hashing", I'm pretty sure, and was weirdly | |
| 43 tied into the generic hash.c code. Martin completely separated them.) | |
| 44 */ | |
| 45 | |
| 489 | 46 /* This file implements the hash table lisp object type. |
| 47 | |
| 504 | 48 This implementation was mostly written by Martin Buchholz in 1997. |
| 49 | |
| 50 The Lisp-level API (derived from Common Lisp) is almost completely | |
| 51 compatible with GNU Emacs 21, even though the implementations are | |
| 52 totally independent. | |
| 53 | |
| 489 | 54 The hash table technique used is "linear probing". Collisions are |
| 55 resolved by putting the item in the next empty place in the array | |
| 56 following the collision. Finding a hash entry performs a linear | |
| 57 search in the cluster starting at the hash value. | |
| 58 | |
| 59 On deletions from the hash table, the entries immediately following | |
| 60 the deleted entry are re-entered in the hash table. We do not have | |
| 61 a special way to mark deleted entries (known as "tombstones"). | |
| 62 | |
| 63 At the end of the hash entries ("hentries"), we leave room for an | |
| 64 entry that is always empty (the "sentinel"). | |
| 65 | |
| 66 The traditional literature on hash table implementation | |
| 67 (e.g. Knuth) suggests that too much "primary clustering" occurs | |
| 68 with linear probing. However, this literature was written when | |
| 69 locality of reference was not a factor. The discrepancy between | |
| 70 CPU speeds and memory speeds is increasing, and the speed of access | |
| 71 to memory is highly dependent on memory caches which work best when | |
| 72 there is high locality of data reference. Random access to memory | |
| 73 is up to 20 times as expensive as access to the nearest address | |
| 74 (and getting worse). So linear probing makes sense. | |
| 75 | |
| 76 But the representation doesn't actually matter that much with the | |
| 77 current elisp engine. Funcall is sufficiently slow that the choice | |
| 78 of hash table implementation is noise. */ | |
| 79 | |
| 428 | 80 #include <config.h> |
| 81 #include "lisp.h" | |
| 82 #include "bytecode.h" | |
| 83 #include "elhash.h" | |
| 489 | 84 #include "opaque.h" |
| 428 | 85 |
| 86 Lisp_Object Qhash_tablep; | |
|
5084
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
87 static Lisp_Object Qhashtable, Qhash_table, Qmake_hash_table; |
| 442 | 88 static Lisp_Object Qweakness, Qvalue, Qkey_or_value, Qkey_and_value; |
| 428 | 89 static Lisp_Object Vall_weak_hash_tables; |
| 90 static Lisp_Object Qrehash_size, Qrehash_threshold; | |
| 91 static Lisp_Object Q_size, Q_test, Q_weakness, Q_rehash_size, Q_rehash_threshold; | |
| 92 | |
| 93 /* obsolete as of 19990901 in xemacs-21.2 */ | |
| 442 | 94 static Lisp_Object Qweak, Qkey_weak, Qvalue_weak, Qkey_or_value_weak; |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
95 static Lisp_Object Qnon_weak, Q_type, Q_data; |
| 428 | 96 |
| 97 struct Lisp_Hash_Table | |
| 98 { | |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
99 NORMAL_LISP_OBJECT_HEADER header; |
| 665 | 100 Elemcount size; |
| 101 Elemcount count; | |
| 102 Elemcount rehash_count; | |
| 428 | 103 double rehash_size; |
| 104 double rehash_threshold; | |
| 665 | 105 Elemcount golden_ratio; |
| 428 | 106 hash_table_hash_function_t hash_function; |
| 107 hash_table_test_function_t test_function; | |
| 1204 | 108 htentry *hentries; |
| 428 | 109 enum hash_table_weakness weakness; |
| 110 Lisp_Object next_weak; /* Used to chain together all of the weak | |
| 111 hash tables. Don't mark through this. */ | |
| 112 }; | |
| 113 | |
| 1204 | 114 #define CLEAR_HTENTRY(htentry) \ |
| 115 ((*(EMACS_UINT*)(&((htentry)->key))) = 0, \ | |
| 116 (*(EMACS_UINT*)(&((htentry)->value))) = 0) | |
| 428 | 117 |
| 118 #define HASH_TABLE_DEFAULT_SIZE 16 | |
| 119 #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3 | |
| 120 #define HASH_TABLE_MIN_SIZE 10 | |
|
4778
0081fd36b783
Cast enumerations to int before comparing them for the sake of VC++.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4777
diff
changeset
|
121 #define HASH_TABLE_DEFAULT_REHASH_THRESHOLD(size, test_function) \ |
|
4779
fd98353950a4
Make my last change to elhash.c more kosher, comparing pointers not ints
Aidan Kehoe <kehoea@parhasard.net>
parents:
4778
diff
changeset
|
122 (((size) > 4096 && NULL == (test_function)) ? 0.7 : 0.6) |
| 428 | 123 |
| 665 | 124 #define HASHCODE(key, ht) \ |
| 444 | 125 ((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \ |
| 126 * (ht)->golden_ratio) \ | |
| 127 % (ht)->size) | |
| 428 | 128 |
| 129 #define KEYS_EQUAL_P(key1, key2, testfun) \ | |
| 434 | 130 (EQ (key1, key2) || ((testfun) && (testfun) (key1, key2))) |
| 428 | 131 |
| 132 #define LINEAR_PROBING_LOOP(probe, entries, size) \ | |
| 133 for (; \ | |
| 1204 | 134 !HTENTRY_CLEAR_P (probe) || \ |
| 428 | 135 (probe == entries + size ? \ |
| 1204 | 136 (probe = entries, !HTENTRY_CLEAR_P (probe)) : 0); \ |
| 428 | 137 probe++) |
| 138 | |
| 800 | 139 #ifdef ERROR_CHECK_STRUCTURES |
| 428 | 140 static void |
| 141 check_hash_table_invariants (Lisp_Hash_Table *ht) | |
| 142 { | |
| 143 assert (ht->count < ht->size); | |
| 144 assert (ht->count <= ht->rehash_count); | |
| 145 assert (ht->rehash_count < ht->size); | |
| 146 assert ((double) ht->count * ht->rehash_threshold - 1 <= (double) ht->rehash_count); | |
| 1204 | 147 assert (HTENTRY_CLEAR_P (ht->hentries + ht->size)); |
| 428 | 148 } |
| 149 #else | |
| 150 #define check_hash_table_invariants(ht) | |
| 151 #endif | |
| 152 | |
| 153 /* Return a suitable size for a hash table, with at least SIZE slots. */ | |
| 665 | 154 static Elemcount |
| 155 hash_table_size (Elemcount requested_size) | |
| 428 | 156 { |
| 157 /* Return some prime near, but greater than or equal to, SIZE. | |
| 158 Decades from the time of writing, someone will have a system large | |
| 159 enough that the list below will be too short... */ | |
| 665 | 160 static const Elemcount primes [] = |
| 428 | 161 { |
| 162 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, | |
| 163 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, | |
| 164 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, | |
| 165 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, | |
| 166 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, | |
| 167 10445899, 13579681, 17653589, 22949669, 29834603, 38784989, | |
| 168 50420551, 65546729, 85210757, 110774011, 144006217, 187208107, | |
| 169 243370577, 316381771, 411296309, 534685237, 695090819, 903618083, | |
| 647 | 170 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */ |
| 428 | 171 }; |
| 172 /* We've heard of binary search. */ | |
| 173 int low, high; | |
| 174 for (low = 0, high = countof (primes) - 1; high - low > 1;) | |
| 175 { | |
| 176 /* Loop Invariant: size < primes [high] */ | |
| 177 int mid = (low + high) / 2; | |
| 178 if (primes [mid] < requested_size) | |
| 179 low = mid; | |
| 180 else | |
| 181 high = mid; | |
| 182 } | |
| 183 return primes [high]; | |
| 184 } | |
| 185 | |
| 186 | |
| 187 | |
| 188 static int | |
| 189 lisp_object_eql_equal (Lisp_Object obj1, Lisp_Object obj2) | |
| 190 { | |
|
4885
6772ce4d982b
Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
191 return EQ (obj1, obj2) || |
|
6772ce4d982b
Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
192 (NON_FIXNUM_NUMBER_P (obj1) && internal_equal (obj1, obj2, 0)); |
| 428 | 193 } |
| 194 | |
| 665 | 195 static Hashcode |
| 428 | 196 lisp_object_eql_hash (Lisp_Object obj) |
| 197 { | |
|
4885
6772ce4d982b
Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
198 return NON_FIXNUM_NUMBER_P (obj) ? internal_hash (obj, 0) : LISP_HASH (obj); |
| 428 | 199 } |
| 200 | |
| 201 static int | |
| 202 lisp_object_equal_equal (Lisp_Object obj1, Lisp_Object obj2) | |
| 203 { | |
| 204 return internal_equal (obj1, obj2, 0); | |
| 205 } | |
| 206 | |
| 665 | 207 static Hashcode |
| 428 | 208 lisp_object_equal_hash (Lisp_Object obj) |
| 209 { | |
| 210 return internal_hash (obj, 0); | |
| 211 } | |
| 212 | |
| 213 | |
| 214 static Lisp_Object | |
| 215 mark_hash_table (Lisp_Object obj) | |
| 216 { | |
| 217 Lisp_Hash_Table *ht = XHASH_TABLE (obj); | |
| 218 | |
| 219 /* If the hash table is weak, we don't want to mark the keys and | |
| 220 values (we scan over them after everything else has been marked, | |
| 221 and mark or remove them as necessary). */ | |
| 222 if (ht->weakness == HASH_TABLE_NON_WEAK) | |
| 223 { | |
| 1204 | 224 htentry *e, *sentinel; |
| 428 | 225 |
| 226 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) | |
| 1204 | 227 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 228 { |
| 229 mark_object (e->key); | |
| 230 mark_object (e->value); | |
| 231 } | |
| 232 } | |
| 233 return Qnil; | |
| 234 } | |
| 235 | |
| 236 /* Equality of hash tables. Two hash tables are equal when they are of | |
| 237 the same weakness and test function, they have the same number of | |
| 238 elements, and for each key in the hash table, the values are `equal'. | |
| 239 | |
| 240 This is similar to Common Lisp `equalp' of hash tables, with the | |
| 241 difference that CL requires the keys to be compared with the test | |
| 242 function, which we don't do. Doing that would require consing, and | |
| 243 consing is a bad idea in `equal'. Anyway, our method should provide | |
| 244 the same result -- if the keys are not equal according to the test | |
| 245 function, then Fgethash() in hash_table_equal_mapper() will fail. */ | |
| 246 static int | |
|
4906
6ef8256a020a
implement equalp in C, fix case-folding, add equal() method for keymaps
Ben Wing <ben@xemacs.org>
parents:
4885
diff
changeset
|
247 hash_table_equal (Lisp_Object hash_table1, Lisp_Object hash_table2, int depth, |
|
6ef8256a020a
implement equalp in C, fix case-folding, add equal() method for keymaps
Ben Wing <ben@xemacs.org>
parents:
4885
diff
changeset
|
248 int foldcase) |
| 428 | 249 { |
| 250 Lisp_Hash_Table *ht1 = XHASH_TABLE (hash_table1); | |
| 251 Lisp_Hash_Table *ht2 = XHASH_TABLE (hash_table2); | |
| 1204 | 252 htentry *e, *sentinel; |
| 428 | 253 |
| 254 if ((ht1->test_function != ht2->test_function) || | |
| 255 (ht1->weakness != ht2->weakness) || | |
| 256 (ht1->count != ht2->count)) | |
| 257 return 0; | |
| 258 | |
| 259 depth++; | |
| 260 | |
| 261 for (e = ht1->hentries, sentinel = e + ht1->size; e < sentinel; e++) | |
| 1204 | 262 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 263 /* Look up the key in the other hash table, and compare the values. */ |
| 264 { | |
| 265 Lisp_Object value_in_other = Fgethash (e->key, hash_table2, Qunbound); | |
| 266 if (UNBOUNDP (value_in_other) || | |
|
4906
6ef8256a020a
implement equalp in C, fix case-folding, add equal() method for keymaps
Ben Wing <ben@xemacs.org>
parents:
4885
diff
changeset
|
267 !internal_equal_0 (e->value, value_in_other, depth, foldcase)) |
| 428 | 268 return 0; /* Give up */ |
| 269 } | |
| 270 | |
| 271 return 1; | |
| 272 } | |
| 442 | 273 |
| 274 /* This is not a great hash function, but it _is_ correct and fast. | |
| 275 Examining all entries is too expensive, and examining a random | |
| 276 subset does not yield a correct hash function. */ | |
| 665 | 277 static Hashcode |
| 2286 | 278 hash_table_hash (Lisp_Object hash_table, int UNUSED (depth)) |
| 442 | 279 { |
| 280 return XHASH_TABLE (hash_table)->count; | |
| 281 } | |
| 282 | |
|
5158
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
283 #ifdef MEMORY_USAGE_STATS |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
284 |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
285 struct hash_table_stats |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
286 { |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
287 struct usage_stats u; |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
288 Bytecount hentries; |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
289 }; |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
290 |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
291 static void |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
292 hash_table_memory_usage (Lisp_Object hashtab, |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
293 struct generic_usage_stats *gustats) |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
294 { |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
295 Lisp_Hash_Table *ht = XHASH_TABLE (hashtab); |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
296 struct hash_table_stats *stats = (struct hash_table_stats *) gustats; |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
297 stats->hentries += |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
298 malloced_storage_size (ht->hentries, |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
299 sizeof (htentry) * (ht->size + 1), |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
300 &stats->u); |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
301 } |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
302 |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
303 #endif /* MEMORY_USAGE_STATS */ |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
304 |
| 428 | 305 |
| 306 /* Printing hash tables. | |
| 307 | |
| 308 This is non-trivial, because we use a readable structure-style | |
| 309 syntax for hash tables. This means that a typical hash table will be | |
| 310 readably printed in the form of: | |
| 311 | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
312 #s(hash-table :size 2 :data (key1 value1 key2 value2)) |
| 428 | 313 |
| 314 The supported hash table structure keywords and their values are: | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
315 `:test' (eql (or nil), eq or equal) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
316 `:size' (a natnum or nil) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
317 `:rehash-size' (a float) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
318 `:rehash-threshold' (a float) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
319 `:weakness' (nil, key, value, key-and-value, or key-or-value) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
320 `:data' (a list) |
| 428 | 321 |
| 430 | 322 If `print-readably' is nil, then a simpler syntax is used, for example |
| 428 | 323 |
| 324 #<hash-table size 2/13 data (key1 value1 key2 value2) 0x874d> | |
| 325 | |
| 326 The data is truncated to four pairs, and the rest is shown with | |
| 327 `...'. This printer does not cons. */ | |
| 328 | |
| 329 | |
| 330 /* Print the data of the hash table. This maps through a Lisp | |
| 331 hash table and prints key/value pairs using PRINTCHARFUN. */ | |
| 332 static void | |
| 333 print_hash_table_data (Lisp_Hash_Table *ht, Lisp_Object printcharfun) | |
| 334 { | |
| 335 int count = 0; | |
| 1204 | 336 htentry *e, *sentinel; |
| 428 | 337 |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
338 write_ascstring (printcharfun, " :data ("); |
| 428 | 339 |
| 340 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) | |
| 1204 | 341 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 342 { |
| 343 if (count > 0) | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
344 write_ascstring (printcharfun, " "); |
| 428 | 345 if (!print_readably && count > 3) |
| 346 { | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
347 write_ascstring (printcharfun, "..."); |
| 428 | 348 break; |
| 349 } | |
| 350 print_internal (e->key, printcharfun, 1); | |
| 800 | 351 write_fmt_string_lisp (printcharfun, " %S", 1, e->value); |
| 428 | 352 count++; |
| 353 } | |
| 354 | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
355 write_ascstring (printcharfun, ")"); |
| 428 | 356 } |
| 357 | |
| 358 static void | |
| 2286 | 359 print_hash_table (Lisp_Object obj, Lisp_Object printcharfun, |
| 360 int UNUSED (escapeflag)) | |
| 428 | 361 { |
| 362 Lisp_Hash_Table *ht = XHASH_TABLE (obj); | |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
363 Ascbyte pigbuf[350]; |
| 428 | 364 |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
365 write_ascstring (printcharfun, |
| 826 | 366 print_readably ? "#s(hash-table" : "#<hash-table"); |
| 428 | 367 |
| 368 /* These checks have a kludgy look to them, but they are safe. | |
| 369 Due to nature of hashing, you cannot use arbitrary | |
| 370 test functions anyway. */ | |
| 371 if (!ht->test_function) | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
372 write_ascstring (printcharfun, " :test eq"); |
| 428 | 373 else if (ht->test_function == lisp_object_equal_equal) |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
374 write_ascstring (printcharfun, " :test equal"); |
| 428 | 375 else if (ht->test_function == lisp_object_eql_equal) |
| 376 DO_NOTHING; | |
| 377 else | |
| 2500 | 378 ABORT (); |
| 428 | 379 |
| 380 if (ht->count || !print_readably) | |
| 381 { | |
| 382 if (print_readably) | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
383 write_fmt_string (printcharfun, " :size %ld", (long) ht->count); |
| 428 | 384 else |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
385 write_fmt_string (printcharfun, " :size %ld/%ld", (long) ht->count, |
| 800 | 386 (long) ht->size); |
| 428 | 387 } |
| 388 | |
| 389 if (ht->weakness != HASH_TABLE_NON_WEAK) | |
| 390 { | |
| 800 | 391 write_fmt_string |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
392 (printcharfun, " :weakness %s", |
| 800 | 393 (ht->weakness == HASH_TABLE_WEAK ? "key-and-value" : |
| 394 ht->weakness == HASH_TABLE_KEY_WEAK ? "key" : | |
| 395 ht->weakness == HASH_TABLE_VALUE_WEAK ? "value" : | |
| 396 ht->weakness == HASH_TABLE_KEY_VALUE_WEAK ? "key-or-value" : | |
| 397 "you-d-better-not-see-this")); | |
| 428 | 398 } |
| 399 | |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
400 if (ht->rehash_size != HASH_TABLE_DEFAULT_REHASH_SIZE) |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
401 { |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
402 float_to_string (pigbuf, ht->rehash_size); |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
403 write_fmt_string (printcharfun, " :rehash-size %s", pigbuf); |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
404 } |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
405 |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
406 if (ht->rehash_threshold |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
407 != HASH_TABLE_DEFAULT_REHASH_THRESHOLD (ht->size, |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
408 ht->test_function)) |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
409 { |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
410 float_to_string (pigbuf, ht->rehash_threshold); |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
411 write_fmt_string (printcharfun, " :rehash-threshold %s", pigbuf); |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
412 } |
|
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
413 |
| 428 | 414 if (ht->count) |
| 415 print_hash_table_data (ht, printcharfun); | |
| 416 | |
| 417 if (print_readably) | |
|
4952
19a72041c5ed
Mule-izing, various fixes related to char * arguments
Ben Wing <ben@xemacs.org>
parents:
4820
diff
changeset
|
418 write_ascstring (printcharfun, ")"); |
| 428 | 419 else |
|
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:
5142
diff
changeset
|
420 write_fmt_string (printcharfun, " 0x%x>", LISP_OBJECT_UID (obj)); |
| 428 | 421 } |
| 422 | |
| 4117 | 423 #ifndef NEW_GC |
| 428 | 424 static void |
| 4117 | 425 free_hentries (htentry *hentries, |
| 2333 | 426 #ifdef ERROR_CHECK_STRUCTURES |
|
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:
5142
diff
changeset
|
427 Elemcount size |
| 4117 | 428 #else /* not ERROR_CHECK_STRUCTURES) */ |
|
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:
5142
diff
changeset
|
429 Elemcount UNUSED (size) |
| 4117 | 430 #endif /* not ERROR_CHECK_STRUCTURES) */ |
| 2333 | 431 ) |
| 489 | 432 { |
| 800 | 433 #ifdef ERROR_CHECK_STRUCTURES |
| 489 | 434 /* Ensure a crash if other code uses the discarded entries afterwards. */ |
|
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:
5142
diff
changeset
|
435 deadbeef_memory (hentries, |
|
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:
5142
diff
changeset
|
436 (Rawbyte *) (hentries + size) - (Rawbyte *) hentries); |
| 489 | 437 #endif |
| 438 | |
| 439 if (!DUMPEDP (hentries)) | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4962
diff
changeset
|
440 xfree (hentries); |
| 489 | 441 } |
| 442 | |
| 443 static void | |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
444 finalize_hash_table (Lisp_Object obj) |
| 428 | 445 { |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
446 Lisp_Hash_Table *ht = XHASH_TABLE (obj); |
|
5124
623d57b7fbe8
separate regular and disksave finalization, print method fixes.
Ben Wing <ben@xemacs.org>
parents:
5120
diff
changeset
|
447 free_hentries (ht->hentries, ht->size); |
|
623d57b7fbe8
separate regular and disksave finalization, print method fixes.
Ben Wing <ben@xemacs.org>
parents:
5120
diff
changeset
|
448 ht->hentries = 0; |
| 428 | 449 } |
| 3263 | 450 #endif /* not NEW_GC */ |
| 428 | 451 |
| 1204 | 452 static const struct memory_description htentry_description_1[] = { |
| 453 { XD_LISP_OBJECT, offsetof (htentry, key) }, | |
| 454 { XD_LISP_OBJECT, offsetof (htentry, value) }, | |
| 428 | 455 { XD_END } |
| 456 }; | |
| 457 | |
| 1204 | 458 static const struct sized_memory_description htentry_description = { |
| 459 sizeof (htentry), | |
| 460 htentry_description_1 | |
| 428 | 461 }; |
| 462 | |
| 3092 | 463 #ifdef NEW_GC |
| 464 static const struct memory_description htentry_weak_description_1[] = { | |
| 465 { XD_LISP_OBJECT, offsetof (htentry, key), 0, { 0 }, XD_FLAG_NO_KKCC}, | |
| 466 { XD_LISP_OBJECT, offsetof (htentry, value), 0, { 0 }, XD_FLAG_NO_KKCC}, | |
| 467 { XD_END } | |
| 468 }; | |
| 469 | |
| 470 static const struct sized_memory_description htentry_weak_description = { | |
| 471 sizeof (htentry), | |
| 472 htentry_weak_description_1 | |
| 473 }; | |
| 474 | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
475 DEFINE_DUMPABLE_INTERNAL_LISP_OBJECT ("hash-table-entry", hash_table_entry, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
476 0, htentry_description_1, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
477 Lisp_Hash_Table_Entry); |
| 3092 | 478 #endif /* NEW_GC */ |
| 479 | |
| 1204 | 480 static const struct memory_description htentry_union_description_1[] = { |
| 481 /* Note: XD_INDIRECT in this table refers to the surrounding table, | |
| 482 and so this will work. */ | |
| 3092 | 483 #ifdef NEW_GC |
| 484 { XD_LISP_OBJECT_BLOCK_PTR, HASH_TABLE_NON_WEAK, | |
| 485 XD_INDIRECT (0, 1), { &htentry_description } }, | |
| 486 { XD_LISP_OBJECT_BLOCK_PTR, 0, XD_INDIRECT (0, 1), | |
| 487 { &htentry_weak_description }, XD_FLAG_UNION_DEFAULT_ENTRY }, | |
| 488 #else /* not NEW_GC */ | |
| 2367 | 489 { XD_BLOCK_PTR, HASH_TABLE_NON_WEAK, XD_INDIRECT (0, 1), |
| 2551 | 490 { &htentry_description } }, |
| 491 { XD_BLOCK_PTR, 0, XD_INDIRECT (0, 1), { &htentry_description }, | |
| 1204 | 492 XD_FLAG_UNION_DEFAULT_ENTRY | XD_FLAG_NO_KKCC }, |
| 3092 | 493 #endif /* not NEW_GC */ |
| 1204 | 494 { XD_END } |
| 495 }; | |
| 496 | |
| 497 static const struct sized_memory_description htentry_union_description = { | |
| 498 sizeof (htentry *), | |
| 499 htentry_union_description_1 | |
| 500 }; | |
| 501 | |
| 502 const struct memory_description hash_table_description[] = { | |
| 503 { XD_ELEMCOUNT, offsetof (Lisp_Hash_Table, size) }, | |
| 504 { XD_INT, offsetof (Lisp_Hash_Table, weakness) }, | |
| 505 { XD_UNION, offsetof (Lisp_Hash_Table, hentries), XD_INDIRECT (1, 0), | |
| 2551 | 506 { &htentry_union_description } }, |
| 440 | 507 { XD_LO_LINK, offsetof (Lisp_Hash_Table, next_weak) }, |
| 428 | 508 { XD_END } |
| 509 }; | |
| 510 | |
| 3263 | 511 #ifdef NEW_GC |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
512 DEFINE_DUMPABLE_LISP_OBJECT ("hash-table", hash_table, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
513 mark_hash_table, print_hash_table, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
514 0, hash_table_equal, hash_table_hash, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
515 hash_table_description, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
516 Lisp_Hash_Table); |
| 3263 | 517 #else /* not NEW_GC */ |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
518 DEFINE_DUMPABLE_LISP_OBJECT ("hash-table", hash_table, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
519 mark_hash_table, print_hash_table, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
520 finalize_hash_table, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
521 hash_table_equal, hash_table_hash, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
522 hash_table_description, |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
523 Lisp_Hash_Table); |
| 3263 | 524 #endif /* not NEW_GC */ |
| 428 | 525 |
| 526 static Lisp_Hash_Table * | |
| 527 xhash_table (Lisp_Object hash_table) | |
| 528 { | |
| 1123 | 529 /* #### What's going on here? Why the gc_in_progress check? */ |
| 428 | 530 if (!gc_in_progress) |
| 531 CHECK_HASH_TABLE (hash_table); | |
| 532 check_hash_table_invariants (XHASH_TABLE (hash_table)); | |
| 533 return XHASH_TABLE (hash_table); | |
| 534 } | |
| 535 | |
| 536 | |
| 537 /************************************************************************/ | |
| 538 /* Creation of Hash Tables */ | |
| 539 /************************************************************************/ | |
| 540 | |
| 541 /* Creation of hash tables, without error-checking. */ | |
| 542 static void | |
| 543 compute_hash_table_derived_values (Lisp_Hash_Table *ht) | |
| 544 { | |
| 665 | 545 ht->rehash_count = (Elemcount) |
| 438 | 546 ((double) ht->size * ht->rehash_threshold); |
| 665 | 547 ht->golden_ratio = (Elemcount) |
| 428 | 548 ((double) ht->size * (.6180339887 / (double) sizeof (Lisp_Object))); |
| 549 } | |
| 550 | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
551 static htentry * |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
552 allocate_hash_table_entries (Elemcount size) |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
553 { |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
554 #ifdef NEW_GC |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
555 return XHASH_TABLE_ENTRY (alloc_lrecord_array |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
556 (size, &lrecord_hash_table_entry)); |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
557 #else /* not NEW_GC */ |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
558 return xnew_array_and_zero (htentry, size); |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
559 #endif /* not NEW_GC */ |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
560 } |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
561 |
| 428 | 562 Lisp_Object |
| 450 | 563 make_standard_lisp_hash_table (enum hash_table_test test, |
| 665 | 564 Elemcount size, |
| 450 | 565 double rehash_size, |
| 566 double rehash_threshold, | |
| 567 enum hash_table_weakness weakness) | |
| 568 { | |
| 462 | 569 hash_table_hash_function_t hash_function = 0; |
| 450 | 570 hash_table_test_function_t test_function = 0; |
| 571 | |
| 572 switch (test) | |
| 573 { | |
| 574 case HASH_TABLE_EQ: | |
| 575 test_function = 0; | |
| 576 hash_function = 0; | |
| 577 break; | |
| 578 | |
| 579 case HASH_TABLE_EQL: | |
| 580 test_function = lisp_object_eql_equal; | |
| 581 hash_function = lisp_object_eql_hash; | |
| 582 break; | |
| 583 | |
| 584 case HASH_TABLE_EQUAL: | |
| 585 test_function = lisp_object_equal_equal; | |
| 586 hash_function = lisp_object_equal_hash; | |
| 587 break; | |
| 588 | |
| 589 default: | |
| 2500 | 590 ABORT (); |
| 450 | 591 } |
| 592 | |
| 593 return make_general_lisp_hash_table (hash_function, test_function, | |
| 594 size, rehash_size, rehash_threshold, | |
| 595 weakness); | |
| 596 } | |
| 597 | |
| 598 Lisp_Object | |
| 599 make_general_lisp_hash_table (hash_table_hash_function_t hash_function, | |
| 600 hash_table_test_function_t test_function, | |
| 665 | 601 Elemcount size, |
| 428 | 602 double rehash_size, |
| 603 double rehash_threshold, | |
| 604 enum hash_table_weakness weakness) | |
| 605 { | |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
606 Lisp_Object hash_table = ALLOC_NORMAL_LISP_OBJECT (hash_table); |
|
5117
3742ea8250b5
Checking in final CVS version of workspace 'ben-lisp-object'
Ben Wing <ben@xemacs.org>
parents:
3017
diff
changeset
|
607 Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); |
| 428 | 608 |
| 450 | 609 ht->test_function = test_function; |
| 610 ht->hash_function = hash_function; | |
| 438 | 611 ht->weakness = weakness; |
| 612 | |
| 613 ht->rehash_size = | |
| 614 rehash_size > 1.0 ? rehash_size : HASH_TABLE_DEFAULT_REHASH_SIZE; | |
| 615 | |
| 616 ht->rehash_threshold = | |
| 617 rehash_threshold > 0.0 ? rehash_threshold : | |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
618 HASH_TABLE_DEFAULT_REHASH_THRESHOLD (size, ht->test_function); |
| 438 | 619 |
| 428 | 620 if (size < HASH_TABLE_MIN_SIZE) |
| 621 size = HASH_TABLE_MIN_SIZE; | |
| 665 | 622 ht->size = hash_table_size ((Elemcount) (((double) size / ht->rehash_threshold) |
| 438 | 623 + 1.0)); |
| 428 | 624 ht->count = 0; |
| 438 | 625 |
| 428 | 626 compute_hash_table_derived_values (ht); |
| 627 | |
| 1204 | 628 /* We leave room for one never-occupied sentinel htentry at the end. */ |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
629 ht->hentries = allocate_hash_table_entries (ht->size + 1); |
| 428 | 630 |
| 631 if (weakness == HASH_TABLE_NON_WEAK) | |
| 632 ht->next_weak = Qunbound; | |
| 633 else | |
| 634 ht->next_weak = Vall_weak_hash_tables, Vall_weak_hash_tables = hash_table; | |
| 635 | |
| 636 return hash_table; | |
| 637 } | |
| 638 | |
| 639 Lisp_Object | |
| 665 | 640 make_lisp_hash_table (Elemcount size, |
| 428 | 641 enum hash_table_weakness weakness, |
| 642 enum hash_table_test test) | |
| 643 { | |
| 450 | 644 return make_standard_lisp_hash_table (test, size, -1.0, -1.0, weakness); |
| 428 | 645 } |
| 646 | |
| 647 /* Pretty reading of hash tables. | |
| 648 | |
| 649 Here we use the existing structures mechanism (which is, | |
| 650 unfortunately, pretty cumbersome) for validating and instantiating | |
| 651 the hash tables. The idea is that the side-effect of reading a | |
| 652 #s(hash-table PLIST) object is creation of a hash table with desired | |
| 653 properties, and that the hash table is returned. */ | |
| 654 | |
| 655 /* Validation functions: each keyword provides its own validation | |
| 656 function. The errors should maybe be continuable, but it is | |
| 657 unclear how this would cope with ERRB. */ | |
| 658 static int | |
| 2286 | 659 hash_table_size_validate (Lisp_Object UNUSED (keyword), Lisp_Object value, |
| 660 Error_Behavior errb) | |
| 428 | 661 { |
| 662 if (NATNUMP (value)) | |
| 663 return 1; | |
| 664 | |
| 563 | 665 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qnatnump, value), |
| 2286 | 666 Qhash_table, errb); |
| 428 | 667 return 0; |
| 668 } | |
| 669 | |
| 665 | 670 static Elemcount |
| 428 | 671 decode_hash_table_size (Lisp_Object obj) |
| 672 { | |
| 673 return NILP (obj) ? HASH_TABLE_DEFAULT_SIZE : XINT (obj); | |
| 674 } | |
| 675 | |
| 676 static int | |
| 2286 | 677 hash_table_weakness_validate (Lisp_Object UNUSED (keyword), Lisp_Object value, |
| 578 | 678 Error_Behavior errb) |
| 428 | 679 { |
| 442 | 680 if (EQ (value, Qnil)) return 1; |
| 681 if (EQ (value, Qt)) return 1; | |
| 682 if (EQ (value, Qkey)) return 1; | |
| 683 if (EQ (value, Qkey_and_value)) return 1; | |
| 684 if (EQ (value, Qkey_or_value)) return 1; | |
| 685 if (EQ (value, Qvalue)) return 1; | |
| 428 | 686 |
| 687 /* Following values are obsolete as of 19990901 in xemacs-21.2 */ | |
| 442 | 688 if (EQ (value, Qnon_weak)) return 1; |
| 689 if (EQ (value, Qweak)) return 1; | |
| 690 if (EQ (value, Qkey_weak)) return 1; | |
| 691 if (EQ (value, Qkey_or_value_weak)) return 1; | |
| 692 if (EQ (value, Qvalue_weak)) return 1; | |
| 428 | 693 |
| 563 | 694 maybe_invalid_constant ("Invalid hash table weakness", |
| 428 | 695 value, Qhash_table, errb); |
| 696 return 0; | |
| 697 } | |
| 698 | |
| 699 static enum hash_table_weakness | |
| 700 decode_hash_table_weakness (Lisp_Object obj) | |
| 701 { | |
| 442 | 702 if (EQ (obj, Qnil)) return HASH_TABLE_NON_WEAK; |
| 703 if (EQ (obj, Qt)) return HASH_TABLE_WEAK; | |
| 704 if (EQ (obj, Qkey_and_value)) return HASH_TABLE_WEAK; | |
| 705 if (EQ (obj, Qkey)) return HASH_TABLE_KEY_WEAK; | |
| 706 if (EQ (obj, Qkey_or_value)) return HASH_TABLE_KEY_VALUE_WEAK; | |
| 707 if (EQ (obj, Qvalue)) return HASH_TABLE_VALUE_WEAK; | |
| 428 | 708 |
| 709 /* Following values are obsolete as of 19990901 in xemacs-21.2 */ | |
| 442 | 710 if (EQ (obj, Qnon_weak)) return HASH_TABLE_NON_WEAK; |
| 711 if (EQ (obj, Qweak)) return HASH_TABLE_WEAK; | |
| 712 if (EQ (obj, Qkey_weak)) return HASH_TABLE_KEY_WEAK; | |
| 713 if (EQ (obj, Qkey_or_value_weak)) return HASH_TABLE_KEY_VALUE_WEAK; | |
| 714 if (EQ (obj, Qvalue_weak)) return HASH_TABLE_VALUE_WEAK; | |
| 428 | 715 |
| 563 | 716 invalid_constant ("Invalid hash table weakness", obj); |
| 1204 | 717 RETURN_NOT_REACHED (HASH_TABLE_NON_WEAK); |
| 428 | 718 } |
| 719 | |
| 720 static int | |
| 2286 | 721 hash_table_test_validate (Lisp_Object UNUSED (keyword), Lisp_Object value, |
| 722 Error_Behavior errb) | |
| 428 | 723 { |
| 724 if (EQ (value, Qnil)) return 1; | |
| 725 if (EQ (value, Qeq)) return 1; | |
| 726 if (EQ (value, Qequal)) return 1; | |
| 727 if (EQ (value, Qeql)) return 1; | |
| 728 | |
| 563 | 729 maybe_invalid_constant ("Invalid hash table test", |
| 2286 | 730 value, Qhash_table, errb); |
| 428 | 731 return 0; |
| 732 } | |
| 733 | |
| 734 static enum hash_table_test | |
| 735 decode_hash_table_test (Lisp_Object obj) | |
| 736 { | |
| 737 if (EQ (obj, Qnil)) return HASH_TABLE_EQL; | |
| 738 if (EQ (obj, Qeq)) return HASH_TABLE_EQ; | |
| 739 if (EQ (obj, Qequal)) return HASH_TABLE_EQUAL; | |
| 740 if (EQ (obj, Qeql)) return HASH_TABLE_EQL; | |
| 741 | |
| 563 | 742 invalid_constant ("Invalid hash table test", obj); |
| 1204 | 743 RETURN_NOT_REACHED (HASH_TABLE_EQ); |
| 428 | 744 } |
| 745 | |
| 746 static int | |
| 2286 | 747 hash_table_rehash_size_validate (Lisp_Object UNUSED (keyword), |
| 748 Lisp_Object value, Error_Behavior errb) | |
| 428 | 749 { |
| 750 if (!FLOATP (value)) | |
| 751 { | |
| 563 | 752 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qfloatp, value), |
| 428 | 753 Qhash_table, errb); |
| 754 return 0; | |
| 755 } | |
| 756 | |
| 757 { | |
| 758 double rehash_size = XFLOAT_DATA (value); | |
| 759 if (rehash_size <= 1.0) | |
| 760 { | |
| 563 | 761 maybe_invalid_argument |
| 428 | 762 ("Hash table rehash size must be greater than 1.0", |
| 763 value, Qhash_table, errb); | |
| 764 return 0; | |
| 765 } | |
| 766 } | |
| 767 | |
| 768 return 1; | |
| 769 } | |
| 770 | |
| 771 static double | |
| 772 decode_hash_table_rehash_size (Lisp_Object rehash_size) | |
| 773 { | |
|
4585
871eb054b34a
Document non-obvious usages.
Stephen J. Turnbull <stephen@xemacs.org>
parents:
4410
diff
changeset
|
774 /* -1.0 signals make_general_lisp_hash_table to use the default. */ |
| 428 | 775 return NILP (rehash_size) ? -1.0 : XFLOAT_DATA (rehash_size); |
| 776 } | |
| 777 | |
| 778 static int | |
| 2286 | 779 hash_table_rehash_threshold_validate (Lisp_Object UNUSED (keyword), |
| 780 Lisp_Object value, Error_Behavior errb) | |
| 428 | 781 { |
| 782 if (!FLOATP (value)) | |
| 783 { | |
| 563 | 784 maybe_signal_error_1 (Qwrong_type_argument, list2 (Qfloatp, value), |
| 428 | 785 Qhash_table, errb); |
| 786 return 0; | |
| 787 } | |
| 788 | |
| 789 { | |
| 790 double rehash_threshold = XFLOAT_DATA (value); | |
| 791 if (rehash_threshold <= 0.0 || rehash_threshold >= 1.0) | |
| 792 { | |
| 563 | 793 maybe_invalid_argument |
| 428 | 794 ("Hash table rehash threshold must be between 0.0 and 1.0", |
| 795 value, Qhash_table, errb); | |
| 796 return 0; | |
| 797 } | |
| 798 } | |
| 799 | |
| 800 return 1; | |
| 801 } | |
| 802 | |
| 803 static double | |
| 804 decode_hash_table_rehash_threshold (Lisp_Object rehash_threshold) | |
| 805 { | |
|
4585
871eb054b34a
Document non-obvious usages.
Stephen J. Turnbull <stephen@xemacs.org>
parents:
4410
diff
changeset
|
806 /* -1.0 signals make_general_lisp_hash_table to use the default. */ |
| 428 | 807 return NILP (rehash_threshold) ? -1.0 : XFLOAT_DATA (rehash_threshold); |
| 808 } | |
| 809 | |
| 810 static int | |
| 2286 | 811 hash_table_data_validate (Lisp_Object UNUSED (keyword), Lisp_Object value, |
| 812 Error_Behavior errb) | |
| 428 | 813 { |
| 814 int len; | |
| 815 | |
|
4585
871eb054b34a
Document non-obvious usages.
Stephen J. Turnbull <stephen@xemacs.org>
parents:
4410
diff
changeset
|
816 /* Check for improper lists while getting length. */ |
| 428 | 817 GET_EXTERNAL_LIST_LENGTH (value, len); |
| 818 | |
| 819 if (len & 1) | |
| 820 { | |
| 563 | 821 maybe_sferror |
| 428 | 822 ("Hash table data must have alternating key/value pairs", |
| 823 value, Qhash_table, errb); | |
| 824 return 0; | |
| 825 } | |
|
4585
871eb054b34a
Document non-obvious usages.
Stephen J. Turnbull <stephen@xemacs.org>
parents:
4410
diff
changeset
|
826 |
| 428 | 827 return 1; |
| 828 } | |
| 829 | |
| 830 /* The actual instantiation of a hash table. This does practically no | |
| 831 error checking, because it relies on the fact that the paranoid | |
| 832 functions above have error-checked everything to the last details. | |
| 833 If this assumption is wrong, we will get a crash immediately (with | |
| 834 error-checking compiled in), and we'll know if there is a bug in | |
| 835 the structure mechanism. So there. */ | |
| 836 static Lisp_Object | |
| 837 hash_table_instantiate (Lisp_Object plist) | |
| 838 { | |
| 839 Lisp_Object hash_table; | |
| 840 Lisp_Object test = Qnil; | |
| 841 Lisp_Object size = Qnil; | |
| 842 Lisp_Object rehash_size = Qnil; | |
| 843 Lisp_Object rehash_threshold = Qnil; | |
| 844 Lisp_Object weakness = Qnil; | |
| 845 Lisp_Object data = Qnil; | |
| 846 | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
847 if (KEYWORDP (Fcar (plist))) |
| 428 | 848 { |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
849 PROPERTY_LIST_LOOP_3 (key, value, plist) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
850 { |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
851 if (EQ (key, Q_test)) test = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
852 else if (EQ (key, Q_size)) size = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
853 else if (EQ (key, Q_rehash_size)) rehash_size = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
854 else if (EQ (key, Q_rehash_threshold)) rehash_threshold = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
855 else if (EQ (key, Q_weakness)) weakness = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
856 else if (EQ (key, Q_data)) data = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
857 else if (!KEYWORDP (key)) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
858 signal_error (Qinvalid_read_syntax, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
859 "can't mix keyword and non-keyword hash table syntax", |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
860 key); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
861 else ABORT(); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
862 } |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
863 } |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
864 else |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
865 { |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
866 PROPERTY_LIST_LOOP_3 (key, value, plist) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
867 { |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
868 if (EQ (key, Qtest)) test = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
869 else if (EQ (key, Qsize)) size = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
870 else if (EQ (key, Qrehash_size)) rehash_size = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
871 else if (EQ (key, Qrehash_threshold)) rehash_threshold = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
872 else if (EQ (key, Qweakness)) weakness = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
873 else if (EQ (key, Qdata)) data = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
874 else if (EQ (key, Qtype))/*obsolete*/ weakness = value; |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
875 else if (KEYWORDP (key)) |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
876 signal_error (Qinvalid_read_syntax, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
877 "can't mix keyword and non-keyword hash table syntax", |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
878 key); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
879 else ABORT(); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
880 } |
| 428 | 881 } |
| 882 | |
| 883 /* Create the hash table. */ | |
| 450 | 884 hash_table = make_standard_lisp_hash_table |
| 428 | 885 (decode_hash_table_test (test), |
| 886 decode_hash_table_size (size), | |
| 887 decode_hash_table_rehash_size (rehash_size), | |
| 888 decode_hash_table_rehash_threshold (rehash_threshold), | |
| 889 decode_hash_table_weakness (weakness)); | |
| 890 | |
| 891 /* I'm not sure whether this can GC, but better safe than sorry. */ | |
| 892 { | |
| 893 struct gcpro gcpro1; | |
| 894 GCPRO1 (hash_table); | |
| 895 | |
| 896 /* And fill it with data. */ | |
| 897 while (!NILP (data)) | |
| 898 { | |
| 899 Lisp_Object key, value; | |
| 900 key = XCAR (data); data = XCDR (data); | |
| 901 value = XCAR (data); data = XCDR (data); | |
| 902 Fputhash (key, value, hash_table); | |
| 903 } | |
| 904 UNGCPRO; | |
| 905 } | |
| 906 | |
| 907 return hash_table; | |
| 908 } | |
| 909 | |
| 910 static void | |
| 911 structure_type_create_hash_table_structure_name (Lisp_Object structure_name) | |
| 912 { | |
| 913 struct structure_type *st; | |
| 914 | |
| 915 st = define_structure_type (structure_name, 0, hash_table_instantiate); | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
916 |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
917 /* First the keyword syntax: */ |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
918 define_structure_type_keyword (st, Q_test, hash_table_test_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
919 define_structure_type_keyword (st, Q_size, hash_table_size_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
920 define_structure_type_keyword (st, Q_rehash_size, hash_table_rehash_size_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
921 define_structure_type_keyword (st, Q_rehash_threshold, hash_table_rehash_threshold_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
922 define_structure_type_keyword (st, Q_weakness, hash_table_weakness_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
923 define_structure_type_keyword (st, Q_data, hash_table_data_validate); |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
924 |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
925 /* Next the mutually exclusive, older, non-keyword syntax: */ |
| 428 | 926 define_structure_type_keyword (st, Qtest, hash_table_test_validate); |
| 927 define_structure_type_keyword (st, Qsize, hash_table_size_validate); | |
| 928 define_structure_type_keyword (st, Qrehash_size, hash_table_rehash_size_validate); | |
| 929 define_structure_type_keyword (st, Qrehash_threshold, hash_table_rehash_threshold_validate); | |
| 930 define_structure_type_keyword (st, Qweakness, hash_table_weakness_validate); | |
| 931 define_structure_type_keyword (st, Qdata, hash_table_data_validate); | |
| 932 | |
| 933 /* obsolete as of 19990901 in xemacs-21.2 */ | |
| 934 define_structure_type_keyword (st, Qtype, hash_table_weakness_validate); | |
| 935 } | |
| 936 | |
| 937 /* Create a built-in Lisp structure type named `hash-table'. | |
| 938 We make #s(hashtable ...) equivalent to #s(hash-table ...), | |
| 939 for backward compatibility. | |
| 940 This is called from emacs.c. */ | |
| 941 void | |
| 942 structure_type_create_hash_table (void) | |
| 943 { | |
| 944 structure_type_create_hash_table_structure_name (Qhash_table); | |
| 945 structure_type_create_hash_table_structure_name (Qhashtable); /* compat */ | |
| 946 } | |
| 947 | |
| 948 | |
| 949 /************************************************************************/ | |
| 950 /* Definition of Lisp-visible methods */ | |
| 951 /************************************************************************/ | |
| 952 | |
| 953 DEFUN ("hash-table-p", Fhash_table_p, 1, 1, 0, /* | |
| 954 Return t if OBJECT is a hash table, else nil. | |
| 955 */ | |
| 956 (object)) | |
| 957 { | |
| 958 return HASH_TABLEP (object) ? Qt : Qnil; | |
| 959 } | |
| 960 | |
| 961 DEFUN ("make-hash-table", Fmake_hash_table, 0, MANY, 0, /* | |
| 962 Return a new empty hash table object. | |
| 963 Use Common Lisp style keywords to specify hash table properties. | |
| 964 | |
| 965 Keyword :test can be `eq', `eql' (default) or `equal'. | |
| 966 Comparison between keys is done using this function. | |
| 967 If speed is important, consider using `eq'. | |
| 968 When storing strings in the hash table, you will likely need to use `equal'. | |
| 969 | |
| 970 Keyword :size specifies the number of keys likely to be inserted. | |
| 971 This number of entries can be inserted without enlarging the hash table. | |
| 972 | |
| 973 Keyword :rehash-size must be a float greater than 1.0, and specifies | |
| 974 the factor by which to increase the size of the hash table when enlarging. | |
| 975 | |
| 976 Keyword :rehash-threshold must be a float between 0.0 and 1.0, | |
| 977 and specifies the load factor of the hash table which triggers enlarging. | |
| 978 | |
| 442 | 979 Non-standard keyword :weakness can be `nil' (default), `t', `key-and-value', |
| 980 `key', `value' or `key-or-value'. `t' is an alias for `key-and-value'. | |
| 428 | 981 |
| 442 | 982 A key-and-value-weak hash table, also known as a fully-weak or simply |
| 983 as a weak hash table, is one whose pointers do not count as GC | |
| 984 referents: for any key-value pair in the hash table, if the only | |
| 985 remaining pointer to either the key or the value is in a weak hash | |
| 986 table, then the pair will be removed from the hash table, and the key | |
| 987 and value collected. A non-weak hash table (or any other pointer) | |
| 988 would prevent the object from being collected. | |
| 428 | 989 |
| 990 A key-weak hash table is similar to a fully-weak hash table except that | |
| 991 a key-value pair will be removed only if the key remains unmarked | |
| 992 outside of weak hash tables. The pair will remain in the hash table if | |
| 993 the key is pointed to by something other than a weak hash table, even | |
| 994 if the value is not. | |
| 995 | |
| 996 A value-weak hash table is similar to a fully-weak hash table except | |
| 997 that a key-value pair will be removed only if the value remains | |
| 998 unmarked outside of weak hash tables. The pair will remain in the | |
| 999 hash table if the value is pointed to by something other than a weak | |
| 1000 hash table, even if the key is not. | |
| 442 | 1001 |
| 1002 A key-or-value-weak hash table is similar to a fully-weak hash table except | |
| 1003 that a key-value pair will be removed only if the value and the key remain | |
| 1004 unmarked outside of weak hash tables. The pair will remain in the | |
| 1005 hash table if the value or key are pointed to by something other than a weak | |
| 1006 hash table, even if the other is not. | |
|
4693
80cd90837ac5
Add argument information to remaining MANY or UNEVALLED C subrs.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4585
diff
changeset
|
1007 |
|
4777
c69aeb86b2a3
Serialise non-default hash table rehash thresholds correctly; use this.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4693
diff
changeset
|
1008 arguments: (&key TEST SIZE REHASH-SIZE REHASH-THRESHOLD WEAKNESS) |
| 428 | 1009 */ |
| 1010 (int nargs, Lisp_Object *args)) | |
| 1011 { | |
|
5084
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1012 #ifdef NO_NEED_TO_HANDLE_21_4_CODE |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1013 PARSE_KEYWORDS (Qmake_hash_table, nargs, args, 0, 5, |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1014 (test, size, rehash_size, rehash_threshold, weakness), |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1015 NULL, weakness = Qunbound), 0); |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1016 #else |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1017 PARSE_KEYWORDS (Qmake_hash_table, nargs, args, 0, 6, |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1018 (test, size, rehash_size, rehash_threshold, weakness, |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1019 type), (type = Qunbound, weakness = Qunbound), 0); |
| 428 | 1020 |
|
5084
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1021 if (EQ (weakness, Qunbound)) |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1022 { |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1023 if (EQ (weakness, Qunbound) && !EQ (type, Qunbound)) |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1024 { |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1025 weakness = type; |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1026 } |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1027 else |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1028 { |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1029 weakness = Qnil; |
|
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1030 } |
| 428 | 1031 } |
|
5084
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1032 #endif |
| 428 | 1033 |
| 1034 #define VALIDATE_VAR(var) \ | |
| 1035 if (!NILP (var)) hash_table_##var##_validate (Q##var, var, ERROR_ME); | |
| 1036 | |
| 1037 VALIDATE_VAR (test); | |
| 1038 VALIDATE_VAR (size); | |
| 1039 VALIDATE_VAR (rehash_size); | |
| 1040 VALIDATE_VAR (rehash_threshold); | |
| 1041 VALIDATE_VAR (weakness); | |
| 1042 | |
| 450 | 1043 return make_standard_lisp_hash_table |
| 428 | 1044 (decode_hash_table_test (test), |
| 1045 decode_hash_table_size (size), | |
| 1046 decode_hash_table_rehash_size (rehash_size), | |
| 1047 decode_hash_table_rehash_threshold (rehash_threshold), | |
| 1048 decode_hash_table_weakness (weakness)); | |
| 1049 } | |
| 1050 | |
| 1051 DEFUN ("copy-hash-table", Fcopy_hash_table, 1, 1, 0, /* | |
| 1052 Return a new hash table containing the same keys and values as HASH-TABLE. | |
| 1053 The keys and values will not themselves be copied. | |
| 1054 */ | |
| 1055 (hash_table)) | |
| 1056 { | |
| 442 | 1057 const Lisp_Hash_Table *ht_old = xhash_table (hash_table); |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
1058 Lisp_Object obj = ALLOC_NORMAL_LISP_OBJECT (hash_table); |
|
5117
3742ea8250b5
Checking in final CVS version of workspace 'ben-lisp-object'
Ben Wing <ben@xemacs.org>
parents:
3017
diff
changeset
|
1059 Lisp_Hash_Table *ht = XHASH_TABLE (obj); |
|
5127
a9c41067dd88
more cleanups, terminology clarification, lots of doc work
Ben Wing <ben@xemacs.org>
parents:
5125
diff
changeset
|
1060 copy_lisp_object (obj, hash_table); |
| 428 | 1061 |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1062 /* We leave room for one never-occupied sentinel htentry at the end. */ |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1063 ht->hentries = allocate_hash_table_entries (ht_old->size + 1); |
| 1204 | 1064 memcpy (ht->hentries, ht_old->hentries, (ht_old->size + 1) * sizeof (htentry)); |
| 428 | 1065 |
| 1066 if (! EQ (ht->next_weak, Qunbound)) | |
| 1067 { | |
| 1068 ht->next_weak = Vall_weak_hash_tables; | |
|
5117
3742ea8250b5
Checking in final CVS version of workspace 'ben-lisp-object'
Ben Wing <ben@xemacs.org>
parents:
3017
diff
changeset
|
1069 Vall_weak_hash_tables = obj; |
| 428 | 1070 } |
| 1071 | |
|
5117
3742ea8250b5
Checking in final CVS version of workspace 'ben-lisp-object'
Ben Wing <ben@xemacs.org>
parents:
3017
diff
changeset
|
1072 return obj; |
| 428 | 1073 } |
| 1074 | |
| 1075 static void | |
| 665 | 1076 resize_hash_table (Lisp_Hash_Table *ht, Elemcount new_size) |
| 428 | 1077 { |
| 1204 | 1078 htentry *old_entries, *new_entries, *sentinel, *e; |
| 665 | 1079 Elemcount old_size; |
| 428 | 1080 |
| 1081 old_size = ht->size; | |
| 1082 ht->size = new_size; | |
| 1083 | |
| 1084 old_entries = ht->hentries; | |
| 1085 | |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1086 /* We leave room for one never-occupied sentinel htentry at the end. */ |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1087 ht->hentries = allocate_hash_table_entries (new_size + 1); |
| 428 | 1088 new_entries = ht->hentries; |
| 1089 | |
| 1090 compute_hash_table_derived_values (ht); | |
| 1091 | |
| 440 | 1092 for (e = old_entries, sentinel = e + old_size; e < sentinel; e++) |
| 1204 | 1093 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1094 { |
| 1204 | 1095 htentry *probe = new_entries + HASHCODE (e->key, ht); |
| 428 | 1096 LINEAR_PROBING_LOOP (probe, new_entries, new_size) |
| 1097 ; | |
| 1098 *probe = *e; | |
| 1099 } | |
| 1100 | |
| 4117 | 1101 #ifndef NEW_GC |
| 489 | 1102 free_hentries (old_entries, old_size); |
| 4117 | 1103 #endif /* not NEW_GC */ |
| 428 | 1104 } |
| 1105 | |
| 440 | 1106 /* After a hash table has been saved to disk and later restored by the |
| 1107 portable dumper, it contains the same objects, but their addresses | |
| 665 | 1108 and thus their HASHCODEs have changed. */ |
| 428 | 1109 void |
| 440 | 1110 pdump_reorganize_hash_table (Lisp_Object hash_table) |
| 428 | 1111 { |
| 442 | 1112 const Lisp_Hash_Table *ht = xhash_table (hash_table); |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1113 /* We leave room for one never-occupied sentinel htentry at the end. */ |
|
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1114 htentry *new_entries = allocate_hash_table_entries (ht->size + 1); |
| 1204 | 1115 htentry *e, *sentinel; |
| 440 | 1116 |
| 1117 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) | |
| 1204 | 1118 if (!HTENTRY_CLEAR_P (e)) |
| 440 | 1119 { |
| 1204 | 1120 htentry *probe = new_entries + HASHCODE (e->key, ht); |
| 440 | 1121 LINEAR_PROBING_LOOP (probe, new_entries, ht->size) |
| 1122 ; | |
| 1123 *probe = *e; | |
| 1124 } | |
| 1125 | |
| 1204 | 1126 memcpy (ht->hentries, new_entries, ht->size * sizeof (htentry)); |
| 440 | 1127 |
| 4117 | 1128 #ifndef NEW_GC |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4962
diff
changeset
|
1129 xfree (new_entries); |
| 3092 | 1130 #endif /* not NEW_GC */ |
| 428 | 1131 } |
| 1132 | |
| 1133 static void | |
| 1134 enlarge_hash_table (Lisp_Hash_Table *ht) | |
| 1135 { | |
| 665 | 1136 Elemcount new_size = |
| 1137 hash_table_size ((Elemcount) ((double) ht->size * ht->rehash_size)); | |
| 428 | 1138 resize_hash_table (ht, new_size); |
| 1139 } | |
| 1140 | |
| 4072 | 1141 htentry * |
| 1204 | 1142 find_htentry (Lisp_Object key, const Lisp_Hash_Table *ht) |
| 428 | 1143 { |
| 1144 hash_table_test_function_t test_function = ht->test_function; | |
| 1204 | 1145 htentry *entries = ht->hentries; |
| 1146 htentry *probe = entries + HASHCODE (key, ht); | |
| 428 | 1147 |
| 1148 LINEAR_PROBING_LOOP (probe, entries, ht->size) | |
| 1149 if (KEYS_EQUAL_P (probe->key, key, test_function)) | |
| 1150 break; | |
| 1151 | |
| 1152 return probe; | |
| 1153 } | |
| 1154 | |
| 2421 | 1155 /* A version of Fputhash() that increments the value by the specified |
| 1156 amount and dispenses will all error checks. Assumes that tables does | |
| 1157 comparison using EQ. Used by the profiling routines to avoid | |
| 1158 overhead -- profiling overhead was being recorded at up to 15% of the | |
| 1159 total time. */ | |
| 1160 | |
| 1161 void | |
| 1162 inchash_eq (Lisp_Object key, Lisp_Object table, EMACS_INT offset) | |
| 1163 { | |
| 1164 Lisp_Hash_Table *ht = XHASH_TABLE (table); | |
| 1165 htentry *entries = ht->hentries; | |
| 1166 htentry *probe = entries + HASHCODE (key, ht); | |
| 1167 | |
| 1168 LINEAR_PROBING_LOOP (probe, entries, ht->size) | |
| 1169 if (EQ (probe->key, key)) | |
| 1170 break; | |
| 1171 | |
| 1172 if (!HTENTRY_CLEAR_P (probe)) | |
| 1173 probe->value = make_int (XINT (probe->value) + offset); | |
| 1174 else | |
| 1175 { | |
| 1176 probe->key = key; | |
| 1177 probe->value = make_int (offset); | |
| 1178 | |
| 1179 if (++ht->count >= ht->rehash_count) | |
| 1180 enlarge_hash_table (ht); | |
| 1181 } | |
| 1182 } | |
| 1183 | |
| 428 | 1184 DEFUN ("gethash", Fgethash, 2, 3, 0, /* |
| 1185 Find hash value for KEY in HASH-TABLE. | |
| 1186 If there is no corresponding value, return DEFAULT (which defaults to nil). | |
| 1187 */ | |
| 1188 (key, hash_table, default_)) | |
| 1189 { | |
| 442 | 1190 const Lisp_Hash_Table *ht = xhash_table (hash_table); |
| 1204 | 1191 htentry *e = find_htentry (key, ht); |
| 428 | 1192 |
| 1204 | 1193 return HTENTRY_CLEAR_P (e) ? default_ : e->value; |
| 428 | 1194 } |
| 1195 | |
| 1196 DEFUN ("puthash", Fputhash, 3, 3, 0, /* | |
|
4410
aae1994dfeec
Document return values for #'puthash, #'clrhash.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4398
diff
changeset
|
1197 Hash KEY to VALUE in HASH-TABLE, and return VALUE. |
| 428 | 1198 */ |
| 1199 (key, value, hash_table)) | |
| 1200 { | |
| 1201 Lisp_Hash_Table *ht = xhash_table (hash_table); | |
| 1204 | 1202 htentry *e = find_htentry (key, ht); |
| 428 | 1203 |
| 1204 | 1204 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1205 return e->value = value; |
| 1206 | |
| 1207 e->key = key; | |
| 1208 e->value = value; | |
| 1209 | |
| 1210 if (++ht->count >= ht->rehash_count) | |
| 1211 enlarge_hash_table (ht); | |
| 1212 | |
| 1213 return value; | |
| 1214 } | |
| 1215 | |
| 1204 | 1216 /* Remove htentry pointed at by PROBE. |
| 428 | 1217 Subsequent entries are removed and reinserted. |
| 1218 We don't use tombstones - too wasteful. */ | |
| 1219 static void | |
| 1204 | 1220 remhash_1 (Lisp_Hash_Table *ht, htentry *entries, htentry *probe) |
| 428 | 1221 { |
| 665 | 1222 Elemcount size = ht->size; |
| 1204 | 1223 CLEAR_HTENTRY (probe); |
| 428 | 1224 probe++; |
| 1225 ht->count--; | |
| 1226 | |
| 1227 LINEAR_PROBING_LOOP (probe, entries, size) | |
| 1228 { | |
| 1229 Lisp_Object key = probe->key; | |
| 1204 | 1230 htentry *probe2 = entries + HASHCODE (key, ht); |
| 428 | 1231 LINEAR_PROBING_LOOP (probe2, entries, size) |
| 1232 if (EQ (probe2->key, key)) | |
| 1204 | 1233 /* htentry at probe doesn't need to move. */ |
| 428 | 1234 goto continue_outer_loop; |
| 1204 | 1235 /* Move htentry from probe to new home at probe2. */ |
| 428 | 1236 *probe2 = *probe; |
| 1204 | 1237 CLEAR_HTENTRY (probe); |
| 428 | 1238 continue_outer_loop: continue; |
| 1239 } | |
| 1240 } | |
| 1241 | |
| 1242 DEFUN ("remhash", Fremhash, 2, 2, 0, /* | |
| 1243 Remove the entry for KEY from HASH-TABLE. | |
| 1244 Do nothing if there is no entry for KEY in HASH-TABLE. | |
| 617 | 1245 Return non-nil if an entry was removed. |
| 428 | 1246 */ |
| 1247 (key, hash_table)) | |
| 1248 { | |
| 1249 Lisp_Hash_Table *ht = xhash_table (hash_table); | |
| 1204 | 1250 htentry *e = find_htentry (key, ht); |
| 428 | 1251 |
| 1204 | 1252 if (HTENTRY_CLEAR_P (e)) |
| 428 | 1253 return Qnil; |
| 1254 | |
| 1255 remhash_1 (ht, ht->hentries, e); | |
| 1256 return Qt; | |
| 1257 } | |
| 1258 | |
| 1259 DEFUN ("clrhash", Fclrhash, 1, 1, 0, /* | |
| 1260 Remove all entries from HASH-TABLE, leaving it empty. | |
|
4410
aae1994dfeec
Document return values for #'puthash, #'clrhash.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4398
diff
changeset
|
1261 Return HASH-TABLE. |
| 428 | 1262 */ |
| 1263 (hash_table)) | |
| 1264 { | |
| 1265 Lisp_Hash_Table *ht = xhash_table (hash_table); | |
| 1204 | 1266 htentry *e, *sentinel; |
| 428 | 1267 |
| 1268 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) | |
| 1204 | 1269 CLEAR_HTENTRY (e); |
| 428 | 1270 ht->count = 0; |
| 1271 | |
| 1272 return hash_table; | |
| 1273 } | |
| 1274 | |
| 1275 /************************************************************************/ | |
| 1276 /* Accessor Functions */ | |
| 1277 /************************************************************************/ | |
| 1278 | |
| 1279 DEFUN ("hash-table-count", Fhash_table_count, 1, 1, 0, /* | |
| 1280 Return the number of entries in HASH-TABLE. | |
| 1281 */ | |
| 1282 (hash_table)) | |
| 1283 { | |
| 1284 return make_int (xhash_table (hash_table)->count); | |
| 1285 } | |
| 1286 | |
| 1287 DEFUN ("hash-table-test", Fhash_table_test, 1, 1, 0, /* | |
| 1288 Return the test function of HASH-TABLE. | |
| 1289 This can be one of `eq', `eql' or `equal'. | |
| 1290 */ | |
| 1291 (hash_table)) | |
| 1292 { | |
| 1293 hash_table_test_function_t fun = xhash_table (hash_table)->test_function; | |
| 1294 | |
| 1295 return (fun == lisp_object_eql_equal ? Qeql : | |
| 1296 fun == lisp_object_equal_equal ? Qequal : | |
| 1297 Qeq); | |
| 1298 } | |
| 1299 | |
| 1300 DEFUN ("hash-table-size", Fhash_table_size, 1, 1, 0, /* | |
| 1301 Return the size of HASH-TABLE. | |
| 1302 This is the current number of slots in HASH-TABLE, whether occupied or not. | |
| 1303 */ | |
| 1304 (hash_table)) | |
| 1305 { | |
| 1306 return make_int (xhash_table (hash_table)->size); | |
| 1307 } | |
| 1308 | |
| 1309 DEFUN ("hash-table-rehash-size", Fhash_table_rehash_size, 1, 1, 0, /* | |
| 1310 Return the current rehash size of HASH-TABLE. | |
| 1311 This is a float greater than 1.0; the factor by which HASH-TABLE | |
| 1312 is enlarged when the rehash threshold is exceeded. | |
| 1313 */ | |
| 1314 (hash_table)) | |
| 1315 { | |
| 1316 return make_float (xhash_table (hash_table)->rehash_size); | |
| 1317 } | |
| 1318 | |
| 1319 DEFUN ("hash-table-rehash-threshold", Fhash_table_rehash_threshold, 1, 1, 0, /* | |
| 1320 Return the current rehash threshold of HASH-TABLE. | |
| 1321 This is a float between 0.0 and 1.0; the maximum `load factor' of HASH-TABLE, | |
| 1322 beyond which the HASH-TABLE is enlarged by rehashing. | |
| 1323 */ | |
| 1324 (hash_table)) | |
| 1325 { | |
| 438 | 1326 return make_float (xhash_table (hash_table)->rehash_threshold); |
| 428 | 1327 } |
| 1328 | |
| 1329 DEFUN ("hash-table-weakness", Fhash_table_weakness, 1, 1, 0, /* | |
| 1330 Return the weakness of HASH-TABLE. | |
| 442 | 1331 This can be one of `nil', `key-and-value', `key-or-value', `key' or `value'. |
| 428 | 1332 */ |
| 1333 (hash_table)) | |
| 1334 { | |
| 1335 switch (xhash_table (hash_table)->weakness) | |
| 1336 { | |
| 442 | 1337 case HASH_TABLE_WEAK: return Qkey_and_value; |
| 1338 case HASH_TABLE_KEY_WEAK: return Qkey; | |
| 1339 case HASH_TABLE_KEY_VALUE_WEAK: return Qkey_or_value; | |
| 1340 case HASH_TABLE_VALUE_WEAK: return Qvalue; | |
| 1341 default: return Qnil; | |
| 428 | 1342 } |
| 1343 } | |
| 1344 | |
| 1345 /* obsolete as of 19990901 in xemacs-21.2 */ | |
| 1346 DEFUN ("hash-table-type", Fhash_table_type, 1, 1, 0, /* | |
| 1347 Return the type of HASH-TABLE. | |
| 1348 This can be one of `non-weak', `weak', `key-weak' or `value-weak'. | |
| 1349 */ | |
| 1350 (hash_table)) | |
| 1351 { | |
| 1352 switch (xhash_table (hash_table)->weakness) | |
| 1353 { | |
| 442 | 1354 case HASH_TABLE_WEAK: return Qweak; |
| 1355 case HASH_TABLE_KEY_WEAK: return Qkey_weak; | |
| 1356 case HASH_TABLE_KEY_VALUE_WEAK: return Qkey_or_value_weak; | |
| 1357 case HASH_TABLE_VALUE_WEAK: return Qvalue_weak; | |
| 1358 default: return Qnon_weak; | |
| 428 | 1359 } |
| 1360 } | |
| 1361 | |
| 1362 /************************************************************************/ | |
| 1363 /* Mapping Functions */ | |
| 1364 /************************************************************************/ | |
| 489 | 1365 |
| 1366 /* We need to be careful when mapping over hash tables because the | |
| 1367 hash table might be modified during the mapping operation: | |
| 1368 - by the mapping function | |
| 1369 - by gc (if the hash table is weak) | |
| 1370 | |
| 1371 So we make a copy of the hentries at the beginning of the mapping | |
| 497 | 1372 operation, and iterate over the copy. Naturally, this is |
| 1373 expensive, but not as expensive as you might think, because no | |
| 1374 actual memory has to be collected by our notoriously inefficient | |
| 1375 GC; we use an unwind-protect instead to free the memory directly. | |
| 1376 | |
| 1377 We could avoid the copying by having the hash table modifiers | |
| 1378 puthash and remhash check for currently active mapping functions. | |
| 1379 Disadvantages: it's hard to get right, and IMO hash mapping | |
| 1380 functions are basically rare, and no extra space in the hash table | |
| 1381 object and no extra cpu in puthash or remhash should be wasted to | |
| 1382 make maphash 3% faster. From a design point of view, the basic | |
| 1383 functions gethash, puthash and remhash should be implementable | |
| 1384 without having to think about maphash. | |
| 1385 | |
| 1386 Note: We don't (yet) have Common Lisp's with-hash-table-iterator. | |
| 1387 If you implement this naively, you cannot have more than one | |
| 1388 concurrently active iterator over the same hash table. The `each' | |
| 1389 function in perl has this limitation. | |
| 1390 | |
| 1391 Note: We GCPRO memory on the heap, not on the stack. There is no | |
| 1392 obvious reason why this is bad, but as of this writing this is the | |
| 1393 only known occurrence of this technique in the code. | |
| 504 | 1394 |
| 1395 -- Martin | |
| 1396 */ | |
| 1397 | |
| 1398 /* Ben disagrees with the "copying hentries" design, and says: | |
| 1399 | |
| 1400 Another solution is the same as I've already proposed -- when | |
| 1401 mapping, mark the table as "change-unsafe", and in this case, use a | |
| 1402 secondary table to maintain changes. this could be basically a | |
| 1403 standard hash table, but with entries only for added or deleted | |
| 1404 entries in the primary table, and a marker like Qunbound to | |
| 1405 indicate a deleted entry. puthash, gethash and remhash need a | |
| 1406 single extra check for this secondary table -- totally | |
| 1407 insignificant speedwise. if you really cared about making | |
| 1408 recursive maphashes completely correct, you'd have to do a bit of | |
| 1409 extra work here -- when maphashing, if the secondary table exists, | |
| 1410 make a copy of it, and use the copy in conjunction with the primary | |
| 1411 table when mapping. the advantages of this are | |
| 1412 | |
| 1413 [a] easy to demonstrate correct, even with weak hashtables. | |
| 1414 | |
| 1415 [b] no extra overhead in the general maphash case -- only when you | |
| 1416 modify the table while maphashing, and even then the overhead is | |
| 1417 very small. | |
| 497 | 1418 */ |
| 1419 | |
| 489 | 1420 static Lisp_Object |
| 1421 maphash_unwind (Lisp_Object unwind_obj) | |
| 1422 { | |
| 1423 void *ptr = (void *) get_opaque_ptr (unwind_obj); | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
4962
diff
changeset
|
1424 xfree (ptr); |
| 489 | 1425 free_opaque_ptr (unwind_obj); |
| 1426 return Qnil; | |
| 1427 } | |
| 1428 | |
| 1429 /* Return a malloced array of alternating key/value pairs from HT. */ | |
| 1430 static Lisp_Object * | |
| 1431 copy_compress_hentries (const Lisp_Hash_Table *ht) | |
| 1432 { | |
| 1433 Lisp_Object * const objs = | |
| 1434 /* If the hash table is empty, ht->count could be 0. */ | |
| 1435 xnew_array (Lisp_Object, 2 * (ht->count > 0 ? ht->count : 1)); | |
| 1204 | 1436 const htentry *e, *sentinel; |
| 489 | 1437 Lisp_Object *pobj; |
| 1438 | |
| 1439 for (e = ht->hentries, sentinel = e + ht->size, pobj = objs; e < sentinel; e++) | |
| 1204 | 1440 if (!HTENTRY_CLEAR_P (e)) |
| 489 | 1441 { |
| 1442 *(pobj++) = e->key; | |
| 1443 *(pobj++) = e->value; | |
| 1444 } | |
| 1445 | |
| 1446 type_checking_assert (pobj == objs + 2 * ht->count); | |
| 1447 | |
| 1448 return objs; | |
| 1449 } | |
| 1450 | |
| 428 | 1451 DEFUN ("maphash", Fmaphash, 2, 2, 0, /* |
| 1452 Map FUNCTION over entries in HASH-TABLE, calling it with two args, | |
| 1453 each key and value in HASH-TABLE. | |
| 1454 | |
| 489 | 1455 FUNCTION must not modify HASH-TABLE, with the one exception that FUNCTION |
| 428 | 1456 may remhash or puthash the entry currently being processed by FUNCTION. |
| 1457 */ | |
| 1458 (function, hash_table)) | |
| 1459 { | |
| 489 | 1460 const Lisp_Hash_Table * const ht = xhash_table (hash_table); |
| 1461 Lisp_Object * const objs = copy_compress_hentries (ht); | |
| 1462 Lisp_Object args[3]; | |
| 1463 const Lisp_Object *pobj, *end; | |
| 1464 int speccount = specpdl_depth (); | |
| 1465 struct gcpro gcpro1; | |
| 1466 | |
| 1467 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs)); | |
| 1468 GCPRO1 (objs[0]); | |
| 1469 gcpro1.nvars = 2 * ht->count; | |
| 428 | 1470 |
| 489 | 1471 args[0] = function; |
| 1472 | |
| 1473 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2) | |
| 1474 { | |
| 1475 args[1] = pobj[0]; | |
| 1476 args[2] = pobj[1]; | |
| 1477 Ffuncall (countof (args), args); | |
| 1478 } | |
| 1479 | |
| 771 | 1480 unbind_to (speccount); |
| 489 | 1481 UNGCPRO; |
| 428 | 1482 |
| 1483 return Qnil; | |
| 1484 } | |
| 1485 | |
| 489 | 1486 /* Map *C* function FUNCTION over the elements of a non-weak lisp hash table. |
| 1487 FUNCTION must not modify HASH-TABLE, with the one exception that FUNCTION | |
| 1488 may puthash the entry currently being processed by FUNCTION. | |
| 1489 Mapping terminates if FUNCTION returns something other than 0. */ | |
| 428 | 1490 void |
| 489 | 1491 elisp_maphash_unsafe (maphash_function_t function, |
| 428 | 1492 Lisp_Object hash_table, void *extra_arg) |
| 1493 { | |
| 442 | 1494 const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); |
| 1204 | 1495 const htentry *e, *sentinel; |
| 428 | 1496 |
| 1497 for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) | |
| 1204 | 1498 if (!HTENTRY_CLEAR_P (e)) |
| 489 | 1499 if (function (e->key, e->value, extra_arg)) |
| 1500 return; | |
| 428 | 1501 } |
| 1502 | |
| 489 | 1503 /* Map *C* function FUNCTION over the elements of a lisp hash table. |
| 1504 It is safe for FUNCTION to modify HASH-TABLE. | |
| 1505 Mapping terminates if FUNCTION returns something other than 0. */ | |
| 1506 void | |
| 1507 elisp_maphash (maphash_function_t function, | |
| 1508 Lisp_Object hash_table, void *extra_arg) | |
| 1509 { | |
| 1510 const Lisp_Hash_Table * const ht = xhash_table (hash_table); | |
| 1511 Lisp_Object * const objs = copy_compress_hentries (ht); | |
| 1512 const Lisp_Object *pobj, *end; | |
| 1513 int speccount = specpdl_depth (); | |
| 1514 struct gcpro gcpro1; | |
| 1515 | |
| 1516 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs)); | |
| 1517 GCPRO1 (objs[0]); | |
| 1518 gcpro1.nvars = 2 * ht->count; | |
| 1519 | |
| 1520 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2) | |
| 1521 if (function (pobj[0], pobj[1], extra_arg)) | |
| 1522 break; | |
| 1523 | |
| 771 | 1524 unbind_to (speccount); |
| 489 | 1525 UNGCPRO; |
| 1526 } | |
| 1527 | |
| 1528 /* Remove all elements of a lisp hash table satisfying *C* predicate PREDICATE. | |
| 1529 PREDICATE must not modify HASH-TABLE. */ | |
| 428 | 1530 void |
| 1531 elisp_map_remhash (maphash_function_t predicate, | |
| 1532 Lisp_Object hash_table, void *extra_arg) | |
| 1533 { | |
| 489 | 1534 const Lisp_Hash_Table * const ht = xhash_table (hash_table); |
| 1535 Lisp_Object * const objs = copy_compress_hentries (ht); | |
| 1536 const Lisp_Object *pobj, *end; | |
| 1537 int speccount = specpdl_depth (); | |
| 1538 struct gcpro gcpro1; | |
| 428 | 1539 |
| 489 | 1540 record_unwind_protect (maphash_unwind, make_opaque_ptr ((void *)objs)); |
| 1541 GCPRO1 (objs[0]); | |
| 1542 gcpro1.nvars = 2 * ht->count; | |
| 1543 | |
| 1544 for (pobj = objs, end = pobj + 2 * ht->count; pobj < end; pobj += 2) | |
| 1545 if (predicate (pobj[0], pobj[1], extra_arg)) | |
| 1546 Fremhash (pobj[0], hash_table); | |
| 1547 | |
| 771 | 1548 unbind_to (speccount); |
| 489 | 1549 UNGCPRO; |
| 428 | 1550 } |
| 1551 | |
| 1552 | |
| 1553 /************************************************************************/ | |
| 1554 /* garbage collecting weak hash tables */ | |
| 1555 /************************************************************************/ | |
| 1598 | 1556 #ifdef USE_KKCC |
| 2645 | 1557 #define MARK_OBJ(obj) do { \ |
| 1558 Lisp_Object mo_obj = (obj); \ | |
| 1559 if (!marked_p (mo_obj)) \ | |
| 1560 { \ | |
| 1561 kkcc_gc_stack_push_lisp_object (mo_obj, 0, -1); \ | |
| 1562 did_mark = 1; \ | |
| 1563 } \ | |
| 1598 | 1564 } while (0) |
| 1565 | |
| 1566 #else /* NO USE_KKCC */ | |
| 1567 | |
| 442 | 1568 #define MARK_OBJ(obj) do { \ |
| 1569 Lisp_Object mo_obj = (obj); \ | |
| 1570 if (!marked_p (mo_obj)) \ | |
| 1571 { \ | |
| 1572 mark_object (mo_obj); \ | |
| 1573 did_mark = 1; \ | |
| 1574 } \ | |
| 1575 } while (0) | |
| 1598 | 1576 #endif /*NO USE_KKCC */ |
| 442 | 1577 |
| 428 | 1578 |
| 1579 /* Complete the marking for semi-weak hash tables. */ | |
| 1580 int | |
| 1581 finish_marking_weak_hash_tables (void) | |
| 1582 { | |
| 1583 Lisp_Object hash_table; | |
| 1584 int did_mark = 0; | |
| 1585 | |
| 1586 for (hash_table = Vall_weak_hash_tables; | |
| 1587 !NILP (hash_table); | |
| 1588 hash_table = XHASH_TABLE (hash_table)->next_weak) | |
| 1589 { | |
| 442 | 1590 const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); |
| 1204 | 1591 const htentry *e = ht->hentries; |
| 1592 const htentry *sentinel = e + ht->size; | |
| 428 | 1593 |
| 1594 if (! marked_p (hash_table)) | |
| 1595 /* The hash table is probably garbage. Ignore it. */ | |
| 1596 continue; | |
| 1597 | |
| 1598 /* Now, scan over all the pairs. For all pairs that are | |
| 1599 half-marked, we may need to mark the other half if we're | |
| 1600 keeping this pair. */ | |
| 1601 switch (ht->weakness) | |
| 1602 { | |
| 1603 case HASH_TABLE_KEY_WEAK: | |
| 1604 for (; e < sentinel; e++) | |
| 1204 | 1605 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1606 if (marked_p (e->key)) |
| 1607 MARK_OBJ (e->value); | |
| 1608 break; | |
| 1609 | |
| 1610 case HASH_TABLE_VALUE_WEAK: | |
| 1611 for (; e < sentinel; e++) | |
| 1204 | 1612 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1613 if (marked_p (e->value)) |
| 1614 MARK_OBJ (e->key); | |
| 1615 break; | |
| 1616 | |
| 442 | 1617 case HASH_TABLE_KEY_VALUE_WEAK: |
| 1618 for (; e < sentinel; e++) | |
| 1204 | 1619 if (!HTENTRY_CLEAR_P (e)) |
| 442 | 1620 { |
| 1621 if (marked_p (e->value)) | |
| 1622 MARK_OBJ (e->key); | |
| 1623 else if (marked_p (e->key)) | |
| 1624 MARK_OBJ (e->value); | |
| 1625 } | |
| 1626 break; | |
| 1627 | |
| 428 | 1628 case HASH_TABLE_KEY_CAR_WEAK: |
| 1629 for (; e < sentinel; e++) | |
| 1204 | 1630 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1631 if (!CONSP (e->key) || marked_p (XCAR (e->key))) |
| 1632 { | |
| 1633 MARK_OBJ (e->key); | |
| 1634 MARK_OBJ (e->value); | |
| 1635 } | |
| 1636 break; | |
| 1637 | |
| 450 | 1638 /* We seem to be sprouting new weakness types at an alarming |
| 1639 rate. At least this is not externally visible - and in | |
| 1640 fact all of these KEY_CAR_* types are only used by the | |
| 1641 glyph code. */ | |
| 1642 case HASH_TABLE_KEY_CAR_VALUE_WEAK: | |
| 1643 for (; e < sentinel; e++) | |
| 1204 | 1644 if (!HTENTRY_CLEAR_P (e)) |
| 450 | 1645 { |
| 1646 if (!CONSP (e->key) || marked_p (XCAR (e->key))) | |
| 1647 { | |
| 1648 MARK_OBJ (e->key); | |
| 1649 MARK_OBJ (e->value); | |
| 1650 } | |
| 1651 else if (marked_p (e->value)) | |
| 1652 MARK_OBJ (e->key); | |
| 1653 } | |
| 1654 break; | |
| 1655 | |
| 428 | 1656 case HASH_TABLE_VALUE_CAR_WEAK: |
| 1657 for (; e < sentinel; e++) | |
| 1204 | 1658 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1659 if (!CONSP (e->value) || marked_p (XCAR (e->value))) |
| 1660 { | |
| 1661 MARK_OBJ (e->key); | |
| 1662 MARK_OBJ (e->value); | |
| 1663 } | |
| 1664 break; | |
| 1665 | |
| 1666 default: | |
| 1667 break; | |
| 1668 } | |
| 1669 } | |
| 1670 | |
| 1671 return did_mark; | |
| 1672 } | |
| 1673 | |
| 1674 void | |
| 1675 prune_weak_hash_tables (void) | |
| 1676 { | |
| 1677 Lisp_Object hash_table, prev = Qnil; | |
| 1678 for (hash_table = Vall_weak_hash_tables; | |
| 1679 !NILP (hash_table); | |
| 1680 hash_table = XHASH_TABLE (hash_table)->next_weak) | |
| 1681 { | |
| 1682 if (! marked_p (hash_table)) | |
| 1683 { | |
| 1684 /* This hash table itself is garbage. Remove it from the list. */ | |
| 1685 if (NILP (prev)) | |
| 1686 Vall_weak_hash_tables = XHASH_TABLE (hash_table)->next_weak; | |
| 1687 else | |
| 1688 XHASH_TABLE (prev)->next_weak = XHASH_TABLE (hash_table)->next_weak; | |
| 1689 } | |
| 1690 else | |
| 1691 { | |
| 1692 /* Now, scan over all the pairs. Remove all of the pairs | |
| 1693 in which the key or value, or both, is unmarked | |
| 1694 (depending on the weakness of the hash table). */ | |
| 1695 Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); | |
| 1204 | 1696 htentry *entries = ht->hentries; |
| 1697 htentry *sentinel = entries + ht->size; | |
| 1698 htentry *e; | |
| 428 | 1699 |
| 1700 for (e = entries; e < sentinel; e++) | |
| 1204 | 1701 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1702 { |
| 1703 again: | |
| 1704 if (!marked_p (e->key) || !marked_p (e->value)) | |
| 1705 { | |
| 1706 remhash_1 (ht, entries, e); | |
| 1204 | 1707 if (!HTENTRY_CLEAR_P (e)) |
| 428 | 1708 goto again; |
| 1709 } | |
| 1710 } | |
| 1711 | |
| 1712 prev = hash_table; | |
| 1713 } | |
| 1714 } | |
| 1715 } | |
| 1716 | |
| 1717 /* Return a hash value for an array of Lisp_Objects of size SIZE. */ | |
| 1718 | |
| 665 | 1719 Hashcode |
| 428 | 1720 internal_array_hash (Lisp_Object *arr, int size, int depth) |
| 1721 { | |
| 1722 int i; | |
| 665 | 1723 Hashcode hash = 0; |
| 442 | 1724 depth++; |
| 428 | 1725 |
| 1726 if (size <= 5) | |
| 1727 { | |
| 1728 for (i = 0; i < size; i++) | |
| 442 | 1729 hash = HASH2 (hash, internal_hash (arr[i], depth)); |
| 428 | 1730 return hash; |
| 1731 } | |
| 1732 | |
| 1733 /* just pick five elements scattered throughout the array. | |
| 1734 A slightly better approach would be to offset by some | |
| 1735 noise factor from the points chosen below. */ | |
| 1736 for (i = 0; i < 5; i++) | |
| 442 | 1737 hash = HASH2 (hash, internal_hash (arr[i*size/5], depth)); |
| 428 | 1738 |
| 1739 return hash; | |
| 1740 } | |
| 1741 | |
| 1742 /* Return a hash value for a Lisp_Object. This is for use when hashing | |
| 1743 objects with the comparison being `equal' (for `eq', you can just | |
| 1744 use the Lisp_Object itself as the hash value). You need to make a | |
| 1745 tradeoff between the speed of the hash function and how good the | |
| 1746 hashing is. In particular, the hash function needs to be FAST, | |
| 1747 so you can't just traipse down the whole tree hashing everything | |
| 1748 together. Most of the time, objects will differ in the first | |
| 1749 few elements you hash. Thus, we only go to a short depth (5) | |
| 1750 and only hash at most 5 elements out of a vector. Theoretically | |
| 1751 we could still take 5^5 time (a big big number) to compute a | |
| 1752 hash, but practically this won't ever happen. */ | |
| 1753 | |
| 665 | 1754 Hashcode |
| 428 | 1755 internal_hash (Lisp_Object obj, int depth) |
| 1756 { | |
| 1757 if (depth > 5) | |
| 1758 return 0; | |
|
4398
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1759 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1760 if (CONSP(obj)) |
| 428 | 1761 { |
|
4398
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1762 Hashcode hash, h; |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1763 int s; |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1764 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1765 depth += 1; |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1766 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1767 if (!CONSP(XCDR(obj))) |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1768 { |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1769 /* special case for '(a . b) conses */ |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1770 return HASH2(internal_hash(XCAR(obj), depth), |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1771 internal_hash(XCDR(obj), depth)); |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1772 } |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1773 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1774 /* Don't simply tail recurse; we want to hash lists with the |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1775 same contents in distinct orders differently. */ |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1776 hash = internal_hash(XCAR(obj), depth); |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1777 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1778 obj = XCDR(obj); |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1779 for (s = 1; s < 6 && CONSP(obj); obj = XCDR(obj), s++) |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1780 { |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1781 h = internal_hash(XCAR(obj), depth); |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1782 hash = HASH3(hash, h, s); |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1783 } |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1784 |
|
479443c0f95a
Have list hashes depend on the order of the contents, as is the case for vectors.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4117
diff
changeset
|
1785 return hash; |
| 428 | 1786 } |
| 1787 if (STRINGP (obj)) | |
| 1788 { | |
| 1789 return hash_string (XSTRING_DATA (obj), XSTRING_LENGTH (obj)); | |
| 1790 } | |
| 1791 if (LRECORDP (obj)) | |
| 1792 { | |
| 442 | 1793 const struct lrecord_implementation |
| 428 | 1794 *imp = XRECORD_LHEADER_IMPLEMENTATION (obj); |
| 1795 if (imp->hash) | |
| 1796 return imp->hash (obj, depth); | |
| 1797 } | |
| 1798 | |
| 1799 return LISP_HASH (obj); | |
| 1800 } | |
| 1801 | |
| 1802 DEFUN ("sxhash", Fsxhash, 1, 1, 0, /* | |
| 1803 Return a hash value for OBJECT. | |
| 444 | 1804 \(equal obj1 obj2) implies (= (sxhash obj1) (sxhash obj2)). |
| 428 | 1805 */ |
| 1806 (object)) | |
| 1807 { | |
| 1808 return make_int (internal_hash (object, 0)); | |
| 1809 } | |
| 1810 | |
| 1811 #if 0 | |
| 826 | 1812 DEFUN ("internal-hash-value", Finternal_hash_value, 1, 1, 0, /* |
| 428 | 1813 Hash value of OBJECT. For debugging. |
| 1814 The value is returned as (HIGH . LOW). | |
| 1815 */ | |
| 1816 (object)) | |
| 1817 { | |
| 1818 /* This function is pretty 32bit-centric. */ | |
| 665 | 1819 Hashcode hash = internal_hash (object, 0); |
| 428 | 1820 return Fcons (hash >> 16, hash & 0xffff); |
| 1821 } | |
| 1822 #endif | |
| 1823 | |
| 1824 | |
| 1825 /************************************************************************/ | |
| 1826 /* initialization */ | |
| 1827 /************************************************************************/ | |
| 1828 | |
| 1829 void | |
|
5158
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1830 hash_table_objects_create (void) |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1831 { |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1832 #ifdef MEMORY_USAGE_STATS |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1833 OBJECT_HAS_METHOD (hash_table, memory_usage); |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1834 #endif |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1835 } |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1836 |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1837 void |
| 428 | 1838 syms_of_elhash (void) |
| 1839 { | |
| 1840 DEFSUBR (Fhash_table_p); | |
| 1841 DEFSUBR (Fmake_hash_table); | |
| 1842 DEFSUBR (Fcopy_hash_table); | |
| 1843 DEFSUBR (Fgethash); | |
| 1844 DEFSUBR (Fremhash); | |
| 1845 DEFSUBR (Fputhash); | |
| 1846 DEFSUBR (Fclrhash); | |
| 1847 DEFSUBR (Fmaphash); | |
| 1848 DEFSUBR (Fhash_table_count); | |
| 1849 DEFSUBR (Fhash_table_test); | |
| 1850 DEFSUBR (Fhash_table_size); | |
| 1851 DEFSUBR (Fhash_table_rehash_size); | |
| 1852 DEFSUBR (Fhash_table_rehash_threshold); | |
| 1853 DEFSUBR (Fhash_table_weakness); | |
| 1854 DEFSUBR (Fhash_table_type); /* obsolete */ | |
| 1855 DEFSUBR (Fsxhash); | |
| 1856 #if 0 | |
| 1857 DEFSUBR (Finternal_hash_value); | |
| 1858 #endif | |
| 1859 | |
| 563 | 1860 DEFSYMBOL_MULTIWORD_PREDICATE (Qhash_tablep); |
| 1861 DEFSYMBOL (Qhash_table); | |
| 1862 DEFSYMBOL (Qhashtable); | |
|
5084
6afe991b8135
Add a PARSE_KEYWORDS macro, use it in #'make-hash-table.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4976
diff
changeset
|
1863 DEFSYMBOL (Qmake_hash_table); |
| 563 | 1864 DEFSYMBOL (Qweakness); |
| 1865 DEFSYMBOL (Qvalue); | |
| 1866 DEFSYMBOL (Qkey_or_value); | |
| 1867 DEFSYMBOL (Qkey_and_value); | |
| 1868 DEFSYMBOL (Qrehash_size); | |
| 1869 DEFSYMBOL (Qrehash_threshold); | |
| 428 | 1870 |
| 563 | 1871 DEFSYMBOL (Qweak); /* obsolete */ |
| 1872 DEFSYMBOL (Qkey_weak); /* obsolete */ | |
| 1873 DEFSYMBOL (Qkey_or_value_weak); /* obsolete */ | |
| 1874 DEFSYMBOL (Qvalue_weak); /* obsolete */ | |
| 1875 DEFSYMBOL (Qnon_weak); /* obsolete */ | |
| 428 | 1876 |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
4779
diff
changeset
|
1877 DEFKEYWORD (Q_data); |
| 563 | 1878 DEFKEYWORD (Q_test); |
| 1879 DEFKEYWORD (Q_size); | |
| 1880 DEFKEYWORD (Q_rehash_size); | |
| 1881 DEFKEYWORD (Q_rehash_threshold); | |
| 1882 DEFKEYWORD (Q_weakness); | |
| 1883 DEFKEYWORD (Q_type); /* obsolete */ | |
| 428 | 1884 } |
| 1885 | |
| 1886 void | |
|
5158
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1887 vars_of_elhash (void) |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1888 { |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1889 #ifdef MEMORY_USAGE_STATS |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1890 OBJECT_HAS_PROPERTY |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1891 (hash_table, memusage_stats_list, list1 (intern ("hash-entries"))); |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1892 #endif /* MEMORY_USAGE_STATS */ |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1893 } |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1894 |
|
9e0b43d3095c
more cleanups to object-memory-usage stuff
Ben Wing <ben@xemacs.org>
parents:
5146
diff
changeset
|
1895 void |
| 771 | 1896 init_elhash_once_early (void) |
| 428 | 1897 { |
|
5117
3742ea8250b5
Checking in final CVS version of workspace 'ben-lisp-object'
Ben Wing <ben@xemacs.org>
parents:
3017
diff
changeset
|
1898 INIT_LISP_OBJECT (hash_table); |
| 3092 | 1899 #ifdef NEW_GC |
|
5118
e0db3c197671
merge up to latest default branch, doesn't compile yet
Ben Wing <ben@xemacs.org>
diff
changeset
|
1900 INIT_LISP_OBJECT (hash_table_entry); |
| 3092 | 1901 #endif /* NEW_GC */ |
| 771 | 1902 |
| 428 | 1903 /* This must NOT be staticpro'd */ |
| 1904 Vall_weak_hash_tables = Qnil; | |
| 452 | 1905 dump_add_weak_object_chain (&Vall_weak_hash_tables); |
| 428 | 1906 } |