summaryrefslogtreecommitdiff
path: root/lib/gl_oset.h
blob: 44e7ef3db8e84e2ba4ec72756f380064f5d5b787 (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
/* Abstract ordered set data type.
   Copyright (C) 2006-2007, 2009-2021 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2006.

   This file is free software: you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation; either version 2.1 of the
   License, or (at your option) any later version.

   This file 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 Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

#ifndef _GL_OSET_H
#define _GL_OSET_H

#include <stdbool.h>
#include <stddef.h>

#ifndef _GL_INLINE_HEADER_BEGIN
 #error "Please include config.h first."
#endif
_GL_INLINE_HEADER_BEGIN
#ifndef GL_OSET_INLINE
# define GL_OSET_INLINE _GL_INLINE
#endif

#ifdef __cplusplus
extern "C" {
#endif


/* gl_oset is an abstract ordered set data type.  It can contain any number
   of objects ('void *' or 'const void *' pointers) in the order of a given
   comparator function.  Duplicates (in the sense of the comparator) are
   forbidden.

   There are several implementations of this ordered set datatype, optimized
   for different operations or for memory.  You can start using the simplest
   ordered set implementation, GL_ARRAY_OSET, 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_oset_create call.

   The implementations are:
     GL_ARRAY_OSET        a growable array
     GL_AVLTREE_OSET      a binary tree (AVL tree)
     GL_RBTREE_OSET       a binary tree (red-black tree)

   The memory consumption is asymptotically the same: O(1) for every object
   in the set.  When looking more closely at the average memory consumed
   for an object, GL_ARRAY_OSET is the most compact representation, and
   GL_AVLTREE_OSET, GL_RBTREE_OSET need more memory.

   The guaranteed average performance of the operations is, for a set of
   n elements:

   Operation                  ARRAY     TREE

   gl_oset_size                O(1)     O(1)
   gl_oset_add                 O(n)   O(log n)
   gl_oset_remove              O(n)   O(log n)
   gl_oset_update              O(n)   O(log n)
   gl_oset_search            O(log n) O(log n)
   gl_oset_search_atleast    O(log n) O(log n)
   gl_oset_iterator            O(1)   O(log n)
   gl_oset_iterator_atleast  O(log n) O(log n)
   gl_oset_iterator_next       O(1)   O(log n)
 */

/* -------------------------- gl_oset_t Data Type -------------------------- */

/* Type of function used to compare two elements.  Same as for qsort().
   NULL denotes pointer comparison.  */
typedef int (*gl_setelement_compar_fn) (const void *elt1, const void *elt2);

#ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED
/* Type of function used to dispose an element once it's removed from a set.
   NULL denotes a no-op.  */
typedef void (*gl_setelement_dispose_fn) (const void *elt);
# define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1
#endif

/* Type of function used to compare an element with a threshold.
   Returns true if the element is greater or equal than the threshold.  */
typedef bool (*gl_setelement_threshold_fn) (const void *elt, const void *threshold);

struct gl_oset_impl;
/* Type representing an entire ordered set.  */
typedef struct gl_oset_impl * gl_oset_t;

struct gl_oset_implementation;
/* Type representing a ordered set datatype implementation.  */
typedef const struct gl_oset_implementation * gl_oset_implementation_t;

#if 0 /* Unless otherwise specified, these are defined inline below.  */

/* Creates an empty set.
   IMPLEMENTATION is one of GL_ARRAY_OSET, GL_AVLTREE_OSET, GL_RBTREE_OSET.
   COMPAR_FN is an element comparison function or NULL.
   DISPOSE_FN is an element disposal function or NULL.  */
/* declared in gl_xoset.h */
extern gl_oset_t gl_oset_create_empty (gl_oset_implementation_t implementation,
                                       gl_setelement_compar_fn compar_fn,
                                       gl_setelement_dispose_fn dispose_fn)
  /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
  _GL_ATTRIBUTE_RETURNS_NONNULL;
/* Likewise.  Returns NULL upon out-of-memory.  */
extern gl_oset_t gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
                                          gl_setelement_compar_fn compar_fn,
                                          gl_setelement_dispose_fn dispose_fn)
  /*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/;

/* Returns the current number of elements in an ordered set.  */
extern size_t gl_oset_size (gl_oset_t set);

