1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2023 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 collection.h
30 * @brief Common definitions for various collection implementations.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_COLLECTION_H
37 #define UCX_COLLECTION_H
38
39 #include "allocator.h"
40 #include "iterator.h"
41 #include "compare.h"
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
47 /**
48 * Special constant used for creating collections that are storing pointers.
49 */
50 #define CX_STORE_POINTERS 0
51
52 /**
53 * Base attributes of a collection.
54 */
55 struct cx_collection_s {
56 /**
57 * The allocator to use.
58 */
59 const CxAllocator *allocator;
60 /**
61 * The comparator function for the elements.
62 */
63 cx_compare_func cmpfunc;
64 /**
65 * The size of each element.
66 */
67 size_t elem_size;
68 /**
69 * The number of currently stored elements.
70 */
71 size_t size;
72 /**
73 * An optional simple destructor for the collection's elements.
74 *
75 * @attention Read the documentation of the particular collection implementation
76 * whether this destructor shall only destroy the contents or also free the memory.
77 */
78 cx_destructor_func simple_destructor;
79 /**
80 * An optional advanced destructor for the collection's elements.
81 *
82 * @attention Read the documentation of the particular collection implementation
83 * whether this destructor shall only destroy the contents or also free the memory.
84 */
85 cx_destructor_func2 advanced_destructor;
86 /**
87 * The pointer to additional data that is passed to the advanced destructor.
88 */
89 void *destructor_data;
90 /**
91 * Indicates if this list is supposed to store pointers
92 * instead of copies of the actual objects.
93 */
94 bool store_pointer;
95 /**
96 * Indicates if this collection is guaranteed to be sorted.
97 * Note that the elements can still be sorted, even when the collection is not aware of that.
98 */
99 bool sorted;
100 };
101
102 /**
103 * Use this macro to declare common members for a collection structure.
104 *
105 * @par Example Use
106 * @code
107 * struct MyCustomSet {
108 * CX_COLLECTION_BASE;
109 * MySetElements *data;
110 * }
111 * @endcode
112 */
113 #define CX_COLLECTION_BASE struct cx_collection_s collection
114
115 /**
116 * Returns the number of elements currently stored.
117 *
118 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
119 * @return (@c size_t) the number of currently stored elements
120 */
121 #define cxCollectionSize(c) ((c)->collection.size)
122
123 /**
124 * Returns the size of one element.
125 *
126 * If #cxCollectionStoresPointers() returns true, this is the size of a pointer.
127 *
128 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
129 * @return (@c size_t) the size of one element in bytes
130 */
131 #define cxCollectionElementSize(c) ((c)->collection.elem_size)
132
133 /**
134 * Indicates whether this collection only stores pointers instead of the actual data.
135 *
136 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
137 * @retval true if this collection stores only pointers to data
138 * @retval false if this collection stores the actual element's data
139 */
140 #define cxCollectionStoresPointers(c) ((c)->collection.store_pointer)
141
142 /**
143 * Indicates whether the collection can guarantee that the stored elements are currently sorted.
144 *
145 * This may return @c false even when the elements are sorted.
146 * It is totally up to the implementation of the collection when to check if the elements are sorted.
147 * It is usually a good practice to establish this property as an invariant that does not need
148 * to be re-checked on certain operations.
149 *
150 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
151 * @retval true if the elements are currently sorted wrt. the collection's compare function
152 * @retval false if the order of elements is unknown
153 */
154 #define cxCollectionSorted(c) ((c)->collection.sorted || (c)->collection.size == 0)
155
156 /**
157 * Sets the compare function for a collection.
158 *
159 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
160 * @param func (@c cx_compare_func) the compare function that shall be used by @c c
161 */
162 #define cxCollectionCompareFunc(c, func) (c)->collection.cmpfunc = (func)
163
164 /**
165 * Sets a simple destructor function for this collection.
166 *
167 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
168 * @param destr the destructor function
169 */
170 #define cxDefineDestructor(c, destr) \
171 (c)->collection.simple_destructor = (cx_destructor_func) destr
172
173 /**
174 * Sets a simple destructor function for this collection.
175 *
176 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
177 * @param destr the destructor function
178 */
179 #define cxDefineAdvancedDestructor(c, destr, data) \
180 (c)->collection.advanced_destructor = (cx_destructor_func2) destr; \
181 (c)->collection.destructor_data = data
182
183 /**
184 * Invokes the simple destructor function for a specific element.
185 *
186 * Usually only used by collection implementations. There should be no need
187 * to invoke this macro manually.
188 *
189 * When the collection stores pointers, those pointers are directly passed
190 * to the destructor. Otherwise, a pointer to the element is passed.
191 *
192 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
193 * @param e the element (the type is @c void* or @c void** depending on context)
194 */
195 #define cx_invoke_simple_destructor(c, e) \
196 (c)->collection.simple_destructor((c)->collection.store_pointer ? (*((void **) (e))) : (e))
197
198 /**
199 * Invokes the advanced destructor function for a specific element.
200 *
201 * Usually only used by collection implementations. There should be no need
202 * to invoke this macro manually.
203 *
204 * When the collection stores pointers, those pointers are directly passed
205 * to the destructor. Otherwise, a pointer to the element is passed.
206 *
207 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
208 * @param e the element (the type is @c void* or @c void** depending on context)
209 */
210 #define cx_invoke_advanced_destructor(c, e) \
211 (c)->collection.advanced_destructor((c)->collection.destructor_data, \
212 (c)->collection.store_pointer ? (*((void **) (e))) : (e))
213
214
215 /**
216 * Invokes all available destructor functions for a specific element.
217 *
218 * Usually only used by collection implementations. There should be no need
219 * to invoke this macro manually.
220 *
221 * When the collection stores pointers, those pointers are directly passed
222 * to the destructor. Otherwise, a pointer to the element is passed.
223 *
224 * @param c a pointer to a struct that contains #CX_COLLECTION_BASE
225 * @param e the element (the type is @c void* or @c void** depending on context)
226 */
227 #define cx_invoke_destructor(c, e) \
228 if ((c)->collection.simple_destructor) cx_invoke_simple_destructor(c,e); \
229 if ((c)->collection.advanced_destructor) cx_invoke_advanced_destructor(c,e)
230
231 #ifdef __cplusplus
232 } // extern "C"
233 #endif
234
235 #endif // UCX_COLLECTION_H
236