src/shared/hashmap.h

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 #pragma once
   4
   5 /***
   6   This file is part of systemd.
   7
   8   Copyright 2010 Lennart Poettering
   9
  10   systemd is free software; you can redistribute it and/or modify it
  11   under the terms of the GNU Lesser General Public License as published by
  12   the Free Software Foundation; either version 2.1 of the License, or
  13   (at your option) any later version.
  14
  15   systemd is distributed in the hope that it will be useful, but
  16   WITHOUT ANY WARRANTY; without even the implied warranty of
  17   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18   Lesser General Public License for more details.
  19
  20   You should have received a copy of the GNU Lesser General Public License
  21   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  22 ***/
  23
  24 #include <stdbool.h>
  25
  26 #include "macro.h"
  27 #include "util.h"
  28
  29 /* Pretty straightforward hash table implementation. As a minor
  30  * optimization a NULL hashmap object will be treated as empty hashmap
  31  * for all read operations. That way it is not necessary to
  32  * instantiate an object for each Hashmap use. */
  33
  34 #define HASH_KEY_SIZE 16
  35
  36 typedef struct Hashmap Hashmap;
  37 typedef struct _IteratorStruct _IteratorStruct;
  38 typedef _IteratorStruct* Iterator;
  39
  40 #define ITERATOR_FIRST ((Iterator) 0)
  41 #define ITERATOR_LAST ((Iterator) -1)
  42
  43 typedef unsigned long (*hash_func_t)(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]);
  44 typedef int (*compare_func_t)(const void *a, const void *b);
  45
  46 unsigned long string_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  47 int string_compare_func(const void *a, const void *b) _pure_;
  48
  49 /* This will compare the passed pointers directly, and will not
  50  * dereference them. This is hence not useful for strings or
  51  * suchlike. */
  52 unsigned long trivial_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  53 int trivial_compare_func(const void *a, const void *b) _const_;
  54
  55 /* 32bit values we can always just embedd in the pointer itself, but
  56  * in order to support 32bit archs we need store 64bit values
  57  * indirectly, since they don't fit in a pointer. */
  58 unsigned long uint64_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  59 int uint64_compare_func(const void *a, const void *b) _pure_;
  60
  61 /* On some archs dev_t is 32bit, and on others 64bit. And sometimes
  62  * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
  63 #if SIZEOF_DEV_T != 8
  64 unsigned long devt_hash_func(const void *p, const uint8_t hash_key[HASH_KEY_SIZE]) _pure_;
  65 int devt_compare_func(const void *a, const void *b) _pure_;
  66 #else
  67 /* No need to define a second version of this... */
  68 #define devt_hash_func uint64_hash_func
  69 #define devt_compare_func uint64_compare_func
  70 #endif
  71
  72 Hashmap *hashmap_new(hash_func_t hash_func, compare_func_t compare_func);
  73 void hashmap_free(Hashmap *h);
  74 void hashmap_free_free(Hashmap *h);
  75 void hashmap_free_free_free(Hashmap *h);
  76 Hashmap *hashmap_copy(Hashmap *h);
  77 int hashmap_ensure_allocated(Hashmap **h, hash_func_t hash_func, compare_func_t compare_func);
  78
  79 int hashmap_put(Hashmap *h, const void *key, void *value);
  80 int hashmap_update(Hashmap *h, const void *key, void *value);
  81 int hashmap_replace(Hashmap *h, const void *key, void *value);
  82 void *hashmap_get(Hashmap *h, const void *key);
  83 void *hashmap_get2(Hashmap *h, const void *key, void **rkey);
  84 bool hashmap_contains(Hashmap *h, const void *key);
  85 void *hashmap_remove(Hashmap *h, const void *key);
  86 void *hashmap_remove2(Hashmap *h, const void *key, void **rkey);
  87 void *hashmap_remove_value(Hashmap *h, const void *key, void *value);
  88 int hashmap_remove_and_put(Hashmap *h, const void *old_key, const void *new_key, void *value);
  89 int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_key, void *value);
  90
  91 int hashmap_merge(Hashmap *h, Hashmap *other);
  92 void hashmap_move(Hashmap *h, Hashmap *other);
  93 int hashmap_move_one(Hashmap *h, Hashmap *other, const void *key);
  94
  95 unsigned hashmap_size(Hashmap *h) _pure_;
  96 bool hashmap_isempty(Hashmap *h) _pure_;
  97 unsigned hashmap_buckets(Hashmap *h) _pure_;
  98
  99 void *hashmap_iterate(Hashmap *h, Iterator *i, const void **key);
 100 void *hashmap_iterate_backwards(Hashmap *h, Iterator *i, const void **key);
 101 void *hashmap_iterate_skip(Hashmap *h, const void *key, Iterator *i);
 102
 103 void hashmap_clear(Hashmap *h);
 104 void hashmap_clear_free(Hashmap *h);
 105 void hashmap_clear_free_free(Hashmap *h);
 106
 107 void *hashmap_steal_first(Hashmap *h);
 108 void *hashmap_steal_first_key(Hashmap *h);
 109 void *hashmap_first(Hashmap *h) _pure_;
 110 void *hashmap_first_key(Hashmap *h) _pure_;
 111 void *hashmap_last(Hashmap *h) _pure_;
 112
 113 void *hashmap_next(Hashmap *h, const void *key);
 114
 115 char **hashmap_get_strv(Hashmap *h);
 116
 117 #define HASHMAP_FOREACH(e, h, i) \
 118         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), NULL); (e); (e) = hashmap_iterate((h), &(i), NULL))
 119
 120 #define HASHMAP_FOREACH_KEY(e, k, h, i) \
 121         for ((i) = ITERATOR_FIRST, (e) = hashmap_iterate((h), &(i), (const void**) &(k)); (e); (e) = hashmap_iterate((h), &(i), (const void**) &(k)))
 122
 123 #define HASHMAP_FOREACH_BACKWARDS(e, h, i) \
 124         for ((i) = ITERATOR_LAST, (e) = hashmap_iterate_backwards((h), &(i), NULL); (e); (e) = hashmap_iterate_backwards((h), &(i), NULL))
 125
 126 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free);
 127 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free);
 128 DEFINE_TRIVIAL_CLEANUP_FUNC(Hashmap*, hashmap_free_free_free);
 129 #define _cleanup_hashmap_free_ _cleanup_(hashmap_freep)
 130 #define _cleanup_hashmap_free_free_ _cleanup_(hashmap_free_freep)
 131 #define _cleanup_hashmap_free_free_free_ _cleanup_(hashmap_free_free_freep)