n_list.c

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#include "nilorea/n_common.h"
#include "nilorea/n_log.h"
#include "nilorea/n_list.h"
 
LIST* new_generic_list(size_t max_items) {
    LIST* list = NULL;
 
    Malloc(list, LIST, 1);
    __n_assert(list, return NULL);
 
    list->nb_max_items = max_items;
    list->nb_items = 0;
 
    list->start = list->end = NULL;
 
    return list;
} /* new_generic_list */
 
LIST_NODE* new_list_node(void* ptr, void (*destructor)(void* ptr)) {
    LIST_NODE* node = NULL;
 
    Malloc(node, LIST_NODE, 1);
    __n_assert(node, n_log(LOG_ERR, "Error allocating node for ptr %p", ptr); return NULL);
 
    node->ptr = ptr;
    node->destroy_func = destructor;
    node->next = node->prev = NULL;
 
    return node;
} /* new_list_node(...) */
 
void* remove_list_node_f(LIST* list, LIST_NODE* node) {
    void* ptr = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "can't remove from NULL list"); return NULL);
    __n_assert(list->start, n_log(LOG_ERR, "can't remove from NULL list->start"); return NULL);
    __n_assert(list->end, n_log(LOG_ERR, "can't remove from NULL list->end"); return NULL);
    __n_assert(node, n_log(LOG_ERR, "can't remove from NULL node"); return NULL);
 
    ptr = node->ptr;
    if (node->prev && node->next) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    } else {
        if (node->prev == NULL && node->next) {
            node->next->prev = NULL;
            list->start = node->next;
        } else {
            if (node->prev && node->next == NULL) {
                node->prev->next = NULL;
                list->end = node->prev;
            } else {
                if (node->prev == NULL && node->next == NULL) {
                    /* removing last item */
                    list->start = list->end = NULL;
                }
            }
        }
    }
    Free(node);
    if (list->nb_items > 0) {
        list->nb_items--;
    }
    return ptr;
} /* remove_list_node_f(...) */
 
int list_node_push(LIST* list, LIST_NODE* node) {
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(node, n_log(LOG_ERR, "invalid node: NULL"); return FALSE);
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
    node->next = NULL;
    if (list->end) {
        list->end->next = node;
        node->prev = list->end;
        list->end = node;
    } else {
        node->prev = NULL;
        list->start = list->end = node;
    }
    list->nb_items++;
    return TRUE;
} /* list_node_push() */
 
LIST_NODE* list_node_pop(LIST* list) {
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return NULL);
 
    if (list->nb_items == 0 || list->end == NULL)
        return NULL;
 
    LIST_NODE* nodeptr = NULL;
 
    nodeptr = list->end;
    if (list->end->prev) {
        list->end = list->end->prev;
        list->end->next = NULL;
    }
    list->nb_items--;
    if (list->nb_items == 0)
        list->start = list->end = NULL;
 
    nodeptr->prev = NULL;
    nodeptr->next = NULL;
    return nodeptr;
} /* list_node_pop() */
 
LIST_NODE* list_node_shift(LIST* list) {
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return NULL);
 
    if (list->nb_items == 0 || list->start == NULL)
        return NULL;
 
    LIST_NODE* nodeptr = NULL;
    nodeptr = list->start;
 
    if (list->start->next) {
        list->start = list->start->next;
        list->start->prev = NULL;
    }
 
    list->nb_items--;
 
    if (list->nb_items == 0)
        list->start = list->end = NULL;
 
    nodeptr->prev = NULL;
    nodeptr->next = NULL;
    return nodeptr;
} /* list_node_shift() */
 
int list_node_unshift(LIST* list, LIST_NODE* node) {
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(node, n_log(LOG_ERR, "invalid node: NULL"); return FALSE);
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
    node->prev = NULL;
    if (list->start) {
        link_node(node, list->start);
        list->start = node;
    } else {
        node->next = NULL;
        list->start = list->end = node;
    }
    list->nb_items++;
 
    return TRUE;
} /* list_node_unshift() */
 
