/*====================================================================* - 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; }