path: root/libical/src/libical/pvl.c

/*======================================================================
 FILE: pvl.c
 CREATOR: eric November, 1995


  (C) COPYRIGHT 1999 Eric Busboom 
  http://www.softwarestudio.org

  The contents of this file are subject to the Mozilla Public License
  Version 1.0 (the "License"); you may not use this file except in
  compliance with the License. You may obtain a copy of the License at
  http://www.mozilla.org/MPL/
 
  Software distributed under the License is distributed on an "AS IS"
  basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
  the License for the specific language governing rights and
  limitations under the License.
======================================================================*/

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "pvl.h"
#include <errno.h>
#include <assert.h>
#include <stdlib.h>



/*
  struct pvl_list_t

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

  This type is also private. Use pvl_list instead 

  */

typedef struct pvl_list_t
{
    int MAGIC;              /* Magic Identifier */
    struct pvl_elem_t *head;    /* Head of list */
    struct pvl_elem_t *tail;    /* Tail of list */
    int count;          /* Number of items in the list */
    struct pvl_elem_t *p;       /* Pointer used for iterators */
} pvl_list_t;




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

int pvl_elem_count = 0;
int pvl_list_count = 0;


/*----------------------------------------------------------------------
  Function: pvl_list pvl_newlist()
 
  Purpose:

  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. 
  *----------------------------------------------------------------------*/

pvl_list 
pvl_newlist()
{
    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;
}

void
pvl_free(pvl_list l)
{
   struct pvl_list_t *L = (struct pvl_list_t *)l;

   pvl_clear(l);

   free(L);
}

/*----------------------------------------------------------------------
  Function: pvl_new_element(void *d, struct pvl_elem_t *next,struct pvl_elem_t *prior)
 
  Purpose:
  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:

  d The data item to be stored in the list
  next  Pointer value to assign to the member "next"
  prior Pointer value to assign to the member "prior"

  Returns:
  
  A pointer to the new element.
  0 if there is no memory available. 

  *----------------------------------------------------------------------*/

pvl_elem 
pvl_new_element(void *d, pvl_elem next,pvl_elem prior)
{
    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;
}

/*----------------------------------------------------------------------
  Function: pvl_unshift(pvl_list l,void *d)
 
  Purpose:

  Add a new element to the from of the list

  Parameters:

  l The list to add the item to 
  d Pointer to the item to add

  Returns:
  *----------------------------------------------------------------------*/

void 
pvl_unshift(pvl_list l,void *d)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    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++;
}

/*----------------------------------------------------------------------
  Function: pvl_shift(pvl_list l)
 
  Purpose:

  Remove an element from the front of the list 

  Parameters:

  l The list to operate on

  Returns:
  *----------------------------------------------------------------------*/

void* 
pvl_shift(pvl_list l)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;

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

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

}

/*----------------------------------------------------------------------
  Function: void  pvl_push(pvl_list l,void *d)

  Purpose:

  Add a new item to the tail of the list

  Paramters:

  l The list to operate on
  d Pointer to the item to add

  Returns:
  *----------------------------------------------------------------------*/

void 
pvl_push(pvl_list l,void *d)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    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++;

}

/*----------------------------------------------------------------------
  Function: void*  pvl_pop(pvl_list l)

  Purpose:

  Remove an element from the tail of the list 

  Paramters:

  l The list to operate on

  Returns:
  *----------------------------------------------------------------------*/

void* 
pvl_pop(pvl_list l)
{

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

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

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

}


/*----------------------------------------------------------------------
  Function: void pvl_insert_ordered(pvl_list l,pvl_comparef f,void *d)

  Purpose:
  
  Add a new item to a list that is ordered by a comparison function. 
  This routine assumes that the list is properly ordered. 

  l The list to operate on
  f Pointer to a comparison function
  d     Pointer to data to pass to the comparison function

  Returns:

  void

  *----------------------------------------------------------------------*/

void 
pvl_insert_ordered(pvl_list l,pvl_comparef f,void *d)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;

    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 */

    assert(0);

}

/*----------------------------------------------------------------------
  Function: void  pvl_insert_after(pvl_list l,pvl_elem p,void *d)

  Purpose:

  Add a new item after the referenced element. 

  Parameters:

  l The list to operate on 
  p The list element to add the item after
  d Pointer to the item to add. 

  Returns:

  void

  *----------------------------------------------------------------------*/

void 
pvl_insert_after(pvl_list l,pvl_elem p,void *d)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    struct pvl_elem_t *P = (struct pvl_elem_t *)p;
    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;
    }
}

