2 * Copyright © 2002, 2003 Sun Microsystems, Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of Sun Microsystems, Inc. nor the names of
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
20 * This software is provided "AS IS," without a warranty of any kind.
22 * ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
23 * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
24 * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED.
25 * SUN AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES OR
26 * LIABILITIES SUFFERED BY LICENSEE AS A RESULT OF OR RELATING TO USE,
27 * MODIFICATION OR DISTRIBUTION OF THE SOFTWARE OR ITS DERIVATIVES.
28 * IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE,
29 * PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
30 * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE
31 * THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE
32 * SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
37 /* @(#)list.c 1.7 03/02/06 SMI */
41 * @brief Bidirectional list class
42 * @author Alexander Gelfenbain
51 #include </usr/local/include/malloc.h>
55 /*- private data types */
56 typedef struct _lnode {
65 lnode *head, *tail, *cptr;
67 void (*eDtor)(void *);
70 /*- private methods */
72 static lnode *newNode(void *el)
74 lnode *ptr = malloc(sizeof(lnode));
82 static lnode *appendPrim(list this, void *el)
84 lnode *ptr = newNode(el);
85 lnode **flink, *blink;
87 if (this->tail != 0) {
88 flink = &(this->tail->next);
93 this->cptr = ptr; /*- list was empty - set current to this element */
106 static lnode *prependPrim(list this, void *el)
108 lnode *ptr = newNode(el);
109 lnode *flink, **blink;
111 if (this->head != 0) {
112 blink = &(this->head->prev);
117 this->cptr = ptr; /*- list was empty - set current to this element */
131 /*- public methods */
132 list listNewEmpty(void) /*- default ctor */
134 list this = malloc(sizeof(struct _list));
139 this->head = this->tail = this->cptr = NULL;
144 list listNewCopy(list l) /*- copy ctor */
150 this = malloc(sizeof(struct _list));
157 this->head = this->tail = this->cptr = NULL;
160 c = appendPrim(this, ptr->value);
161 if (ptr == l->cptr) this->cptr = c;
168 list listNewConcat(list lhs, list rhs)
176 this = malloc(sizeof(struct _list));
182 this->head = this->tail = this->cptr = NULL;
186 c = appendPrim(this, ptr->value);
192 c = appendPrim(this, ptr->value);
196 this->cptr = this->head;
207 void listDispose(list this) /*- dtor */
214 void listSetElementDtor(list this, GDestroyNotify f)
221 list listCopy(list to, list from) /*- assignment */
231 c = appendPrim(to, ptr->value);
232 if (ptr == from->cptr) to->cptr = c;
240 /* calling this function on an empty list is a run-time error */
241 void *listCurrent(list this)
244 assert(this->cptr != 0);
245 return this->cptr->value;
248 int listCount(list this)
254 int listIsEmpty(list this)
257 return this->aCount == 0;
261 int listAtFirst(list this)
264 return this->cptr == this->head;
267 int listAtLast(list this)
270 return this->cptr == this->tail;
273 int listPosition(list this)
281 while (ptr != this->cptr) {
289 int listFind(list this, void *el)
297 if (ptr->value == el) {
307 int listNext(list this)
309 return listSkipForward(this, 1);
312 int listPrev(list this)
314 return listSkipBackward(this, 1);
317 int listSkipForward(list this, int n)
322 if (this->cptr == 0) return 0;
325 if (this->cptr->next == 0) break;
326 this->cptr = this->cptr->next;
333 int listSkipBackward(list this, int n)
338 if (this->cptr == 0) return 0;
341 if (this->cptr->prev == 0) break;
342 this->cptr = this->cptr->prev;
349 int listToFirst(list this)
353 if (this->cptr != this->head) {
354 this->cptr = this->head;
360 int listToLast(list this)
364 if (this->cptr != this->tail) {
365 this->cptr = this->tail;
371 int listPositionAt(list this, int n) /*- returns the actual position number */
376 this->cptr = this->head;
378 if (this->cptr->next == 0) break;
379 this->cptr = this->cptr->next;
386 list listAppend(list this, void *el)
390 appendPrim(this, el);
394 list listConcat(list lhs, list rhs)
403 appendPrim(lhs, ptr->value);
411 list listPrepend(list this, void *el)
415 prependPrim(this, el);
419 list listInsertAfter(list this, void *el)
424 if (this->cptr == 0) return listAppend(this, el);
428 ptr->prev = this->cptr;
429 ptr->next = this->cptr->next;
430 this->cptr->next = ptr;
432 if (ptr->next != 0) {
433 ptr->next->prev = ptr;
441 list listInsertBefore(list this, void *el)
446 if (this->cptr == 0) return listAppend(this, el);
450 ptr->prev = this->cptr->prev;
451 ptr->next = this->cptr;
452 this->cptr->prev = ptr;
454 if (ptr->prev != 0) {
455 ptr->prev->next = ptr;
463 list listRemove(list this)
466 if (this->cptr == 0) return this;
468 if (this->cptr->next != 0) {
469 ptr = this->cptr->next;
470 this->cptr->next->prev = this->cptr->prev;
472 this->tail = this->cptr->prev;
475 if (this->cptr->prev != 0) {
476 if (ptr == 0) ptr = this->cptr->prev;
477 this->cptr->prev->next = this->cptr->next;
479 this->head = this->cptr->next;
482 if (this->eDtor) this->eDtor(this->cptr->value); /* call the dtor callback */
490 list listClear(list this)
492 lnode *node = this->head, *ptr;
496 if (this->eDtor) this->eDtor(node->value); /* call the dtor callback */
502 this->head = this->tail = this->cptr = NULL;
503 assert(this->aCount == 0);
507 void listForAll(list this, void (*f)(void *))
509 lnode *ptr = this->head;
516 void **listToArray(list this)
519 lnode *ptr = this->head;
522 assert(this->aCount != 0);
523 res = calloc(this->aCount, sizeof(void *));
527 res[i++] = ptr->value;
538 void printlist(list l)
542 saved = listPosition(l);
546 if (!listIsEmpty(l)) {
549 printf("%d ", (int) listCurrent(l));
550 } while (listNext(l));
555 listPositionAt(l, saved);
558 void printstringlist(list l)
562 saved = listPosition(l);
566 if (!listIsEmpty(l)) {
569 printf("'%s' ", (char *) listCurrent(l));
570 } while (listNext(l));
575 listPositionAt(l, saved);
578 void printstat(list l)
580 printf("count: %d, position: %d, isEmpty: %d, atFirst: %d, atLast: %d.\n",
581 listCount(l), listPosition(l), listIsEmpty(l), listAtFirst(l), listAtLast(l));
584 void allfunc(void *e)
589 void edtor(void *ptr)
591 printf("element dtor: 0x%08x\n", ptr);
621 listInsertBefore(l1, -5);
625 l2 = listNewCopy(l1);
629 l3 = listNewConcat(l1, l2);
639 listForAll(l2, allfunc);
643 listSetElementDtor(l1, edtor);
645 for(i=0; i<10; i++) {
647 sprintf(ptr, "element # %d", i);
659 mal_dumpleaktrace(stdout);