src/plugins/vcalendar/libical/libical/pvl.c

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