root/maint/gnulib/lib/gl_map.h

/* [previous][next][first][last][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. gl_map_create_empty
  2. gl_map_nx_create_empty
  3. gl_map_size
  4. gl_map_search
  5. gl_map_nx_getput
  6. gl_map_getremove
  7. gl_map_free
  8. gl_map_iterator
  9. gl_map_iterator_next
  10. gl_map_iterator_free
  11. gl_map_get
  12. gl_map_nx_put
  13. gl_map_remove

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

/* [previous][next][first][last][top][bottom][index][help] */