src/libical/pvl.c

   1 /*======================================================================
   2  FILE: pvl.c
   3  CREATOR: eric November, 1995
   4
   5
   6  (C) COPYRIGHT 2000, Eric Busboom <eric@softwarestudio.org>
   7      http://www.softwarestudio.org
   8
   9  This program is free software; you can redistribute it and/or modify
  10  it under the terms of either:
  11
  12     The LGPL as published by the Free Software Foundation, version
  13     2.1, available at: http://www.fsf.org/copyleft/lesser.html
  14
  15   Or:
  16
  17     The Mozilla Public License Version 1.0. You may obtain a copy of
  18     the License at http://www.mozilla.org/MPL/
  19
  20 ======================================================================*/
  21
  22 #ifdef HAVE_CONFIG_H
  23 #include "config.h"
  24 #endif
  25
  26 #include "pvl.h"
  27 #include <errno.h>
  28 #include <assert.h>
  29 #include <stdlib.h>
  30
  31 /**
  32   struct pvl_list_t
  33
  34   The list structure. This is the hanlde for the entire list
  35
  36   This type is also private. Use pvl_list instead
  37
  38   */
  39
  40 typedef struct pvl_list_t
  41 {
  42         int MAGIC;                      /**< Magic Identifier */
  43         struct pvl_elem_t *head;        /**< Head of list */
  44         struct pvl_elem_t *tail;        /**< Tail of list */
  45         int count;                      /**< Number of items in the list */
  46         struct pvl_elem_t *p;           /**< Pointer used for iterators */
  47 } pvl_list_t;
  48
  49
  50
  51
  52 /**
  53  * This global is incremented for each call to pvl_new_element(); it gives each
  54  * list a unique identifer
  55  */
  56
  57 int pvl_elem_count = 0;
  58 int pvl_list_count = 0;
  59
  60
  61 /**
  62  * @brief Creates a new list, clears the pointers and assigns a magic number
  63  *
  64  * @return  Pointer to the new list, 0 if there is no available memory.
  65  */
  66
  67 pvl_list
  68 pvl_newlist()
  69 {
  70     struct pvl_list_t *L;
  71
  72     if ( ( L = (struct pvl_list_t*)malloc(sizeof(struct pvl_list_t))) == 0)
  73     {
  74         errno = ENOMEM;
  75         return 0;
  76     }
  77
  78     L->MAGIC = pvl_list_count;
  79     pvl_list_count++;
  80     L->head = 0;
  81     L->tail = 0;
  82     L->count = 0;
  83     L->p = 0;
  84
  85     return L;
  86 }
  87
  88 void
  89 pvl_free(pvl_list l)
  90 {
  91    struct pvl_list_t *L = (struct pvl_list_t *)l;
  92
  93    pvl_clear(l);
  94
  95    free(L);
  96 }
  97
  98 /**
  99  * @brief Creates a new list element, assigns a magic number, and assigns
 100  * the next and previous pointers.
 101  *
 102  * Passing in the next and previous points may seem odd, but it allos the user
 103  * to set them while keeping the internal data hidden. In nearly all cases,
 104  * the user is the pvl library itself.
 105  *
 106  * @param d     The data item to be stored in the list
 107  * @param next  Pointer value to assign to the member "next"
 108  * @param prior Pointer value to assign to the member "prior"
 109  *
 110  * @return A pointer to the new element, 0 if there is no memory available.
 111  */
 112
 113 pvl_elem
 114 pvl_new_element(void *d, pvl_elem next, pvl_elem prior)
 115 {
 116     struct pvl_elem_t *E;
 117
 118     if ( ( E = (struct pvl_elem_t*)malloc(sizeof(struct pvl_elem_t))) == 0)
 119     {
 120         errno = ENOMEM;
 121         return 0;
 122     }
 123
 124     E->MAGIC = pvl_elem_count++;
 125     E->d = d;
 126     E->next = next;
 127     E->prior = prior;
 128
 129     return (pvl_elem)E;
 130 }
 131
 132 /**
 133  * @brief Add a new element to the from of the list
 134  *
 135  * @param L     The list to add the item to
 136  * @param d     Pointer to the item to add
 137  */
 138
 139 void
 140 pvl_unshift(pvl_list L,void *d)
 141 {
 142     struct pvl_elem_t *E = pvl_new_element(d,L->head,0);
 143
 144     if (E->next != 0)
 145     {
 146         /* Link the head node to it */
 147         E->next->prior = E;
 148     }
 149
 150     /* move the head */
 151     L->head = E;
 152
 153     /* maybe move the tail */
 154
 155     if (L->tail == 0)
 156     {
 157         L->tail = E;
 158     }
 159
 160     L->count++;
 161 }
 162
 163 /**
 164  * @brief Remove an element from the front of the list
 165  *
 166  * @param L     The list to operate on
 167  *
 168  * @return the entry on the front of the list
 169  */
 170
 171 void*
 172 pvl_shift(pvl_list L)
 173 {
 174     if (L->head == 0)
 175     {
 176         return 0;
 177     }
 178
 179     return pvl_remove(L,(void*)L->head);
 180
 181 }
 182
 183 /**
 184  * @brief Add a new item to the tail of the list
 185  *
 186  * @param L     The list to operate on
 187  * @param d     Pointer to the item to add
 188  *
 189  */
 190
 191 void
 192 pvl_push(pvl_list L,void *d)
 193 {
 194     struct pvl_elem_t *E = pvl_new_element(d,0,L->tail);
 195
 196     /* These are done in pvl_new_element
 197        E->next = 0;
 198        E->prior = L->tail;
 199     */
 200
 201     if (L->tail != 0)
 202     {
 203         L->tail->next = E;
 204     }
 205
 206     if (L->head == 0)
 207     {
 208         L->head = E;
 209     }
 210
 211     L->tail = E;
 212
 213     L->count++;
 214
 215 }
 216
 217 /**
 218  * @brief Remove an element from the tail of the list
 219  *
 220  * @param L     The list to operate on
 221  */
 222
 223 void*
 224 pvl_pop(pvl_list L)
 225 {
 226     if ( L->tail == 0)
 227     {
 228         return 0;
 229     }
 230
 231     return pvl_remove(L,(void*) L->tail);;
 232
 233 }
 234
 235
 236 /**
 237  * Add a new item to a list that is ordered by a comparison function.
 238  * This routine assumes that the list is properly ordered.
 239  *
 240  * @param L     The list to operate on
 241  * @param f     Pointer to a comparison function
 242  * @param d     Pointer to data to pass to the comparison function
 243  */
 244
 245 void
 246 pvl_insert_ordered(pvl_list L,pvl_comparef f,void *d)
 247 {
 248     struct pvl_elem_t *P;
 249
 250     L->count++;
 251
 252     /* Empty list, add to head */
 253
 254     if(L->head == 0)
 255     {
 256         pvl_unshift(L,d);
 257         return;
 258     }
 259
 260     /* smaller than head, add to head */
 261
 262     if ( ((*f)(d,L->head->d)) <= 0)
 263     {
 264         pvl_unshift(L,d);
 265         return;
 266     }
 267
 268     /* larger than tail, add to tail */
 269     if ( (*f)(d,L->tail->d) >= 0)
 270     {
 271         pvl_push(L,d);
 272         return;
 273     }
 274
 275
 276     /* Search for the first element that is smaller, and add before it */
 277
 278     for (P=L->head; P != 0; P = P->next)
 279     {
 280         if ( (*f)(P->d,d) >= 0)
 281         {
 282             pvl_insert_before(L,P,d);
 283             return;
 284         }
 285     }
 286
 287     /* badness, choke */
 288 #ifndef lint
 289     assert(0);
 290 #endif
 291 }
 292
 293 /**
 294  * @brief Add a new item after the referenced element.
 295  * @param L     The list to operate on
 296  * @param P     The list element to add the item after
 297  * @param d     Pointer to the item to add.
 298  */
 299
 300 void
 301 pvl_insert_after(pvl_list L,pvl_elem P,void *d)
 302 {
 303     struct pvl_elem_t *E = 0;
 304
 305     L->count++;
 306
 307     if (P == 0)
 308     {
 309         pvl_unshift(L,d);
 310         return;
 311     }
 312
 313     if ( P == L->tail)
 314     {
 315         E = pvl_new_element(d,0,P);
 316         L->tail = E;
 317         E->prior->next = E;
 318     }
 319     else
 320     {
 321         E = pvl_new_element(d,P->next,P);
 322         E->next->prior  = E;
 323         E->prior->next = E;
 324     }
 325 }
 326
 327 /**
 328  * @brief Add an item after a referenced item
 329  *
 330  * @param L     The list to operate on
 331  * @param P     The list element to add the item before
 332  * @param d     Pointer to the data to be added.
 333  */
 334
 335 void
 336 pvl_insert_before(pvl_list L,pvl_elem P,void *d)
 337 {
 338     struct pvl_elem_t *E = 0;
 339
 340     L->count++;
 341
 342     if (P == 0)
 343     {
 344         pvl_unshift(L,d);
 345         return;
 346     }
 347
 348     if ( P == L->head)
 349     {
 350         E = pvl_new_element(d,P,0);
 351         E->next->prior = E;
 352         L->head = E;
 353     }
 354     else
 355     {
 356         E = pvl_new_element(d,P,P->prior);
 357         E->prior->next = E;
 358         E->next->prior = E;
 359     }
 360 }
 361
 362 /**
 363  * @brief Remove the referenced item from the list.
 364  *
 365  * This routine will free the element, but not the data item that the
 366  * element contains.
 367  *
 368  * @param L     The list to operate on
 369  * @param E     The element to remove.
 370  */
 371
 372 void*
 373 pvl_remove(pvl_list L,pvl_elem E)
 374 {
 375     void* data;
 376
 377     if (E == L->head)
 378     {
 379         if (E->next != 0)
 380         {
 381             E->next->prior = 0;
 382             L->head = E->next;
 383         } else {
 384             /* E Also points to tail -> only one element in list */
 385             L->tail = 0;
 386             L->head = 0;
 387         }
 388     }
 389     else if (E == L->tail)
 390     {
 391         if (E->prior != 0)
 392         {
 393             E->prior->next = 0;
 394             L->tail = E->prior;
 395         } else {
 396             /* E points to the head, so it was the last element */
 397             /* This case should be taken care of in the previous clause */
 398             L->head = 0;
 399             L->tail = 0;
 400         }
 401     }
 402     else
 403     {
 404         E->prior->next = E->next;
 405         E->next->prior = E->prior;
 406     }
 407
 408
 409     L->count--;
 410
 411     data = E->d;
 412
 413     E->prior = 0;
 414     E->next = 0;
 415     E->d = 0;
 416
 417     free(E);
 418
 419     return data;
 420
 421 }
 422
 423 /**
 424  * @brief Return a pointer to data that satisfies a function.
 425  *
 426  * This routine will interate through the entire list and call the
 427  * find function for each item. It will break and return a pointer to the
 428  * data that causes the find function to return 1.
 429  *
 430  * @param l     The list to operate on
 431  * @param f     Pointer to the find function
 432  * @param v     Pointer to constant data to pass into the function
 433  *
 434  * @return Pointer to the element that the find function found.
 435  */
 436
 437 pvl_elem
 438 pvl_find(pvl_list l,pvl_findf f,void* v)
 439 {
 440     pvl_elem e;
 441
 442     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
 443     {
 444         if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
 445         {
 446             /* Save this elem for a call to find_next */
 447             ((struct pvl_list_t *)l)->p = e;
 448             return e;
 449         }
 450     }
 451
 452     return 0;
 453
 454 }
 455
 456 /**
 457  * @brief Like pvl_find(), but continues the search where the last find() or
 458  * find_next() left off.
 459  *
 460  * @param l     The list to operate on
 461  * @param f     Pointer to the find function
 462  * @param v     Pointer to constant data to pass into the function
 463  *
 464  * @return Pointer to the element that the find function found.
 465  */
 466
 467 pvl_elem
 468 pvl_find_next(pvl_list l,pvl_findf f,void* v)
 469 {
 470
 471     pvl_elem e;
 472
 473     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
 474     {
 475         if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
 476         {
 477             /* Save this elem for a call to find_next */
 478             ((struct pvl_list_t *)l)->p = e;
 479             return e;
 480         }
 481     }
 482
 483     return 0;
 484
 485 }
 486
 487 /**
 488  * @brief Remove the all the elements in the list. The does not free
 489  * the data items the elements hold.
 490  */
 491
 492 void
 493 pvl_clear(pvl_list l)
 494 {
 495     pvl_elem e = pvl_head(l);
 496     pvl_elem next;
 497
 498     if (e == 0) {
 499         return;
 500     }
 501
 502     while(e != 0)
 503     {
 504         next = pvl_next(e);
 505         pvl_remove(l,e);
 506         e = next;
 507     }
 508 }
 509
 510
 511 /**
 512  * @brief Returns the number of items in the list.
 513  */
 514
 515 int
 516 pvl_count(pvl_list L)
 517 {
 518     return L->count;
 519 }
 520
 521
 522 /**
 523  * @brief Returns a pointer to the given element
 524  */
 525
 526 pvl_elem
 527 pvl_next(pvl_elem E)
 528 {
 529     if (E == 0){
 530         return 0;
 531     }
 532
 533     return (pvl_elem)E->next;
 534 }
 535
 536
 537 /**
 538  * @brief Returns a pointer to the element previous to the element given.
 539  */
 540
 541 pvl_elem
 542 pvl_prior(pvl_elem E)
 543 {
 544     return (pvl_elem)E->prior;
 545 }
 546
 547
 548 /**
 549  * @brief Returns a pointer to the first item in the list.
 550  */
 551
 552 pvl_elem
 553 pvl_head(pvl_list L )
 554 {
 555     return (pvl_elem)L->head;
 556 }
 557
 558 /**
 559  * @brief Returns a pointer to the last item in the list.
 560  */
 561 pvl_elem
 562 pvl_tail(pvl_list L)
 563 {
 564     return (pvl_elem)L->tail;
 565 }
 566
 567 #ifndef PVL_USE_MACROS
 568 void*
 569 pvl_data(pvl_elem E)
 570 {
 571     if ( E == 0){
 572         return 0;
 573     }
 574
 575     return E->d;
 576 }
 577 #endif
 578
 579 /**
 580  * @brief Call a function for every item in the list.
 581  *
 582  * @param l     The list to operate on
 583  * @param f     Pointer to the function to call
 584  * @param v     Data to pass to the function on every iteration
 585  */
 586
 587 void
 588 pvl_apply(pvl_list l,pvl_applyf f, void *v)
 589 {
 590     pvl_elem e;
 591
 592     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
 593     {
 594         (*f)(((struct pvl_elem_t *)e)->d,v);
 595     }
 596
 597 }