diff options
Diffstat (limited to 'libraries/eina/src/include/eina_clist.h')
-rw-r--r-- | libraries/eina/src/include/eina_clist.h | 378 |
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 | */ | ||
109 | typedef 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 | */ | ||
117 | struct _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 | */ | ||
134 | static 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 | */ | ||
147 | static 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 | */ | ||
160 | static 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 | */ | ||
173 | static 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 | */ | ||
188 | static 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 | */ | ||
199 | static 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 | */ | ||
209 | static 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 | */ | ||
220 | static 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 | */ | ||
231 | static 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 | */ | ||
240 | static 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 | */ | ||
249 | static 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 | */ | ||
258 | static 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 | */ | ||
272 | static 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 | */ | ||
281 | static 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 | */ | ||
292 | static 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 | */ | ||
303 | static 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__ */ | ||