J
jacob navia
/* -------------------------------------------------------------------
List routines sample implementation
-----------------------------------
This routines handle the List container class. This is a very general implementation
and efficiency considerations aren't yet primordial. Lists can have elements
of any size. This implement single linked Lists.
The design goals here are just correctness and showing how the implementation of
the proposed interface COULD be done.
---------------------------------------------------------------------- */
#ifndef DEFAULT_START_SIZE
#define DEFAULT_START_SIZE 20
#endif
#include "containers.h"
static int GetCount(List *AL);
static int IsReadOnly(List *AL);
static int SetReadOnly(List *AL,int flag);
static int Add(List *AL,void *newval);
static int Clear(List *AL);
static bool Contains(List *AL,void *str);
static List *Copy(List *AL);
static int IndexOf(List *AL,void *SearchedElement);
static int Insert(List *AL,void *);
static int InsertAt(List *AL,int idx,void *newval);
static void *GetElement(List *AL,int idx);
static int Remove(List *AL,void *);
static int RemoveAt(List *AL,int idx);
static int Finalize(List *AL);
/* The function Push is identical to Insert */
#define Push Insert
static list_element * Pop(List *AL);
static void *ReplaceAt(List *AL,int idx,void *newval);
static List *Sort(List *l,int (*compar)(const void *,const void *));
static List *Reverse(List *l);
static List *GetRange(List *l,int start,int end);
static bool Equal(List *l1,List *l2);
static List *Append(List *l1,List *l2);
static void Apply(List *L,int(Applyfn)(void *,void *),void *arg);
static CompareFunction SetCompareFunction(List *l,CompareFunction fn);
static ErrorFunction SetErrorFunction(List *l,ErrorFunction fn);
static ListInterface listlpVtbl = {
GetCount,IsReadOnly,SetReadOnly,Add,Clear,Contains,Copy,
IndexOf,Insert,InsertAt,GetElement,Remove,RemoveAt,Finalize,Push,Pop,ReplaceAt,
Sort,
Reverse,
GetRange,
Equal,
Append,
SetCompareFunction,
Apply,
SetErrorFunction,
};
#define LIST_READONLY 1
#define LIST_HASPOINTER 2
/*------------------------------------------------------------------------
Procedure: new_link ID:1
Purpose: Allocation of a new list element. If the element
size is zero, we have an heterogenous
list, and we allocate just a pointer to the data
that is maintained by the user.
Note that we allocate the size of a list element
plus the size of the data in a single
block. This block should be passed to the FREE
function.
Input: The list where the new element should be added and a
pointer to the data that will be added (can be
NULL).
Output: A pointer to the new list element (can be NULL)
Errors: If there is no memory returns NULL
------------------------------------------------------------------------*/
static list_element *new_link(List *l,void *data,const char *fname)
{
list_element *result;
/* Here we make an allocation for each element in the list. this is
highly inefficient, and could be optimized if we pre-allocate some
list elements and allocate, say, in blocks of 50 list_elements.
This sample implementation doesn't do this to keep the code simple
*/
result = MALLOC(sizeof(list_element)+l->ElementSize);
if (result != NULL) {
result->Next = NULL;
memcpy(result->Data,data,l->ElementSize);
}
else l->RaiseError(fname,CONTAINER_ERROR_NOMEMORY);
return result;
}
static int DefaultListCompareFunction(void *left,void *right,void *ExtraArgs)
{
int siz=((List *)ExtraArgs)->ElementSize;
return memcmp(left,right,siz);
}
/*------------------------------------------------------------------------
Procedure: newList ID:1
Purpose: Allocates a new list object header, initializes the
lpVtbl field and the element size
Input: The size of the elements of the list. Can be zero,
meaning that the list is made of objects managed by
the user
Output: A pointer to the newly created list or NULL if
there is no memory.
Errors: If element size is smaller than zero an error
routine is called. If there is no memory result is
NULL.
------------------------------------------------------------------------*/
List *newList(int elementsize)
{
List *result;
if (elementsize < 0) {
ContainerRaiseError("newList",CONTAINER_ERROR_BADARG);
return NULL;
}
else if (elementsize < sizeof(void *))
elementsize = sizeof(void *);
result = MALLOC(sizeof(List));
if (result == NULL) {
ContainerRaiseError("newList",CONTAINER_ERROR_NOMEMORY);
return NULL;
}
memset(result,0,sizeof(List));
result->ElementSize = elementsize;
result->lpVtbl = &listlpVtbl;
result->CompareFn = DefaultListCompareFunction;
result->RaiseError = ContainerRaiseError;
return result;
}
/*------------------------------------------------------------------------
Procedure: Contains ID:1
Purpose: Determines if the given data is in the container
Input: The list and the data to be searched
Output: Returns 1 (true) if the data is in there, false
otherwise
Errors: The same as the function IndexOf
------------------------------------------------------------------------*/
static bool Contains(List *l,void *data)
{
return (IndexOf(l,data) < 0) ? 0 : 1;
}
/*------------------------------------------------------------------------
Procedure: DestroyListElements ID:1
Purpose: Reclaims all memory used by a list
Input: The list
Output: None
Errors: None
------------------------------------------------------------------------*/
#ifdef NO_GC
static void DestroyListElements(List *l)
{
list_element *rvp = l->First,*tmp; /* Roving pointer */
while (rvp) {
tmp=rvp->Next;
FREE(rvp);
rvp = tmp;
}
}
#else
#define DestroyListElements(l)
#endif
/*------------------------------------------------------------------------
Procedure: Clear ID:1
Purpose: Reclaims all memory used by a list. The list header
itself is not reclaimed but zeroed. Note that the
list must be writable.
Input: The list to be cleared
Output: Returns the number of elemnts that were in the list
if OK, CONTAINER_ERROR_READONLY otherwise.
Errors: None
------------------------------------------------------------------------*/
static int Clear(List *l)
{
int r;
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
r = l->count;
DestroyListElements(l);
memset(l,0,sizeof(List));
return r;
}
/*------------------------------------------------------------------------
Procedure: Add ID:1
Purpose: Adds an element to the list
Input: The list and the elemnt to be added
Output: Returns the number of elements in the list or a
negative error code if an error occurs.
Errors: The element to be added can't be NULL, and the list
must be writable.
------------------------------------------------------------------------*/
static int Add(List *l,void *elem)
{
list_element *newl;
if (elem == NULL) {
l->RaiseError("Add",CONTAINER_ERROR_BADARG);
return CONTAINER_ERROR_BADARG;
}
if (l->Flags &LIST_READONLY) {
return CONTAINER_ERROR_READONLY;
}
newl = new_link(l,elem,"Add");
if (newl == 0)
return CONTAINER_ERROR_NOMEMORY;
if (l->count == 0) {
l->First = newl;
}
else {
l->Last->Next = newl;
}
l->Last = newl;
return ++l->count;
}
/*------------------------------------------------------------------------
Procedure: SetReadOnly ID:1
Purpose: Sets/Unsets the read only flag.
Input: The list and the new value
Output: The old value of the flag
Errors: None
------------------------------------------------------------------------*/
static int SetReadOnly(List *l,int newval)
{
int result;
result = (l->Flags &LIST_READONLY) ? 1 : 0;
if (newval) {
l->Flags |= LIST_READONLY;
}
else
l->Flags &= ~LIST_READONLY;
return result;
}
/*------------------------------------------------------------------------
Procedure: IsReadOnly ID:1
Purpose: Queries the read only flag
Input: The list
Output: The state of the flag
Errors: None
------------------------------------------------------------------------*/
static int IsReadOnly(List *l)
{
return (l->Flags&LIST_READONLY) ? 1 : 0;
}
/*------------------------------------------------------------------------
Procedure: GetCount ID:1
Purpose: Returns the number of elements in the list
Input: The list
Output: The number of elements
Errors: None
------------------------------------------------------------------------*/
static int GetCount(List *l)
{
return l->count;
}
/*------------------------------------------------------------------------
Procedure: SetCompareFunction ID:1
Purpose: Defines the function to be used in comparison of
list elements
Input: The list and the new comparison function. If the new
comparison function is NULL no changes are done.
Output: Returns the old function
Errors: None
------------------------------------------------------------------------*/
static CompareFunction SetCompareFunction(List *l,CompareFunction fn)
{
CompareFunction oldfn = l->CompareFn;
if (fn != NULL) /* Treat NULL as an enquiry to get the compare function */
l->CompareFn = fn;
return oldfn;
}
/*------------------------------------------------------------------------
Procedure: Copy ID:1
Purpose: Copies a list. The result is fully allocated (list
elements and data).
Input: The list to be copied
Output: A pointer to the new list
Errors: None. Returns NULL if therfe is no memory left.
------------------------------------------------------------------------*/
static List *Copy(List *l)
{
List *result;
list_element *rvp,*newRvp,*last;
result = newList(l->ElementSize);
if (result == NULL)
return NULL;
rvp = l->First;
last = NULL;
while (rvp) {
newRvp = new_link(l,rvp->Data,"Copy");
if (result->First == NULL)
last = result->First = newRvp;
else {
last->Next = newRvp;
last = last->Next;
}
result->Last = newRvp;
result->count++;
rvp = rvp->Next;
}
return result;
}
/*------------------------------------------------------------------------
Procedure: Finalize ID:1
Purpose: Reclaims all memory for a list. The data, list
elements and the list header are reclaimed.
Input: The list to be destroyed. It should NOT be read-
only.
Output: Returns the old count or a negative value if an
error occurs (list not writable)
Errors: Needs a writable list
------------------------------------------------------------------------*/
static int Finalize(List *l)
{
int r,t;
r = l->count;
t = Clear(l);
if (t < 0)
return t;
FREE(l);
return r;
}
/*------------------------------------------------------------------------
Procedure: GetElement ID:1
Purpose: Returns the data associated with a given position
Input: The list and the position
Output: A pointer to the data
Errors: NULL if error in the positgion index
------------------------------------------------------------------------*/
static void * GetElement(List *l,int position)
{
list_element *rvp;
if (position >= (signed)l->count || position < 0) {
l->RaiseError("GetElement",CONTAINER_ERROR_INDEX);
return NULL;
}
rvp = l->First;
while (position) {
rvp = rvp->Next;
position--;
}
return rvp->Data;
}
static void * ReplaceAt(List *l,int position,void *data)
{
list_element *rvp;
/* Error checking */
if (position >= l->count || position < 0) {
l->RaiseError("ReplaceAt",CONTAINER_ERROR_INDEX);
return NULL;
}
if (l->Flags & LIST_READONLY)
return NULL;
/* Position at the right data item */
if (position == l->count-1)
rvp = l->Last;
else {
rvp = l->First;
while (position) {
rvp = rvp->Next;
position--;
}
}
/* Replace the data there */
if (l->ElementSize)
memcpy(rvp->Data , data,l->ElementSize);
else
memcpy(rvp->Data, &data,sizeof(void *));
return data;
}
/*------------------------------------------------------------------------
Procedure: GetRange ID:1
Purpose: Gets a consecutive sub sequence of the list within
two indexes.
Input: The list, the subsequence start and end
Output: A new freshly allocated list. If the source list is
empty or the range is empty, the result list is
empty too.
Errors: None
------------------------------------------------------------------------*/
static List *GetRange(List *l,int start,int end)
{
int counter;
List *result = newList(l->ElementSize);
list_element *newRvp,*rvp;;
if (l->count == 0)
return result;
if (end >= l->count)
end = l->count-1;
if (start > end)
return result;
if (start == l->count-1)
rvp = l->Last;
else {
rvp = l->First;
counter = 0;
while (counter < start) {
rvp = rvp->Next;
counter++;
}
}
while (start <= end) {
newRvp = new_link(l,rvp->Data,"GetRange");
if (result->Last == NULL) {
result->Last = result->First = newRvp;
}
else {
result->Last->Next = newRvp;
result->Last = newRvp;
}
result->count++;
rvp = rvp->Next;
start++;
}
return result;
}
/*------------------------------------------------------------------------
Procedure: Equal ID:1
Purpose: Compares the data of two lists. They must be of the
same length, the elements must have the same size
and the comparison functions must be the same. If
all this is true, the comparisons are done.
Input: The two lists to be compared
Output: Returns 1 if the two lists are equal, zero otherwise
Errors: None
------------------------------------------------------------------------*/
static bool Equal(List *l1,List *l2)
{
list_element *link1,*link2;
CompareFunction fn;
if (l1->count != l2->count)
return 0;
if (l1->ElementSize != l2->ElementSize)
return 0;
if (l1->count == 0)
return 1;
if (l1->CompareFn != l2->CompareFn)
return 1;
fn = l1->CompareFn;
link1 = l1->First;
link2 = l2->First;
while (link1 && link2) {
if (fn(link1->Data,link2->Data,l1))
return 0;
link1 = link1->Next;
link2 = link2->Next;
}
if (link1 || link2)
return 0;
return 1;
}
/*------------------------------------------------------------------------
Procedure: Insert ID:1
Purpose: Inserts an element at the start of the list
Input: The list and the data to insert
Output: The count of the list after insertion, or CONTAINER_ERROR_READONLY
if the list is not writable or CONTAINER_ERROR_NOMEMORY if there is
no more memory left.
Errors: None
------------------------------------------------------------------------*/
static int Insert(List *l,void *pdata)
{
list_element *rvp;
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
rvp = new_link(l,pdata,"Insert");
if (rvp == NULL)
return CONTAINER_ERROR_NOMEMORY;
rvp->Next = l->First;
l->First = rvp;
if (l->Last == NULL)
l->Last = rvp;
l->count++;
return l->count;
}
/*------------------------------------------------------------------------
Procedure: Pop ID:1
Purpose: Takes out the first element of a list.
Input: The list
Output: The first element or NULL if there is none or the
list is read only
Errors: None
------------------------------------------------------------------------*/
static list_element *Pop(List *l)
{
list_element *le;
if (l->count == 0 || (l->Flags & LIST_READONLY))
return NULL;
le = l->First;
if (l->count == 1) {
l->First = l->Last = NULL;
}
else l->First = l->First->Next;
l->count--;
return le;
}
static int InsertAt(List *l,int pos,void *pdata)
{
list_element *rvp,*elem;
if (pos < 0 || pos > l->count) {
l->RaiseError("InsertAt",CONTAINER_ERROR_BADARG);
return 0;
}
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
elem = new_link(l,pdata,"InsertAt");
if (elem == NULL)
return 0;
if (pos == l->count) {
if (pos == 0 && l->count == 0) {
l->First = elem;
l->Last = elem;
}
else {
l->Last->Next = elem;
l->Last = elem;
}
return ++l->count;
}
else if (pos == 0) {
elem->Next = l->First;
l->First = elem;
return ++l->count;
}
rvp = l->First;
while (pos > 0) {
rvp = rvp->Next;
pos--;
}
elem->Next = rvp->Next;
rvp->Next = elem;
return ++l->count;
}
static int Remove(List *l,void *elem)
{
int idx;
idx = IndexOf(l,elem);
if (idx <= 0)
return idx;
return RemoveAt(l,idx);
}
static int RemoveAt(List *l,int position)
{
list_element *rvp,*last;
if (position >= l->count || position < 0)
l->RaiseError("RemoveAt",CONTAINER_ERROR_BADARG);
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
rvp = l->First;
if (position == 0) {
if (l->First == l->Last) {
l->First = l->Last = NULL;
}
else {
l->First = l->First->Next;
}
}
else if (position == l->count - 1) {
while (rvp->Next != l->Last)
rvp = rvp->Next;
rvp->Next = NULL;
l->Last = rvp;
}
else {
position--;
last = rvp;
rvp = rvp->Next;
while (position > 0) {
rvp = rvp->Next;
position --;
}
last->Next = rvp->Next;
}
return --l->count;
}
static List *Append(List *l1,List *l2)
{
if (l1->count == 0)
return l2;
if (l2->count == 0)
return l1;
l1->Last->Next = l2->First;
l1->Last = l2->Last;
l1->count += l2->count;
return l1;
}
static List *Reverse(List *l)
{
list_element *tmp,*prev,*last,*rvp;
if (l->count < 2)
return l;
rvp = l->First;
l->First = l->Last;
last = prev = NULL;
while (rvp) {
last = rvp;
tmp = rvp->Next;
rvp->Next = prev;
prev = rvp;
rvp = tmp;
}
l->Last = prev;
return l;
}
/* Searches a List for a given data item
Returns a positive integer if found, negative if the end is reached
*/
static int IndexOf(List *l,void *ElementToFind)
{
list_element *rvp;
int r,i=0,es;
CompareFunction fn;
rvp = l->First;
fn = l->CompareFn;
es =l->ElementSize;
if (es == 0)
es = sizeof(void *);
while (rvp) {
r = fn(*(char **)rvp->Data,ElementToFind,l);
if (r == 0)
return i;
rvp = rvp->Next;
i++;
}
return -1;
}
static List *Sort(List *l,int (*compar)(const void *,const void *))
{
char **tab;
int i;
list_element *rvp,*newlink;
List *result;
if (l->count < 2)
return Copy(l);
tab = MALLOC(l->count * sizeof(void *));
if (tab == NULL)
l->RaiseError("Sort",CONTAINER_ERROR_NOMEMORY);
rvp = l->First;
for (i=0; i<l->count;i++) {
tab = rvp->Data;
rvp = rvp->Next;
}
qsort(tab,l->count,sizeof(void *),compar);
result = newList(l->ElementSize);
rvp = new_link(result,tab[0],"Sort");
result->First = rvp;
rvp->Next = NULL;
result->First = rvp;
i = 1;
while (i < l->count) {
newlink = new_link(result,tab,"Sort");
rvp->Next = newlink;
rvp = newlink;
rvp->Next = NULL;
}
result->Last = rvp;
return result;
}
static void Apply(List *L,int (Applyfn)(void *,void *),void *arg)
{
list_element *le;
le = L->First;
while (le) {
Applyfn(le->Data,arg);
le = le->Next;
}
}
static ErrorFunction SetErrorFunction(List *l,ErrorFunction fn)
{
ErrorFunction old;
old = l->RaiseError;
l->RaiseError = (fn) ? fn : EmptyErrorFunction;
return old;
}
List routines sample implementation
-----------------------------------
This routines handle the List container class. This is a very general implementation
and efficiency considerations aren't yet primordial. Lists can have elements
of any size. This implement single linked Lists.
The design goals here are just correctness and showing how the implementation of
the proposed interface COULD be done.
---------------------------------------------------------------------- */
#ifndef DEFAULT_START_SIZE
#define DEFAULT_START_SIZE 20
#endif
#include "containers.h"
static int GetCount(List *AL);
static int IsReadOnly(List *AL);
static int SetReadOnly(List *AL,int flag);
static int Add(List *AL,void *newval);
static int Clear(List *AL);
static bool Contains(List *AL,void *str);
static List *Copy(List *AL);
static int IndexOf(List *AL,void *SearchedElement);
static int Insert(List *AL,void *);
static int InsertAt(List *AL,int idx,void *newval);
static void *GetElement(List *AL,int idx);
static int Remove(List *AL,void *);
static int RemoveAt(List *AL,int idx);
static int Finalize(List *AL);
/* The function Push is identical to Insert */
#define Push Insert
static list_element * Pop(List *AL);
static void *ReplaceAt(List *AL,int idx,void *newval);
static List *Sort(List *l,int (*compar)(const void *,const void *));
static List *Reverse(List *l);
static List *GetRange(List *l,int start,int end);
static bool Equal(List *l1,List *l2);
static List *Append(List *l1,List *l2);
static void Apply(List *L,int(Applyfn)(void *,void *),void *arg);
static CompareFunction SetCompareFunction(List *l,CompareFunction fn);
static ErrorFunction SetErrorFunction(List *l,ErrorFunction fn);
static ListInterface listlpVtbl = {
GetCount,IsReadOnly,SetReadOnly,Add,Clear,Contains,Copy,
IndexOf,Insert,InsertAt,GetElement,Remove,RemoveAt,Finalize,Push,Pop,ReplaceAt,
Sort,
Reverse,
GetRange,
Equal,
Append,
SetCompareFunction,
Apply,
SetErrorFunction,
};
#define LIST_READONLY 1
#define LIST_HASPOINTER 2
/*------------------------------------------------------------------------
Procedure: new_link ID:1
Purpose: Allocation of a new list element. If the element
size is zero, we have an heterogenous
list, and we allocate just a pointer to the data
that is maintained by the user.
Note that we allocate the size of a list element
plus the size of the data in a single
block. This block should be passed to the FREE
function.
Input: The list where the new element should be added and a
pointer to the data that will be added (can be
NULL).
Output: A pointer to the new list element (can be NULL)
Errors: If there is no memory returns NULL
------------------------------------------------------------------------*/
static list_element *new_link(List *l,void *data,const char *fname)
{
list_element *result;
/* Here we make an allocation for each element in the list. this is
highly inefficient, and could be optimized if we pre-allocate some
list elements and allocate, say, in blocks of 50 list_elements.
This sample implementation doesn't do this to keep the code simple
*/
result = MALLOC(sizeof(list_element)+l->ElementSize);
if (result != NULL) {
result->Next = NULL;
memcpy(result->Data,data,l->ElementSize);
}
else l->RaiseError(fname,CONTAINER_ERROR_NOMEMORY);
return result;
}
static int DefaultListCompareFunction(void *left,void *right,void *ExtraArgs)
{
int siz=((List *)ExtraArgs)->ElementSize;
return memcmp(left,right,siz);
}
/*------------------------------------------------------------------------
Procedure: newList ID:1
Purpose: Allocates a new list object header, initializes the
lpVtbl field and the element size
Input: The size of the elements of the list. Can be zero,
meaning that the list is made of objects managed by
the user
Output: A pointer to the newly created list or NULL if
there is no memory.
Errors: If element size is smaller than zero an error
routine is called. If there is no memory result is
NULL.
------------------------------------------------------------------------*/
List *newList(int elementsize)
{
List *result;
if (elementsize < 0) {
ContainerRaiseError("newList",CONTAINER_ERROR_BADARG);
return NULL;
}
else if (elementsize < sizeof(void *))
elementsize = sizeof(void *);
result = MALLOC(sizeof(List));
if (result == NULL) {
ContainerRaiseError("newList",CONTAINER_ERROR_NOMEMORY);
return NULL;
}
memset(result,0,sizeof(List));
result->ElementSize = elementsize;
result->lpVtbl = &listlpVtbl;
result->CompareFn = DefaultListCompareFunction;
result->RaiseError = ContainerRaiseError;
return result;
}
/*------------------------------------------------------------------------
Procedure: Contains ID:1
Purpose: Determines if the given data is in the container
Input: The list and the data to be searched
Output: Returns 1 (true) if the data is in there, false
otherwise
Errors: The same as the function IndexOf
------------------------------------------------------------------------*/
static bool Contains(List *l,void *data)
{
return (IndexOf(l,data) < 0) ? 0 : 1;
}
/*------------------------------------------------------------------------
Procedure: DestroyListElements ID:1
Purpose: Reclaims all memory used by a list
Input: The list
Output: None
Errors: None
------------------------------------------------------------------------*/
#ifdef NO_GC
static void DestroyListElements(List *l)
{
list_element *rvp = l->First,*tmp; /* Roving pointer */
while (rvp) {
tmp=rvp->Next;
FREE(rvp);
rvp = tmp;
}
}
#else
#define DestroyListElements(l)
#endif
/*------------------------------------------------------------------------
Procedure: Clear ID:1
Purpose: Reclaims all memory used by a list. The list header
itself is not reclaimed but zeroed. Note that the
list must be writable.
Input: The list to be cleared
Output: Returns the number of elemnts that were in the list
if OK, CONTAINER_ERROR_READONLY otherwise.
Errors: None
------------------------------------------------------------------------*/
static int Clear(List *l)
{
int r;
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
r = l->count;
DestroyListElements(l);
memset(l,0,sizeof(List));
return r;
}
/*------------------------------------------------------------------------
Procedure: Add ID:1
Purpose: Adds an element to the list
Input: The list and the elemnt to be added
Output: Returns the number of elements in the list or a
negative error code if an error occurs.
Errors: The element to be added can't be NULL, and the list
must be writable.
------------------------------------------------------------------------*/
static int Add(List *l,void *elem)
{
list_element *newl;
if (elem == NULL) {
l->RaiseError("Add",CONTAINER_ERROR_BADARG);
return CONTAINER_ERROR_BADARG;
}
if (l->Flags &LIST_READONLY) {
return CONTAINER_ERROR_READONLY;
}
newl = new_link(l,elem,"Add");
if (newl == 0)
return CONTAINER_ERROR_NOMEMORY;
if (l->count == 0) {
l->First = newl;
}
else {
l->Last->Next = newl;
}
l->Last = newl;
return ++l->count;
}
/*------------------------------------------------------------------------
Procedure: SetReadOnly ID:1
Purpose: Sets/Unsets the read only flag.
Input: The list and the new value
Output: The old value of the flag
Errors: None
------------------------------------------------------------------------*/
static int SetReadOnly(List *l,int newval)
{
int result;
result = (l->Flags &LIST_READONLY) ? 1 : 0;
if (newval) {
l->Flags |= LIST_READONLY;
}
else
l->Flags &= ~LIST_READONLY;
return result;
}
/*------------------------------------------------------------------------
Procedure: IsReadOnly ID:1
Purpose: Queries the read only flag
Input: The list
Output: The state of the flag
Errors: None
------------------------------------------------------------------------*/
static int IsReadOnly(List *l)
{
return (l->Flags&LIST_READONLY) ? 1 : 0;
}
/*------------------------------------------------------------------------
Procedure: GetCount ID:1
Purpose: Returns the number of elements in the list
Input: The list
Output: The number of elements
Errors: None
------------------------------------------------------------------------*/
static int GetCount(List *l)
{
return l->count;
}
/*------------------------------------------------------------------------
Procedure: SetCompareFunction ID:1
Purpose: Defines the function to be used in comparison of
list elements
Input: The list and the new comparison function. If the new
comparison function is NULL no changes are done.
Output: Returns the old function
Errors: None
------------------------------------------------------------------------*/
static CompareFunction SetCompareFunction(List *l,CompareFunction fn)
{
CompareFunction oldfn = l->CompareFn;
if (fn != NULL) /* Treat NULL as an enquiry to get the compare function */
l->CompareFn = fn;
return oldfn;
}
/*------------------------------------------------------------------------
Procedure: Copy ID:1
Purpose: Copies a list. The result is fully allocated (list
elements and data).
Input: The list to be copied
Output: A pointer to the new list
Errors: None. Returns NULL if therfe is no memory left.
------------------------------------------------------------------------*/
static List *Copy(List *l)
{
List *result;
list_element *rvp,*newRvp,*last;
result = newList(l->ElementSize);
if (result == NULL)
return NULL;
rvp = l->First;
last = NULL;
while (rvp) {
newRvp = new_link(l,rvp->Data,"Copy");
if (result->First == NULL)
last = result->First = newRvp;
else {
last->Next = newRvp;
last = last->Next;
}
result->Last = newRvp;
result->count++;
rvp = rvp->Next;
}
return result;
}
/*------------------------------------------------------------------------
Procedure: Finalize ID:1
Purpose: Reclaims all memory for a list. The data, list
elements and the list header are reclaimed.
Input: The list to be destroyed. It should NOT be read-
only.
Output: Returns the old count or a negative value if an
error occurs (list not writable)
Errors: Needs a writable list
------------------------------------------------------------------------*/
static int Finalize(List *l)
{
int r,t;
r = l->count;
t = Clear(l);
if (t < 0)
return t;
FREE(l);
return r;
}
/*------------------------------------------------------------------------
Procedure: GetElement ID:1
Purpose: Returns the data associated with a given position
Input: The list and the position
Output: A pointer to the data
Errors: NULL if error in the positgion index
------------------------------------------------------------------------*/
static void * GetElement(List *l,int position)
{
list_element *rvp;
if (position >= (signed)l->count || position < 0) {
l->RaiseError("GetElement",CONTAINER_ERROR_INDEX);
return NULL;
}
rvp = l->First;
while (position) {
rvp = rvp->Next;
position--;
}
return rvp->Data;
}
static void * ReplaceAt(List *l,int position,void *data)
{
list_element *rvp;
/* Error checking */
if (position >= l->count || position < 0) {
l->RaiseError("ReplaceAt",CONTAINER_ERROR_INDEX);
return NULL;
}
if (l->Flags & LIST_READONLY)
return NULL;
/* Position at the right data item */
if (position == l->count-1)
rvp = l->Last;
else {
rvp = l->First;
while (position) {
rvp = rvp->Next;
position--;
}
}
/* Replace the data there */
if (l->ElementSize)
memcpy(rvp->Data , data,l->ElementSize);
else
memcpy(rvp->Data, &data,sizeof(void *));
return data;
}
/*------------------------------------------------------------------------
Procedure: GetRange ID:1
Purpose: Gets a consecutive sub sequence of the list within
two indexes.
Input: The list, the subsequence start and end
Output: A new freshly allocated list. If the source list is
empty or the range is empty, the result list is
empty too.
Errors: None
------------------------------------------------------------------------*/
static List *GetRange(List *l,int start,int end)
{
int counter;
List *result = newList(l->ElementSize);
list_element *newRvp,*rvp;;
if (l->count == 0)
return result;
if (end >= l->count)
end = l->count-1;
if (start > end)
return result;
if (start == l->count-1)
rvp = l->Last;
else {
rvp = l->First;
counter = 0;
while (counter < start) {
rvp = rvp->Next;
counter++;
}
}
while (start <= end) {
newRvp = new_link(l,rvp->Data,"GetRange");
if (result->Last == NULL) {
result->Last = result->First = newRvp;
}
else {
result->Last->Next = newRvp;
result->Last = newRvp;
}
result->count++;
rvp = rvp->Next;
start++;
}
return result;
}
/*------------------------------------------------------------------------
Procedure: Equal ID:1
Purpose: Compares the data of two lists. They must be of the
same length, the elements must have the same size
and the comparison functions must be the same. If
all this is true, the comparisons are done.
Input: The two lists to be compared
Output: Returns 1 if the two lists are equal, zero otherwise
Errors: None
------------------------------------------------------------------------*/
static bool Equal(List *l1,List *l2)
{
list_element *link1,*link2;
CompareFunction fn;
if (l1->count != l2->count)
return 0;
if (l1->ElementSize != l2->ElementSize)
return 0;
if (l1->count == 0)
return 1;
if (l1->CompareFn != l2->CompareFn)
return 1;
fn = l1->CompareFn;
link1 = l1->First;
link2 = l2->First;
while (link1 && link2) {
if (fn(link1->Data,link2->Data,l1))
return 0;
link1 = link1->Next;
link2 = link2->Next;
}
if (link1 || link2)
return 0;
return 1;
}
/*------------------------------------------------------------------------
Procedure: Insert ID:1
Purpose: Inserts an element at the start of the list
Input: The list and the data to insert
Output: The count of the list after insertion, or CONTAINER_ERROR_READONLY
if the list is not writable or CONTAINER_ERROR_NOMEMORY if there is
no more memory left.
Errors: None
------------------------------------------------------------------------*/
static int Insert(List *l,void *pdata)
{
list_element *rvp;
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
rvp = new_link(l,pdata,"Insert");
if (rvp == NULL)
return CONTAINER_ERROR_NOMEMORY;
rvp->Next = l->First;
l->First = rvp;
if (l->Last == NULL)
l->Last = rvp;
l->count++;
return l->count;
}
/*------------------------------------------------------------------------
Procedure: Pop ID:1
Purpose: Takes out the first element of a list.
Input: The list
Output: The first element or NULL if there is none or the
list is read only
Errors: None
------------------------------------------------------------------------*/
static list_element *Pop(List *l)
{
list_element *le;
if (l->count == 0 || (l->Flags & LIST_READONLY))
return NULL;
le = l->First;
if (l->count == 1) {
l->First = l->Last = NULL;
}
else l->First = l->First->Next;
l->count--;
return le;
}
static int InsertAt(List *l,int pos,void *pdata)
{
list_element *rvp,*elem;
if (pos < 0 || pos > l->count) {
l->RaiseError("InsertAt",CONTAINER_ERROR_BADARG);
return 0;
}
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
elem = new_link(l,pdata,"InsertAt");
if (elem == NULL)
return 0;
if (pos == l->count) {
if (pos == 0 && l->count == 0) {
l->First = elem;
l->Last = elem;
}
else {
l->Last->Next = elem;
l->Last = elem;
}
return ++l->count;
}
else if (pos == 0) {
elem->Next = l->First;
l->First = elem;
return ++l->count;
}
rvp = l->First;
while (pos > 0) {
rvp = rvp->Next;
pos--;
}
elem->Next = rvp->Next;
rvp->Next = elem;
return ++l->count;
}
static int Remove(List *l,void *elem)
{
int idx;
idx = IndexOf(l,elem);
if (idx <= 0)
return idx;
return RemoveAt(l,idx);
}
static int RemoveAt(List *l,int position)
{
list_element *rvp,*last;
if (position >= l->count || position < 0)
l->RaiseError("RemoveAt",CONTAINER_ERROR_BADARG);
if (l->Flags & LIST_READONLY)
return CONTAINER_ERROR_READONLY;
rvp = l->First;
if (position == 0) {
if (l->First == l->Last) {
l->First = l->Last = NULL;
}
else {
l->First = l->First->Next;
}
}
else if (position == l->count - 1) {
while (rvp->Next != l->Last)
rvp = rvp->Next;
rvp->Next = NULL;
l->Last = rvp;
}
else {
position--;
last = rvp;
rvp = rvp->Next;
while (position > 0) {
rvp = rvp->Next;
position --;
}
last->Next = rvp->Next;
}
return --l->count;
}
static List *Append(List *l1,List *l2)
{
if (l1->count == 0)
return l2;
if (l2->count == 0)
return l1;
l1->Last->Next = l2->First;
l1->Last = l2->Last;
l1->count += l2->count;
return l1;
}
static List *Reverse(List *l)
{
list_element *tmp,*prev,*last,*rvp;
if (l->count < 2)
return l;
rvp = l->First;
l->First = l->Last;
last = prev = NULL;
while (rvp) {
last = rvp;
tmp = rvp->Next;
rvp->Next = prev;
prev = rvp;
rvp = tmp;
}
l->Last = prev;
return l;
}
/* Searches a List for a given data item
Returns a positive integer if found, negative if the end is reached
*/
static int IndexOf(List *l,void *ElementToFind)
{
list_element *rvp;
int r,i=0,es;
CompareFunction fn;
rvp = l->First;
fn = l->CompareFn;
es =l->ElementSize;
if (es == 0)
es = sizeof(void *);
while (rvp) {
r = fn(*(char **)rvp->Data,ElementToFind,l);
if (r == 0)
return i;
rvp = rvp->Next;
i++;
}
return -1;
}
static List *Sort(List *l,int (*compar)(const void *,const void *))
{
char **tab;
int i;
list_element *rvp,*newlink;
List *result;
if (l->count < 2)
return Copy(l);
tab = MALLOC(l->count * sizeof(void *));
if (tab == NULL)
l->RaiseError("Sort",CONTAINER_ERROR_NOMEMORY);
rvp = l->First;
for (i=0; i<l->count;i++) {
tab = rvp->Data;
rvp = rvp->Next;
}
qsort(tab,l->count,sizeof(void *),compar);
result = newList(l->ElementSize);
rvp = new_link(result,tab[0],"Sort");
result->First = rvp;
rvp->Next = NULL;
result->First = rvp;
i = 1;
while (i < l->count) {
newlink = new_link(result,tab,"Sort");
rvp->Next = newlink;
rvp = newlink;
rvp->Next = NULL;
}
result->Last = rvp;
return result;
}
static void Apply(List *L,int (Applyfn)(void *,void *),void *arg)
{
list_element *le;
le = L->First;
while (le) {
Applyfn(le->Data,arg);
le = le->Next;
}
}
static ErrorFunction SetErrorFunction(List *l,ErrorFunction fn)
{
ErrorFunction old;
old = l->RaiseError;
l->RaiseError = (fn) ? fn : EmptyErrorFunction;
return old;
}