int list_push(LIST* list, void* ptr, void (*destructor)(void* ptr)) {
    LIST_NODE* node = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(ptr, n_log(LOG_ERR, "invalid ptr: NULL"); return FALSE);
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
 
    node = new_list_node(ptr, destructor);
    __n_assert(node, n_log(LOG_ERR, "Couldn't allocate new node"); return FALSE);
 
    if (list->end) {
        list->end->next = node;
        node->prev = list->end;
        list->end = node;
    } else {
        list->start = list->end = node;
    }
    list->nb_items++;
    return TRUE;
} /* list_push( ... ) */
 
int list_push_sorted(LIST* list, void* ptr, int (*comparator)(const void* a, const void* b), void (*destructor)(void* ptr)) {
    LIST_NODE* nodeptr = NULL;
    int ret = TRUE;
 
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(ptr, n_log(LOG_ERR, "invalid ptr: NULL"); return FALSE);
    __n_assert(comparator, n_log(LOG_ERR, "invalid comparator: NULL"); return FALSE);
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
 
    if (list->end) {
        nodeptr = list->end;
        while (nodeptr && (comparator(ptr, nodeptr->ptr) < 0))
            nodeptr = nodeptr->prev;
 
        if (!nodeptr) {
            /* It's the lower ranked element in the sort */
            ret = list_unshift(list, ptr, destructor);
            if (ret == FALSE) {
                n_log(LOG_ERR, "Couldn't list_unshift in list %p ptr %p with destructor %p", list, ptr, destructor);
                return FALSE;
            }
        } else {
            /* we have a match inside the list. let's insert the datas */
            LIST_NODE* node_next = nodeptr->next;
            LIST_NODE* newnode = new_list_node(ptr, destructor);
            __n_assert(newnode, n_log(LOG_ERR, "Couldn't allocate new node"); return FALSE);
 
            if (node_next) {
                link_node(newnode, node_next);
            } else
                list->end = newnode;
 
            link_node(nodeptr, newnode);
            list->nb_items++;
        }
    } else {
        ret = list_push(list, ptr, destructor);
        if (ret == FALSE) {
            n_log(LOG_ERR, "Couldn't list_push in list %p ptr %p with destructor %p", list, ptr, destructor);
            return FALSE;
        }
    }
    return ret;
} /* list_push_sorted( ... ) */
 
int list_unshift(LIST* list, void* ptr, void (*destructor)(void* ptr)) {
    LIST_NODE* node = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(ptr, n_log(LOG_ERR, "invalid ptr: NULL"); return FALSE);
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
    node = new_list_node(ptr, destructor);
    __n_assert(node, n_log(LOG_ERR, "Couldn't allocate new node"); return FALSE);
 
    if (list->start) {
        link_node(node, list->start);
        list->start = node;
    } else {
        list->start = list->end = node;
    }
    list->nb_items++;
 
    return TRUE;
} /* list_unshift_f(...) */
 
int list_unshift_sorted(LIST* list, void* ptr, int (*comparator)(const void* a, const void* b), void (*destructor)(void* ptr)) {
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return FALSE);
    __n_assert(ptr, n_log(LOG_ERR, "invalid ptr: NULL"); return FALSE);
    __n_assert(comparator, n_log(LOG_ERR, "invalid comparator: NULL"); return FALSE);
 
    LIST_NODE* nodeptr = NULL;
    int ret = TRUE;
 
    if (list->nb_max_items > 0 && (list->nb_items >= list->nb_max_items)) {
        n_log(LOG_ERR, "list is full");
        return FALSE;
    }
 
    if (list->start) {
        nodeptr = list->start;
        while (nodeptr && (comparator(ptr, nodeptr->ptr) > 0))
            nodeptr = nodeptr->next;
 
        if (!nodeptr) {
            /* It's the higher ranked element in the sort */
            ret = list_push(list, ptr, destructor);
            if (ret == FALSE) {
                n_log(LOG_ERR, "Couldn't list_push in list %p ptr %p with destructor %p", list, ptr, destructor);
                return FALSE;
            }
        } else {
            /* we have a match inside the list. let's insert the datas */
            LIST_NODE* node_prev = nodeptr->prev;
            LIST_NODE* newnode = new_list_node(ptr, destructor);
            __n_assert(newnode, n_log(LOG_ERR, "Couldn't allocate new node"); return FALSE);
 
            if (node_prev) {
                link_node(node_prev, newnode);
            } else
                list->start = newnode;
 
            link_node(newnode, nodeptr);
            list->nb_items++;
        }
    } else {
        ret = list_unshift(list, ptr, destructor);
        if (ret == FALSE) {
            n_log(LOG_ERR, "Couldn't list_unshift in list %p ptr %p with destructor %p", list, ptr, destructor);
            return FALSE;
        }
    }
    return ret;
} /* list_unshift_sorted(...) */
 
