[GNUnet-SVN] r2602 - in GNUnet/src: include util

[durner]

Author: durner
Date: 2006-04-01 05:48:37 -0800 (Sat, 01 Apr 2006)
New Revision: 2602

Added:
   GNUnet/src/util/hashtable.c
   GNUnet/src/util/hashtabletest.c
Modified:
   GNUnet/src/include/gnunet_util.h
   GNUnet/src/util/Makefile.am
   GNUnet/src/util/hashing.c
Log:
Hash table implementation

Modified: GNUnet/src/include/gnunet_util.h
===================================================================
--- GNUnet/src/include/gnunet_util.h    2006-04-01 13:29:24 UTC (rev 2601)
+++ GNUnet/src/include/gnunet_util.h    2006-04-01 13:48:37 UTC (rev 2602)
@@ -539,9 +539,12 @@
  */
 struct Vector;
 
+/**
+ * @brief a hash table, opaque
+ */
+struct HashTable;
 
 
-
 /* **************** Functions and Macros ************* */
 
 /**
@@ -1452,6 +1455,13 @@
             HashCode512 * result);
 
 /**
+ * @brief Convert a weak 64 bit hash into a string
+ * @param h the hashcode
+ * @param e the string (zero terminated)
+ */
+void encWeakHash(unsigned long long h, char e[14]);
+
+/**
  * Compute the distance between 2 hashcodes.
  * The computation must be fast, not involve
  * a.a or a.e (they're used elsewhere), and
@@ -1485,6 +1495,14 @@
                HashCode512 * ret);
 
 /**
+ * @brief Create a cryptographically weak hashcode from a buffer
+ * @param z the buffer to hash
+ * @param n the size of z
+ * @return the hashcode
+ */
+unsigned long long weakHash(const char *z, int n);
+
+/**
  * Check if 2 hosts are the same (returns 1 if yes)
  * @param first the first host
  * @param second the second host
@@ -2327,6 +2345,148 @@
 void ** vectorElements(struct Vector * v);
 
 /**
+ * @brief creates a new HashTable
+ * @param numOfBuckets the number of buckets to start the HashTable out with.
+ *                     Must be greater than zero, and should be prime.
+ *                     Ideally, the number of buckets should between 1/5
+ *                     and 1 times the expected number of elements in the
+ *                     HashTable.  Values much more or less than this will
+ *                     result in wasted memory or decreased performance
+ *                     respectively.  The number of buckets in a HashTable
+ *                     can be re-calculated to an appropriate number by
+ *                     calling the HashTableRehash() function once the
+ *                     HashTable has been populated.  The number of buckets
+ *                     in a HashTable may also be re-calculated
+ *                     automatically if the ratio of elements to buckets
+ *                     passes the thresholds set by ht_setIdealRatio().
+ * @return a new Hashtable, or NULL on error
+ */
+struct HashTable *ht_create(long numOfBuckets);
+
+/**
+ * @brief destroys an existing HashTable
+ * @param hashTable the HashTable to destroy
+ */
+void ht_destroy(struct HashTable *hashTable);
+
+/**
+ * @brief checks the existence of a key in a HashTable
+ * @param hashTable the HashTable to search
+ * @param key the key to search for
+ * @return whether or not the specified HashTable contains the
+ *         specified key
+ */
+int ht_containsKey(const struct HashTable *hashTable, const void *key, const 
unsigned int keylen);
+
+/**
+ * @brief checks the existence of a value in a HashTable
+ * @param hashTable the HashTable to search
+ * @param value the value to search for
+ * @return whether or not the specified HashTable contains the
+ *         specified value
+ */
+int ht_containsValue(const struct HashTable *hashTable, const void *value, 
const unsigned int valuelen);
+
+/**
+ * @brief adds a key/value pair to a HashTable
+ * @param hashTable the HashTable to add to
+ * @param key the key to add or whose value to replace
+ * @param value the value associated with the key
+ * @return 0 if successful, -1 if an error was encountered
+ */
+int ht_put(struct HashTable *hashTable, const void *key, const unsigned int 
keylen,
+  void *value, const unsigned int valuelen);
+  
+/**
+ * @brief retrieves the value of a key in a HashTable
+ * @param hashTable the HashTable to search
+ * @param key the key whose value is desired
+ * @param value the corresponding value
+ * @param valuelen the length of the value
+ * @return YES if found, NO otherwise
+ */
+int ht_get(const struct HashTable *hashTable, const void *key, const unsigned 
int
+  keylen, void **value, unsigned int *valuelen);
+
+/**
+ * @brief removes a key/value pair from a HashTable
+ * @param hashTable the HashTable to remove the key/value pair from
+ * @param key the key specifying the key/value pair to be removed
+ */
+void ht_remove(struct HashTable *hashTable, const void *key, const unsigned 
int keylen);
+
+/**
+ * @brief removes all key/value pairs from a HashTable
+ * @param hashTable the HashTable to remove all key/value pairs from
+ */
+void ht_removeAll(struct HashTable *hashTable);
+
+/**
+ * @brief returns the number of elements in a HashTable
+ * @param hashTable the HashTable whose size is requested
+ * @return the number of key/value pairs that are present in
+ *         the specified HashTable
+ */
+long ht_size(const struct HashTable *hashTable);
+
+/**
+ * @brief returns the number of buckets in a HashTable
+ * @param hashTable the HashTable whose number of buckets is requested
+ * @return the number of buckets that are in the specified
+ *         HashTable
+ */
+long ht_buckets(const struct HashTable *hashTable);
+
+/**
+ * @brief reorganizes a HashTable to be more efficient
+ * @param hashTable the HashTable to be reorganized
+ * @param numOfBuckets the number of buckets to rehash the HashTable to.
+ *                     Should be prime.  Ideally, the number of buckets
+ *                     should be between 1/5 and 1 times the expected
+ *                     number of elements in the HashTable.  Values much
+ *                     more or less than this will result in wasted memory
+ *                     or decreased performance respectively.  If 0 is
+ *                     specified, an appropriate number of buckets is
+ *                     automatically calculated.
+ */
+void ht_rehash(struct HashTable *hashTable, long numOfBuckets);
+
+/**
+ * @brief sets the ideal element-to-bucket ratio of a HashTable
+ * @param hashTable a HashTable
+ * @param idealRatio the ideal element-to-bucket ratio.  When a rehash
+ *                   occurs (either manually via a call to the
+ *                   HashTableRehash() function or automatically due the
+ *                   the triggering of one of the thresholds below), the
+ *                   number of buckets in the HashTable will be
+ *                   recalculated to be a prime number that achieves (as
+ *                   closely as possible) this ideal ratio.  Must be a
+ *                   positive number.
+ * @param lowerRehashThreshold the element-to-bucket ratio that is considered
+ *                     unacceptably low (i.e., too few elements per bucket).
+ *                     If the actual ratio falls below this number, a
+ *                     rehash will automatically be performed.  Must be
+ *                     lower than the value of idealRatio.  If no ratio
+ *                     is considered unacceptably low, a value of 0.0 can
+ *                     be specified.
+ * @param upperRehashThreshold the element-to-bucket ratio that is considered
+ *                     unacceptably high (i.e., too many elements per bucket).
+ *                     If the actual ratio rises above this number, a
+ *                     rehash will automatically be performed.  Must be
+ *                     higher than idealRatio.  However, if no ratio
+ *                     is considered unacceptably high, a value of 0.0 can
+ *                     be specified.
+ */
+void ht_setIdealRatio(struct HashTable *hashTable, float idealRatio,
+        float lowerRehashThreshold, float upperRehashThreshold);
+
+#define HT_PUT(ht, key, val) ht_put(ht, key, sizeof(key), val, sizeof(val))
+#define HT_GET(ht, key, val, vallen) ht_get(ht, key, sizeof(key), val, vallen)
+#define HT_CONTAINS_KEY(ht, key) ht_containsKey(ht, key, sizeof(key))
+#define HT_CONTAINS_VALUE(ht, value) ht_containsValue(ht, value, sizeof(value))
+#define HT_REMOVE(ht, key) ht_remove(ht, key, sizeof(key))
+
+/**
  * open() a file
  */
 int fileopen(const char *filename, int oflag, ...);

