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_t doubly_linked, bool_t 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_sll(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 }
32}
33
34void delete_dll(LinkedList* ll, void(*rmv) (void*))
35{
36 size_t i;
37 DLnode *current, *tmp;
38
39 current = ll->head;
40
41 for(i = 0; i < ll->length; i++)
42 {
43
44 if(rmv)
45 rmv(current->item);
46 tmp = current;
47 current = current->next;
48 free(tmp);
49
50 }
51}
52
53void* sll_at(const LinkedList* ll, size_t index)
54{
55 size_t i;
56 SLnode* current;
57
58 current = ll->head;
59
60 for(i = 0; i < index; i++)
61 {
62 current = current->next;
63 }
64
65 return current->item;
66}
67
68void* dll_at(const LinkedList* ll, size_t index)
69{
70 size_t i;
71 DLnode* current;
72
73 current = ll->head;
74
75 for(i = 0; i < index; i++)
76 {
77 current = current->next;
78 }
79
80 return current->item;
81}
82
83void* sll_pop_at(LinkedList* ll, size_t index)
84{
85 size_t i;
86 SLnode* current;
87 void* tmp;
88
89 current = ll->head;
90
91 for(i = 0; i < index; i++)
92 {
93 current = current->next;
94 }
95
96 tmp = current->item;
97 ll_remove(ll, index, NULL);
98 return tmp;
99}
100
101void* dll_pop_at(LinkedList* ll, size_t index)
102{
103 size_t i;
104 DLnode* current;
105 void* tmp;
106
107 current = ll->head;
108
109 for(i = 0; i < index; i++)
110 {
111 current = current->next;
112 }
113
114 tmp = current->item;
115 ll_remove(ll, index, NULL);
116 return tmp;
117}
118
119bool_t sll_insert(LinkedList* ll, size_t index, void* item)
120{
121 size_t i;
122 SLnode *current, *prev, *newnode = malloc(sizeof(*newnode));
123
124 if(!newnode)
125 return b_false;
126
127 newnode->item =item;
128 prev = NULL;
129 current = ll->head;
130
131 for(i = 0; i < index; i++)
132 {
133 prev = current;
134 current = current->next;
135 }
136
137 if(current)
138 {
139 newnode->next = current;
140 if(prev)
141 prev->next = newnode;
142 else
143 ll->head = newnode;
144 } else {
145 ll->tail = newnode;
146 if(index == 0)
147 ll->head = newnode;
148 newnode->next = NULL;
149 }
150
151 ll->length++;
152 return b_true;
153}
154
155bool_t dll_insert(LinkedList* ll, size_t index, void* item)
156{
157 size_t i;
158 DLnode *current, *newnode = malloc(sizeof(*newnode));
159
160 if(!newnode)
161 return b_false;
162
163 newnode->item =item;
164 current = ll->head;
165
166 for(i = 0; i < index; i++)
167 {
168 current = current->next;
169 }
170
171 if(current)
172 {
173 newnode->next = current;
174 if(current->prev)
175 {
176 current->prev->next = newnode;
177 newnode->prev =current;
178 } else {
179 ll->head = newnode;
180 newnode->prev = NULL;
181 }
182 } else {
183 ll->tail = newnode;
184 if(index == 0)
185 ll->head = newnode;
186 newnode->next = NULL;
187 newnode->prev = NULL;
188 }
189
190 ll->length++;
191 return b_true;
192}
193
194void sll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
195{
196 size_t i;
197 SLnode *current, *prev;
198
199 prev = NULL;
200 current = ll->head;
201
202 for(i = 0; i < index; i++)
203 {
204 prev = current;
205 current = current->next;
206 }
207
208 if(rmv)
209 rmv(current->item);
210
211 prev->next = current->next;
212 free(current);
213}
214
215void dll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
216{
217 size_t i;
218 DLnode* current;
219
220 current = ll->head;
221
222 for(i = 0; i < index; i++)
223 {
224 current = current->next;
225 }
226
227 if(rmv)
228 rmv(current->item);
229
230 current->prev->next = current->next;
231 current->next->prev = current->prev;
232 free(current);
233}
234
235void sll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
236{
237 size_t i;
238 SLnode *current, *tmp, *prev;
239
240 prev = NULL;
241 current = ll->head;
242
243 for(i = 0; i < index; i++)
244 {
245 prev = current;
246 current = current->next;
247 }
248
249 for(i = 0; i < length; i++)
250 {
251 if(rmv)
252 rmv(current->item);
253 tmp = current;
254 free(current);
255 current = tmp->next;
256 }
257
258 prev->next = current;
259}
260
261void dll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
262{
263 size_t i;
264 DLnode *current, *prev;
265
266 prev = NULL;
267 current = ll->head;
268
269 for(i = 0; i < index; i++)
270 {
271 prev = current;
272 current = current->next;
273 }
274
275 for(i = 0; i < length; i++)
276 {
277 if(rmv)
278 rmv(current->item);
279 current = current->next;
280 free(current->prev);
281 }
282
283 prev->next = current;
284 current->prev = prev;
285}
286
287size_t* sll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*))
288{
289 size_t i, *ret;
290 SLnode* current;
291
292 current = haystack->head;
293
294 for(i = 0; i < haystack->length; i++)
295 {
296 if(cmp(current->item, needle) == 0)
297 {
298 ret = malloc(sizeof(*ret));
299 *ret = i;
300 return ret;
301 }
302 current = current->next;
303 }
304 return NULL;
305}
306
307size_t* dll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*))
308{
309 size_t i, *ret;
310 DLnode* current;
311
312 current = haystack->head;
313
314 for(i = 0; i < haystack->length; i++)
315 {
316 if(cmp(current->item, needle) == 0)
317 {
318 ret = malloc(sizeof(*ret));
319 *ret = i;
320 return ret;
321 }
322 current = current->next;
323 }
324 return NULL;
325}
326
327void sll_swap(LinkedList* ll, size_t item1, size_t item2)
328{
329 size_t i, first_index, second_index;
330 SLnode *first, *second;
331
332 first_index = item1 <= item2 ? item1 : item2;
333 second_index = item1 <= item2 ? item2 : item1;
334
335 first = NULL;
336 second = ll->head;
337
338 for(i = 0; i < second_index; i++)
339 {
340 if(i == first_index)
341 first = second->next;
342 second = second->next;
343 }
344
345 if(!first)
346 first = second;
347
348 memswap(&first->item, &second->item, sizeof(first->item));
349}
350
351void dll_swap(LinkedList* ll, size_t item1, size_t item2)
352{
353 size_t i, first_index, second_index;
354 DLnode *first, *second;
355
356 first_index = item1 <= item2 ? item1 : item2;
357 second_index = item1 <= item2 ? item2 : item1;
358
359 first = NULL;
360 second = ll->head;
361
362 for(i = 0; i < second_index; i++)
363 {
364 if(i == first_index)
365 first = second->next;
366 second = second->next;
367 }
368
369 if(!first)
370 first = second;
371
372 memswap(&first->item, &second->item, sizeof(first->item));
373}
374