lib/hamt.h

   1 /* (Persistent) hash array mapped tries.
   2    Copyright (C) 2021-2025 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Marc Nieper-Wißkirchen <marc@nieper-wisskirchen.de>, 2021. */
  18
  19 /* This module provides a persistent version of hash array mapped
  20    tries (hamts) that can be used in place of hash tables when pure
  21    (functional) operations are needed.
  22
  23    A hash function and an equivalence predicate has to be provided for
  24    the elements that can be inserted, replaced and removed in a hamt.
  25    A hamt cannot contain duplicates that compare equal.
  26
  27    Each non-destructive updating operation returns a new hamt, which
  28    shares structure with the original one.  Destructive updates only
  29    effect the hamt, on which the destructive operation is applied.
  30    For example, given a hamt HAMT1, any non-destructive update
  31    operation (e.g. hamt_insert) will result in a new hamt HAMT2.
  32    Whatever further operations (destructive or not, including freeing
  33    a hamt) are applied to HAMT1 won't change HAMT2 and vice versa.  To
  34    free all the memory, hash_free has therefore to be applied to both
  35    HAMT1 and HAMT2.
  36
  37    If persistence is not needed, transient hash tables are probably
  38    faster.
  39
  40    See also: Phil Bagwell (2000). Ideal Hash Trees (Report). Infoscience
  41    Department, École Polytechnique Fédérale de Lausanne.
  42
  43    https://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf  */
  44
  45 #ifndef _GL_HAMT_H
  46 #define _GL_HAMT_H
  47
  48 /* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE, _GL_ATTRIBUTE_DEALLOC,
  49    _GL_ATTRIBUTE_NODISCARD.  */
  50 #if !_GL_CONFIG_H_INCLUDED
  51  #error "Please include config.h first."
  52 #endif
  53
  54 _GL_INLINE_HEADER_BEGIN
  55 #ifndef _GL_HAMT_INLINE
  56 # define _GL_HAMT_INLINE _GL_INLINE
  57 #endif
  58
  59 /* The GL_HAMT_THREAD_SAFE flag is set if the implementation of hamts
  60    is thread-safe as long as two threads do not simultaneously access
  61    the same hamt.  This is non-trivial as different hamts may share
  62    some structure.
  63    We can define it only when the compiler supports _Atomic.  For GCC,
  64    it is supported starting with GCC 4.9.  For clang, with clang 4.  */
  65
  66 #if (__GNUC__ + (__GNUC_MINOR__ >= 9) > 4 && !defined __clang \
  67      || __clang_major__ >= 4) \
  68     && __STDC_VERSION__ >= 201112L && !defined __STD_NO_ATOMICS__ \
  69     && !defined __cplusplus
  70 # define GL_HAMT_THREAD_SAFE 1
  71 #else
  72 # define GL_HAMT_THREAD_SAFE 0
  73 #endif
  74
  75 #include <stddef.h>
  76 #include <stdint.h>
  77
  78 #ifdef __cplusplus
  79 extern "C" {
  80 #endif
  81
  82
  83 /* Hash values are of type size_t.  For each level of the trie, we use
  84    5 bits (corresponding to lg2 of the width of a 32-bit word.  */
  85 #define _GL_HAMT_MAX_DEPTH ((SIZE_WIDTH + 4) / 5)
  86
  87 /************/
  88 /* Elements */
  89 /************/
  90
  91 /* A hamt stores pointers to elements.  Each element has to be a
  92    struct whose initial member is of the type Hamt_entry.  You need to
  93    define this struct yourself.  It will typically contain an
  94    Hamt_entry, a key, and, optionally, a value.
  95
  96    An element is conceptually owned by a hamt as soon as it is
  97    inserted.  It will be automatically freed as soon as the last hamt
  98    containing it is freed.  */
  99 typedef struct
 100 {
 101 #if GL_HAMT_THREAD_SAFE
 102   _Atomic
 103 #endif
 104   size_t ref_count;
 105 } Hamt_entry;
 106
 107 /* Initialize *ELT, which has to point to a structure as described
 108    above and return ELT type-cast.
 109
 110    Before an element is inserted into any hamt, whether once or
 111    multiple times, it has to be initialized exactly once.  */
 112 _GL_HAMT_INLINE Hamt_entry *
 113 hamt_element (void *elt)
 114 {
 115   Hamt_entry *entry = elt;
 116   entry->ref_count = 0;         /* This assumes that element_entry ==
 117                                    0.  */
 118   return entry;
 119 }
 120
 121 /*************************/
 122 /* Opaque Hamt Structure */
 123 /*************************/
 124
 125 /* In user-code, hamts are accessed through pointers to the opaque
 126    Hamt type.  Two hamts are said to be the same if and only if their
 127    pointers are equal. */
 128 typedef struct hamt Hamt;
 129
 130 /*************/
 131 /* Interface */
 132 /*************/
 133
 134 /* A hash function has to be pure, and two elements that compare equal
 135    have to have the same hash value.  For a hash function to be a good
 136    one, it is important that it uses all SIZE_WIDTH bits in
 137    size_t.  */
 138 typedef size_t (Hamt_hasher) (const void *elt);
 139
 140 /* A comparison function has to be pure, and two elements that have
 141    equal pointers have to compare equal.  */
 142 typedef bool (Hamt_comparator) (const void *elt1, const void *elt2);
 143
 144 /* A user-defined function that is called when the last hamt
 145    containing a particular element is freed.  */
 146 typedef void (Hamt_freer) (Hamt_entry *elt);
 147
 148 /****************************/
 149 /* Creation and Destruction */
 150 /****************************/
 151
 152 /* Free the resources solely allocated by HAMT and all elements solely
 153    contained in it.  */
 154 extern void hamt_free (Hamt *hamt);
 155
 156 /* Create and return a new and empty hash array mapped trie.  */
 157 _GL_ATTRIBUTE_NODISCARD
 158 extern Hamt *hamt_create (Hamt_hasher *hasher, Hamt_comparator *comparator,
 159                           Hamt_freer *freer)
 160   _GL_ATTRIBUTE_DEALLOC (hamt_free, 1);
 161
 162 /* Return a copy of HAMT, which is not the same in the sense above.
 163    This procedure can be used, for example, so that two threads can
 164    access the same data independently.  */
 165 _GL_ATTRIBUTE_NODISCARD
 166 extern Hamt *hamt_copy (Hamt *hamt)
 167   _GL_ATTRIBUTE_DEALLOC (hamt_free, 1);
 168
 169 /**********/
 170 /* Lookup */
 171 /**********/
 172
 173 /* If ELT matches an entry in HAMT, return this entry.  Otherwise,
 174    return NULL.  */
 175 extern Hamt_entry *hamt_lookup (const Hamt *hamt, const void *elt);
 176
 177 /**************************/
 178 /* Insertion and Deletion */
 179 /**************************/
 180
 181 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
 182    existing element and return the original hamt.  Otherwise, insert
 183    *ELT_PTR into a copy of the hamt and return the copy.  */
 184 _GL_ATTRIBUTE_NODISCARD
 185 extern Hamt *hamt_insert (Hamt *hamt, Hamt_entry **elt_ptr);
 186
 187 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
 188 existing element, remove the element from a copy of the hamt and
 189 return the copy.  Otherwise, return the original hamt.  */
 190 _GL_ATTRIBUTE_NODISCARD
 191 extern Hamt *hamt_remove (Hamt *hamt, Hamt_entry **elt_ptr);
 192
 193 /* Insert *ELT_PTR into a copy of HAMT and return the copy.  If an
 194    existing element was replaced, set *ELT_PTR to this element, and to
 195    NULL otherwise.  */
 196 _GL_ATTRIBUTE_NODISCARD
 197 extern Hamt *hamt_replace (Hamt *hamt, Hamt_entry **elt_ptr);
 198
 199 /*************/
 200 /* Iteration */
 201 /*************/
 202
 203 /* A processor function is called during walking of a hamt, which
 204    returns true to continue the walking.  */
 205 typedef bool (Hamt_processor) (Hamt_entry *elt, void *data);
 206
 207 /* Call PROC for every entry of the hamt until it returns false.  The
 208    first argument to the processor is the entry, the second argument
 209    is the value of DATA as received.  Return the number of calls that
 210    returned true.  During processing, the hamt mustn't be
 211    modified.  */
 212 extern size_t hamt_do_while (const Hamt *hamt, Hamt_processor *proc,
 213                              void *data);
 214
 215 /* An alternative interface to iterating through the entry of a hamt
 216    that does not make use of a higher-order function like
 217    hamt_do_while uses the Hamt_iterator type, which can be allocated
 218    through automatic variables on the stack.  As a hamt iterator
 219    operates on a copy of a hamt, the original hamt can modified
 220    (including freeing it) without affecting the iterator.  */
 221 struct hamt_iterator
 222 {
 223   Hamt* hamt;
 224   int depth;
 225   size_t path;
 226   size_t position;
 227   Hamt_entry *entry[_GL_HAMT_MAX_DEPTH + 1];
 228 };
 229 typedef struct hamt_iterator Hamt_iterator;
 230
 231 /* Create of copy of HAMT and return an initialized ITER on the
 232    copy.  */
 233 extern Hamt_iterator hamt_iterator (Hamt *hamt);
 234
 235 /* Free the resources allocated for ITER, including the hamt copy
 236    associated with it.  */
 237 extern void hamt_iterator_free (Hamt_iterator *iter);
 238
 239 /* Return an independent copy of ITER that is initially in the same
 240    state.  Any operation on the original iterator (including freeing
 241    it) doesn't affect the iterator copy and vice versa.  */
 242 extern Hamt_iterator hamt_iterator_copy (Hamt_iterator *iter);
 243
 244 /* Return true if ITER is not at the end, place the current element in
 245    *ELT_PTR and move the iterator forward.  Otherwise, return
 246    false.  */
 247 extern bool hamt_iterator_next (Hamt_iterator *iter,
 248                                 Hamt_entry **elt_ptr);
 249
 250 /***********************/
 251 /* Destructive Updates */
 252 /***********************/
 253
 254 /* If *ELT_PTR matches an element already in HAMT, set *ELT_PTR to the
 255    element from the table and return false.  Otherwise, insert *ELT_PTR
 256    destructively into the hamt and return true.  */
 257 extern bool hamt_insert_x (Hamt *hamt, Hamt_entry **elt_ptr);
 258
 259 /* Insert ELT destructively into HAMT.  If an existing element was
 260    replaced, return true.  Otherwise, return false.  */
 261 extern bool hamt_replace_x (Hamt *hamt, Hamt_entry *elt);
 262
 263 /* If ELT matches an element already in HAMT, remove the element
 264    destructively from the hamt and return true.  Otherwise, return
 265    false.  */
 266 extern bool hamt_remove_x (Hamt *hamt, Hamt_entry *elt);
 267
 268
 269 #ifdef __cplusplus
 270 }
 271 #endif
 272
 273 _GL_INLINE_HEADER_END
 274
 275 #endif /* _GL_HAMT_H */