Leptonica  1.82.0
Image processing and image analysis suite
list.c File Reference
#include <string.h>
#include "allheaders.h"

Go to the source code of this file.

Functions

void listDestroy (DLLIST **phead)
 
l_ok listAddToHead (DLLIST **phead, void *data)
 
l_ok listAddToTail (DLLIST **phead, DLLIST **ptail, void *data)
 
l_ok listInsertBefore (DLLIST **phead, DLLIST *elem, void *data)
 
l_ok listInsertAfter (DLLIST **phead, DLLIST *elem, void *data)
 
void * listRemoveElement (DLLIST **phead, DLLIST *elem)
 
void * listRemoveFromHead (DLLIST **phead)
 
void * listRemoveFromTail (DLLIST **phead, DLLIST **ptail)
 
DLLISTlistFindElement (DLLIST *head, void *data)
 
DLLISTlistFindTail (DLLIST *head)
 
l_int32 listGetCount (DLLIST *head)
 
l_ok listReverse (DLLIST **phead)
 
l_ok listJoin (DLLIST **phead1, DLLIST **phead2)
 

Detailed Description


       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) <do something with elem->data> } Even though these patterns are very simple, they are so common that we've provided macros for them in list.h. Using the macros, this becomes:
<do something with elem->data>
<do something with elem->data>
#define L_END_LIST
Definition: list.h:87
#define L_BEGIN_LIST_FORWARD(head, element)
Definition: list.h:71
#define L_BEGIN_LIST_REVERSE(tail, element)
Definition: list.h:79
Note again that with macros, the application programmer does not need to refer explicitly to next and prev fields. Also, in the reverse case, note that we do not explicitly show the head of the list. However, the head of the list is always in scope, and functions can be called within the iterator that change the head. Some special cases are simpler. For example, when removing all items from the head of the list, you can use
while (head) {
obj = listRemoveFromHead(&head);
<do something with obj>
}
void * listRemoveFromHead(DLLIST **phead)
listRemoveFromHead()
Definition: list.c:560
Removing successive elements from the tail is equally simple:
while (tail) {
obj = listRemoveFromTail(&head, &tail);
<do something with obj>
}
void * listRemoveFromTail(DLLIST **phead, DLLIST **ptail)
listRemoveFromTail()
Definition: list.c:608
When removing an arbitrary element from a list, use
obj = listRemoveElement(&head, elem);
void * listRemoveElement(DLLIST **phead, DLLIST *elem)
listRemoveElement()
Definition: list.c:508
All the listRemove*() functions hand you the object, destroy the list cell to which it was attached, and reset the list pointers if necessary. Several other list operations, that do not involve inserting or removing objects, are also provided. The function listFindElement() locates a list pointer by matching the object hanging on it to a given object. The function listFindTail() gets a handle to the tail list ptr, allowing backwards traversals of the list. listGetCount() gives the number of elements in a list. Functions that reverse a list and concatenate two lists are also provided. These functions can be modified for efficiency in the situation where there is a large amount of creation and destruction of list cells. If millions of cells are made and destroyed, but a relatively small number are around at any time, the list cells can be stored for later re-use in a stack (see the generic stack functions in stack.c).

Definition in file list.c.

Function Documentation

◆ listAddToHead()

l_ok listAddToHead ( DLLIST **  phead,
void *  data 
)

listAddToHead()

Parameters
[in,out]phead[optional] input head
[in]datavoid* ptr, to be added
Returns
0 if OK; 1 on error
Notes:
     (1) This makes a new cell, attaches data, and adds the
         cell to the head of the list.
     (2) When consing from NULL, be sure to initialize head to NULL
         before calling this function.

Definition at line 279 of file list.c.

Referenced by listReverse().

◆ listAddToTail()

l_ok listAddToTail ( DLLIST **  phead,
DLLIST **  ptail,
void *  data 
)

listAddToTail()

Parameters
[in,out]phead[may be updated], can be NULL
[in,out]ptail[updated], can be NULL
[in]datavoid* ptr, to be hung on tail cons cell
Returns
0 if OK; 1 on error
Notes:
     (1) This makes a new cell, attaches data, and adds the
         cell to the tail of the list.
     (2) &head is input to allow the list to be "cons'd" up from NULL.
     (3) &tail is input to allow the tail to be updated
         for efficient sequential operation with this function.
     (4) We assume that if *phead and/or *ptail are not NULL,
         then they are valid addresses.  Therefore:
          (a) when consing from NULL, be sure to initialize both
              head and tail to NULL.
          (b) when tail == NULL for an existing list, the tail
              will be found and updated.

Definition at line 331 of file list.c.

References listFindTail().

Referenced by listJoin().

◆ listDestroy()

void listDestroy ( DLLIST **  phead)

listDestroy()

Parameters
[in,out]pheadhead of list; will be set to null before returning
Returns
void
Notes:
     (1) This only destroys the cons cells.  Before destroying
         the list, it is necessary to remove all data and set the
         data pointers in each cons cell to NULL.
     (2) listDestroy() will give a warning message for each data
         ptr that is not NULL.

Definition at line 239 of file list.c.

◆ listFindElement()

DLLIST* listFindElement ( DLLIST head,
void *  data 
)

listFindElement()

