|
|
e09104 |
/*****************************************************************************/
|
|
|
e09104 |
/* dalist: a zero-dependency book-keeping library */
|
|
|
e09104 |
/* Copyright (C) 2013,2014,2015 Z. Gilboa */
|
|
|
e09104 |
/* Released under GPLv2 and GPLv3; see COPYING.DALIST. */
|
|
|
e09104 |
/*****************************************************************************/
|
|
|
e09104 |
|
|
|
e09104 |
#include <dalist/dalist.h>
|
|
|
e09104 |
#include "dalist_impl.h"
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_init(struct dalist * dlist)
|
|
|
e09104 |
{
|
|
|
e09104 |
dlist->head = dlist->tail = 0;
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_init_ex(
|
|
|
e09104 |
struct dalist_ex * dlist,
|
|
|
e09104 |
size_t dblock_size,
|
|
|
e09104 |
size_t lblock_size,
|
|
|
e09104 |
void * memfn_ptr,
|
|
|
e09104 |
enum dalist_memfn memfn_method)
|
|
|
e09104 |
|
|
|
e09104 |
{
|
|
|
e09104 |
if (!dlist)
|
|
|
e09104 |
return DALIST_ELIST;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->head = dlist->tail = 0;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->dblock_size = dblock_size;
|
|
|
e09104 |
dlist->lblock_size = lblock_size;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->memfn_ptr = memfn_ptr;
|
|
|
e09104 |
dlist->memfn_method = memfn_method;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->free = 0;
|
|
|
e09104 |
dlist->bookmarks = 0;
|
|
|
e09104 |
dlist->memfn_status = 0;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->info.list_nodes = 0;
|
|
|
e09104 |
dlist->info.free_nodes = 0;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->info.bookmark_from = 0;
|
|
|
e09104 |
dlist->info.bookmark_to = 0;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->info.bookmark_key_min = 0;
|
|
|
e09104 |
dlist->info.bookmark_key_max = 0;
|
|
|
e09104 |
|
|
|
e09104 |
dlist->info.nodes_below_first_bookmark = 0;
|
|
|
e09104 |
dlist->info.nodes_above_last_bookmark = 0;
|
|
|
e09104 |
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_insert_before(
|
|
|
e09104 |
struct dalist * dlist,
|
|
|
e09104 |
struct dalist_node * lnode,
|
|
|
e09104 |
struct dalist_node * nnode)
|
|
|
e09104 |
{
|
|
|
e09104 |
if (!dlist)
|
|
|
e09104 |
return DALIST_ELIST;
|
|
|
e09104 |
|
|
|
e09104 |
if (lnode) {
|
|
|
e09104 |
/* insert before an existing node */
|
|
|
e09104 |
nnode->prev = lnode->prev;
|
|
|
e09104 |
nnode->next = lnode;
|
|
|
e09104 |
lnode->prev = nnode;
|
|
|
e09104 |
|
|
|
e09104 |
if (nnode->prev)
|
|
|
e09104 |
nnode->prev->next = nnode;
|
|
|
e09104 |
else
|
|
|
e09104 |
dlist->head = nnode;
|
|
|
e09104 |
} else {
|
|
|
e09104 |
if (dlist->head)
|
|
|
e09104 |
return DALIST_ENODE;
|
|
|
e09104 |
else {
|
|
|
e09104 |
/* nnode is the new head/tail */
|
|
|
e09104 |
nnode->next = 0;
|
|
|
e09104 |
nnode->prev = 0;
|
|
|
e09104 |
dlist->head = nnode;
|
|
|
e09104 |
dlist->tail = nnode;
|
|
|
e09104 |
}
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_insert_after(
|
|
|
e09104 |
struct dalist * dlist,
|
|
|
e09104 |
struct dalist_node * lnode,
|
|
|
e09104 |
struct dalist_node * nnode)
|
|
|
e09104 |
{
|
|
|
e09104 |
if (!dlist)
|
|
|
e09104 |
return DALIST_ELIST;
|
|
|
e09104 |
|
|
|
e09104 |
if (lnode) {
|
|
|
e09104 |
/* insert after an existing node */
|
|
|
e09104 |
nnode->prev = lnode;
|
|
|
e09104 |
nnode->next = lnode->next;
|
|
|
e09104 |
lnode->next = nnode;
|
|
|
e09104 |
|
|
|
e09104 |
if (nnode->next)
|
|
|
e09104 |
nnode->next->prev = nnode;
|
|
|
e09104 |
else
|
|
|
e09104 |
dlist->tail = nnode;
|
|
|
e09104 |
} else {
|
|
|
e09104 |
if (dlist->head)
|
|
|
e09104 |
return DALIST_ENODE;
|
|
|
e09104 |
else {
|
|
|
e09104 |
/* nnode is the new head/tail */
|
|
|
e09104 |
nnode->next = 0;
|
|
|
e09104 |
nnode->prev = 0;
|
|
|
e09104 |
dlist->head = nnode;
|
|
|
e09104 |
dlist->tail = nnode;
|
|
|
e09104 |
}
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_unlink_node(
|
|
|
e09104 |
struct dalist * dlist,
|
|
|
e09104 |
struct dalist_node * node)
|
|
|
e09104 |
{
|
|
|
e09104 |
struct dalist_node * prev;
|
|
|
e09104 |
struct dalist_node * next;
|
|
|
e09104 |
|
|
|
e09104 |
if (!dlist)
|
|
|
e09104 |
return DALIST_ELIST;
|
|
|
e09104 |
else if (!node)
|
|
|
e09104 |
return DALIST_ENODE;
|
|
|
e09104 |
|
|
|
e09104 |
prev = node->prev;
|
|
|
e09104 |
next = node->next;
|
|
|
e09104 |
|
|
|
e09104 |
if (prev)
|
|
|
e09104 |
prev->next = next;
|
|
|
e09104 |
else
|
|
|
e09104 |
dlist->head = next;
|
|
|
e09104 |
|
|
|
e09104 |
if (next)
|
|
|
e09104 |
next->prev = prev;
|
|
|
e09104 |
else
|
|
|
e09104 |
dlist->tail = prev;
|
|
|
e09104 |
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_unlink_node_ex(
|
|
|
e09104 |
struct dalist_ex * dlist,
|
|
|
e09104 |
struct dalist_node_ex * node)
|
|
|
e09104 |
{
|
|
|
e09104 |
int ret;
|
|
|
e09104 |
|
|
|
e09104 |
ret = dalist_unlink_node(
|
|
|
e09104 |
(struct dalist *)dlist,
|
|
|
e09104 |
(struct dalist_node *)node);
|
|
|
e09104 |
|
|
|
e09104 |
if (ret == DALIST_OK)
|
|
|
e09104 |
dlist->info.list_nodes--;
|
|
|
e09104 |
|
|
|
e09104 |
return ret;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_discard_node(
|
|
|
e09104 |
struct dalist_ex * dlist,
|
|
|
e09104 |
struct dalist_node_ex * node)
|
|
|
e09104 |
{
|
|
|
e09104 |
int ret;
|
|
|
e09104 |
|
|
|
e09104 |
ret = dalist_unlink_node_ex(dlist,node);
|
|
|
e09104 |
|
|
|
e09104 |
if (ret == DALIST_OK)
|
|
|
e09104 |
ret = dalist_deposit_free_node(dlist,node);
|
|
|
e09104 |
|
|
|
e09104 |
return ret;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_get_node_by_key(
|
|
|
e09104 |
struct dalist_ex * dlist,
|
|
|
e09104 |
struct dalist_node_ex **node,
|
|
|
e09104 |
uintptr_t key,
|
|
|
e09104 |
uintptr_t get_flags,
|
|
|
e09104 |
uintptr_t * node_flags)
|
|
|
e09104 |
{
|
|
|
e09104 |
struct dalist_node_ex * cnode;
|
|
|
e09104 |
struct dalist_node_ex * nnode;
|
|
|
e09104 |
uintptr_t flags;
|
|
|
e09104 |
int ret;
|
|
|
e09104 |
|
|
|
e09104 |
if (!dlist) return DALIST_ELIST;
|
|
|
e09104 |
|
|
|
e09104 |
/* init */
|
|
|
e09104 |
if (!node_flags)
|
|
|
e09104 |
node_flags = &flag;;
|
|
|
e09104 |
|
|
|
e09104 |
*node = 0;
|
|
|
e09104 |
*node_flags = DALIST_NODE_TYPE_NONE;
|
|
|
e09104 |
|
|
|
e09104 |
/* traverse */
|
|
|
e09104 |
cnode = (struct dalist_node_ex *)dlist->head;
|
|
|
e09104 |
|
|
|
e09104 |
while (cnode && (cnode->key < key))
|
|
|
e09104 |
cnode = cnode->next;
|
|
|
e09104 |
|
|
|
e09104 |
/* return matching node */
|
|
|
e09104 |
if (cnode && (cnode->key == key)) {
|
|
|
e09104 |
*node_flags = DALIST_NODE_TYPE_EXISTING;
|
|
|
e09104 |
*node = cnode;
|
|
|
e09104 |
return DALIST_OK;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
/* key not found, possibly a new node */
|
|
|
e09104 |
if (get_flags & DALIST_NODE_TYPE_NEW) {
|
|
|
e09104 |
ret = dalist_get_free_node(dlist, (void **)&nnode);
|
|
|
e09104 |
if (ret) return ret;
|
|
|
e09104 |
|
|
|
e09104 |
nnode->key = key;
|
|
|
e09104 |
|
|
|
e09104 |
if (cnode)
|
|
|
e09104 |
ret = dalist_insert_before(
|
|
|
e09104 |
(struct dalist *)dlist,
|
|
|
e09104 |
(struct dalist_node *)cnode,
|
|
|
e09104 |
(struct dalist_node *)nnode);
|
|
|
e09104 |
else
|
|
|
e09104 |
ret = dalist_insert_after(
|
|
|
e09104 |
(struct dalist *)dlist,
|
|
|
e09104 |
(struct dalist_node *)dlist->tail,
|
|
|
e09104 |
(struct dalist_node *)nnode);
|
|
|
e09104 |
|
|
|
e09104 |
if (ret == DALIST_OK) {
|
|
|
e09104 |
*node = nnode;
|
|
|
e09104 |
dlist->info.list_nodes++;
|
|
|
e09104 |
*node_flags = DALIST_NODE_TYPE_NEW;
|
|
|
e09104 |
} else
|
|
|
e09104 |
dalist_deposit_free_node(dlist,nnode);
|
|
|
e09104 |
} else
|
|
|
e09104 |
ret = DALIST_OK;
|
|
|
e09104 |
|
|
|
e09104 |
return ret;
|
|
|
e09104 |
}
|
|
|
e09104 |
|
|
|
e09104 |
|
|
|
e09104 |
dalist_api
|
|
|
e09104 |
int dalist_insert_node_by_key(
|
|
|
e09104 |
struct dalist_ex * dlist,
|
|
|
e09104 |
struct dalist_node_ex * node)
|
|
|
e09104 |
{
|
|
|
e09104 |
struct dalist_node_ex * cnode;
|
|
|
e09104 |
int ret;
|
|
|
e09104 |
|
|
|
e09104 |
/* verify dlist */
|
|
|
e09104 |
if (!dlist)
|
|
|
e09104 |
return DALIST_ELIST;
|
|
|
e09104 |
|
|
|
e09104 |
/* traverse */
|
|
|
e09104 |
cnode = (struct dalist_node_ex *)dlist->head;
|
|
|
e09104 |
|
|
|
e09104 |
while (cnode && (cnode->key < node->key))
|
|
|
e09104 |
cnode = cnode->next;
|
|
|
e09104 |
|
|
|
e09104 |
/* verify that node-> is unique */
|
|
|
e09104 |
if (cnode && (cnode->key == node->key))
|
|
|
e09104 |
return DALIST_EKEYEXISTS;
|
|
|
e09104 |
|
|
|
e09104 |
/* key is unique, add a new node */
|
|
|
e09104 |
if (cnode)
|
|
|
e09104 |
ret = dalist_insert_before(
|
|
|
e09104 |
(struct dalist *)dlist,
|
|
|
e09104 |
(struct dalist_node *)cnode,
|
|
|
e09104 |
(struct dalist_node *)node);
|
|
|
e09104 |
else
|
|
|
e09104 |
ret = dalist_insert_after(
|
|
|
e09104 |
(struct dalist *)dlist,
|
|
|
e09104 |
(struct dalist_node *)dlist->tail,
|
|
|
e09104 |
(struct dalist_node *)node);
|
|
|
e09104 |
|
|
|
e09104 |
if (ret == DALIST_OK)
|
|
|
e09104 |
dlist->info.list_nodes++;
|
|
|
e09104 |
|
|
|
e09104 |
return ret;
|
|
|
e09104 |
}
|