lib/gl_map.h

   1 /* Abstract map data type.
   2    Copyright (C) 2006-2007, 2009-2019 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 /* Create 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.  Return 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 /* Return the current number of pairs in a map.  */
 129 extern size_t gl_map_size (gl_map_t map);
 130
 131 /* Search whether a pair with the given key is already in the map.
 132    Return 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 /* Search whether a pair with the given key is already in the map.
 136    Return true and set *VALUEP to the value if found.
 137    Return 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 /* Add a pair to a map.
 141    Return true if a pair with the given key was not already in the map and so
 142    this pair was added.
 143    Return 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.  Return -1 upon out-of-memory.  */
 148 extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value)
 149 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 150   __attribute__ ((__warn_unused_result__))
 151 #endif
 152   ;
 153
 154 /* Add a pair to a map and retrieve the previous value.
 155    Return true if a pair with the given key was not already in the map and so
 156    this pair was added.
 157    Return false and set *OLDVALUEP to the previous value, if a pair with the
 158    given key was already in the map and only its value was replaced.  */
 159 /* declared in gl_xmap.h */
 160 extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
 161                            const void **oldvaluep);
 162 /* Likewise.  Return -1 upon out-of-memory.  */
 163 extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
 164                              const void **oldvaluep)
 165 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 166   __attribute__ ((__warn_unused_result__))
 167 #endif
 168   ;
 169
 170 /* Remove a pair from a map.
 171    Return true if the key was found and its pair removed.
 172    Return false otherwise.  */
 173 extern bool gl_map_remove (gl_map_t map, const void *key);
 174
 175 /* Remove a pair from a map and retrieve the previous value.
 176    Return true and set *OLDVALUEP to the previous value, if the key was found
 177    and its pair removed.
 178    Return false otherwise.  */
 179 extern bool gl_map_getremove (gl_map_t map, const void *key,
 180                               const void **oldvaluep);
 181
 182 /* Free an entire map.
 183    (But this call does not free the keys and values of the pairs in the map.
 184    It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
 185    of the pairs in the map.)  */
 186 extern void gl_map_free (gl_map_t map);
 187
 188 #endif /* End of inline and gl_xmap.h-defined functions.  */
 189
 190 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
 191
 192 /* Functions for iterating through a map.
 193    Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an
 194    unpredictable order.  If you need a predictable order, use GL_LINKEDHASH_MAP
 195    instead of GL_HASH_MAP.  */
 196
 197 /* Type of an iterator that traverses a map.
 198    This is a fixed-size struct, so that creation of an iterator doesn't need
 199    memory allocation on the heap.  */
 200 typedef struct
 201 {
 202   /* For fast dispatch of gl_map_iterator_next.  */
 203   const struct gl_map_implementation *vtable;
 204   /* For detecting whether the last returned pair was removed.  */
 205   gl_map_t map;
 206   size_t count;
 207   /* Other, implementation-private fields.  */
 208   void *p; void *q;
 209   size_t i; size_t j;
 210 } gl_map_iterator_t;
 211
 212 #if 0 /* These are defined inline below.  */
 213
 214 /* Create an iterator traversing a map.
 215    The map's contents must not be modified while the iterator is in use,
 216    except for modifying the value of the last returned key or removing the
 217    last returned pair.  */
 218 extern gl_map_iterator_t gl_map_iterator (gl_map_t map);
 219
 220 /* If there is a next pair, store the next pair in *KEYP and *VALUEP, advance
 221    the iterator, and return true.  Otherwise, return false.  */
 222 extern bool gl_map_iterator_next (gl_map_iterator_t *iterator,
 223                                   const void **keyp, const void **valuep);
 224
 225 /* Free an iterator.  */
 226 extern void gl_map_iterator_free (gl_map_iterator_t *iterator);
 227
 228 #endif /* End of inline functions.  */
 229
 230 /* ------------------------- Implementation Details ------------------------- */
 231
 232 struct gl_map_implementation
 233 {
 234   /* gl_map_t functions.  */
 235   gl_map_t (*nx_create_empty) (gl_map_implementation_t implementation,
 236                                gl_mapkey_equals_fn equals_fn,
 237                                gl_mapkey_hashcode_fn hashcode_fn,
 238                                gl_mapkey_dispose_fn kdispose_fn,
 239                                gl_mapvalue_dispose_fn vdispose_fn);
 240   size_t (*size) (gl_map_t map);
 241   bool (*search) (gl_map_t map, const void *key, const void **valuep);
 242   int (*nx_getput) (gl_map_t map, const void *key, const void *value,
 243                     const void **oldvaluep);
 244   bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep);
 245   void (*map_free) (gl_map_t map);
 246   /* gl_map_iterator_t functions.  */
 247   gl_map_iterator_t (*iterator) (gl_map_t map);
 248   bool (*iterator_next) (gl_map_iterator_t *iterator,
 249                          const void **keyp, const void **valuep);
 250   void (*iterator_free) (gl_map_iterator_t *iterator);
 251 };
 252
 253 struct gl_map_impl_base
 254 {
 255   const struct gl_map_implementation *vtable;
 256   gl_mapkey_equals_fn equals_fn;
 257   gl_mapkey_dispose_fn kdispose_fn;
 258   gl_mapvalue_dispose_fn vdispose_fn;
 259 };
 260
 261 /* Define most functions of this file as accesses to the
 262    struct gl_map_implementation.  */
 263
 264 GL_MAP_INLINE gl_map_t
 265 gl_map_nx_create_empty (gl_map_implementation_t implementation,
 266                         gl_mapkey_equals_fn equals_fn,
 267                         gl_mapkey_hashcode_fn hashcode_fn,
 268                         gl_mapkey_dispose_fn kdispose_fn,
 269                         gl_mapvalue_dispose_fn vdispose_fn)
 270 {
 271   return implementation->nx_create_empty (implementation,
 272                                           equals_fn, hashcode_fn,
 273                                           kdispose_fn, vdispose_fn);
 274 }
 275
 276 GL_MAP_INLINE size_t
 277 gl_map_size (gl_map_t map)
 278 {
 279   return ((const struct gl_map_impl_base *) map)->vtable->size (map);
 280 }
 281
 282 GL_MAP_INLINE bool
 283 gl_map_search (gl_map_t map, const void *key, const void **valuep)
 284 {
 285   return ((const struct gl_map_impl_base *) map)->vtable
 286          ->search (map, key, valuep);
 287 }
 288
 289 GL_MAP_INLINE int
 290 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 291   __attribute__ ((__warn_unused_result__))
 292 #endif
 293 gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
 294                    const void **oldvaluep)
 295 {
 296   return ((const struct gl_map_impl_base *) map)->vtable
 297          ->nx_getput (map, key, value, oldvaluep);
 298 }
 299
 300 GL_MAP_INLINE bool
 301 gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep)
 302 {
 303   return ((const struct gl_map_impl_base *) map)->vtable
 304          ->getremove (map, key, oldvaluep);
 305 }
 306
 307 GL_MAP_INLINE void
 308 gl_map_free (gl_map_t map)
 309 {
 310   ((const struct gl_map_impl_base *) map)->vtable->map_free (map);
 311 }
 312
 313 GL_MAP_INLINE gl_map_iterator_t
 314 gl_map_iterator (gl_map_t map)
 315 {
 316   return ((const struct gl_map_impl_base *) map)->vtable->iterator (map);
 317 }
 318
 319 GL_MAP_INLINE bool
 320 gl_map_iterator_next (gl_map_iterator_t *iterator,
 321                       const void **keyp, const void **valuep)
 322 {
 323   return iterator->vtable->iterator_next (iterator, keyp, valuep);
 324 }
 325
 326 GL_MAP_INLINE void
 327 gl_map_iterator_free (gl_map_iterator_t *iterator)
 328 {
 329   iterator->vtable->iterator_free (iterator);
 330 }
 331
 332 /* Define the convenience functions, that is, the functions that are independent
 333    of the implementation.  */
 334
 335 GL_MAP_INLINE const void *
 336 gl_map_get (gl_map_t map, const void *key)
 337 {
 338   const void *value = NULL;
 339   gl_map_search (map, key, &value);
 340   return value;
 341 }
 342
 343 GL_MAP_INLINE int
 344 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 345   __attribute__ ((__warn_unused_result__))
 346 #endif
 347 gl_map_nx_put (gl_map_t map, const void *key, const void *value)
 348 {
 349   const void *oldvalue;
 350   int result = gl_map_nx_getput (map, key, value, &oldvalue);
 351   if (result == 0)
 352     {
 353       gl_mapvalue_dispose_fn vdispose_fn =
 354         ((const struct gl_map_impl_base *) map)->vdispose_fn;
 355       if (vdispose_fn != NULL)
 356         vdispose_fn (oldvalue);
 357     }
 358   return result;
 359 }
 360
 361 GL_MAP_INLINE bool
 362 gl_map_remove (gl_map_t map, const void *key)
 363 {
 364   const void *oldvalue;
 365   bool result = gl_map_getremove (map, key, &oldvalue);
 366   if (result)
 367     {
 368       gl_mapvalue_dispose_fn vdispose_fn =
 369         ((const struct gl_map_impl_base *) map)->vdispose_fn;
 370       if (vdispose_fn != NULL)
 371         vdispose_fn (oldvalue);
 372     }
 373   return result;
 374 }
 375
 376 #ifdef __cplusplus
 377 }
 378 #endif
 379
 380 _GL_INLINE_HEADER_END
 381
 382 #endif /* _GL_MAP_H */