Category : C Source Code
Archive   : LLIST102.ZIP
Filename : LLIST.C

 
Output of file : LLIST.C contained in archive : LLIST102.ZIP
/**

llist.c -- source file for doubly linked list functions

**/

#define BOOLEAN int
#define TRUE 1
#define FALSE 0
#define L_ERROR -1

/*
* Define NULL if it's not already defined
*/
#ifndef NULL
#if SPTR
#define NULL 0 /* null pointer value */
#else
#define NULL 0L
#endif
#endif

#ifndef NARGS
extern char *malloc(unsigned);
extern char *calloc(unsigned,unsigned);
extern int free(char *);
#else
extern char *malloc();
extern char *calloc();
extern int free();
#endif

#define MALLOC(x) ((x *) malloc(sizeof(x)))
#define CALLOC(n,x) ((x *) calloc(n,sizeof(x)))

struct HEAD /* header of list */
{ int L_LENGTH; /* number of links */
struct LINK *L_FIRST, *L_LAST; /* pointers to first, last links */
};
typedef struct HEAD HEAD_T;

struct LINK /* element of list */
{ struct LINK *L_PREV; /* previous link */
struct LST_DATA *L_DATA; /* this structure user-supplied */
struct LINK *L_NEXT; /* next link */
};
typedef struct LINK LINK_T;

/**************************
* create new linked list *
**************************/

HEAD_T *inst_list()

{ HEAD_T *new;

if (new = MALLOC(HEAD_T)) /* attempt allocation */
{ new->L_LENGTH = 0; /* set length zero, */
new->L_FIRST = new->L_LAST = NULL; /* no links, so NULL */
}

return(new); /* now, return address */
}


/************************
* instantiate new link *
************************/

LINK_T *inst_link(data, prev, next)
struct LST_DATA *data;
LINK_T *prev, *next;

{ LINK_T *new;

if (new = MALLOC(LINK_T)) /* attempt allocation */
{ new->L_PREV = prev; /* link in link */
new->L_DATA = data;
new->L_NEXT = next;
}

return(new); /* and return it's address */
}


/*********************************
* add data to beginning of list *
*********************************/

BOOLEAN add_first(data, list)
struct LST_DATA *data;
HEAD_T *list;

{ LINK_T *new;
LINK_T *inst_link(struct LST_DATA *, LINK_T *, LINK_T *);

if (new = inst_link(data, NULL, list->L_FIRST)) /* allocate memory */
{ if (list->L_LENGTH) /* not empty */
list->L_FIRST->L_PREV = new; /* so readjust pointers */
else /* empty, so this is */
list->L_LAST = new; /* the last */
list->L_FIRST = new; /* as well as the first link */
list->L_LENGTH++; /* chalk up another link */
return(TRUE); /* and say we're OK */
}
else /* memory error... */
return(FALSE); /* let them know */
}


/***************************
* add data to end of list *
***************************/

BOOLEAN add_last(data, list)
struct LST_DATA *data;
HEAD_T *list;

{ LINK_T *new;
LINK_T *inst_link(struct LST_DATA *, LINK_T *, LINK_T *);


if (new = inst_link(data, list->L_LAST, NULL)) /* allocate memory */
{ if (list->L_LENGTH) /* not empty */
list->L_LAST->L_NEXT = new; /* so link item to end */
else /* if empty, */
list->L_FIRST = new; /* this link is the first */
list->L_LAST = new; /* AND the last */
list->L_LENGTH++; /* add one to the counter */
return(TRUE); /* and say we're ok */
}
else /* memory error */
return(FALSE); /* so we're not ok */
}


/************************************
* insert link anywhere into a list *
************************************/

BOOLEAN add_after(data, list, link)
struct LST_DATA *data;
HEAD_T *list;
int link;

