list.c

/*

  FreeWRL support library.
  Linked lists.

*/

/****************************************************************************
    This file is part of the FreeWRL/FreeX3D Distribution.

    Copyright 2009 CRC Canada. (http://www.crc.gc.ca)

    FreeWRL/FreeX3D is free software: you can redistribute it and/or modify
    it under the terms of the GNU Lesser Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    FreeWRL/FreeX3D is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with FreeWRL/FreeX3D.  If not, see <http://www.gnu.org/licenses/>.
****************************************************************************/



#include <config.h>
#include <system.h>
#include <internal.h>

#include <list.h>

/* singly linked */
#if defined(DEBUG_MALLOC) && defined(DEBUG_MALLOC_LIST)
s_list_t* _ml_new(const void *elem, int line, char *fi)
{
    s_list_t *item;
        item = freewrlMalloc(line, fi, sizeof(s_list_t), TRUE);
    ml_elem(item) = (void *) elem;
    return item;
}
#else
s_list_t* ml_new(const void *elem)
{
    s_list_t *item;
    item = XALLOC(s_list_t);
    ml_elem(item) = (void *) elem;
    return item;
}
#endif

int ml_count(s_list_t *list)
{
    int c = 0;
    while (list) {
        c++;
        list = ml_next(list);
    }
    return c;
}

s_list_t* ml_prev(s_list_t *list, s_list_t *item)
{
    s_list_t *n;
    if (!item) return NULL;
    while (list) {
        n = ml_next(list);
        if (!n)
            return NULL;
        if (n == item)
            return list;
        list = n;
    }
    return NULL;
}

s_list_t* ml_last(s_list_t *list)
{
    while (list) {
        if (!ml_next(list))
            break;
        list = ml_next(list);
    }
    return list;
}

s_list_t* ml_find(s_list_t *list, s_list_t *item)
{
    while (list) {
        if (list == item)
            return list;
        list = ml_next(list);
    }
    return NULL;
}

s_list_t* ml_find_elem(s_list_t *list, void *elem)
{
    while (list) {
        if (ml_elem(list) == elem)
            return list;
        list = ml_next(list);
    }
    return NULL;
}

s_list_t* ml_insert(s_list_t *list, s_list_t *point, s_list_t *item)
{
    if (!list) {
        if (item) ml_next(item) = point;
        return item;
    }
    if (!point || (list == point)) {
        if (item) ml_next(item) = list;
    } else {
        s_list_t *prev;
        prev = ml_prev(list, point);
        if (prev) {
                ml_next(prev) = item;
                ml_next(item) = point;
        } else {
                item = NULL;
        }
    }
    return item;
}
s_list_t* ml_append(s_list_t *list, s_list_t *item)
{
    if (list) {
        ml_next(ml_last(list)) = item;
        return list;
    }
    return item;
}

void ml_delete(s_list_t *list, s_list_t *item)
{
    s_list_t *prev;
    prev = ml_prev(list, item);
    if (prev) {
                ml_next(prev) = ml_next(item);
                XFREE(item);
    } else {
                //ERROR_MSG("ml_delete: trying to destroy first element in a list\n");
    }
}

s_list_t *ml_remove(s_list_t *list, s_list_t *item)
{
    s_list_t *prev, *newlist;
        newlist = list;
    prev = ml_prev(list, item);
    if (prev) {
                ml_next(prev) = ml_next(item);
    } else {
                newlist = NULL;
    }
        return newlist;
}
void ml_enqueue(s_list_t **list, s_list_t *item)
{
        *list = ml_insert(*list,*list,item);
}
s_list_t* ml_dequeue(s_list_t **list){
        s_list_t* item = NULL;
        item = ml_last(*list);
        *list = ml_remove(*list,item);
        return item;
}

/*when known to be a singlton with next=null, just free it*/
void ml_free(s_list_t *item){
        XFREE(item);
}
s_list_t* ml_delete_self(s_list_t *list, s_list_t *item)
{
    s_list_t *it;
    if (list == item) {
        /* first element */
        it = item->next;
        XFREE(item);
        return it;
    }
    ml_delete(list, item);
    return list;
}

void ml_delete2(s_list_t *list, s_list_t *item, f_free_t f)
{
    s_list_t *prev;
    prev = ml_prev(list, item);
    ml_next(prev) = ml_next(item);
    if (ml_elem(item)) {
        f(ml_elem(item));
    } else {
        ERROR_MSG("ml_delete2: *error* deleting empty item %p from list %p\n", item, list);
    }
    XFREE(item);
}

void ml_delete_all(s_list_t *list)
{
    s_list_t *next;
    while (list) {
        next = ml_next(list);
        XFREE(list);
        list = next;
    }
}

void ml_delete_all2(s_list_t *list, f_free_t f)
{
    s_list_t *begin, *next;
        f_free_t *FF;
    begin = list;
        FF = f;
    if (!FF) FF = free;
    while (list) {
        if (ml_elem(list)) {
            FF(ml_elem(list));
        } else {
                ERROR_MSG("ml_delete_all2: *error* deleting empty item %p from list %p\n", list, begin);
        }
        next = ml_next(list);
        XFREE(list);
        list = next;
    }
}

s_list_t* ml_get(s_list_t* list, int index)
{
    int i = 0;
    
    while (list) {
        if (i == index)
            return list;
        list = ml_next(list);
        i++;
    }
    return NULL;
}

