[GNUnet-SVN] r7797 - in GNUnet/src: applications/advertising applications/vpn include util/containers

[gnunet]

Author: grothoff
Date: 2008-10-17 10:59:52 -0600 (Fri, 17 Oct 2008)
New Revision: 7797

Added:
   GNUnet/src/util/containers/multihashmap.c
Removed:
   GNUnet/src/util/containers/hashtest.c
Modified:
   GNUnet/src/applications/advertising/bootstrap.c
   GNUnet/src/applications/vpn/vpn.c
   GNUnet/src/include/gnunet_util_containers.h
   GNUnet/src/util/containers/Makefile.am
Log:
hashmap

Modified: GNUnet/src/applications/advertising/bootstrap.c
===================================================================
--- GNUnet/src/applications/advertising/bootstrap.c     2008-10-17 15:14:12 UTC 
(rev 7796)
+++ GNUnet/src/applications/advertising/bootstrap.c     2008-10-17 16:59:52 UTC 
(rev 7797)
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     (C) 2001, 2002, 2003, 2004, 2006 Christian Grothoff (and other 
contributing authors)
+     (C) 2001, 2002, 2003, 2004, 2006, 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
@@ -33,7 +33,7 @@
 
 #define DEBUG_BOOTSTRAP GNUNET_NO
 
-#define hello_HELPER_TABLE_START_SIZE 64
+#define HELLO_HELPER_TABLE_START_SIZE 64
 
 static GNUNET_CoreAPIForPlugins *coreAPI;
 
@@ -56,8 +56,7 @@
 static int
 testTerminate (void *cls)
 {
-  HelloListClosure *c = cls;
-  return !c->do_shutdown;
+  return !hlc.do_shutdown;
 }
 
 static void
@@ -123,16 +122,15 @@
 static void
 downloadHostlistCallback (const GNUNET_MessageHello * hello, void *c)
 {
-  HelloListClosure *cls = c;
-  if (cls->hellosCount >= cls->hellosLen)
+  if (hlc.hellosCount >= hlc.hellosLen)
     {
-      GNUNET_array_grow (cls->hellos,
-                         cls->hellosLen,
-                         cls->hellosLen + hello_HELPER_TABLE_START_SIZE);
+      GNUNET_array_grow (hlc.hellos,
+                         hlc.hellosLen,
+                         hlc.hellosLen + HELLO_HELPER_TABLE_START_SIZE);
     }
-  cls->hellos[cls->hellosCount++] =
+  hlc.hellos[hlc.hellosCount++] =
     GNUNET_malloc (ntohs (hello->header.size));
-  memcpy (cls->hellos[cls->hellosCount - 1], hello,
+  memcpy (hlc.hellos[hlc.hellosCount - 1], hello,
           ntohs (hello->header.size));
 }
 
@@ -211,7 +209,7 @@
       hlc.hellosLen = 0;
       hlc.hellosCount = 0;
       bootstrap->bootstrap (&downloadHostlistCallback,
-                            &hlc, &testTerminate, &hlc);
+                            NULL, &testTerminate, NULL);
       GNUNET_array_grow (hlc.hellos, hlc.hellosLen, hlc.hellosCount);
       processhellos (&hlc);
     }

