home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Monster Media 1994 #1
/
monster.zip
/
monster
/
OS2
/
CPOSTSRC.ZIP
/
LIST.C
< prev
next >
Wrap
C/C++ Source or Header
|
1992-08-08
|
9KB
|
360 lines
/*------------------------------------------------------------------
* list.c : list functions
*------------------------------------------------------------------
* 10-19-88 originally by Patrick J. Mueller
* 08-07-92 fixed up by Patrick J. Mueller
*------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
/*------------------------------------------------------------------
* create a list
*------------------------------------------------------------------*/
List *ListCreate(
int itemSize,
ListCompareFunc *cmpFunc,
ListNoMemFunc *memFunc
)
{
List *list;
/*---------------------------------------------------------------
* sanity check
*---------------------------------------------------------------*/
if (!itemSize || !cmpFunc)
return NULL;
/*---------------------------------------------------------------
* allocate structure
*---------------------------------------------------------------*/
list = malloc(sizeof(List));
if (!list)
{
if (memFunc)
memFunc();
return NULL;
}
/*---------------------------------------------------------------
* set fields
*---------------------------------------------------------------*/
list->head = NULL;
list->itemSize = itemSize;
list->count = 0;
list->cmpFunc = cmpFunc;
list->memFunc = memFunc;
return list;
}
/*------------------------------------------------------------------
* destroy a list
*------------------------------------------------------------------*/
void ListDestroy(
List *list
)
{
ListNode *node;
ListNode *next;
if (!list)
return;
/*---------------------------------------------------------------
* destroy each node
*---------------------------------------------------------------*/
node = list->head;
while (node)
{
next = node->next;
free(node->pItem);
free(node);
node = next;
}
/*---------------------------------------------------------------
* destroy list
*---------------------------------------------------------------*/
free(list);
}
/*------------------------------------------------------------------
* get number of items in list
*------------------------------------------------------------------*/
int ListCount(
List *list
)
{
if (!list)
return 0;
else
return list->count;
}
/*------------------------------------------------------------------
* find an item
*------------------------------------------------------------------*/
void *ListFind(
List *list,
void *pItem
)
{
ListNode *node;
int cmp;
if (!list || !pItem)
return NULL;
/*---------------------------------------------------------------
* look for item
*---------------------------------------------------------------*/
for (node=list->head; node; node=node->next)
{
cmp = list->cmpFunc(pItem,node->pItem);
if (0 == cmp)
return node->pItem;
else if (cmp < 0)
return NULL;
}
return NULL;
}
/*------------------------------------------------------------------
* add an item
*------------------------------------------------------------------*/
void *ListAdd(
List *list,
void *pItem
)
{
ListNode *last;
ListNode *node;
ListNode *new;
int cmp;
if (!list || !pItem)
return NULL;
/*---------------------------------------------------------------
* find insertion point
*---------------------------------------------------------------*/
last = NULL;
for (node=list->head; node; node=node->next)
{
cmp = (list->cmpFunc)(pItem,node->pItem);
if (0 == cmp)
return NULL;
else if (cmp < 0)
break;
last = node;
}
/*---------------------------------------------------------------
* allocate memory
*---------------------------------------------------------------*/
new = malloc(sizeof(ListNode));
if (new)
new->pItem = malloc(list->itemSize);
if (!new || !new->pItem)
{
if (list->memFunc)
list->memFunc();
return NULL;
}
/*---------------------------------------------------------------
* update count, copy item
*---------------------------------------------------------------*/
list->count++;
memcpy(new->pItem,pItem,list->itemSize);
/*---------------------------------------------------------------
* link into list
*---------------------------------------------------------------*/
if (last)
{
new->next = last->next;
last->next = new;
}
else
{
new->next = list->head;
list->head = new;
}
return new->pItem;
}
/*------------------------------------------------------------------
* delete an item
*------------------------------------------------------------------*/
void ListDelete(
List *list,
void *pItem
)
{
ListNode *last;
ListNode *node;
int cmp;
if (!list || !pItem)
return;
/*---------------------------------------------------------------
* find node
*---------------------------------------------------------------*/
last = NULL;
for (node=list->head; node; node=node->next)
{
cmp = (list->cmpFunc)(pItem,node->pItem);
if (0 == cmp)
break;
else if (cmp < 0)
return;
last = node;
}
/*---------------------------------------------------------------
* if not found, exit
*---------------------------------------------------------------*/
if (!node)
return;
/*---------------------------------------------------------------
* unlink from list
*---------------------------------------------------------------*/
if (last)
{
if (last->next)
last->next = last->next->next;
else
last->next = NULL;
}
else
list->head = node->next;
/*---------------------------------------------------------------
* update count, destroy item
*---------------------------------------------------------------*/
list->count--;
free(node->pItem);
free(node);
}
/*------------------------------------------------------------------
* iterate through items
*------------------------------------------------------------------*/
void ListIterate(
List *list,
ListIterateFunc *pIterateFunc,
void *pUserData
)
{
ListNode *node;
if (!list || !pIterateFunc)
return;
for (node=list->head; node; node=node->next)
pIterateFunc(node->pItem,pUserData);
}
/*------------------------------------------------------------------
* test suite
*------------------------------------------------------------------*/
#if defined(TEST)
/*------------------------------------------------------------------
* compare function
*------------------------------------------------------------------*/
static int compareFunc(
void *overi1,
void *overi2
)
{
int *i1 = overi1;
int *i2 = overi2;
if (*i1 < *i2) return -1;
else if (*i1 > *i2) return 1;
else return 0;
}
/*------------------------------------------------------------------
* iterate function
*------------------------------------------------------------------*/
static void iterateFunc(
void *overI,
void *overCounter
)
{
int *pi = overI;
int *pCounter = overCounter;
printf("%5d : %5d\n",*pCounter,*pi);
*pCounter += 1;
}
/*------------------------------------------------------------------
*
*------------------------------------------------------------------*/
int main(void)
{
List *iList;
int i;
int counter;
iList = ListCreate(sizeof(int),compareFunc,NULL);
printf("%d items\n",ListCount(iList));
for (i= 1; i<10; i++)
ListAdd(iList,&i);
for (i=20; i>10; i--)
ListAdd(iList,&i);
for (i=0; i<=21; i++)
if (!ListFind(iList,&i))
printf("didn't find %d\n",i);
printf("\n");
printf("%d items\n",ListCount(iList));
counter = 1;
ListIterate(iList,iterateFunc,&counter);
for (i=-1; i<5; i++)
ListDelete(iList,&i);
for (i=21; i>15; i--)
ListDelete(iList,&i);
printf("\n");
printf("%d items\n",ListCount(iList));
counter = 1;
ListIterate(iList,iterateFunc,&counter);
ListDestroy(iList);
return 0;
}
#endif