{ int floop;
LINK_T *new, *temp;

BOOLEAN add_first(struct LST_DATA *, HEAD_T *);
BOOLEAN add_last(struct LST_DATA *, HEAD_T *);
LINK_T *inst_link(struct LST_DATA *, LINK_T *, LINK_T *);

if (link < 0 || link > list->L_LENGTH) /* out of bounds? */
return(FALSE);

if (link == 0) /* inserting at the head; trivial */
if (add_first(data, list) == FALSE) /* no memory? */
return(FALSE); /* flag error */
else /* otherwise, */
return(TRUE); /* we'eze okee dokee */
else
if (link == list->L_LENGTH) /* inserting at tail; trivial too */
if (add_last(data, list) == FALSE) /* ditto... */
return(FALSE);
else
return(TRUE);
else
{ /* inserting somewhere inside */
temp = list->L_FIRST; /* get the first link */
for (floop = 1; floop < link; ++floop)
temp = temp->L_NEXT; /* now count down to the wanted link */
if ((new = inst_link(data, temp, temp->L_NEXT)) == NULL) /* add AFTER this link */
return(FALSE);
else
{ temp->L_NEXT->L_PREV = new; /* the following link now points to new */
temp->L_NEXT = new; /* so does this link */
list->L_LENGTH++; /* now increment the count */
}
}

return(TRUE); /* we made it! */
}


/*********************
* delete first link *
*********************/

struct LST_DATA *del_first(list)
HEAD_T *list;

/* this will free the link's memory, but not */
/* the data element's memory */

{ LINK_T *temp;
struct LST_DATA *data;

if (list->L_LENGTH == 0) /* empty list? */
return((struct LST_DATA *)L_ERROR); /* flag an error */

temp = list->L_FIRST; /* save the pointer */
data = temp->L_DATA; /* and it's data */
list->L_FIRST = temp->L_NEXT; /* bypass the link */
list->L_LENGTH--; /* decrement the link count */
if (list->L_LENGTH) /* if we still have elements */
list->L_FIRST->L_PREV = NULL; /* then link one's previous pointer */
else /* should be set to NULL. Otherwise, */
list->L_LAST = NULL; /* the last link now is NULL */

free((char *)temp); /* deassign the memory it occupied */

return(data); /* finally, return the link's data pointer */
}


/********************
* delete last link *
********************/

struct LST_DATA *del_last(list)
HEAD_T *list;

{ LINK_T *temp;
struct LST_DATA *data;

if (list->L_LENGTH == 0) /* empty list? */
return((struct LST_DATA *)L_ERROR); /* flag an error */

temp = list->L_LAST; /* save the last link */
data = temp->L_DATA; /* and it's data */

list->L_LAST = temp->L_PREV; /* delete link, hook up with it's predecessor */
list->L_LENGTH--; /* and decrement the link count */
if (list->L_LENGTH) /* if we still have links */
list->L_LAST->L_NEXT = NULL; /* say we're at the end of the list */
else /* otherwise, empty list, so */
list->L_FIRST = NULL; /* say so */

free((char *)temp); /* release it's memory */

return(data); /* and return it's data pointer */
}


/************************
* delete internal link *
************************/

struct LST_DATA *del_link(list, link)
HEAD_T *list;
int link;

{ int floop;
LINK_T *temp;
struct LST_DATA *data;

if ((link < 1) || (link > list->L_LENGTH)) /* out of bounds */
return((struct LST_DATA *)L_ERROR); /* flag an error */

temp = list->L_FIRST; /* point to first link to start */
for (floop = 1; floop < link; ++floop)
temp = temp->L_NEXT; /* now work through the list */

data = temp->L_DATA; /* save the data pointer */

if (link != 1) /* the following is meaningless for link 1 */
temp->L_PREV->L_NEXT = temp->L_NEXT; /* hook the previous link to the next */
else /* but if it is the first link, */
list->L_FIRST = temp->L_NEXT; /* adjust the header */

if (link != list->L_LENGTH) /* likewise for the last link */
temp->L_NEXT->L_PREV = temp->L_PREV;
else /* and adjust the header if it is */
list->L_LAST = temp->L_PREV; /* the new last link */

list->L_LENGTH--; /* now decrement the counter */

/*
note that the previous will set the header to point to two NULLs if
the list was only one link long. How nice. It also collapses to
the del_first() or del_last() functions if the link was the first or
last one in the list.
*/

free((char *)temp); /* release the link's memory */

return(data); /* and return it's data pointer */
}


