Linked List Test Program
Note: Linked Lists Macros Are In The Second File
/**********************************************************************
*
* Description:
*
* Test the Link List Macros.
*
***********************************************************************
*
* Change Log:
*
* 15 Jan 1999 T L Wolfe
* - Original code completed
*
**********************************************************************/
/* include files */
#include <errno.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include "link_list_macros.h"
/* definitions and macros */
#define APPNAME "TEST_LINK_LIST_MACROS (in c)"
#define APPVERSION "1.0"
typedef struct element
{
struct element *flink;
struct element *blink;
int data;
} ELEMENT;
typedef struct
{
ELEMENT *first;
ELEMENT *last;
} LIST;
/* global variables */
int Debug = 0;
static LIST *List = NULL;
/* subroutine prototypes */
static void create_sorted_list();
static ELEMENT *create_new_list_element();
static void delete_list();
static void display_list();
static int empty_string(char*);
static void insert_element_into_list_sorted(ELEMENT*);
static ELEMENT *locate_value_in_list(int);
static void pause_program();
static int process_command_line(int,char**);
/*-------------------------------------------------------------------*/
/* main */
/* */
/* parameter Description */
/* */
/* Argc command line argument count */
/* Argv command line arguments */
/* */
/*-------------------------------------------------------------------*/
int main (int Argc, char *Argv[])
{
int v;
ELEMENT *e;
ELEMENT *ee;
int selection;
char reply[64];
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* housekeeping */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* display startup message */
printf("\n");
printf("Test Utility - test link list macros\n");
printf("\n");
/* process command line arguments and set defaults (if any) */
if (!process_command_line(Argc,Argv)) exit(1);
/* malloc and initialize the list head */
if ((List = (LIST*)malloc(sizeof(LIST))) == NULL) exit(errno);
INITIALIZE_LIST(List);
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* process user commands */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
for(;;)
{
printf("\n");
printf(" ---------------------------------------------------\n");
printf(" Selection Description\n");
printf(" --------- --------------------------------------\n");
printf(" 1 test if list is empty\n");
printf(" 2 insert element at head of list\n");
printf(" 3 insert element at tail of list\n");
printf(" 4 remove element at head of list\n");
printf(" 5 remove element at tail of list\n");
printf(" 6 insert element into list after...\n");
printf(" 7 insert element into list before...\n");
printf(" 8 remove element from list\n");
printf(" 9 display list\n");
printf(" 10 create sorted list\n");
if (Debug)
{
printf(" 11 debug OFF\n");
}
else
{
printf(" 11 debug ON\n");
}
printf(" 12 exit program\n");
printf("\n Enter selection by number: ");
gets(reply);
if (empty_string(reply)) break;
if (sscanf(reply,"%d",&selection) != 1)
{
printf("\n Illegal selection (%s)\n",reply);
pause_program();
continue;
}
if (selection == 12) break;
switch(selection)
{
case 1:
{
if (LIST_EMPTY(List))
{
printf("\n List is empty\n");
}
else
{
printf("\n List is not empty\n");
}
pause_program();
break;
}
case 2:
{
if ((e = create_new_list_element()) != NULL)
{
INSERT_AT_HEAD_OF_LIST(List,e);
}
pause_program();
break;
}
case 3:
{
if ((e = create_new_list_element()) != NULL)
{
INSERT_AT_TAIL_OF_LIST(List,e);
}
pause_program();
break;
}
case 4:
{
REMOVE_FROM_HEAD_OF_LIST(List,e);
if (e != NULL) free(e);
pause_program();
break;
}
case 5:
{
REMOVE_FROM_TAIL_OF_LIST(List,e);
if (e != NULL) free(e);
pause_program();
break;
}
case 6:
{
if ((ee = create_new_list_element()) == NULL) break;
printf("\n Enter location value: ");
gets(reply);
if (empty_string(reply))
{
free(ee);
break;
}
if (sscanf(reply,"%d",&v) != 1)
{
printf("\n Error: bad location value (%s)\n",reply);
free(ee);
pause_program();
break;
}
if ((e = locate_value_in_list(v)) == NULL)
{
printf(
"\n Error: unable to locate value (%d) in list\n",v);
free(ee);
pause_program();
break;
}
INSERT_INTO_LIST_AFTER(List,e,ee);
printf("\n Element inserted in to list\n");
pause_program();
break;
}
case 7:
{
if ((ee = create_new_list_element()) == NULL) break;
printf("\n Enter location value: ");
gets(reply);
if (empty_string(reply))
{
free(ee);
break;
}
if (sscanf(reply,"%d",&v) != 1)
{
printf("\n Error: bad location value (%s)\n",reply);
free(ee);
pause_program();
break;
}
if ((e = locate_value_in_list(v)) == NULL)
{
printf(
"\n Error: unable to locate value (%d) in list\n",v);
free(ee);
pause_program();
break;
}
INSERT_INTO_LIST_BEFORE(List,e,ee);
printf("\n Element inserted in to list\n");
pause_program();
break;
}
case 8:
{
printf("\n");
printf(" Enter value to be removed: ");
gets(reply);
if (empty_string(reply)) break;
if (sscanf(reply,"%d",&v) != 1)
{
printf("\n Error: bad element value (%s)\n",reply);
pause_program();
break;
}
if ((e = locate_value_in_list(v)) != NULL)
{
REMOVE_FROM_LIST(List,e);
free(e);
printf("\n Value %d removed from list\n",v);
}
else
{
printf("\n Could not locate value %d in the list\n",v);
}
pause_program();
break;
}
case 9:
{
display_list();
pause_program();
break;
}
case 10:
{
create_sorted_list();
break;
}
case 11:
{
if (Debug) Debug = 0; else Debug = 1;
break;
}
default:
{
printf("\n Illegal Selection: %d\n",selection);
pause_program();
}
}
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* end of program */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
printf("\n");
}
/*-------------------------------------------------------------------*/
/* Pause before continuing. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static void pause_program ()
{
char reply[64];
printf("\n Enter carriage return to continue: ");
gets(reply);
}
/*-------------------------------------------------------------------*/
/* Locate a specified value in the list. */
/* */
/* parameter Description */
/* */
/* V value to be located */
/* */
/*-------------------------------------------------------------------*/
static ELEMENT *locate_value_in_list (int V)
{
ELEMENT *e;
e = List->first;
while(e != NULL)
{
if (e->data == V) return e;
e = e->flink;
}
return NULL;
}
/*-------------------------------------------------------------------*/
/* Delete all of the elements in the list. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static void delete_list ()
{
ELEMENT *e;
ELEMENT *ee;
e = List->first;
while(e != NULL)
{
ee = e;
e = e->flink;
free(ee);
}
List->first = List->last = NULL;
return;
}
/*-------------------------------------------------------------------*/
/* Create new list element with a user supplied value. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static ELEMENT *create_new_list_element ()
{
int v;
ELEMENT *e;
char reply[64];
printf("\n Enter new element value: ");
gets(reply);
if (empty_string(reply)) return NULL;
if (sscanf(reply,"%d",&v) != 1)
{
printf(" Error: bad element value (%s)\n",reply);
return NULL;
}
if ((e = (ELEMENT*)malloc(sizeof(ELEMENT))) == NULL) exit(errno);
e->flink = NULL;
e->blink = NULL;
e->data = v;
return e;
}
/*-------------------------------------------------------------------*/
/* Insert an element into the list in ascending sort order. */
/* */
/* This routine will maintain the new elements added to the list in */
/* ascending order. */
/* */
/* parameter Description */
/* */
/* New new element to be inserted */
/* */
/*-------------------------------------------------------------------*/
static void insert_element_into_list_sorted (ELEMENT *New)
{
ELEMENT *e;
if (Debug)
{
if (New == NULL)
{
printf("insert_element_into_list_sorted(NULLPOINTER)\n");
}
else
{
printf("insert_element_into_list_sorted(%d)\n",New->data);
}
}
e = List->first;
while (e != NULL)
{
if (New->data < e->data)
{
printf("New->data = %d, e->data = %d\n",New->data,e->data);
INSERT_INTO_LIST_BEFORE(List,e,New);
return;
}
e = e->flink;
}
INSERT_AT_TAIL_OF_LIST(List,New);
return;
}
/*-------------------------------------------------------------------*/
/* Create a sorted list. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static void create_sorted_list ()
{
ELEMENT *e;
delete_list();
while (e = create_new_list_element())
{
insert_element_into_list_sorted(e);
}
return;
}
/*-------------------------------------------------------------------*/
/* Display the list. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static void display_list ()
{
int i = 0;
ELEMENT *e;
printf("\n");
if (Debug)
{
printf(" ------------------------------------\n");
printf(" List:\n");
printf(" First = %p\n",List->first);
printf(" Last = %p\n",List->last);
}
printf(" ------------------------------------\n");
if (LIST_EMPTY(List))
{
printf(" List is empty\n");
}
else
{
e = List->first;
while(e != NULL)
{
if (Debug)
{
printf(" Element %d:\n",i++);
printf(" E = %p\n",e);
printf(" Flink = %p\n",e->flink);
printf(" Blink = %p\n",e->blink);
}
printf(" Value = %d\n",e->data);
e = e->flink;
if (i > 4) break;
}
}
printf(" ------------------------------------\n");
return;
}
/*-------------------------------------------------------------------*/
/* Display usage. */
/* */
/* parameter Description */
/* */
/*-------------------------------------------------------------------*/
static void display_usage ()
{
printf("\n");
printf("--------------------------------------------------------\n");
printf("%s ...\n",APPNAME " - Version " APPVERSION);
printf("\n");
printf(" debug display debug messages\n");
printf("\n");
printf("--------------------------------------------------------\n");
printf("\n");
return;
}
/*-------------------------------------------------------------------*/
/* test for empty string */
/*-------------------------------------------------------------------*/
static int empty_string (char *Str)
{
if (Str == NULL) return 1;
while (*Str != '\0')
{
if (!isspace(*Str++)) return 0;
}
return 1;
}
/*-------------------------------------------------------------------*/
/* Process the command line arguments. */
/* */
/* Return FALSE (zero) if not successful */
/* Return TRUE (non-zero) if successful */
/* */
/* parameter Description */
/* */
/* Argc command line argument count */
/* Argv command line arguments */
/* */
/*-------------------------------------------------------------------*/
static int process_command_line (int Argc, char *Argv[])
{
int i;
for(i = 1; i < Argc; i++)
{
if (strcmp(Argv[i],"debug") == 0)
{
Debug = 1;
}
else if (strcmp(Argv[i],"help") == 0)
{
display_usage();
exit(0);
}
else
{
printf("Command line error: Unknown command (%s)\n",Argv[i]);
return 0;
}
}
Linked List Macros
/****************************************************************
*
* Description:
*
* Macros that manipulate doubly linked lists. The user/developer
* is responsible for defining the list head and list element data
* structures. At a minimum they must include the required data
* items (see code example).
*
***********************************************************************
*
* Change Log:
*
* 01 Jan 1999 T L Wolfe
* - Original code completed
*
***********************************************************************
*
* Code examples:
*
* A typical list element structure definition looks like:
*
* typedef struct element
* {
* struct element *flink; <-- link to next element in list
* struct element *blink; <-- link to previous element in list
* int data1; <-- user defined data
* int data2; <-- user defined data
* int data3; <-- user defined data
* } ELEMENT;
*
* Note: 'flink' (forward link) and 'blink' (backward link)
* are required by the macros.
*
*
* A typical list head structure definition looks like:
*
* typedef struct
* {
* ELEMENT *first; <-- link to first element in list
* ELEMENT *last; <-- link to last element in list
* } LIST;
*
* Note: 'first' (first element in list) and 'last' (last
* element in list) are required by the macros
*
*
* A typical forward-search routine looks like:
*
* ELEMENT *Locate_Value_V_In_The_List (LIST *L, int V)
* {
* ELEMENT *e;
*
* e = L->first;
*
* while(e != NULL)
* {
* if (e->data1 == V) break;
* e = e->flink;
* }
*
* return e;
* }
*
*
* A typical insert-data-in-ascending-order routine looks like:
*
* void Insert_Data_Sorted (LIST *L, ELEMENT *new)
* {
* ELEMENT *e;
*
* e = L->first;
*
* while (e != NULL)
* {
*
* if (new->data < e->data)
* {
* INSERT_INTO_LIST_BEFORE(L,e,new);
* return;
* }
*
* e = e->flink;
* }
*
* INSERT_AT_TAIL_OF_LIST(L,new);
*
* return;
* }
*
*
* Notes:
*
* a) Internally the forward and backward links are terminated with
* a NULL pointer.
*
* b) Internally an empty list is has a list head with the "first"
* and "last" pointers equal to NULL.
*
* c) L is the address of a list head data structure.
*
* d) P, P1, P2 are the addresses of list element data structures when
* inserting into a list.
*
* e) P is a pointer variable where the address of a list element is
* returned or an element remove from a list.
*
*
**********************************************************************/
#ifndef _LINK_LIST_MACROS_H
#define _LINK_LIST_MACROS_H
/*-------------------------------------------------------------------*/
/* initialize the list L */
/* Only do this one time per list. */
/*-------------------------------------------------------------------*/
#define INITIALIZE_LIST(L) (L)->first = (L)->last = NULL;
/*-------------------------------------------------------------------*/
/* test if the list L is empty. 1 (true) or 0 (false) is returned. */
/*-------------------------------------------------------------------*/
#define LIST_EMPTY(L) (((L)->first == NULL) ? 1 : 0)
/*-------------------------------------------------------------------*/
/* Insert the element P2 after the element P1 in the list L */
/*-------------------------------------------------------------------*/
#define INSERT_INTO_LIST_AFTER(L,P1,P2) \
{ \
(P2)->flink = (P1)->flink; \
(P2)->blink = (P1); \
if ((P1)->flink == NULL) \
{ \
(L)->last = (P2); \
} \
else \
{ \
(P1)->flink->blink = (P2); \
} \
(P1)->flink = (P2); \
}
/*-------------------------------------------------------------------*/
/* Insert the element P2 before the element P1 in the list L */
/*-------------------------------------------------------------------*/
#define INSERT_INTO_LIST_BEFORE(L,P1,P2) \
{ \
(P2)->blink = (P1)->blink; \
(P2)->flink = (P1); \
if ((P1)->blink == NULL) \
{ \
(L)->first = (P2); \
} \
else \
{ \
(P1)->blink->flink = (P2); \
} \
(P1)->blink = (P2); \
}
/*-------------------------------------------------------------------*/
/* Remove element P from the list L */
/*-------------------------------------------------------------------*/
#define REMOVE_FROM_LIST(L,P) \
{ \
if ((P)->flink == NULL) \
{ \
(L)->last = (P)->blink; \
} \
else \
{ \
(P)->flink->blink = (P)->blink; \
} \
if ((P)->blink == NULL) \
{ \
(L)->first = (P)->flink; \
} \
else \
{ \
(P)->blink->flink = (P)->flink; \
} \
(P)->flink = (P)->blink = NULL; \
}
/*-------------------------------------------------------------------*/
/* Insert the element P at the head (front) of the list L */
/*-------------------------------------------------------------------*/
#define INSERT_AT_HEAD_OF_LIST(L,P) \
{ \
(P)->blink = NULL; \
(P)->flink = (L)->first; \
if ((L)->first != NULL) \
{ \
(L)->first->blink = (P); \
} \
(L)->first = (P); \
if ((L)->last == NULL) \
{ \
(L)->last = (P); \
}; \
}
/*-------------------------------------------------------------------*/
/* Insert element P at the end (tail) of the list L */
/*-------------------------------------------------------------------*/
#define INSERT_AT_TAIL_OF_LIST(L,P) \
{ \
(P)->flink = NULL; \
(P)->blink = (L)->last; \
if ((L)->last != NULL) \
{ \
(L)->last->flink = (P); \
} \
(L)->last = (P); \
if ((L)->first == NULL) \
{ \
(L)->first = (P); \
}; \
}
/*-------------------------------------------------------------------*/
/* Remove the head (first) element from the list L. */
/* P is set to NULL if no list element was found. */
/*-------------------------------------------------------------------*/
#define REMOVE_FROM_HEAD_OF_LIST(L,P) \
{ \
(P) = (L)->first; \
if ((P) != NULL) \
{ \
(L)->first = (P)->flink; \
if ((P)->flink == NULL) \
{ \
(L)->last = NULL; \
} \
else \
{ \
(P)->flink->blink = NULL; \
} \
(P)->flink = (P)->blink = NULL; \
}; \
}
/*-------------------------------------------------------------------*/
/* Remove the tail (last) element from the list L. */
/* P is set to NULL if no element was found. */
/*-------------------------------------------------------------------*/
#define REMOVE_FROM_TAIL_OF_LIST(L,P) \
{ \
(P) = (L)->last; \
if ((P) != NULL) \
{ \
(L)->last = (P)->blink; \
if ((P)->blink == NULL) \
{ \
(L)->first = NULL; \
} \
else \
{ \
(P)->blink->flink = NULL; \
} \
(P)->flink = (P)->blink = NULL; \
}; \
}
#endif /* #endif for _LINK_LIST_MACROS_H */