Logo Search packages:      
Sourcecode: lanmap version File versions  Download package

list.c

/* ex: set ts=4 noet: */

#include <stddef.h>
#include <string.h>           /* memcpy */
#include <assert.h> /* assert */
#include "mem.h"
#include "debug.h"
#include "list.h"

static void list_head_dump(list_t *); /* formatted display of just a list_t to stdout */
static void list_node_dump(list_node_t *, void (*)(const void *)); /* formatted display of list */
static void list_dump_cb_chars(const void *); /* callback for list_dump to print char * node data */

/* creates list node */
/* returns NULL on failure */
list_node_t *list_node_new(const void *data, const size_t bytes)
{
      list_node_t *node;

#ifdef _DEBUG
      assert(data != NULL);
#endif
      
      node = xmalloc(sizeof(list_node_t));
      if (NULL == node) {
            DEBUG(__FILE__, __LINE__, "could not allocate node");
            return NULL;
      }

      node->data = xmalloc(bytes);
      if (NULL == node->data) {
            DEBUG(__FILE__, __LINE__, "could not allocate node->data");
            xfree(node);
            return NULL;
      }

      /* make a copy of data into node->data */
      memcpy(node->data, data, bytes);

      node->prev = NULL;
      node->next = NULL;

      return node;
}


/* creates list node */
/* returns NULL on failure */
list_node_t *list_node_ptr_new(void *data)
{
      list_node_t *node;

#ifdef _DEBUG
      /* assert(data != NULL); */
#endif
      
      node = xmalloc(sizeof(*node));
      if (NULL == node) {
            DEBUG(__FILE__, __LINE__, "could not allocate node");
            return NULL;
      }

      node->data = data;
      node->prev = NULL;
      node->next = NULL;

      return node;
}

/* creates deep copy of data into list node */
/* returns NULL on failure */
list_node_t * list_node_deep_new(const void *data, void * (*deepcopy)(const void *))
{
      list_node_t *node;
      void *deep;

#ifdef _DEBUG
      assert(NULL != data);
      assert(NULL != deepcopy);
#endif

      if (NULL == (deep = deepcopy(data))) {
            DEBUG(__FILE__, __LINE__, "deepcopy failed");
            return NULL;
      }

      if (NULL == (node = xmalloc(sizeof(list_node_t)))) {
            DEBUG(__FILE__, __LINE__, "could not allocate node");
            return NULL;
      }

      node->data = deep;
      node->prev = NULL;
      node->next = NULL;

      return node;
}


/* initialize list list */
list_t * list_new(void)
{
      list_t * list;
      
      if (NULL == (list = xmalloc(sizeof(list_t)))) {
            DEBUG(__FILE__, __LINE__, "could not allocate list");
            return NULL;
      }

      if (TRUE != list_init(list)) {
            DEBUG(__FILE__, __LINE__, "list_init failed");
            return NULL;
      }

      return list;
}

/* initialize a list_t pointer */
bool list_init(list_t *list)
{

#ifdef _DEBUG
      assert(NULL != list);
#endif

      list->first = NULL;
      list->last = NULL;
      list->nodes = 0;

      return TRUE;

}

/* free internals of list w/o list itself */
bool list_destroy(list_t *list, void (*free_data)(void *))
{
#ifdef _DEBUG
      assert(NULL != list);
#endif
      return list_nodes_free(list, free_data);
}

/* frees memory used by a node */
bool list_node_free(list_node_t *node, void (*free_data)(void *))
{

#ifdef _DEBUG
      assert(NULL != node);
      /* free_data may be NULL */
#endif

#if 0
      ERRF("%s:%d:list_node_free(): freeing node->data node: %p, data: %p, free_data: %p\n",
            __FILE__, __LINE__, (void *)node, (void *)node->data, (void *)free_data);
#endif

      if (NULL != free_data) {
            /* free up data structure with function pointer */
            (*free_data)(node->data);
#if 0
      } else {
            xfree(node->data);
#endif
      }

#if 0
      ERRF("%s:%d:list_node_free(): freeing node (%p)\n",
            __FILE__, __LINE__, (void *)node);
#endif

      xfree(node);

      return TRUE;
}

/* release the list_t. you must obviously get rid of the list before you do this */
/* this is useful if you concatenate 2 lists and want to free the second list's list
but keep the nodes intact */
void list_head_free(list_t *list)
{

#ifdef _DEBUG
      assert(NULL != list);
#endif

      if (NULL == list)
            return;

      xfree(list);
}


/*
 * returns the 'n'th list_node_t in list
 * NOTE: if number is negative we start from the back and work our way
 * forwards, i.e. -4 will get you the 4th to the last item
 */
