#include <stdlib.h>
#include <malloc.h>
#include "list.h"
static int nodata; /* if data points to this, then the element was actually deleted */
t_list * list_create(void)
{
t_list * list;
if (!(list = malloc(sizeof(t_list))))
{
return 0;
}
list->head = 0;
list->tail = 0;
list->len = 0;
return list;
}
int list_destroy(t_list * list)
{
if (!list)
{
return -1;
}
list_purge(list);
if (list->head) {
//eventlog(eventlog_level_error,"list_destroy","got non-empty list");
}
free(list);
return 0;
}
int list_purge(t_list * list)
{
t_elem * curr;
t_elem * head;
t_elem * tail;
t_elem * next;
t_elem * * change;
if (!list)
{
return -1;
}
head = 0;
tail = 0;
change = 0;
for (curr=list->head; curr; curr=next)
{
next = curr->next;
if (curr->data==&nodata)
{
if (change)
*change = next;
free(curr);
}
else
{
tail = curr;
if (!head)
head = curr;
change = &curr->next;
}
}
list->head = head;
list->tail = tail;
return 0;
}
int list_check(t_list const * list)
{
unsigned int emptycnt;
unsigned int validcnt;
t_elem const * tail;
t_elem const * curr;
int ret=0;
if (!list)
{
return -1;
}
emptycnt=validcnt = 0;
tail = 0;
for (curr=list->head; curr; curr=curr->next)
{
if (tail)
{
if (curr==tail) /* tail is currently the previous node */
{
//eventlog(eventlog_level_error,"list_check","list is circular (curr==prev==%p)",curr);
return -1;
}
if (curr->next==tail)
{
//eventlog(eventlog_level_error,"list_check","list is circular (curr->next==prev==%p)",curr);
return -1;
}
if (curr==list->head)
{
//eventlog(eventlog_level_error,"list_check","list is circular (curr==list->head==%p)",curr);
return -1;
}
}
if (curr->data==&nodata)
emptycnt++;
else
validcnt++;
tail = curr;
}
if (emptycnt>8 && emptycnt>validcnt+1) {
/* arbitrary heuristic to detect missing list_purge() calls */
//eventlog(eventlog_level_error,"list_check","emptycnt=%u but validcnt=%u",emptycnt,validcnt);
}
if (list->len!=validcnt)
{
//eventlog(eventlog_level_error,"list_check","list->len=%u but validcnt=%u",list->len,validcnt);
ret = -1;
}
if (list->head && !list->tail)
{
//eventlog(eventlog_level_error,"list_check","list->head=%p but list->tail=%p (len=%u)",list->head,list->tail,list->len);
ret = -1;
}
if (list->tail!=tail)
{
//eventlog(eventlog_level_error,"list_check","list->tail=%p but tail=%p",list->tail,tail);
ret = -1;
}
if (validcnt!=0 && !list->head)
{
//eventlog(eventlog_level_error,"list_check","validcnt=%u but list->head=%p",validcnt,list->head);
ret = -1;
}
return ret;
}
unsigned int list_get_length(t_list const * list)
{
if (!list)
{
//eventlog(eventlog_level_error,"list_get_length","got 0 list");
return 0;
}
return list->len;
}
int list_prepend_data(t_list * list, void * data)
{
t_elem * elem;
if (!list)
{
//eventlog(eventlog_level_error,"list_prepend_data","got 0 list");
return -1;
}
if (!(elem = malloc(sizeof(t_elem))))
{
//eventlog(eventlog_level_error,"list_prepend_data","could not allocate memory for elem");
return -1;
}
elem->data = data;
elem->next = list->head;
list->head = elem;
if (!list->tail)
list->tail = elem;
list->len++;
return 0;
}
int list_append_data(t_list * list, void * data)
{
t_elem * elem;
if (!list)
{
//eventlog(eventlog_level_error,"list_append_data","got 0 list");
return -1;
}
if (!(elem = malloc(sizeof(t_elem))))
{
//eventlog(eventlog_level_error,"list_append_data","could not allocate memory for elem");
return -1;
}
elem->data = data;
elem->next = 0;
if (!list->head)
list->head = elem;
if (list->tail)
list->tail->next = elem;
list->tail = elem;
list->len++;
return 0;
}
t_elem * list_get_elem_by_data(t_list const * list, void const * data)
{
t_elem * curr;
if (!list)
{
//eventlog(eventlog_level_error,"list_get_elem_by_data","got 0 list");
return 0;
}
LIST_TRAVERSE(list,curr)
if (curr->data==data)
return curr;
return 0;
}
t_elem const * list_get_elem_by_data_const(t_list const * list, void const * data)
{
t_elem const * curr;
if (!list)
{
//eventlog(eventlog_level_error,"list_get_elem_by_data_const","got 0 list");
return 0;
}
LIST_TRAVERSE_CONST(list,curr)
if (curr->data==data)
return curr;
return 0;
}
int list_remove_elem(t_list * list, t_elem * elem)
{
if (!list)
{
//eventlog(eventlog_level_error,"list_remove_elem","got 0 list");
return -1;
}
if (!elem)
{
//eventlog(eventlog_level_error,"list_remove_elem","got 0 elem");
return -1;
}
if (elem->data==&nodata)
{
//eventlog(eventlog_level_error,"list_remove_elem","got deleted elem");
return -1;
}
elem->data = &nodata;
list->len--;
return 0;
}
int list_remove_data(t_list * list, void const * data)
{
t_elem * elem;
if (!list)
{
//eventlog(eventlog_level_error,"list_remove_data","got 0 list");
return -1;
}
if (!(elem = list_get_elem_by_data(list,data)))
return -1;
return list_remove_elem(list,elem);
}
int elem_set_data(t_elem * elem, void * data)
{
if (!elem)
{
//eventlog(eventlog_level_error,"elem_set_data","got 0 elem");
return -1;
}
if (elem->data==&nodata)
{
//eventlog(eventlog_level_error,"elem_set_data","got deleted elem");
return -1;
}
if (data==&nodata)
{
//eventlog(eventlog_level_error,"elem_set_data","got bad data");
return -1;
}
elem->data = data;
return 0;
}
void * elem_get_data(t_elem const * elem)
{
if (!elem)
{
//eventlog(eventlog_level_error,"elem_get_data","got 0 elem");
return 0;
}
if (elem->data==&nodata)
{
//eventlog(eventlog_level_error,"elem_get_data","got deleted elem");
return 0;
}
return elem->data;
}
void * list_get_data_by_pos(t_list const * list, unsigned int pos)
{
t_elem const * curr;
unsigned int len;
len = 0;
LIST_TRAVERSE_CONST(list,curr)
if (len++==pos)
return curr->data;
//eventlog(eventlog_level_error,"list_get_data_by_pos","requested position %u but len=%u",pos,len);
return 0;
}
t_elem * list_get_first(t_list const * list)
{
t_elem * curr;
if (!list)
{
//eventlog(eventlog_level_error,"list_get_first","got 0 list");
return 0;
}
for (curr=list->head; curr; curr=curr->next)
if (curr->data!=&nodata)
return curr;
return curr;
}
t_elem const * list_get_first_const(t_list const * list)
{
t_elem const * curr;
if (!list)
{
//eventlog(eventlog_level_error,"list_get_first_const","got 0 list");
return 0;
}
for (curr=list->head; curr; curr=curr->next)
if (curr->data!=&nodata)
return curr;
return curr;
}
t_elem * elem_get_next(t_elem const * elem)
{
t_elem * curr;
if (!elem)
{
//eventlog(eventlog_level_error,"elem_get_next","got 0 elem");
return 0;
}
for (curr=elem->next; curr; curr=curr->next)
if (curr->data!=&nodata)
return curr;
return curr;
}
t_elem const * elem_get_next_const(t_elem const * elem)
{
t_elem const * curr;
if (!elem)
{
//eventlog(eventlog_level_error,"elem_get_next_const","got 0 elem");
return 0;
}
for (curr=elem->next; curr; curr=curr->next)
if (curr->data!=&nodata)
return curr;
return curr;
}
#ifndef _LIST_H_
#define _LIST_H_
typedef struct elem
{
void * data;
struct elem * next;
}
t_elem;
typedef struct list
{
unsigned int len;
t_elem * head;
t_elem * tail;
}
t_list;
t_list * list_create(void);
int list_destroy(t_list * list);
int list_purge(t_list * list);
int list_check(t_list const * list);
unsigned int list_get_length(t_list const * list);
int list_prepend_data(t_list * list, void * data);
int list_append_data(t_list * list, void * data);
t_elem * list_get_elem_by_data(t_list const * list, void const * data);
t_elem const * list_get_elem_by_data_const(t_list const * list, void const * data);
int list_remove_data(t_list * list, void const * data); /* delete matching item */
int list_remove_elem(t_list * list, t_elem * elem);
void * list_get_data_by_pos(t_list const * list, unsigned int pos);
t_elem * list_get_first(t_list const * list);
t_elem const * list_get_first_const(t_list const * list);
void * elem_get_data(t_elem const * elem);
int elem_set_data(t_elem * elem, void * data);
t_elem * elem_get_next(t_elem const * elem);
t_elem const * elem_get_next_const(t_elem const * elem);
#define LIST_TRAVERSE(list,curr) for (curr=(list)?list_get_first(list):(NULL); curr; curr=elem_get_next(curr))
#define LIST_TRAVERSE_CONST(list,curr) for (curr=(list)?list_get_first_const(list):(NULL); curr; curr=elem_get_next_const(curr))
#endif
