src/ttsubset/list.c

   1 /*
   2  * Copyright © 2002, 2003 Sun Microsystems, Inc.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  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.
  15  *
  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.
  19  *
  20  * This software is provided "AS IS," without a warranty of any kind.
  21  *
  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.
  33  *
  34  */
  35
  36 /* $Id$ */
  37 /* @(#)list.c 1.7 03/02/06 SMI */
  38
  39 /*
  40  * @file list.c
  41  * @brief Bidirectional list class
  42  * @author Alexander Gelfenbain
  43  * @version 1.0
  44  *
  45  */
  46
  47 #include <stdlib.h>
  48 #include <assert.h>
  49 #ifdef MALLOC_TRACE
  50 #include <stdio.h>
  51 #include </usr/local/include/malloc.h>
  52 #endif
  53 #include "list.h"
  54
  55 /*- private data types */
  56 typedef struct _lnode {
  57     struct _lnode *next;
  58     struct _lnode *prev;
  59
  60     void *value;
  61
  62 } lnode;
  63
  64 struct _list {
  65     lnode *head, *tail, *cptr;
  66     size_t aCount;
  67     void (*eDtor)(void *);
  68 };
  69
  70 /*- private methods */
  71
  72 static lnode *newNode(void *el)
  73 {
  74     lnode *ptr = malloc(sizeof(lnode));
  75     assert(ptr != 0);
  76
  77     ptr->value = el;
  78
  79     return ptr;
  80 }
  81
  82 static lnode *appendPrim(list this, void *el)
  83 {
  84     lnode *ptr = newNode(el);
  85     lnode **flink, *blink;
  86
  87     if (this->tail != 0) {
  88         flink = &(this->tail->next);
  89         blink = this->tail;
  90     } else {
  91         flink = &this->head;
  92         blink = NULL;
  93         this->cptr = ptr;                         /*- list was empty - set current to this element */
  94     }
  95
  96     *flink  = ptr;
  97     this->tail = ptr;
  98
  99     ptr->prev = blink;
 100     ptr->next = NULL;
 101
 102     this->aCount++;
 103     return ptr;
 104 }
 105
 106 static lnode *prependPrim(list this, void *el)
 107 {
 108     lnode *ptr = newNode(el);
 109     lnode *flink, **blink;
 110
 111     if (this->head != 0) {
 112         blink = &(this->head->prev);
 113         flink = this->head;
 114     } else {
 115         blink = &this->tail;
 116         flink = NULL;
 117         this->cptr  = ptr;                        /*- list was empty - set current to this element */
 118     }
 119
 120     *blink = ptr;
 121     this->head   = ptr;
 122
 123     ptr->next = flink;
 124     ptr->prev = NULL;
 125
 126     this->aCount++;
 127     return ptr;
 128 }
 129
 130
 131 /*- public methods  */
 132 list listNewEmpty(void)                           /*- default ctor */
 133 {
 134     list this = malloc(sizeof(struct _list));
 135     assert(this != 0);
 136
 137     this->aCount = 0;
 138     this->eDtor = NULL;
 139     this->head = this->tail = this->cptr = NULL;
 140
 141     return this;
 142 }
 143
 144 list listNewCopy(list l)                          /*- copy ctor */
 145 {
 146     lnode *ptr, *c;
 147     list this;
 148     assert(l != 0);
 149
 150     this = malloc(sizeof(struct _list));
 151     assert(this != 0);
 152
 153     ptr = l->head;
 154
 155     this->aCount = 0;
 156     this->eDtor = NULL;
 157     this->head = this->tail = this->cptr = NULL;
 158
 159     while (ptr) {
 160         c = appendPrim(this, ptr->value);
 161         if (ptr == l->cptr) this->cptr = c;
 162         ptr = ptr->next;
 163     }
 164
 165     return this;
 166 }
 167
 168 list listNewConcat(list lhs, list rhs)
 169 {
 170     lnode *ptr, *c;
 171     list this;
 172
 173     assert(lhs != 0);
 174     assert(rhs != 0);
 175
 176     this = malloc(sizeof(struct _list));
 177     assert(this != 0);
 178
 179
 180     this->aCount = 0;
 181     this->eDtor = NULL;
 182     this->head = this->tail = this->cptr = NULL;
 183
 184     ptr = lhs->head;
 185     while (ptr) {
 186         c = appendPrim(this, ptr->value);
 187         ptr = ptr->next;
 188     }
 189
 190     ptr = rhs->head;
 191     while (ptr) {
 192         c = appendPrim(this, ptr->value);
 193         ptr = ptr->next;
 194     }
 195
 196     this->cptr = this->head;
 197
 198     return this;
 199 }
 200
 201
 202
 203
 204
 205
 206
 207 void listDispose(list this)                       /*- dtor */
 208 {
 209     assert(this != 0);
 210     listClear(this);
 211     free(this);
 212 }
 213
 214 void listSetElementDtor(list this, GDestroyNotify f)
 215 {
 216     assert(this != 0);
 217     this->eDtor = f;
 218 }
 219
 220
 221 list listCopy(list to, list from)                 /*- assignment */
 222 {
 223     lnode *ptr, *c;
 224     assert(to != 0);
 225     assert(from != 0);
 226
 227     listClear(to);
 228     ptr = from->head;
 229
 230     while (ptr) {
 231         c = appendPrim(to, ptr->value);
 232         if (ptr == from->cptr) to->cptr = c;
 233         ptr = ptr->next;
 234     }
 235
 236     return to;
 237 }
 238
 239
 240 /* calling this function on an empty list is a run-time error */
 241 void *listCurrent(list this)
 242 {
 243     assert(this != 0);
 244     assert(this->cptr != 0);
 245     return this->cptr->value;
 246 }
 247
 248 int   listCount(list this)
 249 {
 250     assert(this != 0);
 251     return this->aCount;
 252 }
 253
 254 int   listIsEmpty(list this)
 255 {
 256     assert(this != 0);
 257     return this->aCount == 0;
 258 }
 259
 260
 261 int   listAtFirst(list this)
 262 {
 263     assert(this != 0);
 264     return this->cptr == this->head;
 265 }
 266
 267 int   listAtLast(list this)
 268 {
 269     assert(this != 0);
 270     return this->cptr == this->tail;
 271 }
 272
 273 int   listPosition(list this)
 274 {
 275     int res = 0;
 276     lnode *ptr;
 277     assert(this != 0);
 278
 279     ptr = this->head;
 280
 281     while (ptr != this->cptr) {
 282         ptr = ptr->next;
 283         res++;
 284     }
 285
 286     return res;
 287 }
 288
 289 int    listFind(list this, void *el)
 290 {
 291     lnode *ptr;
 292     assert(this != 0);
 293
 294     ptr = this->head;
 295
 296     while (ptr) {
 297         if (ptr->value == el) {
 298             this->cptr = ptr;
 299             return 1;
 300         }
 301         ptr = ptr->next;
 302     }
 303
 304     return 0;
 305 }
 306
 307 int    listNext(list this)
 308 {
 309     return listSkipForward(this, 1);
 310 }
 311
 312 int    listPrev(list this)
 313 {
 314     return listSkipBackward(this, 1);
 315 }
 316
 317 int    listSkipForward(list this, int n)
 318 {
 319     int m = 0;
 320     assert(this != 0);
 321
 322     if (this->cptr == 0) return 0;
 323
 324     while (n != 0) {
 325         if (this->cptr->next == 0) break;
 326         this->cptr = this->cptr->next;
 327         n--;
 328         m++;
 329     }
 330     return m;
 331 }
 332
 333 int    listSkipBackward(list this, int n)
 334 {
 335     int m = 0;
 336     assert(this != 0);
 337
 338     if (this->cptr == 0) return 0;
 339
 340     while (n != 0) {
 341         if (this->cptr->prev == 0) break;
 342         this->cptr = this->cptr->prev;
 343         n--;
 344         m++;
 345     }
 346     return m;
 347 }
 348
 349 int    listToFirst(list this)
 350 {
 351     assert(this != 0);
 352
 353     if (this->cptr != this->head) {
 354         this->cptr = this->head;
 355         return 1;
 356     }
 357     return 0;
 358 }
 359
 360 int    listToLast(list this)
 361 {
 362     assert(this != 0);
 363
 364     if (this->cptr != this->tail) {
 365         this->cptr = this->tail;
 366         return 1;
 367     }
 368     return 0;
 369 }
 370
 371 int    listPositionAt(list this, int n)                     /*- returns the actual position number */
 372 {
 373     int m = 0;
 374     assert(this != 0);
 375
 376     this->cptr = this->head;
 377     while (n != 0) {
 378         if (this->cptr->next == 0) break;
 379         this->cptr = this->cptr->next;
 380         n--;
 381         m++;
 382     }
 383     return m;
 384 }
 385
 386 list   listAppend(list this, void *el)
 387 {
 388     assert(this != 0);
 389
 390     appendPrim(this, el);
 391     return this;
 392 }
 393
 394 list   listConcat(list lhs, list rhs)
 395 {
 396     lnode *ptr;
 397
 398     assert(lhs != 0);
 399     assert(rhs != 0);
 400
 401     ptr = rhs->head;
 402     while (ptr != 0) {
 403         appendPrim(lhs, ptr->value);
 404         ptr = ptr->next;
 405     }
 406
 407     return lhs;
 408 }
 409
 410
 411 list   listPrepend(list this, void *el)
 412 {
 413     assert(this != 0);
 414
 415     prependPrim(this, el);
 416     return this;
 417 }
 418
 419 list   listInsertAfter(list this, void *el)
 420 {
 421     lnode *ptr;
 422     assert(this != 0);
 423
 424     if (this->cptr == 0) return listAppend(this, el);
 425
 426     ptr = newNode(el);
 427
 428     ptr->prev  = this->cptr;
 429     ptr->next  = this->cptr->next;
 430     this->cptr->next = ptr;
 431
 432     if (ptr->next != 0) {
 433         ptr->next->prev = ptr;
 434     } else {
 435         this->tail = ptr;
 436     }
 437     this->aCount++;
 438     return this;
 439 }
 440
 441 list   listInsertBefore(list this, void *el)
 442 {
 443     lnode *ptr;
 444     assert(this != 0);
 445
 446     if (this->cptr == 0) return listAppend(this, el);
 447
 448     ptr = newNode(el);
 449
 450     ptr->prev  = this->cptr->prev;
 451     ptr->next  = this->cptr;
 452     this->cptr->prev = ptr;
 453
 454     if (ptr->prev != 0) {
 455         ptr->prev->next = ptr;
 456     } else {
 457         this->head = ptr;
 458     }
 459     this->aCount++;
 460     return this;
 461 }
 462
 463 list   listRemove(list this)
 464 {
 465     lnode *ptr = NULL;
 466     if (this->cptr == 0) return this;
 467
 468     if (this->cptr->next != 0) {
 469         ptr  = this->cptr->next;
 470         this->cptr->next->prev = this->cptr->prev;
 471     } else {
 472         this->tail = this->cptr->prev;
 473     }
 474
 475     if (this->cptr->prev != 0) {
 476         if (ptr == 0) ptr = this->cptr->prev;
 477         this->cptr->prev->next = this->cptr->next;
 478     } else {
 479         this->head = this->cptr->next;
 480     }
 481
 482     if (this->eDtor) this->eDtor(this->cptr->value);        /* call the dtor callback */
 483
 484     free(this->cptr);
 485     this->aCount--;
 486     this->cptr = ptr;
 487     return this;
 488 }
 489
 490 list   listClear(list this)
 491 {
 492     lnode *node = this->head, *ptr;
 493
 494     while (node) {
 495         ptr = node->next;
 496         if (this->eDtor) this->eDtor(node->value);           /* call the dtor callback */
 497         free(node);
 498         this->aCount--;
 499         node = ptr;
 500     }
 501
 502     this->head = this->tail = this->cptr = NULL;
 503     assert(this->aCount == 0);
 504     return this;
 505 }
 506
 507 void   listForAll(list this, void (*f)(void *))
 508 {
 509     lnode *ptr = this->head;
 510     while (ptr) {
 511         f(ptr->value);
 512         ptr = ptr->next;
 513     }
 514 }
 515
 516 void **listToArray(list this)
 517 {
 518     void **res;
 519     lnode *ptr = this->head;
 520     int i = 0;
 521
 522     assert(this->aCount != 0);
 523     res = calloc(this->aCount, sizeof(void *));
 524     assert(res != 0);
 525
 526     while (ptr) {
 527         res[i++] = ptr->value;
 528         ptr = ptr->next;
 529     }
 530     return res;
 531 }
 532
 533
 534 /* #define TEST */
 535 #ifdef TEST
 536 #include <stdio.h>
 537
 538 void printlist(list l)
 539 {
 540     int saved;
 541     assert(l != 0);
 542     saved = listPosition(l);
 543
 544     printf("[ ");
 545
 546     if (!listIsEmpty(l)) {
 547         listToFirst(l);
 548         do {
 549             printf("%d ", (int) listCurrent(l));
 550         } while (listNext(l));
 551     }
 552
 553     printf("]\n");
 554
 555     listPositionAt(l, saved);
 556 }
 557
 558 void printstringlist(list l)
 559 {
 560     int saved;
 561     assert(l != 0);
 562     saved = listPosition(l);
 563
 564     printf("[ ");
 565
 566     if (!listIsEmpty(l)) {
 567         listToFirst(l);
 568         do {
 569             printf("'%s' ", (char *) listCurrent(l));
 570         } while (listNext(l));
 571     }
 572
 573     printf("]\n");
 574
 575     listPositionAt(l, saved);
 576 }
 577
 578 void printstat(list l)
 579 {
 580     printf("count: %d, position: %d, isEmpty: %d, atFirst: %d, atLast: %d.\n",
 581            listCount(l), listPosition(l), listIsEmpty(l), listAtFirst(l), listAtLast(l));
 582 }
 583
 584 void allfunc(void *e)
 585 {
 586     printf("%d ", e);
 587 }
 588
 589 void edtor(void *ptr)
 590 {
 591     printf("element dtor: 0x%08x\n", ptr);
 592     free(ptr);
 593 }
 594
 595 int main()
 596 {
 597     list l1, l2, l3;
 598     char *ptr;
 599     int i;
 600
 601 #ifdef MALLOC_TRACE
 602     mal_leaktrace(1);
 603     mal_debug(2);
 604 #endif
 605
 606     l1 = listNewEmpty();
 607     printstat(l1);
 608
 609     listAppend(l1, 1);
 610     printstat(l1);
 611
 612     listAppend(l1, 2);
 613     printstat(l1);
 614
 615     listAppend(l1, 3);
 616     printstat(l1);
 617
 618     printlist(l1);
 619
 620     listToFirst(l1);
 621     listInsertBefore(l1, -5);
 622     printf("l1: ");
 623     printlist(l1);
 624
 625     l2 = listNewCopy(l1);
 626     printf("l2: ");
 627     printlist(l2);
 628
 629     l3 = listNewConcat(l1, l2);
 630
 631     printf("l1 + l2: ");
 632     printlist(l3);
 633
 634     listConcat(l3, l1);
 635     printf("l3 + l1" );
 636     printlist(l3);
 637
 638
 639     listForAll(l2, allfunc);
 640     printf("\n");
 641
 642     listClear(l1);
 643     listSetElementDtor(l1, edtor);
 644
 645     for(i=0; i<10; i++) {
 646         ptr = malloc(20);
 647         sprintf(ptr, "element # %d", i);
 648         listAppend(l1, ptr);
 649     }
 650
 651     printstringlist(l1);
 652
 653
 654     listDispose(l1);
 655     listDispose(l2);
 656     listDispose(l3);
 657
 658 #ifdef MALLOC_TRACE
 659     mal_dumpleaktrace(stdout);
 660 #endif
 661
 662
 663     return 0;
 664 }
 665 #endif