aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/include/eina_clist.h
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/include/eina_clist.h')
-rw-r--r--libraries/eina/src/include/eina_clist.h378
1 files changed, 0 insertions, 378 deletions
diff --git a/libraries/eina/src/include/eina_clist.h b/libraries/eina/src/include/eina_clist.h
deleted file mode 100644
index 096a4b7..0000000
--- a/libraries/eina/src/include/eina_clist.h
+++ /dev/null
@@ -1,378 +0,0 @@
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_Data_Types_Group Data Types
27 *
28 * @{
29 */
30
31/**
32 * @addtogroup Eina_Containers_Group Containers
33 *
34 * @{
35 */
36
37/**
38 * @defgroup Eina_CList_Group Compact List
39 *
40 * @{
41 *
42 * @brief Eina_Clist is a compact (inline) list implementation
43 *
44 * Elements of this list are members of the structs stored in the list
45 *
46 * Advantages over @ref Eina_List and @ref Eina_Inlist:
47 * - uses less memory (two machine words per item)
48 * - allows removing items without knowing which list they're in using O(1) time
49 * - no need to keep updating the head pointer as the list is changed
50 *
51 * Disadvantages:
52 * - O(N) time to calculate list length
53 * - requires one list entry in a struct per list (i.e. it's an inlist)
54 * - requires a head/tail pointer
55 * - need to know the list head when moving to next or previous pointer
56 *
57 * @note There's no NULL at the end of the list, the last item points to the head.
58 *
59 * @note List heads must be initialized with EINA_CLIST_INIT or by calling eina_clist_element_init
60 *
61 * Define a list like so:
62 *
63 * @code
64 * struct gadget
65 * {
66 * struct Eina_Clist entry; <-- doesn't have to be the first item in the struct
67 * int a, b;
68 * };
69 *
70 * static Eina_Clist global_gadgets = EINA_CLIST_INIT( global_gadgets );
71 * @endcode
72 *
73 * or
74 *
75 * @code
76 * struct some_global_thing
77 * {
78 * Eina_Clist gadgets;
79 * };
80 *
81 * eina_clist_init( &some_global_thing->gadgets );
82 * @endcode
83 *
84 * Manipulate it like this:
85 *
86 * @code
87 * eina_clist_add_head( &global_gadgets, &new_gadget->entry );
88 * eina_clist_remove( &new_gadget->entry );
89 * eina_clist_add_after( &some_random_gadget->entry, &new_gadget->entry );
90 * @endcode
91 *
92 * And to iterate over it:
93 *
94 * @code
95 * struct gadget *gadget;
96 * EINA_CLIST_FOR_EACH_ENTRY( gadget, &global_gadgets, struct gadget, entry )
97 * {
98 * ...
99 * }
100 * @endcode
101 *
102 */
103
104/**
105 * @typedef Eina_Clist
106 * This is the list head and the list entry.
107 * @since 1.1.0
108 */
109typedef struct _Eina_Clist Eina_Clist;
110
111/**
112 * @struct _Eina_Clist
113 * Compact list type
114 * @note This structure is used as both the list head and the list entry.
115 * @since 1.1.0
116 */
117struct _Eina_Clist
118{
119 Eina_Clist *next;
120 Eina_Clist *prev;
121};
122
123/**
124 * Add an element after the specified one.
125 *
126 * @param elem An element in the list
127 * @param to_add The element to add to the list
128 * @pre The list head must be initialized once before adding anything.
129 * @pre The element is not in any list.
130 *
131 * @note There's no need to initialize an element before adding it to the list.
132 * @since 1.1.0
133 */
134static inline void eina_clist_add_after(Eina_Clist *elem, Eina_Clist *to_add);
135
136/**
137 * Add an element before the specified one.
138 *
139 * @param elem An element in the list
140 * @param to_add The element to add to the list
141 * @pre The list head must be initialized once before adding anything.
142 * @pre The element is not in any list.
143 *
144 * @note There's no need to initialize an element before adding it to the list.
145 * @since 1.1.0
146 */
147static inline void eina_clist_add_before(Eina_Clist *elem, Eina_Clist *to_add);
148
149/**
150 * Add element at the head of the list.
151 *
152 * @param list The list
153 * @param elem An element
154 * @pre The list head must be initialized once before adding anything.
155 * @pre The element is not in any list.
156 *
157 * @note There's no need to initialize an element before adding it to the list.
158 * @since 1.1.0
159 */
160static inline void eina_clist_add_head(Eina_Clist *list, Eina_Clist *elem);
161
162/**
163 * Add element at the tail of the list.
164 *
165 * @param list The list
166 * @param elem An element
167 * @pre The list head must be initialized once before adding anything.
168 * @pre The element is not in any list.
169 *
170 * @note There's no need to initialize an element before adding it to the list.
171 * @since 1.1.0
172 */
173static inline void eina_clist_add_tail(Eina_Clist *list, Eina_Clist *elem);
174
175/**
176 * Init an (unlinked) element.
177 *
178 * Call this function on elements that have not been added to the list
179 * if you want eina_clist_element_init() to work correctly
180 *
181 * @param elem An element
182 * @pre The element is not in any list.
183 * @post The element is marked as not being in any list
184 *
185 * @note It is not necessary to call this before adding an element to this list.
186 * @since 1.1.0
187 */
188static inline void eina_clist_element_init(Eina_Clist *elem);
189
190/**
191 * Check if an element is in a list or not.
192 *
193 * @param elem An element
194 *
195 * @pre Either eina_clist_element_init() has been called on @a elem,
196 * it has been added to a list or remove from a list.
197 * @since 1.1.0
198 */
199static inline int eina_clist_element_is_linked(Eina_Clist *elem);
200
201/**
202 * Remove an element from its list.
203 *
204 * @param elem An element
205 * @pre The element is in a list already
206 * @post The element is marked as not being in any list
207 * @since 1.1.0
208 */
209static inline void eina_clist_remove(Eina_Clist *elem);
210
211/**
212 * Get the next element.
213 *
214 * @param list The list
215 * @param elem An element
216 * @pre @a elem is in @a list
217 * @return The element after @a elem in @a list or @c NULL if @a elem is last in @a list
218 * @since 1.1.0
219 */
220static inline Eina_Clist *eina_clist_next(const Eina_Clist *list, const Eina_Clist *elem);
221
222/**
223 * Get the previous element.
224 *
225 * @param list The list
226 * @param elem An element
227 *
228 * @return The element before @a elem or NULL if @a elem is the first in the list
229 * @since 1.1.0
230 */
231static inline Eina_Clist *eina_clist_prev(const Eina_Clist *list, const Eina_Clist *elem);
232
233/**
234 * Get the first element.
235 *
236 * @param list The list
237 * @returns The first element in @a list or NULL if @a list is empty
238 * @since 1.1.0
239 */
240static inline Eina_Clist *eina_clist_head(const Eina_Clist *list);
241
242/**
243 * Get the last element.
244 *
245 * @param list The list
246 * @returns The last element in @a list or NULL if @a list is empty
247 * @since 1.1.0
248 */
249static inline Eina_Clist *eina_clist_tail(const Eina_Clist *list);
250
251/**
252 * Check if a list is empty.
253 *
254 * @param list The list
255 * @returns non-zero if @a list is empty, zero if it is not
256 * @since 1.1.0
257 */
258static inline int eina_clist_empty(const Eina_Clist *list);
259
260/**
261 * Initialize a list
262 *
263 * @param list The list
264 * @pre The list is uninitialized
265 * @post The list contains no items
266 *
267 * @note Don't call this function on a list with items
268 * @note This function must be called. Don't try do
269 * initialize the list by zero'ing out the list head.
270 * @since 1.1.0
271 */
272static inline void eina_clist_init(Eina_Clist *list);
273
274/**
275 * Count the elements of a list
276 *
277 * @param list The list
278 * @returns The number of items in the list
279 * @since 1.1.0
280 */
281static inline unsigned int eina_clist_count(const Eina_Clist *list);
282
283/**
284 * Move all elements from src to the tail of dst
285 *
286 * @param dst List to be appended to
287 * @param src List to append
288 *
289 * @post @a src is initialized but empty after this operation
290 * @since 1.1.0
291 */
292static inline void eina_clist_move_tail(Eina_Clist *dst, Eina_Clist *src);
293
294/**
295 * move all elements from src to the head of dst
296 *
297 * @param dst List to be prepended to
298 * @param src List to prepend
299 *
300 * @post @a src is initialized but empty after this operation
301 * @since 1.1.0
302 */
303static inline void eina_clist_move_head(Eina_Clist *dst, Eina_Clist *src);
304
305/**
306 * iterate through the list
307 */
308#define EINA_CLIST_FOR_EACH(cursor,list) \
309 for ((cursor) = (list)->next; (cursor) != (list); (cursor) = (cursor)->next)
310
311/* iterate through the list, with safety against removal */
312#define EINA_CLIST_FOR_EACH_SAFE(cursor, cursor2, list) \
313 for ((cursor) = (list)->next, (cursor2) = (cursor)->next; \
314 (cursor) != (list); \
315 (cursor) = (cursor2), (cursor2) = (cursor)->next)
316
317/* iterate through the list using a list entry */
318#define EINA_CLIST_FOR_EACH_ENTRY(elem, list, type, field) \
319 for ((elem) = EINA_CLIST_ENTRY((list)->next, type, field); \
320 &(elem)->field != (list); \
321 (elem) = EINA_CLIST_ENTRY((elem)->field.next, type, field))
322
323/* iterate through the list using a list entry, with safety against removal */
324#define EINA_CLIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field) \
325 for ((cursor) = EINA_CLIST_ENTRY((list)->next, type, field), \
326 (cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field); \
327 &(cursor)->field != (list); \
328 (cursor) = (cursor2), \
329 (cursor2) = EINA_CLIST_ENTRY((cursor)->field.next, type, field))
330
331/* iterate through the list in reverse order */
332#define EINA_CLIST_FOR_EACH_REV(cursor,list) \
333 for ((cursor) = (list)->prev; (cursor) != (list); (cursor) = (cursor)->prev)
334
335/* iterate through the list in reverse order, with safety against removal */
336#define EINA_CLIST_FOR_EACH_SAFE_REV(cursor, cursor2, list) \
337 for ((cursor) = (list)->prev, (cursor2) = (cursor)->prev; \
338 (cursor) != (list); \
339 (cursor) = (cursor2), (cursor2) = (cursor)->prev)
340
341/* iterate through the list in reverse order using a list entry */
342#define EINA_CLIST_FOR_EACH_ENTRY_REV(elem, list, type, field) \
343 for ((elem) = EINA_CLIST_ENTRY((list)->prev, type, field); \
344 &(elem)->field != (list); \
345 (elem) = EINA_CLIST_ENTRY((elem)->field.prev, type, field))
346
347/* iterate through the list in reverse order using a list entry, with safety against removal */
348#define EINA_CLIST_FOR_EACH_ENTRY_SAFE_REV(cursor, cursor2, list, type, field) \
349 for ((cursor) = EINA_CLIST_ENTRY((list)->prev, type, field), \
350 (cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field); \
351 &(cursor)->field != (list); \
352 (cursor) = (cursor2), \
353 (cursor2) = EINA_CLIST_ENTRY((cursor)->field.prev, type, field))
354
355/* macros for statically initialized lists */
356#undef EINA_CLIST_INIT
357#define EINA_CLIST_INIT(list) { &(list), &(list) }
358
359/* get pointer to object containing list element */
360#undef EINA_CLIST_ENTRY
361#define EINA_CLIST_ENTRY(elem, type, field) \
362 ((type *)((char *)(elem) - (unsigned long)(&((type *)0)->field)))
363
364#include "eina_inline_clist.x"
365
366/**
367 * @}
368 */
369
370/**
371 * @}
372 */
373
374/**
375 * @}
376 */
377
378#endif /* __EINA_CLIST_H__ */