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 if(current)
83 {
84 newnode->next = current;
85 if(index == 0)
86 ll->head = newnode;
87 else
88 prev->next = newnode;
89 } else {
90 ll->tail = newnode;
91 newnode->next = NULL;
92 if(index == 0)
93 ll->head = newnode;
94 if(prev)
95 prev->next = newnode;
96 }
97
98 ll->length++;
99 return true;
100}
101
102bool dll_insert(LinkedList* ll, size_t index, void* item)
103{
104 size_t i;
105 DLnode *current, *prev, *newnode = malloc(sizeof(*newnode));
106
107 if(!newnode)
108 return false;
109
110 newnode->sl.item = item;
111 prev = NULL;
112 current = ll->head;
113
114 for(i = 0; i < index; i++)
115 {
116 prev = current;
117 current = current->sl.next;
118 }
119
120 if(current)
121 {
122 newnode->sl.next = current;
123 if(index == 0)
124 {
125 ll->head = newnode;
126 newnode->prev = NULL;
127 } else {
128 prev->sl.next = newnode;
129 newnode->prev = prev;
130 }
131 current->prev = newnode;
132 } else {
133 ll->tail = newnode;
134 newnode->sl.next = NULL;
135 if(index == 0)
136 {
137 ll->head = newnode;
138 newnode->prev = NULL;
139 }
140 if(prev)
141 {
142 prev->sl.next = newnode;
143 newnode->prev = prev;
144 }
145
146 }
147
148 ll->length++;
149 return true;
150}
151
152
153
154void sll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
155{
156 size_t i;
157 SLnode *current, *prev;
158
159 prev = NULL;
160 current = ll->head;
161
162 for(i = 0; i < index; i++)
163 {
164 prev = current;
165 current = current->next;
166 }
167
168 if(rmv)
169 rmv(current->item);
170
171 if(!current->next)
172 ll->tail = prev;
173
174 if(prev)
175 prev->next = current->next;
176 else
177 ll->head = current->next;
178
179 free(current);
180 ll->length--;
181}
182
183void dll_remove(LinkedList* ll, size_t index, void (*rmv)(void*))
184{
185 size_t i;
186 DLnode *current, *prev;
187
188 prev = NULL;
189 current = ll->head;
190
191 for(i = 0; i < index; i++)
192 {
193 prev = current;
194 current = current->sl.next;
195 }
196
197 if(rmv)
198 rmv(current->sl.item);
199
200 if(current->sl.next)
201 ((DLnode*)(current->sl.next))->prev = prev;
202 else
203 ll->tail = prev;
204
205 if(prev)
206 prev->sl.next = current->sl.next;
207 else
208 ll->head = current->sl.next;
209
210 free(current);
211 ll->length--;
212}
213
214
215void sll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
216{
217 size_t i;
218 SLnode *current, *tmp, *prev;
219
220 prev = NULL;
221 current = ll->head;
222
223 for(i = 0; i < index; i++)
224 {
225 prev = current;
226 current = current->next;
227 }
228
229 for(i = 0; i < length; i++)
230 {
231 if(rmv)
232 rmv(current->item);
233 tmp = current->next;
234 free(current);
235 current = tmp;
236 }
237
238 if(!current)
239 ll->tail = prev;
240
241 if(prev)
242 prev->next = current;
243 else
244 ll->head = current;
245 ll->length -= length;
246}
247
248void dll_remove_range(LinkedList* ll, size_t index, size_t length, void (*rmv)(void*))
249{
250 size_t i;
251 DLnode *current, *tmp, *prev;
252
253 prev = NULL;
254 current = ll->head;
255
256 for(i = 0; i < index; i++)
257 {
258 prev = current;
259 current = current->sl.next;
260 }
261
262 for(i = 0; i < length; i++)
263 {
264 if(rmv)
265 rmv(current->sl.item);
266 tmp = current->sl.next;
267 free(current);
268 current = tmp;
269 }
270 if(current)
271 current->prev = prev;
272 else
273 ll->tail = prev;
274
275 if(prev)
276 {
277 prev->sl.next = current;
278 } else {
279 ll->head = current;
280 }
281 ll->length -= length;
282}
283
284
285size_t* ll_find(const LinkedList* haystack, const void* needle, int (*cmp)(const void*, const void*))
286{
287 size_t i, *ret;
288 SLnode* current;
289
290 current = haystack->head;
291
292 for(i = 0; i < haystack->length; i++)
293 {
294 if(cmp(current->item, needle) == 0)
295 {
296 ret = malloc(sizeof(*ret));
297 *ret = i;
298 return ret;
299 }
300 current = current->next;
301 }
302 return NULL;
303}
304
305void sll_swap(LinkedList* ll, size_t item1, size_t item2)
306{
307 size_t i, first_index, second_index;
308 SLnode *first, *second;
309
310 first_index = item1 <= item2 ? item1 : item2;
311 second_index = item1 <= item2 ? item2 : item1;
312
313 first = NULL;
314 second = ll->head;
315
316 for(i = 0; i < second_index; i++)
317 {
318 if(i == first_index)
319 first = second;
320 second = second->next;
321 }
322
323 if(!first)
324 first = second;
325
326 memswap(&first->item, &second->item, sizeof(first->item));
327}
328
329void dll_swap(LinkedList* ll, size_t item1, size_t item2)
330{
331 size_t i, first_index, second_index;
332 DLnode *first, *second;
333
334 first_index = item1 <= item2 ? item1 : item2;
335 second_index = item1 <= item2 ? item2 : item1;
336
337 first = NULL;
338 second = ll->head;
339
340 for(i = 0; i < second_index; i++)
341 {
342 if(i == first_index)
343 first = second;
344 second = second->sl.next;
345 }
346
347 if(!first)
348 first = second;
349
350 memswap(&first->sl.item, &second->sl.item, sizeof(first->sl.item));
351}
352