From cf9bf7fcd4a88bfa50ac1d170c11120f387ce34c Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Fri, 18 May 2001 07:07:33 +0000 Subject: [PATCH] updates. --- CHANGES | 16 ++ lib/silccore/idcache.c | 42 ++-- lib/silcutil/silchashtable.c | 379 +++++++++++++++++++---------------- lib/silcutil/silchashtable.h | 51 +++-- 4 files changed, 270 insertions(+), 218 deletions(-) diff --git a/CHANGES b/CHANGES index 47a6a32b..c70abe0d 100644 --- a/CHANGES +++ b/CHANGES @@ -1,3 +1,19 @@ +Fri May 18 08:35:31 EEST 2001 Pekka Riikonen + + * Added silc_hash_table_del[_by_context]_ext functions in to the + lib/silcutil/silchashtable.[ch]. + + Removed silc_hash_table_find_all* routines and added new + silc_hash_table_find_foreach to replace them. + + Added silc_hash_table_replace_ext function as extended + replacing function. Separated the simple hash table interface + from the extended hash table interface in the file + lib/silcutil/silchashtable.h. + + * Fixed minor bugs and changed it to use some of the new + hash table functions in lib/silccore/idcache.c + Thu May 17 18:15:12 EEST 2001 Pekka Riikonen * Added new function silc_hash_table_find_all to return all keys diff --git a/lib/silccore/idcache.c b/lib/silccore/idcache.c index da5c404b..9842a7d7 100644 --- a/lib/silccore/idcache.c +++ b/lib/silccore/idcache.c @@ -189,8 +189,11 @@ bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old) { bool ret; - ret = silc_hash_table_del_by_context(cache->data_table, old->data, - old->context); + ret = silc_hash_table_del_by_context_ext(cache->data_table, old->data, old, + silc_hash_data, + (void *)old->data_len, + silc_hash_data_compare, + (void *)old->data_len); ret = silc_hash_table_del(cache->context_table, old->context); ret = silc_hash_table_del(cache->id_table, old->id); @@ -201,18 +204,12 @@ bool silc_idcache_del(SilcIDCache cache, SilcIDCacheEntry old) bool silc_idcache_del_by_id(SilcIDCache cache, void *id) { - bool ret; SilcIDCacheEntry c; if (!silc_hash_table_find(cache->id_table, id, NULL, (void *)&c)) return FALSE; - ret = silc_hash_table_del_by_context(cache->data_table, c->data, - c->context); - ret = silc_hash_table_del(cache->context_table, c->context); - ret = silc_hash_table_del(cache->id_table, c->id); - - return ret; + return silc_idcache_del(cache, c); } /* Deletes all ID entries from cache. Free's memory as well. */ @@ -222,6 +219,7 @@ bool silc_idcache_del_all(SilcIDCache cache) silc_hash_table_free(cache->id_table); silc_hash_table_free(cache->data_table); silc_hash_table_free(cache->context_table); + return TRUE; } @@ -271,7 +269,7 @@ bool silc_idcache_purge_by_context(SilcIDCache cache, void *context) } /* Callback that is called by the hash table routine when traversing - all entrys in the hash table. */ + entrys in the hash table. */ static void silc_idcache_get_all_foreach(void *key, void *context, void *user_context) @@ -326,25 +324,21 @@ bool silc_idcache_find_by_data(SilcIDCache cache, unsigned char *data, unsigned int data_len, SilcIDCacheList *ret) { SilcIDCacheList list; - void **contexts; - unsigned int count; - int i; - if (!silc_hash_table_find_all_ext(cache->data_table, data, NULL, &contexts, - &count, silc_hash_data, (void *)data_len, - silc_hash_data_compare, (void *)data_len)) - return FALSE; + list = silc_idcache_list_alloc(); - if (!ret) { - silc_free(contexts); + if (!ret) return TRUE; - } - list = silc_idcache_list_alloc(); + silc_hash_table_find_foreach_ext(cache->data_table, data, + silc_hash_data, (void *)data_len, + silc_hash_data_compare, (void *)data_len, + silc_idcache_get_all_foreach, list); - for (i = 0; i < count; i++) - silc_idcache_list_add(list, (SilcIDCacheEntry)contexts[i]); - silc_free(contexts); + if (silc_idcache_list_count(list) == 0) { + silc_idcache_list_free(list); + return FALSE; + } *ret = list; diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index 6902d5c4..fa0d0157 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -92,14 +92,16 @@ static uint32 silc_hash_table_primesize(uint32 size, uint32 *index) static inline SilcHashTableEntry * silc_hash_table_find_internal(SilcHashTable ht, void *key, - SilcHashTableEntry *prev_entry) + SilcHashTableEntry *prev_entry, + SilcHashFunction hash, void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context) { SilcHashTableEntry *entry, prev = NULL; - entry = &ht->table[SILC_HASH_TABLE_HASH]; - if (ht->compare) { - while (*entry && ht->compare((*entry)->key, key, ht->compare_user_context) - == FALSE) { + entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)]; + if (compare) { + while (*entry && !compare((*entry)->key, key, compare_user_context)) { prev = *entry; entry = &(*entry)->next; } @@ -120,14 +122,18 @@ silc_hash_table_find_internal(SilcHashTable ht, void *key, static inline SilcHashTableEntry * silc_hash_table_find_internal_context(SilcHashTable ht, void *key, void *context, - SilcHashTableEntry *prev_entry) + SilcHashTableEntry *prev_entry, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context) { SilcHashTableEntry *entry, prev = NULL; - entry = &ht->table[SILC_HASH_TABLE_HASH]; + entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)]; if (ht->compare) { - while (*entry && ht->compare((*entry)->key, key, ht->compare_user_context) - == FALSE && (*entry)->context != context) { + while (*entry && !compare((*entry)->key, key, compare_user_context) && + (*entry)->context != context) { prev = *entry; entry = &(*entry)->next; } @@ -153,17 +159,10 @@ silc_hash_table_find_internal_simple(SilcHashTable ht, void *key, { SilcHashTableEntry *entry; - if (hash) - entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)]; - else - entry = &ht->table[SILC_HASH_TABLE_HASH]; + entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)]; if (compare) { while (*entry && !compare((*entry)->key, key, compare_user_context)) entry = &(*entry)->next; - } else if (ht->compare) { - while (*entry && !ht->compare((*entry)->key, key, - ht->compare_user_context)) - entry = &(*entry)->next; } else { while (*entry && (*entry)->key != key) entry = &(*entry)->next; @@ -172,83 +171,35 @@ silc_hash_table_find_internal_simple(SilcHashTable ht, void *key, return entry; } -/* Internal routine to find all keys by `key'. This may return multiple - entries if multiple entries with same key exists. */ - -static inline bool -silc_hash_table_find_internal_all(SilcHashTable ht, void *key, - SilcHashTableEntry **entries, - uint32 *count) -{ - SilcHashTableEntry *entry; - - *entries = NULL; - *count = 0; - - entry = &ht->table[SILC_HASH_TABLE_HASH]; - if (ht->compare) { - while (*entry) { - if (ht->compare((*entry)->key, key, ht->compare_user_context)) { - *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1)); - (*entries)[*count] = *entry; - (*count)++; - } - entry = &(*entry)->next; - } - } else { - while (*entry) { - if ((*entry)->key == key) { - *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1)); - (*entries)[*count] = *entry; - (*count)++; - } - entry = &(*entry)->next; - } - } - - return *entries ? TRUE : FALSE; -} - /* Internal routine to find all keys by `key'. This may return multiple entries if multiple entries with same key exists. With specific hash and comparison functions. */ -static inline bool -silc_hash_table_find_internal_all_ext(SilcHashTable ht, void *key, - SilcHashTableEntry **entries, - uint32 *count, - SilcHashFunction hash, - void *hash_user_context, - SilcHashCompare compare, - void *compare_user_context) +static inline void +silc_hash_table_find_internal_all(SilcHashTable ht, void *key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context, + SilcHashForeach foreach, + void *foreach_user_context) { SilcHashTableEntry *entry; - *entries = NULL; - *count = 0; - - entry = &ht->table[SILC_HASH_TABLE_HASH]; + entry = &ht->table[SILC_HASH_TABLE_HASH_F(hash, hash_user_context)]; if (compare) { while (*entry) { - if (compare((*entry)->key, key, compare_user_context)) { - *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1)); - (*entries)[*count] = *entry; - (*count)++; - } + if (compare((*entry)->key, key, compare_user_context)) + foreach((*entry)->key, (*entry)->context, foreach_user_context); entry = &(*entry)->next; } } else { while (*entry) { - if ((*entry)->key == key) { - *entries = silc_realloc(*entries, sizeof(**entries) * (*count + 1)); - (*entries)[*count] = *entry; - (*count)++; - } + if ((*entry)->key == key) + foreach((*entry)->key, (*entry)->context, foreach_user_context); entry = &(*entry)->next; } } - - return *entries ? TRUE : FALSE; } /* Internal routine to add new key to the hash table */ @@ -288,6 +239,34 @@ silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context, } } +/* Internal routine to replace old key with new one (if it exists) */ + +static inline void +silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context) +{ + SilcHashTableEntry *entry; + uint32 index = (hash ? SILC_HASH_TABLE_HASH : + SILC_HASH_TABLE_HASH_F(hash, hash_user_context)); + + entry = &ht->table[index]; + if (*entry) { + /* The entry exists already. We have a collision, replace the old + key and context. */ + if (ht->destructor) + ht->destructor((*entry)->key, (*entry)->context, + ht->destructor_user_context); + } else { + /* New key */ + *entry = silc_calloc(1, sizeof(**entry)); + ht->entry_count++; + } + + (*entry)->key = key; + (*entry)->context = context; +} + /* Allocates new hash table and returns it. If the `table_size' is not zero then the hash table size is the size provided. If zero then the default size will be used. Note that if the `table_size' is provided @@ -390,24 +369,16 @@ void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, void silc_hash_table_replace(SilcHashTable ht, void *key, void *context) { - SilcHashTableEntry *entry; - uint32 index = SILC_HASH_TABLE_HASH; + silc_hash_table_replace_internal(ht, key, context, NULL, NULL); +} - entry = &ht->table[index]; - if (*entry) { - /* The entry exists already. We have a collision, replace the old - key and context. */ - if (ht->destructor) - ht->destructor((*entry)->key, (*entry)->context, - ht->destructor_user_context); - } else { - /* New key */ - *entry = silc_calloc(1, sizeof(**entry)); - ht->entry_count++; - } +/* Same as above but with specific hash function. */ - (*entry)->key = key; - (*entry)->context = context; +void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context) +{ + silc_hash_table_replace_internal(ht, key, context, hash, hash_user_context); } /* Removes the entry from the hash table by the provided `key'. This will @@ -418,7 +389,50 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) { SilcHashTableEntry *entry, prev, e; - entry = silc_hash_table_find_internal(ht, key, &prev); + entry = silc_hash_table_find_internal(ht, key, &prev, + ht->hash, ht->hash_user_context, + ht->compare, ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + e = *entry; + + if (!prev && e->next) + *entry = e->next; + if (!prev && e->next == NULL) + *entry = NULL; + if (prev) + prev->next = NULL; + if (prev && e->next) + prev->next = e->next; + + if (ht->destructor) + ht->destructor(e->key, e->context, ht->destructor_user_context); + silc_free(e); + + ht->entry_count--; + + return TRUE; +} + +/* Same as above but with specific hash and compare functions. */ + +bool silc_hash_table_del_ext(SilcHashTable ht, void *key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context) +{ + SilcHashTableEntry *entry, prev, e; + + entry = silc_hash_table_find_internal(ht, key, &prev, + hash ? hash : ht->hash, + hash_user_context ? hash_user_context : + ht->hash_user_context, + compare ? compare : ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -452,7 +466,55 @@ bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, { SilcHashTableEntry *entry, prev, e; - entry = silc_hash_table_find_internal_context(ht, key, context, &prev); + entry = silc_hash_table_find_internal_context(ht, key, context, &prev, + ht->hash, + ht->hash_user_context, + ht->compare, + ht->compare_user_context); + if (*entry == NULL) + return FALSE; + + e = *entry; + + if (!prev && e->next) + *entry = e->next; + if (!prev && e->next == NULL) + *entry = NULL; + if (prev) + prev->next = NULL; + if (prev && e->next) + prev->next = e->next; + + if (ht->destructor) + ht->destructor(e->key, e->context, ht->destructor_user_context); + silc_free(e); + + ht->entry_count--; + + return TRUE; +} + +/* Same as above but with specific hash and compare functions. */ + +bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, + void *context, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context) +{ + SilcHashTableEntry *entry, prev, e; + + entry = silc_hash_table_find_internal_context(ht, key, context, &prev, + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? + compare : ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -487,8 +549,10 @@ bool silc_hash_table_find(SilcHashTable ht, void *key, { SilcHashTableEntry *entry; - entry = silc_hash_table_find_internal_simple(ht, key, NULL, NULL, - NULL, NULL); + entry = silc_hash_table_find_internal_simple(ht, key, ht->hash, + ht->hash_user_context, + ht->compare, + ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -500,46 +564,6 @@ bool silc_hash_table_find(SilcHashTable ht, void *key, return TRUE; } -/* As the hash table is collision resistant it is possible to save duplicate - keys to the hash table. This function can be used to return all keys - and contexts from the hash table that are found using the `key'. */ - -bool silc_hash_table_find_all(SilcHashTable ht, void *key, - void ***ret_keys, void ***ret_contexts, - unsigned int *ret_count) -{ - SilcHashTableEntry *entries; - uint32 count; - int i; - - if (!silc_hash_table_find_internal_all(ht, key, &entries, &count)) - return FALSE; - - if (ret_keys) - *ret_keys = silc_calloc(count, sizeof(**ret_keys)); - if (ret_contexts) - *ret_contexts = silc_calloc(count, sizeof(**ret_contexts)); - if (ret_count) - *ret_count = count; - - if (ret_keys && ret_count) { - for (i = 0; i < count; i++) { - (*ret_keys)[i] = entries[i]->key; - (*ret_contexts)[i] = entries[i]->context; - } - } else if (ret_keys && !ret_contexts) { - for (i = 0; i < count; i++) - (*ret_keys)[i] = entries[i]->key; - } else if (!ret_keys && ret_contexts) { - for (i = 0; i < count; i++) - (*ret_contexts)[i] = entries[i]->context; - } - - silc_free(entries); - - return TRUE; -} - /* Same as above but with specified hash and comparison functions. */ bool silc_hash_table_find_ext(SilcHashTable ht, void *key, @@ -552,8 +576,15 @@ bool silc_hash_table_find_ext(SilcHashTable ht, void *key, SilcHashTableEntry *entry; entry = silc_hash_table_find_internal_simple(ht, key, - hash, hash_user_context, - compare, compare_user_context); + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? compare : + ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context); if (*entry == NULL) return FALSE; @@ -565,48 +596,40 @@ bool silc_hash_table_find_ext(SilcHashTable ht, void *key, return TRUE; } -/* Same as above but with specified hash and comparison functions. */ +/* As the hash table is collision resistant it is possible to save duplicate + keys to the hash table. This function can be used to find all keys + and contexts from the hash table that are found using the `key'. The + `foreach' is called for every found key. */ -bool silc_hash_table_find_all_ext(SilcHashTable ht, void *key, - void ***ret_keys, void ***ret_contexts, - unsigned int *ret_count, - SilcHashFunction hash, - void *hash_user_context, - SilcHashCompare compare, - void *compare_user_context) +void silc_hash_table_find_foreach(SilcHashTable ht, void *key, + SilcHashForeach foreach, void *user_context) { - SilcHashTableEntry *entries; - uint32 count; - int i; - - if (!silc_hash_table_find_internal_all_ext(ht, key, &entries, &count, - hash, hash_user_context, - compare, compare_user_context)) - return FALSE; - - if (ret_keys) - *ret_keys = silc_calloc(count, sizeof(**ret_keys)); - if (ret_contexts) - *ret_contexts = silc_calloc(count, sizeof(**ret_contexts)); - if (ret_count) - *ret_count = count; - - if (ret_keys && ret_count) { - for (i = 0; i < count; i++) { - (*ret_keys)[i] = entries[i]->key; - (*ret_contexts)[i] = entries[i]->context; - } - } else if (ret_keys && !ret_contexts) { - for (i = 0; i < count; i++) - (*ret_keys)[i] = entries[i]->key; - } else if (!ret_keys && ret_contexts) { - for (i = 0; i < count; i++) - (*ret_contexts)[i] = entries[i]->context; - } + silc_hash_table_find_internal_all(ht, key, ht->hash, ht->hash_user_context, + ht->compare, ht->compare_user_context, + foreach, user_context); +} - silc_free(entries); +/* Same as above but with specific hash and comparison functions. */ - return TRUE; +void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context, + SilcHashForeach foreach, + void *foreach_user_context) +{ + silc_hash_table_find_internal_all(ht, key, + hash ? hash : ht->hash, + hash_user_context ? + hash_user_context : + ht->hash_user_context, + compare ? compare : + ht->compare, + compare_user_context ? + compare_user_context : + ht->compare_user_context, + foreach, foreach_user_context); } /* Traverse all entrys in the hash table and call the `foreach' for diff --git a/lib/silcutil/silchashtable.h b/lib/silcutil/silchashtable.h index 04c1198e..6b76dac4 100644 --- a/lib/silcutil/silchashtable.h +++ b/lib/silcutil/silchashtable.h @@ -43,7 +43,8 @@ typedef void (*SilcHashDestructor)(void *key, void *context, hash table using silc_hash_table_foreach. */ typedef void (*SilcHashForeach)(void *key, void *context, void *user_context); -/* Prototypes */ +/* Simple hash table interface */ + SilcHashTable silc_hash_table_alloc(uint32 table_size, SilcHashFunction hash, void *hash_user_context, @@ -55,32 +56,50 @@ void silc_hash_table_free(SilcHashTable ht); uint32 silc_hash_table_size(SilcHashTable ht); uint32 silc_hash_table_count(SilcHashTable ht); void silc_hash_table_add(SilcHashTable ht, void *key, void *context); -void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, - SilcHashFunction hash, void *hash_user_context); void silc_hash_table_replace(SilcHashTable ht, void *key, void *context); bool silc_hash_table_del(SilcHashTable ht, void *key); bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, void *context); bool silc_hash_table_find(SilcHashTable ht, void *key, void **ret_key, void **ret_context); -bool silc_hash_table_find_all(SilcHashTable ht, void *key, - void ***ret_keys, void ***ret_contexts, - unsigned int *ret_count); +void silc_hash_table_find_foreach(SilcHashTable ht, void *key, + SilcHashForeach foreach, void *user_context); +void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, + void *user_context); +void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); + + +/* Extended hash table interface (same as above but with specific + hash and comparison functions). */ + +void silc_hash_table_add_ext(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, void *hash_user_context); +void silc_hash_table_replace_ext(SilcHashTable ht, void *key, void *context, + SilcHashFunction hash, + void *hash_user_context); +bool silc_hash_table_del_ext(SilcHashTable ht, void *key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context); +bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, + void *context, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context); bool silc_hash_table_find_ext(SilcHashTable ht, void *key, void **ret_key, void **ret_context, SilcHashFunction hash, void *hash_user_context, SilcHashCompare compare, void *compare_user_context); -bool silc_hash_table_find_all_ext(SilcHashTable ht, void *key, - void ***ret_keys, void ***ret_contexts, - unsigned int *ret_count, - SilcHashFunction hash, - void *hash_user_context, - SilcHashCompare compare, - void *compare_user_context); -void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, - void *user_context); -void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); +void silc_hash_table_find_foreach_ext(SilcHashTable ht, void *key, + SilcHashFunction hash, + void *hash_user_context, + SilcHashCompare compare, + void *compare_user_context, + SilcHashForeach foreach, + void *foreach_user_context); #endif -- 2.43.0