tommylist.h

Go to the documentation of this file.

/*
 * Copyright (c) 2010, Andrea Mazzoleni. 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 THE COPYRIGHT OWNER OR 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.
 */
 
#ifndef __TOMMYLIST_H
#define __TOMMYLIST_H
 
#include "tommytypes.h"
 
/******************************************************************************/
/* list */
 
typedef tommy_node* tommy_list;
 
tommy_inline void tommy_list_init(tommy_list* list)
{
        *list = 0;
}
 
tommy_inline tommy_node* tommy_list_head(tommy_list* list)
{
        return *list;
}
 
tommy_inline tommy_node* tommy_list_tail(tommy_list* list)
{
        tommy_node* head = tommy_list_head(list);
 
        if (!head)
                return 0;
 
        return head->prev;
}
 
tommy_inline void tommy_list_insert_first(tommy_list* list, tommy_node* node)
{
        /* one element "circular" prev list */
        node->prev = node;
 
        /* one element "0 terminated" next list */
        node->next = 0;
 
        *list = node;
}
 
tommy_inline void tommy_list_insert_head_not_empty(tommy_list* list, tommy_node* node)
{
        tommy_node* head = tommy_list_head(list);
 
        /* insert in the "circular" prev list */
        node->prev = head->prev;
        head->prev = node;
 
        /* insert in the "0 terminated" next list */
        node->next = head;
 
        *list = node;
}
 
tommy_inline void tommy_list_insert_tail_not_empty(tommy_node* head, tommy_node* node)
{
        /* insert in the "circular" prev list */
        node->prev = head->prev;
        head->prev = node;
 
        /* insert in the "0 terminated" next list */
        node->next = 0;
        node->prev->next = node;
}
 
tommy_inline void tommy_list_insert_head(tommy_list* list, tommy_node* node, void* data)
{
        tommy_node* head = tommy_list_head(list);
 
        if (head)
                tommy_list_insert_head_not_empty(list, node);
        else
                tommy_list_insert_first(list, node);
 
        node->data = data;
}
 
tommy_inline void tommy_list_insert_tail(tommy_list* list, tommy_node* node, void* data)
{
        tommy_node* head = tommy_list_head(list);
 
        if (head)
                tommy_list_insert_tail_not_empty(head, node);
        else
                tommy_list_insert_first(list, node);
 
        node->data = data;
}
 
tommy_inline void* tommy_list_remove_existing(tommy_list* list, tommy_node* node)
{
        tommy_node* head = tommy_list_head(list);
 
        /* remove from the "circular" prev list */
        if (node->next)
                node->next->prev = node->prev;
        else
                head->prev = node->prev; /* the last */
 
        /* remove from the "0 terminated" next list */
        if (head == node)
                *list = node->next; /* the new head, in case 0 */
        else
                node->prev->next = node->next;
 
        return node->data;
}
 
tommy_inline void tommy_list_concat(tommy_list* first, tommy_list* second)
{
        tommy_node* first_head;
        tommy_node* first_tail;
        tommy_node* second_head;
 
        /* if the second is empty, nothing to do */
        second_head = tommy_list_head(second);
        if (second_head == 0)
                return;
 
        /* if the first is empty, copy the second */
        first_head = tommy_list_head(first);
        if (first_head == 0) {
                *first = *second;
                return;
        }
 
        /* tail of the first list */
        first_tail = first_head->prev;
 
        /* set the "circular" prev list */
        first_head->prev = second_head->prev;
        second_head->prev = first_tail;
 
        /* set the "0 terminated" next list */
        first_tail->next = second_head;
}
 
TOMMY_API void tommy_list_sort(tommy_list* list, tommy_compare_func* cmp);
 
tommy_inline tommy_bool_t tommy_list_empty(tommy_list* list)
{
        return tommy_list_head(list) == 0;
}
 
tommy_inline tommy_size_t tommy_list_count(tommy_list* list)
{
        tommy_size_t count = 0;
        tommy_node* i = tommy_list_head(list);
 
        while (i) {
                ++count;
                i = i->next;
        }
 
        return count;
}
 
tommy_inline void tommy_list_foreach(tommy_list* list, tommy_foreach_func* func)
{
        tommy_node* node = tommy_list_head(list);
 
        while (node) {
                void* data = node->data;
                node = node->next;
                func(data);
        }
}
 
tommy_inline void tommy_list_foreach_arg(tommy_list* list, tommy_foreach_arg_func* func, void* arg)
{
        tommy_node* node = tommy_list_head(list);
 
        while (node) {
                void* data = node->data;
                node = node->next;
                func(arg, data);
        }
}
 
#endif