libcutils

libcutils/src/linked-list.c
linked-list.c
⎇
Raw
1#include <cutils/linked-list.h>
2#include <cutils/misc.h>
3
4LinkedList* new_ll(bool doubly_linked, bool circularly_linked)
5{
6 LinkedList* ret = malloc(sizeof(*ret));
7 ret->head = NULL;
8 ret->tail = NULL;
9 ret->length = 0;
10 ret->doubly_linked = doubly_linked;
11 ret->circularly_linked = circularly_linked;
12 return ret;
13}
14
15void delete_ll(LinkedList* ll, void(*rmv) (void*))
16{
17 size_t i;
18 SLnode *current, *tmp;
19
20 current = ll->head;
21
22 for(i = 0; i < ll->length; i++)
23 {
24
25 if(rmv)
26 rmv(current->item);
27 tmp = current;
28 current = current->next;
29 free(tmp);
30 }
31 free(ll);
32}
33
34void* llnode_at(const LinkedList* ll, size_t index)
35{
36 size_t i;
37 SLnode* current;
38
39 current = ll->head;
40
41 for(i = 0; i < index; i++)
42 {
43 current = current->next;
44 }
45
46 return current;
47}
48
49
50void* ll_pop_at(LinkedList* ll, size_t index)
51{
52 SLnode* node;
53 void* tmp;
54
55 node = llnode_at(ll ,index);
56
57 tmp = node->item;
58 ll_remove(ll, index, NULL);
59 return tmp;
60}
61
62
63
64bool sll_insert(LinkedList* ll, size_t index, void* item)
65{
66 size_t i;
67 SLnode *current, *prev, *newnode = malloc(sizeof(*newnode));
68
69 if(!newnode)
70 return false;
71
72 newnode->item =item;
73 prev = NULL;
74 current = ll->head;
75
76 for(i = 0; i < index; i++)
77 {
78 prev = current;
79 current = current->next;
80 }
81
82
83 if(index == 0) /*first item*/
84 {
85 ll->head = newnode;
86 if(ll->length == 0) /* only item*/
87 {
88 ll->tail = newnode;
89 if(ll->circularly_linked)
90 newnode->next = newnode;
91 else
92 newnode->next = NULL;
93 } else { /*at least one other item after this*/
94 newnode->next = current;
95 if(ll->circularly_linked)
96 ((SLnode*)ll->tail)->next = ll->head;
97 }
98 } else if(index < ll->length) { /*middle*/
99 prev->next = newnode;
100 newnode->next = current;
101 } else { /*end*/
102 ll->tail = newnode;
103 prev->next = newnode;
104
105 if(ll->circularly_linked)
106 newnode->next = ll->head;
107 else
108 newnode->next = NULL;
109 }
110
111 ll->length++;
112 return true;
113}
114
115bool dll_insert(LinkedList* ll, size_t index, void* item)
116{
117 size_t i;
118 DLnode *current, *prev, *newnode = malloc(sizeof(*newnode));
119
120 if(!newnode)
121 return false;
122
123 newnode->sl.item = item;
124 prev = NULL;
125 current = ll->head;
126
127 for(i = 0; i < index; i++)
128 {
129 prev = current;
130 current = current->sl.next;
131 }
132
133 if(index == 0) /*first item*/
134 {
135 ll->head = newnode;
136 if(ll->length == 0) /* only item*/
137 {
138 ll->tail = newnode;
139 if(ll->circularly_linked)
140 {
141 newnode->prev = newnode;
142 newnode->sl.next = newnode;
143 } else {
144 newnode->prev = NULL;
145 newnode->sl.next = NULL;
146 }
147 } else { /* at least one other item after this*/
148 newnode->sl.next = current;
149 current->prev = newnode;
150 if(ll->circularly_linked)
151 {
152 ((DLnode*)ll->tail)->sl.next = ll->head;
153 newnode->prev = ll->tail;
154 } else {
155 newnode->prev = NULL;
156 }
157 }
158 } else if(index < ll->length) { /*middle*/
159 prev->sl.next = newnode;
160 newnode->prev = prev;
161 newnode->sl.next = current;
162 current->prev = newnode;
163 } else { /*end*/
164 ll->tail = newnode;
165 prev->sl.next = newnode;
166 newnode->prev = prev;
167
168 if(ll->circularly_linked)
169 {
170 newnode->sl.next = ll->head;
171 ((DLnode*)ll->head)->prev = newnode;
172 } else {
173 newnode->sl.next = NULL;
174 }
175 }
176
177 ll->length++;
178 return true;
179}
180
181void sll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
182{
183 size_t i;
184 SLnode *current, *prev;
185
186 prev = NULL;
187 current = ll->head;
188
189 for(i = 0; i < index; i++)
190 {
191 prev = current;
192 current = current->next;
193 }
194
195 if(rmv)
196 rmv(current->item);
197
198 if(index == 0) /*beginning*/
199 {
200 if(ll->length == 1) /*only item*/
201 {
202 ll->head = ll->tail = NULL;
203 } else {
204 ll->head = current->next;
205 if(ll->circularly_linked && ll->tail) ((SLnode*)ll->tail)->next = ll->head;
206 }
207 } else { /*middle or ned*/
208 prev->next = current->next;
209 if(index == ll->length-1) /*at end*/
210 ll->tail = prev;
211 }
212
213 free(current);
214 ll->length--;
215}
216
217void dll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
218{
219 size_t i;
220 DLnode *current, *prev;
221
222 prev = NULL;
223 current = ll->head;
224
225 for(i = 0; i < index; i++)
226 {
227 prev = current;
228 current = current->sl.next;
229 }
230
231 if(rmv)
232 rmv(current->sl.item);
233
234 if(index == 0) /* beginning*/
235 {
236 if(ll->length == 1) /*only item*/
237 {
238 ll->head = ll->tail = NULL;
239 } else {
240 ll->head = current->sl.next;
241 if(ll->circularly_linked && ll->tail)
242 {
243 ((DLnode*)(current->sl.next))->prev = ll->tail;
244 ((DLnode*)ll->tail)->sl.next = ll->head;
245 } else {
246 ((DLnode*)(current->sl.next))->prev = NULL;
247 }
248 }
249 } else { /*middle or end*/
250 prev->sl.next = current->sl.next;
251 if(index == ll->length-1) /*at end*/
252 {
253 ll->tail = prev;
254 if(ll->circularly_linked)
255 ((DLnode*)(ll->head))->prev = ll->tail;
256 }
257 }
258
259 free(current);
260 ll->length--;
261}
262
263
264void sll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
265{
266 size_t i;
267 SLnode *current, *tmp, *prev;
268
269 prev = NULL;
270 current = ll->head;
271
272 for(i = 0; i < index; i++)
273 {
274 prev = current;
275 current = current->next;
276 }
277
278 for(i = 0; i < length; i++)
279 {
280 if(rmv)
281 rmv(current->item);
282 tmp = current->next;
283 free(current);
284 current = tmp;
285 }
286
287 if(index == 0) /* beginning */
288 ll->head = current;
289
290 if(index+length == ll->length) /* removed last item */
291 {
292 if(index == 0)
293 {
294 ll->head = NULL;
295 ll->tail = NULL;
296 } else {
297 ll->tail = prev;
298 if(ll->circularly_linked)
299 {
300 prev->next = ll->head;
301 } else {
302 prev->next = NULL;
303 }
304 }
305 } else {
306 if(index == 0)
307 {
308 ll->head = current;
309 if(ll->circularly_linked) ((SLnode*)(ll->tail))->next = ll->head;
310 } else {
311 prev->next = current;
312 }
313 }
314
315 ll->length -= length;
316}
317
318void dll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
319{
320 size_t i;
321 DLnode *current, *tmp, *prev;
322
323 prev = NULL;
324 current = ll->head;
325
326 for(i = 0; i < index; i++)
327 {
328 prev = current;
329 current = current->sl.next;
330 }
331
332 for(i = 0; i < length; i++)
333 {
334 if(rmv)
335 rmv(current->sl.item);
336 tmp = current->sl.next;
337 free(current);
338 current = tmp;
339 }
340
341 if(index == 0) /* beginning */
342 {
343 ll->head = current;
344 current->prev = ll->circularly_linked ? ll->tail : NULL;
345 }
346
347 if(index+length == ll->length) /* removed last item */
348 {
349 if(index == 0)
350 {
351 ll->head = NULL;
352 ll->tail = NULL;
353 } else {
354 ll->tail = prev;
355 if(ll->circularly_linked)
356 {
357 prev->sl.next = ll->head;
358 ((DLnode*)(ll->head))->prev = ll->tail;
359 } else {
360 prev->sl.next = NULL;
361 }
362 }
363 } else {
364 if(index == 0)
365 {
366 ll->head = current;
367 if(ll->circularly_linked)
368 {
369 ((SLnode*)(ll->tail))->next = ll->head;
370 current->prev = ll->tail;
371 } else {
372 current->prev = NULL;
373 }
374 } else {
375 prev->sl.next = current;
376 current->prev = prev;
377 }
378 }
379
380 ll->length -= length;
381}
382
383
384size_t* ll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*))
385{
386 size_t i, *ret;
387 SLnode* current;
388
389 current = haystack->head;
390
391 for(i = 0; i < haystack->length; i++)
392 {
393 if(cmp(current->item, needle) == 0)
394 {
395 ret = malloc(sizeof(*ret));
396 *ret = i;
397 return ret;
398 }
399 current = current->next;
400 }
401 return NULL;
402}
403
404void sll_swap(LinkedList* ll, size_t item1, size_t item2)
405{
406 size_t i, first_index, second_index;
407 SLnode *first, *second;
408
409 first_index = item1 <= item2 ? item1 : item2;
410 second_index = item1 <= item2 ? item2 : item1;
411
412 first = NULL;
413 second = ll->head;
414
415 for(i = 0; i < second_index; i++)
416 {
417 if(i == first_index)
418 first = second;
419 second = second->next;
420 }
421
422 if(!first)
423 first = second;
424
425 memswap(&first->item, &second->item, sizeof(first->item));
426}
427
428void dll_swap(LinkedList* ll, size_t item1, size_t item2)
429{
430 size_t i, first_index, second_index;
431 DLnode *first, *second;
432
433 first_index = item1 <= item2 ? item1 : item2;
434 second_index = item1 <= item2 ? item2 : item1;
435
436 first = NULL;
437 second = ll->head;
438
439 for(i = 0; i < second_index; i++)
440 {
441 if(i == first_index)
442 first = second;
443 second = second->sl.next;
444 }
445
446 if(!first)
447 first = second;
448
449 memswap(&first->sl.item, &second->sl.item, sizeof(first->sl.item));
450}
451