void ml_dump(s_list_t *list)
{
        TRACE_MSG("ml_dump (%p) : ", list);
        ml_foreach(list, TRACE_MSG("%p ", __l));
        TRACE_MSG("\n");
}

void ml_dump_char(s_list_t *list)
{
        TRACE_MSG("ml_dump_char (%p) : ", list);
        ml_foreach(list, TRACE_MSG("%s ", (char*)ml_elem(__l)));
        TRACE_MSG("\n");
}
















/* circularly doubly linked - dug9 added feb 16, 2013 but did not test cdl_ functions,
   need use for it */
cd_list_t* cdl_new(const void *elem)
{
    cd_list_t *item;
    item = XALLOC(cd_list_t);
    cdl_elem(item) = (void *) elem;
        item->next = item;
        item->prev = item;
    return item;
}

int cdl_count(cd_list_t *head)
{
        cd_list_t *list;
    int c = 0;
        list = head;
        if(head) do{
        c++;
        list = cdl_next(list);
    }while(list != head);
    return c;
}

cd_list_t* cdl_find(cd_list_t *head, cd_list_t *item)
{
        cd_list_t *list = head;
        if(!head) return NULL;
    do {
        if (list == item)
            return list;
        list = cdl_next(list);
    }while(list != head);
    return NULL;
}

cd_list_t* cdl_find_elem(cd_list_t *head, void *elem)
{
        cd_list_t *list = head;
        if(!list) return NULL;
    do {
        if (cdl_elem(list) == elem)
            return list;
        list = cdl_next(list);
    }while(list != head);
    return NULL;
}

cd_list_t* cdl_insert(cd_list_t *head, cd_list_t *point, cd_list_t *item)
{
        cd_list_t *tmp;
        if(!item) return head;
    if (!head) {
                tmp = point;
                if (item){
                        if(!point) tmp = item;
                        item->next = tmp;
                        item->prev = tmp;
                }
        return tmp;
    }
    if(!point) point = head;
        point->next = item;
        item->prev = point->prev;
        point->prev = item;
        item->prev->next = item;
        if(head == point) {
                head = item;
        }
    return head;
}

cd_list_t* cdl_append(cd_list_t *head, cd_list_t *item)
{
        cd_list_t *last;
    if (head) {
        last = cdl_prev(head);
                last->next = item;
                head->prev = item;
                item->prev = last;
                item->next = head;
        return head;
        }else{
                item->prev = item;
                item->next = item;
                return item;
        }
}

cd_list_t *cdl_delete(cd_list_t *head, cd_list_t *item)
{
    cd_list_t *prev, *next, *ret;
        ret = head;
        if(!item ){
                ERROR_MSG("cdl_delete: no head or item\n");
                return ret;
        }
        if(head){
                if(item == head) ret = head->next;
                if(head->next == head) ret = NULL;
        }
        prev = cdl_prev(item);
        next = cdl_next(item);
        prev->next = next;
        next->prev = prev;
        XFREE(item);
        return ret;
}


cd_list_t * cdl_delete2(cd_list_t *head, cd_list_t *item, f_free_t f)
{
    cd_list_t *prev, *next, *ret;
        ret = head;
        if(!item ){
                ERROR_MSG("cdl_delete2: no head or item\n");
                return ret;
        }
        if(head){
                if(item == head) ret = head->next;
                if(head->next == head) ret = NULL;
        }
        prev = cdl_prev(item);
        next = cdl_next(item);
        prev->next = next;
        next->prev = prev;
    if(cdl_elem(item)) {
                f(cdl_elem(item));
    } else {
                ERROR_MSG("cdl_delete2: *error* deleting empty item %p from list %p\n", item, head);
    }
        XFREE(item);
        return ret;
}

void cdl_delete_all(cd_list_t *head)
{
    cd_list_t *next, *list;
        list = head;
        if(list)
    do{
        next = cdl_next(list);
        XFREE(list);
        list = next;
    }while(list != head);
}

void cdl_delete_all2(cd_list_t *head, f_free_t f)
{
    cd_list_t *list, *next;
        f_free_t *FF;
    list = head;
        FF = f;
    if (!FF) FF = free;
        if(head)
    do{
        if (cdl_elem(list)) {
            FF(cdl_elem(list));
        } else {
                        ERROR_MSG("cdl_delete_all2: *error* deleting empty item %p from list %p\n", list, head);
                }
        next = cdl_next(list);
        XFREE(list);
        list = next;
    }while(list != head);
}

cd_list_t* cdl_get(cd_list_t* head, int index)
{
        cd_list_t* list;
    int i = 0;
    
        list = head;
        if(head)
    do {
                if (i == index)
                        return list;
                list = cdl_next(list);
                i++;
    }while(list != head);
    return NULL;
}

void cdl_dump(cd_list_t *head)
{
        TRACE_MSG("cdl_dump (%p) : ", head);
        cdl_foreach(list, TRACE_MSG("%p ", __l));
        TRACE_MSG("\n");
}

void cdl_dump_char(cd_list_t *head)
{
        TRACE_MSG("cdl_dump_char (%p) : ", head);
        cdl_foreach(list, TRACE_MSG("%s ", (char*)cdl_elem(__l)));
        TRACE_MSG("\n");
}