#include ''LL.h'' t_LL ConsLL (); t_LL InitLL(struct s_LL* head); t_LL ConsCopyLL(t_LL dest); t_LL ConsPtrLL(t_LL dest); void * DestLL(t_LL list); t_LL EmptyLL (t_LL list) int IsEmptyLL(t_LL list) t_LL ReverseLL(t_LL list) void * ApplyLL (t_LL list, void * (*apply) (void *)) t_LL SortLL (t_LL list, int (*compar) (void *, void*)) long SizeLL (t_LL list); void * LookInLL(t_LL list); t_LL File2LL(char * name); t_LL FileNoExit2LL(char * name); void LL2File(t_LL list, char * name); char ** LL2ArrStr(t_LL list); t_LL ReadLL(char * filename); void WriteLev1LL(char * f_name, t_LL list); void WriteLev2LL(char * f_name, t_LL list); void WriteLev3LL(char * f_name, t_LL list); void WriteLevNLL(char * f_name, t_LL list, int l); /* write list of lev l*/ #define InsBefLL(p_el,data) InsBefLLf(p_el, sizeof(data), &data) #define InsAftLL(p_el,data) InsAftLLf(p_el, sizeof(data), &data) #define InsFirstLL(list,data) InsFirstLLf(list, sizeof(data), &data) #define InsLastLL(list,data) InsLastLLf(list, sizeof(data), &data) void * InsBefLLf (void * p_elm, size_t size, void * data); void * InsAftLLf (void * p_elm, size_t size, void * data); void * InsFirstLLf (t_LL list, size_t size, void * data); void * InsLastLLf (t_LL list, size_t size, void * data); #define LinkInsBefLL(p_el,data) LinkInsBefLLf(p_el, sizeof(data),&(data)) #define LinkInsAftLL(p_el,data) LinkInsAftLLf(p_el, sizeof(data),&(data)) #define LinkInsFirstLL(list,data) LinkInsFirstLLf(list,sizeof(data),&(data)) #define LinkInsLastLL(list,data) LinkInsLastLLf(list, sizeof(data),&(data)) void * LinkInsFirstLLf(t_LL list, size_t size, void * newEl); void * LinkInsLastLLf(t_LL list, size_t size, void * newEl); void * LinkInsAftLLf(void * curr, size_t size, void * newEl); void * LinkInsBefLLf(void * curr, size_t size, void * newEl); void DelElmLL (void * p_elm); void * DelElmNeLL(void * p_elm); void * DelElmPrLL(void * p_elm); t_LL MoveListFirstLL(t_LL dest, t_LL src); t_LL MoveListLastLL(t_LL dest, t_LL src); void * MoveListAftLL(void *el, t_LL src); void * MoveListBefLL(void *el, t_LL src); t_LL MoveHeadFirstLL(t_LL dest, t_LL src, void *head); t_LL MoveHeadLastLL(t_LL dest, t_LL src, void *head); void * MoveHeadAftLL(void *el, t_LL src, void *head); void * MoveHeadBefLL(void *el, t_LL src, void *head); t_LL MoveTailFirstLL(t_LL dest, t_LL src, void *tail); t_LL MoveTailLastLL(t_LL dest, t_LL src, void *tail); void * MoveTailAftLL(void *el, t_LL src, void *tail); void * MoveTailBefLL(void *el, t_LL src, void *tail); void * FirstElmLL (t_LL list); void * LastElmLL (t_LL list); void * NthElmLL (t_LL list, long n); void * NextElmLL (void * p_elm); void * PrevElmLL (void * p_elm); void * RelNthElmLL (void * p_elm, long n); void * NextCElmLL (void * p_elm); void * PrevCElmLL (void * p_elm); void * RelCNthElmLL (void * p_elm, long n); void * LinkAftLL(void * curr,void * new); void * LinkBefLL(void * curr,void * new); void * UnlinkLL(void * el); void * UnlinkNeLL(void * el); void * UnlinkPrLL(void * el); int IsElmLL (void * p_elm); int IsFirstElmLL (void * p_elm); int IsLastElmLL (void * p_elm); long IndexElmLL (t_LL list, void *ind_el); void ConsistentLL(t_LL list); ForeachLL_M(list,p_elm) ForeachDownLL_M(list,p_elm) SafeForeachLL_M(list,p_elm,next_p_elm) char * FprintLL(t_LL list, FILE * file, char *b, char *control, char *a) ; char * printLL(t_LL list, char * control); char * SscanLL(t_LL list, char *string, char * control, int termination);
An instance of a list is created using either ConsLL, ConsCopyLL, InitLL or ConsPtrLL functions. It is recommended to call one of the functions at the point of declaration of a list variable; A list variable must be initialised by a call to one of the constructor functions before a list is passed to any function in the LL library.
ConsLL() creates an empty list. ConsCopyLL(src) creates a new copy of an existing list. ConsPtrLL(src) creates a list of pointers to elements stored in list 'src'. DestLL(list) destroys a list, ie. deletes all elements and frees all memory allocated for the list (ie. the memory allocated by ConsLL/ConsCopyLL/ConsPtrLL and by the 'insert element' family of functions). Memory pointed to by elements of the list is not freed. The use of InitLL() function assumes very good understanding of the implementation of the LL library and should be avoided by beginners. InitLL initializes a list similarly to ConsLL, but the head of the list is stored in a structure provided by the user (rather than dynamically allocated as in ConsLL). Lists created using InitLL must not be destroyed using DestLL, such list should only be emptied using EmptyLL.
IsEmptyLL(list) returns a non-zero value if 'list' is an empty list, 0 otherwise.
ReverseLL(list) reverses the element order in a list. ReverseLL retruns its parameter.
ApplyLL(list,function) calls function 'function' in a loop. Pointers to elements of the list are one by one passed to 'function'. The loop is terminated when either pointers to all elements were passed to the function or the function 'function' returned a non-NULL value. ApplyLL returns NULL in the former case, an the return value of 'function' if it is non-NULL. If 'function' is to be applied to all elements the user-defined 'function' must therefore always return NULL. The latter mode can be used as 'FindElement' if function 'function' returns a pointer to an element satisfying a certain condition.
SizeLL(list) returns the number of elements in the list. The complexity of the function is O(n) (ie. the size of list is established by scanning through the list).
SortLL(list,compare) sorts elements of a list according to the 'compare' function. The 'compare' function has a format identical to the comparison function of qsort(3). Two different sorting algorithms have been implemented. A fast mergesort provided by David Kastrup (MergeSortLL) and SysSortLL which builds an array of pointers to list elements and then calls the standard C function qsort(3). SortLL is mapped to MergeSortLL by a #define directive because in my tests MergeSortLL outperformed SysSortLL by a factor of two. The user can change the #define in LL.h to map SortLL to whichever sort is performing best on his machine/for his data. MergeSortLL and SysSortLL can be called directly. See examples 'exSortText' and 'exSortTime' in the EXAMPLE sections.
LookInLL(list) creates a look-up table for list 'list' that enables random access to elements. If the type of elements in the list is 'int' than the type of the look-up table is of type int **table. *table[i] returns the value of the i-th element of 'list'. The ordering reflects the position of an element at the time of LookInLL call. Sorting 'list' according to different criteria and creating a look-up table after every sort allows to order elements according to multiple criteria. It is an error to use the look-up table after any function that deletes elements from a list as any the pointer in 'table' can reference a deallocated part of memory. It is possible to use the table after any function that inserts, moves, changes value of list elements. *table[i] can be then interpreted as the value of the i-th element of list 'list' at the time of LookInLL call regardless of the fact that the element may be in a different position or a member of a different list. The memory allocated by LookInLL for the table should be freed by calling free(table).
DelElmLL, DelElmNeLL, DelElmPrLL delete an element from a list. DelElmNeLL returns a pointer to the next element, DelElmPrLL to the previous element. 'exBasic' shows typical usage of DelElmLL.
for(pElm=FirstElmLL(list);IsElmLL(pElm);pElm=NextElmLL(pElm))
The construct is used so often that the it is provided in a form of the ForeachLL_M macro. A similar macro, ForeachDownLL_M, can be used to scan all the elements starting with the last. The user must ensure that the current 'pElm' is not deleted in the body of the for loop - the p_elm=NextElmLL(pElm) would fail. Use SafeForeachLL_M in this case.
NthElmLL(list,n) returns a pointer to the n-th element of the list. 'n' can be negative. Note that the cost of the operations is proportional to 'n'; this functions should be therefore used sparingly; if random access to elements is required, use LookInLL. RelNthElmLL(p_elm,n) returns a pointer to an element with a distance (relative position) 'n' from 'p_elm'. See also the description and examples for RelCNthElmLLl). IndexElmLL(list,p_elm) returns the position (order) of 'p_elm' in 'list'.
NextCElmLL(p_elm)/PrevCElmLL(p_elm) are analogous to NextElmLL(p_elm)/PrevElmLL(p_elm), but the list is treated as circular. For a non-empty list, NextCElmLL(p_elm) returns pointer to the next elment or, if 'p_elm' is the last element of the list, pointer to the first element. Similarly, PrevCElmLL returns pointer to the previous element or, if 'p_elm' points to the first element, pointer to the last element. For a non-empty list NextCElmLL/PrevCElmLL skips the list head and always points to a genuine element and; the result need not be tested by IsElmLL. For an empty list the functions return pointer to the head.
RelCNthElmLL(p_elm,n) returns a pointer to an element at distance (relative position) 'n' from 'p_elm' treating the list as circular - the 'head' is therefore not counted. So
RelCNthElmLL(FirstElmLL(list),-1);returns pointer to the last elment. In constrast, RelNthElm(FirstElmLL(list),-1) returns pointer to the head. This is consistent with the NthElmLL and LookInLL functions, where head is accessed as 0-th element. The result of RelNthElm(FirstElmLL(list),-1) can be predicted by adding -1 to 1 (for the frist element). Zero is obtained and the corresponding element, the head, is returned.
ConsistentLL(list) runs a couple of check trying to establish whether the list is corrupted.
FprintLL(list,file,before,control,after) first writes string 'before' to 'file'. Then contents of all elements is output according to the 'control' string. Finally, the 'after' string is written to 'file'. With two exceptions, the control string is identical to the control string of the printf(3) family of functions. Because Fprintf must distinguish between double and float parameters, %lf, %lg, %le conversion were introduced for fields of type double. The %f, %g, %e conversions are used for fields of type float. The %S conversion is used for a zero-terminated string field. The %s is used for char* field (as in printf). Example usage is shown in examples 'exBasic', 'exCutPaste' and 'exPrintScan'. The format specification can contain printf(3) conversion flags, modifiers, etc. The field suppression character '*' may be used. FprintLL always returns NULL.
printLL(list,control) is identical to FprintLL(list,stdout,"",control,"\n").
SscanLL(list,string,control,termination) converts 'string' into structures defined by the control string and appends the structures to 'list'. The operation can be viewed as parsing of the string into a list of identical elements. The parsing is terminated either after converting a 'termination' number of elements (if 'termination' is positive) or after the end of 'string' was reached (if 'termination is 0). If 'termination' is equal to -1, then the first token of 'string' defines the number of tokens converted. To skip data in 'string', use a conversion with '*' suppressing the assigment. See 'exPrintScan' for details.
/*----------------- LL library example: basic functions ---------------- */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.2 exBasic.c";
#include "LL.h"
#include <stdio.h>
#include <string.h>
/*-----------------------------------------------------------------------*/
/*
This example shows HOW TO:
- create a list (ConsLL)
- insert elements into it at various positions (start, end, arbitrary)
- print out list contents (ApplyLL)
- print out list using printLL, FprintLL (see warning in LL.h!)
- sort a list (SortLL)
- iterate through a list (ForeachLL_M)
- destroy (free) a list (DestLL)
*/
/*-----------------------------------------------------------------------*/
static void * pr(void *el) /* print a string given a pointer to elem */
{ printf("%s ",*(char**)el); return NULL; }
static
int AlfComp(const void *el1, const void *el2) /* comparison for sort */
{ return strcmp(*(char * const *) el1, *(char * const *) el2); }
/*---------------------------------------------------------------------*/
int main (int argc, char ** argv)
{
t_LL list = ConsLL();
char *string1 = "s1"; /* some arbitrary strings .. */
char *string2 = "s2";
char *string3 = "s3";
fprintf(stderr,"usage: ex1 arg1 arg2 .... .... 0);
while (argc-->0){
InsLastLL(list,argv[argc]);
}
printf("---- a list has been built from the command line argu-
ments: 0);
ApplyLL(list,pr); /* printing the whole list by appling pr to all elems.*/
InsFirstLL(list,string1);
InsLastLL(list,string2);
InsBefLL(NthElmLL(list,4),string3);
printf("0-- s1,s2 and s3 inserted ; s1 first, s2 last, s3
fourth:0);
ApplyLL(list,pr);
DelElmLL(NthElmLL(list,3));
FprintLL(list,stdout,"0-- 3rd element deleted:0,"%s ","0);
/* another way to print out a list */
InsLastLL(list,string1);
InsBefLL( LastElmLL(list),string2);
printf("---- %s inserted as last, %s as
penultimate:0,string1,string2);
printLL(list,"%s "); /* yet another way to print a list */
printf("0-- size of list: %ld0, SizeLL(list));
SortLL(list, AlfComp);
printf("---- sorted alphabetically:0);
ApplyLL(list,pr);
{
char **listElem;
printf("0-- printf first char of each string: 0);
ForeachLL_M(list,listElem)
printf("%c ",(*listElem)[0]);
printf("0);
}
DestLL(list); /* clean up and quit */
return 0;
}
/*-------------- LL library example: cutting and pasting lists --------- */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.3 exCutPaste.c";
#include "LL.h"
/*-----------------------------------------------------------------------*/
/*
This example shows HOW TO:
- make a copy of a list (ConsCopyLL)
- cut and paste a part of a list (Move..)
- sort a list (SortLL)
- print a list (printLL <read the note in LL.h on printLL usage>)
*/
/*-----------------------------------------------------------------------*/
static int CompDouble (const void * p_elm1,const void * p_elm2)
{ return (* (double const *)p_elm1<= * (double const *)p_elm2) ? -1 : 1 ; }
/*-----------------------------------------------------------------------*/
int main (int argc, char ** argv)
{
double some_num [] = { 5.6, 3.9, 4.2, 6.7};
double num;
t_LL list = ConsLL(); /* create an empty list */
{ /* insert all numbers in some_num into the list */
int i;
for (i=0; i < sizeof(some_num)/sizeof(double); i++)
InsLastLL(list,some_num[i]);
}
/* add some other numbers to the end of the list */
num = 7.15; InsFirstLL(list,num);
num = 8.80; InsLastLL(list,num);
FprintLL(list,stdout,"---- initial list of
doubles:0,"%4.2lg","0);
{
t_LL copied_list = ConsCopyLL(list);
MoveListLastLL(list,copied_list);
FprintLL(list,stdout,"---- list duplicated:0,"%4.2lg","0);
DestLL(copied_list);
} /* end of copied list scope*/
SortLL(list,CompDouble);
FprintLL(list,stdout,"---- list sorted :0,"%4.2lg","0);
{ /* and Split now */
t_LL list2 = MoveTailLastLL(ConsLL(),list,NthElmLL(list,6));
printf("---- Cutting the list;0);
FprintLL(list ,stdout," Elements 1-5 (list ) :
","%4.2lg","0);
FprintLL(list2,stdout," Elements 6- (list2) :
","%4.2lg","0);
MoveListFirstLL(list,list2);
MoveHeadFirstLL(list2,list,NthElmLL(list,3));
FprintLL(list,stdout,
"---- Elems 8- (3- elems of list2) inserted at the head of
list:0,
"%4.2lg","0 );
DestLL(list2); /* destroy the list before it goes out of scope */
}
DestLL(list);
return 0;
}
/*----------------- LL library example: sorting text ------------------ */
static char sccsid[]="@(#)94/01/05 g.matas@ee.surrey.ac.uk 6.3 exSortText.c";
#include "LL.h"
#include <stdio.h> /* for printf, gets etc */
#include <string.h> /* for strcmp etc */
/*------------------ LL library example ---------------------------------
1. Read in a text file from stdin ( sort_ex <file)
2. Sort line in alphabetical order
3. print out
-----------------------------------------------------------------------*/
static int sCmp(const void * s1, const void * s2) { return strcmp(s1,s2);}
#define MAX_LINE_LENGTH 200
int main(void)
{
char buffer[MAX_LINE_LENGTH];
t_LL list = ConsLL();
fprintf(stderr,"usage: exSortText <infile >outfile0
" sorted text from stdin follows ---->");
while(fgets(buffer,MAX_LINE_LENGTH,stdin))
InsLastLLf(list,strlen(buffer)+1,buffer);
SortLL(list, sCmp);
printLL(list,"%S"); /* printing out the sorted file */
return 0;
}
/*----- LL library example: list of user-def structures ---------------- */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.5 exStruct.c";
#include "LL.h"
#include <stdio.h>
/*-----------------------------------------------------------------------*/
/*
put some numbers into a linked list
create a list of all pairs of numbers and print it out
*/
/*-----------------------------------------------------------------------*/
static void * PrintInt(void * p_elm)
{ printf("%d ",*(int*)p_elm); return NULL; }
/*-----------------------------------------------------------------------*/
int main(int argc, char ** argv)
{
t_LL list = ConsLL();
t_LL pairs = ConsLL();
int *n, *sec_num;
{ /* insert all numbers in some_num into the list */
int some_num [] = { 7, 3 , 8, 1, 19};
int i;
for (i=0; i < sizeof(some_num)/sizeof(int); i++)
InsLastLL(list,some_num[i]);
printf("---- initial list of doubles:0);
ApplyLL(list,PrintInt);
printf("0);
}
{
struct int_pair { int first; int second; } temp, *p_pair;
ForeachLL_M(list,n)
for(sec_num = NextElmLL(n); IsElmLL(sec_num); sec_num= NextElmLL(sec_num))
{
temp.first = *n;
temp.second = *sec_num;
InsLastLL(pairs,temp);
}
printf("---- All (unordered) pairs: 0);
ForeachLL_M(pairs,p_pair)
printf("%d-%d ",p_pair->first, p_pair->second);
printf("0);
DestLL(pairs);
}
DestLL(list);
return 0;
}
/*----------------- LL library example: printf/scanf use --------------- */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.2 exPrintScan.c";
#include "LL.h"
#include <stdio.h>
/*-----------------------------------------------------------------------*/
/*
Warning:
before using SscanLL, FprintLL, printLL
Read the recommendation about thier use in LL.h!
*/
/*-----------------------------------------------------------------------*/
int main(int argc, char ** argv)
{
t_LL num = ConsLL();
char * some_num_str = " 7 3 8 1 21 25 19 10 10 10";
SscanLL(num,some_num_str,"%d",0); /* get numbers as ints */
printf("testing formats:0);
FprintLL(num,stdout,"Plain : ","%d ","0);
FprintLL(num,stdout,"2digits: ","%2d ","0);
FprintLL(num,stdout,"Element_a_line :0,"%d0,"");
FprintLL(num,stdout,"Elm= - : ","%*d-","0);
printf("0);
EmptyLL(num); /* remove old elms */
SscanLL(num,some_num_str,"%d %*d",0); /* get odd order numbers as ints*/
FprintLL(num,stdout,"Odd Pos: ","%d ","0);
EmptyLL(num); /* remove old elms */
SscanLL(num,some_num_str,"%d",5); /* get first 5 numbers as ints*/
FprintLL(num,stdout,"1-5: ","%d ","0);
DestLL(num); /* clean up, destroy list */
return 0;
}
/*----------------- LL library example: writting out a list ------------ */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.2 exWrite.c";
#include "LL.h"
/*-----------------------------------------------------------------------*/
/*
1. Generate a list of doubles
2. Write it on the standard output in the .LL file format
*/
/*-----------------------------------------------------------------------*/
int main (int argc, char ** argv)
{
t_LL list = ConsLL(); /* create an empty list */
{ /* insert all numbers in some_num into the list */
int i;
double some_num [] = { 5.6, 3.9, 4.2, 6.7};
for (i=0; i < sizeof(some_num)/sizeof(double); i++)
InsLastLL(list,some_num[i]);
}
WriteLev1LL("-",list);
DestLL(list);
return 0;
}
/*----------------- LL library example: reading an LL file ------------- */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.2 exRead.c";
#include "LL.h"
/*-----------------------------------------------------------------------*/
/*
Read a .LL file from standard input.
A list containing doubles is expected
Use exWrite to generated the correct file
*/
/*-----------------------------------------------------------------------*/
int main (int argc, char ** argv)
{
t_LL list = ReadLL("-"); /* read a list from stdin */
printLL(list,"%4.2lf ");
DestLL(list);
return 0;
}
/*----------------- LL library example: sort (with timming) ------------ */
static char sccsid[]="@(#)94/01/03 g.matas@ee.surrey.ac.uk 6.4 exSortTime.c";
#include "LL.h"
#include <stdio.h> /* for printf, gets etc */
#include <stdlib.h>
#include <time.h>
/*------------------------------------------------------------------------*/
static void MarkTime(char * point)
{
static float last=0;
float curr =clock()/(float)CLOCKS_PER_SEC;
fprintf(stderr,"%6.2f %6.2f %s0,curr,curr-last,point);
last = curr;
}
/*------------------------------------------------------------------------*/
static int sCmp(const void * s1, const void * s2)
{ return *(const int*)s1 - *(const int*)s2; }
static void sort(int sortMethod, t_LL list)
{ /* sorting with timming prints */
MarkTime("sort start");
switch (sortMethod)
{
case 1: MergeSortLL(list, sCmp); break;
case 2: SysSortLL(list, sCmp); break;
default:
fprintf(stderr,"choose 1, 2, or 3 for the sorting alg.!0);
exit(1);
}
MarkTime("sort end");
printf(" check elems; 2nd: %d 999th: %d0,
*(int*)NthElmLL(list,2), *(int*)NthElmLL(list,999));
}
/*------------------ LL library example: sorting ------------------------*/
int main(int argc, char ** argv)
{
int numbers=10;
int sortMethod = 1;
int i;
t_LL list = ConsLL();
if(argc!=3)
{
fprintf(stderr,"usage: msort_time.c sorting_alg.
number_of_ints_to_sort0
" sorting_alg: 1-MergeSortLL 2-SysSortLL
(ie.qsort) 0);
exit(-1);
}
sscanf(argv[1],"%d",&sortMethod );
sscanf(argv[2],"%d",&numbers );
srand(0); /* for testing I want the random seq. not to change*/
for(i=0;i<numbers;i++)
{ /* building a list of random numbers */
int r = rand(); /* the randomness is really not that important */
InsLastLL(list,r);
}
printf("-------------------- sorting a random sequence 0);
sort(sortMethod,list);
printf("-------------------- sorting an already sorted list 0);
sort(sortMethod,list);
printf("-------------------- sorting a reversed list 0);
ReverseLL(list);
sort(sortMethod,list);
LinkAftLL(LastElmLL(list), UnlinkLL(FirstElmLL(list)));
/* unlink first and link it after last */
/* i.e. move the first element after the last */
printf("-------------------- sort an almost sorted list, first
is last0);
sort(sortMethod,list); /* sort list almost sorted (only first is last*/
ConsistentLL(list);
return 0;
}
The idea of representing a list by a circular list with a dummy node was picked form the Anasazi Linked List Utilities by Duane Morse (duane@anasaz). The MergeSort code was kindly provided by David Kastrup(dak@pool.informatik.rwth-aachen.de). The design of this library was influenced by numerous discussion with Radek Marik (r.marik@ee.surrey.ac.uk).