Back to index

lightning-sunbird  0.9+nobinonly
pvl.c
Go to the documentation of this file.
00001 /*======================================================================
00002  FILE: pvl.c
00003  CREATOR: eric November, 1995
00004 
00005 
00006  (C) COPYRIGHT 2000, Eric Busboom, http://www.softwarestudio.org
00007 ======================================================================*/
00008 
00009 #ifdef HAVE_CONFIG_H
00010 #include "config.h"
00011 #endif
00012 
00013 #include "pvl.h"
00014 #include <errno.h>
00015 #include <assert.h>
00016 #include <stdlib.h>
00017 
00027 typedef struct pvl_list_t
00028 {
00029        int MAGIC;                   
00030        struct pvl_elem_t *head;    
00031        struct pvl_elem_t *tail;    
00032        int count;                  
00033        struct pvl_elem_t *p;              
00034 } pvl_list_t;
00035 
00036 
00037 
00038 
00044 int pvl_elem_count = 0;
00045 int pvl_list_count = 0;
00046 
00047 
00054 pvl_list 
00055 pvl_newlist()
00056 {
00057     struct pvl_list_t *L;
00058 
00059     if ( ( L = (struct pvl_list_t*)malloc(sizeof(struct pvl_list_t))) == 0)
00060     {
00061        errno = ENOMEM;
00062        return 0;
00063     }
00064 
00065     L->MAGIC = pvl_list_count;
00066     pvl_list_count++;
00067     L->head = 0;
00068     L->tail = 0;
00069     L->count = 0;
00070     L->p = 0;
00071 
00072     return L;
00073 }
00074 
00075 void
00076 pvl_free(pvl_list l)
00077 {
00078    struct pvl_list_t *L = (struct pvl_list_t *)l;
00079 
00080    pvl_clear(l);
00081 
00082    free(L);
00083 }
00084 
00100 pvl_elem 
00101 pvl_new_element(void *d, pvl_elem next, pvl_elem prior)
00102 {
00103     struct pvl_elem_t *E;
00104 
00105     if ( ( E = (struct pvl_elem_t*)malloc(sizeof(struct pvl_elem_t))) == 0)
00106     {
00107        errno = ENOMEM;
00108        return 0;
00109     }
00110 
00111     E->MAGIC = pvl_elem_count++;
00112     E->d = d;
00113     E->next = next;
00114     E->prior = prior;
00115 
00116     return (pvl_elem)E;
00117 }
00118 
00126 void 
00127 pvl_unshift(pvl_list L,void *d)
00128 {
00129     struct pvl_elem_t *E = pvl_new_element(d,L->head,0);
00130 
00131     if (E->next != 0)
00132     {
00133        /* Link the head node to it */
00134        E->next->prior = E;
00135     }
00136 
00137     /* move the head */
00138     L->head = E;
00139 
00140     /* maybe move the tail */
00141   
00142     if (L->tail == 0)
00143     {
00144        L->tail = E;
00145     }
00146 
00147     L->count++;
00148 }
00149 
00158 void* 
00159 pvl_shift(pvl_list L)
00160 {
00161     if (L->head == 0)
00162     {
00163        return 0;
00164     }
00165 
00166     return pvl_remove(L,(void*)L->head);
00167 
00168 }
00169 
00178 void 
00179 pvl_push(pvl_list L,void *d)
00180 {
00181     struct pvl_elem_t *E = pvl_new_element(d,0,L->tail);
00182 
00183     /* These are done in pvl_new_element
00184        E->next = 0;
00185        E->prior = L->tail;
00186     */
00187 
00188     if (L->tail != 0) 
00189     {
00190        L->tail->next = E;
00191     }
00192 
00193     if (L->head == 0) 
00194     {
00195        L->head = E;
00196     }
00197   
00198     L->tail = E;
00199 
00200     L->count++;
00201 
00202 }
00203 
00210 void* 
00211 pvl_pop(pvl_list L)
00212 {
00213     if ( L->tail == 0)
00214     {
00215        return 0;
00216     }
00217 
00218     return pvl_remove(L,(void*) L->tail);;
00219 
00220 }
00221 
00222 
00232 void 
00233 pvl_insert_ordered(pvl_list L,pvl_comparef f,void *d)
00234 {
00235     struct pvl_elem_t *P;
00236 
00237     L->count++;
00238 
00239     /* Empty list, add to head */
00240 
00241     if(L->head == 0)
00242     {
00243        pvl_unshift(L,d);
00244        return;
00245     }
00246 
00247     /* smaller than head, add to head */
00248 
00249     if ( ((*f)(d,L->head->d)) <= 0)
00250     { 
00251        pvl_unshift(L,d);
00252        return;
00253     }
00254 
00255     /* larger than tail, add to tail */
00256     if ( (*f)(d,L->tail->d) >= 0)
00257     { 
00258        pvl_push(L,d);
00259        return;
00260     }
00261 
00262 
00263     /* Search for the first element that is smaller, and add before it */
00264     
00265     for (P=L->head; P != 0; P = P->next)
00266     {
00267        if ( (*f)(P->d,d) >= 0)
00268        {
00269            pvl_insert_before(L,P,d);
00270            return;
00271        }
00272     }
00273 
00274     /* badness, choke */
00275 #ifndef lint
00276     assert(0);
00277 #endif
00278 }
00279 
00287 void 
00288 pvl_insert_after(pvl_list L,pvl_elem P,void *d)
00289 {
00290     struct pvl_elem_t *E = 0;
00291 
00292     L->count++;
00293 
00294     if (P == 0)
00295     {
00296        pvl_unshift(L,d);
00297        return;
00298     }
00299 
00300     if ( P == L->tail)
00301     {
00302        E = pvl_new_element(d,0,P);
00303        L->tail = E;
00304        E->prior->next = E;
00305     }
00306     else
00307     {
00308        E = pvl_new_element(d,P->next,P);
00309        E->next->prior  = E;
00310        E->prior->next = E;
00311     }
00312 }
00313 
00322 void 
00323 pvl_insert_before(pvl_list L,pvl_elem P,void *d)
00324 {
00325     struct pvl_elem_t *E = 0;
00326 
00327     L->count++;
00328 
00329     if (P == 0)
00330     {
00331        pvl_unshift(L,d);
00332        return;
00333     }
00334 
00335     if ( P == L->head)
00336     {
00337        E = pvl_new_element(d,P,0);
00338        E->next->prior = E;
00339        L->head = E;
00340     }
00341     else
00342     {
00343        E = pvl_new_element(d,P,P->prior);
00344        E->prior->next = E;
00345        E->next->prior = E;
00346     }
00347 }
00348 
00359 void* 
00360 pvl_remove(pvl_list L,pvl_elem E)
00361 {
00362     void* data;
00363 
00364     if (E == L->head)
00365     {
00366        if (E->next != 0)
00367        {
00368            E->next->prior = 0;
00369            L->head = E->next;
00370        } else {
00371            /* E Also points to tail -> only one element in list */
00372            L->tail = 0;
00373            L->head = 0;
00374        }
00375     }
00376     else if (E == L->tail)
00377     {
00378        if (E->prior != 0)
00379        {
00380            E->prior->next = 0;
00381            L->tail = E->prior;
00382        } else {
00383            /* E points to the head, so it was the last element */
00384            /* This case should be taken care of in the previous clause */
00385            L->head = 0;
00386            L->tail = 0;
00387        }
00388     }
00389     else
00390     {
00391        E->prior->next = E->next;
00392        E->next->prior = E->prior;
00393     }
00394 
00395 
00396     L->count--;
00397 
00398     data = E->d; 
00399 
00400     E->prior = 0;
00401     E->next = 0;
00402     E->d = 0;
00403 
00404     free(E);
00405 
00406     return data;
00407 
00408 }
00409 
00424 pvl_elem
00425 pvl_find(pvl_list l,pvl_findf f,void* v)
00426 {
00427     pvl_elem e;
00428     
00429     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
00430     {
00431        if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
00432        {
00433            /* Save this elem for a call to find_next */
00434            ((struct pvl_list_t *)l)->p = e;
00435            return e;
00436        }
00437     }
00438     
00439     return 0;
00440 
00441 }
00442 
00454 pvl_elem
00455 pvl_find_next(pvl_list l,pvl_findf f,void* v)
00456 {
00457     
00458     pvl_elem e;
00459     
00460     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
00461     {
00462        if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
00463        {
00464            /* Save this elem for a call to find_next */
00465            ((struct pvl_list_t *)l)->p = e;
00466            return e;
00467        }
00468     }
00469 
00470     return 0;
00471 
00472 }
00473 
00479 void 
00480 pvl_clear(pvl_list l)
00481 {
00482     pvl_elem e = pvl_head(l);
00483     pvl_elem next;
00484 
00485     if (e == 0) {
00486        return;
00487     }
00488 
00489     while(e != 0)
00490     {
00491        next = pvl_next(e);
00492        pvl_remove(l,e);
00493        e = next;
00494     }
00495 }
00496 
00497 
00502 int 
00503 pvl_count(pvl_list L)
00504 {
00505     return L->count;
00506 }
00507 
00508 
00513 pvl_elem 
00514 pvl_next(pvl_elem E)
00515 {
00516     if (E == 0){
00517        return 0;
00518     }
00519 
00520     return (pvl_elem)E->next;
00521 }
00522 
00523 
00528 pvl_elem 
00529 pvl_prior(pvl_elem E)
00530 {
00531     return (pvl_elem)E->prior;
00532 }
00533 
00534 
00539 pvl_elem 
00540 pvl_head(pvl_list L )
00541 {
00542     return (pvl_elem)L->head;
00543 }
00544 
00548 pvl_elem 
00549 pvl_tail(pvl_list L)
00550 {
00551     return (pvl_elem)L->tail;
00552 }
00553 
00554 #ifndef PVL_USE_MACROS
00555 void* 
00556 pvl_data(pvl_elem E)
00557 {
00558     if ( E == 0){
00559        return 0;
00560     }
00561 
00562     return E->d;
00563 }
00564 #endif
00565 
00574 void 
00575 pvl_apply(pvl_list l,pvl_applyf f, void *v)
00576 {
00577     pvl_elem e;
00578 
00579     for (e=pvl_head(l); e!= 0; e = pvl_next(e))
00580     {
00581        (*f)(((struct pvl_elem_t *)e)->d,v);
00582     }
00583 
00584 }