LL(3) LL(3)
16 June 1992
NAME
LL - a double linked list library, ConsLL, ConsCopyLL, ConsPtrLL,
DestLL , EmptyLL, IsEmptyLL, ApplyLL, SortLL, SizeLL, LookInLL,
FprintLL, SprintLL, SscanLL, InsBefLL, InsAftLL, InsFirstLL,
InsLastLL, InsBefLLf, InsAftLLf, InsFirstLLf, InsLastLLf,
MoveListFirstLL, MoveListLastLL, MoveListAftLL, MoveListBefLL,
MoveHeadFirstLL, MoveHeadLastLL, MoveHeadAftLL, MoveHeadBefLL,
MoveTailFirstLL, MoveTailLastLL, MoveTailAftLL, MoveTailBefLL,
FirstElmLL, LastElmLL, NthElmLL, NextElmLL, PrevElmLL, RelNthElmLL,
DelElmLL, IsElmLL, IsFirstElmLL, IsLastElmLL, IndexElmLL, ForeachLL_M,
ForeachDownLL_M, SafeForeachLL_M
SYNOPSIS
#include ''LL.h''
t_LL ConsLL ();
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)
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);
char * FprintLL(t_LL list, FILE * file, char *b, char *control, char *a) ;
char * printLL(t_LL list, char * control);
char * SprintLL(t_LL list, char * str , char *b, char *control, char *a) ;
char * SscanLL(t_LL list, char *string, char * control, int termination);
#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);
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);
- 1 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
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 * 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);
ForeachLL_M(list,p_elm)
ForeachDownLL_M(list,p_elm)
SafeForeachLL_M(list,p_elm,next_p_elm)
DESCRIPTION
List construction and destruction
LL is double-linked list handler. Variables of any type can be stored
in a LL list. Individual elements of a list may be of different types.
Lists of lists of .. can be created. An instance of a list is created
using either ConsLL, ConsCopyLL or ConsPtrLL functions. It is
recommended to call one of these functions at the point of declaration
of a list variable; result of one of the constructor functions must
be assigned to list 'list' before 'list' is passed to any other
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 'list'. It should be called at the point where
'list' goes out of scope.
Basic functions on lists
EmptyLL(list) deletes all elements from list 'list'. EmptyLL returns
its parameter - an empty list 'list'. IsEmptyLL(list) returns a non-
zero value if 'list' is an empty list, 0 otherwise.
ApplyLL(list,function) calls function 'function' in a loop. Pointers
to elements in the list are one by one passed as an argument to
'function'. The loop is terminated when either all pointers to
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. SortLL(list,compare) sort elements in a list
- 2 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
according to the compare function. The compare function has an
identical format as the function required by qsort(3). SortLL builds
an array of references and uses qsort(3). 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 to reference a
deallocated part of memory. It is possible to use the table after any
other 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).
Input/Output functions
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). EXAMPLE2 gives an example usage. 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").
SprintLL(list,str,before,control,after) writes its output to string
'str', otherwise it is identical to FprintLL. User must make sure that
'str' is large enough to hold the output string. If NULL is passed
instead of 'str', a large internal buffer is used instead. SprintLL
returns 'str' or a pointer to the internal buffer if 'str' was NULL.
The buffer contents is overwritten after a next call to SprintLL.
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 EXAMPLE3 for
- 3 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
details.
Inserting and Deleting elements
Macros InsBefLL, InsAftLL, InsFirstLL, InsLastLL and functions
InsBefLLf, InsAftLLf, InsFirstLLf, InsLastLLf allow user to insert
data of any type into a list. After InsFirstLL(f)/InsLastLL(f), the
new element will become the first/last element of a list. Using
InsAftLL(f)/InsBefLL(f), data can be inserted in an arbitrary place in
a list after/before a given element. The functions (as opposed to
macros) must be used when size of the of the inserted object is not
known at compilation time (for instance in the case of a zero-
terminated string). Insert functions creat a new element (element =
stored object (data) + neccessary overhead (links etc.)) by allocating
memory and copying the object in the element. DelElmLL, DelElmNeLL,
DelElmPrLL delete an element from a list. DelElmNeLL returns a pointer
to the next element, DelElmPrLL to the previous element. See
EXAMPLE4.
Moving Strings and Substrings
The Move family of functions can be used to cut and paste parts of
strings. All Move functions have the same structure:
MoveSomethingSomewhereLL. The structure MoveSomethingSomewhereLL is
similar to the naming system of insert functions (eg. InsLastElmLL).
MoveList___LL moves the whole source list (ie. the src list becomes
empty) somewhere (First,Last,Aft(er) element, Bef(ore)) into the
destination list. The Head and Tail functions are analogous, but just
Head (all elements up to (not including) the 'head' one) or Tail(all
elements from 'tail'(including) to end) is moved. The including/not
including choice was made to preserve Head+Tail=List.
Getting a particular element
FirstElmLL(list)/LastElmLL(list) return a pointer to the first element
in 'list'. NextElmLL(p_elm)/PrevElmLL(p_elm) return a pointer to the
next/previous element in 'list'. To access all elements in a list the
following construct can be used: for(p_elm=FirstElmLL(list);
IsElmLL(p_elm); p_elm=NextElmLL(p_elm)) The construct is used so often
that the LL package provides it 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 'p_elm'
is not deleted in the body of the for loop - the
p_elm=NextElmLL(p_elm) 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'. IndexElmLL(list,p_elm) returns
the position (order) of 'p_elm' in 'list'.
Miscellaneous function
IsElmLL(p_elm) tests for the end of a list. IsFirstElmLL/IsLastElmLL
- 4 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
test for the first and last element of the list.
EXAMPLE1 - ConsLL, DestLL, ApplyLL, SortLL, LookInLL, InsLastLL usage
/*----------------------------------------------------------------------*/
#include "LL.h"
#include <stdio.h>
int cmp(void *n1, void *n2) /* comparison function for SortLL */
{
if ( *(int*)n1 > *(int*)n2) return 1;
if ( *(int*)n1 < *(int*)n2) return -1;
return 0;
}
void *negate(void *n) /* function called by ApplyLL */
{
*(int*)n=-*(int*)n;
return NULL; /* do it for all elements */
}
int main(int argc, char ** argv)
{
t_LL num = ConsLL();
int **look_tab1, **look_tab_s, **look_tab_n;
int some_num [] = { 7, 3 , 8, 1, 19};
{ /* insert all numbers in some_num into the list */
int i;
printf("list: ");
for (i=0; i < sizeof(some_num)/sizeof(int); i++){
InsLastLL(num,some_num[i]);
printf("%d ",some_num[i]);
}
printf("0);
}
look_tab1 = LookInLL(num); /* accessing some random elements */
printf("start: 3rd and 4th : %d %d0, *look_tab1[3],*look_tab1[4]);
SortLL(num,cmp);
look_tab_s = LookInLL(num);
printf("original: 3rd and 4th : %d %d0, *look_tab1[3],*look_tab1[4]);
printf("sorted: 3rd and 4th : %d %d0, *look_tab_s[3],*look_tab_s[4]);
ApplyLL(num,negate);
SortLL(num,cmp);
look_tab_n = LookInLL(num);
printf("original: 3rd and 4th : %d %d0, *look_tab1[3], *look_tab1[4]);
printf("sorted: 3rd and 4th : %d %d0, *look_tab_s[3],*look_tab_s[4]);
printf("neg-sort: 3rd and 4th : %d %d0, *look_tab_n[3],*look_tab_n[4]);
- 5 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
DestLL(num); /* clean up, destroy list */
free(look_tab1);
free(look_tab_s);
free(look_tab_n);
return 0;
}
/*--------------------------------------------------------------------*/
EXAMPLE2 - FprintLL, ConsLL, DestLL, InsLastLL usage
/*--------------------------------------------------------------------*/
#include "LL.h"
#include <stdio.h>
int main(int argc, char ** argv)
{
t_LL num = ConsLL();
int some_num [] = { 7, 3 , 8, 1, 19};
{ /* insert all numbers in some_num into the list */
int i;
for (i=0; i < sizeof(some_num)/sizeof(int); i++)
InsLastLL(num,some_num[i]);
}
/* print the list of integers in various formats */
FprintLL(num,stdout,"Plain : ","%d ","0);
FprintLL(num,stdout,"2digits: ","%2d ","0);
FprintLL(num,stdout,"Element_a_line :0,"%d0,"0);
FprintLL(num,stdout,"Elm= - : ","%*d-","0);
DestLL(num); /* clean up, destroy list */
return 0;
}
/*--------------------------------------------------------------------*/
EXAMPLE3 - SscanLL, FprintLL, ConsLL, DestLL, EmptyLL usage
/*--------------------------------------------------------------------*/
#include "LL.h"
#include <stdio.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 all numbers */
FprintLL(num,stdout,"List: ","%d ","0);
EmptyLL(num); /* remove old elms */
- 6 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
SscanLL(num,some_num_str,"%d %*d",0); /* get odd order numbers*/
FprintLL(num,stdout,"Odd Pos: ","%d ","0);
EmptyLL(num); /* remove old elms */
SscanLL(num,some_num_str,"%d",5); /* get first 5 numbers */
FprintLL(num,stdout,"1-5: ","%d ","0);
EmptyLL(num); /* remove old elms */
SscanLL(num,some_num_str,"%d",-1); /* convert according to 1st num*/
FprintLL(num,stdout,"List: ","%d ","0);
DestLL(num); /* clean up, destroy list */
return 0;
}
/*--------------------------------------------------------------------*/
EXAMPLE4 - Inserting and Deleting Elms
/*----------------------------------------------------------------------*/
#include "LL.h"
#include <stdio.h>
#include <string.h> /* for strlen */
int main(int argc, char ** argv)
{
t_LL list = ConsLL();
char * strings[] = {"S1","S2","S3","forth"};
float numbs[] = {1.2,3.4,5.6};
float * numb;
numb = InsFirstLL(list,numbs[0]); /*remember ptr to the 1st insert. elm*/
InsLastLL(list,numbs[1]);
InsLastLL(list,numbs[2]);
InsAftLL(numb,numbs[2]); /* numb[2] is Last and second */
FprintLL(list,stdout,"List : ","%3.1f ","0);
DelElmLL(numb); /* delete one (first) element */
FprintLL(list,stdout,"List : ","%3.1f ","0);
for(numb=FirstElmLL(list); IsElmLL(numb); numb=DelElmNeLL(numb))
; /* empty the list*/
InsFirstLLf(list,strlen(strings[1])+1,strings[1]); /* + 1 for term. zero */
InsFirstLLf(list,strlen(strings[2])+1,strings[2]);
FprintLL(list,stdout,"List :0,"%S0,"0);
DestLL(list); /* clean up, destroy list */
return 0;
}
/*----------------------------------------------------------------------*/
- 7 - Formatted: April 25, 2024
LL(3) LL(3)
16 June 1992
SEE ALSO
qsort(3)
BUGS
The input/output family of functions has not been tested for all
possible format strings. Moreover, these functions are not portable.
No padding inside structures (for alignment) is assumed. I recommend
to use these functions for debugging prints only.
AUTHOR
George Matas, University of Surrey; g.matas@ee.surrey.ac.uk. Thanks to
Duane Morse for the idea of representing an empty list by a circular
list with a dummy node and to Radek Marik and Radim Sara for numerous
discussions on list implementation.
- 8 - Formatted: April 25, 2024
