lib/gl_map.h

   1 /* Abstract map data type.
   2    Copyright (C) 2006-2007, 2009-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2018.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _GL_MAP_H
  19 #define _GL_MAP_H
  20
  21 /* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE,
  22    _GL_ATTRIBUTE_NODISCARD.  */
  23 #if !_GL_CONFIG_H_INCLUDED
  24  #error "Please include config.h first."
  25 #endif
  26
  27 #include <stddef.h>
  28
  29 _GL_INLINE_HEADER_BEGIN
  30 #ifndef GL_MAP_INLINE
  31 # define GL_MAP_INLINE _GL_INLINE
  32 #endif
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38
  39 /* gl_map is an abstract map data type.  It can contain any number of
  40    (key, value) pairs, where
  41      - keys and values are objects ('void *' or 'const void *' pointers),
  42      - There are no (key, value1) and (key, value2) pairs with the same key
  43        (in the sense of a given comparator function).
  44
  45    There are several implementations of this map datatype, optimized for
  46    different operations or for memory.  You can start using the simplest map
  47    implementation, GL_ARRAY_MAP, and switch to a different implementation
  48    later, when you realize which operations are performed the most frequently.
  49    The API of the different implementations is exactly the same; when switching
  50    to a different implementation, you only have to change the gl_map_create
  51    call.
  52
  53    The implementations are:
  54      GL_ARRAY_MAP         a growable array
  55      GL_LINKEDHASH_MAP    a hash table with a linked list
  56      GL_HASH_MAP          a hash table
  57
  58    The memory consumption is asymptotically the same: O(1) for every pair
  59    in the map.  When looking more closely at the average memory consumed
  60    for an object, GL_ARRAY_MAP is the most compact representation, then comes
  61    GL_HASH_MAP, and GL_LINKEDHASH_MAP needs the most memory.
  62
  63    The guaranteed average performance of the operations is, for a map of
  64    n pairs:
  65
  66    Operation                  ARRAY   LINKEDHASH
  67                                       HASH
  68
  69    gl_map_size                 O(1)   O(1)
  70    gl_map_get                  O(n)   O(1)
  71    gl_map_put                  O(n)   O(1)
  72    gl_map_remove               O(n)   O(1)
  73    gl_map_search               O(n)   O(1)
  74    gl_map_iterator             O(1)   O(1)
  75    gl_map_iterator_next        O(1)   O(1)
  76  */
  77
  78 /* --------------------------- gl_map_t Data Type --------------------------- */
  79
  80 /* Type of function used to compare two keys.
  81    NULL denotes pointer comparison.  */
  82 typedef bool (*gl_mapkey_equals_fn) (const void *key1, const void *key2);
  83
  84 /* Type of function used to compute a hash code.
  85    NULL denotes a function that depends only on the pointer itself.  */
  86 typedef size_t (*gl_mapkey_hashcode_fn) (const void *key);
  87
  88 #ifndef _GL_MAP_DISPOSE_FNS_DEFINED
  89
  90 /* Type of function used to dispose a key once a (key, value) pair is removed
  91    from a map.  NULL denotes a no-op.  */
  92 typedef void (*gl_mapkey_dispose_fn) (const void *key);
  93
  94 /* Type of function used to dispose a value once a (key, value) pair is removed
  95    from a map.  NULL denotes a no-op.  */
  96 typedef void (*gl_mapvalue_dispose_fn) (const void *value);
  97
  98 # define _GL_MAP_DISPOSE_FNS_DEFINED 1
  99 #endif
 100
 101 struct gl_map_impl;
 102 /* Type representing an entire map.  */
 103 typedef struct gl_map_impl * gl_map_t;
 104
 105 struct gl_map_implementation;
 106 /* Type representing a map datatype implementation.  */
 107 typedef const struct gl_map_implementation * gl_map_implementation_t;
 108
 109 #if 0 /* Unless otherwise specified, these are defined inline below.  */
 110
 111 /* Creates an empty map.
 112    IMPLEMENTATION is one of GL_ARRAY_MAP, GL_LINKEDHASH_MAP, GL_HASH_MAP.
 113    EQUALS_FN is a key comparison function or NULL.
 114    HASHCODE_FN is a key hash code function or NULL.
 115    KDISPOSE_FN is a key disposal function or NULL.
 116    VDISPOSE_FN is a value disposal function or NULL.  */
 117 /* declared in gl_xmap.h */
 118 extern gl_map_t gl_map_create_empty (gl_map_implementation_t implementation,
 119                                      gl_mapkey_equals_fn equals_fn,
 120                                      gl_mapkey_hashcode_fn hashcode_fn,
 121                                      gl_mapkey_dispose_fn kdispose_fn,
 122                                      gl_mapvalue_dispose_fn vdispose_fn)
 123   /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
 124   _GL_ATTRIBUTE_RETURNS_NONNULL;
 125 /* Likewise.  Returns NULL upon out-of-memory.  */
 126 extern gl_map_t gl_map_nx_create_empty (gl_map_implementation_t implementation,
 127                                         gl_mapkey_equals_fn equals_fn,
 128                                         gl_mapkey_hashcode_fn hashcode_fn,
 129                                         gl_mapkey_dispose_fn kdispose_fn,
 130                                         gl_mapvalue_dispose_fn vdispose_fn)
 131   /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/;
 132
 133 /* Returns the current number of pairs in a map.  */
 134 extern size_t gl_map_size (gl_map_t map);
 135
 136 /* Searches whether a pair with the given key is already in the map.
 137    Returns the value if found, or NULL if not present in the map.  */
 138 extern const void * gl_map_get (gl_map_t map, const void *key);
 139
 140 /* Searches whether a pair with the given key is already in the map.
 141    Returns true and sets *VALUEP to the value if found.
 142    Returns false if not present in the map.  */
 143 extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep);
 144
 145 /* Adds a pair to a map.
 146    Returns true if a pair with the given key was not already in the map and so
 147    this pair was added.
 148    Returns false if a pair with the given key was already in the map and only
 149    its value was replaced.  */
 150 /* declared in gl_xmap.h */
 151 extern bool gl_map_put (gl_map_t map, const void *key, const void *value);
 152 /* Likewise.  Returns -1 upon out-of-memory.  */
 153 _GL_ATTRIBUTE_NODISCARD
 154 extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value);
 155
 156 /* Adds a pair to a map and retrieves the previous value.
 157    Returns true if a pair with the given key was not already in the map and so
 158    this pair was added.
 159    Returns false and sets *OLDVALUEP to the previous value, if a pair with the
 160    given key was already in the map and only its value was replaced.  */
 161 /* declared in gl_xmap.h */
 162 extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
 163                            const void **oldvaluep);
 164 /* Likewise.  Returns -1 upon out-of-memory.  */
 165 _GL_ATTRIBUTE_NODISCARD
 166 extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
 167                              const void **oldvaluep);
 168
 169 /* Removes a pair from a map.
 170    Returns true if the key was found and its pair removed.
 171    Returns false otherwise.  */
 172 extern bool gl_map_remove (gl_map_t map, const void *key);
 173
 174 /* Removes a pair from a map and retrieves the previous value.
 175    Returns true and sets *OLDVALUEP to the previous value, if the key was found
 176    and its pair removed.
 177    Returns false otherwise.  */
 178 extern bool gl_map_getremove (gl_map_t map, const void *key,
 179                               const void **oldvaluep);
 180
 181 /* Frees an entire map.
 182    (But this call does not free the keys and values of the pairs in the map.
 183    It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
 184    of the pairs in the map.)  */
 185 extern void gl_map_free (gl_map_t map);
 186
 187 #endif /* End of inline and gl_xmap.h-defined functions.  */
 188
 189 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
 190
 191 /* Functions for iterating through a map.
 192    Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an
 193    unpredictable order.  If you need a predictable order, use GL_LINKEDHASH_MAP
 194    instead of GL_HASH_MAP.  */
 195
 196 /* Type of an iterator that traverses a map.
 197    This is a fixed-size struct, so that creation of an iterator doesn't need
 198    memory allocation on the heap.  */
 199 typedef struct
 200 {
 201   /* For fast dispatch of gl_map_iterator_next.  */
 202   const struct gl_map_implementation *vtable;
 203   /* For detecting whether the last returned pair was removed.  */
 204   gl_map_t map;
 205   size_t count;
 206   /* Other, implementation-private fields.  */
 207   void *p; void *q;
 208   size_t i; size_t j;
 209 } gl_map_iterator_t;
 210
 211 #if 0 /* These are defined inline below.  */
 212
 213 /* Creates an iterator traversing a map.
 214    The map's contents must not be modified while the iterator is in use,
 215    except for modifying the value of the last returned key or removing the
 216    last returned pair.  */
 217 extern gl_map_iterator_t gl_map_iterator (gl_map_t map);
 218
 219 /* If there is a next pair, stores the next pair in *KEYP and *VALUEP, advances
 220    the iterator, and returns true.  Otherwise, returns false.  */
 221 extern bool gl_map_iterator_next (gl_map_iterator_t *iterator,
 222                                   const void **keyp, const void **valuep);
 223
 224 /* Frees an iterator.  */
 225 extern void gl_map_iterator_free (gl_map_iterator_t *iterator);
 226
 227 #endif /* End of inline functions.  */
 228
 229 /* ------------------------- Implementation Details ------------------------- */
 230
 231 struct gl_map_implementation
 232 {
 233   /* gl_map_t functions.  */
 234   gl_map_t (*nx_create_empty) (gl_map_implementation_t implementation,
 235                                gl_mapkey_equals_fn equals_fn,
 236                                gl_mapkey_hashcode_fn hashcode_fn,
 237                                gl_mapkey_dispose_fn kdispose_fn,
 238                                gl_mapvalue_dispose_fn vdispose_fn);
 239   size_t (*size) (gl_map_t map);
 240   bool (*search) (gl_map_t map, const void *key, const void **valuep);
 241   int (*nx_getput) (gl_map_t map, const void *key, const void *value,
 242                     const void **oldvaluep);
 243   bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep);
 244   void (*map_free) (gl_map_t map);
 245   /* gl_map_iterator_t functions.  */
 246   gl_map_iterator_t (*iterator) (gl_map_t map);
 247   bool (*iterator_next) (gl_map_iterator_t *iterator,
 248                          const void **keyp, const void **valuep);
 249   void (*iterator_free) (gl_map_iterator_t *iterator);
 250 };
 251
 252 struct gl_map_impl_base
 253 {
 254   const struct gl_map_implementation *vtable;
 255   gl_mapkey_equals_fn equals_fn;
 256   gl_mapkey_dispose_fn kdispose_fn;
 257   gl_mapvalue_dispose_fn vdispose_fn;
 258 };
 259
 260 /* Define most functions of this file as accesses to the
 261    struct gl_map_implementation.  */
 262
 263 GL_MAP_INLINE
 264 /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
 265 gl_map_t
 266 gl_map_nx_create_empty (gl_map_implementation_t implementation,
 267                         gl_mapkey_equals_fn equals_fn,
 268                         gl_mapkey_hashcode_fn hashcode_fn,
 269                         gl_mapkey_dispose_fn kdispose_fn,
 270                         gl_mapvalue_dispose_fn vdispose_fn)
 271 {
 272   return implementation->nx_create_empty (implementation,
 273                                           equals_fn, hashcode_fn,
 274                                           kdispose_fn, vdispose_fn);
 275 }
 276
 277 GL_MAP_INLINE size_t
 278 gl_map_size (gl_map_t map)
 279 {
 280   return ((const struct gl_map_impl_base *) map)->vtable->size (map);
 281 }
 282
 283 GL_MAP_INLINE bool
 284 gl_map_search (gl_map_t map, const void *key, const void **valuep)
 285 {
 286   return ((const struct gl_map_impl_base *) map)->vtable
 287          ->search (map, key, valuep);
 288 }
 289
 290 _GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
 291 gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
 292                    const void **oldvaluep)
 293 {
 294   return ((const struct gl_map_impl_base *) map)->vtable
 295          ->nx_getput (map, key, value, oldvaluep);
 296 }
 297
 298 GL_MAP_INLINE bool
 299 gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep)
 300 {
 301   return ((const struct gl_map_impl_base *) map)->vtable
 302          ->getremove (map, key, oldvaluep);
 303 }
 304
 305 GL_MAP_INLINE void
 306 gl_map_free (gl_map_t map)
 307 {
 308   ((const struct gl_map_impl_base *) map)->vtable->map_free (map);
 309 }
 310
 311 GL_MAP_INLINE gl_map_iterator_t
 312 gl_map_iterator (gl_map_t map)
 313 {
 314   return ((const struct gl_map_impl_base *) map)->vtable->iterator (map);
 315 }
 316
 317 GL_MAP_INLINE bool
 318 gl_map_iterator_next (gl_map_iterator_t *iterator,
 319                       const void **keyp, const void **valuep)
 320 {
 321   return iterator->vtable->iterator_next (iterator, keyp, valuep);
 322 }
 323
 324 GL_MAP_INLINE void
 325 gl_map_iterator_free (gl_map_iterator_t *iterator)
 326 {
 327   iterator->vtable->iterator_free (iterator);
 328 }
 329
 330 /* Define the convenience functions, that is, the functions that are independent
 331    of the implementation.  */
 332
 333 GL_MAP_INLINE const void *
 334 gl_map_get (gl_map_t map, const void *key)
 335 {
 336   const void *value = NULL;
 337   gl_map_search (map, key, &value);
 338   return value;
 339 }
 340
 341 _GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
 342 gl_map_nx_put (gl_map_t map, const void *key, const void *value)
 343 {
 344   const void *oldvalue;
 345   int result = gl_map_nx_getput (map, key, value, &oldvalue);
 346   if (result == 0)
 347     {
 348       gl_mapvalue_dispose_fn vdispose_fn =
 349         ((const struct gl_map_impl_base *) map)->vdispose_fn;
 350       if (vdispose_fn != NULL)
 351         vdispose_fn (oldvalue);
 352     }
 353   return result;
 354 }
 355
 356 GL_MAP_INLINE bool
 357 gl_map_remove (gl_map_t map, const void *key)
 358 {
 359   const void *oldvalue;
 360   bool result = gl_map_getremove (map, key, &oldvalue);
 361   if (result)
 362     {
 363       gl_mapvalue_dispose_fn vdispose_fn =
 364         ((const struct gl_map_impl_base *) map)->vdispose_fn;
 365       if (vdispose_fn != NULL)
 366         vdispose_fn (oldvalue);
 367     }
 368   return result;
 369 }
 370
 371 #ifdef __cplusplus
 372 }
 373 #endif
 374
 375 _GL_INLINE_HEADER_END
 376
 377 #endif /* _GL_MAP_H */