Modified: GNUnet/src/util/Makefile.am
===================================================================
--- GNUnet/src/util/Makefile.am 2006-04-01 13:29:24 UTC (rev 2601)
+++ GNUnet/src/util/Makefile.am 2006-04-01 13:48:37 UTC (rev 2602)
@@ -53,6 +53,7 @@
  dso.c \
  getopt.c \
  hashing.c \
+ hashtable.c \
  hostkey_gcrypt.c \
  initialize.c \
  io.c \
@@ -88,6 +89,7 @@
  crontest \
  configtest \
  daemontest \
+ hashtabletest \
  hashtest \
  hashingtest \
  hostkeytest \
@@ -131,6 +133,11 @@
 timertest_LDADD = \
  $(top_builddir)/src/util/libgnunetutil.la  
 
+hashtabletest_SOURCES = \
+ hashtabletest.c
+hashtabletest_LDADD = \
+ $(top_builddir)/src/util/libgnunetutil.la  
+
 hashingtest_SOURCES = \
  hashingtest.c
 hashingtest_LDADD = \

Modified: GNUnet/src/util/hashing.c
===================================================================
--- GNUnet/src/util/hashing.c   2006-04-01 13:29:24 UTC (rev 2601)
+++ GNUnet/src/util/hashing.c   2006-04-01 13:48:37 UTC (rev 2602)
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     (C) 2001, 2002, 2003, 2004 Christian Grothoff (and other contributing 
authors)
+     (C) 2001, 2002, 2003, 2004, 2005, 2006 Christian Grothoff (and other 
contributing authors)
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -372,6 +372,21 @@
   return OK;
 }
 
