Blame src/dalist.c

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
}