1 /*
2 (c) Copyright 2001-2009 The world wide DirectFB Open Source Community (directfb.org)
3 (c) Copyright 2000-2004 Convergence (integrated media) GmbH
4
5 All rights reserved.
6
7 Written by Denis Oliver Kropp <dok@directfb.org>,
8 Andreas Hundt <andi@fischlustig.de>,
9 Sven Neumann <neo@directfb.org>,
10 Ville Syrjälä <syrjala@sci.fi> and
11 Claudio Ciccani <klan@users.sf.net>.
12
13 This library is free software; you can redistribute it and/or
14 modify it under the terms of the GNU Lesser General Public
15 License as published by the Free Software Foundation; either
16 version 2 of the License, or (at your option) any later version.
17
18 This library is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 Lesser General Public License for more details.
22
23 You should have received a copy of the GNU Lesser General Public
24 License along with this library; if not, write to the
25 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
26 Boston, MA 02111-1307, USA.
27 */
28
29 #ifndef __DIRECT__LIST_H__
30 #define __DIRECT__LIST_H__
31
32 #include <direct/types.h>
33 #include <direct/debug.h>
34
35
36 struct __D_DirectLink {
37 int magic;
38
39 DirectLink *next;
40 DirectLink *prev; /* The 'prev' pointer of the first element always points
41 to the last element of the list, for fast appending ;-) */
42 };
43
44 static __inline__ void
direct_list_prepend(DirectLink ** list,DirectLink * link)45 direct_list_prepend( DirectLink **list, DirectLink *link )
46 {
47 DirectLink *first = *list;
48
49 link->next = first;
50
51 if (first) {
52 D_MAGIC_ASSERT( first, DirectLink );
53
54 link->prev = first->prev;
55
56 first->prev = link;
57 }
58 else
59 link->prev = link;
60
61 *list = link;
62
63 D_MAGIC_SET( link, DirectLink );
64 }
65
66 static __inline__ void
direct_list_append(DirectLink ** list,DirectLink * link)67 direct_list_append( DirectLink **list, DirectLink *link )
68 {
69 DirectLink *first = *list;
70
71 link->next = NULL;
72
73 if (first) {
74 DirectLink *last = first->prev;
75
76 D_MAGIC_ASSERT( first, DirectLink );
77 D_MAGIC_ASSERT( last, DirectLink );
78
79 link->prev = last;
80
81 last->next = first->prev = link;
82 }
83 else
84 *list = link->prev = link;
85
86 D_MAGIC_SET( link, DirectLink );
87 }
88
89 static __inline__ bool
direct_list_contains_element_EXPENSIVE(DirectLink * list,DirectLink * link)90 direct_list_contains_element_EXPENSIVE( DirectLink *list, DirectLink *link )
91 {
92 D_MAGIC_ASSERT_IF( list, DirectLink );
93
94 while (list) {
95 if (list == link)
96 return true;
97
98 list = list->next;
99 }
100
101 return false;
102 }
103
104 static __inline__ int
direct_list_count_elements_EXPENSIVE(DirectLink * list)105 direct_list_count_elements_EXPENSIVE( DirectLink *list )
106 {
107 int count = 0;
108
109 while (list) {
110 D_MAGIC_ASSERT( list, DirectLink );
111
112 count++;
113
114 list = list->next;
115 }
116
117 return count;
118 }
119
120 static __inline__ void
direct_list_remove(DirectLink ** list,DirectLink * link)121 direct_list_remove( DirectLink **list, DirectLink *link )
122 {
123 DirectLink *next;
124 DirectLink *prev;
125
126 D_ASSERT( list != NULL );
127
128 D_ASSERT( direct_list_contains_element_EXPENSIVE( *list, link ) );
129
130 D_MAGIC_ASSERT( *list, DirectLink );
131 D_MAGIC_ASSERT( link, DirectLink );
132
133 next = link->next;
134 prev = link->prev;
135
136 if (next) {
137 D_MAGIC_ASSERT( next, DirectLink );
138
139 next->prev = prev;
140 }
141 else
142 (*list)->prev = prev;
143
144 if (link == *list)
145 *list = next;
146 else {
147 D_MAGIC_ASSERT( prev, DirectLink );
148
149 prev->next = next;
150 }
151
152 link->next = link->prev = NULL;
153
154 D_MAGIC_CLEAR( link );
155 }
156
157 static __inline__ void
direct_list_move_to_front(DirectLink ** list,DirectLink * link)158 direct_list_move_to_front( DirectLink **list, DirectLink *link )
159 {
160 DirectLink *next;
161 DirectLink *prev;
162 DirectLink *first;
163
164 D_ASSERT( list != NULL );
165
166 first = *list;
167
168 D_ASSERT( direct_list_contains_element_EXPENSIVE( first, link ) );
169
170 D_MAGIC_ASSERT( first, DirectLink );
171 D_MAGIC_ASSERT( link, DirectLink );
172
173 if (first == link)
174 return;
175
176 next = link->next;
177 prev = link->prev;
178
179 D_MAGIC_ASSERT_IF( next, DirectLink );
180 D_MAGIC_ASSERT( prev, DirectLink );
181
182 if (next) {
183 next->prev = prev;
184
185 link->prev = first->prev;
186 }
187 else
188 link->prev = prev;
189
190 prev->next = next;
191
192 link->next = first;
193
194 first->prev = link;
195
196 *list = link;
197 }
198
199 #define direct_list_check_link( link ) \
200 ({ \
201 D_MAGIC_ASSERT_IF( link, DirectLink ); \
202 link != NULL; \
203 })
204
205
206 #define direct_list_foreach(elem, list) \
207 for (elem = (__typeof__(elem))(list); \
208 direct_list_check_link( (DirectLink*)(elem) ); \
209 elem = (__typeof__(elem))(((DirectLink*)(elem))->next))
210
211 #define direct_list_foreach_reverse(elem, list) \
212 for (elem = (__typeof__(elem))((list) ? (list)->prev : NULL); \
213 direct_list_check_link( (DirectLink*)(elem) ); \
214 elem = (__typeof__(elem))((((DirectLink*)(elem))->prev->next) ? ((DirectLink*)(elem))->prev : NULL))
215
216 #define direct_list_foreach_safe(elem, temp, list) \
217 for (elem = (__typeof__(elem))(list), temp = ((__typeof__(temp))(elem) ? (__typeof__(temp))(((DirectLink*)(elem))->next) : NULL); \
218 direct_list_check_link( (DirectLink*)(elem) ); \
219 elem = (__typeof__(elem))(temp), temp = ((__typeof__(temp))(elem) ? (__typeof__(temp))(((DirectLink*)(elem))->next) : NULL))
220
221 #endif
222
223