/*************************
* delete multiple links *
*************************/

int del_from_to(list, from, to, process)
HEAD_T *list;
int from, to;
void (*process)(struct LST_DATA *);

{ int floop, deleted = 0;
struct LST_DATA *data;
struct LST_DATA *del_link(HEAD_T *, int);

if ((from < 1) || (from > list->L_LENGTH) || (to < 1) || (to > list->L_LENGTH)
|| (to < from))
return(L_ERROR); /* out of bounds */

/*
to delete n nodes in a list, start at the from node, and always
delete it. Set a counter that run for n nodes (that is, to - from),
and since a deletion always bumps nodes forwards, by deleting the
"from-th" node, you will always delete the proper node, so simply do
this n number of times. This is what the following statement does!
Process() is a function that does something with the discarded data
from the node. It is user-supplied.
*/
for (floop = from; floop <= to; ++floop)
{ if ((data = del_link(list, from)) != (struct LST_DATA *)L_ERROR)
{ (*process)(data); /* process data if ok */
++deleted; /* and increment deleted counter */
}
}

return(deleted); /* and send back how many we're creamed */
}


/*************************************
* delete multiple links recursively *
*************************************/

void rdel_from_to(list, from, to, process)
HEAD_T *list;
int from, to;
void (*process)(struct LST_DATA *);

{ struct LST_DATA *data;

if ((from < 1) || (from > list->L_LENGTH) || (to < 1) || (to >list->L_LENGTH)
|| (to < from))
return;

if (from != to) /* climb "down" the list to the to-th link */
rdel_from_to(list, from + 1, to, process);

data = del_link(list, from); /* unhook this link */
(*process)(data); /* and process it's data */

return;
}


/****************************
* merge two lists together *
****************************/

BOOLEAN merge_after(from_list, to_list, after_link)
HEAD_T *from_list, *to_list;
int after_link;

{ int floop;
LINK_T *temp;

if (after_link < 0 || after_link > to_list->L_LENGTH)
return(FALSE); /* out of bounds */

if (after_link == 0) /* merging to beginning */
{ from_list->L_LAST->L_NEXT = to_list->L_FIRST; /* add on the new list */
to_list->L_FIRST->L_PREV = from_list->L_LAST; /* to the start of the first */
to_list->L_FIRST = from_list->L_FIRST; /* and fix the header */
to_list->L_LENGTH += from_list->L_LENGTH; /* adjust the count */
}
else
if (after_link != to_list->L_LENGTH) /* merging to middle */
{ temp = to_list->L_FIRST; /* save the first link */
for (floop = 1; floop < after_link; ++floop)
temp = temp->L_NEXT; /* move to the wanted link */
from_list->L_FIRST->L_PREV = temp; /* link from's head to to */
from_list->L_LAST->L_NEXT = temp->L_NEXT; /* and from's tail to to too! */
temp->L_NEXT->L_PREV = from_list->L_LAST; /* link to to from's tail */
temp->L_NEXT = from_list->L_FIRST; /* and to from's head! */
to_list->L_LENGTH += from_list->L_LENGTH; /* adjust the count */
}
else
/* if (after_link == to_list->L_LENGTH) /* merging to the tail */ */
{ from_list->L_FIRST->L_PREV = to_list->L_LAST; /* add on the new list */
to_list->L_LAST->L_NEXT = from_list->L_FIRST; /* to the tail of the first */
to_list->L_LAST = from_list->L_LAST; /* and fix the header */
to_list->L_LENGTH += from_list->L_LENGTH; /* adjust the counter */
}

return(TRUE); /* and scram */
}


/*************************************
* split a list into two other lists *
*************************************/

HEAD_T *split_list(list, from, to)
HEAD_T *list;
int from, to;

