summaryrefslogtreecommitdiff
path: root/lib/gl_map.h
blob: f646ce8f5177fb73b7bfc55c2ad6455420c9aee4 (plain)
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
/* Abstract map data type.
   Copyright (C) 2006-2007, 2009-2023 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

#include <stddef.h>

#ifndef _GL_INLINE_HEADER_BEGIN
 #error "Please include config.h first."
#endif
_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 */