updates.

[runtime.git] / lib / silcutil / silchashtable.c

diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c
index fe75b10a22af69bb059a84af03b6e930c984746e..31f333082cfbf0a4a109216a3fafc8c18fa90eac 100644 (file)
--- a/lib/silcutil/silchashtable.c
+++ b/lib/silcutil/silchashtable.c
@@ -2,7 +2,7 @@
 
   silchashtable.c
 
-  Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
+  Author: Pekka Riikonen <priikone@silcnet.org>
 
   Copyright (C) 2001 Pekka Riikonen
 
@@ -42,11 +42,16 @@
 #define SILC_HASH_TABLE_SIZE 3
 
 /* Produce the index by hashing the key */
-#define SILC_HASH_TABLE_HASH \
-  (ht->hash(key, ht->hash_user_context) % primesize[ht->table_size])
-#define SILC_HASH_TABLE_HASH_F(f, c) \
+#define SILC_HASH_TABLE_HASH(f, c) \
   ((f)(key, (c)) % primesize[ht->table_size])
 
+/* Check whether need to rehash */
+#define SILC_HASH_REHASH_INC \
+  (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size])
+#define SILC_HASH_REHASH_DEC \
+  (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \
+   ht->entry_count > primesize[SILC_HASH_TABLE_SIZE])
+
 /* One entry in the hash table. Includes the key and the associated
    context. The `next' pointer is non-NULL if two (or more) different
    keys hashed to same value.  The pointer is the pointer to the next
@@ -68,6 +73,7 @@ struct SilcHashTableStruct {
   void *hash_user_context;
   void *compare_user_context;
   void *destructor_user_context;
+  bool auto_rehash;
 };
 
 /* Prime sizes for the hash table. The size of the table will always
@@ -109,7 +115,7 @@ silc_hash_table_find_internal(SilcHashTable ht, void *key,
                              void *compare_user_context)
 {
   SilcHashTableEntry *entry, prev = NULL;
-  uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p", i, key));
 
@@ -143,7 +149,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_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p context %p", i, key, context));
 
@@ -179,7 +185,7 @@ silc_hash_table_find_internal_simple(SilcHashTable ht, void *key,
                                     void *compare_user_context)
 {
   SilcHashTableEntry *entry;
-  uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p", i, key));
 
@@ -209,7 +215,7 @@ silc_hash_table_find_internal_all(SilcHashTable ht, void *key,
                                  void *foreach_user_context)
 {
   SilcHashTableEntry *entry;
-  uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p", i, key));
 
@@ -237,7 +243,7 @@ silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
                             void *hash_user_context)
 {
   SilcHashTableEntry *entry;
-  uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p", i, key));
 
@@ -268,6 +274,9 @@ silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context,
     (*entry)->context = context;
     ht->entry_count++;
   }
+
+  if (SILC_HASH_REHASH_INC)
+    silc_hash_table_rehash(ht, 0);
 }
 
 /* Internal routine to replace old key with new one (if it exists) */
