vcl/source/fontsubset/list.c

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * This file is part of OpenOffice.org.
  10  *
  11  * OpenOffice.org is free software: you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License version 3
  13  * only, as published by the Free Software Foundation.
  14  *
  15  * OpenOffice.org is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU Lesser General Public License version 3 for more details
  19  * (a copy is included in the LICENSE file that accompanied this code).
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * version 3 along with OpenOffice.org.  If not, see
  23  * <http://www.openoffice.org/license.html>
  24  * for a copy of the LGPLv3 License.
  25  *
  26  ************************************************************************/
  27
  28 /*[]---------------------------------------------------[]*/
  29 /*|                                                     |*/
  30 /*|     list.c - bidirectional list class               |*/
  31 /*|                                                     |*/
  32 /*|                                                     |*/
  33 /*|  Author: Alexander Gelfenbain                       |*/
  34 /*[]---------------------------------------------------[]*/
  35
  36 #include <stdlib.h>
  37
  38 #if OSL_DEBUG_LEVEL == 0
  39 #  ifndef NDEBUG
  40 #    define NDEBUG
  41 #  endif
  42 #endif
  43
  44 #include <assert.h>
  45
  46 #ifdef MALLOC_TRACE
  47 #include <stdio.h>
  48 #include </usr/local/include/malloc.h>
  49 #endif
  50 /* #define TEST */
  51 #include "list.h"
  52
  53 /*- private data types */
  54 typedef struct _lnode {
  55     struct _lnode *next;
  56     struct _lnode *prev;
  57
  58     void *value;
  59
  60 } lnode;
  61
  62 struct _list {
  63     lnode *head, *tail, *cptr;
  64     size_t aCount;
  65     list_destructor eDtor;
  66 };
  67
  68 /*- private methods */
  69
  70 static lnode *newNode(void *el)
  71 {
  72     lnode *ptr = malloc(sizeof(lnode));
  73     assert(ptr != 0);
  74
  75     ptr->value = el;
  76
  77     return ptr;
  78 }
  79
  80 static lnode *appendPrim(list this, void *el)
  81 {
  82     lnode *ptr = newNode(el);
  83     lnode **flink, *blink;
  84
  85     if (this->tail != 0) {
  86         flink = &(this->tail->next);
  87         blink = this->tail;
  88     } else {
  89         flink = &this->head;
  90         blink = 0;
  91         this->cptr = ptr;                         /*- list was empty - set current to this element */
  92     }
  93
  94     *flink  = ptr;
  95     this->tail = ptr;
  96
  97     ptr->prev = blink;
  98     ptr->next = 0;
  99
 100     this->aCount++;
 101     return ptr;
 102 }
 103 #ifdef TEST
 104 static lnode *prependPrim(list this, void *el)
 105 {
 106     lnode *ptr = newNode(el);
 107     lnode *flink, **blink;
 108
 109     if (this->head != 0) {
 110         blink = &(this->head->prev);
 111         flink = this->head;
 112     } else {
 113         blink = &this->tail;
 114         flink = 0;
 115         this->cptr  = ptr;                        /*- list was empty - set current to this element */
 116     }
 117
 118     *blink = ptr;
 119     this->head   = ptr;
 120
 121     ptr->next = flink;
 122     ptr->prev = 0;
 123
 124     this->aCount++;
 125     return ptr;
 126 }
 127 #endif
 128
 129 /*- public methods  */
 130 list listNewEmpty(void)                           /*- default ctor */
 131 {
 132     list this = malloc(sizeof(struct _list));
 133     assert(this != 0);
 134
 135     this->aCount = 0;
 136     this->eDtor = 0;
 137     this->head = this->tail = this->cptr = 0;
 138
 139     return this;
 140 }
 141
 142 #ifdef TEST
 143 list listNewCopy(list l)                          /*- copy ctor */
 144 {
 145     lnode *ptr, *c;
 146     list this;
 147     assert(l != 0);
 148
 149     this = malloc(sizeof(struct _list));
 150     assert(this != 0);
 151
 152     ptr = l->head;
 153
 154     this->aCount = 0;
 155     this->eDtor = 0;
 156     this->head = this->tail = this->cptr = 0;
 157
 158     while (ptr) {
 159         c = appendPrim(this, ptr->value);
 160         if (ptr == l->cptr) this->cptr = c;
 161         ptr = ptr->next;
 162     }
 163
 164     return this;
 165 }
 166 #endif
 167
 168 void listDispose(list this)                       /*- dtor */
 169 {
 170     assert(this != 0);
 171     listClear(this);
 172     free(this);
 173 }
 174
 175 void listSetElementDtor(list this, list_destructor f)
 176 {
 177     assert(this != 0);
 178     this->eDtor = f;
 179 }
 180
 181 /* calling this function on an empty list is a run-time error */
 182 void *listCurrent(list this)
 183 {
 184     assert(this != 0);
 185     assert(this->cptr != 0);
 186     return this->cptr->value;
 187 }
 188
 189 int   listCount(list this)
 190 {
 191     assert(this != 0);
 192     return this->aCount;
 193 }
 194
 195 int   listIsEmpty(list this)
 196 {
 197     assert(this != 0);
 198     return this->aCount == 0;
 199 }
 200
 201
 202 #ifdef TEST
 203 int   listAtFirst(list this)
 204 {
 205     assert(this != 0);
 206     return this->cptr == this->head;
 207 }
 208
 209 int   listAtLast(list this)
 210 {
 211     assert(this != 0);
 212     return this->cptr == this->tail;
 213 }
 214
 215 int   listPosition(list this)
 216 {
 217     int res = 0;
 218     lnode *ptr;
 219     assert(this != 0);
 220
 221     ptr = this->head;
 222
 223     while (ptr != this->cptr) {
 224         ptr = ptr->next;
 225         res++;
 226     }
 227
 228     return res;
 229 }
 230 #endif
 231 int    listFind(list this, void *el)
 232 {
 233     lnode *ptr;
 234     assert(this != 0);
 235
 236     ptr = this->head;
 237
 238     while (ptr) {
 239         if (ptr->value == el) {
 240             this->cptr = ptr;
 241             return 1;
 242         }
 243         ptr = ptr->next;
 244     }
 245
 246     return 0;
 247 }
 248
 249 int    listNext(list this)
 250 {
 251     return listSkipForward(this, 1);
 252 }
 253
 254 int    listSkipForward(list this, int n)
 255 {
 256     int m = 0;
 257     assert(this != 0);
 258
 259     if (this->cptr == 0) return 0;
 260
 261     while (n != 0) {
 262         if (this->cptr->next == 0) break;
 263         this->cptr = this->cptr->next;
 264         n--;
 265         m++;
 266     }
 267     return m;
 268 }
 269
 270 int    listToFirst(list this)
 271 {
 272     assert(this != 0);
 273
 274     if (this->cptr != this->head) {
 275         this->cptr = this->head;
 276         return 1;
 277     }
 278     return 0;
 279 }
 280
 281 int    listToLast(list this)
 282 {
 283     assert(this != 0);
 284
 285     if (this->cptr != this->tail) {
 286         this->cptr = this->tail;
 287         return 1;
 288     }
 289     return 0;
 290 }
 291
 292 int    listPositionAt(list this, int n)                     /*- returns the actual position number */
 293 {
 294     int m = 0;
 295     assert(this != 0);
 296
 297     this->cptr = this->head;
 298     while (n != 0) {
 299         if (this->cptr->next == 0) break;
 300         this->cptr = this->cptr->next;
 301         n--;
 302         m++;
 303     }
 304     return m;
 305 }
 306
 307 list   listAppend(list this, void *el)
 308 {
 309     assert(this != 0);
 310
 311     appendPrim(this, el);
 312     return this;
 313 }
 314 #ifdef TEST
 315 list   listPrepend(list this, void *el)
 316 {
 317     assert(this != 0);
 318
 319     prependPrim(this, el);
 320     return this;
 321 }
 322
 323 list   listInsertAfter(list this, void *el)
 324 {
 325     lnode *ptr;
 326     assert(this != 0);
 327
 328     if (this->cptr == 0) return listAppend(this, el);
 329
 330     ptr = newNode(el);
 331
 332     ptr->prev  = this->cptr;
 333     ptr->next  = this->cptr->next;
 334     this->cptr->next = ptr;
 335
 336     if (ptr->next != 0) {
 337         ptr->next->prev = ptr;
 338     } else {
 339         this->tail = ptr;
 340     }
 341     this->aCount++;
 342     return this;
 343 }
 344
 345 list   listInsertBefore(list this, void *el)
 346 {
 347     lnode *ptr;
 348     assert(this != 0);
 349
 350     if (this->cptr == 0) return listAppend(this, el);
 351
 352     ptr = newNode(el);
 353
 354     ptr->prev  = this->cptr->prev;
 355     ptr->next  = this->cptr;
 356     this->cptr->prev = ptr;
 357
 358     if (ptr->prev != 0) {
 359         ptr->prev->next = ptr;
 360     } else {
 361         this->head = ptr;
 362     }
 363     this->aCount++;
 364     return this;
 365 }
 366 #endif
 367 list   listRemove(list this)
 368 {
 369     lnode *ptr = 0;
 370     if (this->cptr == 0) return this;
 371
 372     if (this->cptr->next != 0) {
 373         ptr  = this->cptr->next;
 374         this->cptr->next->prev = this->cptr->prev;
 375     } else {
 376         this->tail = this->cptr->prev;
 377     }
 378
 379     if (this->cptr->prev != 0) {
 380         if (ptr == 0) ptr = this->cptr->prev;
 381         this->cptr->prev->next = this->cptr->next;
 382     } else {
 383         this->head = this->cptr->next;
 384     }
 385
 386     if (this->eDtor) this->eDtor(this->cptr->value);        /* call the dtor callback */
 387
 388     free(this->cptr);
 389     this->aCount--;
 390     this->cptr = ptr;
 391     return this;
 392 }
 393
 394 list   listClear(list this)
 395 {
 396     lnode *node = this->head, *ptr;
 397
 398     while (node) {
 399         ptr = node->next;
 400         if (this->eDtor) this->eDtor(node->value);           /* call the dtor callback */
 401         free(node);
 402         this->aCount--;
 403         node = ptr;
 404     }
 405
 406     this->head = this->tail = this->cptr = 0;
 407     assert(this->aCount == 0);
 408     return this;
 409 }
 410
 411 #ifdef TEST
 412
 413 void   listForAll(list this, void (*f)(void *))
 414 {
 415     lnode *ptr = this->head;
 416     while (ptr) {
 417         f(ptr->value);
 418         ptr = ptr->next;
 419     }
 420 }
 421
 422
 423 #include <stdio.h>
 424
 425 void printlist(list l)
 426 {
 427     int saved;
 428     assert(l != 0);
 429     saved = listPosition(l);
 430
 431     printf("[ ");
 432
 433     if (!listIsEmpty(l)) {
 434         listToFirst(l);
 435         do {
 436             printf("%d ", (int) listCurrent(l));
 437         } while (listNext(l));
 438     }
 439
 440     printf("]\n");
 441
 442     listPositionAt(l, saved);
 443 }
 444
 445 void printstringlist(list l)
 446 {
 447     int saved;
 448     assert(l != 0);
 449     saved = listPosition(l);
 450
 451     printf("[ ");
 452
 453     if (!listIsEmpty(l)) {
 454         listToFirst(l);
 455         do {
 456             printf("'%s' ", (char *) listCurrent(l));
 457         } while (listNext(l));
 458     }
 459
 460     printf("]\n");
 461
 462     listPositionAt(l, saved);
 463 }
 464
 465 void printstat(list l)
 466 {
 467     printf("count: %d, position: %d, isEmpty: %d, atFirst: %d, atLast: %d.\n",
 468            listCount(l), listPosition(l), listIsEmpty(l), listAtFirst(l), listAtLast(l));
 469 }
 470
 471 void allfunc(void *e)
 472 {
 473     printf("%d ", e);
 474 }
 475
 476 void edtor(void *ptr)
 477 {
 478     printf("element dtor: 0x%08x\n", ptr);
 479     free(ptr);
 480 }
 481
 482 int main()
 483 {
 484     list l1, l2;
 485     char *ptr;
 486     int i;
 487
 488 #ifdef MALLOC_TRACE
 489     mal_leaktrace(1);
 490     mal_debug(2);
 491 #endif
 492
 493     l1 = listNewEmpty();
 494     printstat(l1);
 495
 496     listAppend(l1, 1);
 497     printstat(l1);
 498
 499     listAppend(l1, 2);
 500     printstat(l1);
 501
 502     listAppend(l1, 3);
 503     printstat(l1);
 504
 505     printlist(l1);
 506
 507     listToFirst(l1);
 508     listInsertBefore(l1, -5);
 509     printlist(l1);
 510
 511     l2 = listNewCopy(l1);
 512     printlist(l2);
 513
 514     listForAll(l2, allfunc);
 515     printf("\n");
 516
 517     listClear(l1);
 518     listSetElementDtor(l1, edtor);
 519
 520     for(i=0; i<10; i++) {
 521         ptr = malloc(20);
 522         snprintf(ptr, 20, "element # %d", i);
 523         listAppend(l1, ptr);
 524     }
 525
 526     printstringlist(l1);
 527
 528
 529     listDispose(l1);
 530     listDispose(l2);
 531
 532 #ifdef MALLOC_TRACE
 533     mal_dumpleaktrace(stdout);
 534 #endif
 535
 536
 537     return 0;
 538 }
 539 #endif
 540
 541