rohrpost

A commandline mail client to change the world as we see it.
git clone git://r-36.net/rohrpost
Log | Files | Refs | README | 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