@@ -278,7 +287,7 @@ silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
                                 void *hash_user_context)
 {
   SilcHashTableEntry *entry;
-  uint32 i = SILC_HASH_TABLE_HASH_F(hash, hash_user_context);
+  uint32 i = SILC_HASH_TABLE_HASH(hash, hash_user_context);
 
   SILC_HT_DEBUG(("index %d key %p", i, key));
 
@@ -297,6 +306,9 @@ silc_hash_table_replace_internal(SilcHashTable ht, void *key, void *context,
 
   (*entry)->key = key;
   (*entry)->context = context;
+
+  if (SILC_HASH_REHASH_INC)
+    silc_hash_table_rehash(ht, 0);
 }
 
 /* Allocates new hash table and returns it.  If the `table_size' is not
@@ -313,7 +325,8 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size,
                                    SilcHashCompare compare,
                                    void *compare_user_context,
                                    SilcHashDestructor destructor,
-                                   void *destructor_user_context)
+                                   void *destructor_user_context,
+                                   bool auto_rehash)
 {
   SilcHashTable ht;
   uint32 size_index = SILC_HASH_TABLE_SIZE;
@@ -333,6 +346,7 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size,
   ht->hash_user_context = hash_user_context;
   ht->compare_user_context = compare_user_context;
   ht->destructor_user_context = destructor_user_context;
+  ht->auto_rehash = auto_rehash;
 
   return ht;
 }
@@ -446,6 +460,9 @@ bool silc_hash_table_del(SilcHashTable ht, void *key)
 
   ht->entry_count--;
 
+  if (SILC_HASH_REHASH_DEC)
+    silc_hash_table_rehash(ht, 0);
+
   return TRUE;
 }
 
@@ -455,7 +472,9 @@ bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
                             SilcHashFunction hash, 
                             void *hash_user_context,
                             SilcHashCompare compare, 
-                            void *compare_user_context)
+                            void *compare_user_context,
+                            SilcHashDestructor destructor,
+                            void *destructor_user_context)
 {
   SilcHashTableEntry *entry, prev, e;
 
@@ -481,12 +500,19 @@ bool silc_hash_table_del_ext(SilcHashTable ht, void *key,
   if (prev && e->next)
     prev->next = e->next;
 
-  if (ht->destructor)
-    ht->destructor(e->key, e->context, ht->destructor_user_context);
+  if (destructor) {
+    destructor(e->key, e->context, destructor_user_context);
+  } else {
+    if (ht->destructor)
+      ht->destructor(e->key, e->context, ht->destructor_user_context);
+  }
   silc_free(e);
 
   ht->entry_count--;
 
+  if (SILC_HASH_REHASH_DEC)
+    silc_hash_table_rehash(ht, 0);
+
   return TRUE;
 }
 
@@ -525,6 +551,9 @@ bool silc_hash_table_del_by_context(SilcHashTable ht, void *key,
 
   ht->entry_count--;
 
+  if (SILC_HASH_REHASH_DEC)
+    silc_hash_table_rehash(ht, 0);
+
   return TRUE;
 }
 
@@ -535,7 +564,9 @@ bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
                                        SilcHashFunction hash, 
                                        void *hash_user_context,
                                        SilcHashCompare compare, 
-                                       void *compare_user_context)
+                                       void *compare_user_context,
+                                       SilcHashDestructor destructor,
+                                       void *destructor_user_context)
 {
   SilcHashTableEntry *entry, prev, e;
 
@@ -563,12 +594,19 @@ bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key,
   if (prev && e->next)
     prev->next = e->next;
 
-  if (ht->destructor)
-    ht->destructor(e->key, e->context, ht->destructor_user_context);
+  if (destructor) {
+    destructor(e->key, e->context, destructor_user_context);
+  } else {
+    if (ht->destructor)
+      ht->destructor(e->key, e->context, ht->destructor_user_context);
+  }
   silc_free(e);
 
   ht->entry_count--;
 
+  if (SILC_HASH_REHASH_DEC)
+    silc_hash_table_rehash(ht, 0);
+
   return TRUE;
 }
 
@@ -700,17 +738,26 @@ void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size)
   SilcHashTableEntry *table, e, tmp;
   uint32 table_size, size_index;
 
+  SILC_HT_DEBUG(("Start"));
+
+  if (new_size)
+    silc_hash_table_primesize(new_size, &size_index);
+  else
+    silc_hash_table_primesize(ht->entry_count, &size_index);
+
+  if (size_index == ht->table_size)
+    return;
+
+  SILC_HT_DEBUG(("Rehashing"));
+
   /* 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 = silc_calloc(primesize[size_index], sizeof(*ht->table));
   ht->table_size = size_index;
+  ht->entry_count = 0;
 
   /* Rehash */
   for (i = 0; i < primesize[table_size]; i++) {
@@ -739,6 +786,16 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
   SilcHashTableEntry *table, e, tmp;
   uint32 table_size, size_index;
 
+  SILC_HT_DEBUG(("Start"));
+
+  if (new_size)
+    silc_hash_table_primesize(new_size, &size_index);
+  else
+    silc_hash_table_primesize(ht->entry_count, &size_index);
+
+  if (size_index == ht->table_size)
+    return;
+
   SILC_HT_DEBUG(("Rehashing"));
 
   /* Take old hash table */
@@ -746,12 +803,9 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
   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 = silc_calloc(primesize[size_index], sizeof(*ht->table));
   ht->table_size = size_index;
+  ht->entry_count = 0;
 
   /* Rehash */
   for (i = 0; i < primesize[table_size]; i++) {
@@ -770,3 +824,55 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size,
   /* Remove old table */
   silc_free(table);
 }
+
+/* Prepares the `htl' list structure sent as argument to be used in the
+   hash table traversing with the silc_hash_table_get. Usage:
+   SilcHashTableList htl; silc_hash_table_list(ht, &htl); */
+
+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
+   `context' and TRUE.  If this returns FALSE then there are no anymore
+   any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */
+
+bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context)
+{
+  SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry;
+
+  if (!htl->ht->entry_count)
+    return FALSE;
+
+  while (!entry && htl->index < primesize[htl->ht->table_size]) {
+    entry = htl->ht->table[htl->index];
+    htl->index++;
+  }
+
+  if (!entry)
+    return FALSE;
+
+  htl->entry = entry->next;
+
+  if (key)
+    *key = entry->key;
+  if (context)
+    *context = entry->context;
+
+  return TRUE;
+}