{ int floop;
LINK_T *temp;
HEAD_T *new;

HEAD_T *inst_list();

if ((from < 1) || (from > list->L_LENGTH) || (to < 1) || (to > list->L_LENGTH)
|| (to < from))
return((HEAD_T *)L_ERROR); /* out of ... you guessed it! */

if ((new = inst_list()) == NULL)
return((HEAD_T *)L_ERROR); /* memory error. Abort! */

temp = list->L_FIRST; /* get the front of the old list */
for (floop = 1; floop < from; ++floop)
temp = temp->L_NEXT; /* now move to the from-th link */
new->L_FIRST = temp; /* if from == 1, we haven't gone anywhere */

for (floop = from; floop < to; ++floop)
temp = temp->L_NEXT; /* now move to the to-th link */

new->L_LAST = temp; /* if from == to, again we don't move */

/*
Now, we must break the first list's chain and re-link it
together so it skips the links that have been moved; we
don't want any dangling links or double pointers (links
belonging to more than one chain) when we're done. If we
changed the old list's first or last links, we need to
update its header as well.
*/
if (new->L_FIRST->L_PREV != NULL) /* if not first link */
new->L_FIRST->L_PREV->L_NEXT = /* the link in front of the one we're moving */
new->L_LAST->L_NEXT; /* gets hooked to the one after the last */
else /* if is the first link, */
list->L_FIRST = /* set the old list first link to */
new->L_LAST->L_NEXT; /* be the link following the last of the move */

if (new->L_LAST->L_NEXT != NULL) /* if not last link */
new->L_LAST->L_NEXT->L_PREV = /* the link after the last link we're changing */
new->L_FIRST->L_PREV; /* gets hooked to the one before the first */
else /* if it is the last link */
list->L_LAST = /* set the old list last link to */
new->L_FIRST->L_PREV; /* the link in front of the new list's first link */
/*
the preceeding if .. else statements will have the effect
of producing a header that points to two NULLs if the
entire list is to be moved.
*/

new->L_FIRST->L_PREV = new->L_LAST->L_NEXT = NULL; /* now NULL the start and end */

list->L_LENGTH -= (to - from + 1); /* delete the old link count */
new->L_LENGTH += (to - from + 1); /* and add that amount to the new list */

return(new); /* finally, this is the new list! */
}


/**********************************************
* move one section of a list to another list *
**********************************************/

BOOLEAN move_list(from_list, to_list, from_from, from_to, to)
HEAD_T *from_list, *to_list;
int from_from, from_to, to;

{ BOOLEAN ret_val;
HEAD_T *temp;

HEAD_T *split_list(HEAD_T *, int, int);
BOOLEAN merge_after(HEAD_T *, HEAD_T *, int);

if ((temp = split_list(from_list, from_from, from_to)) == (HEAD_T *)L_ERROR)
return(FALSE); /* attempt to split list; signal if can't */

ret_val = (merge_after(temp, to_list, to) == FALSE) ? FALSE : TRUE;
/* now try to merge the new split */
/* list into the to_list. If can't, */
/* return with error */
free((char *)temp); /* free the temporary list */
return(ret_val); /* back we go */
}


/***********************************************
* delete a list's contents but not the header *
***********************************************/

void free_links(link)
LINK_T *link;

{ void free_links(LINK_T *);

if (link->L_NEXT != NULL) /* recursive climb down to the end */
free_links(link->L_NEXT);

if (link->L_PREV != NULL) /* not the first link */
link->L_PREV->L_NEXT = NULL; /* so break the chain! */

free((char *)link->L_DATA); /* free the data */
free((char *)link); /* and the link */

return; /* now go back */
}


/**************************
* free up an entire list *
**************************/

void purge_list(list)
HEAD_T *list;

{ void free_links(LINK_T *);

free_links(list->L_FIRST); /* break the chain into bits */

free((char *)list); /* and eliminate the header itself */

return;
}


  3 Responses to “Category : C Source Code
Archive   : LLIST102.ZIP
Filename : LLIST.C

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/