Back to index

lightning-sunbird  0.9+nobinonly
Classes | Typedefs | Functions | Variables
pvl.c File Reference
#include "pvl.h"
#include <errno.h>
#include <assert.h>
#include <stdlib.h>

Go to the source code of this file.

Classes

struct  pvl_list_t
 struct pvl_list_t More...

Typedefs

typedef struct pvl_list_t pvl_list_t
 struct pvl_list_t

Functions

pvl_list pvl_newlist ()
 Creates a new list, clears the pointers and assigns a magic number.
void pvl_free (pvl_list l)
pvl_elem pvl_new_element (void *d, pvl_elem next, pvl_elem prior)
 Creates a new list element, assigns a magic number, and assigns the next and previous pointers.
void pvl_unshift (pvl_list L, void *d)
 Add a new element to the from of the list.
voidpvl_shift (pvl_list L)
 Remove an element from the front of the list.
void pvl_push (pvl_list L, void *d)
 Add a new item to the tail of the list.
voidpvl_pop (pvl_list L)
 Remove an element from the tail of the list.
void pvl_insert_ordered (pvl_list L, pvl_comparef f, void *d)
 Add a new item to a list that is ordered by a comparison function.
void pvl_insert_after (pvl_list L, pvl_elem P, void *d)
 Add a new item after the referenced element.
void pvl_insert_before (pvl_list L, pvl_elem P, void *d)
 Add an item after a referenced item.
voidpvl_remove (pvl_list L, pvl_elem E)
 Remove the referenced item from the list.
pvl_elem pvl_find (pvl_list l, pvl_findf f, void *v)
 Return a pointer to data that satisfies a function.
pvl_elem pvl_find_next (pvl_list l, pvl_findf f, void *v)
 Like pvl_find(), but continues the search where the last find() or find_next() left off.
void pvl_clear (pvl_list l)
 Remove the all the elements in the list.
int pvl_count (pvl_list L)
 Returns the number of items in the list.
pvl_elem pvl_next (pvl_elem E)
 Returns a pointer to the given element.
pvl_elem pvl_prior (pvl_elem E)
 Returns a pointer to the element previous to the element given.
pvl_elem pvl_head (pvl_list L)
 Returns a pointer to the first item in the list.
pvl_elem pvl_tail (pvl_list L)
 Returns a pointer to the last item in the list.
voidpvl_data (pvl_elem E)
void pvl_apply (pvl_list l, pvl_applyf f, void *v)
 Call a function for every item in the list.

Variables

int pvl_elem_count = 0
 This global is incremented for each call to pvl_new_element(); it gives each list a unique identifer.
int pvl_list_count = 0

Class Documentation

struct pvl_list_t

struct pvl_list_t

The list structure. This is the hanlde for the entire list

This type is also private. Use pvl_list instead

Definition at line 27 of file pvl.c.

Collaboration diagram for pvl_list_t:
Class Members
int count Number of items in the list.
struct pvl_elem_t * head Head of list.
int MAGIC Magic Identifier.
struct pvl_elem_t * p Pointer used for iterators.
struct pvl_elem_t * tail Tail of list.

Typedef Documentation

typedef struct pvl_list_t pvl_list_t

struct pvl_list_t

The list structure. This is the hanlde for the entire list

This type is also private. Use pvl_list instead


Function Documentation

void pvl_apply ( pvl_list  l,
pvl_applyf  f,
void v 
)

Call a function for every item in the list.

Parameters:
lThe list to operate on
fPointer to the function to call
vData to pass to the function on every iteration

Definition at line 575 of file pvl.c.

{
    pvl_elem e;

    for (e=pvl_head(l); e!= 0; e = pvl_next(e))
    {
       (*f)(((struct pvl_elem_t *)e)->d,v);
    }

}

Here is the call graph for this function:

Remove the all the elements in the list.

The does not free the data items the elements hold.

Definition at line 480 of file pvl.c.

