lib/gl_map.h

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