rohrpost

llist.c (15271B)

---

 /*
  * Copy me if you can.
  * by 20h
  */
 
 #include <unistd.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include <strings.h>
 #include <sys/types.h>
 #include <regex.h>
 
 #include "ind.h"
 #include "llist.h"
 
 enum {
 	FREE_NORMAL = 0x0,
 	FREE_EXTENDED = 0x1,
 	FREE_BARE = 0x2
 };
 
 void
 llistelemvalue_internfree(llistelem_t *elem, int mode)
 {
 	if (elem->key == NULL && elem->data != NULL
 			&& (mode & FREE_EXTENDED)) {
 		if (mode & FREE_BARE)
 			llist_ebfree((llist_t *)elem->data);
 		else
 			llist_efree((llist_t *)elem->data);
 	} else {
 		if (elem->data != NULL && !(mode & FREE_BARE)) {
 			free(elem->data);
 			elem->data = NULL;
 		}
 	}
 	if (elem->key != NULL && !(mode & FREE_BARE)) {
 		free(elem->key);
 		elem->key = NULL;
 	}
 }
 
 void
 llistelemvalue_free(llistelem_t *elem)
 {
 	llistelemvalue_internfree(elem, FREE_NORMAL);
 }
 
 void
 llistelem_free(llistelem_t *elem)
 {
 	llistelemvalue_internfree(elem, FREE_NORMAL);
 	free(elem);
 }
 
 void
 llistelemvalue_efree(llistelem_t *elem)
 {
 	llistelemvalue_internfree(elem, FREE_EXTENDED);
 }
 
 void
 llistelem_efree(llistelem_t *elem)
 {
 	llistelemvalue_internfree(elem, FREE_EXTENDED);
 	free(elem);
 }
 
 llistelem_t *
 llistelem_set(llistelem_t *elem, char *key, void *data, int datalen)
 {
 	int keylen;
 
 	llistelemvalue_free(elem);
 
 	if (key != NULL) {
 		keylen = strlen(key);
 		elem->key = mallocz(keylen+1, 2);
 		memmove(elem->key, key, keylen);
 	}
 	if (data != NULL) {
 		elem->data = mallocz(datalen+1, 2);
 		elem->datalen = datalen;
 		memmove(elem->data, data, datalen);
 	}
 
 	return elem;
 }
 
 llistelem_t *
 llistelem_rawset(llistelem_t *elem, char *key, void *data, int datalen)
 {
 	llistelemvalue_free(elem);
 
 	elem->key = key;
 	elem->data = data;
 	elem->datalen = datalen;
 
 	return elem;
 }
 
 llistelem_t *
 llistelem_new(char *key, void *data, int datalen)
 {
 	return llistelem_set(mallocz(sizeof(llistelem_t), 2), key, data,
 			datalen);
 }
 
 llistelem_t *
 llistelem_rawnew(char *key, void *data, int datalen)
 {
 	return llistelem_rawset(mallocz(sizeof(llistelem_t), 2), key, data,
 			datalen);
 }
 
 void
 llistelem_print(llistelem_t *elem)
 {
 	//printf("(%p)%s = %s\n", elem, elem->key, (char *)elem->data);
 	printf("%s = %s\n", elem->key, (char *)elem->data);
 }
 
 void
 llistelem_printkey(llistelem_t *elem)
 {
 	printf("%s\n", elem->key);
 }
 
 void
 llistelem_printdata(llistelem_t *elem)
 {
 	printf("%s\n", (char *)elem->data);
 }
 
 int
 llistelem_cmp(llistelem_t *elem1, llistelem_t *elem2)
 {
 	int ret, len1, len2;
 
 	if (elem1 == elem2)
 		return 0;
 
 	len1 = strlen(elem1->key);
 	len2 = strlen(elem2->key);
 
 	if (len1 != len2)
 		return (len1 - len2);
 	if (elem1->datalen != elem2->datalen)
 		return (elem1->datalen - elem2->datalen);
 	if ((ret = memcmp(elem1->key, elem2->key, len1)))
 		return ret;
 	if ((ret = memcmp(elem1->data, elem2->data, elem1->datalen)))
 		return ret;
 
 	return 0;
 }
 
 llist_t *
 llist_new(void)
 {
 	return (llist_t *)mallocz(sizeof(llist_t), 2);
 }
 
 /* for mode argument see beginning of this file */
 void
 llist_internfree(llist_t *llist, int mode)
 {
 	llistelem_t *elem;
 
 	//printf("internfree: %p\n", llist);
 	if (llist->first != NULL) {
 		for (elem = llist->first;;) {
 			//printf("list free %d %d\n", elem->datalen, sizeof(llist_t));
 			llistelemvalue_internfree(elem, mode);
 
 			if (elem->next != NULL) {
 				elem = elem->next;
 				free(elem->prev);
 			} else {
 				free(elem);
 				break;
 			}
 		}
 	}
 	free(llist);
 }
 
 void
 llist_free(llist_t *llist)
 {
 	llist_internfree(llist, FREE_NORMAL);
 }
 
 void
 llist_bfree(llist_t *llist)
 {
 	llist_internfree(llist, FREE_BARE);
 }
 
 void
 llist_efree(llist_t *llist)
 {
 	llist_internfree(llist, FREE_EXTENDED);
 }
 
 void
 llist_ebfree(llist_t *llist)
 {
 	llist_internfree(llist, FREE_EXTENDED|FREE_BARE);
 }
 
 llistelem_t *
 llist_addelem(llist_t *llist, llistelem_t *elem)
 {
 	if (llist->first == NULL)
 		llist->first = elem;
 	if (llist->last == NULL)
 		llist->last = elem;
 	else {
 		llist->last->next = elem;
 		elem->prev = llist->last;
 		llist->last = elem;
 	}
 	llist->len++;
 
 	return elem;
 }
 
 llistelem_t *
 llist_addraw(llist_t *llist, char *key, void *data, int datalen)
 {
 	llistelem_t *elem;
 
 	elem = llistelem_new(NULL, NULL, 0);
 	elem->key = key;
 	elem->data = data;
 	elem->datalen = datalen;
 
 	llist_addelem(llist, elem);
 
 	return elem;
 }
 
 llistelem_t *
 llist_add(llist_t *llist, char *key, void *data, int datalen)
 {
 	return llist_addelem(llist, llistelem_new(key, data, datalen));
 }
 
 llistelem_t *
 llist_push(llist_t *llist, char *key, void *data, int datalen)
 {
 	llistelem_t *elem;
 
 	elem = llistelem_new(key, data, datalen);
 
 	if (llist->first == NULL)
 		llist->first = elem;
 	else {
 		llist->first->prev = elem;
 		elem->next = llist->first;
 		llist->first = elem;
 	}
 	if (llist->last == NULL)
 		llist->last = elem;
 	llist->len++;
 
 	return elem;
 }
 
 llistelem_t *
 llist_pop(llist_t *llist)
 {
 	llistelem_t *elem;
 
 	if (llist->len < 1)
 		return NULL;
 
 	elem = llist->first;
 	if (elem->next != NULL)
 		elem->next->prev = NULL;
 	llist->first = elem->next;
 	elem->prev = NULL;
 	elem->next = NULL;
 	llist->len--;
 
 	return elem;
 }
 
 enum {
 	FIND_NORMAL = 0x0,
 	FIND_EXTENDED = 0x1,
 	FIND_CI = 0x2
 };
 
 llist_t *
 llist_internfind(llist_t *llist, char *regex, int mode)
 {
 	llist_t *results, *sresults;
 	llistelem_t *elem;
 	regex_t preg;
 
 	if (regcomp(&preg, regex, REG_EXTENDED|REG_NOSUB \
 				|((mode & FIND_CI)? REG_ICASE : 0))) {
 		return NULL;
 	}
 
 	results = llist_new();
 	forllist(llist, elem) {
 		if (mode & FIND_EXTENDED && elem->key != NULL
 				&& elem->data != NULL
 				&& elem->datalen == sizeof(llist_t)) {
 			sresults = llist_internfind((llist_t *)elem->data,
 					regex, mode);
 			if (sresults != NULL) {
 				llist_rawlistadd(results, sresults);
 				llist_bfree(sresults);
 			}
 			continue;
 		}
 
 		if (!regexec(&preg, elem->key, 0, NULL, 0)) {
 			llist_add(results, elem->key, elem->data,
 					elem->datalen);
 		}
 	}
 
 	regfree(&preg);
 
 	if (results->first == NULL) {
 		llist_free(results);
 		results = NULL;
 	}
 
 	return results;
 }
 
 llist_t *
 llist_find(llist_t *llist, char *regex)
 {
 	return llist_internfind(llist, regex, FIND_NORMAL);
 }
 
 llist_t *
 llist_efind(llist_t *llist, char *regex)
 {
 	return llist_internfind(llist, regex, FIND_EXTENDED);
 }
 
 llist_t *
 llist_cifind(llist_t *llist, char *regex)
 {
 	return llist_internfind(llist, regex, FIND_NORMAL|FIND_CI);
 }
 
 llist_t *
 llist_ecifind(llist_t *llist, char *regex)
 {
 	return llist_internfind(llist, regex, FIND_EXTENDED|FIND_CI);
 }
 
 enum {
 	GET_NORMAL = 0x01,
 	GET_EXTENDED = 0x02,
 	GET_CASEINSENSITIVE = 0x04
 };
 
 llistelem_t *
 llist_internget(llist_t *llist, char *key, int mode)
 {
 	llistelem_t *elem, *selem;
 
 	forllist(llist, elem) {
 		if (mode & GET_EXTENDED && elem->key == NULL
 				&& elem->data != NULL
 				&& elem->datalen == sizeof(llist_t)) {
 			selem = llist_internget((llist_t *)elem->data, key,
 					mode);
 			if (selem != NULL)
 				return selem;
 		}
 
 		if (mode & GET_CASEINSENSITIVE) {
 			if (elem->key != NULL && !strcasecmp(elem->key, key))
 				break;
 		} else {
 			if (elem->key != NULL && !strcmp(elem->key, key))
 				break;
 		}
 	}
 
 	return elem;
 }
 
 llistelem_t *
 llist_get(llist_t *llist, char *key)
 {
 	return llist_internget(llist, key, GET_NORMAL);
 }
 
 llistelem_t *
 llist_ciget(llist_t *llist, char *key)
 {
 	return llist_internget(llist, key, GET_NORMAL|GET_CASEINSENSITIVE);
 }
 
 llistelem_t *
 llist_eget(llist_t *llist, char *key)
 {
 	return llist_internget(llist, key, GET_EXTENDED);
 }
 
 llistelem_t *
 llist_eciget(llist_t *llist, char *key)
 {
 	return llist_internget(llist, key, GET_EXTENDED|GET_CASEINSENSITIVE);
 }
 
 llistelem_t *
 llist_getn(llist_t *llist, int idx)
 {
 	llistelem_t *elem;
 	int i;
 
 	i = 0;
 	forllist(llist, elem) {
 		if (i == idx)
 			return elem;
 		i++;
 	}
 	return NULL;
 }
 
 void
 llist_delelemlinks(llist_t *llist, llistelem_t *elem)
 {
 	llistelem_t *prev, *next;
 
 	prev = elem->prev;
 	next = elem->next;
 
 	if (prev != NULL)
 		prev->next = next;
 	if (next != NULL)
 		next->prev = prev;
 	if (llist->first == elem)
 		llist->first = next;
 	if (llist->last == elem)
 		llist->last = prev;
 }
 
 void
 llist_delelem(llist_t *llist, llistelem_t *elem)
 {
 	llist_delelemlinks(llist, elem);
 	llistelem_free(elem);
 	llist->len--;
 }
 
 llistelem_t *
 llist_del(llist_t *llist, char *key)
 {
 	llistelem_t *elem;
 
 	elem = llist_get(llist, key);
 	if (elem != NULL)
 		llist_delelem(llist, elem);
 
 	return elem;
 }
 
 llistelem_t *
 llist_insert(llist_t *llist, llistelem_t *elem, int idx)
 {
 	int i;
 	llistelem_t *next;
 
 	i = 0;
 
 	if (idx > llist->len-1)
 		return NULL;
 	if (idx == llist->len-1)
 		return llist_addelem(llist, elem);
 
 	forllist(llist, next)
 		if (i == idx)
 			break;
 
 	if (next->prev != NULL)
 		next->prev->next = elem;
 	elem->prev = next->prev;
 	next->prev = elem;
 	elem->next = next;
 
 	return elem;
 }
 
 llistelem_t *
 llist_move(llist_t *llist, llistelem_t *elem, int idx)
 {
 	llist_delelemlinks(llist, elem);
 	return llist_insert(llist, elem, idx);
 }
 
 void
 llist_print(llist_t *llist)
 {
 	llistelem_t *elem;
 
 	forllist(llist, elem)
 		printf("%s = \"%s\"\n", (char *)elem->key, (char *)elem->data);
 	fflush(stdout);
 }
 
 void
 llistelem_eprintelem(llistelem_t *elem, int depth)
 {
 	for (; depth; depth--)
 		printf("\t");
 	llistelem_print(elem);
 }
 
 void
 llist_eprintintern(llist_t *stru, int depth)
 {
 	llistelem_t *elem;
 	int i;
 
 	for (i = 0; i < depth; i++)
 		printf("\t");
 	//printf("list %p\n", stru);
 	printf("list\n");
 	forllist(stru, elem) {
 		if (elem->key == NULL)
 			llist_eprintintern((llist_t *)elem->data, depth+1);
 		else
 			llistelem_eprintelem(elem, depth);
 	}
 	for (i = 0; i < depth; i++)
 		printf("\t");
 	printf("list ended\n");
 }
 
 void
 llist_eprint(llist_t *llist)
 {
 	llist_eprintintern(llist, 0);
 }
 
 void
 llistelem_eprint(llistelem_t *elem)
 {
 	if (elem->key == NULL)
 		llist_eprintintern((llist_t *)elem->data, 0);
 	else
 		llistelem_print(elem);
 }
 
 llist_t *
 llist_getdiff(llist_t *llist1, llist_t *llist2)
 {
 	llist_t *diff;
 	llistelem_t *elem1, *elem2;
 
 	diff = llist_new();
 
 	forllist(llist1, elem1) {
 		forllist(llist2, elem2) {
 			if (llistelem_cmp(elem1, elem2)) {
 				llist_add(diff, elem1->key, elem1->data,
 						elem1->datalen);
 				llist_add(diff, elem2->key, elem2->data,
 						elem2->datalen);
 			}
 		}
 	}
 
 	return diff;
 }
 
 llist_t *
 llist_getsame(llist_t *llist1, llist_t *llist2)
 {
 	llist_t *same;
 	llistelem_t *elem1, *elem2;
 
 	same = llist_new();
 
 	forllist(llist1, elem1) {
 		forllist(llist2, elem2) {
 			if (!llistelem_cmp(elem1, elem2)) {
 				llist_add(same, elem1->key, elem1->data,
 						elem1->datalen);
 			}
 		}
 	}
 
 	return same;
 }
 
 llist_t *
 llist_copy(llist_t *llist)
 {
 	llist_t *rllist;
 	llistelem_t *elem;
 
 	rllist = llist_new();
 	forllist(llist, elem)
 		llist_add(rllist, elem->key, elem->data, elem->datalen);
 
 	return rllist;
 }
 
 llist_t *
 llist_listdel(llist_t *llist, llist_t *elems)
 {
 	llistelem_t *elem;
 
 	forllist(elems, elem)
 		llist_del(llist, elem->key);
 
 	return llist;
 }
 
 llist_t *
 llist_rawlistadd(llist_t *llist, llist_t *elems)
 {
 	llistelem_t *elem;
 
 	forllist(elems, elem)
 		llist_addraw(llist, elem->key, elem->data, elem->datalen);
 
 	return llist;
 }
 
 llist_t *
 llist_listadd(llist_t *llist, llist_t *elems)
 {
 	llistelem_t *elem;
 
 	forllist(elems, elem)
 		llist_add(llist, elem->key, elem->data, elem->datalen);
 
 	return llist;
 }
 
 llist_t *
 llist_splitstr(char *str, char *sep)
 {
 	char *tok, *strc, *saveptr;
 	llist_t *llist;
 
 	saveptr = NULL;
 
 	strc = memdups(str);
 
 	tok = strtok_r(strc, sep, &saveptr);
 	if (tok == NULL) {
 		free(strc);
 		return NULL;
 	}
 
 	llist = llist_new();
 	do {
 		llist_add(llist, tok, NULL, 0);
 	} while((tok = strtok_r(NULL, sep, &saveptr)));
 	free(strc);
 
 	return llist;
 }
 
 llist_t *
 llist_splitargv(int argc, char *argv[])
 {
 	llist_t *llist;
 	int i;
 
 	if (argc < 1)
 		return NULL;
 
 	llist = llist_new();
 	for(i = 0; argc; i++, argc--)
 		llist_add(llist, argv[i], NULL, 0);
 
 	return llist;
 }
 
 char *
 llist_joinstr(llist_t *llist, char *sep)
 {
 	char *str, *tstr, *sstr;
 	llistelem_t *elem;
 	int keylen, seplen, size;
 
 	str = NULL;
 	seplen = strlen(sep);
 	size = 0;
 
 	forllist(llist, elem) {
 		keylen = strlen(elem->key);
 		if (str == NULL) {
 			str = memdup(elem->key, keylen+1);
 			size += keylen;
 		} else {
 			/*
 			 * Premature optimisation.
 			 */
 			sstr = mallocz(keylen + seplen + 1, 1);
 			memmove(sstr, sep, seplen);
 			memmove(&sstr[seplen], elem->key, keylen);
 
 			keylen += seplen;
 			tstr = memdupcat(str, size, sstr, keylen+1);
 			free(sstr);
 			str = tstr;
 
 			size += keylen;
 		}
 	}
 
 	return str;
 }
 
 llist_t *
 llist_genrange(int begin, int end, int step)
 {
 	llist_t *llist;
 	int i, min, max;
 
 	if (begin == end)
 		return NULL;
 
 	max = (begin > end)? begin : end;
 	min = (begin > end)? end : begin;
 
 	llist = llist_new();
 	for (i = min; i < max; i += step)
 		llist_addraw(llist, smprintf("%d", i), NULL, 0);
 
 	return llist;
 }
 
 int
 llist_strcmp(llistelem_t *elem1, llistelem_t *elem2)
 {
 	return strcmp(elem1->key, elem2->key);
 }
 
 int
 llist_intcmp(llistelem_t *elem1, llistelem_t *elem2)
 {
 	return atoi(elem1->key) - atoi(elem2->key);
 }
 
 /* Taken from:
  * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
  *
  *
  * This following algorithm is copyright 2001 Simon Tatham.
  *
  * Permission is hereby granted, free of charge, to any person
  * obtaining a copy of this software and associated documentation
  * files (the "Software"), to deal in the Software without
  * restriction, including without limitation the rights to use,
  * copy, modify, merge, publish, distribute, sublicense, and/or
  * sell copies of the Software, and to permit persons to whom the
  * Software is furnished to do so, subject to the following
  * conditions:
  *
  * The above copyright notice and this permission notice shall be
  * included in all copies or substantial portions of the Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  */
 
 llist_t *
 llist_internsort(llist_t *llist, int (*cmp)(llistelem_t *, llistelem_t *))
 {
 	llistelem_t *p, *q, *e, *tail;
 	int insize, nmerges, psize, qsize, i;
 
 	insize = 1;
 	for (;;) {
 		p = llist->first;
 		llist->first = NULL;
 		tail = NULL;
 
 		nmerges = 0;
 
 		while(p) {
 			nmerges++;
 
 			q = p;
 			psize = 0;
 			for (i = 0; i < insize; i++) {
 				psize++;
 				q = q->next;
 				if (!q)
 					break;
 			}
 
 			qsize = insize;
 			while (psize > 0 || (qsize > 0 && q)) {
 				if (psize == 0) {
 					e = q;
 					q = q->next;
 					qsize--;
 				} else if (qsize == 0 || !q) {
 					e = p;
 					p = p->next;
 					psize--;
 				} else if (cmp(p, q) <= 0) {
 					e = p;
 					p = p->next;
 					psize--;
 				} else {
 					e = q;
 					q = q->next;
 					qsize--;
 				}
 
 				if (tail)
 					tail->next = e;
 				else
 					llist->first = e;
 				e->prev = tail;
 				tail = e;
 			}
 			p = q;
 		}
 		tail->next = NULL;
 
 		if (nmerges <= 1)
 			return llist;
 
 		insize *= 2;
 	}
 }
 
 llist_t *
 llist_sort(llist_t *llist)
 {
 	return llist_internsort(llist, llist_strcmp);
 }
 
 llist_t *
 llist_intsort(llist_t *llist)
 {
 	return llist_internsort(llist, llist_intcmp);
 }