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_malloc_large (len *
150                                   sizeof (struct MapEntry *));
151   if (NULL == ret->map)
152   {
153     GNUNET_free (ret);
154     return NULL;
155   }
156   ret->map_length = len;
157   return ret;
158 }
159
160
161 /**
162  * Destroy a hash map.  Will not free any values
163  * stored in the hash map!
164  *
165  * @param map the map
166  */
167 void
168 GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
169 {
170   struct MapEntry *e;
171
172   for (unsigned int i = 0; i < map->map_length; i++)
173   {
174     while (NULL != (e = map->map[i]))
175     {
176       map->map[i] = e->next;
177       GNUNET_free (e);
178     }
179   }
180   GNUNET_free (map->map);
181   GNUNET_free (map);
182 }
183
184
185 /**
186  * Compute the index of the bucket for the given key.
187  *
188  * @param m hash map for which to compute the index
189  * @param key what key should the index be computed for
190  * @return offset into the "map" array of "m"
191  */
192 static unsigned int
193 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
194         const uint32_t key)
195 {
196   GNUNET_assert (NULL != m);
197   return ((unsigned int) key) % m->map_length;
198 }
199
200
201 /**
202  * Get the number of key-value pairs in the map.
203  *
204  * @param map the map
205  * @return the number of key value pairs
206  */
207 unsigned int
208 GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
209 {
210   return map->size;
211 }
212
213
214 /**
215  * Given a key find a value in the map matching the key.
216  *
217  * @param map the map
218  * @param key what to look for
219  * @return NULL if no value was found; note that
220  *   this is indistinguishable from values that just
221  *   happen to be NULL; use "contains" to test for
222  *   key-value pairs with value NULL
223  */
224 void *
225 GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
226                                      uint32_t key)
227 {
228   struct MapEntry *e;
229
230   e = map->map[idx_of (map, key)];
231   while (NULL != e)
232   {
233     if (key == e->key)
234       return e->value;
235     e = e->next;
236   }
237   return NULL;
238 }
239
240
241 /**
242  * Iterate over all entries in the map.
243  *
244  * @param map the map
245  * @param it function to call on each entry
246  * @param it_cls extra argument to @a it
247  * @return the number of key value pairs processed,
248  *         #GNUNET_SYSERR if it aborted iteration
249  */
250 int
251 GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
252                                          GNUNET_CONTAINER_HashMapIterator32 it,
253                                          void *it_cls)
254 {
255   int count;
256   struct MapEntry **ce;
257
258   count = 0;
259   GNUNET_assert (NULL != map);
260   ce = &map->next_cache[map->next_cache_off];
261   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
262   for (unsigned int i = 0; i < map->map_length; i++)
263   {
264     struct MapEntry *e;
265
266     *ce = map->map[i];
267     while (NULL != (e = *ce))
268     {
269       *ce = e->next;
270       if (NULL != it)
271       {
272         if (GNUNET_OK != it (it_cls,
273                              e->key,
274                              e->value))
275         {
276           GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
277           return GNUNET_SYSERR;
278         }
279       }
280       count++;
281     }
282   }
283   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
284   return count;
285 }
286
287
288 /**
289  * We are about to free() the @a bme, make sure it is not in
290  * the list of next values for any iterator in the @a map's next_cache.
291  *
292  * @param map the map to check
293  * @param bme the entry that is about to be free'd
294  */
295 static void
296 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
297                    const struct MapEntry *me)
298 {
299   for (unsigned int i=0;i<map->next_cache_off;i++)
300     if (map->next_cache[i] == me)
301       map->next_cache[i] = me->next;
302 }
303
304
305 /**
306  * Remove the given key-value pair from the map.  Note that if the
307  * key-value pair is in the map multiple times, only one of the pairs
308  * will be removed.
309  *
310  * @param map the map
311  * @param key key of the key-value pair
312  * @param value value of the key-value pair
313  * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
314  *  is not in the map
315  */
316 int
317 GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
318                                         uint32_t key,
319                                         const void *value)
320 {
321   struct MapEntry *e;
322   struct MapEntry *p;
323   unsigned int i;
324
325   map->modification_counter++;
326
327   i = idx_of (map, key);
328   p = NULL;
329   e = map->map[i];
330   while (e != NULL)
331   {
332     if ( (key == e->key) && (value == e->value) )
333     {
334       if (p == NULL)
335         map->map[i] = e->next;
336       else
337         p->next = e->next;
338       update_next_cache (map,
339                          e);
340       GNUNET_free (e);
341       map->size--;
342       return GNUNET_YES;
343     }
344     p = e;
345     e = e->next;
346   }
347   return GNUNET_NO;
348 }
349
350
351 /**
352  * Remove all entries for the given key from the map.
353  * Note that the values would not be "freed".
354  *
355  * @param map the map
356  * @param key identifies values to be removed
357  * @return number of values removed
358  */
359 int
360 GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
361                                             uint32_t key)
362 {
363   struct MapEntry *e;
364   struct MapEntry *p;
365   unsigned int i;
366   int ret;
367
368   map->modification_counter++;
369
370   ret = 0;
371   i = idx_of (map, key);
372   p = NULL;
373   e = map->map[i];
374   while (e != NULL)
375   {
376     if (key == e->key)
377     {
378       if (p == NULL)
379         map->map[i] = e->next;
380       else
381         p->next = e->next;
382       update_next_cache (map,
383                          e);
384       GNUNET_free (e);
385       map->size--;
386       if (p == NULL)
387         e = map->map[i];
388       else
389         e = p->next;
390       ret++;
391     }
392     else
393     {
394       p = e;
395       e = e->next;
396     }
397   }
398   return ret;
399 }
400
401
402 /**
403  * Check if the map contains any value under the given
404  * key (including values that are NULL).
405  *
406  * @param map the map
407  * @param key the key to test if a value exists for it
408  * @return #GNUNET_YES if such a value exists,
409  *         #GNUNET_NO if not
410  */
411 int
412 GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
413                                           uint32_t key)
414 {
415   struct MapEntry *e;
416
417   e = map->map[idx_of (map, key)];
418   while (e != NULL)
419   {
420     if (key == e->key)
421       return GNUNET_YES;
422     e = e->next;
423   }
424   return GNUNET_NO;
425 }
426
427
428 /**
429  * Check if the map contains the given value under the given
430  * key.
431  *
432  * @param map the map
433  * @param key the key to test if a value exists for it
434  * @param value value to test for
435  * @return #GNUNET_YES if such a value exists,
436  *         #GNUNET_NO if not
437  */
438 int
439 GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
440                                                 uint32_t key,
441                                                 const void *value)
442 {
443   struct MapEntry *e;
444
445   e = map->map[idx_of (map, key)];
446   while (e != NULL)
447   {
448     if ( (key == e->key) && (e->value == value) )
449       return GNUNET_YES;
450     e = e->next;
451   }
452   return GNUNET_NO;
453 }
454
455
456 /**
457  * Grow the given map to a more appropriate size.
458  *
459  * @param map the hash map to grow
460  */
461 static void
462 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
463 {
464   struct MapEntry **old_map;
465   struct MapEntry **new_map;
466   struct MapEntry *e;
467   unsigned int old_len;
468   unsigned int new_len;
469   unsigned int idx;
470
471   old_map = map->map;
472   old_len = map->map_length;
473   new_len = old_len * 2;
474   if (0 == new_len) /* 2^31 * 2 == 0 */
475     new_len = old_len; /* never use 0 */
476   if (new_len == old_len)
477     return; /* nothing changed */
478   new_map = GNUNET_malloc_large (new_len *
479                                  sizeof (struct MapEntry *));
480   if (NULL == new_map)
481     return; /* grow not possible */
482   map->modification_counter++;
483   map->map_length = new_len;
484   map->map = new_map;
485   for (unsigned int i = 0; i < old_len; i++)
486   {
487     while (NULL != (e = old_map[i]))
488     {
489       old_map[i] = e->next;
490       idx = idx_of (map, e->key);
491       e->next = new_map[idx];
492       new_map[idx] = e;
493     }
494   }
495   GNUNET_free (old_map);
496 }
497
498
499 /**
500  * Store a key-value pair in the map.
501  *
502  * @param map the map
503  * @param key key to use
504  * @param value value to use
505  * @param opt options for put
506  * @return #GNUNET_OK on success,
507  *         #GNUNET_NO if a value was replaced (with REPLACE)
508  *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
509  *                       value already exists
510  */
511 int
512 GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
513                                      *map, uint32_t key, void *value,
514                                      enum GNUNET_CONTAINER_MultiHashMapOption
515                                      opt)
516 {
517   struct MapEntry *e;
518   unsigned int i;
519
520   i = idx_of (map, key);
521   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
522       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
523   {
524     e = map->map[i];
525     while (e != NULL)
526     {
527       if (key == e->key)
528       {
529         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
530           return GNUNET_SYSERR;
531         e->value = value;
532         return GNUNET_NO;
533       }
534       e = e->next;
535     }
536   }
537   if (map->size / 3 >= map->map_length / 4)
538   {
539     grow (map);
540     i = idx_of (map, key);
541   }
542   e = GNUNET_new (struct MapEntry);
543   e->key = key;
544   e->value = value;
545   e->next = map->map[i];
546   map->map[i] = e;
547   map->size++;
548   return GNUNET_OK;
549 }
550
551
552 /**
553  * Iterate over all entries in the map that match a particular key.
554  *
555  * @param map the map
556  * @param key key that the entries must correspond to
557  * @param it function to call on each entry
558  * @param it_cls extra argument to @a it
559  * @return the number of key value pairs processed,
560  *         GNUNET_SYSERR if it aborted iteration
561  */
562 int
563 GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
564                                               uint32_t key,
565                                               GNUNET_CONTAINER_HashMapIterator32 it,
566                                               void *it_cls)
567 {
568   int count;
569   struct MapEntry *e;
570   struct MapEntry **ce;
571
572   count = 0;
573   ce = &map->next_cache[map->next_cache_off];
574   GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
575
576   *ce = map->map[idx_of (map, key)];
577   while (NULL != (e = *ce))
578   {
579     *ce = e->next;
580     if (key != e->key)
581       continue;
582     if ( (NULL != it) &&
583          (GNUNET_OK != it (it_cls,
584                            key,
585                            e->value)) )
586       {
587         GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
588         return GNUNET_SYSERR;
589       }
590     count++;
591   }
592   GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
593   return count;
594 }
595
596
597 /**
598  * Create an iterator for a multihashmap.
599  * The iterator can be used to retrieve all the elements in the multihashmap
600  * one by one, without having to handle all elements at once (in contrast to
601  * GNUNET_CONTAINER_multihashmap_iterate()).  Note that the iterator can not be
602  * used anymore if elements have been removed from 'map' after the creation of
603  * the iterator, or 'map' has been destroyed.  Adding elements to 'map' may
604  * result in skipped or repeated elements.
605  *
606  * @param map the map to create an iterator for
607  * @return an iterator over the given multihashmap @a map
608  */
609 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
610 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
611 {
612   struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
613
614   iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
615   iter->map = map;
616   iter->modification_counter = map->modification_counter;
617   iter->me = map->map[0];
618   return iter;
619 }
620
621
622 /**
623  * Retrieve the next element from the hash map at the iterator's position.
624  * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
625  * are not modified.
626  * This operation is only allowed if no elements have been removed from the
627  * multihashmap since the creation of 'iter', and the map has not been destroyed.
628  * Adding elements may result in repeating or skipping elements.
629  *
630  * @param iter the iterator to get the next element from
631  * @param key pointer to store the key in, can be NULL
632  * @param value pointer to store the value in, can be NULL
633  * @return #GNUNET_YES we returned an element,
634  *         #GNUNET_NO if we are out of elements
635  */
636 int
637 GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
638                                                uint32_t *key,
639                                                const void **value)
640 {
641   /* make sure the map has not been modified */
642   GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
643
644   /* look for the next entry, skipping empty buckets */
645   while (1)
646   {
647     if (iter->idx >= iter->map->map_length)
648       return GNUNET_NO;
649     if (NULL != iter->me)
650     {
651       if (NULL != key)
652         *key = iter->me->key;
653       if (NULL != value)
654         *value = iter->me->value;
655       iter->me = iter->me->next;
656       return GNUNET_YES;
657     }
658     iter->idx += 1;
659     if (iter->idx < iter->map->map_length)
660       iter->me = iter->map->map[iter->idx];
661   }
662 }
663
664
665 /**
666  * Destroy a multihashmap iterator.
667  *
668  * @param iter the iterator to destroy
669  */
670 void
671 GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
672 {
673   GNUNET_free (iter);
674 }
675
676
677 /* end of container_multihashmap.c */