+/**
+ * @brief Create a cryptographically weak hashcode from a buffer
+ * @param z the buffer to hash
+ * @param n the size of z
+ * @return the hashcode
+ */
+unsigned long long weakHash(const char *z, int n){
+  unsigned long long h = 0;
+  while(n > 0) {
+    h = (h << 3) ^ h ^ (unsigned char) *z++;
+    n--;
+  }
+  return h;
+}
+
 /* ***************** binary-ASCII encoding *************** */
 
 /**
@@ -470,6 +485,19 @@
 }
 
 /**
+ * @brief Convert a weak 64 bit hash into a string
+ * @param h the hashcode
+ * @param e the string (zero terminated)
+ */
+void encWeakHash(unsigned long long h, char e[14]) {
+  int i;
+
+  for (i = 0; i < 13; i++)
+    e[i] = encTable__[(h << (5 * i)) >> 59];
+  e[13] = 0;
+}
+
+/**
  * Compute the distance between 2 hashcodes.  The computation must be
  * fast, not involve bits[0] or bits[4] (they're used elsewhere), and be
  * somewhat consistent. And of course, the result should be a positive

Added: GNUnet/src/util/hashtable.c
===================================================================
--- GNUnet/src/util/hashtable.c 2006-04-01 13:29:24 UTC (rev 2601)
+++ GNUnet/src/util/hashtable.c 2006-04-01 13:48:37 UTC (rev 2602)
@@ -0,0 +1,430 @@
+/*
+     This file is part of GNUnet.
+     (C) 2006 Christian Grothoff (and other contributing authors)
+
+     GNUnet 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, or (at your
+     option) any later version.
+
+     GNUnet 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 GNU
+     General Public License for more details.
+
+     You should have received a copy of the GNU General Public License
+     along with GNUnet; see the file COPYING.  If not, write to the
+     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+     Boston, MA 02111-1307, USA.
+
+     Based on http://www.pomakis.com/hashtable/hashtable.c which is public
+     domain
+*/
+
+/**
+ * @brief Hashtable implementation
+ * @author Keith Pomakis
+ * @author Nils Durner
+ * @file util/hashtable.c
+ */
+
+#include "gnunet_util.h"
+#include "platform.h"
+
+typedef struct KeyValuePair {
+    void *key;
+    unsigned long keylen;
+    void *value;
+    unsigned long valuelen;
+    struct KeyValuePair *next;
+} KeyValuePair;
+
+typedef struct HashTable {
+    long numOfBuckets;
+    long numOfElements;
+    KeyValuePair **bucketArray;
+    float idealRatio, lowerRehashThreshold, upperRehashThreshold;
+} HashTable;
+
+static int isProbablePrime(long oddNumber) {
+    long i;
+
+    for (i=3; i<51; i+=2)
+        if (oddNumber == i)
+            return 1;
+        else if (oddNumber%i == 0)
+            return 0;
+
+    return 1; /* maybe */
+}
+
+static long calculateIdealNumOfBuckets(struct HashTable *hashTable) {
+    long idealNumOfBuckets = hashTable->numOfElements / hashTable->idealRatio;
+    if (idealNumOfBuckets < 5)
+        idealNumOfBuckets = 5;
+    else
+        idealNumOfBuckets |= 0x01; /* make it an odd number */
+    while (!isProbablePrime(idealNumOfBuckets))
+        idealNumOfBuckets += 2;
+
+    return idealNumOfBuckets;
+}
+
+
+/**
+ * @brief creates a new HashTable
+ * @param numOfBuckets the number of buckets to start the HashTable out with.
+ *                     Must be greater than zero, and should be prime.
+ *                     Ideally, the number of buckets should between 1/5
+ *                     and 1 times the expected number of elements in the
+ *                     HashTable.  Values much more or less than this will
+ *                     result in wasted memory or decreased performance
+ *                     respectively.  The number of buckets in a HashTable
+ *                     can be re-calculated to an appropriate number by
+ *                     calling the HashTableRehash() function once the
+ *                     HashTable has been populated.  The number of buckets
+ *                     in a HashTable may also be re-calculated
+ *                     automatically if the ratio of elements to buckets
+ *                     passes the thresholds set by ht_setIdealRatio().
+ * @return a new Hashtable, or NULL on error
+ */
+struct HashTable *ht_create(long numOfBuckets) {
+    struct HashTable *hashTable;
+    int i;
+
+    if (numOfBuckets <= 0)
+      return NULL;
+
+    hashTable = (struct HashTable *) MALLOC(sizeof(struct HashTable));
+    if (hashTable == NULL)
+        return NULL;
+
+    hashTable->bucketArray = (KeyValuePair **)
+                        MALLOC(numOfBuckets * sizeof(KeyValuePair *));
+    if (hashTable->bucketArray == NULL) {
+        FREE(hashTable);
+        return NULL;
+    }
+    
+    hashTable->numOfBuckets = numOfBuckets;
+    hashTable->numOfElements = 0;
+
+    for (i=0; i<numOfBuckets; i++)
+        hashTable->bucketArray[i] = NULL;
+
+    hashTable->idealRatio = 3.0;
+    hashTable->lowerRehashThreshold = 0.0;
+    hashTable->upperRehashThreshold = 15.0;
+
+    return hashTable;
+}
+
+/**
+ * @brief destroys an existing HashTable
+ * @param hashTable the HashTable to destroy
+ */
+void ht_destroy(struct HashTable *hashTable) {
+    int i;
+
+    for (i=0; i < hashTable->numOfBuckets; i++) {
+        KeyValuePair *pair = hashTable->bucketArray[i];
+        while (pair != NULL) {
+            KeyValuePair *nextPair = (KeyValuePair *) pair->next;
+            FREE(pair->key);
+            FREE(pair->value);
+            FREE(pair);
+            pair = nextPair;
+        }
+    }
+
+    FREE(hashTable->bucketArray);
+    FREE(hashTable);
+}
+
+/**
+ * @brief checks the existence of a key in a HashTable
+ * @param hashTable the HashTable to search
+ * @param key the key to search for
+ * @return whether or not the specified HashTable contains the
+ *         specified key
+ */
+int ht_containsKey(const struct HashTable *hashTable, const void *key, const 
unsigned int keylen) {
+    void *ret;
+    unsigned int retlen;
+    
+    return ht_get(hashTable, key, keylen, &ret, &retlen);
+}
+
+/**
+ * @brief checks the existence of a value in a HashTable
+ * @param hashTable the HashTable to search
+ * @param value the value to search for
+ * @return whether or not the specified HashTable contains the
+ *         specified value
+ */
+int ht_containsValue(const struct HashTable *hashTable, const void *value, 
const unsigned int valuelen) {
+    int i;
+
+    for (i=0; i<hashTable->numOfBuckets; i++) {
+        KeyValuePair *pair = hashTable->bucketArray[i];
+        while (pair != NULL) {
+            if (pair->valuelen == valuelen && memcmp(value, pair->value,
+              valuelen) == 0)
+                return 1;
+            pair = pair->next;
+        }
+    }
+
+    return 0;
+}
+
+/**
+ * @brief adds a key/value pair to a HashTable
+ * @param hashTable the HashTable to add to
+ * @param key the key to add or whose value to replace
+ * @param value the value associated with the key
+ * @return YES if successful, NO if an error was encountered
+ */
+int ht_put(struct HashTable *hashTable, const void *key, const unsigned int 
keylen,
+  void *value, const unsigned int valuelen) {
+    long hashValue;
+    KeyValuePair *pair;
+
+    if (key == NULL || value == NULL)
+      return NO;
+
+    hashValue = weakHash(key, keylen) % hashTable->numOfBuckets;
+    pair = hashTable->bucketArray[hashValue];
+
+    while (pair != NULL && pair->keylen != keylen &&
+      memcmp(key, pair->key, keylen) != 0)
+        pair = pair->next;
+
+    if (pair) {
+        pair->key = REALLOC(pair->key, keylen);
+        memcpy(pair->key, key, keylen);
+        pair->keylen = keylen;
+
+        pair->key = REALLOC(value, valuelen);
+        memcpy(pair->value, value, valuelen);
+        pair->valuelen = valuelen;
+    }
+    else {
+        KeyValuePair *newPair = (KeyValuePair *) MALLOC(sizeof(KeyValuePair));
+        if (newPair == NULL)
+            return NO;
+        else {
+            newPair->key = MALLOC(keylen);
+            memcpy(newPair->key, key, keylen);
+            newPair->keylen = keylen;
+            newPair->value = MALLOC(valuelen);
+            memcpy(newPair->value, value, valuelen);
+            newPair->valuelen = valuelen;
+            newPair->next = hashTable->bucketArray[hashValue];
+            hashTable->bucketArray[hashValue] = newPair;
+            hashTable->numOfElements++;
+
+            if (hashTable->upperRehashThreshold > hashTable->idealRatio) {
+                float elementToBucketRatio = (float) hashTable->numOfElements /
+                                             (float) hashTable->numOfBuckets;
+                if (elementToBucketRatio > hashTable->upperRehashThreshold)
+                    ht_rehash(hashTable, 0);
+            }
+        }
+    }
+
+    return YES;
+}
+
+/**
+ * @brief retrieves the value of a key in a HashTable
+ * @param hashTable the HashTable to search
+ * @param key the key whose value is desired
+ * @param value the corresponding value
+ * @param valuelen the length of the value
+ * @return YES if found, NO otherwise
+ */
+int ht_get(const struct HashTable *hashTable, const void *key, const unsigned 
int
+  keylen, void **value, unsigned int *valuelen) {
+    long hashValue = weakHash(key, keylen) % hashTable->numOfBuckets;
+    KeyValuePair *pair = hashTable->bucketArray[hashValue];
+
+    while (pair != NULL && keylen != pair->keylen && memcmp(key, pair->key, 
keylen) != 0)
+        pair = pair->next;
+
+    if (pair != NULL)
+    {
+      *value = pair->value;
+      *valuelen = pair->valuelen;
+    }
+
+    return pair != NULL;
+}
+
+/**
+ * @brief removes a key/value pair from a HashTable
+ * @param hashTable the HashTable to remove the key/value pair from
+ * @param key the key specifying the key/value pair to be removed
+ */
+void ht_remove(struct HashTable *hashTable, const void *key, const unsigned 
int keylen) {
+    long hashValue = weakHash(key, keylen) % hashTable->numOfBuckets;
+    KeyValuePair *pair = hashTable->bucketArray[hashValue];
+    KeyValuePair *previousPair = NULL;
+
+    while (pair != NULL && pair->keylen != keylen &&
+      memcmp(pair->key, key, keylen) != 0) {
+        previousPair = pair;
+        pair = pair->next;
+    }
+
+    if (pair != NULL) {
+        FREE(pair->key);
+        FREE(pair->value);
+        if (previousPair != NULL)
+            previousPair->next = pair->next;
+        else
+            hashTable->bucketArray[hashValue] = pair->next;
+        FREE(pair);
+        hashTable->numOfElements--;
+
+        if (hashTable->lowerRehashThreshold > 0.0) {
+            float elementToBucketRatio = (float) hashTable->numOfElements /
+                                         (float) hashTable->numOfBuckets;
+            if (elementToBucketRatio < hashTable->lowerRehashThreshold)
+                ht_rehash(hashTable, 0);
+        }
+    }
+}
+
+/**
+ * @brief removes all key/value pairs from a HashTable
+ * @param hashTable the HashTable to remove all key/value pairs from
+ */
+void ht_removeAll(struct HashTable *hashTable) {
+    int i;
+
+    for (i=0; i<hashTable->numOfBuckets; i++) {
+        KeyValuePair *pair = hashTable->bucketArray[i];
+        while (pair != NULL) {
+            KeyValuePair *nextPair = pair->next;
+            FREE(pair->key);
+            FREE(pair->value);
+            FREE(pair);
+            pair = nextPair;
+        }
+        hashTable->bucketArray[i] = NULL;
+    }
+
+    hashTable->numOfElements = 0;
+    ht_rehash(hashTable, 5);
+}
+
+/**
+ * @brief returns the number of elements in a HashTable
+ * @param hashTable the HashTable whose size is requested
+ * @return the number of key/value pairs that are present in
+ *         the specified HashTable
+ */
+long ht_size(const struct HashTable *hashTable) {
+    return hashTable->numOfElements;
+}
+
+/**
+ * @brief returns the number of buckets in a HashTable
+ * @param hashTable the HashTable whose number of buckets is requested
+ * @return the number of buckets that are in the specified
+ *         HashTable
+ */
+long ht_buckets(const struct HashTable *hashTable) {
+    return hashTable->numOfBuckets;
+}
+
+/**
+ * @brief reorganizes a HashTable to be more efficient
+ * @param hashTable the HashTable to be reorganized
+ * @param numOfBuckets the number of buckets to rehash the HashTable to.
+ *                     Should be prime.  Ideally, the number of buckets
+ *                     should be between 1/5 and 1 times the expected
+ *                     number of elements in the HashTable.  Values much
+ *                     more or less than this will result in wasted memory
+ *                     or decreased performance respectively.  If 0 is
+ *                     specified, an appropriate number of buckets is
+ *                     automatically calculated.
+ */
+void ht_rehash(struct HashTable *hashTable, long numOfBuckets) {
+    KeyValuePair **newBucketArray;
+    int i;
+
+    if (numOfBuckets == 0)
+        numOfBuckets = calculateIdealNumOfBuckets(hashTable);
+
+    if (numOfBuckets == hashTable->numOfBuckets)
+        return; /* already the right size! */
+
+    newBucketArray = (KeyValuePair **)
+                                MALLOC(numOfBuckets * sizeof(KeyValuePair *));
+    if (newBucketArray == NULL) {
+        /* Couldn't allocate memory for the new array.  This isn't a fatal
+         * error; we just can't perform the rehash. */
+        return;
+    }
+
+    for (i=0; i<numOfBuckets; i++)
+        newBucketArray[i] = NULL;
+
+    for (i=0; i<hashTable->numOfBuckets; i++) {
+        KeyValuePair *pair = hashTable->bucketArray[i];
+        while (pair != NULL) {
+            KeyValuePair *nextPair = pair->next;
+            long hashValue = weakHash(pair->key, pair->keylen) % numOfBuckets;
+            pair->next = newBucketArray[hashValue];
+            newBucketArray[hashValue] = pair;
+            pair = nextPair;
+        }
+    }
+
+    FREE(hashTable->bucketArray);
+    hashTable->bucketArray = newBucketArray;
+    hashTable->numOfBuckets = numOfBuckets;
+}
+
+/**
+ * @brief sets the ideal element-to-bucket ratio of a HashTable
+ * @param hashTable a HashTable
+ * @param idealRatio the ideal element-to-bucket ratio.  When a rehash
+ *                   occurs (either manually via a call to the
+ *                   HashTableRehash() function or automatically due the
+ *                   the triggering of one of the thresholds below), the
+ *                   number of buckets in the HashTable will be
+ *                   recalculated to be a prime number that achieves (as
+ *                   closely as possible) this ideal ratio.  Must be a
+ *                   positive number.
+ * @param lowerRehashThreshold the element-to-bucket ratio that is considered
+ *                     unacceptably low (i.e., too few elements per bucket).
+ *                     If the actual ratio falls below this number, a
+ *                     rehash will automatically be performed.  Must be
+ *                     lower than the value of idealRatio.  If no ratio
+ *                     is considered unacceptably low, a value of 0.0 can
+ *                     be specified.
+ * @param upperRehashThreshold the element-to-bucket ratio that is considered
+ *                     unacceptably high (i.e., too many elements per bucket).
+ *                     If the actual ratio rises above this number, a
+ *                     rehash will automatically be performed.  Must be
+ *                     higher than idealRatio.  However, if no ratio
+ *                     is considered unacceptably high, a value of 0.0 can
+ *                     be specified.
+ */
+void ht_setIdealRatio(struct HashTable *hashTable, float idealRatio,
+        float lowerRehashThreshold, float upperRehashThreshold) {
+
+    if (idealRatio <= 0.0 || lowerRehashThreshold >= idealRatio ||
+          (upperRehashThreshold != 0.0 || upperRehashThreshold <= idealRatio))
+      return;
+
+    hashTable->idealRatio = idealRatio;
+    hashTable->lowerRehashThreshold = lowerRehashThreshold;
+    hashTable->upperRehashThreshold = upperRehashThreshold;
+}
+
+
+/* end of hashtable.c */

