- 32-bit key hashmap

3 files changed, 611 insertions, 1 deletions

diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index f872527a6..ac855c25e 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -73,6 +73,7 @@ libgnunetutil_la_SOURCES = \
   container_heap.c \
   container_meta_data.c \
   container_multihashmap.c \
+  container_multihashmap32.c \
   container_slist.c \
   crypto_aes.c \
   crypto_crc.c \
@@ -209,6 +210,7 @@ check_PROGRAMS = \
  test_container_bloomfilter \
  test_container_meta_data \
  test_container_multihashmap \
+ test_container_multihashmap32 \
  test_container_heap \
  test_container_slist \
  test_crypto_aes \
@@ -310,7 +312,12 @@ test_container_meta_data_LDADD = \
 test_container_multihashmap_SOURCES = \
  test_container_multihashmap.c
 test_container_multihashmap_LDADD = \
- $(top_builddir)/src/util/libgnunetutil.la  
+ $(top_builddir)/src/util/libgnunetutil.la
+
+test_container_multihashmap32_SOURCES = \
+ test_container_multihashmap32.c
+test_container_multihashmap32_LDADD = \
+ $(top_builddir)/src/util/libgnunetutil.la
 
 test_container_heap_SOURCES = \
  test_container_heap.c
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c
new file mode 100644
index 000000000..da727d710
--- /dev/null
+++ b/src/util/container_multihashmap32.c
@@ -0,0 +1,497 @@
+/*
+     This file is part of GNUnet.
+     (C) 2008 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.
+*/
+/**
+ * @file util/container_multihashmap32.c
+ * @brief a version of hash map implemented in container_multihashmap.c but with
+ *          uint32_t as keys
+ * @author Christian Grothoff
+ * @author Sree Harsha Totakura
+ */
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_container_lib.h"
+#include "gnunet_crypto_lib.h"
+
+#define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
+
+/**
+ * An entry in the hash map.
+ */
+struct MapEntry
+{
+
+  /**
+   * Key for the entry.
+   */
+  uint32_t key;
+
+  /**
+   * Value of the entry.
+   */
+  void *value;
+
+  /**
+   * If there is a hash collision, we create a linked list.
+   */
+  struct MapEntry *next;
+
+};
+
+/**
+ * Internal representation of the hash map.
+ */
+struct GNUNET_CONTAINER_MultiHashMap32
+{
+
+  /**
+   * All of our buckets.
+   */
+  struct MapEntry **map;
+
+  /**
+   * Number of entries in the map.
+   */
+  unsigned int size;
+
+  /**
+   * Length of the "map" array.
+   */
+  unsigned int map_length;
+};
+
+
+/**
+ * Create a multi hash map.
+ *
+ * @param len initial size (map will grow as needed)
+ * @return NULL on error
+ */
+struct GNUNET_CONTAINER_MultiHashMap32 *
+GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
+{
+  struct GNUNET_CONTAINER_MultiHashMap32 *ret;
+
+  GNUNET_assert (len > 0);
+  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap32));
+  ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
+  ret->map_length = len;
+  return ret;
+}
+
+
+/**
+ * Destroy a hash map.  Will not free any values
+ * stored in the hash map!
+ *
+ * @param map the map
+ */
+void
+GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
+                                         *map)
+{
+  unsigned int i;
+  struct MapEntry *e;
+
+  for (i = 0; i < map->map_length; i++)
+  {
+    while (NULL != (e = map->map[i]))
+    {
+      map->map[i] = e->next;
+      GNUNET_free (e);
+    }
+  }
+  GNUNET_free (map->map);
+  GNUNET_free (map);
+}
+
+
+/**
+ * Compute the index of the bucket for the given key.
+ *
+ * @param m hash map for which to compute the index
+ * @param key what key should the index be computed for
+ * @return offset into the "map" array of "m"
+ */
+static unsigned int
+idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
+        const uint32_t key)
+{
+  GNUNET_assert (m != NULL);
+  return ((unsigned int) key) % m->map_length;
+}
+
+
+/**
+ * Get the number of key-value pairs in the map.
+ *
+ * @param map the map
+ * @return the number of key value pairs
+ */
+unsigned int
+GNUNET_CONTAINER_multihashmap32_size (const struct
+                                      GNUNET_CONTAINER_MultiHashMap32 *map)
+{
+  return map->size;
+}
+
+
+/**
+ * Given a key find a value in the map matching the key.
+ *
+ * @param map the map
+ * @param key what to look for
+ * @return NULL if no value was found; note that
+ *   this is indistinguishable from values that just
+ *   happen to be NULL; use "contains" to test for
+ *   key-value pairs with value NULL
+ */
+void *
+GNUNET_CONTAINER_multihashmap32_get (const struct
+                                     GNUNET_CONTAINER_MultiHashMap32 *map,
+                                     uint32_t key)
+{
+  struct MapEntry *e;
+
+  e = map->map[idx_of (map, key)];
+  while (e != NULL)
+  {
+    if (key == e->key)
+      return e->value;
+    e = e->next;
+  }
+  return NULL;
+}
+
+
+/**
+ * Iterate over all entries in the map.
+ *
+ * @param map the map
+ * @param it function to call on each entry
+ * @param it_cls extra argument to it
+ * @return the number of key value pairs processed,
+ *         GNUNET_SYSERR if it aborted iteration
+ */
+int
+GNUNET_CONTAINER_multihashmap32_iterate (const struct
+                                         GNUNET_CONTAINER_MultiHashMap32 *map,
+                                         GNUNET_CONTAINER_HashMapIterator32 it,
+                                         void *it_cls)
+{
+  int count;
+  unsigned int i;
+  struct MapEntry *e;
+  struct MapEntry *n;
+
+  count = 0;
+  GNUNET_assert (map != NULL);
+  for (i = 0; i < map->map_length; i++)
+  {
+    n = map->map[i];
+    while (NULL != (e = n))
+    {
+      n = e->next;
+      if (NULL != it)
+      {
+        if (GNUNET_OK != it (it_cls, e->key, e->value))
+          return GNUNET_SYSERR;
+      }
+      count++;
+    }
+  }
+  return count;
+}
+
+
+/**
+ * Remove the given key-value pair from the map.  Note that if the
+ * key-value pair is in the map multiple times, only one of the pairs
+ * will be removed.
+ *
+ * @param map the map
+ * @param key key of the key-value pair
+ * @param value value of the key-value pair
+ * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
+ *  is not in the map
+ */
+int
+GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
+                                        *map,
+                                        uint32_t key, void *value)
+{
+  struct MapEntry *e;
+  struct MapEntry *p;
+  unsigned int i;
+
+  i = idx_of (map, key);
+  p = NULL;
+  e = map->map[i];
+  while (e != NULL)
+  {
+    if ( (key == e->key) && (value == e->value) )
+    {
+      if (p == NULL)
+        map->map[i] = e->next;
+      else
+        p->next = e->next;
+      GNUNET_free (e);
+      map->size--;
+      return GNUNET_YES;
+    }
+    p = e;
+    e = e->next;
+  }
+  return GNUNET_NO;
+}
+
+
+/**
+ * Remove all entries for the given key from the map.
+ * Note that the values would not be "freed".
+ *
+ * @param map the map
+ * @param key identifies values to be removed
+ * @return number of values removed
+ */
+int
+GNUNET_CONTAINER_multihashmap32_remove_all (struct
+                                            GNUNET_CONTAINER_MultiHashMap32
+                                            *map,
+                                            uint32_t key)
+{
+  struct MapEntry *e;
+  struct MapEntry *p;
+  unsigned int i;
+  int ret;
+
+  ret = 0;
+  i = idx_of (map, key);
+  p = NULL;
+  e = map->map[i];
+  while (e != NULL)
+  {
+    if (key == e->key)
+    {
+      if (p == NULL)
+        map->map[i] = e->next;
+      else
+        p->next = e->next;
+      GNUNET_free (e);
+      map->size--;
+      if (p == NULL)
+        e = map->map[i];
+      else
+        e = p->next;
+      ret++;
+    }
+    else
+    {
+      p = e;
+      e = e->next;
+    }
+  }
+  return ret;
+}
+
+
+/**
+ * Check if the map contains any value under the given
+ * key (including values that are NULL).
+ *
+ * @param map the map
+ * @param key the key to test if a value exists for it
+ * @return GNUNET_YES if such a value exists,
+ *         GNUNET_NO if not
+ */
+int
+GNUNET_CONTAINER_multihashmap32_contains (const struct
+                                          GNUNET_CONTAINER_MultiHashMap32 *map,
+                                          uint32_t key)
+{
+  struct MapEntry *e;
+
+  e = map->map[idx_of (map, key)];
+  while (e != NULL)
+  {
+    if (key == e->key)
+      return GNUNET_YES;
+    e = e->next;
+  }
+  return GNUNET_NO;
+}
+
+
+/**
+ * Check if the map contains the given value under the given
+ * key.
+ *
+ * @param map the map
+ * @param key the key to test if a value exists for it
+ * @param value value to test for
+ * @return GNUNET_YES if such a value exists,
+ *         GNUNET_NO if not
+ */
+int
+GNUNET_CONTAINER_multihashmap32_contains_value (const struct
+                                                GNUNET_CONTAINER_MultiHashMap32
+                                                *map, 
+                                                uint32_t key,
+                                                const void *value)
+{
+  struct MapEntry *e;
+
+  e = map->map[idx_of (map, key)];
+  while (e != NULL)
+  {
+    if ( (key == e->key) && (e->value == value) )
+      return GNUNET_YES;
+    e = e->next;
+  }
+  return GNUNET_NO;
+}
+
+
+/**
+ * Grow the given map to a more appropriate size.
+ *
+ * @param map the hash map to grow
+ */
+static void
+grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
+{
+  struct MapEntry **old_map;
+  struct MapEntry **new_map;
+  struct MapEntry *e;
+  unsigned int old_len;
+  unsigned int new_len;
+  unsigned int idx;
+  unsigned int i;
+
+  old_map = map->map;
+  old_len = map->map_length;
+  new_len = old_len * 2;
+  new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
+  map->map_length = new_len;
+  map->map = new_map;
+  for (i = 0; i < old_len; i++)
+  {
+    while (NULL != (e = old_map[i]))
+    {
+      old_map[i] = e->next;
+      idx = idx_of (map, e->key);
+      e->next = new_map[idx];
+      new_map[idx] = e;
+    }
+  }
+  GNUNET_free (old_map);
+}
+
+
+/**
+ * Store a key-value pair in the map.
+ *
+ * @param map the map
+ * @param key key to use
+ * @param value value to use
+ * @param opt options for put
+ * @return GNUNET_OK on success,
+ *         GNUNET_NO if a value was replaced (with REPLACE)
+ *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
+ *                       value already exists
+ */
+int
+GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
+                                     *map, uint32_t key, void *value,
+                                     enum GNUNET_CONTAINER_MultiHashMapOption
+                                     opt)
+{
+  struct MapEntry *e;
+  unsigned int i;
+
+  i = idx_of (map, key);
+  if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
+      (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
+  {
+    e = map->map[i];
+    while (e != NULL)
+    {
+      if (key == e->key)
+      {
+        if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
+          return GNUNET_SYSERR;
+        e->value = value;
+        return GNUNET_NO;
+      }
+      e = e->next;
+    }
+  }
+  if (map->size / 3 >= map->map_length / 4)
+  {
+    grow (map);
+    i = idx_of (map, key);
+  }
+  e = GNUNET_malloc (sizeof (struct MapEntry));
+  e->key = key;
+  e->value = value;
+  e->next = map->map[i];
+  map->map[i] = e;
+  map->size++;
+  return GNUNET_OK;
+}
+
+
+/**
+ * Iterate over all entries in the map that match a particular key.
+ *
+ * @param map the map
+ * @param key key that the entries must correspond to
+ * @param it function to call on each entry
+ * @param it_cls extra argument to it
+ * @return the number of key value pairs processed,
+ *         GNUNET_SYSERR if it aborted iteration
+ */
+int
+GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
+                                              GNUNET_CONTAINER_MultiHashMap32
+                                              *map, uint32_t key,
+                                              GNUNET_CONTAINER_HashMapIterator32 
+                                              it, void *it_cls)
+{
+  int count;
+  struct MapEntry *e;
+  struct MapEntry *n;
+
+  count = 0;
+  n = map->map[idx_of (map, key)];
+  while (NULL != (e = n))
+  {
+    n = e->next;
+    if (key != e->key)
+      continue;
+    if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
+      return GNUNET_SYSERR;
+    count++;
+  }
+  return count;
+}
+
+
+/* end of container_multihashmap.c */
diff --git a/src/util/test_container_multihashmap32.c b/src/util/test_container_multihashmap32.c
new file mode 100644
index 000000000..7997c73ac
--- /dev/null
+++ b/src/util/test_container_multihashmap32.c
@@ -0,0 +1,106 @@
+/*
+     This file is part of GNUnet.
+     (C) 2008 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 3, 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.
+*/
+
+/**
+ * @file util/test_container_multihashmap32.c
+ * @brief Test for container_multihashmap32.c
+ * @author Christian Grothoff
+ * @author Sree Harsha Totakura
+ */
+
+#include "platform.h"
+#include "gnunet_common.h"
+#include "gnunet_container_lib.h"
+
+#define ABORT() { fprintf(stderr, "Error at %s:%d\n", __FILE__, __LINE__); if (m != NULL) GNUNET_CONTAINER_multihashmap32_destroy(m); return 1; }
+#define CHECK(c) { if (! (c)) ABORT(); }
+
+static int
+testMap (int i)
+{
+  struct GNUNET_CONTAINER_MultiHashMap32 *m;
+  uint32_t k1;
+  uint32_t k2;
+  const char *ret;
+  int j;
+
+  CHECK (NULL != (m = GNUNET_CONTAINER_multihashmap32_create (i)));
+  k1 = 0;
+  k2 = UINT32_MAX;
+  CHECK (GNUNET_NO == GNUNET_CONTAINER_multihashmap32_contains (m, k1));
+  CHECK (GNUNET_NO == GNUNET_CONTAINER_multihashmap32_contains (m, k2));
+  CHECK (GNUNET_NO == GNUNET_CONTAINER_multihashmap32_remove (m, k1, NULL));
+  CHECK (GNUNET_NO == GNUNET_CONTAINER_multihashmap32_remove (m, k2, NULL));
+  CHECK (NULL == GNUNET_CONTAINER_multihashmap32_get (m, k1));
+  CHECK (NULL == GNUNET_CONTAINER_multihashmap32_get (m, k2));
+  CHECK (0 == GNUNET_CONTAINER_multihashmap32_remove_all (m, k1));
+  CHECK (0 == GNUNET_CONTAINER_multihashmap32_size (m));
+  CHECK (0 == GNUNET_CONTAINER_multihashmap32_iterate (m, NULL, NULL));
+  CHECK (0 == GNUNET_CONTAINER_multihashmap32_get_multiple (m, k1, NULL, NULL));
+
+  CHECK (GNUNET_OK ==
+         GNUNET_CONTAINER_multihashmap32_put (m, k1, "v1",
+                                              GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE));
+  CHECK (1 == GNUNET_CONTAINER_multihashmap32_size (m));
+  ret = GNUNET_CONTAINER_multihashmap32_get (m, k1);
+  GNUNET_assert (ret != NULL);
+  CHECK (0 == strcmp ("v1", ret));
+  CHECK (GNUNET_NO ==
+         GNUNET_CONTAINER_multihashmap32_put (m, k1, "v1",
+                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_REPLACE));
+  CHECK (1 == GNUNET_CONTAINER_multihashmap32_size (m));
+  CHECK (GNUNET_OK ==
+         GNUNET_CONTAINER_multihashmap32_put (m, k1, "v2",
+                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
+  CHECK (GNUNET_OK ==
+         GNUNET_CONTAINER_multihashmap32_put (m, k1, "v3",
+                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
+  CHECK (3 == GNUNET_CONTAINER_multihashmap32_size (m));
+  CHECK (GNUNET_OK == GNUNET_CONTAINER_multihashmap32_remove (m, k1, "v3"));
+  CHECK (2 == GNUNET_CONTAINER_multihashmap32_size (m));
+  CHECK (GNUNET_YES == GNUNET_CONTAINER_multihashmap32_contains (m, k1));
+  CHECK (GNUNET_NO == GNUNET_CONTAINER_multihashmap32_contains (m, k2));
+  CHECK (2 == GNUNET_CONTAINER_multihashmap32_get_multiple (m, k1, NULL, NULL));
+  CHECK (0 == GNUNET_CONTAINER_multihashmap32_get_multiple (m, k2, NULL, NULL));
+  CHECK (2 == GNUNET_CONTAINER_multihashmap32_iterate (m, NULL, NULL));
+  CHECK (2 == GNUNET_CONTAINER_multihashmap32_remove_all (m, k1));
+  for (j = 0; j < 1024; j++)
+    CHECK (GNUNET_OK ==
+           GNUNET_CONTAINER_multihashmap32_put (m, k1, "v2",
+                                                GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE));
+  GNUNET_CONTAINER_multihashmap32_destroy (m);
+  return 0;
+}
+
+int
+main (int argc, char *argv[])
+{
+  int failureCount = 0;
+  int i;
+
+  GNUNET_log_setup ("test-container-multihashmap", "WARNING", NULL);
+  for (i = 1; i < 255; i++)
+    failureCount += testMap (i);
+  if (failureCount != 0)
+    return 1;
+  return 0;
+}
+
+/* end of test_container_multihashmap.c */