llist.c - rohrpost - A commandline mail client to change the world as we see it.
(HTM) git clone git://r-36.net/rohrpost
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
llist.c (15271B)
---
1 /*
2 * Copy me if you can.
3 * by 20h
4 */
5
6 #include <unistd.h>
7 #include <stdlib.h>
8 #include <stdio.h>
9 #include <string.h>
10 #include <strings.h>
11 #include <sys/types.h>
12 #include <regex.h>
13
14 #include "ind.h"
15 #include "llist.h"
16
17 enum {
18 FREE_NORMAL = 0x0,
19 FREE_EXTENDED = 0x1,
20 FREE_BARE = 0x2
21 };
22
23 void
24 llistelemvalue_internfree(llistelem_t *elem, int mode)
25 {
26 if (elem->key == NULL && elem->data != NULL
27 && (mode & FREE_EXTENDED)) {
28 if (mode & FREE_BARE)
29 llist_ebfree((llist_t *)elem->data);
30 else
31 llist_efree((llist_t *)elem->data);
32 } else {
33 if (elem->data != NULL && !(mode & FREE_BARE)) {
34 free(elem->data);
35 elem->data = NULL;
36 }
37 }
38 if (elem->key != NULL && !(mode & FREE_BARE)) {
39 free(elem->key);
40 elem->key = NULL;
41 }
42 }
43
44 void
45 llistelemvalue_free(llistelem_t *elem)
46 {
47 llistelemvalue_internfree(elem, FREE_NORMAL);
48 }
49
50 void
51 llistelem_free(llistelem_t *elem)
52 {
53 llistelemvalue_internfree(elem, FREE_NORMAL);
54 free(elem);
55 }
56
57 void
58 llistelemvalue_efree(llistelem_t *elem)
59 {
60 llistelemvalue_internfree(elem, FREE_EXTENDED);
61 }
62
63 void
64 llistelem_efree(llistelem_t *elem)
65 {
66 llistelemvalue_internfree(elem, FREE_EXTENDED);
67 free(elem);
68 }
69
70 llistelem_t *
71 llistelem_set(llistelem_t *elem, char *key, void *data, int datalen)
72 {
73 int keylen;
74
75 llistelemvalue_free(elem);
76
77 if (key != NULL) {
78 keylen = strlen(key);
79 elem->key = mallocz(keylen+1, 2);
80 memmove(elem->key, key, keylen);
81 }
82 if (data != NULL) {
83 elem->data = mallocz(datalen+1, 2);
84 elem->datalen = datalen;
85 memmove(elem->data, data, datalen);
86 }
87
88 return elem;
89 }
90
91 llistelem_t *
92 llistelem_rawset(llistelem_t *elem, char *key, void *data, int datalen)
93 {
94 llistelemvalue_free(elem);
95
96 elem->key = key;
97 elem->data = data;
98 elem->datalen = datalen;
99
100 return elem;
101 }
102
103 llistelem_t *
104 llistelem_new(char *key, void *data, int datalen)
105 {
106 return llistelem_set(mallocz(sizeof(llistelem_t), 2), key, data,
107 datalen);
108 }
109
110 llistelem_t *
111 llistelem_rawnew(char *key, void *data, int datalen)
112 {
113 return llistelem_rawset(mallocz(sizeof(llistelem_t), 2), key, data,
114 datalen);
115 }
116
117 void
118 llistelem_print(llistelem_t *elem)
119 {
120 //printf("(%p)%s = %s\n", elem, elem->key, (char *)elem->data);
121 printf("%s = %s\n", elem->key, (char *)elem->data);
122 }
123
124 void
125 llistelem_printkey(llistelem_t *elem)
126 {
127 printf("%s\n", elem->key);
128 }
129
130 void
131 llistelem_printdata(llistelem_t *elem)
132 {
133 printf("%s\n", (char *)elem->data);
134 }
135
136 int
137 llistelem_cmp(llistelem_t *elem1, llistelem_t *elem2)
138 {
139 int ret, len1, len2;
140
141 if (elem1 == elem2)
142 return 0;
143
144 len1 = strlen(elem1->key);
145 len2 = strlen(elem2->key);
146
147 if (len1 != len2)
148 return (len1 - len2);
149 if (elem1->datalen != elem2->datalen)
150 return (elem1->datalen - elem2->datalen);
151 if ((ret = memcmp(elem1->key, elem2->key, len1)))
152 return ret;
153 if ((ret = memcmp(elem1->data, elem2->data, elem1->datalen)))
154 return ret;
155
156 return 0;
157 }
158
159 llist_t *
160 llist_new(void)
161 {
162 return (llist_t *)mallocz(sizeof(llist_t), 2);
163 }
164
165 /* for mode argument see beginning of this file */
166 void
167 llist_internfree(llist_t *llist, int mode)
168 {
169 llistelem_t *elem;
170
171 //printf("internfree: %p\n", llist);
172 if (llist->first != NULL) {
173 for (elem = llist->first;;) {
174 //printf("list free %d %d\n", elem->datalen, sizeof(llist_t));
175 llistelemvalue_internfree(elem, mode);
176
177 if (elem->next != NULL) {
178 elem = elem->next;
179 free(elem->prev);
180 } else {
181 free(elem);
182 break;
183 }
184 }
185 }
186 free(llist);
187 }
188
189 void
190 llist_free(llist_t *llist)
191 {
192 llist_internfree(llist, FREE_NORMAL);
193 }
194
195 void
196 llist_bfree(llist_t *llist)
197 {
198 llist_internfree(llist, FREE_BARE);
199 }
200
201 void
202 llist_efree(llist_t *llist)
203 {
204 llist_internfree(llist, FREE_EXTENDED);
205 }
206
207 void
208 llist_ebfree(llist_t *llist)
209 {
210 llist_internfree(llist, FREE_EXTENDED|FREE_BARE);
211 }
212
213 llistelem_t *
214 llist_addelem(llist_t *llist, llistelem_t *elem)
215 {
216 if (llist->first == NULL)
217 llist->first = elem;
218 if (llist->last == NULL)
219 llist->last = elem;
220 else {
221 llist->last->next = elem;
222 elem->prev = llist->last;
223 llist->last = elem;
224 }
225 llist->len++;
226
227 return elem;
228 }
229
230 llistelem_t *
231 llist_addraw(llist_t *llist, char *key, void *data, int datalen)
232 {
233 llistelem_t *elem;
234
235 elem = llistelem_new(NULL, NULL, 0);
236 elem->key = key;
237 elem->data = data;
238 elem->datalen = datalen;
239
240 llist_addelem(llist, elem);
241
242 return elem;
243 }
244
245 llistelem_t *
246 llist_add(llist_t *llist, char *key, void *data, int datalen)
247 {
248 return llist_addelem(llist, llistelem_new(key, data, datalen));
249 }
250
251 llistelem_t *
252 llist_push(llist_t *llist, char *key, void *data, int datalen)
253 {
254 llistelem_t *elem;
255
256 elem = llistelem_new(key, data, datalen);
257
258 if (llist->first == NULL)
259 llist->first = elem;
260 else {
261 llist->first->prev = elem;
262 elem->next = llist->first;
263 llist->first = elem;
264 }
265 if (llist->last == NULL)
266 llist->last = elem;
267 llist->len++;
268
269 return elem;
270 }
271
272 llistelem_t *
273 llist_pop(llist_t *llist)
274 {
275 llistelem_t *elem;
276
277 if (llist->len < 1)
278 return NULL;
279
280 elem = llist->first;
281 if (elem->next != NULL)
282 elem->next->prev = NULL;
283 llist->first = elem->next;
284 elem->prev = NULL;
285 elem->next = NULL;
286 llist->len--;
287
288 return elem;
289 }
290
291 enum {
292 FIND_NORMAL = 0x0,
293 FIND_EXTENDED = 0x1,
294 FIND_CI = 0x2
295 };
296
297 llist_t *
298 llist_internfind(llist_t *llist, char *regex, int mode)
299 {
300 llist_t *results, *sresults;
301 llistelem_t *elem;
302 regex_t preg;
303
304 if (regcomp(&preg, regex, REG_EXTENDED|REG_NOSUB \
305 |((mode & FIND_CI)? REG_ICASE : 0))) {
306 return NULL;
307 }
308
309 results = llist_new();
310 forllist(llist, elem) {
311 if (mode & FIND_EXTENDED && elem->key != NULL
312 && elem->data != NULL
313 && elem->datalen == sizeof(llist_t)) {
314 sresults = llist_internfind((llist_t *)elem->data,
315 regex, mode);
316 if (sresults != NULL) {
317 llist_rawlistadd(results, sresults);
318 llist_bfree(sresults);
319 }
320 continue;
321 }
322
323 if (!regexec(&preg, elem->key, 0, NULL, 0)) {
324 llist_add(results, elem->key, elem->data,
325 elem->datalen);
326 }
327 }
328
329 regfree(&preg);
330
331 if (results->first == NULL) {
332 llist_free(results);
333 results = NULL;
334 }
335
336 return results;
337 }
338
339 llist_t *
340 llist_find(llist_t *llist, char *regex)
341 {
342 return llist_internfind(llist, regex, FIND_NORMAL);
343 }
344
345 llist_t *
346 llist_efind(llist_t *llist, char *regex)
347 {
348 return llist_internfind(llist, regex, FIND_EXTENDED);
349 }
350
351 llist_t *
352 llist_cifind(llist_t *llist, char *regex)
353 {
354 return llist_internfind(llist, regex, FIND_NORMAL|FIND_CI);
355 }
356
357 llist_t *
358 llist_ecifind(llist_t *llist, char *regex)
359 {
360 return llist_internfind(llist, regex, FIND_EXTENDED|FIND_CI);
361 }
362
363 enum {
364 GET_NORMAL = 0x01,
365 GET_EXTENDED = 0x02,
366 GET_CASEINSENSITIVE = 0x04
367 };
368
369 llistelem_t *
370 llist_internget(llist_t *llist, char *key, int mode)
371 {
372 llistelem_t *elem, *selem;
373
374 forllist(llist, elem) {
375 if (mode & GET_EXTENDED && elem->key == NULL
376 && elem->data != NULL
377 && elem->datalen == sizeof(llist_t)) {
378 selem = llist_internget((llist_t *)elem->data, key,
379 mode);
380 if (selem != NULL)
381 return selem;
382 }
383
384 if (mode & GET_CASEINSENSITIVE) {
385 if (elem->key != NULL && !strcasecmp(elem->key, key))
386 break;
387 } else {
388 if (elem->key != NULL && !strcmp(elem->key, key))
389 break;
390 }
391 }
392
393 return elem;
394 }
395
396 llistelem_t *
397 llist_get(llist_t *llist, char *key)
398 {
399 return llist_internget(llist, key, GET_NORMAL);
400 }
401
402 llistelem_t *
403 llist_ciget(llist_t *llist, char *key)
404 {
405 return llist_internget(llist, key, GET_NORMAL|GET_CASEINSENSITIVE);
406 }
407
408 llistelem_t *
409 llist_eget(llist_t *llist, char *key)
410 {
411 return llist_internget(llist, key, GET_EXTENDED);
412 }
413
414 llistelem_t *
415 llist_eciget(llist_t *llist, char *key)
416 {
417 return llist_internget(llist, key, GET_EXTENDED|GET_CASEINSENSITIVE);
418 }
419
420 llistelem_t *
421 llist_getn(llist_t *llist, int idx)
422 {
423 llistelem_t *elem;
424 int i;
425
426 i = 0;
427 forllist(llist, elem) {
428 if (i == idx)
429 return elem;
430 i++;
431 }
432 return NULL;
433 }
434
435 void
436 llist_delelemlinks(llist_t *llist, llistelem_t *elem)
437 {
438 llistelem_t *prev, *next;
439
440 prev = elem->prev;
441 next = elem->next;
442
443 if (prev != NULL)
444 prev->next = next;
445 if (next != NULL)
446 next->prev = prev;
447 if (llist->first == elem)
448 llist->first = next;
449 if (llist->last == elem)
450 llist->last = prev;
451 }
452
453 void
454 llist_delelem(llist_t *llist, llistelem_t *elem)
455 {
456 llist_delelemlinks(llist, elem);
457 llistelem_free(elem);
458 llist->len--;
459 }
460
461 llistelem_t *
462 llist_del(llist_t *llist, char *key)
463 {
464 llistelem_t *elem;
465
466 elem = llist_get(llist, key);
467 if (elem != NULL)
468 llist_delelem(llist, elem);
469
470 return elem;
471 }
472
473 llistelem_t *
474 llist_insert(llist_t *llist, llistelem_t *elem, int idx)
475 {
476 int i;
477 llistelem_t *next;
478
479 i = 0;
480
481 if (idx > llist->len-1)
482 return NULL;
483 if (idx == llist->len-1)
484 return llist_addelem(llist, elem);
485
486 forllist(llist, next)
487 if (i == idx)
488 break;
489
490 if (next->prev != NULL)
491 next->prev->next = elem;
492 elem->prev = next->prev;
493 next->prev = elem;
494 elem->next = next;
495
496 return elem;
497 }
498
499 llistelem_t *
500 llist_move(llist_t *llist, llistelem_t *elem, int idx)
501 {
502 llist_delelemlinks(llist, elem);
503 return llist_insert(llist, elem, idx);
504 }
505
506 void
507 llist_print(llist_t *llist)
508 {
509 llistelem_t *elem;
510
511 forllist(llist, elem)
512 printf("%s = \"%s\"\n", (char *)elem->key, (char *)elem->data);
513 fflush(stdout);
514 }
515
516 void
517 llistelem_eprintelem(llistelem_t *elem, int depth)
518 {
519 for (; depth; depth--)
520 printf("\t");
521 llistelem_print(elem);
522 }
523
524 void
525 llist_eprintintern(llist_t *stru, int depth)
526 {
527 llistelem_t *elem;
528 int i;
529
530 for (i = 0; i < depth; i++)
531 printf("\t");
532 //printf("list %p\n", stru);
533 printf("list\n");
534 forllist(stru, elem) {
535 if (elem->key == NULL)
536 llist_eprintintern((llist_t *)elem->data, depth+1);
537 else
538 llistelem_eprintelem(elem, depth);
539 }
540 for (i = 0; i < depth; i++)
541 printf("\t");
542 printf("list ended\n");
543 }
544
545 void
546 llist_eprint(llist_t *llist)
547 {
548 llist_eprintintern(llist, 0);
549 }
550
551 void
552 llistelem_eprint(llistelem_t *elem)
553 {
554 if (elem->key == NULL)
555 llist_eprintintern((llist_t *)elem->data, 0);
556 else
557 llistelem_print(elem);
558 }
559
560 llist_t *
561 llist_getdiff(llist_t *llist1, llist_t *llist2)
562 {
563 llist_t *diff;
564 llistelem_t *elem1, *elem2;
565
566 diff = llist_new();
567
568 forllist(llist1, elem1) {
569 forllist(llist2, elem2) {
570 if (llistelem_cmp(elem1, elem2)) {
571 llist_add(diff, elem1->key, elem1->data,
572 elem1->datalen);
573 llist_add(diff, elem2->key, elem2->data,
574 elem2->datalen);
575 }
576 }
577 }
578
579 return diff;
580 }
581
582 llist_t *
583 llist_getsame(llist_t *llist1, llist_t *llist2)
584 {
585 llist_t *same;
586 llistelem_t *elem1, *elem2;
587
588 same = llist_new();
589
590 forllist(llist1, elem1) {
591 forllist(llist2, elem2) {
592 if (!llistelem_cmp(elem1, elem2)) {
593 llist_add(same, elem1->key, elem1->data,
594 elem1->datalen);
595 }
596 }
597 }
598
599 return same;
600 }
601
602 llist_t *
603 llist_copy(llist_t *llist)
604 {
605 llist_t *rllist;
606 llistelem_t *elem;
607
608 rllist = llist_new();
609 forllist(llist, elem)
610 llist_add(rllist, elem->key, elem->data, elem->datalen);
611
612 return rllist;
613 }
614
615 llist_t *
616 llist_listdel(llist_t *llist, llist_t *elems)
617 {
618 llistelem_t *elem;
619
620 forllist(elems, elem)
621 llist_del(llist, elem->key);
622
623 return llist;
624 }
625
626 llist_t *
627 llist_rawlistadd(llist_t *llist, llist_t *elems)
628 {
629 llistelem_t *elem;
630
631 forllist(elems, elem)
632 llist_addraw(llist, elem->key, elem->data, elem->datalen);
633
634 return llist;
635 }
636
637 llist_t *
638 llist_listadd(llist_t *llist, llist_t *elems)
639 {
640 llistelem_t *elem;
641
642 forllist(elems, elem)
643 llist_add(llist, elem->key, elem->data, elem->datalen);
644
645 return llist;
646 }
647
648 llist_t *
649 llist_splitstr(char *str, char *sep)
650 {
651 char *tok, *strc, *saveptr;
652 llist_t *llist;
653
654 saveptr = NULL;
655
656 strc = memdups(str);
657
658 tok = strtok_r(strc, sep, &saveptr);
659 if (tok == NULL) {
660 free(strc);
661 return NULL;
662 }
663
664 llist = llist_new();
665 do {
666 llist_add(llist, tok, NULL, 0);
667 } while((tok = strtok_r(NULL, sep, &saveptr)));
668 free(strc);
669
670 return llist;
671 }
672
673 llist_t *
674 llist_splitargv(int argc, char *argv[])
675 {
676 llist_t *llist;
677 int i;
678
679 if (argc < 1)
680 return NULL;
681
682 llist = llist_new();
683 for(i = 0; argc; i++, argc--)
684 llist_add(llist, argv[i], NULL, 0);
685
686 return llist;
687 }
688
689 char *
690 llist_joinstr(llist_t *llist, char *sep)
691 {
692 char *str, *tstr, *sstr;
693 llistelem_t *elem;
694 int keylen, seplen, size;
695
696 str = NULL;
697 seplen = strlen(sep);
698 size = 0;
699
700 forllist(llist, elem) {
701 keylen = strlen(elem->key);
702 if (str == NULL) {
703 str = memdup(elem->key, keylen+1);
704 size += keylen;
705 } else {
706 /*
707 * Premature optimisation.
708 */
709 sstr = mallocz(keylen + seplen + 1, 1);
710 memmove(sstr, sep, seplen);
711 memmove(&sstr[seplen], elem->key, keylen);
712
713 keylen += seplen;
714 tstr = memdupcat(str, size, sstr, keylen+1);
715 free(sstr);
716 str = tstr;
717
718 size += keylen;
719 }
720 }
721
722 return str;
723 }
724
725 llist_t *
726 llist_genrange(int begin, int end, int step)
727 {
728 llist_t *llist;
729 int i, min, max;
730
731 if (begin == end)
732 return NULL;
733
734 max = (begin > end)? begin : end;
735 min = (begin > end)? end : begin;
736
737 llist = llist_new();
738 for (i = min; i < max; i += step)
739 llist_addraw(llist, smprintf("%d", i), NULL, 0);
740
741 return llist;
742 }
743
744 int
745 llist_strcmp(llistelem_t *elem1, llistelem_t *elem2)
746 {
747 return strcmp(elem1->key, elem2->key);
748 }
749
750 int
751 llist_intcmp(llistelem_t *elem1, llistelem_t *elem2)
752 {
753 return atoi(elem1->key) - atoi(elem2->key);
754 }
755
756 /* Taken from:
757 * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
758 *
759 *
760 * This following algorithm is copyright 2001 Simon Tatham.
761 *
762 * Permission is hereby granted, free of charge, to any person
763 * obtaining a copy of this software and associated documentation
764 * files (the "Software"), to deal in the Software without
765 * restriction, including without limitation the rights to use,
766 * copy, modify, merge, publish, distribute, sublicense, and/or
767 * sell copies of the Software, and to permit persons to whom the
768 * Software is furnished to do so, subject to the following
769 * conditions:
770 *
771 * The above copyright notice and this permission notice shall be
772 * included in all copies or substantial portions of the Software.
773 *
774 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
775 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
776 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
777 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
778 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
779 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
780 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
781 * SOFTWARE.
782 */
783
784 llist_t *
785 llist_internsort(llist_t *llist, int (*cmp)(llistelem_t *, llistelem_t *))
786 {
787 llistelem_t *p, *q, *e, *tail;
788 int insize, nmerges, psize, qsize, i;
789
790 insize = 1;
791 for (;;) {
792 p = llist->first;
793 llist->first = NULL;
794 tail = NULL;
795
796 nmerges = 0;
797
798 while(p) {
799 nmerges++;
800
801 q = p;
802 psize = 0;
803 for (i = 0; i < insize; i++) {
804 psize++;
805 q = q->next;
806 if (!q)
807 break;
808 }
809
810 qsize = insize;
811 while (psize > 0 || (qsize > 0 && q)) {
812 if (psize == 0) {
813 e = q;
814 q = q->next;
815 qsize--;
816 } else if (qsize == 0 || !q) {
817 e = p;
818 p = p->next;
819 psize--;
820 } else if (cmp(p, q) <= 0) {
821 e = p;
822 p = p->next;
823 psize--;
824 } else {
825 e = q;
826 q = q->next;
827 qsize--;
828 }
829
830 if (tail)
831 tail->next = e;
832 else
833 llist->first = e;
834 e->prev = tail;
835 tail = e;
836 }
837 p = q;
838 }
839 tail->next = NULL;
840
841 if (nmerges <= 1)
842 return llist;
843
844 insize *= 2;
845 }
846 }
847
848 llist_t *
849 llist_sort(llist_t *llist)
850 {
851 return llist_internsort(llist, llist_strcmp);
852 }
853
854 llist_t *
855 llist_intsort(llist_t *llist)
856 {
857 return llist_internsort(llist, llist_intcmp);
858 }
859