Merge branch 'master' of ssh://gnunet.org/gnunet
[oweals/gnunet.git] / src / util / container_multihashmap32.c
1 /*
2      This file is part of GNUnet.
3      Copyright (C) 2008 GNUnet e.V.
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 3, 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., 51 Franklin Street, Fifth Floor,
18      Boston, MA 02110-1301, USA.
19 */
20 /**
21  * @file util/container_multihashmap32.c
22  * @brief a version of hash map implemented in container_multihashmap.c but with
23  *          uint32_t as keys
24  * @author Christian Grothoff
25  * @author Sree Harsha Totakura
26  */
27
28 #include "platform.h"
29 #include "gnunet_container_lib.h"
30
31 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
32
33 /**
34  * An entry in the hash map.
35  */
36 struct MapEntry
37 {
38
39   /**
40    * Key for the entry.
41    */
42   uint32_t key;
43
44   /**
45    * Value of the entry.
46    */
47   void *value;
48
49   /**
50    * If there is a hash collision, we create a linked list.
51    */
52   struct MapEntry *next;
53
54 };
55
56 /**
57  * Internal representation of the hash map.
58  */
59 struct GNUNET_CONTAINER_MultiHashMap32
60 {
61
62   /**
63    * All of our buckets.
64    */
65   struct MapEntry **map;
66
67   /**
68    * Number of entries in the map.
69    */
70   unsigned int size;
71
72   /**
73    * Length of the "map" array.
74    */
75   unsigned int map_length;
76
77   /**
78    * Counts the destructive modifications (grow, remove)
79    * to the map, so that iterators can check if they are still valid.
80    */
81   unsigned int modification_counter;
82 };
83
84
85 /**
86  * Cursor into a multihashmap.
87  * Allows to enumerate elements asynchronously.
88  */
89 struct GNUNET_CONTAINER_MultiHashMap32Iterator
90 {
91   /**
92    * Position in the bucket 'idx'
93    */
94   struct MapEntry *me;
95
96   /**
97    * Current bucket index.
98    */
99   unsigned int idx;
100
101   /**
102    * Modification counter as observed on the map when the iterator
103    * was created.
104    */
105   unsigned int modification_counter;
106
107   /**
108    * Map that we are iterating over.
109    */
110   const struct GNUNET_CONTAINER_MultiHashMap32 *map;
111 };
112
113
114 /**
115  * Create a multi hash map.
116  *
117  * @param len initial size (map will grow as needed)
118  * @return NULL on error
119  */
120 struct GNUNET_CONTAINER_MultiHashMap32 *
121 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
122 {
123   struct GNUNET_CONTAINER_MultiHashMap32 *ret;
124
125   GNUNET_assert (len > 0);
126   ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
127   ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
128   ret->map_length = len;
129   return ret;
130 }
131
132
133 /**
134  * Destroy a hash map.  Will not free any values
135  * stored in the hash map!
136  *
137  * @param map the map
138  */
139 void
140 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
141                                          *map)
142 {
143   unsigned int i;
144   struct MapEntry *e;
145
146   for (i = 0; i < map->map_length; i++)
147   {
148     while (NULL != (e = map->map[i]))
149     {
150       map->map[i] = e->next;
151       GNUNET_free (e);
152     }
153   }
154   GNUNET_free (map->map);
155   GNUNET_free (map);
156 }
157
158
159 /**
160  * Compute the index of the bucket for the given key.
161  *
162  * @param m hash map for which to compute the index
163  * @param key what key should the index be computed for
164  * @return offset into the "map" array of "m"
165  */
166 static unsigned int
167 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
168         const uint32_t key)
169 {
170   GNUNET_assert (m != NULL);
171   return ((unsigned int) key) % m->map_length;
172 }
173
174
175 /**
176  * Get the number of key-value pairs in the map.
177  *
178  * @param map the map
179  * @return the number of key value pairs
180  */
181 unsigned int
182 GNUNET_CONTAINER_multihashmap32_size (const struct
183                                       GNUNET_CONTAINER_MultiHashMap32 *map)
184 {
185   return map->size;
186 }
187
188
189 /**
190  * Given a key find a value in the map matching the key.
191  *
192  * @param map the map
193  * @param key what to look for
194  * @return NULL if no value was found; note that
195  *   this is indistinguishable from values that just
196  *   happen to be NULL; use "contains" to test for
197  *   key-value pairs with value NULL
198  */
199 void *
200 GNUNET_CONTAINER_multihashmap32_get (const struct
201                                      GNUNET_CONTAINER_MultiHashMap32 *map,
202                                      uint32_t key)
203 {
204   struct MapEntry *e;
205
206   e = map->map[idx_of (map, key)];
207   while (e != NULL)
208   {
209     if (key == e->key)
210       return e->value;
211     e = e->next;
212   }
213   return NULL;
214 }
215
216
217 /**
218  * Iterate over all entries in the map.
219  *
220  * @param map the map
221  * @param it function to call on each entry
222  * @param it_cls extra argument to @a it
223  * @return the number of key value pairs processed,
224  *         #GNUNET_SYSERR if it aborted iteration
225  */
226 int
227 GNUNET_CONTAINER_multihashmap32_iterate (const struct
228                                          GNUNET_CONTAINER_MultiHashMap32 *map,
229                                          GNUNET_CONTAINER_HashMapIterator32 it,
230                                          void *it_cls)
231 {
232   int count;
233   unsigned int i;
234   struct MapEntry *e;
235   struct MapEntry *n;
236
237   count = 0;
238   GNUNET_assert (NULL != map);
239   for (i = 0; i < map->map_length; i++)
240   {
241     n = map->map[i];
242     while (NULL != (e = n))
243     {
244       n = e->next;
245       if (NULL != it)
246       {
247         if (GNUNET_OK != it (it_cls, e->key, e->value))
248           return GNUNET_SYSERR;
249       }
250       count++;
251     }
252   }
253   return count;
254 }
255
256
257 /**
258  * Remove the given key-value pair from the map.  Note that if the
259  * key-value pair is in the map multiple times, only one of the pairs
260  * will be removed.
261  *
262  * @param map the map
263  * @param key key of the key-value pair
264  * @param value value of the key-value pair
265  * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
266  *  is not in the map
267  */
268 int
269 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
270                                         *map,
271                                         uint32_t key, const void *value)
272 {
273   struct MapEntry *e;
274   struct MapEntry *p;
275   unsigned int i;
276
277   map->modification_counter++;
278
279   i = idx_of (map, key);
280   p = NULL;
281   e = map->map[i];
282   while (e != NULL)
283   {
284     if ( (key == e->key) && (value == e->value) )
285     {
286       if (p == NULL)
287         map->map[i] = e->next;
288       else
289         p->next = e->next;
290       GNUNET_free (e);
291       map->size--;
292       return GNUNET_YES;
293     }
294     p = e;
295     e = e->next;
296   }
297   return GNUNET_NO;
298 }
299
300
301 /**
302  * Remove all entries for the given key from the map.
303  * Note that the values would not be "freed".
304  *
305  * @param map the map
306  * @param key identifies values to be removed
307  * @return number of values removed
308  */
309 int
310 GNUNET_CONTAINER_multihashmap32_remove_all (struct
311                                             GNUNET_CONTAINER_MultiHashMap32
312                                             *map,
313                                             uint32_t key)
314 {
315   struct MapEntry *e;
316   struct MapEntry *p;
317   unsigned int i;
318   int ret;
319
320   map->modification_counter++;
321
322   ret = 0;
323   i = idx_of (map, key);
324   p = NULL;
325   e = map->map[i];
326   while (e != NULL)
327   {
328     if (key == e->key)
329     {
330       if (p == NULL)
331         map->map[i] = e->next;
332       else
333         p->next = e->next;
334       GNUNET_free (e);
335       map->size--;
336       if (p == NULL)
337         e = map->map[i];
338       else
339         e = p->next;
340       ret++;
341     }
342     else
343     {
344       p = e;
345       e = e->next;
346     }
347   }
348   return ret;
349 }
350
351
352 /**
353  * Check if the map contains any value under the given
354  * key (including values that are NULL).
355  *
356  * @param map the map
357  * @param key the key to test if a value exists for it
358  * @return GNUNET_YES if such a value exists,
359  *         GNUNET_NO if not
360  */
361 int
362 GNUNET_CONTAINER_multihashmap32_contains (const struct
363                                           GNUNET_CONTAINER_MultiHashMap32 *map,
364                                           uint32_t key)
365 {
366   struct MapEntry *e;
367
368   e = map->map[idx_of (map, key)];
369   while (e != NULL)
370   {
371     if (key == e->key)
372       return GNUNET_YES;
373     e = e->next;
374   }
375   return GNUNET_NO;
376 }
377
378
379 /**
380  * Check if the map contains the given value under the given
381  * key.
382  *
383  * @param map the map
384  * @param key the key to test if a value exists for it
385  * @param value value to test for
386  * @return GNUNET_YES if such a value exists,
387  *         GNUNET_NO if not
388  */
389 int
390 GNUNET_CONTAINER_multihashmap32_contains_value (const struct
391                                                 GNUNET_CONTAINER_MultiHashMap32
392                                                 *map,
393                                                 uint32_t key,
394                                                 const void *value)
395 {
396   struct MapEntry *e;
397
398   e = map->map[idx_of (map, key)];
399   while (e != NULL)
400   {
401     if ( (key == e->key) && (e->value == value) )
402       return GNUNET_YES;
403     e = e->next;
404   }
405   return GNUNET_NO;
406 }
407
408
409 /**
410  * Grow the given map to a more appropriate size.
411  *
412  * @param map the hash map to grow
413  */
414 static void
415 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
416 {
417   struct MapEntry **old_map;
418   struct MapEntry **new_map;
419   struct MapEntry *e;
420   unsigned int old_len;
421   unsigned int new_len;
422   unsigned int idx;
423   unsigned int i;
424
425   map->modification_counter++;
426
427   old_map = map->map;
428   old_len = map->map_length;
429   new_len = old_len * 2;
430   new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
431   map->map_length = new_len;
432   map->map = new_map;
433   for (i = 0; i < old_len; i++)
434   {
435     while (NULL != (e = old_map[i]))
436     {
437       old_map[i] = e->next;
438       idx = idx_of (map, e->key);
439       e->next = new_map[idx];
440       new_map[idx] = e;
441     }
442   }
443   GNUNET_free (old_map);
444 }
445
446
447 /**
448  * Store a key-value pair in the map.
449  *
450  * @param map the map
451  * @param key key to use
452  * @param value value to use
453  * @param opt options for put
454  * @return GNUNET_OK on success,
455  *         GNUNET_NO if a value was replaced (with REPLACE)
456  *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
457  *                       value already exists
458  */
459 int
460 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
461                                      *map, uint32_t key, void *value,
462                                      enum GNUNET_CONTAINER_MultiHashMapOption
463                                      opt)
464 {
465   struct MapEntry *e;
466   unsigned int i;
467
468   i = idx_of (map, key);
469   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
470       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
471   {
472     e = map->map[i];
473     while (e != NULL)
474     {
475       if (key == e->key)
476       {
477         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
478           return GNUNET_SYSERR;
479         e->value = value;
480         return GNUNET_NO;
481       }
482       e = e->next;
483     }
484   }
485   if (map->size / 3 >= map->map_length / 4)
486   {
487     grow (map);
488     i = idx_of (map, key);
489   }
490   e = GNUNET_new (struct MapEntry);
491   e->key = key;
492   e->value = value;
493   e->next = map->map[i];
494   map->map[i] = e;
495   map->size++;
496   return GNUNET_OK;
497 }
498
499
500 /**
501  * Iterate over all entries in the map that match a particular key.
502  *
503  * @param map the map
504  * @param key key that the entries must correspond to
505  * @param it function to call on each entry
506  * @param it_cls extra argument to it
507  * @return the number of key value pairs processed,
508  *         GNUNET_SYSERR if it aborted iteration
509  */
510 int
511 GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
512                                               GNUNET_CONTAINER_MultiHashMap32
513                                               *map, uint32_t key,
514                                               GNUNET_CONTAINER_HashMapIterator32
515                                               it, void *it_cls)
516 {
517   int count;
518   struct MapEntry *e;
519   struct MapEntry *n;
520
521   count = 0;
522   n = map->map[idx_of (map, key)];
523   while (NULL != (e = n))
524   {
525     n = e->next;
526     if (key != e->key)
527       continue;
528     if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
529       return GNUNET_SYSERR;
530     count++;
531   }
532   return count;
533 }
534
535
536 /**
537  * Create an iterator for a multihashmap.
538  * The iterator can be used to retrieve all the elements in the multihashmap
539  * one by one, without having to handle all elements at once (in contrast to
540  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
541  * used anymore if elements have been removed from 'map' after the creation of
542  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
543  * result in skipped or repeated elements.
544  *
545  * @param map the map to create an iterator for
546  * @return an iterator over the given multihashmap 'map'
547  */
548 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
549 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
550 {
551   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
552
553   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
554   iter->map = map;
555   iter->modification_counter = map->modification_counter;
556   iter->me = map->map[0];
557   return iter;
558 }
559
560
561 /**
562  * Retrieve the next element from the hash map at the iterator's position.
563  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
564  * are not modified.
565  * This operation is only allowed if no elements have been removed from the
566  * multihashmap since the creation of 'iter', and the map has not been destroyed.
567  * Adding elements may result in repeating or skipping elements.
568  *
569  * @param iter the iterator to get the next element from
570  * @param key pointer to store the key in, can be NULL
571  * @param value pointer to store the value in, can be NULL
572  * @return #GNUNET_YES we returned an element,
573  *         #GNUNET_NO if we are out of elements
574  */
575 int
576 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
577                                                uint32_t *key,
578                                                const void **value)
579 {
580   /* make sure the map has not been modified */
581   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
582
583   /* look for the next entry, skipping empty buckets */
584   while (1)
585   {
586     if (iter->idx >= iter->map->map_length)
587       return GNUNET_NO;
588     if (NULL != iter->me)
589     {
590       if (NULL != key)
591         *key = iter->me->key;
592       if (NULL != value)
593         *value = iter->me->value;
594       iter->me = iter->me->next;
595       return GNUNET_YES;
596     }
597     iter->idx += 1;
598     if (iter->idx < iter->map->map_length)
599       iter->me = iter->map->map[iter->idx];
600   }
601 }
602
603
604 /**
605  * Destroy a multihashmap iterator.
606  *
607  * @param iter the iterator to destroy
608  */
609 void
610 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
611 {
612   GNUNET_free (iter);
613 }
614
615
616 /* end of container_multihashmap.c */