Branch
Hash :
7b089321
Author :
Date :
2025-01-01T09:24:36
maint: run 'make update-copyright'
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
/* Abstract map data type.
Copyright (C) 2006-2007, 2009-2025 Free Software Foundation, Inc.
Written by Bruno Haible <bruno@clisp.org>, 2018.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>. */
#ifndef _GL_MAP_H
#define _GL_MAP_H
/* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE,
_GL_ATTRIBUTE_NODISCARD. */
#if !_GL_CONFIG_H_INCLUDED
#error "Please include config.h first."
#endif
#include <stddef.h>
_GL_INLINE_HEADER_BEGIN
#ifndef GL_MAP_INLINE
# define GL_MAP_INLINE _GL_INLINE
#endif
#ifdef __cplusplus
extern "C" {
#endif
/* gl_map is an abstract map data type. It can contain any number of
(key, value) pairs, where
- keys and values are objects ('void *' or 'const void *' pointers),
- There are no (key, value1) and (key, value2) pairs with the same key
(in the sense of a given comparator function).
There are several implementations of this map datatype, optimized for
different operations or for memory. You can start using the simplest map
implementation, GL_ARRAY_MAP, and switch to a different implementation
later, when you realize which operations are performed the most frequently.
The API of the different implementations is exactly the same; when switching
to a different implementation, you only have to change the gl_map_create
call.
The implementations are:
GL_ARRAY_MAP a growable array
GL_LINKEDHASH_MAP a hash table with a linked list
GL_HASH_MAP a hash table
The memory consumption is asymptotically the same: O(1) for every pair
in the map. When looking more closely at the average memory consumed
for an object, GL_ARRAY_MAP is the most compact representation, then comes
GL_HASH_MAP, and GL_LINKEDHASH_MAP needs the most memory.
The guaranteed average performance of the operations is, for a map of
n pairs:
Operation ARRAY LINKEDHASH
HASH
gl_map_size O(1) O(1)
gl_map_get O(n) O(1)
gl_map_put O(n) O(1)
gl_map_remove O(n) O(1)
gl_map_search O(n) O(1)
gl_map_iterator O(1) O(1)
gl_map_iterator_next O(1) O(1)
*/
/* --------------------------- gl_map_t Data Type --------------------------- */
/* Type of function used to compare two keys.
NULL denotes pointer comparison. */
typedef bool (*gl_mapkey_equals_fn) (const void *key1, const void *key2);
/* Type of function used to compute a hash code.
NULL denotes a function that depends only on the pointer itself. */
typedef size_t (*gl_mapkey_hashcode_fn) (const void *key);
#ifndef _GL_MAP_DISPOSE_FNS_DEFINED
/* Type of function used to dispose a key once a (key, value) pair is removed
from a map. NULL denotes a no-op. */
typedef void (*gl_mapkey_dispose_fn) (const void *key);
/* Type of function used to dispose a value once a (key, value) pair is removed
from a map. NULL denotes a no-op. */
typedef void (*gl_mapvalue_dispose_fn) (const void *value);
# define _GL_MAP_DISPOSE_FNS_DEFINED 1
#endif
struct gl_map_impl;
/* Type representing an entire map. */
typedef struct gl_map_impl * gl_map_t;
struct gl_map_implementation;
/* Type representing a map datatype implementation. */
typedef const struct gl_map_implementation * gl_map_implementation_t;
#if 0 /* Unless otherwise specified, these are defined inline below. */
/* Creates an empty map.
IMPLEMENTATION is one of GL_ARRAY_MAP, GL_LINKEDHASH_MAP, GL_HASH_MAP.
EQUALS_FN is a key comparison function or NULL.
HASHCODE_FN is a key hash code function or NULL.
KDISPOSE_FN is a key disposal function or NULL.
VDISPOSE_FN is a value disposal function or NULL. */
/* declared in gl_xmap.h */
extern gl_map_t gl_map_create_empty (gl_map_implementation_t implementation,
gl_mapkey_equals_fn equals_fn,
gl_mapkey_hashcode_fn hashcode_fn,
gl_mapkey_dispose_fn kdispose_fn,
gl_mapvalue_dispose_fn vdispose_fn)
/*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
_GL_ATTRIBUTE_RETURNS_NONNULL;
/* Likewise. Returns NULL upon out-of-memory. */
extern gl_map_t gl_map_nx_create_empty (gl_map_implementation_t implementation,
gl_mapkey_equals_fn equals_fn,
gl_mapkey_hashcode_fn hashcode_fn,
gl_mapkey_dispose_fn kdispose_fn,
gl_mapvalue_dispose_fn vdispose_fn)
/*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/;
/* Returns the current number of pairs in a map. */
extern size_t gl_map_size (gl_map_t map);
/* Searches whether a pair with the given key is already in the map.
Returns the value if found, or NULL if not present in the map. */
extern const void * gl_map_get (gl_map_t map, const void *key);
/* Searches whether a pair with the given key is already in the map.
Returns true and sets *VALUEP to the value if found.
Returns false if not present in the map. */
extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep);
/* Adds a pair to a map.
Returns true if a pair with the given key was not already in the map and so
this pair was added.
Returns false if a pair with the given key was already in the map and only
its value was replaced. */
/* declared in gl_xmap.h */
extern bool gl_map_put (gl_map_t map, const void *key, const void *value);
/* Likewise. Returns -1 upon out-of-memory. */
_GL_ATTRIBUTE_NODISCARD
extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value);
/* Adds a pair to a map and retrieves the previous value.
Returns true if a pair with the given key was not already in the map and so
this pair was added.
Returns false and sets *OLDVALUEP to the previous value, if a pair with the
given key was already in the map and only its value was replaced. */
/* declared in gl_xmap.h */
extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
const void **oldvaluep);
/* Likewise. Returns -1 upon out-of-memory. */
_GL_ATTRIBUTE_NODISCARD
extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
const void **oldvaluep);
/* Removes a pair from a map.
Returns true if the key was found and its pair removed.
Returns false otherwise. */
extern bool gl_map_remove (gl_map_t map, const void *key);
/* Removes a pair from a map and retrieves the previous value.
Returns true and sets *OLDVALUEP to the previous value, if the key was found
and its pair removed.
Returns false otherwise. */
extern bool gl_map_getremove (gl_map_t map, const void *key,
const void **oldvaluep);
/* Frees an entire map.
(But this call does not free the keys and values of the pairs in the map.
It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
of the pairs in the map.) */
extern void gl_map_free (gl_map_t map);
#endif /* End of inline and gl_xmap.h-defined functions. */
/* ---------------------- gl_map_iterator_t Data Type ---------------------- */
/* Functions for iterating through a map.
Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an
unpredictable order. If you need a predictable order, use GL_LINKEDHASH_MAP
instead of GL_HASH_MAP. */
/* Type of an iterator that traverses a map.
This is a fixed-size struct, so that creation of an iterator doesn't need
memory allocation on the heap. */
typedef struct
{
/* For fast dispatch of gl_map_iterator_next. */
const struct gl_map_implementation *vtable;
/* For detecting whether the last returned pair was removed. */
gl_map_t map;
size_t count;
/* Other, implementation-private fields. */
void *p; void *q;
size_t i; size_t j;
} gl_map_iterator_t;
#if 0 /* These are defined inline below. */
/* Creates an iterator traversing a map.
The map's contents must not be modified while the iterator is in use,
except for modifying the value of the last returned key or removing the
last returned pair. */
extern gl_map_iterator_t gl_map_iterator (gl_map_t map);
/* If there is a next pair, stores the next pair in *KEYP and *VALUEP, advances
the iterator, and returns true. Otherwise, returns false. */
extern bool gl_map_iterator_next (gl_map_iterator_t *iterator,
const void **keyp, const void **valuep);
/* Frees an iterator. */
extern void gl_map_iterator_free (gl_map_iterator_t *iterator);
#endif /* End of inline functions. */
/* ------------------------- Implementation Details ------------------------- */
struct gl_map_implementation
{
/* gl_map_t functions. */
gl_map_t (*nx_create_empty) (gl_map_implementation_t implementation,
gl_mapkey_equals_fn equals_fn,
gl_mapkey_hashcode_fn hashcode_fn,
gl_mapkey_dispose_fn kdispose_fn,
gl_mapvalue_dispose_fn vdispose_fn);
size_t (*size) (gl_map_t map);
bool (*search) (gl_map_t map, const void *key, const void **valuep);
int (*nx_getput) (gl_map_t map, const void *key, const void *value,
const void **oldvaluep);
bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep);
void (*map_free) (gl_map_t map);
/* gl_map_iterator_t functions. */
gl_map_iterator_t (*iterator) (gl_map_t map);
bool (*iterator_next) (gl_map_iterator_t *iterator,
const void **keyp, const void **valuep);
void (*iterator_free) (gl_map_iterator_t *iterator);
};
struct gl_map_impl_base
{
const struct gl_map_implementation *vtable;
gl_mapkey_equals_fn equals_fn;
gl_mapkey_dispose_fn kdispose_fn;
gl_mapvalue_dispose_fn vdispose_fn;
};
/* Define most functions of this file as accesses to the
struct gl_map_implementation. */
GL_MAP_INLINE
/*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
gl_map_t
gl_map_nx_create_empty (gl_map_implementation_t implementation,
gl_mapkey_equals_fn equals_fn,
gl_mapkey_hashcode_fn hashcode_fn,
gl_mapkey_dispose_fn kdispose_fn,
gl_mapvalue_dispose_fn vdispose_fn)
{
return implementation->nx_create_empty (implementation,
equals_fn, hashcode_fn,
kdispose_fn, vdispose_fn);
}
GL_MAP_INLINE size_t
gl_map_size (gl_map_t map)
{
return ((const struct gl_map_impl_base *) map)->vtable->size (map);
}
GL_MAP_INLINE bool
gl_map_search (gl_map_t map, const void *key, const void **valuep)
{
return ((const struct gl_map_impl_base *) map)->vtable
->search (map, key, valuep);
}
_GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
const void **oldvaluep)
{
return ((const struct gl_map_impl_base *) map)->vtable
->nx_getput (map, key, value, oldvaluep);
}
GL_MAP_INLINE bool
gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep)
{
return ((const struct gl_map_impl_base *) map)->vtable
->getremove (map, key, oldvaluep);
}
GL_MAP_INLINE void
gl_map_free (gl_map_t map)
{
((const struct gl_map_impl_base *) map)->vtable->map_free (map);
}
GL_MAP_INLINE gl_map_iterator_t
gl_map_iterator (gl_map_t map)
{
return ((const struct gl_map_impl_base *) map)->vtable->iterator (map);
}
GL_MAP_INLINE bool
gl_map_iterator_next (gl_map_iterator_t *iterator,
const void **keyp, const void **valuep)
{
return iterator->vtable->iterator_next (iterator, keyp, valuep);
}
GL_MAP_INLINE void
gl_map_iterator_free (gl_map_iterator_t *iterator)
{
iterator->vtable->iterator_free (iterator);
}
/* Define the convenience functions, that is, the functions that are independent
of the implementation. */
GL_MAP_INLINE const void *
gl_map_get (gl_map_t map, const void *key)
{
const void *value = NULL;
gl_map_search (map, key, &value);
return value;
}
_GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
gl_map_nx_put (gl_map_t map, const void *key, const void *value)
{
const void *oldvalue;
int result = gl_map_nx_getput (map, key, value, &oldvalue);
if (result == 0)
{
gl_mapvalue_dispose_fn vdispose_fn =
((const struct gl_map_impl_base *) map)->vdispose_fn;
if (vdispose_fn != NULL)
vdispose_fn (oldvalue);
}
return result;
}
GL_MAP_INLINE bool
gl_map_remove (gl_map_t map, const void *key)
{
const void *oldvalue;
bool result = gl_map_getremove (map, key, &oldvalue);
if (result)
{
gl_mapvalue_dispose_fn vdispose_fn =
((const struct gl_map_impl_base *) map)->vdispose_fn;
if (vdispose_fn != NULL)
vdispose_fn (oldvalue);
}
return result;
}
#ifdef __cplusplus
}
#endif
_GL_INLINE_HEADER_END
#endif /* _GL_MAP_H */