src/list/list.c File Reference

#include "util.h"
#include "list.h"
#include "lsort.h"

Include dependency graph for list.c:

Go to the source code of this file.

Data Structures
struct	list_elem
struct	list_desc
struct	gen_desc
Defines
#define	TYPE   lsElem
#define	SORT   lsSortItems
#define	NEXT   nextPtr
#define	FIELD   userData
Typedefs
typedef struct list_elem	lsElem
typedef struct list_desc	lsDesc
typedef struct gen_desc	lsGenInternal
Functions
lsList	lsCreate (void)
lsStatus	lsDestroy (lsList list, void(*delFunc)(lsGeneric))
static lsGeneric	lsIdentity (lsGeneric data)
lsList	lsCopy (lsList list, lsGeneric(*copyFunc)(lsGeneric))
lsStatus	lsNewBegin (lsList list, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsNewEnd (lsList list, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsFirstItem (lsList list, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsLastItem (lsList list, lsGeneric data, lsHandle *itemHandle)
int	lsLength (lsList list)
lsStatus	lsDelBegin (lsList list, lsGeneric data)
lsStatus	lsDelEnd (lsList list, lsGeneric data)
lsGen	lsStart (lsList list)
lsGen	lsEnd (lsList list)
lsGen	lsGenHandle (lsHandle itemHandle, lsGeneric data, int option)
lsStatus	lsNext (lsGen generator, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsPrev (lsGen generator, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsInBefore (lsGen generator, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsInAfter (lsGen generator, lsGeneric data, lsHandle *itemHandle)
lsStatus	lsDelBefore (lsGen generator, lsGeneric data)
lsStatus	lsDelAfter (lsGen generator, lsGeneric data)
lsStatus	lsFinish (lsGen generator)
static lsStatus	lsGenForm (lsStatus(*userFunc)(lsGeneric, lsGeneric), lsGeneric arg, lsGen gen, lsStatus(*gen_func)(lsGen, lsGeneric, lsHandle *), lsStatus(*del_func)(lsGen, lsGeneric))
lsStatus	lsForeach (lsList list, lsStatus(*userFunc)(lsGeneric, lsGeneric), lsGeneric arg)
lsStatus	lsBackeach (lsList list, lsStatus(*userFunc)(lsGeneric, lsGeneric), lsGeneric arg)
lsList	lsQueryHandle (lsHandle itemHandle)
lsGeneric	lsFetchHandle (lsHandle itemHandle)
lsStatus	lsRemoveItem (lsHandle itemHandle, lsGeneric userData)
lsStatus	lsSort (lsList list, int(*compare)(lsGeneric, lsGeneric))
lsStatus	lsUniq (lsList list, int(*compare)(lsGeneric, lsGeneric), void(*delFunc)(lsGeneric))

---

Define Documentation

#define FIELD   userData

Definition at line 812 of file list.c.

#define NEXT   nextPtr

Definition at line 811 of file list.c.

#define SORT   lsSortItems

Definition at line 810 of file list.c.

#define TYPE   lsElem

Definition at line 809 of file list.c.

---

Typedef Documentation

typedef struct list_desc lsDesc

typedef struct list_elem lsElem

typedef struct gen_desc lsGenInternal

---

Function Documentation

lsStatus lsBackeach	(	lsList	list,
		lsStatus(*)(lsGeneric, lsGeneric)	userFunc,
		lsGeneric	arg
	)

Definition at line 716 of file list.c.

{
    return lsGenForm(userFunc, arg, lsEnd(list), lsPrev, lsDelAfter);
}

lsList lsCopy	(	lsList	list,
		lsGeneric(*)(lsGeneric)	copyFunc
	)

Definition at line 118 of file list.c.

                                                                    :
 *   lsGeneric copyFunc(data)
 *   lsGeneric data;
 * This is normally used to make copies of the user data in the new list.
 * If no `copyFunc' is provided,  an identity function is used.
 */
{
    lsList newList;
    lsGen gen;
    lsGeneric data;

    if (!copyFunc) copyFunc = lsIdentity;
    newList = lsCreate();
    gen = lsStart(list);
    while (lsNext(gen, &data, LS_NH) == LS_OK) {
        (void) lsNewEnd(newList, (*copyFunc)(data), LS_NH);
    }
    lsFinish(gen);
    return newList;
}

lsList lsCreate

(

void

)

Definition at line 66 of file list.c.

{
    lsDesc *newList;

    newList = ALLOC(lsDesc, 1);
    newList->topPtr = newList->botPtr = NIL(lsElem);
    newList->length = 0;
    return( (lsList) newList );
}

lsStatus lsDelAfter	(	lsGen	generator,
		lsGeneric	data
	)

Definition at line 620 of file list.c.

{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *doomedItem;

    if (realGen->afterSpot == NIL(lsElem)) {
        /* No item to delete */
        *(void **)data = (lsGeneric) 0;
        return LS_BADSTATE;
    } else if (realGen->afterSpot == realGen->mainList->topPtr) {
        /* Delete the first item of the list */
        realGen->afterSpot = realGen->afterSpot->nextPtr;
        return lsDelBegin((lsList) realGen->mainList, data);
    } else if (realGen->afterSpot == realGen->mainList->botPtr) {
        /* Delete the last item of the list */
        realGen->afterSpot = realGen->afterSpot->nextPtr;
        return lsDelEnd((lsList) realGen->mainList, data);
    } else {
        /* Normal mid list deletion */
        doomedItem = realGen->afterSpot;
        doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
        doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
        realGen->afterSpot = doomedItem->nextPtr;
        realGen->mainList->length -= 1;
        *(void **)data = doomedItem->userData;
        FREE(doomedItem);
        return LS_OK;
    }
}

lsStatus lsDelBefore	(	lsGen	generator,
		lsGeneric	data
	)

Definition at line 579 of file list.c.

{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *doomedItem;

    if (realGen->beforeSpot == NIL(lsElem)) {
        /* No item to delete */
        *(void **)data = (lsGeneric) 0;
        return LS_BADSTATE;
    } else if (realGen->beforeSpot == realGen->mainList->topPtr) {
        /* Delete the first item of the list */
        realGen->beforeSpot = realGen->beforeSpot->prevPtr;
        return lsDelBegin((lsList) realGen->mainList, data);
    } else if (realGen->beforeSpot == realGen->mainList->botPtr) {
        /* Delete the last item of the list */
        realGen->beforeSpot = realGen->beforeSpot->prevPtr;
        return lsDelEnd((lsList) realGen->mainList, data);
    } else {
        /* Normal mid list deletion */
        doomedItem = realGen->beforeSpot;
        doomedItem->prevPtr->nextPtr = doomedItem->nextPtr;
        doomedItem->nextPtr->prevPtr = doomedItem->prevPtr;
        realGen->beforeSpot = doomedItem->prevPtr;
        realGen->mainList->length -= 1;
        *(void **)data = doomedItem->userData;
        FREE(doomedItem);
        return LS_OK;
    }
}

lsStatus lsDelBegin	(	lsList	list,
		lsGeneric	data
	)

Definition at line 285 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsElem *temp;

    if (realList->topPtr == NIL(lsElem)) {
        /* Nothing to delete */
        *(void **)data = (lsGeneric) 0;
        return LS_NOMORE;
    } else {
        *(void **)data = realList->topPtr->userData;
        temp = realList->topPtr;
        realList->topPtr = realList->topPtr->nextPtr;
        if (temp->nextPtr != NIL(lsElem)) {
            /* There is something after the first item */
            temp->nextPtr->prevPtr = NIL(lsElem);
        } else {
            /* Nothing after it - bottom becomes null as well */
            realList->botPtr = NIL(lsElem);
        }
        FREE(temp);
        realList->length -= 1;
    }
    return LS_OK;
}

lsStatus lsDelEnd	(	lsList	list,
		lsGeneric	data
	)

Definition at line 320 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsElem *temp;

    if (realList->botPtr == NIL(lsElem)) {
        /* Nothing to delete */
        *(void **)data = (lsGeneric) 0;
        return LS_NOMORE;
    } else {
        *(void **)data = realList->botPtr->userData;
        temp = realList->botPtr;
        realList->botPtr = realList->botPtr->prevPtr;
        if (temp->prevPtr != NIL(lsElem)) {
            /* There is something before the last item */
            temp->prevPtr->nextPtr = NIL(lsElem);
        } else {
            /* Nothing before it - top becomes null as well */
            realList->topPtr = NIL(lsElem);
        }
        FREE(temp);
        realList->length -= 1;
    }
    return LS_OK;
}

lsStatus lsDestroy	(	lsList	list,
		void(*)(lsGeneric)	delFunc
	)

Definition at line 80 of file list.c.

{
    lsDesc *realList;
    lsElem *index, *temp;

    realList = (lsDesc *) list;
    /* Get rid of elements */
    index = realList->topPtr;
    while (index != NIL(lsElem)) {
        temp = index;  index = index->nextPtr;
        if (delFunc)
          (*delFunc)(temp->userData);
        FREE(temp);
    }
    /* Get rid of descriptor */
    FREE(realList);
    return(LS_OK);
}

lsGen lsEnd

(

lsList

list

)

Definition at line 380 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realList;
    newGen->beforeSpot = realList->botPtr;
    newGen->afterSpot = NIL(lsElem);
    return (lsGen) newGen;
}

lsGeneric lsFetchHandle

(

lsHandle

itemHandle

)

Definition at line 779 of file list.c.

{
    return ((lsElem *) itemHandle)->userData;
}

lsStatus lsFinish

(

lsGen

generator

)

Definition at line 661 of file list.c.

{
    lsGenInternal *realGen = (lsGenInternal *) generator;

    FREE(realGen);
    return(LS_OK);
}

lsStatus lsFirstItem	(	lsList	list,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 215 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;

    if (realList->topPtr != NIL(lsElem)) {
        *(void **)data = realList->topPtr->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realList->topPtr);
        return(LS_OK);
    } else {
        *(void **)data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return(LS_NOMORE);
    }
}

lsStatus lsForeach	(	lsList	list,
		lsStatus(*)(lsGeneric, lsGeneric)	userFunc,
		lsGeneric	arg
	)

Definition at line 691 of file list.c.

                                 :
 *   lsStatus userFunc(data, arg)
 *   lsGeneric data;
 *   lsGeneric arg;
 * `data' will be the user data associated with the item generated.
 * `arg' will be the same pointer provided to lsForeach.  The
 * routine should return LS_OK to continue the generation,  LS_STOP
 * to stop generating items,  and LS_DELETE to delete the item
 * from the list.  If the generation was stopped prematurely,
 * the routine will return LS_STOP.  If the user provided function
 * does not return an appropriate value,  the routine will return
 * LS_BADPARAM.
 */
{
    return lsGenForm(userFunc, arg, lsStart(list), lsNext, lsDelBefore);
}

static lsStatus lsGenForm	(	lsStatus(*)(lsGeneric, lsGeneric)	userFunc,
		lsGeneric	arg,
		lsGen	gen,
		lsStatus(*)(lsGen, lsGeneric, lsHandle *)	gen_func,
		lsStatus(*)(lsGen, lsGeneric)	del_func
	)			[static]

Definition at line 729 of file list.c.

{
    lsGeneric data;

    while ((*gen_func)(gen, &data, LS_NH) == LS_OK) {
        switch ((*userFunc)(data, arg)) {
        case LS_OK:
            /* Nothing */
            break;
        case LS_STOP:
            (void) lsFinish(gen);
            return LS_STOP;
        case LS_DELETE:
            (*del_func)(gen, &data);
            break;
        default:
            return LS_BADPARAM;
        }
    }
    (void) lsFinish(gen);
    return LS_OK;
}

lsGen lsGenHandle	(	lsHandle	itemHandle,
		lsGeneric	data,
		int	option
	)

Definition at line 398 of file list.c.

                                          :  the generator
 * should be freed using lsFinish.  The 'option' parameter
 * determines whether the generator spot is before or after
 * the handle item.
 */
{
    lsElem *realItem = (lsElem *) itemHandle;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realItem->mainList;
    *(void **)data = realItem->userData;
    if (option & LS_BEFORE) {
        newGen->beforeSpot = realItem->prevPtr;
        newGen->afterSpot = realItem;
    } else if (option & LS_AFTER) {
        newGen->beforeSpot = realItem;
        newGen->afterSpot = realItem->nextPtr;
    } else {
        FREE(newGen);
        newGen = (lsGenInternal *) 0;
    }
    return ( (lsGen) newGen );
}

static lsGeneric lsIdentity

(

lsGeneric

data

)

[static]

Definition at line 112 of file list.c.

{
    return data;
}

lsStatus lsInAfter	(	lsGen	generator,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 537 of file list.c.

{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *newElem;

    if (realGen->beforeSpot == NIL(lsElem)) {
        /* Item added to the beginning of the list */
        (void) lsNewBegin((lsList) realGen->mainList, data, itemHandle);
        realGen->beforeSpot = realGen->mainList->topPtr;
        return LS_OK;
    } else if (realGen->afterSpot == NIL(lsElem)) {
        /* Item added to the end of the list */
        (void) lsNewEnd((lsList) realGen->mainList, data, itemHandle);
        realGen->afterSpot = realGen->mainList->botPtr;
        return LS_OK;
    } else {
        /* Item added in the middle of the list */
        newElem = ALLOC(lsElem, 1);
        newElem->mainList = realGen->mainList;
        newElem->prevPtr = realGen->beforeSpot;
        newElem->nextPtr = realGen->afterSpot;
        newElem->userData = data;
        realGen->beforeSpot->nextPtr = newElem;
        realGen->afterSpot->prevPtr = newElem;
        realGen->afterSpot = newElem;
        realGen->mainList->length += 1;
        if (itemHandle) *itemHandle = (lsHandle) newElem;
        return LS_OK;
    }
}

lsStatus lsInBefore	(	lsGen	generator,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 496 of file list.c.

{
    lsGenInternal *realGen = (lsGenInternal *) generator;
    lsElem *newElem;

    if (realGen->beforeSpot == NIL(lsElem)) {
        /* Item added to the beginning of the list */
        (void) lsNewBegin((lsList) realGen->mainList, data, itemHandle);
        realGen->beforeSpot = realGen->mainList->topPtr;
        return LS_OK;
    } else if (realGen->afterSpot == NIL(lsElem)) {
        /* Item added to the end of the list */
        (void) lsNewEnd((lsList) realGen->mainList, data, itemHandle);
        realGen->afterSpot = realGen->mainList->botPtr;
        return LS_OK;
    } else {
        /* Item added in the middle of the list */
        newElem = ALLOC(lsElem, 1);
        newElem->mainList = realGen->mainList;
        newElem->prevPtr = realGen->beforeSpot;
        newElem->nextPtr = realGen->afterSpot;
        newElem->userData = data;
        realGen->beforeSpot->nextPtr = newElem;
        realGen->afterSpot->prevPtr = newElem;
        realGen->beforeSpot = newElem;
        realGen->mainList->length += 1;
        if (itemHandle) *itemHandle = (lsHandle) newElem;
        return LS_OK;
    }
}

lsStatus lsLastItem	(	lsList	list,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 239 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;

    if (realList->botPtr != NIL(lsElem)) {
        *(void **)data = realList->botPtr->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realList->botPtr);
        return(LS_OK);
    } else {
        *(void **)data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return(LS_NOMORE);
    }
}

int lsLength

(

lsList

list

)

Definition at line 268 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;

    return(realList->length);
}

lsStatus lsNewBegin	(	lsList	list,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 151 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->nextPtr = realList->topPtr;
    newElem->prevPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem)) {
        /* The new item is both the top and bottom element */
        realList->botPtr = newElem;
    } else {
        /* There was a top element - make its prev correct */
        realList->topPtr->prevPtr = newElem;
    }
    realList->topPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

lsStatus lsNewEnd	(	lsList	list,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 183 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsElem *newElem;

    newElem = ALLOC(lsElem, 1);
    newElem->userData = data;
    newElem->prevPtr = realList->botPtr;
    newElem->nextPtr = NIL(lsElem);
    newElem->mainList = realList;
    if (realList->topPtr == NIL(lsElem))
      realList->topPtr = newElem;
    if (realList->botPtr != NIL(lsElem))
      realList->botPtr->nextPtr = newElem;
    realList->botPtr = newElem;
    realList->length += 1;
    if (itemHandle) *itemHandle = (lsHandle) newElem;
    return(LS_OK);
}

lsStatus lsNext	(	lsGen	generator,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 432 of file list.c.

{
    register lsGenInternal *realGen = (lsGenInternal *) generator;

    if (realGen->afterSpot == NIL(lsElem)) {
        /* No more stuff to generate */
        *(void **) data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return LS_NOMORE;
    } else {
        *(void **) data = realGen->afterSpot->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realGen->afterSpot);
        /* Move the pointers down one */
        realGen->beforeSpot = realGen->afterSpot;
        realGen->afterSpot = realGen->afterSpot->nextPtr;
        return LS_OK;
    }
}

lsStatus lsPrev	(	lsGen	generator,
		lsGeneric	data,
		lsHandle *	itemHandle
	)

Definition at line 464 of file list.c.

{
    register lsGenInternal *realGen = (lsGenInternal *) generator;

    if (realGen->beforeSpot == NIL(lsElem)) {
        /* No more stuff to generate */
        *(void **) data = (lsGeneric) 0;
        if (itemHandle) *itemHandle = (lsHandle) 0;
        return LS_NOMORE;
    } else {
        *(void **) data = realGen->beforeSpot->userData;
        if (itemHandle) *itemHandle = (lsHandle) (realGen->beforeSpot);
        /* Move the pointers down one */
        realGen->afterSpot = realGen->beforeSpot;
        realGen->beforeSpot = realGen->beforeSpot->prevPtr;
        return LS_OK;
    }

}

lsList lsQueryHandle

(

lsHandle

itemHandle

)

Definition at line 763 of file list.c.

{
    lsElem *realHandle = (lsElem *) itemHandle;

    if (realHandle) {
        return (lsList) realHandle->mainList;
    } else {
        return (lsList) 0;
    }
}

lsStatus lsRemoveItem	(	lsHandle	itemHandle,
		lsGeneric	userData
	)

Definition at line 788 of file list.c.

{
    lsElem *realItem = (lsElem *) itemHandle;
    lsGenInternal gen;

    gen.mainList = realItem->mainList;
    gen.beforeSpot = realItem->prevPtr;
    gen.afterSpot = realItem;
    return lsDelAfter((lsGen) &gen, userData);
}

lsStatus lsSort	(	lsList	list,
		int(*)(lsGeneric, lsGeneric)	compare
	)

Definition at line 815 of file list.c.

                                                                        :
 *   int compare(item1, item2)
 *   lsGeneric item1, item2;
 * The routine should return -1 if item1 is less than item2, 0 if
 * they are equal,  and 1 if item1 is greater than item2.
 * The routine uses a generic merge sort written by Rick Rudell.
 */
{
    lsDesc *realList = (lsDesc *) list;
    lsElem *idx, *lastElem;

    realList->topPtr = lsSortItems(realList->topPtr, compare,
                                  realList->length);

    /* Forward pointers are correct - fix backward pointers */
    lastElem = (lsElem *) 0;
    for (idx = realList->topPtr;  idx != (lsElem *) 0;  idx = idx->nextPtr) {
        idx->prevPtr = lastElem;
        lastElem = idx;
    }
    /* lastElem is last item in list */
    realList->botPtr = lastElem;
    return LS_OK;
}

lsGen lsStart

(

lsList

list

)

Definition at line 361 of file list.c.

{
    lsDesc *realList = (lsDesc *) list;
    lsGenInternal *newGen;

    newGen = ALLOC(lsGenInternal, 1);
    newGen->mainList = realList;
    newGen->beforeSpot = NIL(lsElem);
    newGen->afterSpot = realList->topPtr;
    return ( (lsGen) newGen );
}

lsStatus lsUniq	(	lsList	list,
		int(*)(lsGeneric, lsGeneric)	compare,
		void(*)(lsGeneric)	delFunc
	)

Definition at line 846 of file list.c.

00852                                              :
00853  *   int compare(item1, item2)
00854  *   lsGeneric item1, item2;
00855  * The routine should return -1 if item1 is less than item2, 0 if
00856  * they are equal,  and 1 if item1 is greater than item2. `delFunc'
00857  * will be called with a pointer to a user data item for each
00858  * duplicate destroyed.  `delFunc' can be zero if no clean up
00859  * is required.
00860  */
00861 {
00862     lsGeneric this_item, last_item;
00863     lsGenInternal realGen;
00864     lsDesc *realList = (lsDesc *) list;
00865 
00866     if (realList->length > 1) {
00867         last_item = realList->topPtr->userData;
00868 
00869         /* Inline creation of generator */
00870         realGen.mainList = realList;
00871         realGen.beforeSpot = realList->topPtr;
00872         realGen.afterSpot = realList->topPtr->nextPtr;
00873 
00874         while (realGen.afterSpot) {
00875             this_item = realGen.afterSpot->userData;
00876             if ((*compare)(this_item, last_item) == 0) {
00877                 /* Duplicate -- eliminate */
00878                 (void) lsDelAfter((lsGen) &realGen, &this_item);
00879                 if (delFunc) (*delFunc)(this_item);
00880             } else {
00881                 /* Move generator forward */
00882                 realGen.beforeSpot = realGen.afterSpot;
00883                 realGen.afterSpot = realGen.afterSpot->nextPtr;
00884                 last_item = this_item;
00885             }
00886         }
00887     }
00888     return LS_OK;
00889 }
}