* File name: m_list.h
* Author: Seree Rakwong
* Date: 13-SEP-2013
*
* A list is implemented by the range as [a, b) (including a, but b)
*/
#ifndef _MLIST_H_
#define _MLIST_H_
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
extern "C" {
#endif
typedef void* mlist_t;
typedef void* mlist_item_t;
/*
* create and destroy a list
*/
long mlist_init();
void mlist_release();
mlist_t mlist_create();
void mlist_destroy(mlist_t list);
unsigned long mlist_get_count(mlist_t list);
/*
* manipulate data in the list
*/
mlist_item_t mlist_insert_first(mlist_t list, const void* data, size_t size);
mlist_item_t mlist_insert_last(mlist_t list, const void* data, size_t size);
mlist_item_t mlist_insert_before(mlist_t list, mlist_item_t item_after, const void* data, size_t size);
mlist_item_t mlist_insert_after(mlist_t list, mlist_item_t item_before, const void* data, size_t size);
/*
* mlist_remove_*
* return:
* <0 - errors
* =0 - successful
* >0 - ok, but the list is not created by meo_create_list() or
* the list is null object
*/
int mlist_remove_at(mlist_t list, mlist_item_t item);
int mlist_remove_all(mlist_t list);
int mlist_remove_first(mlist_t list);
int mlist_remove_last(mlist_t list);
int meo_set_item(mlist_t list, mlist_item_t item, const void* data, size_t size);
/*
* traversal
*/
mlist_item_t mlist_get_begin(mlist_t list);
mlist_item_t mlist_get_end(mlist_t list);
mlist_item_t mlist_get_next(mlist_t list, mlist_item_t item);
mlist_item_t mlist_get_prev(mlist_t list, mlist_item_t item);
size_t mlist_get_item(mlist_item_t item, void* data, size_t size); /*deep copy*/
void* mlist_get_item_at(mlist_item_t item, size_t* size); /*copy pointer*/
void mlist_set_item_at(mlist_item_t item, void* data, size_t size); /*copy pointer*/
/*
* int (*pf_enum)(const void*, size_t)
* return 0 = continue reading
* otherwise break
*/
void mlist_enumerate_items(mlist_t list, int (*pf_enum)(const void*, size_t));
/*
* int (*pf_cmp)(const void*, size_t, const void*, size_t)
* return 0 = items are equal
* otherwise not equal
*/
mlist_item_t mlist_find_first(mlist_t list, const void* data, size_t size, int (*pf_cmp)(const void*, size_t, const void*, size_t));
mlist_item_t mlist_find_next(mlist_t list, mlist_item_t next_item, const void* data, size_t size, int (*pf_cmp)(const void*, size_t, const void*, size_t));
#ifdef __cplusplus
}
#endif
#endif /* _MLIST_H_ */
/*
* File name: m_list.c
* Author: Seree Rakwong
* Date: 13-SEP-2013
*/
#include "m_list.h"
#define MLIST_SIGNATURE 0x6c697374
#define MLIST_ITEM_SIGNATURE 0x6c697300
#define MLIST_MAX_ITEMS 0xffffffff
#ifdef __cplusplus
extern "C" {
#endif
/*
* encapsulate the list and the item list structure
*/
typedef struct mlist_item_s
{
struct mlist_item_s *prev;
struct mlist_item_s *next;
void *data;
size_t size;
unsigned long signature;
mlist_t owner;
} mlist_item_s, *mlist_item_sp;
typedef struct mlist_s
{
struct mlist_item_s *head;
struct mlist_item_s *tail;
unsigned long items;
unsigned long signature;
} mlist_s, *mlist_sp;
/*
* #################### BOF helper functions ####################
*/
mlist_sp mlist_verify_list(mlist_t list);
mlist_item_sp mlist_verify_list_item(mlist_t list, mlist_item_t item);
mlist_item_sp mlist_create_list_item(mlist_t list);
void mlist_destroy_list_item(mlist_item_t item);
mlist_sp mlist_verify_list(mlist_t list)
{
mlist_sp plist = (mlist_sp)list;
if (!plist || plist->signature != MLIST_SIGNATURE)
return 0;
return plist;
}
mlist_item_sp mlist_verify_list_item(mlist_t list, mlist_item_t item)
{
mlist_sp plist = (mlist_sp)list;
mlist_item_sp pitem = (mlist_item_sp)item;
if (!plist || !pitem || pitem->signature != MLIST_ITEM_SIGNATURE || pitem->owner != list)
return 0;
return pitem;
}
mlist_item_sp mlist_create_list_item(mlist_t list)
{
mlist_item_sp pitem = (mlist_item_sp)malloc(sizeof(mlist_item_s));
if (!pitem)
{
return 0;
}
pitem->next = 0;
pitem->prev = 0;
pitem->data = 0;
pitem->size = 0;
pitem->signature = (long)MLIST_ITEM_SIGNATURE;
pitem->owner = list;
return pitem;
}
void mlist_destroy_list_item(mlist_item_t item)
{
mlist_item_sp pitem = (mlist_item_sp)item;
free(pitem->data);
free(pitem);
pitem = 0;
}
/*
#################### EOF helper functions ####################
*/
static mlist_sp g_pNullList = 0;
long
mlist_init()
{
if (!g_pNullList)
{
g_pNullList = (mlist_sp)mlist_create();
if (!g_pNullList)
return 0;
}
return 1;
}
void
mlist_release()
{
mlist_destroy(g_pNullList);
g_pNullList = 0;
}
mlist_t mlist_create()
{
/*
* allocate a new memory block
*/
mlist_sp plist = (mlist_sp)malloc(sizeof(mlist_s));
if (!plist)
{
return 0;
}
/*
* initialize the list
* at the initialization, its head must be pointed to its tail
*/
plist->tail = mlist_create_list_item((mlist_t)plist);
if (!plist->tail)
{
mlist_destroy((mlist_t)plist);
return 0;
}
plist->head = plist->tail;
plist->items = 0;
plist->signature = MLIST_SIGNATURE;
return (mlist_t)plist;
}
void mlist_destroy(mlist_t list)
{
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return;
/*
* remove all items in the list
*/
mlist_remove_all(list);
/*
* free the memory block
*/
mlist_destroy_list_item((mlist_item_t)plist->tail);
free(plist);
list = 0;
}
unsigned long mlist_get_count(mlist_t list)
{
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return 0;
return plist->items;
}
int mlist_remove_all(mlist_t list)
{
mlist_item_sp pitem = 0;
mlist_item_t item = 0;
mlist_sp plist = mlist_verify_list(list);
if (plist == 0)
return 1;
item = mlist_get_begin(list);
while (item != mlist_get_end(list))
{
pitem = mlist_verify_list_item(list, item);
/*
* read the next item before removing the current item
*/
item = mlist_get_next(list, item);
mlist_destroy_list_item((mlist_item_t)pitem);
}
/*
* set the tail and head of the list
*/
plist->tail->prev = 0;
plist->head = plist->tail;
plist->items = 0;
return 0;
}
int mlist_remove_at(mlist_t list, mlist_item_t item)
{
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem = mlist_verify_list_item(list, item);
/* is item ok to be removed? */
if (!plist || !pitem)
return 0;
/* is it a head item? */
if (pitem == plist->head)
return mlist_remove_first(list);
/* is it a tail item? */
if (pitem == plist->tail)
return mlist_remove_last(list);
/* link them */
if (pitem->next)
pitem->next->prev = pitem->prev;
if (pitem->prev)
pitem->prev->next = pitem->next;
/* remove it */
mlist_destroy_list_item(item);
if (plist->items > 0)
plist->items--;
return 0;
}
int mlist_remove_first(mlist_t list)
{
mlist_item_sp first = 0;
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return 0;
first = plist->head;
if (first == plist->tail)
/* no more item to remove */
return 0;
plist->head = first->next;
plist->head->prev = 0;
/* ok, we have already freed */
mlist_destroy_list_item((mlist_item_t)first);
if (plist->items > 0)
plist->items--;
return 0;
}
int mlist_remove_last(mlist_t list)
{
mlist_item_sp last = 0;
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return 0;
last = plist->tail->prev;
if (!last)
/* no more item to remove */
return 0;
plist->tail->prev = last->prev;
if (last->prev)
last->prev->next = plist->tail;
/* ok, we have already freed */
mlist_destroy_list_item((mlist_item_t)last);
if (plist->items > 0)
plist->items--;
return 0;
}
int mlist_set_item(mlist_t list, mlist_item_t item, const void* data, size_t size)
{
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem = mlist_verify_list_item(list, item);
void* new_data = malloc(size);
if (!plist || !pitem || !data || size == 0 || !new_data)
return 1;
/* clear old data */
free(pitem->data);
/* allocate the new data size */
pitem->size = size;
pitem->data = new_data;
memset(pitem->data, 0, size);
memcpy(pitem->data, data, size);
return 0;
}
mlist_item_t mlist_get_begin(mlist_t list)
{
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return 0;
return (mlist_item_t)plist->head;
}
mlist_item_t mlist_get_end(mlist_t list)
{
mlist_sp plist = mlist_verify_list(list);
if (!plist)
return 0;
return (mlist_item_t)plist->tail;
}
mlist_item_t mlist_get_next(mlist_t list, mlist_item_t item)
{
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem = mlist_verify_list_item(list, item);
if (!plist || !pitem)
return 0;
return (mlist_item_t)pitem->next;
}
mlist_item_t mlist_get_prev(mlist_t list, mlist_item_t item)
{
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem = mlist_verify_list_item(list, item);
if (!plist || !pitem)
return 0;
return (mlist_item_t)pitem->prev;
}
size_t mlist_get_item(mlist_item_t item, void* data, size_t size)
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (!item || !data)
return 0;
if (size > pitem->size)
size = pitem->size;
memset(data, 0, size);
memcpy(data, pitem->data, size);
return size;
}
void* mlist_get_item_at(mlist_item_t item, size_t* size) /*copy pointer*/
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (!item)
return 0;
*size = pitem->size;
return pitem->data;
}
void mlist_set_item_at(mlist_item_t item, void* data, size_t size) /*copy pointer*/
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (!item)
return;
pitem->size = size;
pitem->data = data;
}
mlist_item_t mlist_insert_first(mlist_t list, const void* data, size_t size)
{
mlist_item_sp pitem = 0;
mlist_sp plist = mlist_verify_list(list);
void* new_data = 0;
if (!plist || !data || size == 0)
return 0;
if (plist->items == MLIST_MAX_ITEMS)
{
return 0;
}
new_data = malloc(size);
if (!new_data)
{
return 0;
}
pitem = mlist_create_list_item(list);
if (!pitem)
{
return 0;
}
/*
* copy data now
*/
pitem->size = size;
pitem->data = new_data;
memset(pitem->data, 0, size);
memcpy(pitem->data, data, size);
/*
* link the new item to the list
*/
pitem->next = plist->head;
plist->head->prev = pitem;
plist->head = pitem;
plist->items++;
return (mlist_item_t)pitem;
}
mlist_item_t mlist_insert_last(mlist_t list, const void* data, size_t size)
{
mlist_item_sp pitem = 0;
mlist_sp plist = mlist_verify_list(list);
void* new_data = 0;
if (!plist || !data || size == 0)
return 0;
if (plist->items == MLIST_MAX_ITEMS)
{
return 0;
}
new_data = malloc(size);
if (!new_data)
{
return 0;
}
pitem = mlist_create_list_item(list);
if (!pitem)
{
return 0;
}
/*
* copy data now
*/
pitem->size = size;
pitem->data = new_data;
memset(pitem->data, 0, size);
memcpy(pitem->data, data, size);
/*
* link the new item to the list
*/
pitem->next = plist->tail;
pitem->prev = plist->tail->prev;
if (plist->tail->prev && plist->tail->prev->next)
plist->tail->prev->next = pitem;
plist->tail->prev = pitem;
if (plist->head == plist->tail)
plist->head = pitem;
plist->items++;
return (mlist_item_t)pitem;
}
mlist_item_t mlist_insert_before(mlist_t list, mlist_item_t item_after, const void* data, size_t size)
{
mlist_item_sp pitem = 0;
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem_after = mlist_verify_list_item(list, item_after);
void* new_data = 0;
if (!pitem_after || pitem_after == plist->head)
{
return mlist_insert_first(list, data, size);
}
if (!plist || !data || size == 0)
return 0;
if (plist->items == MLIST_MAX_ITEMS)
{
return 0;
}
new_data = malloc(size);
if (!new_data)
{
return 0;
}
pitem = mlist_create_list_item(list);
if (!pitem)
{
return 0;
}
/*
* copy data now
*/
pitem->size = size;
pitem->data = new_data;
memset(pitem->data, 0, size);
memcpy(pitem->data, data, size);
/*
* link the new item to the list
*/
pitem->next = pitem_after;
pitem->prev = pitem_after->prev;
if (pitem_after->prev && pitem_after->prev->next)
pitem_after->prev->next = pitem;
pitem_after->prev = pitem;
plist->items++;
return (mlist_item_t)pitem;
}
mlist_item_t mlist_insert_after(mlist_t list, mlist_item_t item_before, const void* data, size_t size)
{
mlist_item_sp pitem = 0;
mlist_sp plist = mlist_verify_list(list);
mlist_item_sp pitem_before = mlist_verify_list_item(list, item_before);
void* new_data = 0;
if (!pitem_before || pitem_before == plist->tail){
return mlist_insert_last(list, data, size);
}
if (!plist || !data || size == 0)
return 0;
if (plist->items == MLIST_MAX_ITEMS)
{
return 0;
}
new_data = malloc(size);
if (!new_data)
{
return 0;
}
pitem = mlist_create_list_item(list);
if (!pitem)
{
return 0;
}
/*
* copy data now
*/
pitem->size = size;
pitem->data = new_data;
memset(pitem->data, 0, size);
memcpy(pitem->data, data, size);
/*
* link the new item to the list
*/
pitem->prev = pitem_before;
pitem->next = pitem_before->next;
if (pitem_before->next)
pitem_before->next->prev = pitem;
pitem_before->next = pitem;
plist->items++;
return (mlist_item_t)pitem;
}
mlist_item_t mlist_find_first(mlist_t list, const void* data, size_t size, int(*pf_cmp)(const void*, size_t, const void*, size_t))
{
mlist_item_t item = mlist_get_begin(list);
for (; item != mlist_get_end(list); item = mlist_get_next(list, item))
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (pf_cmp(data, size, pitem->data, pitem->size) == 0)
{
return item;
}
}
return 0;
}
mlist_item_t mlist_find_next(mlist_t list, mlist_item_t next_item, const void* data, size_t size, int(*pf_cmp)(const void*, size_t, const void*, size_t))
{
mlist_item_t item = next_item;
for (; item != mlist_get_end(list); item = mlist_get_next(list, item))
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (pf_cmp(data, size, pitem->data, pitem->size) == 0)
{
return item;
}
}
return 0;
}
void mlist_enumerate_items(mlist_t list, int(*pf_enum)(const void*, size_t))
{
mlist_item_t item = mlist_get_begin(list);
for (; item != mlist_get_end(list); item = mlist_get_next(list, item))
{
mlist_item_sp pitem = (mlist_item_sp)item;
if (pf_enum(pitem->data, pitem->size) != 0)
{
break;
}
}
}
#ifdef __cplusplus
}
#endif
No comments:
Post a Comment