2 This file is part of GNUnet.
3 (C) 2008 Christian Grothoff (and other contributing authors)
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.
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.
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.
21 * @file util/container_multihashmap.c
22 * @brief hash map where the same key maybe present multiple times
23 * @author Christian Grothoff
27 #include "gnunet_common.h"
28 #include "gnunet_container_lib.h"
29 #include "gnunet_crypto_lib.h"
35 struct MapEntry *next;
38 struct GNUNET_CONTAINER_MultiHashMap
41 struct MapEntry **map;
45 unsigned int map_length;
48 struct GNUNET_CONTAINER_MultiHashMap *
49 GNUNET_CONTAINER_multihashmap_create (unsigned int len)
51 struct GNUNET_CONTAINER_MultiHashMap *ret;
53 ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
55 ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
56 memset (ret->map, 0, len * sizeof (struct MapEntry *));
57 ret->map_length = len;
62 GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
68 for (i = 0; i < map->map_length; i++)
70 while (NULL != (e = map->map[i]))
72 map->map[i] = e->next;
76 GNUNET_free (map->map);
81 idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m,
82 const GNUNET_HashCode * key)
84 return (*(unsigned int *) key) % m->map_length;
88 GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
95 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
96 *map, const GNUNET_HashCode * key)
100 e = map->map[idx_of (map, key)];
103 if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
111 GNUNET_CONTAINER_multihashmap_iterate (const struct
112 GNUNET_CONTAINER_MultiHashMap *map,
113 GNUNET_CONTAINER_HashMapIterator it,
121 for (i = 0; i < map->map_length; i++)
126 if ((NULL != it) && (GNUNET_OK != it (&e->key, e->value, cls)))
127 return GNUNET_SYSERR;
136 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap
137 *map, const GNUNET_HashCode * key,
144 i = idx_of (map, key);
149 if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
153 map->map[i] = e->next;
167 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
168 *map, const GNUNET_HashCode * key)
176 i = idx_of (map, key);
181 if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
184 map->map[i] = e->next;
205 GNUNET_CONTAINER_multihashmap_contains (const struct
206 GNUNET_CONTAINER_MultiHashMap *map,
207 const GNUNET_HashCode * key)
212 i = idx_of (map, key);
216 if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
224 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
226 struct MapEntry **old;
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++)
238 while (NULL != (e = old[i]))
241 e->next = map->map[idx_of (map, &e->key)];
242 map->map[idx_of (map, &e->key)] = e;
249 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
250 const GNUNET_HashCode * key,
252 enum GNUNET_CONTAINER_MultiHashMapOption
258 i = idx_of (map, key);
259 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
260 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
265 if ((0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode))) &&
268 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
269 return GNUNET_SYSERR;
276 if (map->size / 3 > map->map_length / 4)
278 e = GNUNET_malloc (sizeof (struct MapEntry));
281 e->next = map->map[i];
288 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
289 GNUNET_CONTAINER_MultiHashMap
290 *map, const GNUNET_HashCode * key,
291 GNUNET_CONTAINER_HashMapIterator
298 e = map->map[idx_of (map, key)];
301 if (0 == memcmp (key, &e->key, sizeof (GNUNET_HashCode)))
303 if ((it != NULL) && (GNUNET_OK != it (&e->key, e->value, cls)))
304 return GNUNET_SYSERR;
313 GNUNET_CONTAINER_multihashmap_get_random (const struct
314 GNUNET_CONTAINER_MultiHashMap *map)
326 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
334 /* end of multihashmap.c */