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