Added: GNUnet/src/util/hashtabletest.c
===================================================================
--- GNUnet/src/util/hashtabletest.c     2006-04-01 13:29:24 UTC (rev 2601)
+++ GNUnet/src/util/hashtabletest.c     2006-04-01 13:48:37 UTC (rev 2602)
@@ -0,0 +1,127 @@
+/**
+ * @file util/hashtabletest.c
+ * @brief testcase for util/hashtable.c
+ * @author Nils Durner
+ */
+
+#include "gnunet_util.h"
+#include "platform.h"
+
+static int testHT()
+{
+  struct HashTable *ht = ht_create(10);
+  void *val;
+  unsigned int vallen;
+  
+  if (HT_PUT(ht, "Sweden", "Stockholm") != YES ||
+    HT_PUT(ht, "Germany", "Berlin") != YES ||
+    HT_PUT(ht, "France", "Paris") != YES ||
+    HT_PUT(ht, "Spain", "Madrid") != YES ||
+    HT_PUT(ht, "Italy", "Rome") != YES ||
+    HT_PUT(ht, "USA", "Washington") != YES)
+  {
+    puts("ht_put failed\n");
+    return 1;
+  }
+  
+  if (HT_CONTAINS_KEY(ht, "France") != YES ||
+    HT_CONTAINS_KEY(ht, "Iceland") != NO)
+  {
+    puts("ht_contains_key failed!\n");
+    return 1;
+  }
+  
+  if (HT_CONTAINS_VALUE(ht, "Paris") != YES ||
+    HT_CONTAINS_VALUE(ht, "London") != NO)
+  {
+    puts("ht_contains_value failed!\n");
+    return 1;
+  }
+  
+  if (HT_GET(ht, "USA", &val, &vallen) != YES)
+  {
+    puts("ht_get failed!\n");
+    return 1;
+  }
+  
+  if (strcmp((char *) val, "Washington") != 0)
+  {
+    puts("ht_get result invalid!\n");
+    return 1;
+  }
+  
+  HT_REMOVE(ht, "Spain");
+  if (HT_CONTAINS_KEY(ht, "Spain") != NO)
+  {
+    puts("ht_remove failed!\n");
+    return 1;    
+  }
+  
+  if (ht_size(ht) != 5)
+  {
+    puts("ht_size failed!\n");
+    return 1;    
+  }
+  
+  ht_removeAll(ht);
+  if (ht_size(ht) != 0)
+  {
+    puts("ht_size#2 failed!\n");
+    return 1;    
+  }
+  
+  ht_destroy(ht);
+  
+  return 0;
+}
+
+
+/**
+ * Perform option parsing from the command line.
+ */
+static int parseCommandLine(int argc,
+                           char * argv[]) {
+  char c;
+
+  while (1) {
+    int option_index = 0;
+    static struct GNoption long_options[] = {
+      { "loglevel",1, 0, 'L' },
+      { "config",  1, 0, 'c' },
+      { 0,0,0,0 }
+    };
+
+    c = GNgetopt_long(argc,
+                     argv,
+                     "c:L:",
+                     long_options,
+                     &option_index);
+
+    if (c == -1)
+      break;  /* No more flags to process */
+
+    switch(c) {
+    case 'L':
+      FREENONNULL(setConfigurationString("GNUNET",
+                                        "LOGLEVEL",
+                                        GNoptarg));
+      break;
+    case 'c':
+      FREENONNULL(setConfigurationString("FILES",
+                                        "gnunet.conf",
+                                        GNoptarg));
+      break;
+    } /* end of parsing commandline */
+  }
+  return OK;
+}
+
+int main(int argc, char * argv[]){
+  int ret = 0;
+
+  initUtil(argc, argv, &parseCommandLine);
+  ret = testHT();
+  doneUtil();
+
+  return ret;
+}