From e09104e6e294bed185227d5a2065d7a1877562b9 Mon Sep 17 00:00:00 2001 From: midipix Date: Sun, 12 Apr 2015 12:23:25 -0400 Subject: dalist: initial commit. --- src/dalist.c | 297 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 297 insertions(+) create mode 100644 src/dalist.c (limited to 'src/dalist.c') diff --git a/src/dalist.c b/src/dalist.c new file mode 100644 index 0000000..dffac64 --- /dev/null +++ b/src/dalist.c @@ -0,0 +1,297 @@ +/*****************************************************************************/ +/* dalist: a zero-dependency book-keeping library */ +/* Copyright (C) 2013,2014,2015 Z. Gilboa */ +/* Released under GPLv2 and GPLv3; see COPYING.DALIST. */ +/*****************************************************************************/ + +#include +#include "dalist_impl.h" + + +dalist_api +int dalist_init(struct dalist * dlist) +{ + dlist->head = dlist->tail = 0; + return DALIST_OK; +} + + +dalist_api +int dalist_init_ex( + struct dalist_ex * dlist, + size_t dblock_size, + size_t lblock_size, + void * memfn_ptr, + enum dalist_memfn memfn_method) + +{ + if (!dlist) + return DALIST_ELIST; + + dlist->head = dlist->tail = 0; + + dlist->dblock_size = dblock_size; + dlist->lblock_size = lblock_size; + + dlist->memfn_ptr = memfn_ptr; + dlist->memfn_method = memfn_method; + + dlist->free = 0; + dlist->bookmarks = 0; + dlist->memfn_status = 0; + + dlist->info.list_nodes = 0; + dlist->info.free_nodes = 0; + + dlist->info.bookmark_from = 0; + dlist->info.bookmark_to = 0; + + dlist->info.bookmark_key_min = 0; + dlist->info.bookmark_key_max = 0; + + dlist->info.nodes_below_first_bookmark = 0; + dlist->info.nodes_above_last_bookmark = 0; + + return DALIST_OK; +} + + +dalist_api +int dalist_insert_before( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode) +{ + if (!dlist) + return DALIST_ELIST; + + if (lnode) { + /* insert before an existing node */ + nnode->prev = lnode->prev; + nnode->next = lnode; + lnode->prev = nnode; + + if (nnode->prev) + nnode->prev->next = nnode; + else + dlist->head = nnode; + } else { + if (dlist->head) + return DALIST_ENODE; + else { + /* nnode is the new head/tail */ + nnode->next = 0; + nnode->prev = 0; + dlist->head = nnode; + dlist->tail = nnode; + } + } + + return DALIST_OK; +} + + +dalist_api +int dalist_insert_after( + struct dalist * dlist, + struct dalist_node * lnode, + struct dalist_node * nnode) +{ + if (!dlist) + return DALIST_ELIST; + + if (lnode) { + /* insert after an existing node */ + nnode->prev = lnode; + nnode->next = lnode->next; + lnode->next = nnode; + + if (nnode->next) + nnode->next->prev = nnode; + else + dlist->tail = nnode; + } else { + if (dlist->head) + return DALIST_ENODE; + else { + /* nnode is the new head/tail */ + nnode->next = 0; + nnode->prev = 0; + dlist->head = nnode; + dlist->tail = nnode; + } + } + + return DALIST_OK; +} + + +dalist_api +int dalist_unlink_node( + struct dalist * dlist, + struct dalist_node * node) +{ + struct dalist_node * prev; + struct dalist_node * next; + + if (!dlist) + return DALIST_ELIST; + else if (!node) + return DALIST_ENODE; + + prev = node->prev; + next = node->next; + + if (prev) + prev->next = next; + else + dlist->head = next; + + if (next) + next->prev = prev; + else + dlist->tail = prev; + + return DALIST_OK; +} + + +dalist_api +int dalist_unlink_node_ex( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + int ret; + + ret = dalist_unlink_node( + (struct dalist *)dlist, + (struct dalist_node *)node); + + if (ret == DALIST_OK) + dlist->info.list_nodes--; + + return ret; +} + + +dalist_api +int dalist_discard_node( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + int ret; + + ret = dalist_unlink_node_ex(dlist,node); + + if (ret == DALIST_OK) + ret = dalist_deposit_free_node(dlist,node); + + return ret; +} + + +dalist_api +int dalist_get_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex **node, + uintptr_t key, + uintptr_t get_flags, + uintptr_t * node_flags) +{ + struct dalist_node_ex * cnode; + struct dalist_node_ex * nnode; + uintptr_t flags; + int ret; + + if (!dlist) return DALIST_ELIST; + + /* init */ + if (!node_flags) + node_flags = &flags; + + *node = 0; + *node_flags = DALIST_NODE_TYPE_NONE; + + /* traverse */ + cnode = (struct dalist_node_ex *)dlist->head; + + while (cnode && (cnode->key < key)) + cnode = cnode->next; + + /* return matching node */ + if (cnode && (cnode->key == key)) { + *node_flags = DALIST_NODE_TYPE_EXISTING; + *node = cnode; + return DALIST_OK; + } + + /* key not found, possibly a new node */ + if (get_flags & DALIST_NODE_TYPE_NEW) { + ret = dalist_get_free_node(dlist, (void **)&nnode); + if (ret) return ret; + + nnode->key = key; + + if (cnode) + ret = dalist_insert_before( + (struct dalist *)dlist, + (struct dalist_node *)cnode, + (struct dalist_node *)nnode); + else + ret = dalist_insert_after( + (struct dalist *)dlist, + (struct dalist_node *)dlist->tail, + (struct dalist_node *)nnode); + + if (ret == DALIST_OK) { + *node = nnode; + dlist->info.list_nodes++; + *node_flags = DALIST_NODE_TYPE_NEW; + } else + dalist_deposit_free_node(dlist,nnode); + } else + ret = DALIST_OK; + + return ret; +} + + +dalist_api +int dalist_insert_node_by_key( + struct dalist_ex * dlist, + struct dalist_node_ex * node) +{ + struct dalist_node_ex * cnode; + int ret; + + /* verify dlist */ + if (!dlist) + return DALIST_ELIST; + + /* traverse */ + cnode = (struct dalist_node_ex *)dlist->head; + + while (cnode && (cnode->key < node->key)) + cnode = cnode->next; + + /* verify that node-> is unique */ + if (cnode && (cnode->key == node->key)) + return DALIST_EKEYEXISTS; + + /* key is unique, add a new node */ + if (cnode) + ret = dalist_insert_before( + (struct dalist *)dlist, + (struct dalist_node *)cnode, + (struct dalist_node *)node); + else + ret = dalist_insert_after( + (struct dalist *)dlist, + (struct dalist_node *)dlist->tail, + (struct dalist_node *)node); + + if (ret == DALIST_OK) + dlist->info.list_nodes++; + + return ret; +} -- cgit v1.2.3