Mercurial > hg > webserver / file comparison

comparison: src/ucx/cx/list.h

src/ucx/cx/list.h

changeset 415
d938228c382e
child 438
22eca559aded
equal deleted inserted replaced
414:99a34860c105 415:d938228c382e
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * \file list.h
30 * \brief Interface for list implementations.
31 * \author Mike Becker
32 * \author Olaf Wintermann
33 * \version 3.0
34 * \copyright 2-Clause BSD License
35 */
36
37 #ifndef UCX_LIST_H
38 #define UCX_LIST_H
39
40 #include "common.h"
41 #include "allocator.h"
42 #include "iterator.h"
43
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47
48 /**
49 * A comparator function comparing two list elements.
50 */
51 typedef int(*CxListComparator)(
52 void const *left,
53 void const *right
54 );
55
56 /**
57 * List class type.
58 */
59 typedef struct cx_list_class_s cx_list_class;
60
61 /**
62 * Structure for holding the base data of a list.
63 */
64 struct cx_list_s {
65 /**
66 * The list class definition.
67 */
68 cx_list_class *cl;
69 /**
70 * The allocator to use.
71 */
72 CxAllocator const *allocator;
73 /**
74 * The comparator function for the elements.
75 */
76 CxListComparator cmpfunc;
77 /**
78 * The size of each element (payload only).
79 */
80 size_t itemsize;
81 /**
82 * The size of the list (number of currently stored elements).
83 */
84 size_t size;
85 /**
86 * The capacity of the list (maximum number of elements).
87 */
88 size_t capacity;
89 union {
90 /**
91 * An optional simple destructor for the list contents that admits the free() interface.
92 *
93 * @remark Set content_destructor_type to #CX_DESTRUCTOR_SIMPLE.
94 *
95 * @attention Read the documentation of the particular list implementation
96 * whether this destructor shall only destroy the contents or also free the memory.
97 */
98 cx_destructor_func simple_destructor;
99 /**
100 * An optional advanced destructor for the list contents providing additional data.
101 *
102 * @remark Set content_destructor_type to #CX_DESTRUCTOR_ADVANCED.
103 *
104 * @attention Read the documentation of the particular list implementation
105 * whether this destructor shall only destroy the contents or also free the memory.
106 */
107 cx_advanced_destructor advanced_destructor;
108 };
109 /**
110 * The type of destructor to use.
111 */
112 enum cx_destructor_type content_destructor_type;
113 };
114
115 /**
116 * The class definition for arbitrary lists.
117 */
118 struct cx_list_class_s {
119 /**
120 * Destructor function.
121 */
122 void (*destructor)(struct cx_list_s *list);
123
124 /**
125 * Member function for adding an element.
126 */
127 int (*add)(
128 struct cx_list_s *list,
129 void const *elem
130 );
131
132 /**
133 * Member function for inserting an element.
134 */
135 int (*insert)(
136 struct cx_list_s *list,
137 size_t index,
138 void const *elem
139 );
140
141 /**
142 * Member function for inserting an element relative to an iterator position.
143 */
144 int (*insert_iter)(
145 struct cx_iterator_s *iter,
146 void const *elem,
147 int prepend
148 );
149
150 /**
151 * Member function for removing an element.
152 */
153 int (*remove)(
154 struct cx_list_s *list,
155 size_t index
156 );
157
158 /**
159 * Member function for element lookup.
160 */
161 void *(*at)(
162 struct cx_list_s const *list,
163 size_t index
164 );
165
166 /**
167 * Member function for finding an element.
168 */
169 size_t (*find)(
170 struct cx_list_s const *list,
171 void const *elem
172 );
173
174 /**
175 * Member function for sorting the list in place.
176 */
177 void (*sort)(struct cx_list_s *list);
178
179 /**
180 * Member function for comparing this list to another list of the same type.
181 */
182 int (*compare)(
183 struct cx_list_s const *list,
184 struct cx_list_s const *other
185 );
186
187 /**
188 * Member function for reversing the order of the items.
189 */
190 void (*reverse)(struct cx_list_s *list);
191
192 /**
193 * Returns an iterator pointing to the specified index.
194 */
195 struct cx_iterator_s (*iterator)(
196 struct cx_list_s *list,
197 size_t index
198 );
199 };
200
201 /**
202 * Common type for all list implementations.
203 */
204 typedef struct cx_list_s CxList;
205
206 /**
207 * Adds an item to the end of the list.
208 *
209 * @param list the list
210 * @param elem a pointer to the element to add
211 * @return zero on success, non-zero on memory allocation failure
212 */
213 __attribute__((__nonnull__))
214 static inline int cxListAdd(
215 CxList *list,
216 void const *elem
217 ) {
218 return list->cl->add(list, elem);
219 }
220
221 /**
222 * Inserts an item at the specified index.
223 *
224 * If \p index equals the list \c size, this is effectively cxListAdd().
225 *
226 * @param list the list
227 * @param index the index the element shall have
228 * @param elem a pointer to the element to add
229 * @return zero on success, non-zero on memory allocation failure
230 * or when the index is out of bounds
231 * @see cxListInsertAfter()
232 * @see cxListInsertBefore()
233 */
234 __attribute__((__nonnull__))
235 static inline int cxListInsert(
236 CxList *list,
237 size_t index,
238 void const *elem
239 ) {
240 return list->cl->insert(list, index, elem);
241 }
242
243 /**
244 * Inserts an element after the current location of the specified iterator.
245 *
246 * The used iterator remains operational, but all other active iterators should
247 * be considered invalidated.
248 *
249 * If \p iter is not a list iterator, the behavior is undefined.
250 * If \p iter is a past-the-end iterator, the new element gets appended to the list.
251 *
252 * @param iter an iterator
253 * @param elem the element to insert
254 * @return zero on success, non-zero on memory allocation failure
255 * @see cxListInsert()
256 * @see cxListInsertBefore()
257 */
258 __attribute__((__nonnull__))
259 static inline int cxListInsertAfter(
260 CxIterator *iter,
261 void const *elem
262 ) {
263 return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 0);
264 }
265
266 /**
267 * Inserts an element before the current location of the specified iterator.
268 *
269 * The used iterator remains operational, but all other active iterators should
270 * be considered invalidated.
271 *
272 * If \p iter is not a list iterator, the behavior is undefined.
273 * If \p iter is a past-the-end iterator, the new element gets appended to the list.
274 *
275 * @param iter an iterator
276 * @param elem the element to insert
277 * @return zero on success, non-zero on memory allocation failure
278 * @see cxListInsert()
279 * @see cxListInsertAfter()
280 */
281 __attribute__((__nonnull__))
282 static inline int cxListInsertBefore(
283 CxIterator *iter,
284 void const *elem
285 ) {
286 return ((struct cx_list_s *) iter->src_handle)->cl->insert_iter(iter, elem, 1);
287 }
288
289 /**
290 * Removes the element at the specified index.
291 * @param list the list
292 * @param index the index of the element
293 * @return zero on success, non-zero if the index is out of bounds
294 */
295 __attribute__((__nonnull__))
296 static inline int cxListRemove(
297 CxList *list,
298 size_t index
299 ) {
300 return list->cl->remove(list, index);
301 }
302
303 /**
304 * Returns a pointer to the element at the specified index.
305 *
306 * @param list the list
307 * @param index the index of the element
308 * @return a pointer to the element or \c NULL if the index is out of bounds
309 */
310 __attribute__((__nonnull__))
311 static inline void *cxListAt(
312 CxList *list,
313 size_t index
314 ) {
315 return list->cl->at(list, index);
316 }
317
318 /**
319 * Returns an iterator pointing to the item at the specified index.
320 *
321 * The returned iterator is position-aware.
322 *
323 * If the index is out of range, a past-the-end iterator will be returned.
324 *
325 * @param list the list
326 * @param index the index where the iterator shall point at
327 * @return a new iterator
328 */
329 __attribute__((__nonnull__, __warn_unused_result__))
330 static inline CxIterator cxListIterator(
331 CxList *list,
332 size_t index
333 ) {
334 return list->cl->iterator(list, index);
335 }
336
337 /**
338 * Returns an iterator pointing to the first item of the list.
339 *
340 * The returned iterator is position-aware.
341 *
342 * If the list is empty, a past-the-end iterator will be returned.
343 *
344 * @param list the list
345 * @return a new iterator
346 */
347 __attribute__((__nonnull__, __warn_unused_result__))
348 static inline CxIterator cxListBegin(CxList *list) {
349 return list->cl->iterator(list, 0);
350 }
351
352 /**
353 * Returns the index of the first element that equals \p elem.
354 *
355 * Determining equality is performed by the list's comparator function.
356 *
357 * @param list the list
358 * @param elem the element to find
359 * @return the index of the element or \c (size+1) if the element is not found
360 */
361 __attribute__((__nonnull__))
362 static inline size_t cxListFind(
363 CxList *list,
364 void const *elem
365 ) {
366 return list->cl->find(list, elem);
367 }
368
369 /**
370 * Sorts the list in place.
371 *
372 * \remark The underlying sort algorithm is implementation defined.
373 *
374 * @param list the list
375 */
376 __attribute__((__nonnull__))
377 static inline void cxListSort(CxList *list) {
378 list->cl->sort(list);
379 }
380
381 /**
382 * Reverses the order of the items.
383 *
384 * @param list the list
385 */
386 __attribute__((__nonnull__))
387 static inline void cxListReverse(CxList *list) {
388 list->cl->reverse(list);
389 }
390
391 /**
392 * Compares a list to another list of the same type.
393 *
394 * First, the list sizes are compared. If they match, the lists are compared element-wise.
395 *
396 * @param list the list
397 * @param other the list to compare to
398 * @return zero, if both lists are equal element wise, negative if the first list is smaller, zero if the first list is larger
399 */
400 __attribute__((__nonnull__))
401 static inline int cxListCompare(
402 CxList *list,
403 CxList *other
404 ) {
405 return list->cl->compare(list, other);
406 }
407
408 /**
409 * Deallocates the memory of the specified list structure.
410 *
411 * Also calls content a destructor function, depending on the configuration
412 * in CxList.content_destructor_type.
413 *
414 * This function itself is a destructor function for the CxList.
415 *
416 * @param list the list which shall be destroyed
417 */
418 __attribute__((__nonnull__))
419 void cxListDestroy(CxList *list);
420
421 #ifdef __cplusplus
422 } /* extern "C" */
423 #endif
424
425 #endif /* UCX_LIST_H */

Mercurial Repository: webserver

mercurial