/*----------------------------------------------------------------------
  Function: void pvl_insert_before(pvl_list l,pvl_elem p,void *d)

  Purpose:

  Add an item after a referenced item

  Parameters:

  l The list to operate on
  p The list element to add the item before
  d Pointer to the data to be added. 

  Returns:
  *----------------------------------------------------------------------*/

void 
pvl_insert_before(pvl_list l,pvl_elem p,void *d)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    struct pvl_elem_t *P = (struct pvl_elem_t *)p;
    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;
    }
}

/*----------------------------------------------------------------------
  Function: void pvl_remove(pvl_list l,pvl_elem e)
 
  Purpose:

  Remove the referenced item from the list

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

  Parameters:

  l The list to operate on
  e The element to remove. 

  Returns:
  *----------------------------------------------------------------------*/

void* 
pvl_remove(pvl_list l,pvl_elem e)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    struct pvl_elem_t *E = (struct pvl_elem_t *)e;
    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; 

    free(E);

    return data;

}

/*----------------------------------------------------------------------
  Function: pvl_elem pvl_find(pvl_list l,pvl_findf f,void* v)

  Purpose:

  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:

  l The list to operate on
  f Pointer to the find function
  v Pointer to constant data to pass into the function

  Returns:

  Pointer to the element that the find function found. 

  *----------------------------------------------------------------------*/

pvl_elem
pvl_find(pvl_list l,pvl_findf f,void* v)
{
    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;

}
/*----------------------------------------------------------------------
  Function: void*  pvl_find_next(pvl_list l,pvl_findf f,void* v)

  Purpose:

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

  Parameters:

  l The list to operate on
  f Pointer to the find function
  v Pointer to constant data to pass into the function

  Returns:

  Pointer to the element that the find function found. 

  *----------------------------------------------------------------------*/

pvl_elem
pvl_find_next(pvl_list l,pvl_findf f,void* v)
{
    
    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;

}

/*----------------------------------------------------------------------
  Function: void pvl_clear(pvl_list l)

  Purpose:
  
  Remove the all the elements in the list. The does not free the data items
  the elements hold. 


  Returns:
  *----------------------------------------------------------------------*/

void 
pvl_clear(pvl_list l)
{
    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;
    }
}

/*----------------------------------------------------------------------
  Function: int pvl_count(pvl_list l)

  Purpose:

  Returns the number of items in the list. 

  Returns:
  *----------------------------------------------------------------------*/

int 
pvl_count(pvl_list l)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;

    return L->count;
}


/*----------------------------------------------------------------------
  Function: pvl_elem  pvl_next(pvl_elem e)
 
  Purpose: 
  Returns a pointer to the given element 

  Returns:
  *----------------------------------------------------------------------*/

pvl_elem 
pvl_next(pvl_elem e)
{
    struct pvl_elem_t *E = (struct pvl_elem_t *)e;

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

    return (pvl_elem)E->next;
}

/*----------------------------------------------------------------------
  Function: pvl_elem  pvl_prior(pvl_elem e)

  Purpose:

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

  Returns:
  *----------------------------------------------------------------------*/

pvl_elem 
pvl_prior(pvl_elem e)
{
    struct pvl_elem_t *E = (struct pvl_elem_t *)e;

    return (pvl_elem)E->prior;
}

/*----------------------------------------------------------------------
  Function: pvl_elem  pvl_head(pvl_list l )
 
  Purpose:
  
  Returns a pointer to the first item in the list. 

  Returns:
  *----------------------------------------------------------------------*/
pvl_elem 
pvl_head(pvl_list l )
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;

    return (pvl_elem)L->head;
}

/*----------------------------------------------------------------------
  Function: pvl_elem  pvl_tail(pvl_list l)
 
  Purpose:

  Returns a pointer to the last item in the list. 

  Returns:
  *----------------------------------------------------------------------*/
pvl_elem 
pvl_tail(pvl_list l)
{
    struct pvl_list_t *L = (struct pvl_list_t *)l;
    return (pvl_elem)L->tail;
}

/*----------------------------------------------------------------------
  Function:
 

  Purpose:


  Returns:
  *----------------------------------------------------------------------*/

#ifndef PVL_USE_MACROS
void* 
pvl_data(pvl_elem e)
{
    struct pvl_elem_t *E = (struct pvl_elem_t *)e;
  
    if ( e == 0){
    return 0;
    }

    return E->d;
}
#endif

/*----------------------------------------------------------------------
  Function: void  pvl_apply(pvl_list l,pvl_applyf f, void *v)
 
  Purpose:

  Call a function for every item in the list. 

  Paramters: 

  l The list to operate on
  f Pointer to the function to call
  v Data to pass to the function on every iteration

  Returns:

  void
  *----------------------------------------------------------------------*/

void 
pvl_apply(pvl_list l,pvl_applyf f, void *v)
{
    pvl_elem e;

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

}