Mercurial > hg > octave-lyh > gnulib-hg
changeset 13446:6a37ca840ab5
hash: extend module to deal with non-pointer keys
* lib/hash.c (hash_insert0): New interface, much like hash_insert
but that allows insertion of non-pointer entries.
Do not disallow an ENTRY value of NULL.
(hash_insert): This is now just a thin wrapper. Call hash_insert0.
* lib/hash.h (hash_insert0): Declare.
author | Jim Meyering <meyering@redhat.com> |
---|---|
date | Thu, 01 Jul 2010 23:17:25 +0200 |
parents | 90623df97ca6 |
children | 6d9c300c28a5 |
files | ChangeLog lib/hash.c lib/hash.h |
diffstat | 3 files changed, 51 insertions(+), 17 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2010-07-01 Jim Meyering <meyering@redhat.com> + + hash: extend module to deal with non-pointer keys + * lib/hash.c (hash_insert0): New interface, much like hash_insert + but that allows insertion of non-pointer entries. + Do not disallow an ENTRY value of NULL. + (hash_insert): This is now just a thin wrapper. Call hash_insert0. + * lib/hash.h (hash_insert0): Declare. + 2010-07-01 Christian Weisgerber <naddy@mips.inka.de> (tiny change) gettext: Use AC_GNU_SOURCE as a fallback for AC_USE_SYSTEM_EXTENSIONS.
--- a/lib/hash.c +++ b/lib/hash.c @@ -1020,25 +1020,32 @@ return false; } -/* If ENTRY matches an entry already in the hash table, return the pointer - to the entry from the table. Otherwise, insert ENTRY and return ENTRY. - Return NULL if the storage required for insertion cannot be allocated. - This implementation does not support duplicate entries or insertion of - NULL. */ +/* Return -1 upon memory allocation failure. + Return 1 if insertion succeeded. + Return 0 if there is already a matching entry in the table, + and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT + to that entry. -void * -hash_insert (Hash_table *table, const void *entry) + This interface is easier to use than hash_insert when you must + distinguish between the latter two cases. More importantly, + hash_insert is unusable for some types of ENTRY values. When using + hash_insert, the only way to distinguish those cases is to compare + the return value and ENTRY. That works only when you can have two + different ENTRY values that point to data that compares "equal". Thus, + when the ENTRY value is a simple scalar, you must use hash_insert0. */ +int +hash_insert0 (Hash_table *table, void const *entry, void const **matched_ent) { void *data; struct hash_entry *bucket; - /* The caller cannot insert a NULL entry. */ - if (! entry) - abort (); - /* If there's a matching entry already in the table, return that. */ if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL) - return data; + { + if (matched_ent) + *matched_ent = data; + return 0; + } /* If the growth threshold of the buckets in use has been reached, increase the table size and rehash. There's no point in checking the number of @@ -1062,11 +1069,11 @@ * tuning->growth_threshold)); if (SIZE_MAX <= candidate) - return NULL; + return -1; /* If the rehash fails, arrange to return NULL. */ if (!hash_rehash (table, candidate)) - return NULL; + return -1; /* Update the bucket we are interested in. */ if (hash_find_entry (table, entry, &bucket, false) != NULL) @@ -1081,7 +1088,7 @@ struct hash_entry *new_entry = allocate_entry (table); if (new_entry == NULL) - return NULL; + return -1; /* Add ENTRY in the overflow of the bucket. */ @@ -1089,7 +1096,7 @@ new_entry->next = bucket->next; bucket->next = new_entry; table->n_entries++; - return (void *) entry; + return 1; } /* Add ENTRY right in the bucket head. */ @@ -1098,7 +1105,23 @@ table->n_entries++; table->n_buckets_used++; - return (void *) entry; + return 1; +} + +/* If ENTRY matches an entry already in the hash table, return the pointer + to the entry from the table. Otherwise, insert ENTRY and return ENTRY. + Return NULL if the storage required for insertion cannot be allocated. + This implementation does not support duplicate entries or insertion of + NULL. */ + +void * +hash_insert (Hash_table *table, void const *entry) +{ + void const *matched_ent; + int err = hash_insert0 (table, entry, &matched_ent); + return (err == -1 + ? NULL + : (void *) (err == 0 ? matched_ent : entry)); } /* If ENTRY is already in the table, remove it and return the just-deleted
--- a/lib/hash.h +++ b/lib/hash.h @@ -88,6 +88,8 @@ /* Insertion and deletion. */ bool hash_rehash (Hash_table *, size_t) ATTRIBUTE_WUR; void *hash_insert (Hash_table *, const void *) ATTRIBUTE_WUR; +int hash_insert0 (Hash_table *table, const void *entry, + const void **matched_ent); void *hash_delete (Hash_table *, const void *); #endif