packages icon



 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021






 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:  January 26, 2021