/*====================================================================*
- Copyright (C) 2001 Leptonica. All rights reserved.
- This software is distributed in the hope that it will be
- useful, but with NO WARRANTY OF ANY KIND.
- No author or distributor accepts responsibility to anyone for the
- consequences of using this software, or for whether it serves any
- particular purpose or works at all, unless he or she says so in
- writing. Everyone is granted permission to copy, modify and
- redistribute this source code, for commercial or non-commercial
- purposes, with the following restrictions: (1) the origin of this
- source code must not be misrepresented; (2) modified versions must
- be plainly marked as such; and (3) this notice may not be removed
- or altered from any source or modified source distribution.
*====================================================================*/
/*
* 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)
* <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:
*
* L_BEGIN_LIST_FORWARD(head, elem)
* <do something with elem->data>
* L_END_LIST
*
* L_BEGIN_LIST_REVERSE(tail, elem)
* <do something with elem->data>
* L_END_LIST
*
* 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>
* }
*
* Removing successive elements from the tail is equally simple:
*
* while (tail) {
* obj = listRemoveFromTail(&head, &tail);
* <do something with obj>
* }
*
* When removing an arbitrary element from a list, use
*
* obj = listRemoveElement(&head, elem);
*
* 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).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "allheaders.h"
/*---------------------------------------------------------------------*
* Inserting and removing elements *
*---------------------------------------------------------------------*/
/*!
* listDestroy()
*
* Input: &head (<to be nulled> head of list)
* Return: 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.
*/
void
listDestroy(DLLIST **phead)
{
DLLIST *elem, *next, *head;
PROCNAME("listDestroy");
if (phead == NULL) {
L_WARNING("ptr address is null!", procName);
return;
}
if ((head = *phead) == NULL)
return;
for (elem = head; elem; elem = next) {
if (elem->data)
L_WARNING("list data ptr is not null", procName);
next = elem->next;
FREE(elem);
}
*phead = NULL;
return;
}
/*!
* listAddToHead()
*
* Input: &head (<optional> input head)
* data (void* ptr, to be added)
* Return: 0 if OK; 1 on error
*
* Notes:
* (1) This makes a new cell, attaches the 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.
*/
l_int32
listAddToHead(DLLIST **phead,
void *data)
{
DLLIST *cell, *head;
PROCNAME("listAddToHead");
if (!phead)
return ERROR_INT("&head not defined", procName, 1);
head = *phead;
if (!data)
return ERROR_INT("data not defined", procName, 1);
if ((cell = (DLLIST *)CALLOC(1, sizeof(DLLIST))) == NULL)
return ERROR_INT("cell not made", procName, 1);
cell->data = data;
if (!head) { /* start the list; initialize the ptrs */
cell->prev = NULL;
cell->next = NULL;
}
else {
cell->prev = NULL;
cell->next = head;
head->prev = cell;
}
*phead = cell;
return 0;
}
/*!
* listAddToTail()
*
* Input: &head (<may be updated>, head can be null)
* &tail (<updated>, tail can be null)
* data (void* ptr, to be hung on tail cons cell)
* Return: 0 if OK; 1 on error
*
* Notes:
* (1) This makes a new cell, attaches the 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.
*/
l_int32
listAddToTail(DLLIST **phead,
DLLIST **ptail,
void *data)
{
DLLIST *cell, *head, *tail;
PROCNAME("listAddToTail");
if (!phead)
return ERROR_INT("&head not defined", procName, 1);
head = *phead;
if (!ptail)
return ERROR_INT("&tail not defined", procName, 1);
if (!data)
return ERROR_INT("data not defined", procName, 1);
if ((cell = (DLLIST *)CALLOC(1, sizeof(DLLIST))) == NULL)
return ERROR_INT("cell not made", procName, 1);
cell->data = data;
if (!head) { /* Start the list and initialize the ptrs. *ptail
* should also have been initialized to NULL */
cell->prev = NULL;
cell->next = NULL;
*phead = cell;
*ptail = cell;
}
else {
if ((tail = *ptail) == NULL)
tail = listFindTail(head);
cell->prev = tail;
cell->next = NULL;
tail->next = cell;
*ptail = cell;
}
return 0;
}
/*!
* listInsertBefore()
*
* Input: &head (<optional> input head)
* elem (list element to be inserted in front of;
* must be null if head is null)
* data (void* address, to be added)
* Return: 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:
* L_BEGIN_LIST_FORWARD(head, elem)
* <identify an elem to insert before>
* listInsertBefore(&head, elem, data);
* L_END_LIST
*
*/
l_int32
listInsertBefore(DLLIST **phead,
DLLIST *elem,
void *data)
{
DLLIST *cell, *head;
PROCNAME("listInsertBefore");
if (!phead)
return ERROR_INT("&head not defined", procName, 1);
head = *phead;
if (!data)
return ERROR_INT("data not defined", procName, 1);
if ((!head && elem) || (head && !elem))
return ERROR_INT("head and elem not consistent", procName, 1);
/* New cell to insert */
if ((cell = (DLLIST *)CALLOC(1, sizeof(DLLIST))) == NULL)
return ERROR_INT("cell not made", procName, 1);
cell->data = data;
if (!head) { /* start the list; initialize the ptrs */
cell->prev = NULL;
cell->next = NULL;
*phead = cell;
}
else if (head == elem) { /* insert before head of list */
cell->prev = NULL;
cell->next = head;
head->prev = cell;
*phead = cell;
}
else { /* insert before elem and after head of list */
cell->prev = elem->prev;
cell->next = elem;
elem->prev->next = cell;
elem->prev = cell;
}
return 0;
}
/*!
* listInsertAfter()
*
* Input: &head (<optional> input head)
* elem (list element to be inserted after;
* must be null if head is null)
* data (void* ptr, to be added)
* Return: 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:
* L_BEGIN_LIST_FORWARD(head, elem)
* <identify an elem to insert after>
* listInsertAfter(&head, elem, data);
* L_END_LIST
*/
l_int32
listInsertAfter(DLLIST **phead,
DLLIST *elem,
void *data)
{
DLLIST *cell, *head;
PROCNAME("listInsertAfter");
if (!phead)
return ERROR_INT("&head not defined", procName, 1);
head = *phead;
if (!data)
return ERROR_INT("data not defined", procName, 1);
if ((!head && elem) || (head && !elem))
return ERROR_INT("head and elem not consistent", procName, 1);
/* New cell to insert */
if ((cell = (DLLIST *)CALLOC(1, sizeof(DLLIST))) == NULL)
return ERROR_INT("cell not made", procName, 1);
cell->data = data;
if (!head) { /* start the list; initialize the ptrs */
cell->prev = NULL;
cell->next = NULL;
*phead = cell;
}
else if (elem->next == NULL) { /* insert after last */
cell->prev = elem;
cell->next = NULL;
elem->next = cell;
}
else { /* insert after elem and before the end */
cell->prev = elem;
cell->next = elem->next;
elem->next->prev = cell;
elem->next = cell;
}
return 0;
}
/*!
* listRemoveElement()
*
* Input: &head (<can be changed> input head)
* elem (list element to be removed)
* Return: 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);
*/
void *
listRemoveElement(DLLIST **phead,
DLLIST *elem)
{
void *data;
DLLIST *head;
PROCNAME("listRemoveElement");
if (!phead)
return (void *)ERROR_PTR("&head not defined", procName, NULL);
head = *phead;
if (!head)
return (void *)ERROR_PTR("head not defined", procName, NULL);
if (!elem)
return (void *)ERROR_PTR("elem not defined", procName, NULL);
data = elem->data;
if (head->next == NULL) { /* only one */
if (elem != head)
return (void *)ERROR_PTR("elem must be head", procName, NULL);
*phead = NULL;
}
else if (head == elem) { /* first one */
elem->next->prev = NULL;
*phead = elem->next;
}
else if (elem->next == NULL) { /* last one */
elem->prev->next = NULL;
}
else { /* neither the first nor the last one */
elem->next->prev = elem->prev;
elem->prev->next = elem->next;
}
FREE(elem);
return data;
}
/*!
* listRemoveFromHead()
*
* Input: &head (<to be updated> head of list)
* Return: 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);
*/
void *
listRemoveFromHead(DLLIST **phead)
{
DLLIST *head;
void *data;
PROCNAME("listRemoveFromHead");
if (!phead)
return (void *)ERROR_PTR("&head not defined", procName, NULL);
if ((head = *phead) == NULL)
return (void *)ERROR_PTR("head not defined", procName, NULL);
if (head->next == NULL) /* only one */
*phead = NULL;
else {
head->next->prev = NULL;
*phead = head->next;
}
data = head->data;
FREE(head);
return data;
}
/*!
* listRemoveFromTail()
*
* Input: &head (<may be changed>, head must NOT be null)
* &tail (<always updated>, tail may be null)
* Return: 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);
*/
void *
listRemoveFromTail(DLLIST **phead,
DLLIST **ptail)
{
DLLIST *head, *tail;
void *data;
PROCNAME("listRemoveFromTail");
if (!phead)
return (void *)ERROR_PTR("&head not defined", procName, NULL);
if ((head = *phead) == NULL)
return (void *)ERROR_PTR("head not defined", procName, NULL);
if (!ptail)
return (void *)ERROR_PTR("&tail not defined", procName, NULL);
if ((tail = *ptail) == NULL)
tail = listFindTail(head);
if (head->next == NULL) { /* only one */
*phead = NULL;
*ptail = NULL;
}
else {
tail->prev->next = NULL;
*ptail = tail->prev;
}
data = tail->data;
FREE(tail);
return data;
}
/*---------------------------------------------------------------------*
* Other list operations *
*---------------------------------------------------------------------*/
/*!
* listFindElement()
*
* Input: head (list head)
* data (void* address, to be searched for)
* Return: 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?
*/
DLLIST *
listFindElement(DLLIST *head,
void *data)
{
DLLIST *cell;
PROCNAME("listFindElement");
if (!head)
return (DLLIST *)ERROR_PTR("head not defined", procName, NULL);
if (!data)
return (DLLIST *)ERROR_PTR("data not defined", procName, NULL);
for (cell = head; cell; cell = cell->next) {
if (cell->data == data)
return cell;
}
return NULL;
}
/*!
* listFindTail()
*
* Input: head
* Return: tail, or null on error
*/
DLLIST *
listFindTail(DLLIST *head)
{
DLLIST *cell;
PROCNAME("listFindTail");
if (!head)
return (DLLIST *)ERROR_PTR("head not defined", procName, NULL);
for (cell = head; cell; cell = cell->next) {
if (cell->next == NULL)
return cell;
}
return (DLLIST *)ERROR_PTR("tail not found !!", procName, NULL);
}
/*!
* listGetCount()
*
* Input: head (of list)
* Return: number of elements; 0 if no list or on error
*/
l_int32
listGetCount(DLLIST *head)
{
l_int32 count;
DLLIST *elem;
PROCNAME("listGetCount");
if (!head)
return ERROR_INT("head not defined", procName, 0);
count = 0;
for (elem = head; elem; elem = elem->next)
count++;
return count;
}
/*!
* listReverse()
*
* Input: &head (<may be changed> list head)
* Return: 0 if OK, 1 on error
*
* Notes:
* (1) This reverses the list in-place.
*/
l_int32
listReverse(DLLIST **phead)
{
void *obj; /* whatever */
DLLIST *head, *rhead;
PROCNAME("listReverse");
if (!phead)
return ERROR_INT("&head not defined", procName, 1);
if ((head = *phead) == NULL)
return ERROR_INT("head not defined", procName, 1);
rhead = NULL;
while (head) {
obj = listRemoveFromHead(&head);
listAddToHead(&rhead, obj);
}
*phead = rhead;
return 0;
}
/*!
* listJoin()
*
* Input: &head1 (<may be changed> head of first list)
* &head2 (<to be nulled> head of second list)
* Return: 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.
*/
l_int32
listJoin(DLLIST **phead1,
DLLIST **phead2)
{
void *obj;
DLLIST *head1, *head2, *tail1;
PROCNAME("listJoin");
if (!phead1)
return ERROR_INT("&head1 not defined", procName, 1);
if (!phead2)
return ERROR_INT("&head2 not defined", procName, 1);
/* If no list2, just return list1 unchanged */
if ((head2 = *phead2) == NULL)
return 0;
/* If no list1, just return list2 */
if ((head1 = *phead1) == NULL) {
*phead1 = head2;
*phead2 = NULL;
return 0;
}
/* General case for concatenation into list 1 */
tail1 = listFindTail(head1);
while (head2) {
obj = listRemoveFromHead(&head2);
listAddToTail(&head1, &tail1, obj);
}
*phead2 = NULL;
return 0;
}