1 /* radare - LGPL - Copyright 2007-2019 - pancake, alvarofe */
2 // TODO: RRef - reference counting
3
4 #include <stdio.h>
5
6 #define _R_LIST_C_
7 #include "r_util.h"
8
r_list_iter_new(void)9 inline RListIter *r_list_iter_new(void) {
10 return calloc (1, sizeof (RListIter));
11 }
12
r_list_iter_free(RListIter * list)13 R_API void r_list_iter_free(RListIter *list) {
14 /* do nothing? */
15 }
16
r_list_iter_get_next(RListIter * list)17 R_API RListIter *r_list_iter_get_next(RListIter *list) {
18 r_return_val_if_fail (list, NULL);
19 return list->n;
20 }
21
r_list_iter_get_data(RListIter * list)22 R_API void *r_list_iter_get_data(RListIter *list) {
23 r_return_val_if_fail (list, NULL);
24 return list->data;
25 }
26
r_list_iterator(const RList * list)27 R_API RListIter *r_list_iterator(const RList *list) {
28 r_return_val_if_fail (list, NULL);
29 return list->head;
30 }
31
r_list_push(RList * list,void * item)32 R_API RListIter *r_list_push(RList *list, void *item) {
33 return r_list_append (list, item);
34 }
35
r_list_get_next(RListIter * list)36 R_API RListIter *r_list_get_next(RListIter *list) {
37 r_return_val_if_fail (list, NULL);
38 return list->n;
39 }
40
41 // rename to head/last
r_list_first(const RList * list)42 R_API void *r_list_first(const RList *list) {
43 r_return_val_if_fail (list, NULL);
44 return list->head ? list->head->data : NULL;
45 }
46
r_list_last(const RList * list)47 R_API void *r_list_last(const RList *list) {
48 r_return_val_if_fail (list, NULL);
49 return list->tail ? list->tail->data : NULL;
50 }
51
r_list_init(RList * list)52 R_API void r_list_init(RList *list) {
53 list->head = NULL;
54 list->tail = NULL;
55 list->free = NULL;
56 list->length = 0;
57 list->sorted = false;
58 }
59
r_list_length(const RList * list)60 R_API int r_list_length(const RList *list) {
61 r_return_val_if_fail (list, 0);
62 return list->length;
63 }
64
65 /* remove all elements of a list */
r_list_purge(RList * list)66 R_API void r_list_purge(RList *list) {
67 if (!list) {
68 return;
69 }
70 RListIter *it = list->head;
71 while (it) {
72 RListIter *next = it->n;
73 r_list_delete (list, it);
74 it = next;
75 }
76 list->length = 0;
77 list->head = list->tail = NULL;
78 }
79
80 /* free the list */
r_list_free(RList * list)81 R_API void r_list_free(RList *list) {
82 if (list) {
83 r_list_purge (list);
84 free (list);
85 }
86 }
87
r_list_delete_data(RList * list,void * ptr)88 R_API bool r_list_delete_data(RList *list, void *ptr) {
89 void *p;
90 RListIter *iter;
91
92 r_return_val_if_fail (list, false);
93
94 r_list_foreach (list, iter, p) {
95 if (ptr == p) {
96 r_list_delete (list, iter);
97 return true;
98 }
99 }
100 return false;
101 }
102
r_list_delete(RList * list,RListIter * iter)103 R_API void r_list_delete(RList *list, RListIter *iter) {
104 r_return_if_fail (list && iter);
105 r_list_split_iter (list, iter);
106 if (list->free && iter->data) {
107 list->free (iter->data);
108 }
109 iter->data = NULL;
110 free (iter);
111 }
112
r_list_split(RList * list,void * ptr)113 R_API void r_list_split(RList *list, void *ptr) {
114 r_return_if_fail (list);
115
116 RListIter *iter = r_list_iterator (list);
117 while (iter) {
118 void *item = iter->data;
119 if (ptr == item) {
120 r_list_split_iter (list, iter);
121 free (iter);
122 break;
123 }
124 iter = iter->n;
125 }
126 }
127
r_list_split_iter(RList * list,RListIter * iter)128 R_API void r_list_split_iter(RList *list, RListIter *iter) {
129 r_return_if_fail (list);
130
131 if (list->head == iter) {
132 list->head = iter->n;
133 }
134 if (list->tail == iter) {
135 list->tail = iter->p;
136 }
137 if (iter->p) {
138 iter->p->n = iter->n;
139 }
140 if (iter->n) {
141 iter->n->p = iter->p;
142 }
143 list->length--;
144 }
145
146 //Warning: free functions must be compatible
r_list_join(RList * list1,RList * list2)147 R_API int r_list_join(RList *list1, RList *list2) {
148 r_return_val_if_fail (list1 && list2, 0);
149
150 if (!(list2->length)) {
151 return 0;
152 }
153 if (!(list1->length)) {
154 list1->head = list2->head;
155 list1->tail = list2->tail;
156 } else {
157 list1->tail->n = list2->head;
158 list2->head->p = list1->tail;
159 list1->tail = list2->tail;
160 list1->tail->n = NULL;
161 list1->sorted = false;
162 }
163 list1->length += list2->length;
164 list2->length = 0;
165 list2->head = list2->tail = NULL;
166 return 1;
167 }
168
r_list_new(void)169 R_API RList *r_list_new(void) {
170 RList *list = R_NEW0 (RList);
171 if (!list) {
172 return NULL;
173 }
174 r_list_init (list);
175 return list;
176 }
177
r_list_newf(RListFree f)178 R_API RList *r_list_newf(RListFree f) {
179 RList *l = r_list_new ();
180 if (l) {
181 l->free = f;
182 }
183 return l;
184 }
185
r_list_item_new(void * data)186 R_API RListIter *r_list_item_new(void *data) {
187 RListIter *item = R_NEW0 (RListIter);
188 if (item) {
189 item->data = data;
190 }
191 return item;
192 }
193
r_list_append(RList * list,void * data)194 R_API RListIter *r_list_append(RList *list, void *data) {
195 RListIter *item = NULL;
196
197 r_return_val_if_fail (list, NULL);
198
199 item = R_NEW (RListIter);
200 if (!item) {
201 return item;
202 }
203 if (list->tail) {
204 list->tail->n = item;
205 }
206 item->data = data;
207 item->p = list->tail;
208 item->n = NULL;
209 list->tail = item;
210 if (!list->head) {
211 list->head = item;
212 }
213 list->length++;
214 list->sorted = false;
215 return item;
216 }
217
r_list_prepend(RList * list,void * data)218 R_API RListIter *r_list_prepend(RList *list, void *data) {
219 r_return_val_if_fail (list, NULL);
220
221 RListIter *item = R_NEW0 (RListIter);
222 if (!item) {
223 return NULL;
224 }
225 if (list->head) {
226 list->head->p = item;
227 }
228 item->data = data;
229 item->n = list->head;
230 item->p = NULL;
231 list->head = item;
232 if (!list->tail) {
233 list->tail = item;
234 }
235 list->length++;
236 list->sorted = true;
237 return item;
238 }
239
r_list_insert(RList * list,int n,void * data)240 R_API RListIter *r_list_insert(RList *list, int n, void *data) {
241 RListIter *it, *item;
242 int i;
243
244 r_return_val_if_fail (list, NULL);
245
246 if (!list->head || !n) {
247 return r_list_prepend (list, data);
248 }
249 for (it = list->head, i = 0; it && it->data; it = it->n, i++) {
250 if (i == n) {
251 item = R_NEW (RListIter);
252 if (!item) {
253 return NULL;
254 }
255 item->data = data;
256 item->n = it;
257 item->p = it->p;
258 if (it->p) {
259 it->p->n = item;
260 }
261 it->p = item;
262 list->length++;
263 list->sorted = true;
264 return item;
265 }
266 }
267 return r_list_append (list, data);
268 }
269
r_list_pop(RList * list)270 R_API void *r_list_pop(RList *list) {
271 void *data = NULL;
272 RListIter *iter;
273
274 r_return_val_if_fail (list, NULL);
275
276 if (list->tail) {
277 iter = list->tail;
278 if (list->head == list->tail) {
279 list->head = list->tail = NULL;
280 } else {
281 list->tail = iter->p;
282 list->tail->n = NULL;
283 }
284 data = iter->data;
285 free (iter);
286 list->length--;
287 }
288 return data;
289 }
290
r_list_pop_head(RList * list)291 R_API void *r_list_pop_head(RList *list) {
292 void *data = NULL;
293
294 r_return_val_if_fail (list, NULL);
295
296 if (list->head) {
297 RListIter *iter = list->head;
298 if (list->head == list->tail) {
299 list->head = list->tail = NULL;
300 } else {
301 list->head = iter->n;
302 list->head->p = NULL;
303 }
304 data = iter->data;
305 free (iter);
306 list->length--;
307 }
308 return data;
309 }
310
r_list_del_n(RList * list,int n)311 R_API int r_list_del_n(RList *list, int n) {
312 RListIter *it;
313 int i;
314
315 r_return_val_if_fail (list, false);
316
317 for (it = list->head, i = 0; it && it->data; it = it->n, i++) {
318 if (i == n) {
319 if (!it->p && !it->n) {
320 list->head = list->tail = NULL;
321 } else if (!it->p) {
322 it->n->p = NULL;
323 list->head = it->n;
324 } else if (!it->n) {
325 it->p->n = NULL;
326 list->tail = it->p;
327 } else {
328 it->p->n = it->n;
329 it->n->p = it->p;
330 }
331 free (it);
332 list->length--;
333 return true;
334 }
335 }
336 return false;
337 }
338
r_list_get_top(const RList * list)339 R_API void *r_list_get_top(const RList *list) {
340 r_return_val_if_fail (list, NULL);
341
342 return list->tail ? list->tail->data : NULL;
343 }
344
r_list_get_bottom(const RList * list)345 R_API void *r_list_get_bottom(const RList *list) {
346 r_return_val_if_fail (list, NULL);
347
348 return list->head ? list->head->data : NULL;
349 }
350
r_list_reverse(RList * list)351 R_API void r_list_reverse(RList *list) {
352 RListIter *it, *tmp;
353
354 r_return_if_fail (list);
355
356 for (it = list->head; it && it->data; it = it->p) {
357 tmp = it->p;
358 it->p = it->n;
359 it->n = tmp;
360 }
361 tmp = list->head;
362 list->head = list->tail;
363 list->tail = tmp;
364 }
365
r_list_clone(const RList * list)366 R_API RList *r_list_clone(const RList *list) {
367 RListIter *iter;
368 void *data;
369
370 r_return_val_if_fail (list, NULL);
371
372 RList *l = r_list_new ();
373 if (!l) {
374 return NULL;
375 }
376 l->free = NULL;
377 r_list_foreach (list, iter, data) {
378 r_list_append (l, data);
379 }
380 l->sorted = list->sorted;
381 return l;
382 }
383
r_list_add_sorted(RList * list,void * data,RListComparator cmp)384 R_API RListIter *r_list_add_sorted(RList *list, void *data, RListComparator cmp) {
385 RListIter *it, *item = NULL;
386
387 r_return_val_if_fail (list && data && cmp, NULL);
388
389 for (it = list->head; it && it->data && cmp (data, it->data) > 0; it = it->n) {
390 ;
391 }
392 if (it) {
393 item = R_NEW0 (RListIter);
394 if (!item) {
395 return NULL;
396 }
397 item->n = it;
398 item->p = it->p;
399 item->data = data;
400 item->n->p = item;
401 if (!item->p) {
402 list->head = item;
403 } else {
404 item->p->n = item;
405 }
406 list->length++;
407 } else {
408 r_list_append (list, data);
409 }
410 list->sorted = true;
411 return item;
412 }
413
r_list_set_n(RList * list,int n,void * p)414 R_API int r_list_set_n(RList *list, int n, void *p) {
415 RListIter *it;
416 int i;
417
418 r_return_val_if_fail (list, false);
419 for (it = list->head, i = 0; it ; it = it->n, i++) {
420 if (i == n) {
421 if (list->free) {
422 list->free (it->data);
423 }
424 it->data = p;
425 list->sorted = false;
426 return true;
427 }
428 }
429 return false;
430 }
431
r_list_get_n(const RList * list,int n)432 R_API void *r_list_get_n(const RList *list, int n) {
433 RListIter *it;
434 int i;
435
436 r_return_val_if_fail (list, NULL);
437
438 for (it = list->head, i = 0; it && it->data; it = it->n, i++) {
439 if (i == n) {
440 return it->data;
441 }
442 }
443 return NULL;
444 }
445
r_list_contains(const RList * list,const void * p)446 R_API RListIter *r_list_contains(const RList *list, const void *p) {
447 void *q;
448 RListIter *iter;
449
450 r_return_val_if_fail (list, NULL);
451
452 r_list_foreach (list, iter, q) {
453 if (p == q) {
454 return iter;
455 }
456 }
457 return NULL;
458 }
459
r_list_find(const RList * list,const void * p,RListComparator cmp)460 R_API RListIter *r_list_find(const RList *list, const void *p, RListComparator cmp) {
461 void *q;
462 RListIter *iter;
463
464 r_return_val_if_fail (list, NULL);
465
466 r_list_foreach (list, iter, q) {
467 if (!cmp (p, q)) {
468 return iter;
469 }
470 }
471 return NULL;
472 }
473
_merge(RListIter * first,RListIter * second,RListComparator cmp)474 static RListIter *_merge(RListIter *first, RListIter *second, RListComparator cmp) {
475 RListIter *next = NULL, *result = NULL, *head = NULL;
476 while (first || second) {
477 if (!second) {
478 next = first;
479 first = first->n;
480 } else if (!first) {
481 next = second;
482 second = second->n;
483 } else if (cmp (first->data, second->data) <= 0) {
484 next = first;
485 first = first->n;
486 } else {
487 next = second;
488 second = second->n;
489 }
490 if (!head) {
491 result = next;
492 head = result;
493 head->p = NULL;
494 } else {
495 result->n = next;
496 next->p = result;
497 result = result->n;
498 }
499 }
500 head->p = NULL;
501 next->n = NULL;
502 return head;
503 }
504
_r_list_half_split(RListIter * head)505 static RListIter * _r_list_half_split(RListIter *head) {
506 RListIter *tmp;
507 RListIter *fast;
508 RListIter *slow;
509 if (!head || !head->n) {
510 return head;
511 }
512 slow = head;
513 fast = head;
514 while (fast && fast->n && fast->n->n) {
515 fast = fast->n->n;
516 slow = slow->n;
517 }
518 tmp = slow->n;
519 slow->n = NULL;
520 return tmp;
521 }
522
_merge_sort(RListIter * head,RListComparator cmp)523 static RListIter * _merge_sort(RListIter *head, RListComparator cmp) {
524 RListIter *second;
525 if (!head || !head->n) {
526 return head;
527 }
528 second = _r_list_half_split (head);
529 head = _merge_sort (head, cmp);
530 second = _merge_sort (second, cmp);
531 return _merge (head, second, cmp);
532 }
533
r_list_merge_sort(RList * list,RListComparator cmp)534 R_API void r_list_merge_sort(RList *list, RListComparator cmp) {
535 r_return_if_fail (list);
536
537 if (!list->sorted && list->head && cmp) {
538 RListIter *iter;
539 list->head = _merge_sort (list->head, cmp);
540 //update tail reference
541 iter = list->head;
542 while (iter && iter->n) {
543 iter = iter->n;
544 }
545 list->tail = iter;
546 }
547 list->sorted = true;
548 }
549
r_list_insertion_sort(RList * list,RListComparator cmp)550 R_API void r_list_insertion_sort(RList *list, RListComparator cmp) {
551 r_return_if_fail (list);
552
553 if (!list->sorted) {
554 RListIter *it;
555 RListIter *it2;
556 if (cmp) {
557 for (it = list->head; it && it->data; it = it->n) {
558 for (it2 = it->n; it2 && it2->data; it2 = it2->n) {
559 if (cmp (it->data, it2->data) > 0) {
560 void *t = it->data;
561 it->data = it2->data;
562 it2->data = t;
563 }
564 }
565 }
566 }
567 list->sorted = true;
568 }
569 }
570
571 //chose wisely based on length
r_list_sort(RList * list,RListComparator cmp)572 R_API void r_list_sort(RList *list, RListComparator cmp) {
573 r_return_if_fail (list);
574 if (list->length > 43) {
575 r_list_merge_sort (list, cmp);
576 } else {
577 r_list_insertion_sort (list, cmp);
578 }
579 }
580
r_list_uniq(const RList * list,RListComparator cmp)581 R_API RList *r_list_uniq(const RList *list, RListComparator cmp) {
582 RListIter *iter, *iter2;
583 void *item, *item2;
584
585 r_return_val_if_fail (list && cmp, NULL);
586
587 RList *nl = r_list_newf (NULL);
588 if (!nl) {
589 return NULL;
590 }
591 r_list_foreach (list, iter, item) {
592 bool found = false;
593 r_list_foreach (nl, iter2, item2) {
594 if (cmp (item, item2) == 0) {
595 found = true;
596 break;
597 }
598 }
599 if (!found) {
600 r_list_append (nl, item);
601 }
602 }
603 return nl;
604 }
r_list_to_str(RList * list,char ch)605 R_API char *r_list_to_str(RList *list, char ch) {
606 RListIter *iter;
607 RStrBuf *buf = r_strbuf_new ("");
608 if (!buf) {
609 return NULL;
610 }
611 char *item;
612 r_list_foreach (list, iter, item) {
613 r_strbuf_appendf (buf, "%s%c", item, ch);
614 }
615 return r_strbuf_drain (buf);
616 }
617