list_node_t * list_nth_node(list_t *list, int n)
{
      list_node_t *node = NULL;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      if (n < 0) {
            /* NOTE: 1-based. -1 is last item */
            if ((size_t)-n + 1 > list_size(list)) {
                  return NULL;
            }
            node = list_last(list);
            while (++n < 0) {
                  node = list_node_prev(node);
                  if (NULL == node) {
                        return NULL;
                  }
            }
      } else { /* n >= 0 */
            /* NOTE: 0-based. 0 is first item */
            if ((size_t)(n + 1) > list_size(list)) {
                  return NULL;
            }
            node = list_first(list);
            while (n-- > 0) {
                  node = list_node_next(node);
                  if (NULL == node) {
                        return NULL;
                  }
            }
      }

      return node;
}

/*
 * 
 */
void * list_nth(list_t *list, int n)
{
      list_node_t *node;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      node = list_nth_node(list, n);

      if (NULL == node)
            return NULL;

      return list_node_data(node);
}


/*
      detach node from list and update count
*/
bool list_node_detach(list_t *list, list_node_t *node)
{
#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
#endif

#if 0
      DEBUGF(__FILE__, __LINE__, "detach before: list:%p, list->last:%p, node:%p, node->prev:%p, node->next:%p",
            list, list->last, node, node->prev, node->next);
#endif

      if (NULL == node->prev) { /* first item */
            list->first = node->next;
      } else {
            node->prev->next = node->next;
      }
      if (NULL == node->next) { /* last item */
            list->last = node->prev;
      } else {
            node->next->prev = node->prev;
      }

      node->prev = NULL;
      node->next = NULL;

      list->nodes--;

#if 0
      DEBUGF(__FILE__, __LINE__, "detach after: list:%p, list->last:%p, node:%p, node->prev:%p, node->next:%p",
            list, list->last, node, node->prev, node->next);
#endif

      return TRUE;
}

/* prepend new node into list */
/* returns pointer to node on success, NULL on failure */
list_node_t * list_prepend(list_t *list, list_node_t *node)
{

#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
#endif

      if (NULL != list->first)
            list->first->prev = node;

      if (NULL == list->last)
            list->last = node;

      node->next = list->first;
      list->first = node;

      list->nodes++;
      
      return node;

}

/* prepend new node into list */
/* returns pointer to node on success, NULL on failure */
list_node_t * list_prepend_ptr(list_t *list, void *v)
{
      list_node_t *node;

#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != v);
#endif

      node = list_node_ptr_new(v);
      if (NULL == node) {
            DEBUG(__FILE__, __LINE__, "list_node_ptr_new returned NULL, failing");
            return NULL;
      }

      return list_prepend(list, node);
}


/* append new node into list */
/* returns pointer to node on success, NULL on failure */
list_node_t * list_append(list_t *list, list_node_t *node)
{
#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
#endif

      node->prev = list->last;
      node->next = NULL;

      if (NULL != list->last) {
            list->last->next = node;
      }

      if (NULL == list->first) {
            list->first = node;
      }

      list->last = node;

      list->nodes++;
      
      return node;
}

/* append new node into list */
/* returns pointer to node on success, NULL on failure */
list_node_t * list_append_ptr(list_t *list, void *v)
{
      list_node_t *node;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      node = list_node_ptr_new(v);
      if (NULL == node) {
            DEBUG(__FILE__, __LINE__, "list_node_ptr_new returned NULL, failing");
            return NULL;
      }

      return list_append(list, node);
}

/*
 * 
 */
list_node_t * list_insert_before(list_t *list, list_node_t *node, list_node_t *insert)
{
#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
      assert(NULL != insert);
#endif

      if (NULL == node->prev) {
            return list_prepend(list, insert);
      } else {
            node->prev->next = insert;
            insert->prev = node->prev;
      }

      insert->next = node;
      node->prev = insert;

      list->nodes++;

      return insert;
}

/*
 * 
 */
list_node_t * list_insert_before_ptr(list_t *list, list_node_t *node, void *v)
{
      list_node_t *newnode;

#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
      assert(NULL != v);
#endif

      newnode = list_node_ptr_new(v);
      if (NULL == newnode) {
            DEBUG(__FILE__, __LINE__, "list_node_ptr_new returned NULL, failing");
            return NULL;
      }

      return list_insert_before(list, node, newnode);
}

/* pops and returns last item in list or NULL if list is empty */
void * list_pop(list_t *list)
{

      list_node_t *node;
      void *data;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      if (NULL == list->last) {
            return NULL;
      }

      node = list->last;
      if (TRUE != list_node_detach(list, node)) {
            DEBUG(__FILE__, __LINE__, "list_node_detach failed");
            return NULL;
      }

      data = list_node_data(node);

      /* clear everything in node except data */
      xfree(node);

      return data;
}

