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 maybe 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 struct MapEntry
  32 {
  33   GNUNET_HashCode key;
  34   void *value;
  35   struct MapEntry *next;
  36 };
  37
  38 struct GNUNET_CONTAINER_MultiHashMap
  39 {
  40
  41   struct MapEntry **map;
  42
  43   unsigned int size;
  44
  45   unsigned int map_length;
  46 };
  47
  48 struct GNUNET_CONTAINER_MultiHashMap *
  49 GNUNET_CONTAINER_multihashmap_create (unsigned int len)
  50 {
  51   struct GNUNET_CONTAINER_MultiHashMap *ret;
  52
  53   ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
  54   ret->size = 0;
  55   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
  56   memset (ret->map, 0, len * sizeof (struct MapEntry *));
  57   ret->map_length = len;
  58   return ret;
  59 }
  60
  61 void
  62 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
  63                                        *map)
  64 {
  65   unsigned int i;
  66   struct MapEntry *e;
  67
  68   for (i = 0; i < map->map_length; i++)
  69     {
  70       while (NULL != (e = map->map[i]))
  71         {
  72           map->map[i] = e->next;
  73           GNUNET_free (e);
  74         }
  75     }
  76   GNUNET_free (map->map);
  77   GNUNET_free (map);
  78 }
  79
  80 static unsigned int
  81 idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m,
  82         const GNUNET_HashCode * key)
  83 {
  84   return (*(unsigned int *) key) % m->map_length;
  85 }
  86
  87 unsigned int
  88 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
  89                                     *map)
  90 {
  91   return map->size;
  92 }
  93
  94 void *
  95 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
  96                                    *map, const GNUNET_HashCode * key)
  97 {
  98   struct MapEntry *e;
  99
 100   e = map->map[idx_of (map, key)];
 101   while (e != NULL)
 102     {
 103       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 104         return e->value;
 105       e = e->next;
 106     }
 107   return NULL;
 108 }
 109
 110 int
 111 GNUNET_CONTAINER_multihashmap_iterate (const struct
 112                                        GNUNET_CONTAINER_MultiHashMap *map,
 113                                        GNUNET_CONTAINER_HashMapIterator it,
 114                                        void *cls)
 115 {
 116   int count;
 117   unsigned int i;
 118   struct MapEntry *e;
 119
 120   count = 0;
 121   for (i = 0; i < map->map_length; i++)
 122     {
 123       e = map->map[i];
 124       while (e != NULL)
 125         {
 126           if ((NULL != it) && (GNUNET_OK != it (&e->key, e->value, cls)))
 127             return GNUNET_SYSERR;
 128           count++;
 129           e = e->next;
 130         }
 131     }
 132   return count;
 133 }
 134
 135 int
 136 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
 137                                       *map, const GNUNET_HashCode * key,
 138                                       void *value)
 139 {
 140   struct MapEntry *e;
 141   struct MapEntry *p;
 142   unsigned int i;
 143
 144   i = idx_of (map, key);
 145   p = NULL;
 146   e = map->map[i];
 147   while (e != NULL)
 148     {
 149       if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
 150           (value == e->value))
 151         {
 152           if (p == NULL)
 153             map->map[i] = e->next;
 154           else
 155             p->next = e->next;
 156           GNUNET_free (e);
 157           map->size--;
 158           return GNUNET_YES;
 159         }
 160       p = e;
 161       e = e->next;
 162     }
 163   return GNUNET_NO;
 164 }
 165
 166 int
 167 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
 168                                           *map, const GNUNET_HashCode * key)
 169 {
 170   struct MapEntry *e;
 171   struct MapEntry *p;
 172   unsigned int i;
 173   int ret;
 174
 175   ret = 0;
 176   i = idx_of (map, key);
 177   p = NULL;
 178   e = map->map[i];
 179   while (e != NULL)
 180     {
 181       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 182         {
 183           if (p == NULL)
 184             map->map[i] = e->next;
 185           else
 186             p->next = e->next;
 187           GNUNET_free (e);
 188           map->size--;
 189           if (p == NULL)
 190             e = map->map[i];
 191           else
 192             e = p->next;
 193           ret++;
 194         }
 195       else
 196         {
 197           p = e;
 198           e = e->next;
 199         }
 200     }
 201   return ret;
 202 }
 203
 204 int
 205 GNUNET_CONTAINER_multihashmap_contains (const struct
 206                                         GNUNET_CONTAINER_MultiHashMap *map,
 207                                         const GNUNET_HashCode * key)
 208 {
 209   struct MapEntry *e;
 210   unsigned int i;
 211
 212   i = idx_of (map, key);
 213   e = map->map[i];
 214   while (e != NULL)
 215     {
 216       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 217         return GNUNET_YES;
 218       e = e->next;
 219     }
 220   return GNUNET_NO;
 221 }
 222
 223 static void
 224 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 225 {
 226   struct MapEntry **old;
 227   struct MapEntry *e;
 228   unsigned int i;
 229   unsigned int l;
 230
 231   old = map->map;
 232   l = map->map_length;
 233   map->map_length *= 2;
 234   map->map = GNUNET_malloc (sizeof (struct MapEntry *) * map->map_length);
 235   memset (map->map, 0, sizeof (struct MapEntry *) * map->map_length);
 236   for (i = 0; i < l; i++)
 237     {
 238       while (NULL != (e = old[i]))
 239         {
 240           old[i] = e->next;
 241           e->next = map->map[idx_of (map, &e->key)];
 242           map->map[idx_of (map, &e->key)] = e;
 243         }
 244     }
 245   GNUNET_free (old);
 246 }
 247
 248 int
 249 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
 250                                    const GNUNET_HashCode * key,
 251                                    void *value,
 252                                    enum GNUNET_CONTAINER_MultiHashMapOption
 253                                    opt)
 254 {
 255   struct MapEntry *e;
 256   unsigned int i;
 257
 258   i = idx_of (map, key);
 259   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
 260       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 261     {
 262       e = map->map[i];
 263       while (e != NULL)
 264         {
 265           if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
 266               (value == e->value))
 267             {
 268               if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
 269                 return GNUNET_SYSERR;
 270               e->value = value;
 271               return GNUNET_NO;
 272             }
 273           e = e->next;
 274         }
 275     }
 276   if (map->size / 3 > map->map_length / 4)
 277     grow (map);
 278   e = GNUNET_malloc (sizeof (struct MapEntry));
 279   e->key = *key;
 280   e->value = value;
 281   e->next = map->map[i];
 282   map->map[i] = e;
 283   map->size++;
 284   return GNUNET_OK;
 285 }
 286
 287 int
 288 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 289                                             GNUNET_CONTAINER_MultiHashMap
 290                                             *map, const GNUNET_HashCode * key,
 291                                             GNUNET_CONTAINER_HashMapIterator
 292                                             it, void *cls)
 293 {
 294   int count;
 295   struct MapEntry *e;
 296
 297   count = 0;
 298   e = map->map[idx_of (map, key)];
 299   while (e != NULL)
 300     {
 301       if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
 302         {
 303           if ((it != NULL) && (GNUNET_OK != it (&e->key, e->value, cls)))
 304             return GNUNET_SYSERR;
 305           count++;
 306         }
 307       e = e->next;
 308     }
 309   return count;
 310 }
 311
 312 void *
 313 GNUNET_CONTAINER_multihashmap_get_random (const struct
 314                                           GNUNET_CONTAINER_MultiHashMap *map)
 315 {
 316   unsigned int rand;
 317   struct MapEntry *e;
 318   e = NULL;
 319
 320   if (map->size == 0)
 321     return NULL;
 322
 323   while (e == NULL)
 324     {
 325       rand =
 326         GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 327                                   map->map_length);
 328       e = map->map[rand];
 329     }
 330
 331   return e->value;
 332 }
 333
 334 /* end of multihashmap.c */