lib/gl_omap.h

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