/* pops and returns first item in list or NULL if list is empty */
void * list_shift(list_t *list)
{
      list_node_t *node;
      void *data;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      if (NULL == list->first)
            return NULL;

      node = list->first;
      if (TRUE != list_node_detach(list, node)) {
            DEBUG(__FILE__, __LINE__, "list_node_detach failed");
            return NULL;
      }

      data = list_node_data(node);

      /* clear everything in node except data */
      xfree(node);

      return data;
}

/*
 * remove a node from a list
 */
bool list_remove(list_t *list, list_node_t *node, void (*free_data)(void *))
{
#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != node);
      /* free_data may be NULL */
#endif

      if (TRUE != list_node_detach(list, node)) {
            DEBUG(__FILE__, __LINE__, "list_node_detach failed");
            return FALSE;
      }
      if (TRUE != list_node_free(node, free_data)) {
            DEBUG(__FILE__, __LINE__, "list_node_free failed");
            return FALSE;
      }

      return TRUE;
}

/* frees entire list and list_t */
/* returns 1 on success, 0 on failure */
bool list_free(list_t *list, void (*free_data)(void *))
{

#ifdef _DEBUG
      assert(NULL != list);
      /* free_data may be NULL */
#endif

      if (TRUE != list_nodes_free(list, free_data)) {
            DEBUG(__FILE__, __LINE__, "list_nodes_free failed");
            return FALSE;
      }

      list_head_free(list);

      return TRUE;
}

/* frees entire list structure but not the list */
/* free_data may be NULL, list_node_free handles it */
bool list_nodes_free(list_t *list, void (*free_data)(void *))
{
      list_node_t *curr, *tmp = NULL;

#ifdef _DEBUG
      assert(NULL != list);
      /* free_data may be NULL */
#endif

      curr = list_first(list);

      while (NULL != curr) {
            /* prev on the list will be NULL, not a circular list */
            tmp = list_node_next(curr);

            if (TRUE != list_remove(list, curr, free_data)) {
                  DEBUG(__FILE__, __LINE__, "list_node_detach failed");
                  return FALSE;
            }
            list->first = tmp;
            curr = tmp;
      }

      list->first = NULL;
      list->last = NULL;
      list->nodes = 0;

      return TRUE;

}

/* print an entire list */
void list_dump(list_t *list, void (*data_print)(const void *))
{
      list_node_t *curr;

#ifdef _DEBUG
      assert(NULL != list);
#endif

      list_head_dump(list);

      for (curr = list->first; curr != NULL; curr = curr->next) {
            list_node_dump(curr, data_print);
      }

}

/* apply a function to the data of all members of the list */
void list_map(list_t *list, void (*mapped)(void *))
{
      list_node_t *curr;

#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != mapped);
#endif

      for (curr = list->first; curr != NULL; curr = curr->next)
            (*mapped)(curr->data);

}

/* apply a function to all members of the list */
void list_map_node(list_t *list, void (*mapped)(list_node_t *))
{
      list_node_t *curr;

#ifdef _DEBUG
      assert(NULL != list);
      assert(NULL != mapped);
#endif

      for (curr = list->first; curr != NULL; curr = curr->next)
            (*mapped)(curr);

}

/* print a single list_t */
static void list_head_dump(list_t *list)
{

#ifdef _DEBUG
      assert(NULL != list);
#endif

      PRINTF(
            "list_t(%p){\n",
            (void *)list
      );
            
      if (NULL != list) {
            PRINTF(
                  "\tnodes: %d\n"
                  "\tfirst: %p\n"
                  "\tlast: %p\n"
                  ,list->nodes
                  ,(void *)list->first
                  ,(void *)list->last
            );
      }
      PRINTF("}\n");

}

/* print a single node */
static void list_node_dump(list_node_t *node, void (*data_print)(const void *))
{

#ifdef _DEBUG
      assert(NULL != node);
      assert(NULL != data_print);
#endif

      OUTF("list_node_t(%p){\n", (void *)node);

      if (NULL != node)
            OUTF("\tprev: %p\n\tnext: %p\n",
                  (void *)node->prev, (void *)node->next);

      if (NULL != data_print)
            data_print(node->data);

      OUTF("}\n");

}

/* a callback you can pass to list_dump() if node->data is a char array */
static void list_dump_cb_chars(const void *v)
{
      /* v may be NULL */

      PRINTF("\tdata(%p){\n", v);
      if (NULL != v)
            PRINTF("\t\t\"%s\"\n", (const char *)v);
      PRINTF("}\n");
}


Generated by  Doxygen 1.6.0   Back to index