/* Searches whether an element is already in the ordered set.
   Returns true if found, or false if not present in the set.  */
extern bool gl_oset_search (gl_oset_t set, const void *elt);

/* Searches the least element in the ordered set that compares greater or equal
   to the given THRESHOLD.  The representation of the THRESHOLD is defined
   by the THRESHOLD_FN.
   Returns true and stores the found element in *ELTP if found, otherwise returns
   false.  */
extern bool gl_oset_search_atleast (gl_oset_t set,
                                    gl_setelement_threshold_fn threshold_fn,
                                    const void *threshold,
                                    const void **eltp);

/* Adds an element to an ordered set.
   Returns true if it was not already in the set and added, false otherwise.  */
/* declared in gl_xoset.h */
extern bool gl_oset_add (gl_oset_t set, const void *elt);

/* Likewise.  Returns -1 upon out-of-memory.  */
_GL_ATTRIBUTE_NODISCARD
extern int gl_oset_nx_add (gl_oset_t set, const void *elt);

/* Removes an element from an ordered set.
   Returns true if it was found and removed.  */
extern bool gl_oset_remove (gl_oset_t set, const void *elt);

/* Invokes ACTION (ELT, ACTION_DATA) and updates the given ordered set if,
   during this invocation, the attributes/properties of the element ELT change
   in a way that influences the comparison function.
   Warning: During the invocation of ACTION, the ordered set is inconsistent
   and must not be accessed!
   Returns 1 if the position of the element in the ordered set has changed as
   a consequence, 0 if the element stayed at the same position, or -1 if it
   collided with another element and was therefore removed.  */
extern int gl_oset_update (gl_oset_t set, const void *elt,
                           void (*action) (const void *elt, void *action_data),
                           void *action_data);

/* Frees an entire ordered set.
   (But this call does not free the elements of the set.  It only invokes
   the DISPOSE_FN on each of the elements of the set.)  */
extern void gl_oset_free (gl_oset_t set);

#endif /* End of inline and gl_xoset.h-defined functions.  */

/* --------------------- gl_oset_iterator_t Data Type --------------------- */

/* Functions for iterating through an ordered set.  */

/* Type of an iterator that traverses an ordered set.
   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_oset_iterator_next.  */
  const struct gl_oset_implementation *vtable;
  /* For detecting whether the last returned element was removed.  */
  gl_oset_t set;
  size_t count;
  /* Other, implementation-private fields.  */
  void *p; void *q;
  size_t i; size_t j;
} gl_oset_iterator_t;

#if 0 /* These are defined inline below.  */

/* Creates an iterator traversing an ordered set.
   The set's contents must not be modified while the iterator is in use,
   except for removing the last returned element.  */
extern gl_oset_iterator_t gl_oset_iterator (gl_oset_t set);

/* Creates an iterator traversing the tail of an ordered set, that comprises
   the elements that compare greater or equal to the given THRESHOLD.  The
   representation of the THRESHOLD is defined by the THRESHOLD_FN.  */
extern gl_oset_iterator_t gl_oset_iterator_atleast (gl_oset_t set,
                                                    gl_setelement_threshold_fn threshold_fn,
                                                    const void *threshold);

/* If there is a next element, stores the next element in *ELTP, advances the
   iterator and returns true.  Otherwise, returns false.  */
extern bool gl_oset_iterator_next (gl_oset_iterator_t *iterator,
                                   const void **eltp);

/* Frees an iterator.  */
extern void gl_oset_iterator_free (gl_oset_iterator_t *iterator);

#endif /* End of inline functions.  */

/* ------------------------ Implementation Details ------------------------ */

