list.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/
 
#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */
 
#include <string.h>
#include "allheaders.h"
 
/*---------------------------------------------------------------------*
 *                    Inserting and removing elements                  *
 *---------------------------------------------------------------------*/
void
listDestroy(DLLIST  **phead)
{
DLLIST  *elem, *next, *head;
 
    PROCNAME("listDestroy");
 
    if (phead == NULL) {
        L_WARNING("ptr address is null!\n", procName);
        return;
    }
 
    if ((head = *phead) == NULL)
        return;
 
    for (elem = head; elem; elem = next) {
        if (elem->data)
            L_WARNING("list data ptr is not null\n", procName);
        next = elem->next;
        LEPT_FREE(elem);
    }
    *phead = NULL;
}
 
 
l_ok
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);
 
    cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
    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;
}
 
 
l_ok
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);
 
    cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
    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;
}
 
 
l_ok
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 */
    cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
    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;
}
 
 
l_ok
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 */
    cell = (DLLIST *)LEPT_CALLOC(1, sizeof(DLLIST));
    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;
}
 
 
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;
    }
 
    LEPT_FREE(elem);
    return data;
}
 
 
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;
    LEPT_FREE(head);
    return data;
}
 
 
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;
    LEPT_FREE(tail);
    return data;
}
 
 
 
/*---------------------------------------------------------------------*
 *                         Other list operations                       *
 *---------------------------------------------------------------------*/
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;
}
 
 
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);
}
 
 
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;
}
 
 
l_ok
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;
}
 
 
l_ok
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;
}