view release on metacpan or  search on metacpan

lib/Image/Leptonica/Func/list.pm  view on Meta::CPAN

=head1 C<list.c>

   list.c

      Inserting and removing elements

           void      listDestroy()
           DLLIST   *listAddToHead()
           l_int32   listAddToTail()
           l_int32   listInsertBefore()
           l_int32   listInsertAfter()
           void     *listRemoveElement()
           void     *listRemoveFromHead()
           void     *listRemoveFromTail()

      Other list operations

           DLLIST   *listFindElement()
           DLLIST   *listFindTail()
           l_int32   listGetCount()
           l_int32   listReverse()
           DLLIST   *listJoin()

      Lists are much harder to handle than arrays.  There is
      more overhead for the programmer, both cognitive and
      codewise, and more likelihood that an error can be made.
      For that reason, lists should only be used when it is
      inefficient to use arrays, such as when elements are
      routinely inserted or deleted from inside arrays whose
      average size is greater than about 10.

      A list of data structures can be implemented in a number
      of ways.  The two most popular are:

         (1) The list can be composed of a linked list of
             pointer cells ("cons cells"), where the data structures
             are hung off the cells.  This is more difficult
             to use because you have to keep track of both
             your hanging data and the cell structures.
             It requires 3 pointers for every data structure
             that is put in a list.  There is no problem
             cloning (using reference counts) for structures that
             are put in such a list.  We implement lists by this
             method here.

         (2) The list pointers can be inserted directly into
             the data structures.  This is easy to implement
             and easier to use, but it adds 2 ptrs of overhead
             to every data structure in which the ptrs are embedded.
             It also requires special care not to put the ptrs
             in any data that is cloned with a reference count;
             else your lists will break.

      Writing C code that uses list pointers explicitly to make
      and alter lists is difficult and prone to error.
      Consequently, a generic list utility that handles lists
      of arbitrary objects and doesn't force the programmer to
      touch the "next" and "prev" pointers, is quite useful.
      Such functions are provided here.   However, the usual
      situation requires traversing a list and applying some
      function to one or more of the list elements.  Macros
      for traversing the list are, in general, necessary, to
      achieve the goal of invisibly handling all "next" and "prev"
      pointers in generic lists.  We provide macros for
      traversing a list in both forward and reverse directions.

      Because of the typing in C, implementation of a general
      list utility requires casting.  If macros are used, the
      casting can be done implicitly; otherwise, using functions,
      some of the casts must be explicit.  Fortunately, this
      can be implemented with void* so the programmer using
      the library will not have to make any casts!  (Unless you
      compile with g++, in which case the rules on implicit
      conversion are more strict.)

      For example, to add an arbitrary data structure foo to the
      tail of a list, use
             listAddToTail(&head, &tail, pfoo);
      where head and tail are list cell ptrs and pfoo is
      a pointer to the foo object.
      And to remove an arbitrary data structure foo from a
      list, when you know the list cell element it is hanging from,
      use
             pfoo = listRemoveElement(&head, elem)
      where head and elem are list cell ptrs and pfoo is a pointer
      to the foo object.  No casts are required for foo in
      either direction in ANSI C.  (However, casts are
      required for ANSI C++).

      We use lists that are composed of doubly-linked
      cells with data structures hanging off the cells.
      We use doubly-linked cells to simplify insertion
      and deletion, and to allow operations to proceed in either
      direction along the list.  With doubly-linked lists,
      it is tempting to make them circular, by setting head->prev
      to the tail of the list and tail->next to the head.
      The circular list costs nothing extra in storage, and
      allows operations to proceed from either end of the list
      with equal speed.  However, the circular link adds
      cognitive overhead for the application programmer in
      general, and it greatly complicates list traversal when
      arbitrary list elements can be added or removed as you
      move through.  It can be done, but in the spirit of
      simplicity, we avoid the temptation.  The price to be paid
      is the extra cost to find the tail of a list -- a full
      traversal -- before the tail can be used.  This is a
      cheap price to pay to avoid major headaches and buggy code.

      When you are only applying some function to each element
      in a list, you can go either forwards or backwards.
      To run through a list forwards, use:

          for (elem = head; elem; elem = nextelem) {
              nextelem = elem->next;   (in case we destroy elem)
              <do something with elem->data>
          }

      To run through a list backwards, find the tail and use:

          for (elem = tail; elem; elem = prevelem) {
 #              prevelem = elem->prev;  (in case we destroy elem)