struct gl_oset_implementation
{
  /* gl_oset_t functions.  */
  gl_oset_t (*nx_create_empty) (gl_oset_implementation_t implementation,
                                gl_setelement_compar_fn compar_fn,
                                gl_setelement_dispose_fn dispose_fn);
  size_t (*size) (gl_oset_t set);
  bool (*search) (gl_oset_t set, const void *elt);
  bool (*search_atleast) (gl_oset_t set,
                          gl_setelement_threshold_fn threshold_fn,
                          const void *threshold, const void **eltp);
  int (*nx_add) (gl_oset_t set, const void *elt);
  bool (*remove_elt) (gl_oset_t set, const void *elt);
  int (*update) (gl_oset_t set, const void *elt,
                 void (*action) (const void * /*elt*/, void * /*action_data*/),
                 void *action_data);
  void (*oset_free) (gl_oset_t set);
  /* gl_oset_iterator_t functions.  */
  gl_oset_iterator_t (*iterator) (gl_oset_t set);
  gl_oset_iterator_t (*iterator_atleast) (gl_oset_t set,
                                          gl_setelement_threshold_fn threshold_fn,
                                          const void *threshold);
  bool (*iterator_next) (gl_oset_iterator_t *iterator, const void **eltp);
  void (*iterator_free) (gl_oset_iterator_t *iterator);
};

struct gl_oset_impl_base
{
  const struct gl_oset_implementation *vtable;
  gl_setelement_compar_fn compar_fn;
  gl_setelement_dispose_fn dispose_fn;
};

/* Define all functions of this file as accesses to the
   struct gl_oset_implementation.  */

GL_OSET_INLINE
/*_GL_ATTRIBUTE_DEALLOC (gl_oset_free, 1)*/
gl_oset_t
gl_oset_nx_create_empty (gl_oset_implementation_t implementation,
                         gl_setelement_compar_fn compar_fn,
                         gl_setelement_dispose_fn dispose_fn)
{
  return implementation->nx_create_empty (implementation, compar_fn,
                                          dispose_fn);
}

GL_OSET_INLINE size_t
gl_oset_size (gl_oset_t set)
{
  return ((const struct gl_oset_impl_base *) set)->vtable->size (set);
}

GL_OSET_INLINE bool
gl_oset_search (gl_oset_t set, const void *elt)
{
  return ((const struct gl_oset_impl_base *) set)->vtable->search (set, elt);
}

GL_OSET_INLINE bool
gl_oset_search_atleast (gl_oset_t set,
                        gl_setelement_threshold_fn threshold_fn,
                        const void *threshold, const void **eltp)
{
  return ((const struct gl_oset_impl_base *) set)->vtable
         ->search_atleast (set, threshold_fn, threshold, eltp);
}

_GL_ATTRIBUTE_NODISCARD GL_OSET_INLINE int
gl_oset_nx_add (gl_oset_t set, const void *elt)
{
  return ((const struct gl_oset_impl_base *) set)->vtable->nx_add (set, elt);
}

GL_OSET_INLINE bool
gl_oset_remove (gl_oset_t set, const void *elt)
{
  return ((const struct gl_oset_impl_base *) set)->vtable
         ->remove_elt (set, elt);
}

GL_OSET_INLINE int
gl_oset_update (gl_oset_t set, const void *elt,
                void (*action) (const void * /*elt*/, void * /*action_data*/),
                void *action_data)
{
  return ((const struct gl_oset_impl_base *) set)->vtable
         ->update (set, elt, action, action_data);
}

GL_OSET_INLINE void
gl_oset_free (gl_oset_t set)
{
  ((const struct gl_oset_impl_base *) set)->vtable->oset_free (set);
}

GL_OSET_INLINE gl_oset_iterator_t
gl_oset_iterator (gl_oset_t set)
{
  return ((const struct gl_oset_impl_base *) set)->vtable->iterator (set);
}

GL_OSET_INLINE gl_oset_iterator_t
gl_oset_iterator_atleast (gl_oset_t set,
                          gl_setelement_threshold_fn threshold_fn,
                          const void *threshold)
{
  return ((const struct gl_oset_impl_base *) set)->vtable
         ->iterator_atleast (set, threshold_fn, threshold);
}

GL_OSET_INLINE bool
gl_oset_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
{
  return iterator->vtable->iterator_next (iterator, eltp);
}

GL_OSET_INLINE void
gl_oset_iterator_free (gl_oset_iterator_t *iterator)
{
  iterator->vtable->iterator_free (iterator);
}

#ifdef __cplusplus
}
#endif

_GL_INLINE_HEADER_END

#endif /* _GL_OSET_H */