1 /*
2 * list.c, list
3 *
4 * Copyright (c) 2009-2010 Wind River Systems, Inc.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18
19 #include <stdlib.h>
20
21 #include <list.h>
22
__list_init(struct list * entry)23 void __list_init(struct list *entry)
24 {
25 if (entry) {
26 entry->prev = NULL;
27 entry->next = NULL;
28 entry->data = NULL;
29 }
30 }
31
__list_alloc(void)32 struct list *__list_alloc(void)
33 {
34 struct list *new;
35
36 new = malloc(sizeof(struct list));
37 __list_init(new);
38
39 return new;
40 }
41
list_alloc(void * data)42 struct list *list_alloc(void *data)
43 {
44 struct list *new;
45
46 new = __list_alloc();
47 if (new)
48 new->data = data;
49
50 return new;
51 }
52
__list_free(struct list * entry)53 void __list_free(struct list *entry)
54 {
55 free(entry);
56 }
57
list_free_all(struct list * list)58 void list_free_all(struct list *list)
59 {
60 struct list *ptr, *tmp;
61
62 list_foreach_safe(list, ptr, tmp) {
63 __list_free(ptr);
64 }
65 }
66
__list_last(struct list * list)67 struct list *__list_last(struct list *list)
68 {
69 if (list)
70 while (list->next)
71 list = list->next;
72
73 return list;
74 }
75
__list_first(struct list * list)76 struct list *__list_first(struct list *list)
77 {
78 if (list)
79 while (list->prev)
80 list = list->prev;
81
82 return list;
83 }
84
__list_entry(struct list * list,int index)85 struct list *__list_entry(struct list *list, int index)
86 {
87 struct list *entry;
88 int i = 0;
89
90 list_foreach(list, entry) {
91 if (i == index)
92 break;
93 i++;
94 }
95
96 return entry;
97 }
98
list_length(struct list * list)99 int list_length(struct list *list)
100 {
101 int length = 0;
102
103 while (list) {
104 list = list->next;
105 length++;
106 }
107
108 return length;
109 }
110
__list_add_before(struct list * entry,struct list * new)111 struct list *__list_add_before(struct list *entry, struct list *new)
112 {
113 struct list *prev;
114
115 if (entry) {
116 prev = entry->prev;
117 if (prev)
118 prev->next = new;
119 new->prev = prev;
120 new->next = entry;
121 entry->prev = new;
122 }
123
124 return new;
125 }
126
__list_add_after(struct list * entry,struct list * new)127 struct list *__list_add_after(struct list *entry, struct list *new)
128 {
129 struct list *next;
130
131 if (entry) {
132 next = entry->next;
133 if (next)
134 next->prev = new;
135 new->next = next;
136 new->prev = entry;
137 entry->next = new;
138
139 return entry;
140 }
141
142 return new;
143 }
144
__list_add_head(struct list * list,struct list * new)145 struct list *__list_add_head(struct list *list, struct list *new)
146 {
147 struct list *first;
148
149 if (list) {
150 first = __list_first(list);
151 __list_add_before(first, new);
152 }
153
154 return new;
155 }
156
__list_add_tail(struct list * list,struct list * new)157 struct list *__list_add_tail(struct list *list, struct list *new)
158 {
159 struct list *last;
160
161 if (list) {
162 last = __list_last(list);
163 __list_add_after(last, new);
164
165 return list;
166 }
167 else
168 return new;
169 }
170
list_add_head(struct list * list,void * data)171 struct list *list_add_head(struct list *list, void *data)
172 {
173 struct list *new;
174
175 new = list_alloc(data);
176 if (!new)
177 return NULL;
178
179 return __list_add_head(list, new);
180 }
181
list_add_tail(struct list * list,void * data)182 struct list *list_add_tail(struct list *list, void *data)
183 {
184 struct list *new;
185
186 new = list_alloc(data);
187 if (!new)
188 return NULL;
189
190 return __list_add_tail(list, new);
191 }
192
__list_remove(struct list * list,struct list * entry)193 struct list *__list_remove(struct list *list, struct list *entry)
194 {
195 struct list *prev, *next;
196
197 if (entry) {
198 prev = entry->prev;
199 next = entry->next;
200
201 if (prev)
202 prev->next = next;
203 else
204 list = next;
205 if (next)
206 next->prev = prev;
207
208 entry->prev = NULL;
209 entry->next = NULL;
210 }
211
212 return list;
213 }
214
__list_delete(struct list * list,struct list * entry)215 struct list *__list_delete(struct list *list,
216 struct list *entry)
217 {
218 list = __list_remove(list, entry);
219 __list_free(entry);
220
221 return list;
222 }
223
list_delete(struct list * list,void * data)224 struct list *list_delete(struct list *list, void *data)
225 {
226 struct list *ptr, *tmp;
227
228 list_foreach_safe(list, ptr, tmp) {
229 if (ptr->data == data) {
230 list = __list_delete(list, ptr);
231 break;
232 }
233 }
234
235 return list;
236 }
237
list_delete_all(struct list * list,void * data)238 struct list *list_delete_all(struct list *list, void *data)
239 {
240 struct list *ptr, *tmp;
241
242 list_foreach_safe(list, ptr, tmp) {
243 if (ptr->data == data)
244 list = __list_delete(list, ptr);
245 }
246
247 return list;
248 }
249
list_find(struct list * list,void * data)250 struct list *list_find(struct list *list, void *data)
251 {
252 struct list *ptr;
253
254 list_foreach(list, ptr) {
255 if (ptr->data == data)
256 break;
257 }
258
259 return ptr;
260 }
261
list_find_reverse(struct list * list,void * data)262 struct list *list_find_reverse(struct list *list, void *data)
263 {
264 struct list *ptr;
265
266 list_foreach_reverse(list, ptr) {
267 if (ptr->data == data)
268 break;
269 }
270
271 return ptr;
272 }
273