A container library in C: Part 3. List container implementation

Discussion in 'C Programming' started by jacob navia, Sep 28, 2009.

  1. jacob navia

    jacob navia Guest

    This implements the list routines
    -----------------------------list.c cut here-------------------------

    /* -------------------------------------------------------------------
    List routines
    ---------------
    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
    This is still experimental.
    ----------------------------------------------------------------------
    */

    #ifndef DEFAULT_START_SIZE
    #define DEFAULT_START_SIZE 20
    #endif
    #include "containers.h"

    #ifndef NO_GC
    #include <gc.h>
    #define MALLOC GC_malloc
    #define FREE(a)
    #else
    #include <stdlib.h>
    #define MALLOC malloc
    #define FREE free
    #endif

    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);
    static int GetCapacity(List AL);
    static int Push(List AL,void *str);
    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 CompareFunction SetCompareFunction(List l,CompareFunction 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,
    NULL, // Comparison function initially empty
    SetCompareFunction,
    };
    #define LIST_READONLY 1
    #define LIST_HASPOINTER 2

    /* local routines to this module */
    static list_element *new_link(List l,void *data)
    {
    int es = l.ElementSize;
    list_element *result;

    if (es == 0) {
    result = MALLOC(sizeof(list_element)+sizeof(void *));
    }
    else
    result = MALLOC(sizeof(list_element)+l.ElementSize);
    if (result != NULL) {
    result->Next = NULL;
    if (data != NULL) {
    if (es)
    memcpy(result->Data,data,es);
    else
    memcpy(result->Data,&data,sizeof(void *));
    }
    }
    else ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    return result;
    }

    /* ------------------------------------------------------------------
    Allocation of a new List header
    ---------------------------------------------------------------------
    */
    List newList(int elementsize)
    {
    List result;

    if (elementsize < 0)
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    memset(&result,0,sizeof(List));
    result.ElementSize = elementsize;
    result.lpVtbl = &listlpVtbl;
    if (elementsize == 0)
    result.Flags = LIST_HASPOINTER;
    return result;
    }

    static bool Contains(List l,void *data)
    {
    return (IndexOf(l,data) < 0) ? false : true;
    }

    static int Clear(List l)
    {
    int r,f;

    if (l.Flags & LIST_READONLY)
    return CONTAINER_ERROR_READONLY;
    r = l.count;
    f = l.Flags;
    memset(&l,0,sizeof(List));
    l.Flags = f;
    return r;
    }

    static int Add(List l,void *elem)
    {
    if (elem == NULL)
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    if (l.Flags &LIST_READONLY)
    return CONTAINER_ERROR_READONLY;
    list_element *newl = new_link(l,elem);
    if (l.count == 0) {
    l.First = newl;
    }
    else {
    l.Last->Next = newl;
    }
    l.Last = newl;
    return ++l.count;

    }

    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;
    }

    static int IsReadOnly(List l)
    {
    return (l.Flags&LIST_READONLY) ? 1 : 0;
    }

    static int GetCount(List l)
    {
    return l.count;
    }

    static CompareFunction SetCompareFunction(List l,CompareFunction fn)
    {
    CompareFunction oldfn = l.CompareFn;
    l.CompareFn = fn;
    return oldfn;
    }

    static List Copy(List l)
    {
    List result;
    list_element *rvp,*newRvp,*last;

    result = newList(l.ElementSize);
    rvp = l.First;
    last = NULL;
    while (rvp) {
    newRvp = new_link(l,rvp->Data);
    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;
    }

    static int Finalize(List l)
    {
    int r;

    r = l.count;
    memset(&l,0,sizeof(List));
    return r;
    }

    static void * GetElement(List l,int position)
    {
    list_element *rvp;

    if (position >= (signed)l.count || position < 0) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_INDEX);
    return NULL;
    }
    rvp = l.First;
    while (position) {
    rvp = rvp->Next;
    position--;
    }
    return rvp;
    }

    static void * ReplaceAt(List l,int position,void *data)
    {
    list_element *rvp;

    if (position >= l.count) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_INDEX);
    return NULL;
    }
    if (l.Flags & LIST_READONLY)
    return NULL;
    if (position == l.count-1)
    rvp = l.Last;
    else {
    rvp = l.First;
    while (position) {
    rvp = rvp->Next;
    position--;
    }
    }
    memcpy(rvp->Data , data,l.ElementSize);
    return data;
    }

    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);
    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;
    }

    static bool Equal(List l1,List l2)
    {
    list_element *link1,*link2;
    CompareFunction fn;

    if (l1.count != l2.count)
    return false;
    if (l1.ElementSize != l2.ElementSize)
    return false;
    if (l1.count == 0)
    return true;
    if (l1.CompareFn != l2.CompareFn)
    return false;
    fn = l1.CompareFn;
    link1 = l1.First;
    link2 = l2.First;
    while (link1 && link2) {
    if (fn) {
    if (fn(link1->Data,link2->Data))
    return false;
    }
    else {
    if (memcmp(link1->Data,link2->Data,l1.ElementSize))
    return false;
    }
    link1 = link1->Next;
    link2 = link2->Next;
    }
    if (link1 || link2)
    return false;
    return true;
    }

    static int __declspec(naked) Push(List l,void *pdata)
    {
    }

    static int Insert(List l,void *pdata)
    {
    list_element *rvp;

    if (l.Flags & LIST_READONLY)
    return -1;
    rvp = new_link(l,pdata);
    rvp->Next = l.First;
    l.First = rvp;
    if (l.Last == NULL)
    l.Last = rvp;
    l.count++;
    return l.count;
    }


    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;
    if (pos < 0 || pos > l.count) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return 0;
    }
    if (l.Flags & LIST_READONLY)
    return CONTAINER_ERROR_READONLY;;
    list_element *elem = new_link(l,pdata);
    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)
    ContainerRaiseError(__func__,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;
    }

    #if 0
    static List Concat(List l1,List l2)
    {
    list_element *copy;
    List newList;
    if (l1.count == 0)
    return Copy(l2);
    if (l2.count == 0)
    return Copy(l1);

    copy = new_link(l1,l1.Last);
    newList = newList(l1->ElementSize);
    memcpy(newList,l1,sizeof(List));
    newList.Last = copy;
    newList.Last->Next = l2.First;
    newList.Last = l2.Last;
    newList.count += l2.count;
    return newList;
    }
    #endif

    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 pointer to the last element analyzed or NULL 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) {
    if (fn)
    r = fn(*(char **)rvp->Data,ElementToFind);
    else
    r = memcmp(&rvp->Data,ElementToFind,es);
    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)
    ContainerRaiseError(__func__,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]);
    result.First = rvp;
    rvp->Next = NULL;
    result.First = rvp;
    i = 1;
    while (i < l.count) {
    newlink = new_link(result,tab);
    rvp->Next = newlink;
    rvp = newlink;
    rvp->Next = NULL;
    }
    result.Last = rvp;
    return result;
    }
     
    jacob navia, Sep 28, 2009
    #1
    1. Advertising

  2. jacob navia <> writes:

    > This implements the list routines


    Is this supposed to standard C or something specific to lcc-win32? I
    can't get it to compile and I can't see how it is supposed to work
    even if I could.

    I suspect it is an edited version of something else because I can't
    believe lcc-win32 can compile it either (for example List has no
    member named CompareFn).

    <snip code>
    --
    Ben.
     
    Ben Bacarisse, Sep 28, 2009
    #2
    1. Advertising

  3. jacob navia

    jacob navia Guest

    Version that can be compiled with gcc

    This is very bad. I have completely messed up the files I transferred

    Here is the version that was the portable one
    compile with

    gcc -std=c99 -c list.c

    ----------------------------------------------------------

    /* -------------------------------------------------------------------
    List routines
    ---------------
    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
    This is still experimental.
    ----------------------------------------------------------------------
    */

    #ifndef DEFAULT_START_SIZE
    #define DEFAULT_START_SIZE 20
    #endif
    #include "containers.h"
    #ifndef NO_GC
    #include <gc.h>
    #define MALLOC GC_malloc
    #define FREE(a)
    #else
    #include <stdlib.h>
    #define MALLOC malloc
    #define FREE free
    #endif

    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);
    static int GetCapacity(List AL);
    static int Push(List AL,void *str);
    // 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 CompareFunction SetCompareFunction(List l,CompareFunction 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,
    NULL, // Comparison function initially empty
    SetCompareFunction,
    };
    #define LIST_READONLY 1
    #define LIST_HASPOINTER 2

    /* local routines to this module */
    static list_element *new_link(List l,void *data)
    {
    int es = l.ElementSize;
    list_element *result;

    if (es == 0) {
    result = MALLOC(sizeof(list_element)+sizeof(void *));
    }
    else
    result = MALLOC(sizeof(list_element)+l.ElementSize);
    if (result != NULL) {
    result->Next = NULL;
    if (data != NULL) {
    if (es)
    memcpy(result->Data,data,es);
    else
    memcpy(result->Data,&data,sizeof(void *));
    }
    }
    else ContainerRaiseError(__func__,CONTAINER_ERROR_NOMEMORY);
    return result;
    }

    /* ------------------------------------------------------------------
    Allocation of a new List header
    ---------------------------------------------------------------------
    */
    List newList(int elementsize)
    {
    List result;

    if (elementsize < 0)
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    memset(&result,0,sizeof(List));
    result.ElementSize = elementsize;
    result.lpVtbl = &listlpVtbl;
    if (elementsize == 0)
    result.Flags = LIST_HASPOINTER;
    return result;
    }

    static bool Contains(List l,void *data)
    {
    return (IndexOf(l,data) < 0) ? false : true;
    }

    static int Clear(List l)
    {
    int r,f;

    if (l.Flags & LIST_READONLY)
    return CONTAINER_ERROR_READONLY;
    r = l.count;
    f = l.Flags;
    memset(&l,0,sizeof(List));
    l.Flags = f;
    return r;
    }

    static int Add(List l,void *elem)
    {
    if (elem == NULL)
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    if (l.Flags &LIST_READONLY)
    return CONTAINER_ERROR_READONLY;
    list_element *newl = new_link(l,elem);
    if (l.count == 0) {
    l.First = newl;
    }
    else {
    l.Last->Next = newl;
    }
    l.Last = newl;
    return ++l.count;

    }

    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;
    }

    static int IsReadOnly(List l)
    {
    return (l.Flags&LIST_READONLY) ? 1 : 0;
    }

    static int GetCount(List l)
    {
    return l.count;
    }

    static CompareFunction SetCompareFunction(List l,CompareFunction fn)
    {
    CompareFunction oldfn = l.lpVtbl->CompareFn;

    l.lpVtbl->CompareFn = fn;
    return oldfn;
    }

    static List Copy(List l)
    {
    List result;
    list_element *rvp,*newRvp,*last;

    result = newList(l.ElementSize);
    rvp = l.First;
    last = NULL;
    while (rvp) {
    newRvp = new_link(l,rvp->Data);
    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;
    }

    static int Finalize(List l)
    {
    int r;

    r = l.count;
    memset(&l,0,sizeof(List));
    return r;
    }

    static void * GetElement(List l,int position)
    {
    list_element *rvp;

    if (position >= (signed)l.count || position < 0) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_INDEX);
    return NULL;
    }
    rvp = l.First;
    while (position) {
    rvp = rvp->Next;
    position--;
    }
    return rvp;
    }

    static void * ReplaceAt(List l,int position,void *data)
    {
    list_element *rvp;

    if (position >= l.count) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_INDEX);
    return NULL;
    }
    if (l.Flags & LIST_READONLY)
    return NULL;
    if (position == l.count-1)
    rvp = l.Last;
    else {
    rvp = l.First;
    while (position) {
    rvp = rvp->Next;
    position--;
    }
    }
    memcpy(rvp->Data , data,l.ElementSize);
    return data;
    }

    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);
    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;
    }

    static bool Equal(List l1,List l2)
    {
    list_element *link1,*link2;
    CompareFunction fn;

    if (l1.count != l2.count)
    return false;
    if (l1.ElementSize != l2.ElementSize)
    return false;
    if (l1.count == 0)
    return true;
    if (l1.lpVtbl->CompareFn != l2.lpVtbl->CompareFn)
    return false;
    fn = l1.lpVtbl->CompareFn;
    link1 = l1.First;
    link2 = l2.First;
    while (link1 && link2) {
    if (fn) {
    if (fn(link1->Data,link2->Data))
    return false;
    }
    else {
    if (memcmp(link1->Data,link2->Data,l1.ElementSize))
    return false;
    }
    link1 = link1->Next;
    link2 = link2->Next;
    }
    if (link1 || link2)
    return false;
    return true;
    }


    static int Insert(List l,void *pdata)
    {
    list_element *rvp;

    if (l.Flags & LIST_READONLY)
    return -1;
    rvp = new_link(l,pdata);
    rvp->Next = l.First;
    l.First = rvp;
    if (l.Last == NULL)
    l.Last = rvp;
    l.count++;
    return l.count;
    }


    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;
    if (pos < 0 || pos > l.count) {
    ContainerRaiseError(__func__,CONTAINER_ERROR_BADARG);
    return 0;
    }
    if (l.Flags & LIST_READONLY)
    return CONTAINER_ERROR_READONLY;;
    list_element *elem = new_link(l,pdata);
    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)
    ContainerRaiseError(__func__,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;
    }

    #if 0
    static List Concat(List l1,List l2)
    {
    list_element *copy;
    List newList;
    if (l1.count == 0)
    return Copy(l2);
    if (l2.count == 0)
    return Copy(l1);

    copy = new_link(l1,l1.Last);
    newList = newList(l1->ElementSize);
    memcpy(newList,l1,sizeof(List));
    newList.Last = copy;
    newList.Last->Next = l2.First;
    newList.Last = l2.Last;
    newList.count += l2.count;
    return newList;
    }
    #endif

    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 pointer to the last element analyzed or NULL 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.lpVtbl->CompareFn;
    es =l.ElementSize;
    if (es == 0)
    es = sizeof(void *);
    while (rvp) {
    if (fn)
    r = fn(*(char **)rvp->Data,ElementToFind);
    else
    r = memcmp(&rvp->Data,ElementToFind,es);
    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)
    ContainerRaiseError(__func__,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]);
    result.First = rvp;
    rvp->Next = NULL;
    result.First = rvp;
    i = 1;
    while (i < l.count) {
    newlink = new_link(result,tab);
    rvp->Next = newlink;
    rvp = newlink;
    rvp->Next = NULL;
    }
    result.Last = rvp;
    return result;
    }
     
    jacob navia, Sep 28, 2009
    #3
  4. jacob navia

    jacob navia Guest

    Ben Bacarisse a écrit :
    > jacob navia <> writes:
    >
    >> This implements the list routines

    >
    > Is this supposed to standard C or something specific to lcc-win32? I
    > can't get it to compile and I can't see how it is supposed to work
    > even if I could.
    >
    > I suspect it is an edited version of something else because I can't
    > believe lcc-win32 can compile it either (for example List has no
    > member named CompareFn).
    >
    > <snip code>


    Sorry but I miexed up the files when transferring to the
    email.

    Please see my other message in this thread.
     
    jacob navia, Sep 28, 2009
    #4
  5. jacob navia

    Flash Gordon Guest

    Re: Version that can be compiled with gcc

    jacob navia wrote:
    > This is very bad. I have completely messed up the files I transferred


    It happens.

    > Here is the version that was the portable one
    > compile with
    >
    > gcc -std=c99 -c list.c


    Mark-Gordons-MacBook-Air:~ markg$ gcc -c -std=c99 jn.c
    jn.c: In function ‘new_link’:
    jn.c:86: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘newList’:
    jn.c:99: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘Add’:
    jn.c:129: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘GetElement’:
    jn.c:212: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘ReplaceAt’:
    jn.c:228: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘InsertAt’:
    jn.c:352: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘RemoveAt’:
    jn.c:399: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    jn.c: In function ‘Sort’:
    jn.c:525: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    qualifiers from pointer target type
    Mark-Gordons-MacBook-Air:~ markg$

    I suggest that the first parameter of ContainerRaiseError should be
    const char *. I used the most recent version of containers.h that I've
    seen so far, and C99 specifies that __func__ is const.
    --
    Flash Gordon
     
    Flash Gordon, Sep 28, 2009
    #5
  6. jacob navia

    jacob navia Guest

    Re: Version that can be compiled with gcc

    Flash Gordon a écrit :
    > jacob navia wrote:
    >> This is very bad. I have completely messed up the files I transferred

    >
    > It happens.
    >
    >> Here is the version that was the portable one
    >> compile with
    >>
    >> gcc -std=c99 -c list.c

    >
    > Mark-Gordons-MacBook-Air:~ markg$ gcc -c -std=c99 jn.c
    > jn.c: In function ‘new_link’:
    > jn.c:86: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘newList’:
    > jn.c:99: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘Add’:
    > jn.c:129: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘GetElement’:
    > jn.c:212: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘ReplaceAt’:
    > jn.c:228: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘InsertAt’:
    > jn.c:352: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘RemoveAt’:
    > jn.c:399: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > jn.c: In function ‘Sort’:
    > jn.c:525: warning: passing argument 1 of ‘ContainerRaiseError’ discards
    > qualifiers from pointer target type
    > Mark-Gordons-MacBook-Air:~ markg$
    >
    > I suggest that the first parameter of ContainerRaiseError should be
    > const char *. I used the most recent version of containers.h that I've
    > seen so far, and C99 specifies that __func__ is const.


    Right.

    Thanks
     
    jacob navia, Sep 28, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jacob navia

    A container library in C. Part 1: Header file

    jacob navia, Sep 28, 2009, in forum: C Programming
    Replies:
    14
    Views:
    679
    Tech07
    Oct 3, 2009
  2. jacob navia
    Replies:
    3
    Views:
    330
    jacob navia
    Sep 29, 2009
  3. jacob navia
    Replies:
    10
    Views:
    646
    jacob navia
    Oct 1, 2009
  4. Alan Curry

    review of the "container library", part 1/?

    Alan Curry, Mar 1, 2011, in forum: C Programming
    Replies:
    18
    Views:
    660
    jacob navia
    Mar 11, 2011
  5. jacob navia

    Engineering a list container. Part 1.

    jacob navia, Dec 7, 2013, in forum: C Programming
    Replies:
    71
    Views:
    553
    Eric Sosman
    Dec 26, 2013
Loading...

Share This Page