X-Git-Url: http://git.chise.org/gitweb/?a=blobdiff_plain;f=src%2Felhash.c;h=688018c81c668c3accf863a2659ca6ebc6d3c380;hb=4f29597e4f3696a59bb08ffece07183c1568c4a5;hp=e44ca97892254d309d9164c34fa6e40db675b06f;hpb=b73e352f264e9da0a00159dc29f318305cbe8636;p=chise%2Fxemacs-chise.git- diff --git a/src/elhash.c b/src/elhash.c index e44ca97..688018c 100644 --- a/src/elhash.c +++ b/src/elhash.c @@ -59,7 +59,6 @@ struct Lisp_Hash_Table Lisp_Object next_weak; /* Used to chain together all of the weak hash tables. Don't mark through this. */ }; -typedef struct Lisp_Hash_Table Lisp_Hash_Table; #define HENTRY_CLEAR_P(hentry) ((*(EMACS_UINT*)(&((hentry)->key))) == 0) #define CLEAR_HENTRY(hentry) \ @@ -70,13 +69,13 @@ typedef struct Lisp_Hash_Table Lisp_Hash_Table; #define HASH_TABLE_DEFAULT_REHASH_SIZE 1.3 #define HASH_TABLE_MIN_SIZE 10 -#define HASH_CODE(key, ht) \ - (((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \ - * (ht)->golden_ratio) \ - % (ht)->size)) +#define HASH_CODE(key, ht) \ +((((ht)->hash_function ? (ht)->hash_function (key) : LISP_HASH (key)) \ + * (ht)->golden_ratio) \ + % (ht)->size) #define KEYS_EQUAL_P(key1, key2, testfun) \ - (EQ ((key1), (key2)) || ((testfun) && (testfun) ((key1), (key2)))) + (EQ (key1, key2) || ((testfun) && (testfun) (key1, key2))) #define LINEAR_PROBING_LOOP(probe, entries, size) \ for (; \ @@ -123,7 +122,7 @@ hash_table_size (size_t requested_size) /* Return some prime near, but greater than or equal to, SIZE. Decades from the time of writing, someone will have a system large enough that the list below will be too short... */ - static CONST size_t primes [] = + static const size_t primes [] = { 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, @@ -253,6 +252,16 @@ hash_table_equal (Lisp_Object hash_table1, Lisp_Object hash_table2, int depth) return 1; } + +/* This is not a great hash function, but it _is_ correct and fast. + Examining all entries is too expensive, and examining a random + subset does not yield a correct hash function. */ +static hashcode_t +hash_table_hash (Lisp_Object hash_table, int depth) +{ + return XHASH_TABLE (hash_table)->count; +} + /* Printing hash tables. @@ -374,27 +383,27 @@ finalize_hash_table (void *header, int for_disksave) } static const struct lrecord_description hentry_description_1[] = { - { XD_LISP_OBJECT, offsetof(hentry, key), 2 }, + { XD_LISP_OBJECT, offsetof (hentry, key) }, + { XD_LISP_OBJECT, offsetof (hentry, value) }, { XD_END } }; static const struct struct_description hentry_description = { - sizeof(hentry), + sizeof (hentry), hentry_description_1 }; const struct lrecord_description hash_table_description[] = { - { XD_SIZE_T, offsetof(Lisp_Hash_Table, size) }, - { XD_STRUCT_PTR, offsetof(Lisp_Hash_Table, hentries), XD_INDIRECT(0, 1), &hentry_description }, - { XD_LO_LINK, offsetof(Lisp_Hash_Table, next_weak) }, + { XD_SIZE_T, offsetof (Lisp_Hash_Table, size) }, + { XD_STRUCT_PTR, offsetof (Lisp_Hash_Table, hentries), XD_INDIRECT(0, 1), &hentry_description }, + { XD_LO_LINK, offsetof (Lisp_Hash_Table, next_weak) }, { XD_END } }; DEFINE_LRECORD_IMPLEMENTATION ("hash-table", hash_table, mark_hash_table, print_hash_table, finalize_hash_table, - /* #### Implement hash_table_hash()! */ - hash_table_equal, 0, + hash_table_equal, hash_table_hash, hash_table_description, Lisp_Hash_Table); @@ -413,19 +422,11 @@ xhash_table (Lisp_Object hash_table) /************************************************************************/ /* Creation of hash tables, without error-checking. */ -static double -hash_table_rehash_threshold (Lisp_Hash_Table *ht) -{ - return - ht->rehash_threshold > 0.0 ? ht->rehash_threshold : - ht->size > 4096 && !ht->test_function ? 0.7 : 0.6; -} - static void compute_hash_table_derived_values (Lisp_Hash_Table *ht) { ht->rehash_count = (size_t) - ((double) ht->size * hash_table_rehash_threshold (ht)); + ((double) ht->size * ht->rehash_threshold); ht->golden_ratio = (size_t) ((double) ht->size * (.6180339887 / (double) sizeof (Lisp_Object))); } @@ -440,10 +441,6 @@ make_general_lisp_hash_table (enum hash_table_test test, Lisp_Object hash_table; Lisp_Hash_Table *ht = alloc_lcrecord_type (Lisp_Hash_Table, &lrecord_hash_table); - ht->rehash_size = rehash_size; - ht->rehash_threshold = rehash_threshold; - ht->weakness = weakness; - switch (test) { case HASH_TABLE_EQ: @@ -465,15 +462,21 @@ make_general_lisp_hash_table (enum hash_table_test test, abort (); } - if (ht->rehash_size <= 0.0) - ht->rehash_size = HASH_TABLE_DEFAULT_REHASH_SIZE; + ht->weakness = weakness; + + ht->rehash_size = + rehash_size > 1.0 ? rehash_size : HASH_TABLE_DEFAULT_REHASH_SIZE; + + ht->rehash_threshold = + rehash_threshold > 0.0 ? rehash_threshold : + size > 4096 && !ht->test_function ? 0.7 : 0.6; + if (size < HASH_TABLE_MIN_SIZE) size = HASH_TABLE_MIN_SIZE; - if (rehash_threshold < 0.0) - rehash_threshold = 0.75; - ht->size = - hash_table_size ((size_t) ((double) size / hash_table_rehash_threshold (ht)) + 1); + ht->size = hash_table_size ((size_t) (((double) size / ht->rehash_threshold) + + 1.0)); ht->count = 0; + compute_hash_table_derived_values (ht); /* We leave room for one never-occupied sentinel hentry at the end. */ @@ -500,8 +503,7 @@ make_lisp_hash_table (size_t size, enum hash_table_weakness weakness, enum hash_table_test test) { - return make_general_lisp_hash_table - (test, size, HASH_TABLE_DEFAULT_REHASH_SIZE, -1.0, weakness); + return make_general_lisp_hash_table (test, size, -1.0, -1.0, weakness); } /* Pretty reading of hash tables. @@ -868,7 +870,7 @@ The keys and values will not themselves be copied. */ (hash_table)) { - CONST Lisp_Hash_Table *ht_old = xhash_table (hash_table); + const Lisp_Hash_Table *ht_old = xhash_table (hash_table); Lisp_Hash_Table *ht = alloc_lcrecord_type (Lisp_Hash_Table, &lrecord_hash_table); copy_lcrecord (ht, ht_old); @@ -890,7 +892,7 @@ The keys and values will not themselves be copied. static void resize_hash_table (Lisp_Hash_Table *ht, size_t new_size) { - hentry *old_entries, *new_entries, *old_sentinel, *new_sentinel, *e; + hentry *old_entries, *new_entries, *sentinel, *e; size_t old_size; old_size = ht->size; @@ -898,18 +900,12 @@ resize_hash_table (Lisp_Hash_Table *ht, size_t new_size) old_entries = ht->hentries; - ht->hentries = xnew_array (hentry, new_size + 1); + ht->hentries = xnew_array_and_zero (hentry, new_size + 1); new_entries = ht->hentries; - old_sentinel = old_entries + old_size; - new_sentinel = new_entries + new_size; - - for (e = new_entries; e <= new_sentinel; e++) - CLEAR_HENTRY (e); - compute_hash_table_derived_values (ht); - for (e = old_entries; e < old_sentinel; e++) + for (e = old_entries, sentinel = e + old_size; e < sentinel; e++) if (!HENTRY_CLEAR_P (e)) { hentry *probe = new_entries + HASH_CODE (e->key, ht); @@ -922,22 +918,40 @@ resize_hash_table (Lisp_Hash_Table *ht, size_t new_size) xfree (old_entries); } +/* After a hash table has been saved to disk and later restored by the + portable dumper, it contains the same objects, but their addresses + and thus their HASH_CODEs have changed. */ void -reorganize_hash_table (Lisp_Hash_Table *ht) +pdump_reorganize_hash_table (Lisp_Object hash_table) { - resize_hash_table (ht, ht->size); + const Lisp_Hash_Table *ht = xhash_table (hash_table); + hentry *new_entries = xnew_array_and_zero (hentry, ht->size + 1); + hentry *e, *sentinel; + + for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) + if (!HENTRY_CLEAR_P (e)) + { + hentry *probe = new_entries + HASH_CODE (e->key, ht); + LINEAR_PROBING_LOOP (probe, new_entries, ht->size) + ; + *probe = *e; + } + + memcpy (ht->hentries, new_entries, ht->size * sizeof (hentry)); + + xfree (new_entries); } static void enlarge_hash_table (Lisp_Hash_Table *ht) { - size_t new_size = + size_t new_size = hash_table_size ((size_t) ((double) ht->size * ht->rehash_size)); resize_hash_table (ht, new_size); } static hentry * -find_hentry (Lisp_Object key, CONST Lisp_Hash_Table *ht) +find_hentry (Lisp_Object key, const Lisp_Hash_Table *ht) { hash_table_test_function_t test_function = ht->test_function; hentry *entries = ht->hentries; @@ -956,7 +970,7 @@ If there is no corresponding value, return DEFAULT (which defaults to nil). */ (key, hash_table, default_)) { - CONST Lisp_Hash_Table *ht = xhash_table (hash_table); + const Lisp_Hash_Table *ht = xhash_table (hash_table); hentry *e = find_hentry (key, ht); return HENTRY_CLEAR_P (e) ? default_ : e->value; @@ -1090,7 +1104,7 @@ beyond which the HASH-TABLE is enlarged by rehashing. */ (hash_table)) { - return make_float (hash_table_rehash_threshold (xhash_table (hash_table))); + return make_float (xhash_table (hash_table)->rehash_threshold); } DEFUN ("hash-table-weakness", Fhash_table_weakness, 1, 1, 0, /* @@ -1136,8 +1150,8 @@ may remhash or puthash the entry currently being processed by FUNCTION. */ (function, hash_table)) { - CONST Lisp_Hash_Table *ht = xhash_table (hash_table); - CONST hentry *e, *sentinel; + const Lisp_Hash_Table *ht = xhash_table (hash_table); + const hentry *e, *sentinel; for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) if (!HENTRY_CLEAR_P (e)) @@ -1162,8 +1176,8 @@ void elisp_maphash (maphash_function_t function, Lisp_Object hash_table, void *extra_arg) { - CONST Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); - CONST hentry *e, *sentinel; + const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); + const hentry *e, *sentinel; for (e = ht->hentries, sentinel = e + ht->size; e < sentinel; e++) if (!HENTRY_CLEAR_P (e)) @@ -1204,6 +1218,15 @@ elisp_map_remhash (maphash_function_t predicate, /************************************************************************/ /* garbage collecting weak hash tables */ /************************************************************************/ +#define MARK_OBJ(obj) do { \ + Lisp_Object mo_obj = (obj); \ + if (!marked_p (mo_obj)) \ + { \ + mark_object (mo_obj); \ + did_mark = 1; \ + } \ +} while (0) + /* Complete the marking for semi-weak hash tables. */ int @@ -1216,9 +1239,9 @@ finish_marking_weak_hash_tables (void) !NILP (hash_table); hash_table = XHASH_TABLE (hash_table)->next_weak) { - CONST Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); - CONST hentry *e = ht->hentries; - CONST hentry *sentinel = e + ht->size; + const Lisp_Hash_Table *ht = XHASH_TABLE (hash_table); + const hentry *e = ht->hentries; + const hentry *sentinel = e + ht->size; if (! marked_p (hash_table)) /* The hash table is probably garbage. Ignore it. */ @@ -1227,9 +1250,6 @@ finish_marking_weak_hash_tables (void) /* Now, scan over all the pairs. For all pairs that are half-marked, we may need to mark the other half if we're keeping this pair. */ -#define MARK_OBJ(obj) \ -do { if (!marked_p (obj)) mark_object (obj), did_mark = 1; } while (0) - switch (ht->weakness) { case HASH_TABLE_KEY_WEAK: @@ -1323,12 +1343,13 @@ hashcode_t internal_array_hash (Lisp_Object *arr, int size, int depth) { int i; - unsigned long hash = 0; + hashcode_t hash = 0; + depth++; if (size <= 5) { for (i = 0; i < size; i++) - hash = HASH2 (hash, internal_hash (arr[i], depth + 1)); + hash = HASH2 (hash, internal_hash (arr[i], depth)); return hash; } @@ -1336,7 +1357,7 @@ internal_array_hash (Lisp_Object *arr, int size, int depth) A slightly better approach would be to offset by some noise factor from the points chosen below. */ for (i = 0; i < 5; i++) - hash = HASH2 (hash, internal_hash (arr[i*size/5], depth + 1)); + hash = HASH2 (hash, internal_hash (arr[i*size/5], depth)); return hash; } @@ -1369,16 +1390,9 @@ internal_hash (Lisp_Object obj, int depth) { return hash_string (XSTRING_DATA (obj), XSTRING_LENGTH (obj)); } - if (VECTORP (obj)) - { - return HASH2 (XVECTOR_LENGTH (obj), - internal_array_hash (XVECTOR_DATA (obj), - XVECTOR_LENGTH (obj), - depth + 1)); - } if (LRECORDP (obj)) { - CONST struct lrecord_implementation + const struct lrecord_implementation *imp = XRECORD_LHEADER_IMPLEMENTATION (obj); if (imp->hash) return imp->hash (obj, depth); @@ -1404,7 +1418,7 @@ The value is returned as (HIGH . LOW). (object)) { /* This function is pretty 32bit-centric. */ - unsigned long hash = internal_hash (object, 0); + hashcode_t hash = internal_hash (object, 0); return Fcons (hash >> 16, hash & 0xffff); } #endif @@ -1417,6 +1431,8 @@ The value is returned as (HIGH . LOW). void syms_of_elhash (void) { + INIT_LRECORD_IMPLEMENTATION (hash_table); + DEFSUBR (Fhash_table_p); DEFSUBR (Fmake_hash_table); DEFSUBR (Fcopy_hash_table);