#include <stdlib.h> /* for free() */
#include <stdio.h> /* for fprintf() */
#include <string.h> /* for memset() */
#include "list.h"
#ifdef MEMWATCH
#include "memwatch.h"
#endif
/* structures for constructing the list */
struct _listheader
{
struct _listheader *next;
void *payload;
struct _listheader *pool_next;
};
struct _list
{
struct _listheader *head;
struct _listheader *tail;
unsigned long len;
struct _list *pool_next;
struct _list *pool_prev;
};
struct _list_iterator
{
struct _listheader *cur;
List l;
};
struct cleanup
{
struct cleanup *next;
void *data;
};
static List lPool = NULL;
static List lPoolUsed = NULL;
static unsigned long long lPoolSize = 0; /* for exponential growth */
static struct cleanup *lCleanupPool = NULL;
static inline List get_l(void);
static void fill_l_pool(void);
static struct _listheader *lhPool = NULL;
static unsigned long long lhPoolSize = 0; /* for exponential growth */
static struct cleanup *lhCleanupPool = NULL;
static inline struct _listheader * get_lh(void);
static void fill_lh_pool(void);
static void poolReturn(struct _listheader *lh);
/* This sets up the memory pool(s) */
void lists_init()
{ /*{{{ */
fill_lh_pool();
fill_l_pool();
} /*}}} */
/* This clean up the memory pool(s) */
void lists_cleanup()
{ /*{{{ */
struct cleanup *freec;
struct _listheader *freeme;
List freeme2;
while (lhCleanupPool != NULL) {
freec = lhCleanupPool;
freeme = freec->data;
lhCleanupPool = lhCleanupPool->next;
free(freeme);
free(freec);
}
while (lCleanupPool != NULL) {
freec = lCleanupPool;
freeme2 = freec->data;
lCleanupPool = lCleanupPool->next;
free(freeme2);
free(freec);
}
} /*}}} */
/* This returns a struct to the pool */
void poolReturn(struct _listheader *lh)
{ /*{{{ */
memset(lh, 0, sizeof(struct _listheader));
lh->pool_next = lhPool;
lhPool = lh;
} /*}}} */
/* This fills the list header memory pool with 1024 items (or doubles the pool
* size) */
static void fill_lh_pool()
{ /*{{{ */
struct _listheader *tlist;
struct _listheader *temp;
struct cleanup *ch;
size_t newobjcount;
size_t i;
newobjcount = (lhPoolSize == 0) ? 1024 : lhPoolSize;
tlist = calloc(newobjcount, sizeof(struct _listheader));
ch = calloc(1, sizeof(struct cleanup));
ch->data = tlist;
ch->next = lhCleanupPool;
lhCleanupPool = ch;
for (i = 0; i < newobjcount; ++i) {
temp = &(tlist[i]);
temp->pool_next = lhPool;
lhPool = temp;
}
lhPoolSize += newobjcount;
} /*}}} */
/* This fills the list item memory pool with 2 items (or doubles the pool
* size) */
static void fill_l_pool()
{ /*{{{ */
size_t i, newobjcount;
List temp;
List tlist;
struct cleanup *ch;
newobjcount = (lPoolSize == 0) ? 2 : lPoolSize;
tlist = calloc(newobjcount, sizeof(struct _list));
ch = calloc(1, sizeof(struct cleanup));
ch->data = tlist;
ch->next = lCleanupPool;
lCleanupPool = ch;
for (i = 0; i < newobjcount; ++i) {
temp = &(tlist[i]);
temp->pool_next = lPool;
lPool = temp;
}
lPoolSize += newobjcount;
} /*}}} */
/* This frees up the memory allocated by the list */
void freeList(List * lst)
{ /*{{{ */
List thelist;
if (!lst) {
return;
}
thelist = *lst;
if (!thelist) {
return;
}
while (thelist->len > 0 && thelist->head != NULL) {
struct _listheader *h = thelist->head;
thelist->head = h->next;
thelist->len--;
poolReturn(h);
}
if (lPoolUsed == thelist) {
lPoolUsed = thelist->pool_next;
}
if (thelist->pool_next) {
thelist->pool_next->pool_prev = thelist->pool_prev;
}
if (thelist->pool_prev) {
thelist->pool_prev->pool_next = thelist->pool_next;
}
thelist->pool_next = lPool;
thelist->pool_prev = NULL;
lPool = thelist;
*lst = NULL;
} /*}}} */
/* this fetches a new list header from the pool */
static inline struct _listheader *get_lh()
{ /*{{{ */
struct _listheader *lh;
if (NULL == lhPool) {
fill_lh_pool();
}
lh = lhPool;
lhPool = lh->pool_next;
lh->pool_next = NULL;
return lh;
} /*}}} */
/* this fetches a new list from the pool */
static inline List get_l()
{ /*{{{ */
List l;
if (NULL == lPool) {
fill_l_pool();
}
l = lPool;
lPool = l->pool_next;
l->pool_next = lPoolUsed;
if (lPoolUsed) {
lPoolUsed->pool_prev = l;
}
lPoolUsed = l;
lPoolUsed->pool_prev = NULL;
return l;
} /*}}} */
/* This adds "addme" to the end of the list */
void addToList(List * lst, void *addme)
{ /*{{{ */
List list;
struct _listheader *pl;
pl = get_lh();
pl->payload = addme;
pl->next = NULL;
if (!lst) {
fprintf(stderr, "null list passed\n");
exit(EXIT_FAILURE);
}
list = *lst;
if (!list) {
list = *lst = get_l();
list->tail = list->head = pl;
list->len = 1;
} else {
if (list->tail) {
list->tail->next = pl;
list->tail = pl;
list->len++;
} else {
list->tail = list->head = pl;
list->len = 1;
}
}
} /*}}} */
/* This adds "addme" to the head of the list */
void addToListHead(List * lst, void *addme)
{ /*{{{ */
List list;
struct _listheader *pl;
pl = get_lh();
pl->payload = addme;
pl->next = NULL;
if (!lst) {
fprintf(stderr, "null list passed\n");
exit(EXIT_FAILURE);
}
list = *lst;
if (!list) {
list = *lst = get_l();
list->tail = list->head = pl;
list->len = 1;
} else {
if (list->head) {
pl->next = list->head;
list->head = pl;
list->len++;
} else {
list->tail = list->head = pl;
list->len = 1;
}
}
} /*}}} */
/* This removes the front of the list from the list and returns it */
void *getHeadOfList(List list)
{ /*{{{ */
void *payload;
struct _listheader *pl;
if (!list || !list->head) {
return NULL;
}
payload = list->head->payload;
pl = list->head;
list->head = list->head->next;
poolReturn(pl);
list->len--;
if (list->len == 0) {
list->head = list->tail = NULL;
}
return payload;
} /*}}} */
/* This returns the n'th element of the list, as if the list was an array */
void *peekListElement(List list, size_t n)
{ /*{{{ */
struct _listheader *pl;
size_t counter;
if (!list || !list->head || list->len <= n) {
if (!list) {
fprintf(stderr, "peekListElement: null List passed\n");
}
return NULL;
}
pl = list->head;
for (counter = 1; counter <= n; counter++) {
if (pl->next == NULL) {
return NULL;
}
pl = pl->next;
}
return pl->payload;
} /*}}} */
/* This returns the n'th element of the list, as if the list was an array,
* and removes it from the list */
void *getListElement(List list, size_t n)
{ /*{{{ */
struct _listheader *pl;
size_t counter;
void *payload = NULL;
struct _listheader *returnme;
if (!list || !list->head || list->len <= n) {
if (!list) {
fprintf(stderr, "getListElement: null List passed\n");
}
return NULL;
}
pl = list->head;
if (n > 0) {
for (counter = 1; counter < n; counter++) {
if (pl->next == NULL) {
return NULL;
}
pl = pl->next;
}
if (pl->next) {
payload = pl->next->payload;
returnme = pl->next;
pl->next = pl->next->next;
poolReturn(returnme);
}
} else {
payload = pl->payload;
returnme = pl;
list->head = pl->next;
if (list->tail == returnme) {
list->tail = NULL;
}
}
list->len --;
return payload;
} /*}}} */
/* This returns the head of the list */
inline void *peekAheadInList(List list)
{ /*{{{ */
if (list && list->head) {
return list->head->payload;
}
return NULL;
} /*}}} */
/* This tells you how many items there are in the list */
inline unsigned long listLen(List list)
{ /*{{{ */
if (list) {
return list->len;
} else {
return 0;
}
} /*}}} */
/* This returns a list iterator to a list */
ListIterator getListIterator(List list)
{ /*{{{ */
ListIterator li;
if (!list) {
return NULL;
}
li = malloc(sizeof(struct _list_iterator));
li->cur = list->head;
li->l = list;
return li;
} /*}}} */
/* This returns the value of the current element in the list Iterator */
void *currentListElement(ListIterator li)
{ /*{{{ */
if (!li || !(li->cur)) {
return NULL;
}
return li->cur->payload;
} /*}}} */
/* This iterates a list iterator */
void *nextListElement(ListIterator li)
{ /*{{{ */
void *payload;
if (!li || !(li->cur)) {
return NULL;
}
payload = li->cur->payload;
li->cur = li->cur->next;
return payload;
} /*}}} */
/* This sets the iterator back to the beginning */
void resetListIterator(ListIterator li)
{ /*{{{ */
if (li) {
li->cur = li->l->head;
}
} /*}}} */
/* This frees up a list iterator */
void freeListIterator(ListIterator li)
{ /*{{{ */
if (li) {
free(li);
}
} /*}}} */
/* This searches the list for a specific value, and removes it */
void removeFromList(List list, void * item)
{
struct _listheader *pl;
struct _listheader *returnme;
if (!list || !list->head) {
if (!list) {
fprintf(stderr, "getListElement: null List passed\n");
}
return;
}
pl = list->head;
if (pl->payload == item) {
if (list->head == list->tail) {
list->head = list->tail = NULL;
list->len = 0;
} else {
list->len --;
list->head = list->head->next;
}
poolReturn(pl);
} else {
while (pl->next && pl->next != list->tail) {
if (pl->next->payload == item) {
break;
}
if (pl->next->next == NULL) {
return;
}
pl = pl->next;
}
if (pl->next && pl->next->payload == item) {
returnme = pl->next;
pl->next = pl->next->next;
poolReturn(returnme);
}
}
}
syntax highlighted by Code2HTML, v. 0.9.1