src/util/container_multihashmap.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2008 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20 /**
  21  * @file util/container_multihashmap.c
  22  * @brief hash map where the same key may be present multiple times
  23  * @author Christian Grothoff
  24  */
  25
  26 #include "platform.h"
  27 #include "gnunet_common.h"
  28 #include "gnunet_container_lib.h"
  29 #include "gnunet_crypto_lib.h"
  30
  31 /**
  32  *
  33  */
  34 struct MapEntry
  35 {
  36   GNUNET_HashCode key;
  37   void *value;
  38   struct MapEntry *next;
  39 };
  40
  41 /**
  42  *
  43  */
  44 struct GNUNET_CONTAINER_MultiHashMap
  45 {
  46
  47   struct MapEntry **map;
  48
  49   unsigned int size;
  50
  51   unsigned int map_length;
  52 };
  53
  54
  55 struct GNUNET_CONTAINER_MultiHashMap *
  56 GNUNET_CONTAINER_multihashmap_create (unsigned int len)
  57 {
  58   struct GNUNET_CONTAINER_MultiHashMap *ret;
  59
  60   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
  61   ret->size = 0;
  62   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
  63   memset (ret->map, 0, len * sizeof (struct MapEntry *));
  64   ret->map_length = len;
  65   return ret;
  66 }
  67
  68
  69 void
  70 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
  71                                        *map)
  72 {
  73   unsigned int i;
  74   struct MapEntry *e;
  75
  76   for (i = 0; i < map->map_length; i++)
  77     {
  78       while (NULL != (e = map->map[i]))
  79         {
  80           map->map[i] = e->next;
  81           GNUNET_free (e);
  82         }
  83     }
  84   GNUNET_free (map->map);
  85   GNUNET_free (map);
  86 }
  87
  88 static unsigned int
  89 idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m,
  90         const GNUNET_HashCode * key)
  91 {
  92   return (*(unsigned int *) key) % m->map_length;
  93 }
  94
  95
  96 unsigned int
  97 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
  98                                     *map)
  99 {
 100   return map->size;
 101 }
 102
 103
 104 void *
 105 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
 106                                    *map, const GNUNET_HashCode * key)
 107 {
 108   struct MapEntry *e;
 109
 110   e = map->map[idx_of (map, key)];
 111   while (e != NULL)
 112     {
 113       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 114         return e->value;
 115       e = e->next;
 116     }
 117   return NULL;
 118 }
 119
 120
 121 int
 122 GNUNET_CONTAINER_multihashmap_iterate (const struct
 123                                        GNUNET_CONTAINER_MultiHashMap *map,
 124                                        GNUNET_CONTAINER_HashMapIterator it,
 125                                        void *cls)
 126 {
 127   int count;
 128   unsigned int i;
 129   struct MapEntry *e;
 130
 131   count = 0;
 132   for (i = 0; i < map->map_length; i++)
 133     {
 134       e = map->map[i];
 135       while (e != NULL)
 136         {
 137           if ((NULL != it) && (GNUNET_OK != it (cls, &e->key, e->value)))
 138             return GNUNET_SYSERR;
 139           count++;
 140           e = e->next;
 141         }
 142     }
 143   return count;
 144 }
 145
 146
 147 int
 148 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 149                                       *map, const GNUNET_HashCode * key,
 150                                       void *value)
 151 {
 152   struct MapEntry *e;
 153   struct MapEntry *p;
 154   unsigned int i;
 155
 156   i = idx_of (map, key);
 157   p = NULL;
 158   e = map->map[i];
 159   while (e != NULL)
 160     {
 161       if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
 162           (value == e->value))
 163         {
 164           if (p == NULL)
 165             map->map[i] = e->next;
 166           else
 167             p->next = e->next;
 168           GNUNET_free (e);
 169           map->size--;
 170           return GNUNET_YES;
 171         }
 172       p = e;
 173       e = e->next;
 174     }
 175   return GNUNET_NO;
 176 }
 177
 178
 179 int
 180 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
 181                                           *map, const GNUNET_HashCode * key)
 182 {
 183   struct MapEntry *e;
 184   struct MapEntry *p;
 185   unsigned int i;
 186   int ret;
 187
 188   ret = 0;
 189   i = idx_of (map, key);
 190   p = NULL;
 191   e = map->map[i];
 192   while (e != NULL)
 193     {
 194       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 195         {
 196           if (p == NULL)
 197             map->map[i] = e->next;
 198           else
 199             p->next = e->next;
 200           GNUNET_free (e);
 201           map->size--;
 202           if (p == NULL)
 203             e = map->map[i];
 204           else
 205             e = p->next;
 206           ret++;
 207         }
 208       else
 209         {
 210           p = e;
 211           e = e->next;
 212         }
 213     }
 214   return ret;
 215 }
 216
 217
 218 int
 219 GNUNET_CONTAINER_multihashmap_contains (const struct
 220                                         GNUNET_CONTAINER_MultiHashMap *map,
 221                                         const GNUNET_HashCode * key)
 222 {
 223   struct MapEntry *e;
 224   unsigned int i;
 225
 226   i = idx_of (map, key);
 227   e = map->map[i];
 228   while (e != NULL)
 229     {
 230       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 231         return GNUNET_YES;
 232       e = e->next;
 233     }
 234   return GNUNET_NO;
 235 }
 236
 237
 238 static void
 239 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 240 {
 241   struct MapEntry **old;
 242   struct MapEntry *e;
 243   unsigned int i;
 244   unsigned int l;
 245
 246   old = map->map;
 247   l = map->map_length;
 248   map->map_length *= 2;
 249   map->map = GNUNET_malloc (sizeof (struct MapEntry *) * map->map_length);
 250   memset (map->map, 0, sizeof (struct MapEntry *) * map->map_length);
 251   for (i = 0; i < l; i++)
 252     {
 253       while (NULL != (e = old[i]))
 254         {
 255           old[i] = e->next;
 256           e->next = map->map[idx_of (map, &e->key)];
 257           map->map[idx_of (map, &e->key)] = e;
 258         }
 259     }
 260   GNUNET_free (old);
 261 }
 262
 263
 264 int
 265 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 266                                    const GNUNET_HashCode * key,
 267                                    void *value,
 268                                    enum GNUNET_CONTAINER_MultiHashMapOption
 269                                    opt)
 270 {
 271   struct MapEntry *e;
 272   unsigned int i;
 273
 274   i = idx_of (map, key);
 275   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 276       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 277     {
 278       e = map->map[i];
 279       while (e != NULL)
 280         {
 281           if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
 282               (value == e->value))
 283             {
 284               if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 285                 return GNUNET_SYSERR;
 286               e->value = value;
 287               return GNUNET_NO;
 288             }
 289           e = e->next;
 290         }
 291     }
 292   if (map->size / 3 > map->map_length / 4)
 293     grow (map);
 294   e = GNUNET_malloc (sizeof (struct MapEntry));
 295   e->key = *key;
 296   e->value = value;
 297   e->next = map->map[i];
 298   map->map[i] = e;
 299   map->size++;
 300   return GNUNET_OK;
 301 }
 302
 303
 304 int
 305 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 306                                             GNUNET_CONTAINER_MultiHashMap
 307                                             *map, const GNUNET_HashCode * key,
 308                                             GNUNET_CONTAINER_HashMapIterator
 309                                             it, void *cls)
 310 {
 311   int count;
 312   struct MapEntry *e;
 313
 314   count = 0;
 315   e = map->map[idx_of (map, key)];
 316   while (e != NULL)
 317     {
 318       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 319         {
 320           if ((it != NULL) && (GNUNET_OK != it (&e->key, e->value, cls)))
 321             return GNUNET_SYSERR;
 322           count++;
 323         }
 324       e = e->next;
 325     }
 326   return count;
 327 }
 328
 329
 330 void *
 331 GNUNET_CONTAINER_multihashmap_get_random (const struct
 332                                           GNUNET_CONTAINER_MultiHashMap *map)
 333 {
 334   unsigned int rand;
 335   struct MapEntry *e;
 336   e = NULL;
 337
 338   if (map->size == 0)
 339     return NULL;
 340
 341   while (e == NULL)
 342     {
 343       rand =
 344         GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 345                                   map->map_length);
 346       e = map->map[rand];
 347     }
 348
 349   return e->value;
 350 }
 351
 352 /* end of container_multihashmap.c */