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.
 *====================================================================*/

#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;
    return;
}


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 *)LEPT_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;
}


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 *)LEPT_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;
}


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 *)LEPT_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;
}


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 *)LEPT_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;
}


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_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;
}


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;
}