Parameters
[in]headlist head
[in]datavoid* address, to be searched for
Returns
cell the containing cell, or NULL if not found or on error
Notes:
     (1) This returns a ptr to the cell, which is still embedded in
         the list.
     (2) This handle and the attached data have not been copied or
         reference counted, so they must not be destroyed.  This
         violates our basic rule that every handle returned from a
         function is owned by that function and must be destroyed,
         but if rules aren't there to be broken, why have them?

Definition at line 662 of file list.c.

◆ listFindTail()

DLLIST* listFindTail ( DLLIST head)

listFindTail()

Parameters
[in]head
Returns
tail, or NULL on error

Definition at line 690 of file list.c.

Referenced by listAddToTail(), listJoin(), and listRemoveFromTail().

◆ listGetCount()

l_int32 listGetCount ( DLLIST head)

listGetCount()

Parameters
[in]headof list
Returns
number of elements; 0 if no list or on error

Definition at line 715 of file list.c.

◆ listInsertAfter()

l_ok listInsertAfter ( DLLIST **  phead,
DLLIST elem,
void *  data 
)

listInsertAfter()

Parameters
[in,out]phead[optional] input head
[in]elemlist element to be inserted after; must be NULL if head is NULL
[in]datavoid* ptr, to be added
Returns
0 if OK; 1 on error
Notes:
     (1) This can be called on a null list, in which case both
         head and elem must be null.  The head is included
         in the call to allow "consing" up from NULL.
     (2) If you are searching through a list, looking for a condition
         to add an element, you can do something like this:
<identify an elem to insert after>
listInsertAfter(&head, elem, data);
l_ok listInsertAfter(DLLIST **phead, DLLIST *elem, void *data)
listInsertAfter()
Definition: list.c:455

Definition at line 455 of file list.c.

◆ listInsertBefore()

l_ok listInsertBefore ( DLLIST **  phead,
DLLIST elem,
void *  data 
)

listInsertBefore()

Parameters
[in,out]phead[optional] input head
[in]elemlist element to be inserted in front of; must be NULL if head is NULL
[in]datavoid* address, to be added
Returns
0 if OK; 1 on error
Notes:
     (1) This can be called on a null list, in which case both
         head and elem must be null.
     (2) If you are searching through a list, looking for a condition
         to add an element, you can do something like this:
<identify an elem to insert before>
listInsertBefore(&head, elem, data);
l_ok listInsertBefore(DLLIST **phead, DLLIST *elem, void *data)
listInsertBefore()
Definition: list.c:392

Definition at line 392 of file list.c.

◆ listJoin()

l_ok listJoin ( DLLIST **  phead1,
DLLIST **  phead2 
)

listJoin()

Parameters
[in,out]phead1head of first list; may be changed
[in,out]phead2head of second list; to be nulled
Returns
0 if OK, 1 on error
Notes:
     (1) The concatenated list is returned with head1 as the new head.
     (2) Both input ptrs must exist, though either can have the value NULL.

Definition at line 782 of file list.c.

References listAddToTail(), listFindTail(), and listRemoveFromHead().

◆ listRemoveElement()

void* listRemoveElement ( DLLIST **  phead,
DLLIST elem 
)

listRemoveElement()

Parameters
[in,out]pheadinput head; can be changed
[in]elemlist element to be removed
Returns
data void* struct on cell
Notes:
     (1) in ANSI C, it is not necessary to cast return to actual type; e.g.,
            pix = listRemoveElement(&head, elem);
         but in ANSI C++, it is necessary to do the cast:
            pix = (Pix *)listRemoveElement(&head, elem);

Definition at line 508 of file list.c.

◆ listRemoveFromHead()

void* listRemoveFromHead ( DLLIST **  phead)

listRemoveFromHead()

Parameters
[in,out]pheadhead of list; updated
Returns
data void* struct on cell, or NULL on error
Notes:
     (1) in ANSI C, it is not necessary to cast return to actual type; e.g.,
           pix = listRemoveFromHead(&head);
         but in ANSI C++, it is necessary to do the cast; e.g.,
           pix = (Pix *)listRemoveFromHead(&head);

Definition at line 560 of file list.c.

Referenced by listJoin(), and listReverse().

◆ listRemoveFromTail()

void* listRemoveFromTail ( DLLIST **  phead,
DLLIST **  ptail 
)

listRemoveFromTail()

Parameters
[in,out]pheadlist head must NOT be NULL; may be changed
[in,out]ptaillist tail may be NULL; always updated
Returns
data void* struct on cell or NULL on error
Notes:
     (1) We include &head so that it can be set to NULL if
         if the only element in the list is removed.
     (2) The function is relying on the fact that if tail is
         not NULL, then is is a valid address.  You can use
         this function with tail == NULL for an existing list, in
         which case  the tail is found and updated, and the
         removed element is returned.
     (3) In ANSI C, it is not necessary to cast return to actual type; e.g.,
           pix = listRemoveFromTail(&head, &tail);
         but in ANSI C++, it is necessary to do the cast; e.g.,
           pix = (Pix *)listRemoveFromTail(&head, &tail);

Definition at line 608 of file list.c.

References listFindTail().

◆ listReverse()

l_ok listReverse ( DLLIST **  phead)

listReverse()

Parameters
[in,out]pheadlist head; may be changed
Returns
0 if OK, 1 on error
Notes:
     (1) This reverses the list in-place.

Definition at line 745 of file list.c.

References listAddToHead(), and listRemoveFromHead().