|
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 map.h |
|
30 * \brief Interface for map implementations. |
|
31 * \author Mike Becker |
|
32 * \author Olaf Wintermann |
|
33 * \version 3.0 |
|
34 * \copyright 2-Clause BSD License |
|
35 */ |
|
36 |
|
37 #ifndef UCX_MAP_H |
|
38 #define UCX_MAP_H |
|
39 |
|
40 #include "common.h" |
|
41 #include "allocator.h" |
|
42 #include "iterator.h" |
|
43 #include "hash_key.h" |
|
44 |
|
45 #ifdef __cplusplus |
|
46 extern "C" { |
|
47 #endif |
|
48 |
|
49 /** Type for the UCX map. */ |
|
50 typedef struct cx_map_s CxMap; |
|
51 |
|
52 /** Type for a map entry. */ |
|
53 typedef struct cx_map_entry_s CxMapEntry; |
|
54 |
|
55 /** Type for map class definitions. */ |
|
56 typedef struct cx_map_class_s cx_map_class; |
|
57 |
|
58 /** Structure for the UCX map. */ |
|
59 struct cx_map_s { |
|
60 /** The map class definition. */ |
|
61 cx_map_class *cl; |
|
62 /** An allocator that is used for the map elements. */ |
|
63 CxAllocator *allocator; |
|
64 /** The number of elements currently stored. */ |
|
65 size_t size; |
|
66 // TODO: elemsize + a flag if values shall be copied to the map |
|
67 }; |
|
68 |
|
69 /** |
|
70 * The class definition for arbitrary maps. |
|
71 */ |
|
72 struct cx_map_class_s { |
|
73 /** |
|
74 * Deallocates the entire memory. |
|
75 */ |
|
76 __attribute__((__nonnull__)) |
|
77 void (*destructor)(struct cx_map_s *map); |
|
78 |
|
79 /** |
|
80 * Removes all elements. |
|
81 */ |
|
82 __attribute__((__nonnull__)) |
|
83 void (*clear)(struct cx_map_s *map); |
|
84 |
|
85 /** |
|
86 * Add or overwrite an element. |
|
87 */ |
|
88 __attribute__((__nonnull__)) |
|
89 int (*put)( |
|
90 CxMap *map, |
|
91 CxHashKey key, |
|
92 void *value |
|
93 ); |
|
94 |
|
95 /** |
|
96 * Returns an element. |
|
97 */ |
|
98 __attribute__((__nonnull__, __warn_unused_result__)) |
|
99 void *(*get)( |
|
100 CxMap const *map, |
|
101 CxHashKey key |
|
102 ); |
|
103 |
|
104 /** |
|
105 * Removes an element. |
|
106 */ |
|
107 __attribute__((__nonnull__, __warn_unused_result__)) |
|
108 void *(*remove)( |
|
109 CxMap *map, |
|
110 CxHashKey key |
|
111 ); |
|
112 |
|
113 /** |
|
114 * Iterator over the key/value pairs. |
|
115 */ |
|
116 __attribute__((__nonnull__, __warn_unused_result__)) |
|
117 CxIterator (*iterator)(CxMap *map); |
|
118 |
|
119 /** |
|
120 * Iterator over the keys. |
|
121 */ |
|
122 __attribute__((__nonnull__, __warn_unused_result__)) |
|
123 CxIterator (*iterator_keys)(CxMap *map); |
|
124 |
|
125 /** |
|
126 * Iterator over the values. |
|
127 */ |
|
128 __attribute__((__nonnull__, __warn_unused_result__)) |
|
129 CxIterator (*iterator_values)(CxMap *map); |
|
130 }; |
|
131 |
|
132 /** |
|
133 * A map entry. |
|
134 */ |
|
135 struct cx_map_entry_s { |
|
136 /** |
|
137 * A pointer to the key. |
|
138 */ |
|
139 CxHashKey const *key; |
|
140 /** |
|
141 * A pointer to the value. |
|
142 */ |
|
143 void *value; |
|
144 }; |
|
145 |
|
146 |
|
147 /** |
|
148 * Deallocates the memory of the specified map. |
|
149 * |
|
150 * @param map the map to be destroyed |
|
151 */ |
|
152 __attribute__((__nonnull__)) |
|
153 static inline void cxMapDestroy(CxMap *map) { |
|
154 // TODO: likely to add auto-free feature for contents in the future |
|
155 map->cl->destructor(map); |
|
156 } |
|
157 |
|
158 |
|
159 /** |
|
160 * Clears a map by removing all elements. |
|
161 * |
|
162 * @param map the map to be cleared |
|
163 */ |
|
164 __attribute__((__nonnull__)) |
|
165 static inline void cxMapClear(CxMap *map) { |
|
166 map->cl->clear(map); |
|
167 } |
|
168 |
|
169 /** |
|
170 * Puts a key/value-pair into the map. |
|
171 * |
|
172 * @param map the map |
|
173 * @param key the key |
|
174 * @param value the value |
|
175 * @return 0 on success, non-zero value on failure |
|
176 */ |
|
177 __attribute__((__nonnull__)) |
|
178 static inline int cxMapPut( |
|
179 CxMap *map, |
|
180 CxHashKey key, |
|
181 void *value |
|
182 ) { |
|
183 return map->cl->put(map, key, value); |
|
184 } |
|
185 |
|
186 /** |
|
187 * Retrieves a value by using a key. |
|
188 * |
|
189 * @param map the map |
|
190 * @param key the key |
|
191 * @return the value |
|
192 */ |
|
193 __attribute__((__nonnull__, __warn_unused_result__)) |
|
194 static inline void *cxMapGet( |
|
195 CxMap const *map, |
|
196 CxHashKey key |
|
197 ) { |
|
198 return map->cl->get(map, key); |
|
199 } |
|
200 |
|
201 /** |
|
202 * Removes a key/value-pair from the map by using the key. |
|
203 * |
|
204 * @param map the map |
|
205 * @param key the key |
|
206 * @return the removed value |
|
207 */ |
|
208 __attribute__((__nonnull__, __warn_unused_result__)) |
|
209 static inline void *cxMapRemove( |
|
210 CxMap *map, |
|
211 CxHashKey key |
|
212 ) { |
|
213 return map->cl->remove(map, key); |
|
214 } |
|
215 |
|
216 // TODO: set-like map operations (union, intersect, difference) |
|
217 |
|
218 /** |
|
219 * Creates a value iterator for a map. |
|
220 * |
|
221 * \note An iterator iterates over all elements successively. Therefore the order |
|
222 * highly depends on the map implementation and may change arbitrarily when the contents change. |
|
223 * |
|
224 * @param map the map to create the iterator for |
|
225 * @return an iterator for the currently stored values |
|
226 */ |
|
227 __attribute__((__nonnull__, __warn_unused_result__)) |
|
228 static inline CxIterator cxMapIteratorValues(CxMap *map) { |
|
229 return map->cl->iterator_values(map); |
|
230 } |
|
231 |
|
232 /** |
|
233 * Creates a key iterator for a map. |
|
234 * |
|
235 * The elements of the iterator are keys of type CxHashKey. |
|
236 * |
|
237 * \note An iterator iterates over all elements successively. Therefore the order |
|
238 * highly depends on the map implementation and may change arbitrarily when the contents change. |
|
239 * |
|
240 * @param map the map to create the iterator for |
|
241 * @return an iterator for the currently stored keys |
|
242 */ |
|
243 __attribute__((__nonnull__, __warn_unused_result__)) |
|
244 static inline CxIterator cxMapIteratorKeys(CxMap *map) { |
|
245 return map->cl->iterator_keys(map); |
|
246 } |
|
247 |
|
248 /** |
|
249 * Creates an iterator for a map. |
|
250 * |
|
251 * The elements of the iterator are key/value pairs of type CxMapEntry. |
|
252 * |
|
253 * \note An iterator iterates over all elements successively. Therefore the order |
|
254 * highly depends on the map implementation and may change arbitrarily when the contents change. |
|
255 * |
|
256 * @param map the map to create the iterator for |
|
257 * @return an iterator for the currently stored entries |
|
258 * @see cxMapIteratorKeys() |
|
259 * @see cxMapIteratorValues() |
|
260 */ |
|
261 __attribute__((__nonnull__, __warn_unused_result__)) |
|
262 static inline CxIterator cxMapIterator(CxMap *map) { |
|
263 return map->cl->iterator(map); |
|
264 } |
|
265 |
|
266 #ifdef __cplusplus |
|
267 } |
|
268 #endif |
|
269 |
|
270 #endif // UCX_MAP_H |