lib/gl_omap.h

   1 /* Abstract ordered map data type.
   2    Copyright (C) 2006-2007, 2009-2018 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_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    Return 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 /* Create 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,
 118                                        gl_mapkey_compar_fn compar_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_omap_t gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
 123                                           gl_mapkey_compar_fn compar_fn,
 124                                           gl_mapkey_dispose_fn kdispose_fn,
 125                                           gl_mapvalue_dispose_fn vdispose_fn);
 126
 127 /* Return the current number of pairs in an ordered map.  */
 128 extern size_t gl_omap_size (gl_omap_t map);
 129
 130 /* Search whether a pair with the given key is already in the ordered map.
 131    Return the value if found, or NULL if not present in the map.  */
 132 extern const void * gl_omap_get (gl_omap_t map, const void *key);
 133
 134 /* Search whether a pair with the given key is already in the ordered map.
 135    Return true and set *VALUEP to the value if found.
 136    Return false if not present in the map.  */
 137 extern bool gl_omap_search (gl_omap_t map, const void *key,
 138                             const void **valuep);
 139
 140 /* Search the pair with the least key in the ordered map that compares
 141    greater or equal to the given THRESHOLD.  The representation of the
 142    THRESHOLD is defined by the THRESHOLD_FN.
 143    Return true and store the found pair in *KEYP and *VALUEP if found.
 144    Otherwise return false.  */
 145 extern bool gl_omap_search_atleast (gl_omap_t map,
 146                                     gl_mapkey_threshold_fn threshold_fn,
 147                                     const void *threshold,
 148                                     const void **keyp, const void **valuep);
 149
 150 /* Add a pair to an ordered map.
 151    Return true if a pair with the given key was not already in the map and so
 152    this pair was added.
 153    Return false if a pair with the given key was already in the map and only
 154    its value was replaced.  */
 155 /* declared in gl_xomap.h */
 156 extern bool gl_omap_put (gl_omap_t map, const void *key, const void *value);
 157 /* Likewise.  Return -1 upon out-of-memory.  */
 158 extern int gl_omap_nx_put (gl_omap_t map, const void *key, const void *value)
 159 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 160   __attribute__ ((__warn_unused_result__))
 161 #endif
 162   ;
 163
 164 /* Add a pair to an ordered map and retrieve the previous value.
 165    Return true if a pair with the given key was not already in the map and so
 166    this pair was added.
 167    Return false and set *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.  Return -1 upon out-of-memory.  */
 173 extern int gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
 174                               const void **oldvaluep)
 175 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 176   __attribute__ ((__warn_unused_result__))
 177 #endif
 178   ;
 179
 180 /* Remove a pair from an ordered map.
 181    Return true if the key was found and its pair removed.
 182    Return false otherwise.  */
 183 extern bool gl_omap_remove (gl_omap_t map, const void *key);
 184
 185 /* Remove a pair from an ordered map and retrieve the previous value.
 186    Return true and set *OLDVALUEP to the previous value, if the key was found
 187    and its pair removed.
 188    Return false otherwise.  */
 189 extern bool gl_omap_getremove (gl_omap_t map, const void *key,
 190                                const void **oldvaluep);
 191
 192 /* Free an entire ordered map.
 193    (But this call does not free the keys and values of the pairs in the map.
 194    It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
 195    of the pairs in the map.)  */
 196 extern void gl_omap_free (gl_omap_t map);
 197
 198 #endif /* End of inline and gl_xomap.h-defined functions.  */
 199
 200 /* ---------------------- gl_omap_iterator_t Data Type ---------------------- */
 201
 202 /* Functions for iterating through an ordered map.  */
 203
 204 /* Type of an iterator that traverses an ordered map.
 205    This is a fixed-size struct, so that creation of an iterator doesn't need
 206    memory allocation on the heap.  */
 207 typedef struct
 208 {
 209   /* For fast dispatch of gl_omap_iterator_next.  */
 210   const struct gl_omap_implementation *vtable;
 211   /* For detecting whether the last returned pair was removed.  */
 212   gl_omap_t map;
 213   size_t count;
 214   /* Other, implementation-private fields.  */
 215   void *p; void *q;
 216   size_t i; size_t j;
 217 } gl_omap_iterator_t;
 218
 219 #if 0 /* These are defined inline below.  */
 220
 221 /* Create an iterator traversing an ordered map.
 222    The map's contents must not be modified while the iterator is in use,
 223    except for modifying the value of the last returned key or removing the
 224    last returned pair.  */
 225 extern gl_omap_iterator_t gl_omap_iterator (gl_omap_t map);
 226
 227 /* If there is a next pair, store the next pair in *KEYP and *VALUEP, advance
 228    the iterator, and return true.  Otherwise, return false.  */
 229 extern bool gl_omap_iterator_next (gl_omap_iterator_t *iterator,
 230                                    const void **keyp, const void **valuep);
 231
 232 /* Free an iterator.  */
 233 extern void gl_omap_iterator_free (gl_omap_iterator_t *iterator);
 234
 235 #endif /* End of inline functions.  */
 236
 237 /* ------------------------- Implementation Details ------------------------- */
 238
 239 struct gl_omap_implementation
 240 {
 241   /* gl_omap_t functions.  */
 242   gl_omap_t (*nx_create_empty) (gl_omap_implementation_t implementation,
 243                                 gl_mapkey_compar_fn compar_fn,
 244                                 gl_mapkey_dispose_fn kdispose_fn,
 245                                 gl_mapvalue_dispose_fn vdispose_fn);
 246   size_t (*size) (gl_omap_t map);
 247   bool (*search) (gl_omap_t map, const void *key, const void **valuep);
 248   bool (*search_atleast) (gl_omap_t map,
 249                           gl_mapkey_threshold_fn threshold_fn,
 250                           const void *threshold,
 251                           const void **keyp, const void **valuep);
 252   int (*nx_getput) (gl_omap_t map, const void *key, const void *value,
 253                     const void **oldvaluep);
 254   bool (*getremove) (gl_omap_t map, const void *key, const void **oldvaluep);
 255   void (*omap_free) (gl_omap_t map);
 256   /* gl_omap_iterator_t functions.  */
 257   gl_omap_iterator_t (*iterator) (gl_omap_t map);
 258   bool (*iterator_next) (gl_omap_iterator_t *iterator,
 259                          const void **keyp, const void **valuep);
 260   void (*iterator_free) (gl_omap_iterator_t *iterator);
 261 };
 262
 263 struct gl_omap_impl_base
 264 {
 265   const struct gl_omap_implementation *vtable;
 266   gl_mapkey_compar_fn compar_fn;
 267   gl_mapkey_dispose_fn kdispose_fn;
 268   gl_mapvalue_dispose_fn vdispose_fn;
 269 };
 270
 271 /* Define most functions of this file as accesses to the
 272    struct gl_omap_implementation.  */
 273
 274 GL_OMAP_INLINE gl_omap_t
 275 gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
 276                          gl_mapkey_compar_fn compar_fn,
 277                          gl_mapkey_dispose_fn kdispose_fn,
 278                          gl_mapvalue_dispose_fn vdispose_fn)
 279 {
 280   return implementation->nx_create_empty (implementation, compar_fn,
 281                                           kdispose_fn, vdispose_fn);
 282 }
 283
 284 GL_OMAP_INLINE size_t
 285 gl_omap_size (gl_omap_t map)
 286 {
 287   return ((const struct gl_omap_impl_base *) map)->vtable->size (map);
 288 }
 289
 290 GL_OMAP_INLINE bool
 291 gl_omap_search (gl_omap_t map, const void *key, const void **valuep)
 292 {
 293   return ((const struct gl_omap_impl_base *) map)->vtable
 294          ->search (map, key, valuep);
 295 }
 296
 297 GL_OMAP_INLINE bool
 298 gl_omap_search_atleast (gl_omap_t map,
 299                         gl_mapkey_threshold_fn threshold_fn,
 300                         const void *threshold,
 301                         const void **keyp, const void **valuep)
 302 {
 303   return ((const struct gl_omap_impl_base *) map)->vtable
 304          ->search_atleast (map, threshold_fn, threshold, keyp, valuep);
 305 }
 306
 307 GL_OMAP_INLINE int
 308 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 309   __attribute__ ((__warn_unused_result__))
 310 #endif
 311 gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
 312                    const void **oldvaluep)
 313 {
 314   return ((const struct gl_omap_impl_base *) map)->vtable
 315          ->nx_getput (map, key, value, oldvaluep);
 316 }
 317
 318 GL_OMAP_INLINE bool
 319 gl_omap_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
 320 {
 321   return ((const struct gl_omap_impl_base *) map)->vtable
 322          ->getremove (map, key, oldvaluep);
 323 }
 324
 325 GL_OMAP_INLINE void
 326 gl_omap_free (gl_omap_t map)
 327 {
 328   ((const struct gl_omap_impl_base *) map)->vtable->omap_free (map);
 329 }
 330
 331 GL_OMAP_INLINE gl_omap_iterator_t
 332 gl_omap_iterator (gl_omap_t map)
 333 {
 334   return ((const struct gl_omap_impl_base *) map)->vtable->iterator (map);
 335 }
 336
 337 GL_OMAP_INLINE bool
 338 gl_omap_iterator_next (gl_omap_iterator_t *iterator,
 339                        const void **keyp, const void **valuep)
 340 {
 341   return iterator->vtable->iterator_next (iterator, keyp, valuep);
 342 }
 343
 344 GL_OMAP_INLINE void
 345 gl_omap_iterator_free (gl_omap_iterator_t *iterator)
 346 {
 347   iterator->vtable->iterator_free (iterator);
 348 }
 349
 350 /* Define the convenience functions, that is, the functions that are independent
 351    of the implementation.  */
 352
 353 GL_OMAP_INLINE const void *
 354 gl_omap_get (gl_omap_t map, const void *key)
 355 {
 356   const void *value = NULL;
 357   gl_omap_search (map, key, &value);
 358   return value;
 359 }
 360
 361 GL_OMAP_INLINE int
 362 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 363   __attribute__ ((__warn_unused_result__))
 364 #endif
 365 gl_omap_nx_put (gl_omap_t map, const void *key, const void *value)
 366 {
 367   const void *oldvalue;
 368   int result = gl_omap_nx_getput (map, key, value, &oldvalue);
 369   if (result == 0)
 370     {
 371       gl_mapvalue_dispose_fn vdispose_fn =
 372         ((const struct gl_omap_impl_base *) map)->vdispose_fn;
 373       if (vdispose_fn != NULL)
 374         vdispose_fn (oldvalue);
 375     }
 376   return result;
 377 }
 378
 379 GL_OMAP_INLINE bool
 380 gl_omap_remove (gl_omap_t map, const void *key)
 381 {
 382   const void *oldvalue;
 383   bool result = gl_omap_getremove (map, key, &oldvalue);
 384   if (result)
 385     {
 386       gl_mapvalue_dispose_fn vdispose_fn =
 387         ((const struct gl_omap_impl_base *) map)->vdispose_fn;
 388       if (vdispose_fn != NULL)
 389         vdispose_fn (oldvalue);
 390     }
 391   return result;
 392 }
 393
 394 #ifdef __cplusplus
 395 }
 396 #endif
 397
 398 _GL_INLINE_HEADER_END
 399
 400 #endif /* _GL_OMAP_H */