00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <stdlib.h>
00023 #include <stddef.h>
00024 #include <assert.h>
00025 #define llist_IMPLEMENTATION
00026 #include "list.h"
00027
00028 #define next llist_next
00029 #define prev llist_prev
00030 #define data llist_data
00031
00032 #define pool llist_pool
00033 #define fre llist_free
00034 #define size llist_size
00035
00036 #define nilnode llist_nilnode
00037 #define nodecount llist_nodecount
00038 #define maxcount llist_maxcount
00039
00040 #define llist_nil(L) (&(L)->nilnode)
00041 #define llist_first_priv(L) ((L)->nilnode.next)
00042 #define llist_last_priv(L) ((L)->nilnode.prev)
00043 #define llnode_next(N) ((N)->next)
00044 #define llnode_prev(N) ((N)->prev)
00045
00046 #ifdef KAZLIB_RCSID
00047 static const char rcsid[] = "$Id: list.c,v 1.3 2000/03/23 19:30:30 ndevilla Exp $";
00048 #endif
00049
00050
00051 #include "memory.h"
00052
00053
00054
00055
00056
00057
00058
00059
00060 llist_t *llist_init(llist_t *list, listcount_t maxcount)
00061 {
00062 assert (maxcount != 0);
00063 list->nilnode.next = &list->nilnode;
00064 list->nilnode.prev = &list->nilnode;
00065 list->nodecount = 0;
00066 list->maxcount = maxcount;
00067 return list;
00068 }
00069
00070
00071
00072
00073
00074
00075
00076 llist_t *llist_create(listcount_t maxcount)
00077 {
00078 llist_t *new = malloc(sizeof *new);
00079 if (new) {
00080 assert (maxcount != 0);
00081 new->nilnode.next = &new->nilnode;
00082 new->nilnode.prev = &new->nilnode;
00083 new->nodecount = 0;
00084 new->maxcount = maxcount;
00085 }
00086 return new;
00087 }
00088
00089
00090
00091
00092
00093
00094 void llist_destroy(llist_t *list)
00095 {
00096 assert (llist_isempty(list));
00097 free(list);
00098 }
00099
00100
00101
00102
00103
00104
00105
00106 void llist_destroy_nodes(llist_t *list)
00107 {
00108 llnode_t *lnode = llist_first_priv(list), *nil = llist_nil(list), *tmp;
00109
00110 while (lnode != nil) {
00111 tmp = lnode->next;
00112 lnode->next = NULL;
00113 lnode->prev = NULL;
00114 llnode_destroy(lnode);
00115 lnode = tmp;
00116 }
00117
00118 llist_init(list, list->maxcount);
00119 }
00120
00121
00122
00123
00124
00125
00126 void llist_return_nodes(llist_t *list, lnodepool_t *pool)
00127 {
00128 llnode_t *lnode = llist_first_priv(list), *tmp, *nil = llist_nil(list);
00129
00130 while (lnode != nil) {
00131 tmp = lnode->next;
00132 lnode->next = NULL;
00133 lnode->prev = NULL;
00134 llnode_return(pool, lnode);
00135 lnode = tmp;
00136 }
00137
00138 llist_init(list, list->maxcount);
00139 }
00140
00141
00142
00143
00144
00145 void llist_ins_after(llist_t *list, llnode_t *new, llnode_t *this)
00146 {
00147 llnode_t *that = this->next;
00148
00149 assert (new != NULL);
00150 assert (!llist_contains(list, new));
00151 assert (!llnode_is_in_a_list(new));
00152 assert (this == llist_nil(list) || llist_contains(list, this));
00153 assert (list->nodecount + 1 > list->nodecount);
00154
00155 new->prev = this;
00156 new->next = that;
00157 that->prev = new;
00158 this->next = new;
00159 list->nodecount++;
00160
00161 assert (list->nodecount <= list->maxcount);
00162 }
00163
00164
00165
00166
00167
00168 void llist_ins_before(llist_t *list, llnode_t *new, llnode_t *this)
00169 {
00170 llnode_t *that = this->prev;
00171
00172 assert (new != NULL);
00173 assert (!llist_contains(list, new));
00174 assert (!llnode_is_in_a_list(new));
00175 assert (this == llist_nil(list) || llist_contains(list, this));
00176 assert (list->nodecount + 1 > list->nodecount);
00177
00178 new->next = this;
00179 new->prev = that;
00180 that->next = new;
00181 this->prev = new;
00182 list->nodecount++;
00183
00184 assert (list->nodecount <= list->maxcount);
00185 }
00186
00187
00188
00189
00190
00191 llnode_t *llist_delete(llist_t *list, llnode_t *del)
00192 {
00193 llnode_t *next = del->next;
00194 llnode_t *prev = del->prev;
00195
00196 assert (llist_contains(list, del));
00197
00198 prev->next = next;
00199 next->prev = prev;
00200 list->nodecount--;
00201
00202 del->next = del->prev = NULL;
00203
00204 return del;
00205 }
00206
00207
00208
00209
00210
00211
00212
00213 void llist_process(llist_t *list, void *context,
00214 void (* function)(llist_t *list, llnode_t *lnode, void *context))
00215 {
00216 llnode_t *node = llist_first_priv(list), *next, *nil = llist_nil(list);
00217
00218 while (node != nil) {
00219
00220
00221 assert (llist_contains(list, node));
00222 next = node->next;
00223 function(list, node, context);
00224 node = next;
00225 }
00226 }
00227
00228
00229
00230
00231
00232 llnode_t *llnode_create(void *data)
00233 {
00234 llnode_t *new = malloc(sizeof *new);
00235 if (new) {
00236 new->data = data;
00237 new->next = NULL;
00238 new->prev = NULL;
00239 }
00240 return new;
00241 }
00242
00243
00244
00245
00246
00247 llnode_t *llnode_init(llnode_t *lnode, void *data)
00248 {
00249 lnode->data = data;
00250 lnode->next = NULL;
00251 lnode->prev = NULL;
00252 return lnode;
00253 }
00254
00255
00256
00257
00258
00259 void llnode_destroy(llnode_t *lnode)
00260 {
00261 assert (!llnode_is_in_a_list(lnode));
00262 free(lnode);
00263 }
00264
00265
00266
00267
00268
00269
00270
00271 lnodepool_t *llnode_pool_init(lnodepool_t *pool, llnode_t *nodes, listcount_t n)
00272 {
00273 listcount_t i;
00274
00275 assert (n != 0);
00276
00277 pool->pool = nodes;
00278 pool->fre = nodes;
00279 pool->size = n;
00280 for (i = 0; i < n - 1; i++) {
00281 nodes[i].next = nodes + i + 1;
00282 }
00283 nodes[i].next = NULL;
00284 nodes[i].prev = nodes;
00285 return pool;
00286 }
00287
00288
00289
00290
00291
00292 lnodepool_t *llnode_pool_create(listcount_t n)
00293 {
00294 lnodepool_t *pool;
00295 llnode_t *nodes;
00296
00297 assert (n != 0);
00298
00299 pool = malloc(sizeof *pool);
00300 if (!pool)
00301 return NULL;
00302 nodes = malloc(n * sizeof *nodes);
00303 if (!nodes) {
00304 free(pool);
00305 return NULL;
00306 }
00307 llnode_pool_init(pool, nodes, n);
00308 return pool;
00309 }
00310
00311
00312
00313
00314
00315 int llnode_pool_isfrom(lnodepool_t *pool, llnode_t *node)
00316 {
00317 listcount_t i;
00318
00319
00320
00321
00322
00323 for (i = 0; i < pool->size; i++) {
00324 if (pool->pool + i == node)
00325 return 1;
00326 }
00327 return 0;
00328 }
00329
00330
00331
00332
00333
00334 void llnode_pool_destroy(lnodepool_t *p)
00335 {
00336 free(p->pool);
00337 free(p);
00338 }
00339
00340
00341
00342
00343
00344
00345 llnode_t *llnode_borrow(lnodepool_t *pool, void *data)
00346 {
00347 llnode_t *new = pool->fre;
00348 if (new) {
00349 pool->fre = new->next;
00350 new->data = data;
00351 new->next = NULL;
00352 new->prev = NULL;
00353 }
00354 return new;
00355 }
00356
00357
00358
00359
00360
00361
00362 void llnode_return(lnodepool_t *pool, llnode_t *node)
00363 {
00364 assert (llnode_pool_isfrom(pool, node));
00365 assert (!llnode_is_in_a_list(node));
00366
00367 node->next = pool->fre;
00368 node->prev = node;
00369 pool->fre = node;
00370 }
00371
00372
00373
00374
00375
00376
00377 int llist_contains(llist_t *list, llnode_t *node)
00378 {
00379 llnode_t *n, *nil = llist_nil(list);
00380
00381 for (n = llist_first_priv(list); n != nil; n = llnode_next(n)) {
00382 if (node == n)
00383 return 1;
00384 }
00385
00386 return 0;
00387 }
00388
00389
00390
00391
00392
00393
00394
00395 void llist_extract(llist_t *dest, llist_t *source, llnode_t *first, llnode_t *last)
00396 {
00397 listcount_t moved = 1;
00398
00399 assert (first == NULL || llist_contains(source, first));
00400 assert (last == NULL || llist_contains(source, last));
00401
00402 if (first == NULL || last == NULL)
00403 return;
00404
00405
00406
00407 first->prev->next = last->next;
00408 last->next->prev = first->prev;
00409
00410
00411
00412 last->next = &dest->nilnode;
00413 first->prev = dest->nilnode.prev;
00414 dest->nilnode.prev->next = first;
00415 dest->nilnode.prev = last;
00416
00417 while (first != last) {
00418 first = first->next;
00419 assert (first != llist_nil(source));
00420 moved++;
00421 }
00422
00423
00424 assert (source->nodecount - moved <= source->nodecount);
00425 assert (dest->nodecount + moved >= dest->nodecount);
00426
00427
00428 assert (moved <= source->nodecount);
00429
00430 source->nodecount -= moved;
00431 dest->nodecount += moved;
00432
00433
00434 assert (llist_verify(source));
00435 assert (llist_verify(dest));
00436 }
00437
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447 void llist_transfer(llist_t *dest, llist_t *source, llnode_t *first)
00448 {
00449 listcount_t moved = 1;
00450 llnode_t *last;
00451
00452 assert (first == NULL || llist_contains(source, first));
00453
00454 if (first == NULL)
00455 return;
00456
00457 last = source->nilnode.prev;
00458
00459 source->nilnode.prev = first->prev;
00460 first->prev->next = &source->nilnode;
00461
00462 last->next = &dest->nilnode;
00463 first->prev = dest->nilnode.prev;
00464 dest->nilnode.prev->next = first;
00465 dest->nilnode.prev = last;
00466
00467 while (first != last) {
00468 first = first->next;
00469 moved++;
00470 }
00471
00472
00473 assert (source->nodecount - moved <= source->nodecount);
00474 assert (dest->nodecount + moved >= dest->nodecount);
00475
00476
00477 assert (moved <= source->nodecount);
00478
00479 source->nodecount -= moved;
00480 dest->nodecount += moved;
00481
00482
00483 assert (llist_verify(source));
00484 assert (llist_verify(dest));
00485 }
00486
00487 void llist_merge(llist_t *dest, llist_t *sour,
00488 int compare (const void *, const void *))
00489 {
00490 llnode_t *dn, *sn, *tn;
00491 llnode_t *d_nil = llist_nil(dest), *s_nil = llist_nil(sour);
00492
00493
00494 assert (llist_count(sour) + llist_count(dest) > llist_count(sour));
00495
00496
00497 assert (llist_is_sorted(sour, compare));
00498 assert (llist_is_sorted(dest, compare));
00499
00500 dn = llist_first_priv(dest);
00501 sn = llist_first_priv(sour);
00502
00503 while (dn != d_nil && sn != s_nil) {
00504 if (compare(llnode_get(dn), llnode_get(sn)) >= 0) {
00505 tn = llnode_next(sn);
00506 llist_delete(sour, sn);
00507 llist_ins_before(dest, sn, dn);
00508 sn = tn;
00509 } else {
00510 dn = llnode_next(dn);
00511 }
00512 }
00513
00514 if (dn != d_nil)
00515 return;
00516
00517 if (sn != s_nil)
00518 llist_transfer(dest, sour, sn);
00519 }
00520
00521 void llist_sort(llist_t *list, int compare(const void *, const void *))
00522 {
00523 llist_t extra;
00524 listcount_t middle;
00525 llnode_t *node;
00526
00527 if (llist_count(list) > 1) {
00528 middle = llist_count(list) / 2;
00529 node = llist_first_priv(list);
00530
00531 llist_init(&extra, llist_count(list) - middle);
00532
00533 while (middle--)
00534 node = llnode_next(node);
00535
00536 llist_transfer(&extra, list, node);
00537 llist_sort(list, compare);
00538 llist_sort(&extra, compare);
00539 llist_merge(list, &extra, compare);
00540 }
00541 assert (llist_is_sorted(list, compare));
00542 }
00543
00544 llnode_t *llist_find(llist_t *list, const void *key, int compare(const void *, const void *))
00545 {
00546 llnode_t *node;
00547
00548 for (node = llist_first_priv(list); node != llist_nil(list); node = node->next) {
00549 if (compare(llnode_get(node), key) == 0)
00550 return node;
00551 }
00552
00553 return 0;
00554 }
00555
00556
00557
00558
00559
00560
00561 int llist_is_sorted(llist_t *list, int compare(const void *, const void *))
00562 {
00563 llnode_t *node, *next, *nil;
00564
00565 next = nil = llist_nil(list);
00566 node = llist_first_priv(list);
00567
00568 if (node != nil)
00569 next = llnode_next(node);
00570
00571 for (; next != nil; node = next, next = llnode_next(next)) {
00572 if (compare(llnode_get(node), llnode_get(next)) > 0)
00573 return 0;
00574 }
00575
00576 return 1;
00577 }
00578
00579
00580
00581
00582
00583
00584 #undef llist_isempty
00585 #undef llist_isfull
00586 #undef llnode_pool_isempty
00587 #undef llist_append
00588 #undef llist_prepend
00589 #undef llist_first
00590 #undef llist_last
00591 #undef llist_next
00592 #undef llist_prev
00593 #undef llist_count
00594 #undef llist_del_first
00595 #undef llist_del_last
00596 #undef llnode_put
00597 #undef llnode_get
00598
00599
00600
00601
00602
00603 int llist_isempty(llist_t *list)
00604 {
00605 return list->nodecount == 0;
00606 }
00607
00608
00609
00610
00611
00612
00613 int llist_isfull(llist_t *list)
00614 {
00615 return list->nodecount == list->maxcount;
00616 }
00617
00618
00619
00620
00621
00622 int llnode_pool_isempty(lnodepool_t *pool)
00623 {
00624 return (pool->fre == NULL);
00625 }
00626
00627
00628
00629
00630
00631 void llist_append(llist_t *list, llnode_t *node)
00632 {
00633 llist_ins_before(list, node, &list->nilnode);
00634 }
00635
00636
00637
00638
00639
00640 void llist_prepend(llist_t *list, llnode_t *node)
00641 {
00642 llist_ins_after(list, node, &list->nilnode);
00643 }
00644
00645
00646
00647
00648
00649 llnode_t *llist_first(llist_t *list)
00650 {
00651 if (list->nilnode.next == &list->nilnode)
00652 return NULL;
00653 return list->nilnode.next;
00654 }
00655
00656
00657
00658
00659
00660 llnode_t *llist_last(llist_t *list)
00661 {
00662 if (list->nilnode.prev == &list->nilnode)
00663 return NULL;
00664 return list->nilnode.prev;
00665 }
00666
00667
00668
00669
00670
00671 listcount_t llist_count(llist_t *list)
00672 {
00673 return list->nodecount;
00674 }
00675
00676
00677
00678
00679
00680 llnode_t *llist_del_first(llist_t *list)
00681 {
00682 return llist_delete(list, list->nilnode.next);
00683 }
00684
00685
00686
00687
00688
00689 llnode_t *llist_del_last(llist_t *list)
00690 {
00691 return llist_delete(list, list->nilnode.prev);
00692 }
00693
00694
00695
00696
00697
00698
00699 void llnode_put(llnode_t *lnode, void *data)
00700 {
00701 lnode->data = data;
00702 }
00703
00704
00705
00706
00707
00708 void *llnode_get(llnode_t *lnode)
00709 {
00710 return lnode->data;
00711 }
00712
00713
00714
00715
00716
00717
00718 llnode_t *llist_next(llist_t *list, llnode_t *lnode)
00719 {
00720 assert (llist_contains(list, lnode));
00721
00722 if (lnode->next == llist_nil(list))
00723 return NULL;
00724 return lnode->next;
00725 }
00726
00727
00728
00729
00730
00731 llnode_t *llist_prev(llist_t *list, llnode_t *lnode)
00732 {
00733 assert (llist_contains(list, lnode));
00734
00735 if (lnode->prev == llist_nil(list))
00736 return NULL;
00737 return lnode->prev;
00738 }
00739
00740
00741
00742
00743
00744 int llnode_is_in_a_list(llnode_t *lnode)
00745 {
00746 return (lnode->next != NULL || lnode->prev != NULL);
00747 }
00748
00749
00750 int llist_verify(llist_t *list)
00751 {
00752 llnode_t *node = llist_first_priv(list), *nil = llist_nil(list);
00753 listcount_t count = llist_count(list);
00754
00755 if (node->prev != nil)
00756 return 0;
00757
00758 if (count > list->maxcount)
00759 return 0;
00760
00761 while (node != nil && count--) {
00762 if (node->next->prev != node)
00763 return 0;
00764 node = node->next;
00765 }
00766
00767 if (count != 0 || node != nil)
00768 return 0;
00769
00770 return 1;
00771 }
00772
00773 #ifdef KAZLIB_TEST_MAIN
00774
00775 #include <stdio.h>
00776 #include <string.h>
00777 #include <ctype.h>
00778 #include <stdarg.h>
00779
00780 typedef char input_t[256];
00781
00782 static int tokenize(char *string, ...)
00783 {
00784 char **tokptr;
00785 va_list arglist;
00786 int tokcount = 0;
00787
00788 va_start(arglist, string);
00789 tokptr = va_arg(arglist, char **);
00790 while (tokptr) {
00791 while (*string && isspace((unsigned char) *string))
00792 string++;
00793 if (!*string)
00794 break;
00795 *tokptr = string;
00796 while (*string && !isspace((unsigned char) *string))
00797 string++;
00798 tokptr = va_arg(arglist, char **);
00799 tokcount++;
00800 if (!*string)
00801 break;
00802 *string++ = 0;
00803 }
00804 va_end(arglist);
00805
00806 return tokcount;
00807 }
00808
00809 static int comparef(const void *key1, const void *key2)
00810 {
00811 return strcmp(key1, key2);
00812 }
00813
00814 static char *dupstring(char *str)
00815 {
00816 int sz = strlen(str) + 1;
00817 char *new = malloc(sz);
00818 if (new)
00819 memcpy(new, str, sz);
00820 return new;
00821 }
00822
00823 int main(void)
00824 {
00825 input_t in;
00826 llist_t *l = llist_create(LISTCOUNT_T_MAX);
00827 llnode_t *ln;
00828 char *tok1, *val;
00829 int prompt = 0;
00830
00831 char *help =
00832 "a <val> append value to list\n"
00833 "d <val> delete value from list\n"
00834 "l <val> lookup value in list\n"
00835 "s sort list\n"
00836 "c show number of entries\n"
00837 "t dump whole list\n"
00838 "p turn prompt on\n"
00839 "q quit";
00840
00841 if (!l)
00842 puts("llist_create failed");
00843
00844 for (;;) {
00845 if (prompt)
00846 putchar('>');
00847 fflush(stdout);
00848
00849 if (!fgets(in, sizeof(input_t), stdin))
00850 break;
00851
00852 switch(in[0]) {
00853 case '?':
00854 puts(help);
00855 break;
00856 case 'a':
00857 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
00858 puts("what?");
00859 break;
00860 }
00861 val = dupstring(tok1);
00862 ln = llnode_create(val);
00863
00864 if (!val || !ln) {
00865 puts("allocation failure");
00866 if (ln)
00867 llnode_destroy(ln);
00868 free(val);
00869 break;
00870 }
00871
00872 llist_append(l, ln);
00873 break;
00874 case 'd':
00875 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
00876 puts("what?");
00877 break;
00878 }
00879 ln = llist_find(l, tok1, comparef);
00880 if (!ln) {
00881 puts("llist_find failed");
00882 break;
00883 }
00884 llist_delete(l, ln);
00885 val = llnode_get(ln);
00886 llnode_destroy(ln);
00887 free(val);
00888 break;
00889 case 'l':
00890 if (tokenize(in+1, &tok1, (char **) 0) != 1) {
00891 puts("what?");
00892 break;
00893 }
00894 ln = llist_find(l, tok1, comparef);
00895 if (!ln)
00896 puts("llist_find failed");
00897 else
00898 puts("found");
00899 break;
00900 case 's':
00901 llist_sort(l, comparef);
00902 break;
00903 case 'c':
00904 printf("%lu\n", (unsigned long) llist_count(l));
00905 break;
00906 case 't':
00907 for (ln = llist_first(l); ln != 0; ln = llist_next(l, ln))
00908 puts(llnode_get(ln));
00909 break;
00910 case 'q':
00911 exit(0);
00912 break;
00913 case '\0':
00914 break;
00915 case 'p':
00916 prompt = 1;
00917 break;
00918 default:
00919 putchar('?');
00920 putchar('\n');
00921 break;
00922 }
00923 }
00924
00925 return 0;
00926 }
00927
00928 #endif