From 0d805c373cb74658990551a5a2725f0d07b2d6c7 Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Wed, 16 May 2001 19:59:33 +0000 Subject: [PATCH] updates. --- CHANGES | 13 ++++++ TODO | 2 - lib/silcutil/silchashtable.c | 58 ++++++++++++++++++++++++-- lib/silcutil/silchashtable.h | 1 + lib/silcutil/silcutil.c | 80 ++++++++++++++++++++++++++++++++++++ lib/silcutil/silcutil.h | 6 +++ 6 files changed, 154 insertions(+), 6 deletions(-) diff --git a/CHANGES b/CHANGES index 3744d073..cc536529 100644 --- a/CHANGES +++ b/CHANGES @@ -1,3 +1,16 @@ +Wed May 16 23:03:30 EEST 2001 Pekka Riikonen + + * Added entry_count field to the SilcHashTable to keep the number + of the entries in the table. Implemented the function + silc_hash_table_rehash. Added new function + silc_hash_table_count. Affected file lib/silcutil/silchashtable.c. + + Fixed a minor bug in silc_hash_table_free. + + * Added silc_hash_string, silc_hash_uint, silc_hash_ptr, + silc_hash_client_id, silc_hash_server_id and silc_hash_channel_id + into the lib/silcutil/silcutil.[ch]. + Wed May 16 20:02:47 EEST 2001 Pekka Riikonen * Implemented a collision resistant hash table into the diff --git a/TODO b/TODO index 82ccb76b..8a837e92 100644 --- a/TODO +++ b/TODO @@ -88,8 +88,6 @@ TODO/bugs In SILC Libraries o The CAST cipher is not compiled currently due to compilation errors; check those. Cast is in lib/silccrypt/cast.c. - o silc_hash_table_rehash is not implemented in lib/silcutil/silchashtable.c. - o All payload parsing (decoding) functions should take unsigned char * and uint32 as data and data length as arguments. Now some of the routines do already that but most of the routines use SilcBuffer. diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index fe364020..3f93747e 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -43,6 +43,7 @@ typedef struct SilcHashTableEntryStruct { struct SilcHashTableStruct { SilcHashTableEntry *table; uint32 table_size; + uint32 entry_count; SilcHashFunction hash; SilcHashCompare compare; SilcHashDestructor destructor; @@ -136,14 +137,19 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, void silc_hash_table_free(SilcHashTable ht) { + SilcHashTableEntry e, tmp; int i; - for (i = 0; i < primesize[ht->table_size]; i++) - if (ht->table[i]) { + for (i = 0; i < primesize[ht->table_size]; i++) { + e = ht->table[i]; + while (e) { if (ht->destructor) - ht->destructor(ht->table[i]->key, ht->table[i]->context); - silc_free(ht->table[i]); + ht->destructor(e->key, e->context); + tmp = e; + e = e->next; + silc_free(tmp); } + } silc_free(ht->table); silc_free(ht); @@ -156,6 +162,15 @@ uint32 silc_hash_table_size(SilcHashTable ht) return primesize[ht->table_size]; } +/* Returns the number of the entires in the hash table. If there is more + entries in the table thatn the size of the hash table calling the + silc_hash_table_rehash is recommended. */ + +uint32 silc_hash_table_count(SilcHashTable ht) +{ + return ht->entry_count; +} + /* Adds new entry to the hash table. The `key' is hashed using the hash function and the both `key' and `context' will be saved to the hash table. This function quarantees that the entry is always added @@ -182,11 +197,13 @@ void silc_hash_table_add(SilcHashTable ht, void *key, void *context) e->next = silc_calloc(1, sizeof(*e->next)); e->next->key = key; e->next->context = context; + ht->entry_count++; } else { /* New key */ *entry = silc_calloc(1, sizeof(**entry)); (*entry)->key = key; (*entry)->context = context; + ht->entry_count++; } } @@ -209,6 +226,7 @@ void silc_hash_table_replace(SilcHashTable ht, void *key, void *context) } else { /* New key */ *entry = silc_calloc(1, sizeof(**entry)); + ht->entry_count++; } (*entry)->key = key; @@ -242,6 +260,8 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) ht->destructor(e->key, e->context); silc_free(e); + ht->entry_count--; + return TRUE; } @@ -275,5 +295,35 @@ bool silc_hash_table_find(SilcHashTable ht, void *key, void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size) { + int i; + SilcHashTableEntry *table, e, tmp; + uint32 table_size, size_index; + + /* Take old hash table */ + table = ht->table; + table_size = ht->table_size; + + /* Allocate new table */ + ht->table = silc_calloc(new_size ? silc_hash_table_primesize(new_size, + &size_index) : + silc_hash_table_primesize(ht->entry_count, + &size_index), + sizeof(*ht->table)); + ht->table_size = size_index; + + /* Rehash */ + for (i = 0; i < primesize[table_size]; i++) { + e = table[i]; + while (e) { + silc_hash_table_add(ht, e->key, e->context); + tmp = e; + e = e->next; + + /* Remove old entry */ + silc_free(tmp); + } + } + /* Remove old table */ + silc_free(table); } diff --git a/lib/silcutil/silchashtable.h b/lib/silcutil/silchashtable.h index 7dfe0d97..86b7902b 100644 --- a/lib/silcutil/silchashtable.h +++ b/lib/silcutil/silchashtable.h @@ -45,6 +45,7 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, SilcHashDestructor destructor); 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_replace(SilcHashTable ht, void *key, void *context); bool silc_hash_table_del(SilcHashTable ht, void *key); diff --git a/lib/silcutil/silcutil.c b/lib/silcutil/silcutil.c index 2907f2cc..d4d56d03 100644 --- a/lib/silcutil/silcutil.c +++ b/lib/silcutil/silcutil.c @@ -768,3 +768,83 @@ char *silc_get_real_name() return realname; } + +/* Basic has function to hash strings. May be used with the SilcHashTable. */ + +uint32 silc_hash_string(void *key) +{ + char *s = (char *)key; + uint32 h = 0, g; + + while (*s != '\0') { + h = (h << 4) + toupper(*s); + if ((g = h & 0xf0000000)) { + h = h ^ (g >> 24); + h = h ^ g; + } + s++; + } + + return h; +} + +/* Basic hash function to hash integers. May be used with the SilcHashTable. */ + +uint32 silc_hash_uint(void *key) +{ + return *(uint32 *)key; +} + +/* Basic hash funtion to hash pointers. May be used with the SilcHashTable. */ + +uint32 silc_hash_ptr(void *key) +{ + return (uint32)key; +} + +/* Hash a Server ID. */ + +uint32 silc_hash_server_id(void *key) +{ + SilcServerID *id = (SilcServerID *)key; + int i; + uint32 h; + + h = id->port * id->rnd; + for (i = 0; i < id->ip.data_len; i++) + h ^= id->ip.data[i]; + + return h; +} + +/* Hash a Client ID. */ + +uint32 silc_hash_client_id(void *key) +{ + SilcClientID *id = (SilcClientID *)key; + int i; + uint32 h; + + h = id->rnd; + for (i = 0; i < sizeof(id->hash); i++) + h ^= id->hash[i]; + for (i = 0; i < id->ip.data_len; i++) + h ^= id->ip.data[i]; + + return h; +} + +/* Hash a Channel ID. */ + +uint32 silc_hash_channel_id(void *key) +{ + SilcChannelID *id = (SilcChannelID *)key; + int i; + uint32 h; + + h = id->port * id->rnd; + for (i = 0; i < id->ip.data_len; i++) + h ^= id->ip.data[i]; + + return h; +} diff --git a/lib/silcutil/silcutil.h b/lib/silcutil/silcutil.h index ef610aed..2e92330c 100644 --- a/lib/silcutil/silcutil.h +++ b/lib/silcutil/silcutil.h @@ -50,5 +50,11 @@ int silc_string_regex_match(const char *regex, const char *string); int silc_string_match(const char *string1, const char *string2); char *silc_get_username(); char *silc_get_real_name(); +uint32 silc_hash_string(void *key); +uint32 silc_hash_uint(void *key); +uint32 silc_hash_ptr(void *key); +uint32 silc_hash_server_id(void *key); +uint32 silc_hash_client_id(void *key); +uint32 silc_hash_channel_id(void *key); #endif -- 2.24.0