Modified: GNUnet/src/applications/vpn/vpn.c
===================================================================
--- GNUnet/src/applications/vpn/vpn.c   2008-10-17 15:14:12 UTC (rev 7796)
+++ GNUnet/src/applications/vpn/vpn.c   2008-10-17 16:59:52 UTC (rev 7797)
@@ -292,7 +292,7 @@
   if (fd < 0)
     {
       GNUNET_GE_LOG (ectx, GNUNET_GE_ERROR | GNUNET_GE_BULK | GNUNET_GE_USER,
-                     _("Cannot open tunnel device because of %s"),
+                     _("Cannot open tunnel device: %s"),
                      strerror (fd));
       GNUNET_GE_DIE_STRERROR (ectx,
                               GNUNET_GE_FATAL | GNUNET_GE_ADMIN |

Modified: GNUnet/src/include/gnunet_util_containers.h
===================================================================
--- GNUnet/src/include/gnunet_util_containers.h 2008-10-17 15:14:12 UTC (rev 
7796)
+++ GNUnet/src/include/gnunet_util_containers.h 2008-10-17 16:59:52 UTC (rev 
7797)
@@ -331,6 +331,42 @@
  */
 int GNUNET_meta_data_test_for_directory (const struct GNUNET_MetaData *md);
 
+
+/* ******************************* HashMap **************************** */
+
+struct GNUNET_MultiHashMap;
+
+enum GNUNET_MultiHashMapOption {
+  GNUNET_MultiHashMapOption_REPLACE,
+  GNUNET_MultiHashMapOption_MULTIPLE,
+  GNUNET_MultiHashMapOption_UNIQUE_ONLY
+};
+
+struct GNUNET_MultiHashMap *
+GNUNET_multi_hash_map_create(unsigned int len);
+
+void GNUNET_multi_hash_map_destroy(struct GNUNET_MultiHashMap* map);
+
+void * GNUNET_multi_hash_map_get(struct GNUNET_MultiHashMap* map,
+                                const GNUNET_HashCode * key);
+
+int GNUNET_multi_hash_map_remove(struct GNUNET_MultiHashMap* map,
+                                const GNUNET_HashCode * key,
+                                void * value);
+
+int GNUNET_multi_hash_map_remove_all(struct GNUNET_MultiHashMap* map,
+                                    const GNUNET_HashCode * key);
+
+int GNUNET_multi_hash_map_contains(struct GNUNET_MultiHashMap* map,
+                                  const GNUNET_HashCode * key);
+
+int GNUNET_multi_hash_map_put(struct GNUNET_MultiHashMap* map,
+                             const GNUNET_HashCode * key,
+                             void * value,
+                             enum GNUNET_MultiHashMapOptions opt);
+
+
+
 #if 0                           /* keep Emacsens' auto-indent happy */
 {
 #endif

Modified: GNUnet/src/util/containers/Makefile.am
===================================================================
--- GNUnet/src/util/containers/Makefile.am      2008-10-17 15:14:12 UTC (rev 
7796)
+++ GNUnet/src/util/containers/Makefile.am      2008-10-17 16:59:52 UTC (rev 
7797)
@@ -6,7 +6,8 @@
 
 libcontainers_la_SOURCES = \
  bloomfilter.c \
- meta.c 
+ meta.c \
+ multihashmap.c 
 
 libcontainers_la_LIBADD = \
  -lz \

Deleted: GNUnet/src/util/containers/hashtest.c
===================================================================
--- GNUnet/src/util/containers/hashtest.c       2008-10-17 15:14:12 UTC (rev 
7796)
+++ GNUnet/src/util/containers/hashtest.c       2008-10-17 16:59:52 UTC (rev 
7797)
@@ -1,52 +0,0 @@
-/**
- * @file test/hashtest.c
- * @brief testcase for util/hashing.c
- */
-
-#include "gnunet_util.h"
-#include "platform.h"
-
-/**
- * Perform option parsing from the command line.
- */
-static int
-parseCommandLine (int argc, char *argv[])
-{
-  return GNUNET_OK;
-}
-
-int
-main (int argc, char *argv[])
-{
-  GNUNET_HashCode hc;
-
-  initUtil (argc, argv, &parseCommandLine);
-  GNUNET_hash ("TEST", 4, &hc);
-  if ((hc.bits[0] != ntohl (2080019878)) ||
-      (hc.bits[1] != ntohl (-2003678137)) ||
-      (hc.bits[2] != ntohl (-942529663)) ||
-      (hc.bits[3] != ntohl (-234043098)) ||
-      (hc.bits[4] != ntohl (-182141268)))
-    {
-      printf ("Hash of TEST wrong (%d, %d, %d, %d, %d).\n",
-              ntohl (hc.bits[0]),
-              ntohl (hc.bits[1]),
-              ntohl (hc.bits[2]), ntohl (hc.bits[3]), ntohl (hc.bits[4]));
-      return -1;
-    }
-  GNUNET_hash (NULL, 0, &hc);
-  if ((hc.bits[0] != ntohl (-813440715)) ||
-      (hc.bits[1] != ntohl (2129639613)) ||
-      (hc.bits[2] != ntohl (-246142896)) ||
-      (hc.bits[3] != ntohl (-697466873)) ||
-      (hc.bits[4] != ntohl (-702487547)))
-    {
-      printf ("Hash of nothing (0-size) wrong  (%d, %d, %d, %d, %d).\n",
-              ntohl (hc.bits[0]),
-              ntohl (hc.bits[1]),
-              ntohl (hc.bits[2]), ntohl (hc.bits[3]), ntohl (hc.bits[4]));
-      return -1;
-    }
-  doneUtil ();
-  return 0;
-}

Added: GNUnet/src/util/containers/multihashmap.c
===================================================================
--- GNUnet/src/util/containers/multihashmap.c                           (rev 0)
+++ GNUnet/src/util/containers/multihashmap.c   2008-10-17 16:59:52 UTC (rev 
7797)
@@ -0,0 +1,245 @@
+/*
+     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/containers/multihashmap.c
+ * @brief hash map where the same key maybe present multiple times
+ * @author Christian Grothoff
+ */
+
+#include "platform.h"
+#include "gnunet_util.h"
+#include "gnunet_util_containers.h"
+
+struct MapEntry {
+  GNUNET_HashCode key;
+  void * value;
+  struct MapEntry * next;
+};
+
+struct GNUNET_MultiHashMap {
+
+  struct MapEntry ** map;
+
+  unsigned int size;
+
+  unsigned int map_length;
+};
+
+struct GNUNET_MultiHashMap *
+GNUNET_multi_hash_map_create(unsigned int len) 
+{
+  struct GNUNET_MultiHashMap * ret;
+
+  ret = GNUNET_malloc(sizeof(struct GNUNET_MultiHashMap));
+  ret->size = 0;
+  ret->map = GNUNET_malloc(len * sizeof(struct MapEntry*));
+  memset(ret->map, 0, len * sizeof(struct MapEntry*));
+  ret->map_length = len;
+  return ret;
+}
+
+void GNUNET_multi_hash_map_destroy(struct GNUNET_MultiHashMap* 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);
+}
+
+static unsigned int 
+idx_of(struct GNUNET_MultiHashMap * m,
+       const GNUNET_HashCode * key) 
+{
+  return (*(unsigned int *) key) % m->map_length;
+}
+
+
+void * 
+GNUNET_multi_hash_map_get(struct GNUNET_MultiHashMap* map,
+                                const GNUNET_HashCode * key) 
+{
+  struct MapEntry* e;
+
+  e = map->map[idx_of(map, key)];
+  while (e != NULL)
+    {
+      if (0 == memcmp(key, e->key, sizeof(GNUNET_HashCode)))
+       return e->value;
+      e = e->next;
+    }
+  return NULL;
+}
+
+int GNUNET_multi_hash_map_remove(struct GNUNET_MultiHashMap* map,
+                                const GNUNET_HashCode * 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 ( (0 == memcmp(key, e->key, sizeof(GNUNET_HashCode))) &&
+          (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;
+}
+
+int GNUNET_multi_hash_map_remove_all(struct GNUNET_MultiHashMap* map,
+                                    const GNUNET_HashCode * 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 (0 == memcmp(key, e->key, sizeof(GNUNET_HashCode)))
+       {
+         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;
+}
+
+int GNUNET_multi_hash_map_contains(struct GNUNET_MultiHashMap* map,
+                                  const GNUNET_HashCode * key) 
+{
+  struct MapEntry* e;
+  unsigned int i;
+  
+  i = idx_of(map, key);
+  e = map->map[i];
+  while (e != NULL)
+    {
+      if ( (0 == memcmp(key, e->key, sizeof(GNUNET_HashCode))) &&
+          (value == e->value) )
+       return GNUNET_YES;
+      e = e->next;
+    }
+  return GNUNET_NO;
+}
+
+static void 
+grow(struct GNUNET_MultiHashMap * map)
+{
+  struct MapEntry** old;
+  struct MapEntry* e;
+  unsigned int i;
+  unsigned int l;
+
+  old = map->map;
+  l = map->map_length;
+  map->map_length *= 2;
+  map->map = GNUNET_malloc(sizeof(struct MapEntry*)*map->map_length);
+  memset(map->map, 0, sizeof(struct MapEntry*)*map->map_length);
+  for (i=0;i<l;i++)
+    {
+      while (NULL != (e = old[i]))
+       {         
+         old[i] = e->next;
+         e->next = map->map[idx_of(e->key)];
+         map->map[idx_of(e->key)] = e;
+       }
+    }
+  GNUNET_free(old);
+}
+
+int GNUNET_multi_hash_map_put(struct GNUNET_MultiHashMap* map,
+                             const GNUNET_HashCode * key,
+                             void * value,
+                             enum GNUNET_MultiHashMapOptions opt) 
+{
+  struct MapEntry* e;
+  unsigned int i;
+  
+  i = idx_of(map, key);
+  if (opt != GNUNET_MultiHashMapOption_MULTIPLE)
+    {
+      e = map->map[i];
+      while (e != NULL)
+       {
+         if ( (0 == memcmp(key, e->key, sizeof(GNUNET_HashCode))) &&
+              (value == e->value) )
+           {
+             if (opt == GNUNET_MultiHashMapOption_UNIQUE)
+               return GNUNET_SYSERR;
+             e->value = value;
+             return GNUNET_NO;
+           }
+         e = e->next;
+       }
+    }
+  if (map->size / 3 > map->map_length / 4)
+    grow(map);
+  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;
+}
+
+/* end of multihashmap.c */