root/maint/gnulib/lib/gl_omap.h

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

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. gl_omap_create_empty
  2. gl_omap_nx_create_empty
  3. gl_omap_size
  4. gl_omap_search
  5. gl_omap_search_atleast
  6. gl_omap_nx_getput
  7. gl_omap_getremove
  8. gl_omap_free
  9. gl_omap_iterator
  10. gl_omap_iterator_next
  11. gl_omap_iterator_free
  12. gl_omap_get
  13. gl_omap_nx_put
  14. gl_omap_remove

   1 /* Abstract ordered 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 file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9 
  10    This file 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 Lesser General Public License for more details.
  14 
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17 
  18 #ifndef _GL_OMAP_H
  19 #define _GL_OMAP_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_OMAP_INLINE
  29 # define GL_OMAP_INLINE _GL_INLINE
  30 #endif
  31 
  32 #ifdef __cplusplus
  33 extern "C" {
  34 #endif
  35 
  36 
  37 /* gl_omap is an abstract ordered map data type.  It can contain any number
  38    of (key, value) pairs, where
  39      - keys and values are objects ('void *' or 'const void *' pointers),
  40      - The (key, value) pairs are ordered by the key, in the order of a given
  41        comparator function.
  42      - There are no (key, value1) and (key, value2) pairs with the same key
  43        (in the sense of the comparator function).
  44 
  45    There are several implementations of this ordered map datatype, optimized
  46    for different operations or for memory.  You can start using the simplest
  47    ordered map implementation, GL_ARRAY_OMAP, and switch to a different
  48    implementation later, when you realize which operations are performed
  49    the most frequently.  The API of the different implementations is exactly
  50    the same; when switching to a different implementation, you only have to
  51    change the gl_omap_create call.
  52 
  53    The implementations are:
  54      GL_ARRAY_OMAP        a growable array
  55      GL_AVLTREE_OMAP      a binary tree (AVL tree)
  56      GL_RBTREE_OMAP       a binary tree (red-black tree)
  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 pair, GL_ARRAY_OMAP is the most compact representation, and
  61    GL_AVLTREE_OMAP, GL_RBTREE_OMAP need more memory.
  62 
  63    The guaranteed average performance of the operations is, for a map of
  64    n pairs:
  65 
  66    Operation                  ARRAY     TREE
  67 
  68    gl_omap_size                O(1)     O(1)
  69    gl_omap_get               O(log n) O(log n)
  70    gl_omap_put                 O(n)   O(log n)
  71    gl_omap_remove              O(n)   O(log n)
  72    gl_omap_search            O(log n) O(log n)
  73    gl_omap_search_atleast    O(log n) O(log n)
  74    gl_omap_iterator            O(1)   O(log n)
  75    gl_omap_iterator_next       O(1)   O(log n)
  76  */
  77 
  78 /* -------------------------- gl_omap_t Data Type -------------------------- */
  79 
  80 /* Type of function used to compare two keys.  Same as for qsort().
  81    NULL denotes pointer comparison.  */
  82 typedef int (*gl_mapkey_compar_fn) (const void *key1, const void *key2);
  83 
  84 #ifndef _GL_MAP_DISPOSE_FNS_DEFINED
  85 
  86 /* Type of function used to dispose a key once a (key, value) pair is removed
  87    from a map.  NULL denotes a no-op.  */
  88 typedef void (*gl_mapkey_dispose_fn) (const void *key);
  89 
  90 /* Type of function used to dispose a value once a (key, value) pair is removed
  91    from a map.  NULL denotes a no-op.  */
  92 typedef void (*gl_mapvalue_dispose_fn) (const void *value);
  93 
  94 # define _GL_MAP_DISPOSE_FNS_DEFINED 1
  95 #endif
  96 
  97 /* Type of function used to compare a key with a threshold.
  98    Returns true if the key is greater or equal than the threshold.  */
  99 typedef bool (*gl_mapkey_threshold_fn) (const void *key, const void *threshold);
 100 
 101 struct gl_omap_impl;
 102 /* Type representing an entire ordered map.  */
 103 typedef struct gl_omap_impl * gl_omap_t;
 104 
 105 struct gl_omap_implementation;
 106 /* Type representing a ordered map datatype implementation.  */
 107 typedef const struct gl_omap_implementation * gl_omap_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_OMAP, GL_AVLTREE_OMAP, GL_RBTREE_OMAP.
 113    COMPAR_FN is a key comparison function or NULL.
 114    KDISPOSE_FN is a key disposal function or NULL.
 115    VDISPOSE_FN is a value disposal function or NULL.  */
 116 /* declared in gl_xomap.h */
 117 extern gl_omap_t gl_omap_create_empty (gl_omap_implementation_t implementation,
     /* [previous][next][first][last][top][bottom][index][help] */
 118                                        gl_mapkey_compar_fn compar_fn,
 119                                        gl_mapkey_dispose_fn kdispose_fn,
 120                                        gl_mapvalue_dispose_fn vdispose_fn)
 121   /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/
 122   _GL_ATTRIBUTE_RETURNS_NONNULL;
 123 /* Likewise.  Returns NULL upon out-of-memory.  */
 124 extern gl_omap_t gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
 125                                           gl_mapkey_compar_fn compar_fn,
 126                                           gl_mapkey_dispose_fn kdispose_fn,
 127                                           gl_mapvalue_dispose_fn vdispose_fn)
 128   /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/;
 129 
 130 /* Returns the current number of pairs in an ordered map.  */
 131 extern size_t gl_omap_size (gl_omap_t map);
 132 
 133 /* Searches whether a pair with the given key is already in the ordered map.
 134    Returns the value if found, or NULL if not present in the map.  */
 135 extern const void * gl_omap_get (gl_omap_t map, const void *key);
 136 
 137 /* Searches whether a pair with the given key is already in the ordered map.
 138    Returns true and sets *VALUEP to the value if found.
 139    Returns false if not present in the map.  */
 140 extern bool gl_omap_search (gl_omap_t map, const void *key,
 141                             const void **valuep);
 142 
 143 /* Searches the pair with the least key in the ordered map that compares
 144    greater or equal to the given THRESHOLD.  The representation of the
 145    THRESHOLD is defined by the THRESHOLD_FN.
 146    Returns true and stores the found pair in *KEYP and *VALUEP if found.
 147    Otherwise returns false.  */
 148 extern bool gl_omap_search_atleast (gl_omap_t map,
 149                                     gl_mapkey_threshold_fn threshold_fn,
 150                                     const void *threshold,
 151                                     const void **keyp, const void **valuep);
 152 
 153 /* Adds a pair to an ordered map.
 154    Returns true if a pair with the given key was not already in the map and so
 155    this pair was added.
 156    Returns false if a pair with the given key was already in the map and only
 157    its value was replaced.  */
 158 /* declared in gl_xomap.h */
 159 extern bool gl_omap_put (gl_omap_t map, const void *key, const void *value);
 160 /* Likewise.  Returns -1 upon out-of-memory.  */
 161 _GL_ATTRIBUTE_NODISCARD
 162 extern int gl_omap_nx_put (gl_omap_t map, const void *key, const void *value);
 163 
 164 /* Adds a pair to an ordered map and retrieves the previous value.
 165    Returns true if a pair with the given key was not already in the map and so
 166    this pair was added.
 167    Returns false and sets *OLDVALUEP to the previous value, if a pair with the
 168    given key was already in the map and only its value was replaced.  */
 169 /* declared in gl_xomap.h */
 170 extern bool gl_omap_getput (gl_omap_t map, const void *key, const void *value,
 171                             const void **oldvaluep);
 172 /* Likewise.  Returns -1 upon out-of-memory.  */
 173 _GL_ATTRIBUTE_NODISCARD
 174 extern int gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
 175                               const void **oldvaluep);
 176 
 177 /* Removes a pair from an ordered map.
 178    Returns true if the key was found and its pair removed.
 179    Returns false otherwise.  */
 180 extern bool gl_omap_remove (gl_omap_t map, const void *key);
 181 
 182 /* Removes a pair from an ordered map and retrieves the previous value.
 183    Returns true and sets *OLDVALUEP to the previous value, if the key was found
 184    and its pair removed.
 185    Returns false otherwise.  */
 186 extern bool gl_omap_getremove (gl_omap_t map, const void *key,
 187                                const void **oldvaluep);
 188 
 189 /* Frees an entire ordered map.
 190    (But this call does not free the keys and values of the pairs in the map.
 191    It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
 192    of the pairs in the map.)  */
 193 extern void gl_omap_free (gl_omap_t map);
 194 
 195 #endif /* End of inline and gl_xomap.h-defined functions.  */
 196 
 197 /* ---------------------- gl_omap_iterator_t Data Type ---------------------- */
 198 
 199 /* Functions for iterating through an ordered map.  */
 200 
 201 /* Type of an iterator that traverses an ordered map.
 202    This is a fixed-size struct, so that creation of an iterator doesn't need
 203    memory allocation on the heap.  */
 204 typedef struct
 205 {
 206   /* For fast dispatch of gl_omap_iterator_next.  */
 207   const struct gl_omap_implementation *vtable;
 208   /* For detecting whether the last returned pair was removed.  */
 209   gl_omap_t map;
 210   size_t count;
 211   /* Other, implementation-private fields.  */
 212   void *p; void *q;
 213   size_t i; size_t j;
 214 } gl_omap_iterator_t;
 215 
 216 #if 0 /* These are defined inline below.  */
 217 
 218 /* Creates an iterator traversing an ordered map.
 219    The map's contents must not be modified while the iterator is in use,
 220    except for modifying the value of the last returned key or removing the
 221    last returned pair.  */
 222 extern gl_omap_iterator_t gl_omap_iterator (gl_omap_t map);
 223 
 224 /* If there is a next pair, stores the next pair in *KEYP and *VALUEP, advances
 225    the iterator, and returns true.  Otherwise, returns false.  */
 226 extern bool gl_omap_iterator_next (gl_omap_iterator_t *iterator,
 227                                    const void **keyp, const void **valuep);
 228 
 229 /* Frees an iterator.  */
 230 extern void gl_omap_iterator_free (gl_omap_iterator_t *iterator);
 231 
 232 #endif /* End of inline functions.  */
 233 
 234 /* ------------------------- Implementation Details ------------------------- */
 235 
 236 struct gl_omap_implementation
 237 {
 238   /* gl_omap_t functions.  */
 239   gl_omap_t (*nx_create_empty) (gl_omap_implementation_t implementation,
 240                                 gl_mapkey_compar_fn compar_fn,
 241                                 gl_mapkey_dispose_fn kdispose_fn,
 242                                 gl_mapvalue_dispose_fn vdispose_fn);
 243   size_t (*size) (gl_omap_t map);
 244   bool (*search) (gl_omap_t map, const void *key, const void **valuep);
 245   bool (*search_atleast) (gl_omap_t map,
 246                           gl_mapkey_threshold_fn threshold_fn,
 247                           const void *threshold,
 248                           const void **keyp, const void **valuep);
 249   int (*nx_getput) (gl_omap_t map, const void *key, const void *value,
 250                     const void **oldvaluep);
 251   bool (*getremove) (gl_omap_t map, const void *key, const void **oldvaluep);
 252   void (*omap_free) (gl_omap_t map);
 253   /* gl_omap_iterator_t functions.  */
 254   gl_omap_iterator_t (*iterator) (gl_omap_t map);
 255   bool (*iterator_next) (gl_omap_iterator_t *iterator,
 256                          const void **keyp, const void **valuep);
 257   void (*iterator_free) (gl_omap_iterator_t *iterator);
 258 };
 259 
 260 struct gl_omap_impl_base
 261 {
 262   const struct gl_omap_implementation *vtable;
 263   gl_mapkey_compar_fn compar_fn;
 264   gl_mapkey_dispose_fn kdispose_fn;
 265   gl_mapvalue_dispose_fn vdispose_fn;
 266 };
 267 
 268 /* Define most functions of this file as accesses to the
 269    struct gl_omap_implementation.  */
 270 
 271 GL_OMAP_INLINE
 272 /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/
 273 gl_omap_t
 274 gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
     /* [previous][next][first][last][top][bottom][index][help] */
 275                          gl_mapkey_compar_fn compar_fn,
 276                          gl_mapkey_dispose_fn kdispose_fn,
 277                          gl_mapvalue_dispose_fn vdispose_fn)
 278 {
 279   return implementation->nx_create_empty (implementation, compar_fn,
 280                                           kdispose_fn, vdispose_fn);
 281 }
 282 
 283 GL_OMAP_INLINE size_t
 284 gl_omap_size (gl_omap_t map)
     /* [previous][next][first][last][top][bottom][index][help] */
 285 {
 286   return ((const struct gl_omap_impl_base *) map)->vtable->size (map);
 287 }
 288 
 289 GL_OMAP_INLINE bool
 290 gl_omap_search (gl_omap_t map, const void *key, const void **valuep)
     /* [previous][next][first][last][top][bottom][index][help] */
 291 {
 292   return ((const struct gl_omap_impl_base *) map)->vtable
 293          ->search (map, key, valuep);
 294 }
 295 
 296 GL_OMAP_INLINE bool
 297 gl_omap_search_atleast (gl_omap_t map,
     /* [previous][next][first][last][top][bottom][index][help] */
 298                         gl_mapkey_threshold_fn threshold_fn,
 299                         const void *threshold,
 300                         const void **keyp, const void **valuep)
 301 {
 302   return ((const struct gl_omap_impl_base *) map)->vtable
 303          ->search_atleast (map, threshold_fn, threshold, keyp, valuep);
 304 }
 305 
 306 _GL_ATTRIBUTE_NODISCARD GL_OMAP_INLINE int
 307 gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
     /* [previous][next][first][last][top][bottom][index][help] */
 308                    const void **oldvaluep)
 309 {
 310   return ((const struct gl_omap_impl_base *) map)->vtable
 311          ->nx_getput (map, key, value, oldvaluep);
 312 }
 313 
 314 GL_OMAP_INLINE bool
 315 gl_omap_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
     /* [previous][next][first][last][top][bottom][index][help] */
 316 {
 317   return ((const struct gl_omap_impl_base *) map)->vtable
 318          ->getremove (map, key, oldvaluep);
 319 }
 320 
 321 GL_OMAP_INLINE void
 322 gl_omap_free (gl_omap_t map)
     /* [previous][next][first][last][top][bottom][index][help] */
 323 {
 324   ((const struct gl_omap_impl_base *) map)->vtable->omap_free (map);
 325 }
 326 
 327 GL_OMAP_INLINE gl_omap_iterator_t
 328 gl_omap_iterator (gl_omap_t map)
     /* [previous][next][first][last][top][bottom][index][help] */
 329 {
 330   return ((const struct gl_omap_impl_base *) map)->vtable->iterator (map);
 331 }
 332 
 333 GL_OMAP_INLINE bool
 334 gl_omap_iterator_next (gl_omap_iterator_t *iterator,
     /* [previous][next][first][last][top][bottom][index][help] */
 335                        const void **keyp, const void **valuep)
 336 {
 337   return iterator->vtable->iterator_next (iterator, keyp, valuep);
 338 }
 339 
 340 GL_OMAP_INLINE void
 341 gl_omap_iterator_free (gl_omap_iterator_t *iterator)
     /* [previous][next][first][last][top][bottom][index][help] */
 342 {
 343   iterator->vtable->iterator_free (iterator);
 344 }
 345 
 346 /* Define the convenience functions, that is, the functions that are independent
 347    of the implementation.  */
 348 
 349 GL_OMAP_INLINE const void *
 350 gl_omap_get (gl_omap_t map, const void *key)
     /* [previous][next][first][last][top][bottom][index][help] */
 351 {
 352   const void *value = NULL;
 353   gl_omap_search (map, key, &value);
 354   return value;
 355 }
 356 
 357 _GL_ATTRIBUTE_NODISCARD GL_OMAP_INLINE int
 358 gl_omap_nx_put (gl_omap_t map, const void *key, const void *value)
     /* [previous][next][first][last][top][bottom][index][help] */
 359 {
 360   const void *oldvalue;
 361   int result = gl_omap_nx_getput (map, key, value, &oldvalue);
 362   if (result == 0)
 363     {
 364       gl_mapvalue_dispose_fn vdispose_fn =
 365         ((const struct gl_omap_impl_base *) map)->vdispose_fn;
 366       if (vdispose_fn != NULL)
 367         vdispose_fn (oldvalue);
 368     }
 369   return result;
 370 }
 371 
 372 GL_OMAP_INLINE bool
 373 gl_omap_remove (gl_omap_t map, const void *key)
     /* [previous][next][first][last][top][bottom][index][help] */
 374 {
 375   const void *oldvalue;
 376   bool result = gl_omap_getremove (map, key, &oldvalue);
 377   if (result)
 378     {
 379       gl_mapvalue_dispose_fn vdispose_fn =
 380         ((const struct gl_omap_impl_base *) map)->vdispose_fn;
 381       if (vdispose_fn != NULL)
 382         vdispose_fn (oldvalue);
 383     }
 384   return result;
 385 }
 386 
 387 #ifdef __cplusplus
 388 }
 389 #endif
 390 
 391 _GL_INLINE_HEADER_END
 392 
 393 #endif /* _GL_OMAP_H */

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