X-Git-Url: http://git.silcnet.org/gitweb/?p=silc.git;a=blobdiff_plain;f=lib%2Fsilcutil%2Fsilchashtable.c;h=d7bca802f7cd99575a29cd98797433ce5ddeb5fc;hp=130d9fa72e4a3b80d90b1b372ad57d1bc7077e2e;hb=a818c5b5411bbc4436d1c5f011236985c96bb787;hpb=ab530adb8aab5b1aa48f66f3cd0dd6be509dd6de diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index 130d9fa7..d7bca802 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -1,16 +1,15 @@ /* - silchashtable.c + silchashtable.c Author: Pekka Riikonen - Copyright (C) 2001 Pekka Riikonen + Copyright (C) 2001 - 2002 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - + the Free Software Foundation; version 2 of the License. + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the @@ -65,8 +64,8 @@ typedef struct SilcHashTableEntryStruct { /* Hash table. */ struct SilcHashTableStruct { SilcHashTableEntry *table; - uint32 table_size; - uint32 entry_count; + SilcUInt32 table_size; + SilcUInt32 entry_count; SilcHashFunction hash; SilcHashCompare compare; SilcHashDestructor destructor; @@ -78,7 +77,7 @@ struct SilcHashTableStruct { /* Prime sizes for the hash table. The size of the table will always be one of these. */ -const uint32 primesize[42] = +const SilcUInt32 primesize[42] = { 1, 3, 5, 11, 17, 37, 67, 109, 131, 163, 257, 367, 521, 823, 1031, 1237, 2053, 2777, 4099, 6247, 8209, 14057, 16411, 21089, 32771, 47431, @@ -88,7 +87,7 @@ const uint32 primesize[42] = /* Find appropriate size for the hash table. The size will be a prime. */ -static uint32 silc_hash_table_primesize(uint32 size, uint32 *index) +static SilcUInt32 silc_hash_table_primesize(SilcUInt32 size, SilcUInt32 *index) { int i; @@ -115,7 +114,7 @@ silc_hash_table_find_internal(SilcHashTable ht, void *key, void *compare_user_context) { SilcHashTableEntry *entry, prev = NULL; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p", i, key)); @@ -149,7 +148,7 @@ silc_hash_table_find_internal_context(SilcHashTable ht, void *key, void *compare_user_context) { SilcHashTableEntry *entry, prev = NULL; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p context %p", i, key, context)); @@ -185,7 +184,7 @@ silc_hash_table_find_internal_simple(SilcHashTable ht, void *key, void *compare_user_context) { SilcHashTableEntry *entry; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p", i, key)); @@ -214,25 +213,41 @@ silc_hash_table_find_internal_all(SilcHashTable ht, void *key, SilcHashForeach foreach, void *foreach_user_context) { - SilcHashTableEntry *entry; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcHashTableEntry *entry, *tmp; + bool auto_rehash; + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p", i, key)); + /* Disallow auto rehashing while going through the table since we call + the `foreach' function which could alter the table. */ + auto_rehash = ht->auto_rehash; + ht->auto_rehash = FALSE; + entry = &ht->table[i]; if (compare) { while (*entry) { - if (compare((*entry)->key, key, compare_user_context)) + if (compare((*entry)->key, key, compare_user_context)) { + tmp = &(*entry)->next; foreach((*entry)->key, (*entry)->context, foreach_user_context); + entry = tmp; + continue; + } entry = &(*entry)->next; } } else { while (*entry) { - if ((*entry)->key == key) + if ((*entry)->key == key) { + tmp = &(*entry)->next; foreach((*entry)->key, (*entry)->context, foreach_user_context); + entry = tmp; + continue; + } entry = &(*entry)->next; } } + + ht->auto_rehash = auto_rehash; } /* Internal routine to add new key to the hash table */ @@ -243,7 +258,7 @@ silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context, void *hash_user_context) { SilcHashTableEntry *entry; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p", i, key)); @@ -287,7 +302,7 @@ silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context, void *hash_user_context) { SilcHashTableEntry *entry; - uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); + SilcUInt32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context); SILC_HT_DEBUG(("index %d key %p", i, key)); @@ -319,7 +334,7 @@ silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context, destructor function, respectively. The `hash' is mandatory, the others are optional. */ -SilcHashTable silc_hash_table_alloc(uint32 table_size, +SilcHashTable silc_hash_table_alloc(SilcUInt32 table_size, SilcHashFunction hash, void *hash_user_context, SilcHashCompare compare, @@ -329,7 +344,7 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, bool auto_rehash) { SilcHashTable ht; - uint32 size_index = SILC_HASH_TABLE_SIZE; + SilcUInt32 size_index = SILC_HASH_TABLE_SIZE; if (!hash) return NULL; @@ -376,7 +391,7 @@ void silc_hash_table_free(SilcHashTable ht) /* Returns the size of the hash table */ -uint32 silc_hash_table_size(SilcHashTable ht) +SilcUInt32 silc_hash_table_size(SilcHashTable ht) { return primesize[ht->table_size]; } @@ -385,7 +400,7 @@ uint32 silc_hash_table_size(SilcHashTable ht) 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) +SilcUInt32 silc_hash_table_count(SilcHashTable ht) { return ht->entry_count; } @@ -712,10 +727,13 @@ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, { SilcHashTableEntry e, tmp; int i; + bool auto_rehash; if (!foreach) return; + auto_rehash = ht->auto_rehash; + ht->auto_rehash = FALSE; for (i = 0; i < primesize[ht->table_size]; i++) { e = ht->table[i]; while (e) { @@ -725,6 +743,7 @@ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, e = tmp; } } + ht->auto_rehash = auto_rehash; } /* Rehashs the hash table. The size of the new hash table is provided @@ -732,11 +751,11 @@ void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, the new table of a suitable size. Note that this operation may be very slow. */ -void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size) +void silc_hash_table_rehash(SilcHashTable ht, SilcUInt32 new_size) { int i; SilcHashTableEntry *table, e, tmp; - uint32 table_size, size_index; + SilcUInt32 table_size, size_index; SILC_HT_DEBUG(("Start")); @@ -778,13 +797,13 @@ void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size) /* Same as above but with specific hash function. */ -void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size, +void silc_hash_table_rehash_ext(SilcHashTable ht, SilcUInt32 new_size, SilcHashFunction hash, void *hash_user_context) { int i; SilcHashTableEntry *table, e, tmp; - uint32 table_size, size_index; + SilcUInt32 table_size, size_index; SILC_HT_DEBUG(("Start")); @@ -834,6 +853,18 @@ void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl) htl->ht = ht; htl->entry = NULL; htl->index = 0; + htl->auto_rehash = ht->auto_rehash; + + /* Disallow rehashing of the table while traversing the table */ + ht->auto_rehash = FALSE; +} + +/* Resets the `htl' SilcHashTableList. */ + +void silc_hash_table_list_reset(SilcHashTableList *htl) +{ + /* Set back the original auto rehash value to the table */ + htl->ht->auto_rehash = htl->auto_rehash; } /* Returns always the next entry in the hash table into the `key' and