diff options
Diffstat (limited to 'libraries/eina/src/include/eina_clist.h')
-rw-r--r-- | libraries/eina/src/include/eina_clist.h | 456 |
1 files changed, 456 insertions, 0 deletions
diff --git a/libraries/eina/src/include/eina_clist.h b/libraries/eina/src/include/eina_clist.h new file mode 100644 index 0000000..68f15df --- /dev/null +++ b/libraries/eina/src/include/eina_clist.h | |||
@@ -0,0 +1,456 @@ | |||
1 | /* | ||
2 | * Linked lists support | ||
3 | * | ||
4 | * Copyright (C) 2002 Alexandre Julliard | ||
5 | * Copyright (C) 2011 Mike McCormack (adapted for Eina) | ||
6 | * | ||
7 | * This library is free software; you can redistribute it and/or | ||
8 | * modify it under the terms of the GNU Lesser General Public | ||
9 | * License as published by the Free Software Foundation; either | ||
10 | * version 2.1 of the License, or (at your option) any later version. | ||
11 | * | ||
12 | * This library is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
15 | * Lesser General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU Lesser General Public | ||
18 | * License along with this library; if not, write to the Free Software | ||
19 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA | ||
20 | */ | ||
21 | |||
22 | #ifndef __EINA_CLIST_H__ | ||
23 | #define __EINA_CLIST_H__ | ||
24 | |||
25 | /** | ||
26 | * @addtogroup Eina_CList_Group Compact inline list | ||
27 | * @brief Eina_Clist is a compact (inline) list implementation | ||
28 | * | ||
29 | * Elements of this list are members of the structs stored in the list | ||
30 | * | ||
31 | * Advantages over @ref Eina_List and @ref Eina_Inlist: | ||
32 | * - uses less memory (two machine words per item) | ||
33 | * - allows removing items without knowing which list they're in using O(1) time | ||
34 | * - no need to keep updating the head pointer as the list is changed | ||
35 | * | ||
36 | * Disadvantages: | ||
37 | * - O(N) time to calculate list length | ||
38 | * - requires one list entry in a struct per list (i.e. it's an inlist) | ||
39 | * - requires a head/tail pointer | ||
40 | * - need to know the list head when moving to next or previous pointer | ||
41 | * | ||
42 | * @note There's no NULL at the end of the list, the last item points to the head. | ||
43 | * | ||
44 | * @note List heads must be initialized with EINA_CLIST_INIT or by calling eina_clist_element_init | ||
45 | */ | ||
46 | |||
47 | /* Define a list like so: | ||
48 | * | ||
49 | * @code | ||
50 | * struct gadget | ||
51 | * { | ||
52 | * struct Eina_Clist entry; <-- doesn't have to be the first item in the struct | ||
53 | * int a, b; | ||
54 | * }; | ||
55 | * | ||
56 | * static Eina_Clist global_gadgets = EINA_CLIST_INIT( global_gadgets ); | ||
57 | * @endcode | ||
58 | * | ||
59 | * or | ||
60 | * | ||
61 | * @code | ||
62 | * struct some_global_thing | ||
63 | * { | ||
64 | * Eina_Clist gadgets; | ||
65 | * }; | ||
66 | * | ||
67 | * eina_clist_init( &some_global_thing->gadgets ); | ||
68 | * @endcode | ||
69 | * | ||
70 | * Manipulate it like this: | ||
71 | * | ||
72 | * @code | ||
73 | * eina_clist_add_head( &global_gadgets, &new_gadget->entry ); | ||
74 | * eina_clist_remove( &new_gadget->entry ); | ||
75 | * eina_clist_add_after( &some_random_gadget->entry, &new_gadget->entry ); | ||
76 | * @endcode | ||
77 | * | ||
78 | * And to iterate over it: | ||
79 | * | ||
80 | * @code | ||
81 | * struct gadget *gadget; | ||
82 | * EINA_CLIST_FOR_EACH_ENTRY( gadget, &global_gadgets, struct gadget, entry ) | ||
83 | * { | ||
84 | * ... | ||
85 | * } | ||
86 | * @endcode | ||
87 | * | ||
88 | */ | ||
89 | |||
90 | /** | ||
91 | * @addtogroup Eina_Data_Types_Group Data Types | ||
92 | * | ||
93 | * @{ | ||
94 | */ | ||
95 | |||
96 | /** | ||
97 | * @addtogroup Eina_Containers_Group Containers | ||
98 | * | ||
99 | * @{ | ||
100 | */ | ||
101 | |||
102 | /** | ||
103 | * @defgroup Eina_CList_Group Compact list | ||
104 | * | ||
105 | * @{ | ||
106 | */ | ||
107 | |||
108 | /** | ||
109 | * @typedef Eina_Clist | ||
110 | * This is the list head and the list entry. | ||
111 | * @since 1.1.0 | ||
112 | */ | ||
113 | typedef struct _Eina_Clist Eina_Clist; | ||
114 | |||
115 | /** | ||
116 | * @struct _Eina_Clist | ||
117 | * Compact list type | ||
118 | * @note This structure is used as both the list head and the list entry. | ||
119 | * @since 1.1.0 | ||
120 | */ | ||
121 | struct _Eina_Clist | ||
122 | { | ||
123 | Eina_Clist *next; | ||
124 | Eina_Clist *prev; | ||
125 | }; | ||
126 | |||
127 | /** | ||
128 | * Add an element after the specified one. | ||
129 | * | ||
130 | * @param elem An element in the list | ||
131 | * @param to_add The element to add to the list | ||
132 | * @pre The list head must be initialized once before adding anything. | ||
133 | * @pre The element is not in any list. | ||
134 | * | ||
135 | * @note There's no need to initialize an element before adding it to the list. | ||
136 | * @since 1.1.0 | ||
137 | */ | ||
138 | static inline void eina_clist_add_after(Eina_Clist *elem, Eina_Clist *to_add) | ||
139 | { | ||
140 | to_add->next = elem->next; | ||
141 | to_add->prev = elem; | ||
142 | elem->next->prev = to_add; | ||
143 | elem->next = to_add; | ||
144 | } | ||
145 | |||
146 | /** | ||
147 | * Add an element before the specified one. | ||
148 | * | ||
149 | * @param elem An element in the list | ||
150 | * @param to_add The element to add to the list | ||
151 | * @pre The list head must be initialized once before adding anything. | ||
152 | * @pre The element is not in any list. | ||
153 | * | ||
154 | * @note There's no need to initialize an element before adding it to the list. | ||
155 | * @since 1.1.0 | ||
156 | */ | ||
157 | static inline void eina_clist_add_before(Eina_Clist *elem, Eina_Clist *to_add) | ||
158 | { | ||
159 | to_add->next = elem; | ||
160 | to_add->prev = elem->prev; | ||
161 | elem->prev->next = to_add; | ||
162 | elem->prev = to_add; | ||
163 | } | ||
164 | |||
165 | /** | ||
166 | * Add element at the head of the list. | ||
167 | * | ||
168 | * @param list The list | ||
169 | * @param elem An element | ||
170 | * @pre The list head must be initialized once before adding anything. | ||
171 | * @pre The element is not in any list. | ||
172 | * | ||
173 | * @note There's no need to initialize an element before adding it to the list. | ||
174 | * @since 1.1.0 | ||
175 | */ | ||
176 | static inline void eina_clist_add_head(Eina_Clist *list, Eina_Clist *elem) | ||
177 | { | ||
178 | eina_clist_add_after(list, elem); | ||
179 | } | ||
180 | |||
181 | /** | ||
182 | * Add element at the tail of the list. | ||
183 | * | ||
184 | * @param list The list | ||
185 | * @param elem An element | ||
186 | * @pre The list head must be initialized once before adding anything. | ||
187 | * @pre The element is not in any list. | ||
188 | * | ||
189 | * @note There's no need to initialize an element before adding it to the list. | ||
190 | * @since 1.1.0 | ||
191 | */ | ||
192 | static inline void eina_clist_add_tail(Eina_Clist *list, Eina_Clist *elem) | ||
193 | { | ||
194 | eina_clist_add_before(list, elem); | ||
195 | } | ||
196 | |||
197 | /** | ||
198 | * Init an (unlinked) element. | ||
199 | * | ||
200 | * Call this function on elements that have not been added to the list | ||
201 | * if you want eina_clist_element_init() to work correctly | ||
202 | * | ||
203 | * @param elem An element | ||
204 | * @pre The element is not in any list. | ||
205 | * @post The element is marked as not being in any list | ||
206 | * | ||
207 | * @note It is not necessary to call this before adding an element to this list. | ||
208 | * @since 1.1.0 | ||
209 | */ | ||
210 | static inline void eina_clist_element_init(Eina_Clist *elem) | ||
211 | { | ||
212 | elem->next = NULL; | ||
213 | elem->prev = NULL; | ||
214 | } | ||
215 | |||
216 | /** | ||
217 | * Check if an element is in a list or not. | ||
218 | * | ||
219 | * @param elem An element | ||
220 | * | ||
221 | * @pre Either eina_clist_element_init() has been called on @a elem, | ||
222 | * it has been added to a list or remove from a list. | ||
223 | * @since 1.1.0 | ||
224 | */ | ||
225 | static inline int eina_clist_element_is_linked(Eina_Clist *elem) | ||
226 | { | ||
227 | return (elem->next != NULL && elem->prev != NULL); | ||
228 | } | ||
229 | |||
230 | /** | ||
231 | * Remove an element from its list. | ||
232 | * | ||
233 | * @param elem An element | ||
234 | * @pre The element is in a list already | ||
235 | * @post The element is marked as not being in any list | ||
236 | * @since 1.1.0 | ||
237 | */ | ||
238 | static inline void eina_clist_remove(Eina_Clist *elem) | ||
239 | { | ||
240 | elem->next->prev = elem->prev; | ||
241 | elem->prev->next = elem->next; | ||
242 | eina_clist_element_init(elem); | ||
243 | } | ||
244 | |||
245 | /** | ||
246 | * Get the next element. | ||
247 | * | ||
248 | * @param list The list | ||
249 | * @param elem An element | ||
250 | * @pre @a elem is in @a list | ||
251 | * @return The element after @elem in @list or NULL if @a elem is last in @a list | ||
252 | * @since 1.1.0 | ||
253 | */ | ||
254 | static inline Eina_Clist *eina_clist_next(const Eina_Clist *list, const Eina_Clist *elem) | ||
255 | { | ||
256 | Eina_Clist *ret = elem->next; | ||
257 | if (elem->next == list) ret = NULL; | ||
258 | return ret; | ||
259 | } | ||
260 | |||
261 | /** | ||
262 | * Get the previous element. | ||
263 | * | ||
264 | * @param list The list | ||
265 | * @param elem An element | ||
266 | * | ||
267 | * @return The element before @a elem or NULL if @a elem is the first in the list | ||
268 | * @since 1.1.0 | ||
269 | */ | ||
270 | static inline Eina_Clist *eina_clist_prev(const Eina_Clist *list, const Eina_Clist *elem) | ||
271 | { | ||
272 | Eina_Clist *ret = elem->prev; | ||
273 | if (elem->prev == list) ret = NULL; | ||
274 | return ret; | ||
275 | } | ||
276 | |||
277 | /** | ||
278 | * Get the first element. | ||
279 | * | ||
280 | * @param list The list | ||
281 | * @returns The first element in @a list or NULL if @a list is empty | ||
282 | * @since 1.1.0 | ||
283 | */ | ||
284 | static inline Eina_Clist *eina_clist_head(const Eina_Clist *list) | ||
285 | { | ||
286 | return eina_clist_next(list, list); | ||
287 | } | ||
288 | |||
289 | /** | ||
290 | * Get the last element. | ||
291 | * | ||
292 | * @param list The list | ||
293 | * @returns The last element in @a list or NULL if @list is empty | ||
294 | * @since 1.1.0 | ||
295 | */ | ||
296 | static inline Eina_Clist *eina_clist_tail(const Eina_Clist *list) | ||
297 | { | ||
298 | return eina_clist_prev(list, list); | ||
299 | } | ||
300 | |||
301 | /** | ||
302 | * Check if a list is empty. | ||
303 | * | ||
304 | * @param list The list | ||
305 | * @returns non-zero if @a list is empty, zero if it is not | ||
306 | * @since 1.1.0 | ||
307 | */ | ||
308 | static inline int eina_clist_empty(const Eina_Clist *list) | ||
309 | { | ||
310 | return list->next == list; | ||
311 | } | ||
312 | |||
313 | /** | ||
314 | * Initialize a list | ||
315 | * | ||
316 | * @param list The list | ||
317 | * @pre The list is uninitialized | ||
318 | * @post The list contains no items | ||
319 | * | ||
320 | * @note Don't call this function on a list with items | ||
321 | * @note This function must be called. Don't try do | ||
322 | * initialize the list by zero'ing out the list head. | ||
323 | * @since 1.1.0 | ||
324 | */ | ||
325 | static inline void eina_clist_init(Eina_Clist *list) | ||
326 | { | ||
327 | list->next = list->prev = list; | ||
328 | } | ||
329 | |||
330 | /** | ||
331 | * Count the elements of a list | ||
332 | * | ||
333 | * @param list The list | ||
334 | * @returns The number of items in the list | ||
335 | * @since 1.1.0 | ||
336 | */ | ||
337 | static inline unsigned int eina_clist_count(const Eina_Clist *list) | ||
338 | { | ||
339 | unsigned count = 0; | ||
340 | const Eina_Clist *ptr; | ||
341 | for (ptr = list->next; ptr != list; ptr = ptr->next) count++; | ||
342 | return count; | ||
343 | } | ||
344 | |||
345 | /** | ||
346 | * Move all elements from src to the tail of dst | ||
347 | * | ||
348 | * @param dst List to be appended to | ||
349 | * @param src List to append | ||
350 | * | ||
351 | * @post @a src is initialized but empty after this operation | ||
352 | * @since 1.1.0 | ||
353 | */ | ||
354 | static inline void eina_clist_move_tail(Eina_Clist *dst, Eina_Clist *src) | ||
355 | { | ||
356 | if (eina_clist_empty(src)) return; | ||
357 | |||
358 | dst->prev->next = src->next; | ||
359 | src->next->prev = dst->prev; | ||
360 | dst->prev = src->prev; | ||
361 | src->prev->next = dst; | ||
362 | eina_clist_init(src); | ||
363 | } | ||
364 | |||
365 | /** | ||
366 | * move all elements from src to the head of dst | ||
367 | * | ||
368 | * @param dst List to be prepended to | ||
369 | * @param src List to prepend | ||
370 | * | ||
371 | * @post @a src is initialized but empty after this operation | ||
372 | * @since 1.1.0 | ||
373 | */ | ||
374 | static inline void eina_clist_move_head(Eina_Clist *dst, Eina_Clist *src) | ||
375 | { | ||
376 | if (eina_clist_empty(src)) return; | ||
377 | |||
378 | dst->next->prev = src->prev; | ||
379 | src->prev->next = dst->next; | ||
380 | dst->next = src->next; | ||
381 | src->next->prev = dst; | ||
382 | eina_clist_init(src); | ||
383 | } | ||
384 | |||
385 | /** | ||
386 | * iterate through the list | ||
387 | */ | ||
388 | #define EINA_CLIST_FOR_EACH(cursor,list) \ | ||
389 | for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next) | ||
390 | |||
391 | /* iterate through the list, with safety against removal */ | ||
392 | #define EINA_CLIST_FOR_EACH_SAFE(cursor, cursor2, list) \ | ||
393 | for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \ | ||
394 | (cursor) != (list); \ | ||
395 | (cursor) = (cursor2), (cursor2) = (cursor)->next) | ||
396 | |||
397 | /* iterate through the list using a list entry */ | ||
398 | #define EINA_CLIST_FOR_EACH_ENTRY(elem, list, type, field) \ | ||
399 | for ((elem) = EINA_CLIST_ENTRY((list)->next, type, field); \ | ||
400 | &(elem)->field != (list); \ | ||
401 | (elem) = EINA_CLIST_ENTRY((elem)->field.next, type, field)) | ||
402 | |||
403 | /* iterate through the list using a list entry, with safety against removal */ | ||
404 | #define EINA_CLIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field) \ | ||
405 | for ((cursor) = EINA_CLIST_ENTRY((list)->next, type, field), \ | ||
406 | (cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field); \ | ||
407 | &(cursor)->field != (list); \ | ||
408 | (cursor) = (cursor2), \ | ||
409 | (cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field)) | ||
410 | |||
411 | /* iterate through the list in reverse order */ | ||
412 | #define EINA_CLIST_FOR_EACH_REV(cursor,list) \ | ||
413 | for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev) | ||
414 | |||
415 | /* iterate through the list in reverse order, with safety against removal */ | ||
416 | #define EINA_CLIST_FOR_EACH_SAFE_REV(cursor, cursor2, list) \ | ||
417 | for ((cursor) = (list)->prev, (cursor2) = (cursor)->prev; \ | ||
418 | (cursor) != (list); \ | ||
419 | (cursor) = (cursor2), (cursor2) = (cursor)->prev) | ||
420 | |||
421 | /* iterate through the list in reverse order using a list entry */ | ||
422 | #define EINA_CLIST_FOR_EACH_ENTRY_REV(elem, list, type, field) \ | ||
423 | for ((elem) = EINA_CLIST_ENTRY((list)->prev, type, field); \ | ||
424 | &(elem)->field != (list); \ | ||
425 | (elem) = EINA_CLIST_ENTRY((elem)->field.prev, type, field)) | ||
426 | |||
427 | /* iterate through the list in reverse order using a list entry, with safety against removal */ | ||
428 | #define EINA_CLIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field) \ | ||
429 | for ((cursor) = EINA_CLIST_ENTRY((list)->prev, type, field), \ | ||
430 | (cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field); \ | ||
431 | &(cursor)->field != (list); \ | ||
432 | (cursor) = (cursor2), \ | ||
433 | (cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field)) | ||
434 | |||
435 | /* macros for statically initialized lists */ | ||
436 | #undef EINA_CLIST_INIT | ||
437 | #define EINA_CLIST_INIT(list) { &(list), &(list) } | ||
438 | |||
439 | /* get pointer to object containing list element */ | ||
440 | #undef EINA_CLIST_ENTRY | ||
441 | #define EINA_CLIST_ENTRY(elem, type, field) \ | ||
442 | ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field))) | ||
443 | |||
444 | /* | ||
445 | * @} | ||
446 | */ | ||
447 | |||
448 | /* | ||
449 | * @} | ||
450 | */ | ||
451 | |||
452 | /* | ||
453 | * @} | ||
454 | */ | ||
455 | |||
456 | #endif /* __EINA_CLIST_H__ */ | ||