void* list_pop_f(LIST* list) {
    LIST_NODE* nodeptr = NULL;
    void* ptr = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "invalid list: NULL"); return NULL);
 
    if (list->nb_items == 0 || list->end == NULL)
        return NULL;
 
    nodeptr = list->end;
    ptr = nodeptr->ptr;
 
    if (list->end->prev) {
        list->end = list->end->prev;
        list->end->next = NULL;
    }
 
    list->nb_items--;
    if (list->nb_items == 0)
        list->start = list->end = NULL;
 
    Free(nodeptr);
 
    return ptr;
} /* list_pop_f( ... ) */
 
void* list_shift_f(LIST* list, char* file, size_t line) {
    LIST_NODE* nodeptr = NULL;
    void* ptr = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "%s:%d: invalid list: NULL", file, line); return NULL);
 
    if (list->nb_items == 0 || list->start == NULL)
        return NULL;
 
    nodeptr = list->start;
    ptr = nodeptr->ptr;
 
    if (list->start->next) {
        list->start = list->start->next;
        list->start->prev = NULL;
    }
 
    list->nb_items--;
 
    if (list->nb_items == 0)
        list->start = list->end = NULL;
 
    Free(nodeptr);
 
    return ptr;
} /* list_shift_f(...)*/
 
LIST_NODE* list_search(LIST* list, const void* ptr) {
    __n_assert(list, return NULL);
 
    list_foreach(node, list) {
        if (node->ptr == ptr)
            return node;
    }
    return NULL;
} /* list_search */
 
LIST_NODE* list_search_with_f(LIST* list, int (*checkfunk)(void* ptr)) {
    __n_assert(list, return NULL);
    __n_assert(checkfunk, return NULL);
 
    list_foreach(node, list) {
        if (checkfunk(node->ptr))
            return node;
    }
    return NULL;
} /* list_search */
 
int list_empty(LIST* list) {
    LIST_NODE* node = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "list is NULL"); return FALSE);
 
    node = list->start;
    while (node) {
        LIST_NODE* node_ptr = node;
        node = node->next;
        if (node_ptr->destroy_func != NULL) {
            node_ptr->destroy_func(node_ptr->ptr);
        }
        Free(node_ptr);
    }
    list->start = list->end = NULL;
    list->nb_items = 0;
    return TRUE;
} /* list_empty( ... ) */
 
int list_empty_with_f(LIST* list, void (*free_fnct)(void* ptr)) {
    LIST_NODE* node = NULL;
 
    __n_assert(list, n_log(LOG_ERR, "list is NULL"); return FALSE);
 
    node = list->start;
    while (node) {
        LIST_NODE* node_ptr = node;
        node = node->next;
        if (free_fnct) free_fnct(node_ptr->ptr);
        Free(node_ptr);
    }
    list->start = list->end = NULL;
    list->nb_items = 0;
    return TRUE;
} /* list_empty_with_f */
 
int list_destroy(LIST** list) {
    __n_assert(list && (*list), n_log(LOG_ERR, "list already destroyed"); return FALSE);
    list_empty((*list));
    Free((*list));
    return TRUE;
} /* free_list( ... ) */