{
    pvl_elem e = pvl_head(l);
    pvl_elem next;

    if (e == 0) {
       return;
    }

    while(e != 0)
    {
       next = pvl_next(e);
       pvl_remove(l,e);
       e = next;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Returns the number of items in the list.

Definition at line 503 of file pvl.c.

{
    return L->count;
}

Here is the caller graph for this function:

Definition at line 556 of file pvl.c.

{
    if ( E == 0){
       return 0;
    }

    return E->d;
}
pvl_elem pvl_find ( pvl_list  l,
pvl_findf  f,
void v 
)

Return a pointer to data that satisfies a function.

This routine will interate through the entire list and call the find function for each item. It will break and return a pointer to the data that causes the find function to return 1.

Parameters:
lThe list to operate on
fPointer to the find function
vPointer to constant data to pass into the function
Returns:
Pointer to the element that the find function found.

Definition at line 425 of file pvl.c.

{
    pvl_elem e;
    
    for (e=pvl_head(l); e!= 0; e = pvl_next(e))
    {
       if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
       {
           /* Save this elem for a call to find_next */
           ((struct pvl_list_t *)l)->p = e;
           return e;
       }
    }
    
    return 0;

}

Here is the call graph for this function:

pvl_elem pvl_find_next ( pvl_list  l,
pvl_findf  f,
void v 
)

Like pvl_find(), but continues the search where the last find() or find_next() left off.

Parameters:
lThe list to operate on
fPointer to the find function
vPointer to constant data to pass into the function
Returns:
Pointer to the element that the find function found.

Definition at line 455 of file pvl.c.

{
    
    pvl_elem e;
    
    for (e=pvl_head(l); e!= 0; e = pvl_next(e))
    {
       if ( (*f)(((struct pvl_elem_t *)e)->d,v) == 1)
       {
           /* Save this elem for a call to find_next */
           ((struct pvl_list_t *)l)->p = e;
           return e;
       }
    }

    return 0;

}

Here is the call graph for this function:

Definition at line 76 of file pvl.c.

{
   struct pvl_list_t *L = (struct pvl_list_t *)l;

   pvl_clear(l);

   free(L);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Returns a pointer to the first item in the list.

Definition at line 540 of file pvl.c.

{
    return (pvl_elem)L->head;
}

Here is the caller graph for this function:

void pvl_insert_after ( pvl_list  L,
pvl_elem  P,
void d 
)

Add a new item after the referenced element.

Parameters:
LThe list to operate on
PThe list element to add the item after
dPointer to the item to add.

Definition at line 288 of file pvl.c.

{
    struct pvl_elem_t *E = 0;

    L->count++;

    if (P == 0)
    {
       pvl_unshift(L,d);
       return;
    }

    if ( P == L->tail)
    {
       E = pvl_new_element(d,0,P);
       L->tail = E;
       E->prior->next = E;
    }
    else
    {
       E = pvl_new_element(d,P->next,P);
       E->next->prior  = E;
       E->prior->next = E;
    }
}

Here is the call graph for this function:

void pvl_insert_before ( pvl_list  L,
pvl_elem  P,
void d 
)

Add an item after a referenced item.

Parameters:
LThe list to operate on
PThe list element to add the item before
dPointer to the data to be added.

Definition at line 323 of file pvl.c.

{
    struct pvl_elem_t *E = 0;

    L->count++;

    if (P == 0)
    {
       pvl_unshift(L,d);
       return;
    }

    if ( P == L->head)
    {
       E = pvl_new_element(d,P,0);
       E->next->prior = E;
       L->head = E;
    }
    else
    {
       E = pvl_new_element(d,P,P->prior);
       E->prior->next = E;
       E->next->prior = E;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Add a new item to a list that is ordered by a comparison function.

This routine assumes that the list is properly ordered.

Parameters:
LThe list to operate on
fPointer to a comparison function
dPointer to data to pass to the comparison function

Definition at line 233 of file pvl.c.

{
    struct pvl_elem_t *P;

    L->count++;

    /* Empty list, add to head */

    if(L->head == 0)
    {
       pvl_unshift(L,d);
       return;
    }

    /* smaller than head, add to head */

    if ( ((*f)(d,L->head->d)) <= 0)
    { 
       pvl_unshift(L,d);
       return;
    }

    /* larger than tail, add to tail */
    if ( (*f)(d,L->tail->d) >= 0)
    { 
       pvl_push(L,d);
       return;
    }


    /* Search for the first element that is smaller, and add before it */
    
    for (P=L->head; P != 0; P = P->next)
    {
       if ( (*f)(P->d,d) >= 0)
       {
           pvl_insert_before(L,P,d);
           return;
       }
    }

    /* badness, choke */
#ifndef lint
    assert(0);
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

pvl_elem pvl_new_element ( void d,
pvl_elem  next,
pvl_elem  prior 
)

Creates a new list element, assigns a magic number, and assigns the next and previous pointers.

Passing in the next and previous points may seem odd, but it allos the user to set them while keeping the internal data hidden. In nearly all cases, the user is the pvl library itself.

Parameters:
dThe data item to be stored in the list
nextPointer value to assign to the member "next"
priorPointer value to assign to the member "prior"
Returns:
A pointer to the new element, 0 if there is no memory available.

Definition at line 101 of file pvl.c.

{
    struct pvl_elem_t *E;

    if ( ( E = (struct pvl_elem_t*)malloc(sizeof(struct pvl_elem_t))) == 0)
    {
       errno = ENOMEM;
       return 0;
    }

    E->MAGIC = pvl_elem_count++;
    E->d = d;
    E->next = next;
    E->prior = prior;

    return (pvl_elem)E;
}

Here is the caller graph for this function:

Creates a new list, clears the pointers and assigns a magic number.

Returns:
Pointer to the new list, 0 if there is no available memory.

Definition at line 55 of file pvl.c.

{
    struct pvl_list_t *L;

    if ( ( L = (struct pvl_list_t*)malloc(sizeof(struct pvl_list_t))) == 0)
    {
       errno = ENOMEM;
       return 0;
    }

    L->MAGIC = pvl_list_count;
    pvl_list_count++;
    L->head = 0;
    L->tail = 0;
    L->count = 0;
    L->p = 0;

    return L;
}

Here is the caller graph for this function:

Returns a pointer to the given element.

Definition at line 514 of file pvl.c.

{
    if (E == 0){
       return 0;
    }

    return (pvl_elem)E->next;
}

Here is the caller graph for this function:

Remove an element from the tail of the list.

Parameters:
LThe list to operate on

Definition at line 211 of file pvl.c.

{
    if ( L->tail == 0)
    {
       return 0;
    }

    return pvl_remove(L,(void*) L->tail);;

}

Here is the call graph for this function:

Here is the caller graph for this function:

Returns a pointer to the element previous to the element given.

Definition at line 529 of file pvl.c.

{
    return (pvl_elem)E->prior;
}

Here is the caller graph for this function:

void pvl_push ( pvl_list  L,
void d 
)

Add a new item to the tail of the list.

Parameters:
LThe list to operate on
dPointer to the item to add

Definition at line 179 of file pvl.c.

{
    struct pvl_elem_t *E = pvl_new_element(d,0,L->tail);

    /* These are done in pvl_new_element
       E->next = 0;
       E->prior = L->tail;
    */

    if (L->tail != 0) 
    {
       L->tail->next = E;
    }

    if (L->head == 0) 
    {
       L->head = E;
    }
  
    L->tail = E;

    L->count++;

}

Here is the call graph for this function:

Here is the caller graph for this function:

void* pvl_remove ( pvl_list  L,
pvl_elem  E 
)

Remove the referenced item from the list.

This routine will free the element, but not the data item that the element contains.

Parameters:
LThe list to operate on
EThe element to remove.

Definition at line 360 of file pvl.c.

{
    void* data;

    if (E == L->head)
    {
       if (E->next != 0)
       {
           E->next->prior = 0;
           L->head = E->next;
       } else {
           /* E Also points to tail -> only one element in list */
           L->tail = 0;
           L->head = 0;
       }
    }
    else if (E == L->tail)
    {
       if (E->prior != 0)
       {
           E->prior->next = 0;
           L->tail = E->prior;
       } else {
           /* E points to the head, so it was the last element */
           /* This case should be taken care of in the previous clause */
           L->head = 0;
           L->tail = 0;
       }
    }
    else
    {
       E->prior->next = E->next;
       E->next->prior = E->prior;
    }


    L->count--;

    data = E->d; 

    E->prior = 0;
    E->next = 0;
    E->d = 0;

    free(E);

    return data;

}

Here is the caller graph for this function:

Remove an element from the front of the list.

Parameters:
LThe list to operate on
Returns:
the entry on the front of the list

Definition at line 159 of file pvl.c.

{
    if (L->head == 0)
    {
       return 0;
    }

    return pvl_remove(L,(void*)L->head);

}

Here is the call graph for this function:

Returns a pointer to the last item in the list.

Definition at line 549 of file pvl.c.

{
    return (pvl_elem)L->tail;
}

Here is the caller graph for this function:

void pvl_unshift ( pvl_list  L,
void d 
)

Add a new element to the from of the list.

Parameters:
LThe list to add the item to
dPointer to the item to add

Definition at line 127 of file pvl.c.

{
    struct pvl_elem_t *E = pvl_new_element(d,L->head,0);

    if (E->next != 0)
    {
       /* Link the head node to it */
       E->next->prior = E;
    }

    /* move the head */
    L->head = E;

    /* maybe move the tail */
  
    if (L->tail == 0)
    {
       L->tail = E;
    }

    L->count++;
}

Here is the call graph for this function:

Here is the caller graph for this function:


Variable Documentation

This global is incremented for each call to pvl_new_element(); it gives each list a unique identifer.

Definition at line 44 of file pvl.c.

Definition at line 45 of file pvl.c.