dalist: initial commit.

12 files changed, 1429 insertions, 0 deletions

diff --git a/Makefile.in b/Makefile.in
new file mode 100644
index 0000000..b370cb0
--- /dev/null
+++ b/Makefile.in
@@ -0,0 +1,14 @@
+all:
+	./lazy -x build
+
+install:
+	./lazy -x build -e install
+
+clean:
+	rm -rf src
+	rm -rf lib
+	rm -f  lazy
+	rm -f  lazy.config.tag
+	rm -f  lz_stack
+	rm -f  *.objs
+	rm -rf *.lst
diff --git a/config.lzy b/config.lzy
new file mode 100644
index 0000000..4983d6b
--- /dev/null
+++ b/config.lzy
@@ -0,0 +1,28 @@
+# package
+lz_package=dalist
+
+
+# toolchain
+lz_default_target=x86_64-nt64-midipix
+lz_default_arch=x86_64
+lz_default_compiler=gcc
+
+
+# lazy
+lz_cflags_cmdline=
+lz_cxxflags_cmdline=
+lz_ldflags_cmdline=
+
+lz_cflags_debug=
+lz_cflags_release=
+
+lz_cflags_include_first=
+lz_cflags_include_last=
+lz_cflags_include_cmdline=
+lz_cxxflags_include_cmdline=
+
+lz_exec_prefix=
+lz_bindir=
+lz_libdir=
+lz_includedir=
+lz_syslibdir=
diff --git a/configure b/configure
new file mode 100755
index 0000000..eb7a40c
--- /dev/null
+++ b/configure
@@ -0,0 +1,115 @@
+#!/bin/sh
+
+# a simple configure-make wrapper for use in conjunction with the 'lazy' build script.
+# 'lazy' is deviant, occasionally useful, and permissively licensed; get_lazy() below,
+# then look for configure.template in the root directory.
+
+init_vars()
+{
+	lz_config_dir=`readlink -f $(dirname $0)`
+	lz_pwd=`pwd`
+
+	if [ x"$lz_config" = x ]; then
+		. $lz_config_dir/config.lzy || exit 2
+	else
+		. "$lz_config" || exit 2
+	fi
+}
+
+
+error_msg()
+{
+	echo $@ >&2
+}
+
+
+require_out_of_tree()
+{
+	if [ x"$lz_config_dir" = x"$lz_pwd" ]; then
+		error_msg "$lz_package: out-of-tree builds are required."
+		error_msg "please invoke configure again from a clean build directory."
+		exit 2
+	fi
+
+	return 0
+}
+
+
+get_lazy()
+{
+	which lazy && lazy=`which lazy` && return 0
+
+	if ! [ -d slazy ]; then
+		git clone git://midipix.org/lazy slazy || exit 2
+	fi
+
+	lazy=$lz_pwd/slazy/lazy
+}
+
+
+lazy_approach()
+{
+	if [ x"$lz_prefix" = x ]; then
+		error_msg "prefix is required."
+		exit 2
+	fi
+
+	if [ x"$lz_arch" = x ];     then lz_arch=$lz_default_arch; fi
+	if [ x"$lz_target" = x ];   then lz_target=$lz_default_target; fi
+	if [ x"$lz_compiler" = x ]; then lz_compiler=$lz_default_compiler; fi
+	if [ x"$lz_compiler" = x ]; then lz_compiler=gcc; fi
+
+	$lazy -x config	$lz_debug	\
+		-t $lz_target		\
+		-a $lz_arch		\
+		-c $lz_compiler		\
+		-n $lz_package		\
+		-p $lz_config_dir	\
+		-f $lz_prefix		\
+		|| exit 2
+
+}
+
+
+lazy_copy()
+{
+	cp "$lz_config_dir/Makefile.in" "$lz_pwd/Makefile"
+}
+
+
+for arg ; do
+	case "$arg" in
+		--help)	usage
+			;;
+
+		--prefix=*)
+			lz_prefix=${arg#*=}
+			;;
+		--host=*)
+			lz_target=${arg#*=}
+			;;
+		--target=*)
+			lz_target=${arg#*=}
+			;;
+		--compiler=*)
+			lz_compiler=${arg#*=}
+			;;
+		--config=*)
+			lz_config=${arg#*=}
+			;;
+		--debug)
+			lz_debug='-d'
+			;;
+		*)
+			error_msg ${arg#}: "unsupported config argument."
+			exit 2
+			;;
+	esac
+done
+
+
+init_vars
+require_out_of_tree
+get_lazy
+lazy_approach
+lazy_copy
diff --git a/dalist.lzy b/dalist.lzy
new file mode 100644
index 0000000..1b82f7b
--- /dev/null
+++ b/dalist.lzy
@@ -0,0 +1,127 @@
+lz_project_rules()
+{
+	lz_rules="all install xstatic install_xstatic"
+}
+
+lz_project_definitions()
+{
+	dalist_lib_name=libdalist
+	dalist_so_name="$lz_build_dir/lib/$dalist_lib_name$lz_dylib_ext"
+	dalist_a_name="$lz_build_dir/lib/$dalist_lib_name$lz_stlib_ext"
+	dalist_so_def_name="$lz_build_dir/lib/$dalist_lib_name$lz_libdef_ext"
+	dalist_implib_name="$lz_build_dir/lib/$dalist_lib_name$lz_implib_ext"
+
+	lz_cflags_common="-DMIDIPIX_FREESTANDING
+			-D__NT$lz_arch_bits \
+			-UWIN32 -U_WIN32 -U__WIN32__ -UWIN64 -U_WIN64 -U__WIN64__ \
+			-Werror=all -fno-builtin -ffreestanding"
+
+
+	# lz_cflags_extra="-Os -fno-stack-protector -fomit-frame-pointer -fno-unwind-tables -fno-asynchronous-unwind-tables"
+				
+	dalist_so_ldflags="-shared --image-base=0x320000 \
+				--entry "$lz_default_underscore"dalist_lib_entry_point@12 \
+				--exclude-all-symbols \
+				--output-def $dalist_so_def_name \
+				--out-implib $dalist_implib_name \
+				--subsystem=windows"
+
+	lz_cflags_include_common="-I$lz_project_dir/include"
+
+	if [ "$MIDIPIX_ROOT"x != x ]; then
+		lz_cflags_include_common="$lz_cflags_include_common -I$MIDIPIX_ROOT/include"
+	fi
+
+	dalist_so_obj_list=dalist.so.objs
+	dalist_so_src_list=dalist.so.src.lst
+
+	dalist_a_obj_list=dalist.a.objs
+	dalist_a_src_list=dalist.a.src.lst
+}
+
+dalist_shared()
+{
+	lz_src_dirs="src"
+	lz_cflags_step="-DDALIST_BUILD"
+
+	if ! [ "$lz_pecoff_winnt"x = yesx ]; then
+		lz_cflags_step="$lz_cflags_step -fpic"
+	fi	
+
+	lz_compile "$dalist_so_obj_list" "$dalist_so_src_list" "$lz_dyobj_ext"
+        lz_link    "$dalist_so_obj_list" "$dalist_so_src_list" "$dalist_so_name" \
+			"$dalist_so_ldflags" \
+			''
+}
+
+
+dalist_static()
+{
+	lz_src_dirs="src"
+
+	lz_compile "$dalist_a_obj_list" "$dalist_a_src_list" "$lz_stobj_ext"
+        lz_archive "$dalist_a_obj_list" "$dalist_a_src_list" "$dalist_a_name"
+}
+
+
+dalist_xstatic()
+{
+	lz_src_dirs="src"
+	lz_cflags_step="-DDALIST_BUILD"
+
+	lz_compile "$dalist_a_obj_list" "$dalist_a_src_list" "$lz_stobj_ext"
+        lz_archive "$dalist_a_obj_list" "$dalist_a_src_list" "$dalist_a_name"
+}
+
+
+dalist_install_headers()
+{
+	lz_pushd $lz_project_dir
+
+	cp -r -t $lz_prefix/include include/$lz_project_name
+
+	lz_popd
+}
+
+
+dalist_install_shared()
+{
+	lz_pushd $lz_build_dir/lib
+
+	cp -t $lz_prefix/lib $dalist_lib_name$lz_dylib_ext
+	cp -t $lz_prefix/lib $dalist_lib_name$lz_implib_ext
+
+	lz_popd
+}
+
+
+dalist_install_static()
+{
+	lz_pushd $lz_build_dir/lib
+
+	cp -t $lz_prefix/lib $dalist_lib_name$lz_stlib_ext
+
+	lz_popd
+}
+
+dalist_install_xstatic()
+{
+	lz_step dalist_xstatic
+	lz_step dalist_install_static
+}
+
+
+dalist_all()
+{
+	lz_step dalist_shared
+	lz_step dalist_static
+}
+
+
+dalist_install()
+{
+	lz_step dalist_all
+	lz_step dalist_install_shared
+	lz_step dalist_install_static
+	lz_step dalist_install_headers
+}
diff --git a/include/dalist/dalist.h b/include/dalist/dalist.h
new file mode 100644
index 0000000..a478306
--- /dev/null
+++ b/include/dalist/dalist.h
@@ -0,0 +1,256 @@
+#ifndef DALIST_H
+#define DALIST_H
+
+#include "dalist_api.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* dalist node types */
+enum dalist_node_types {
+	DALIST_NODE,
+	DALIST_NODE_EX,
+};
+
+
+/* dalist caller-provided memory allocation methods */
+enum dalist_memfn {
+	DALIST_MEMFN_CUSTOM,
+	DALIST_MEMFN_MMAP,
+	DALIST_MEMFN_MALLOC,
+	DALIST_MEMFN_NT_ALLOCATE_VIRTUAL_MEMORY,
+};
+
+
+/* dalist debug environments */
+enum dalist_dbgenv {
+	DALIST_DEBUG_ENV_POSIX,
+	DALIST_DEBUG_ENV_NT,
+};
+
+
+/* dalist return values */
+#define DALIST_OK			(0x0)
+#define DALIST_EINTERNAL		(0xD0000000)	/* internal error */
+#define DALIST_EMEMFN			(0xD0000001)	/* memory allocation error */
+#define DALIST_EMEMBLOCK		(0xD0000002)	/* invalid memory block */
+#define DALIST_ELIST			(0xD0000003)	/* invalid list */
+#define DALIST_ENODE			(0xD0000004)	/* invalid node */
+#define DALIST_EPARAMMIX		(0xD0000005)	/* invalid parameter mix */
+#define DALIST_EKEYEXISTS		(0xD0000006)	/* key already exists */
+#define DALIST_ELISTNOTEMPTY		(0xD0000007)	/* null insertion point with non-empty list */
+
+/* dalist debug return values */
+#define DALIST_EDEBUGSTRUCT		(0xD0001000)	/* invalid debug structure */
+#define DALIST_EDEBUGENV		(0xD0001001)	/* invalid debug environment */
+#define DALIST_EDEBUGSPRINTF		(0xD0001002)	/* invalid debug pointer to sprintf */
+#define DALIST_EDEBUGWRITE		(0xD0001003)	/* invalid debug pointer to write (posix) */
+#define DALIST_EDEBUGWRITEFILE		(0xD0001004)	/* invalid debug pointer to zw_write_file (nt) */
+
+
+/* dalist node flag bits */
+#define DALIST_NODE_TYPE_NONE		(0x00u)
+#define DALIST_NODE_TYPE_EXISTING	(0x01u)
+#define DALIST_NODE_TYPE_NEW		(0x02u)
+#define DALIST_NODE_TYPE_DELETED	(0x04u)
+#define DALIST_NODE_MEM_BLOCK_BASE	(0x80u)
+
+
+struct dalist_node {
+	struct dalist_node *	prev;
+	struct dalist_node *	next;
+	uintptr_t		any;
+};
+
+
+struct dalist {
+	struct dalist_node *	head;
+	struct dalist_node *	tail;
+};
+
+
+struct dalist_node_ex {
+	struct dalist_node_ex *	prev;
+	struct dalist_node_ex *	next;
+	uintptr_t		key;
+	uintptr_t		flags;
+	uintptr_t		dblock;
+};
+
+
+struct dalist_debug;
+
+struct dalist_ex {
+	void *			head;		/************************************/
+	void *			tail;		/* head, tail, free:                */
+	void *			free;		/* dalist_node when dblock_size is  */
+	uintptr_t *		bookmarks;	/* zero, dalist_node_ex otherwise.  */
+	size_t			dblock_size;	/*                                  */
+	size_t			lblock_size;	/* lblock_size:                     */
+	void *			memfn_ptr;	/* used when memfn_method is mmap   */
+	enum dalist_memfn	memfn_method;	/* or nt_allocate_virtual_memory    */
+	int			memfn_status;	/* as the system call's alloc_size  */
+	int			mmap_prot;	/* argument.                        */
+	int			mmap_flags;	/*                                  */
+	int			mmap_fildes;	/*                                  */
+	intptr_t		mmap_offset;	/************************************/
+	struct dalist_debug *	debug;
+
+	struct dalist_info {
+		uintptr_t	list_nodes;
+		uintptr_t	free_nodes;
+		uintptr_t	bookmark_from;
+		uintptr_t	bookmark_to;
+		uintptr_t	bookmark_key_min;
+		uintptr_t	bookmark_key_max;
+		uintptr_t	nodes_below_first_bookmark;
+		uintptr_t	nodes_above_last_bookmark;
+	} info;
+};
+
+
+/* signatures for caller-provided debug output functions */
+typedef int	__cdecl	  dalist_sprintf(char * buffer, const char * format, ...);
+typedef ssize_t	__cdecl	  dalist_write(int fildes, const void *buf, size_t nbyte);
+typedef int32_t __stdcall dalist_write_file(
+	void *		hfile,
+	void *		hevent,
+	void *		apc_routine,
+	void * 		apc_context,
+	void * 		io_status_block,
+	void * 		buffer,
+	uint32_t	bytes_sent,
+	int64_t *	byte_offset,
+	uint32_t *	key);
+
+
+/* debug */
+struct dalist_debug {
+	enum dalist_dbgenv	dbgenv;
+	dalist_sprintf *	sprintf;	/* required (all) */
+	dalist_write *		write;		/* required (posix only) */
+	dalist_write_file *	zw_write_file;	/* required (nt only) */
+};
+
+
+/* signatures for caller-provided memory allocation functions */
+typedef void * __cdecl dalist_memfn_mmap(
+	void *		addr,
+	size_t		alloc_size,
+	int		prot,
+	int		flags,
+	int		fildes,
+	intptr_t	offset);
+
+
+typedef void * __cdecl dalist_memfn_malloc(
+	size_t		alloc_size);
+
+
+typedef int32_t __stdcall dalist_memfn_nt_allocvm(
+	void *		hprocess,
+	void **		base_address,
+	uint32_t	zero_bits,
+	size_t *	alloc_size,
+	uint32_t	alloc_type,
+	uint32_t	protect);
+
+
+/**
+ *  dalist_memfn_custom:
+ *  must return either DALIST_OK or DALIST_EMEMFN;
+ *  may update the list's memfn_status member
+**/
+typedef int __cdecl dalist_memfn_custom(
+	struct dalist_ex *	dlist,
+	void **			addr,
+	size_t *		alloc_size);
+
+dalist_api
+int dalist_init(struct dalist *	dlist);
+
+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);
+
+dalist_api
+int dalist_insert_before(
+	struct dalist *		dlist,
+	struct dalist_node *	lnode,
+	struct dalist_node *	nnode);
+
+dalist_api
+int dalist_insert_after(
+	struct dalist *		dlist,
+	struct dalist_node *	lnode,
+	struct dalist_node *	nnode);
+
+dalist_api
+int dalist_get_free_node(
+	struct dalist_ex *	dlist,
+	void **			fnode);
+
+dalist_api
+int dalist_deposit_free_node(
+	struct dalist_ex *	dlist,
+	void *			fnode);
+
+dalist_api
+int dalist_deposit_memory_block(
+	struct dalist_ex *	dlist,
+	void *			addr,
+	size_t			alloc_size);
+
+dalist_api
+int dalist_unlink_node(
+	struct dalist *		dlist,
+	struct dalist_node *	node);
+
+dalist_api
+int dalist_unlink_node_ex(
+	struct dalist_ex *	dlist,
+	struct dalist_node_ex *	node);
+
+dalist_api
+int dalist_discard_node(
+	struct dalist_ex *	dlist,
+	struct dalist_node_ex *	node);
+
+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);
+
+dalist_api
+int dalist_insert_node_by_key(
+	struct dalist_ex *	dlist,
+	struct dalist_node_ex *	node);
+
+/* debug routines */
+dalist_api
+int dalist_debug_setup(
+	struct dalist_ex *	dlist,
+	struct dalist_debug *	dlist_debug,
+	enum dalist_dbgenv	dbgenv,
+	dalist_sprintf *	pfn_sprintf,
+	dalist_write *		pfn_write,
+	dalist_write_file *	pfn_write_file);
+
+dalist_api
+int dalist_debug_print(
+	struct dalist_ex *	dlist,
+	intptr_t		fildes_or_hfile);
+
+
+#ifdef __cplusplus
+}
+#endif
+#endif
diff --git a/include/dalist/dalist_api.h b/include/dalist/dalist_api.h
new file mode 100644
index 0000000..b120527
--- /dev/null
+++ b/include/dalist/dalist_api.h
@@ -0,0 +1,32 @@
+#ifndef DALIST_API_H
+#define DALIST_API_H
+
+/* host type (posix-libc/free-standing) */
+#include "dalist_env.h"
+
+/* dalist_export */
+#if	defined(__attr_export__)
+#define dalist_export __attr_export__
+#else
+#define dalist_export
+#endif
+
+/* dalist_import */
+#if	defined(__attr_import__)
+#define dalist_import __attr_import__
+#else
+#define dalist_import
+#endif
+
+/* dalist_api */
+#if     defined (DALIST_BUILD)
+#define dalist_api dalist_export
+#elif   defined (DALIST_SHARED)
+#define dalist_api dalist_import
+#elif   defined (DALIST_STATIC)
+#define dalist_api
+#else
+#define dalist_api
+#endif
+
+#endif
diff --git a/include/dalist/dalist_env.h b/include/dalist/dalist_env.h
new file mode 100644
index 0000000..2f2b57a
--- /dev/null
+++ b/include/dalist/dalist_env.h
@@ -0,0 +1,25 @@
+#ifndef DALIST_ENV_H
+#define DALIST_ENV_H
+
+#if defined (MIDIPIX_FREESTANDING)
+
+#include <psxtypes/psxtypes.h>
+
+#else
+
+#include <stdint.h>
+#include <stdio.h>
+#include <errno.h>
+#include <sys/mman.h>
+
+#ifndef __cdecl
+#define __cdecl
+#endif
+
+#ifndef __stdcall
+#define __stdcall
+#endif
+
+#endif
+
+#endif
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 <dalist/dalist.h>
+#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;
+}
diff --git a/src/dalist_debug.c b/src/dalist_debug.c
new file mode 100644
index 0000000..4461286
--- /dev/null
+++ b/src/dalist_debug.c
@@ -0,0 +1,213 @@
+/*****************************************************************************/
+/*  dalist: a zero-dependency book-keeping library                           */
+/*  Copyright (C) 2013,2014,2015  Z. Gilboa                                  */
+/*  Released under GPLv2 and GPLv3; see COPYING.DALIST.                      */
+/*****************************************************************************/
+
+#include <dalist/dalist.h>
+#include "dalist_impl.h"
+
+dalist_api
+int dalist_debug_setup(
+	struct dalist_ex *	dlist,
+	struct dalist_debug *	dlist_debug,
+	enum dalist_dbgenv	dbgenv,
+	dalist_sprintf *	pfn_sprintf,
+	dalist_write *		pfn_write,
+	dalist_write_file *	pfn_write_file)
+{
+	if (dlist)
+		/* in case we fail */
+		dlist->debug = 0;
+	else
+		return DALIST_ELIST;
+
+	if (!dlist_debug)
+		return DALIST_EDEBUGSTRUCT;
+	else if (!pfn_sprintf)
+		return DALIST_EDEBUGSPRINTF;
+
+	switch (dbgenv) {
+		case DALIST_DEBUG_ENV_POSIX:
+			if (!pfn_write)
+				return DALIST_EDEBUGWRITE;
+			break;
+
+		case DALIST_DEBUG_ENV_NT:
+			if (!pfn_write_file)
+				return DALIST_EDEBUGWRITEFILE;
+			break;
+
+		default:
+			return DALIST_EDEBUGENV;
+	}
+
+	dlist_debug->dbgenv        = dbgenv;
+	dlist_debug->sprintf       = pfn_sprintf;
+	dlist_debug->write         = pfn_write;
+	dlist_debug->zw_write_file = pfn_write_file;
+
+	dlist->debug = dlist_debug;
+
+	return DALIST_OK;
+}
+
+
+static const char dalist_fmt_header_32[] =
+	"dlist:\t\t0x%08x\n"
+	"dlist->head:\t0x%08x\n"
+	"dlist->tail:\t0x%08x\n\n";
+
+static const char dalist_fmt_header_64[] =
+	"dlist:\t\t0x%016x\n"
+	"dlist->head:\t0x%016x\n"
+	"dlist->tail:\t0x%016x\n\n";
+
+static const char dalist_fmt_node_32[] =
+	"node: 0x%08x\t"
+	"prev: 0x%08x\t"
+	"next: 0x%08x\t"
+	"any:  0x%08x\t\n";
+
+static const char dalist_fmt_node_64[] =
+	"node: 0x%016x\t"
+	"prev: 0x%016x\t"
+	"next: 0x%016x\t"
+	"any:  0x%016x\t\n";
+
+
+static int dalist_dbg_write_posix(
+	struct dalist_ex *	dlist,
+	intptr_t		fildes_or_hfile,
+	const void *		buf,
+	size_t			nbyte)
+{
+	int		fildes;
+	dalist_write *	pfn_write;
+	ssize_t		bytes_written;
+
+	fildes = (int)fildes_or_hfile;
+	pfn_write = (dalist_write *)dlist->debug->write;
+
+	bytes_written = pfn_write(fildes,buf,nbyte);
+
+	if (bytes_written == nbyte)
+		return DALIST_OK;
+	else
+		return DALIST_EDEBUGENV;
+}
+
+
+static int dalist_dbg_write_nt(
+	struct dalist_ex *	dlist,
+	intptr_t		fildes_or_hfile,
+	const void *		buf,
+	size_t			nbyte)
+{
+	void *			hfile;
+	dalist_iosb		iosb;
+	dalist_write_file *	pfn_write_file;
+
+	hfile          = (void *)fildes_or_hfile;
+	pfn_write_file = (dalist_write_file *)dlist->debug->zw_write_file;
+
+	return pfn_write_file(
+		hfile,
+		(void *)0,
+		(void *)0,
+		(void *)0,
+		&iosb,
+		(void *)buf,
+		(uint32_t)nbyte,
+		(int64_t *)0,
+		(uint32_t *)0);
+
+	if (iosb.info == nbyte)
+		return DALIST_OK;
+	else
+		return DALIST_EDEBUGENV;
+}
+
+
+dalist_api
+int dalist_debug_print(
+	struct dalist_ex *	dlist,
+	intptr_t		fildes_or_hfile)
+{
+	const char *		fmt_header;
+	const char *		fmt_node;
+	char			dbg_buf[128];
+	intptr_t		nbyte;
+
+	int			status;
+	struct dalist_node *	node;
+	dalist_sprintf *	dbg_sprintf;
+	dalist_dbg_write *	dbg_write;
+
+	if (!dlist)
+		return DALIST_ELIST;
+	else if (!dlist->debug)
+		return DALIST_EDEBUGENV;
+
+	/* initial setup */
+	dbg_sprintf = (dalist_sprintf *)dlist->debug->sprintf;
+
+	if (sizeof(size_t) == 4) {
+		fmt_header = (char *)dalist_fmt_header_32;
+		fmt_node   = (char *)dalist_fmt_node_32;
+	} else if (sizeof(size_t) == 8) {
+		fmt_header = (char *)dalist_fmt_header_64;
+		fmt_node   = (char *)dalist_fmt_node_64;
+	} else
+		return DALIST_EDEBUGENV;
+
+	if (dlist->debug->dbgenv == DALIST_DEBUG_ENV_POSIX)
+		dbg_write = dalist_dbg_write_posix;
+	else if (dlist->debug->dbgenv == DALIST_DEBUG_ENV_NT)
+		dbg_write = dalist_dbg_write_nt;
+	else
+		dbg_write = 0;
+
+	if ((!dbg_sprintf) || (!dbg_write))
+		return DALIST_EDEBUGENV;
+
+	/* print list header */
+	nbyte = dbg_sprintf((char *)dbg_buf,fmt_header,dlist,dlist->head,dlist->tail);
+
+	if (nbyte < 0)
+		return DALIST_EDEBUGENV;
+
+	status = dbg_write(dlist,fildes_or_hfile,dbg_buf,nbyte);
+
+	if (status != NT_STATUS_SUCCESS)
+		return DALIST_EDEBUGENV;
+
+	/* print node information */
+	status = DALIST_OK;
+	node   = (struct dalist_node *)dlist->head;
+
+	while (node && (status == DALIST_OK)) {
+		/* create output line */
+		nbyte = dbg_sprintf(
+			(char *)dbg_buf,
+			fmt_node,
+			node,
+			node->prev,
+			node->next,
+			node->any);
+
+		if (nbyte < 0)
+			return DALIST_EDEBUGENV;
+
+		/* write output line */
+		status = dbg_write(
+			dlist,
+			fildes_or_hfile,
+			dbg_buf,
+			nbyte);
+
+		node = node->next;
+	}
+
+	return DALIST_OK;
+}
diff --git a/src/dalist_impl.h b/src/dalist_impl.h
new file mode 100644
index 0000000..97cef11
--- /dev/null
+++ b/src/dalist_impl.h
@@ -0,0 +1,43 @@
+#include <dalist/dalist.h>
+
+/* internal synonyms and prototypes */
+typedef dalist_memfn_custom	memfn_custom;
+typedef dalist_memfn_mmap	memfn_mmap;
+typedef dalist_memfn_malloc	memfn_malloc;
+typedef dalist_memfn_nt_allocvm	memfn_allocvm;
+
+
+/* memfn_allocvm */
+#define NT_STATUS_SUCCESS		0
+#define NT_CURRENT_PROCESS_HANDLE	(void *)(uintptr_t)-1
+#define NT_PAGE_READWRITE		(0x0004u)
+#define NT_MEM_COMMIT			(0x1000u)
+#define NT_MEM_RESERVE			(0x2000u)
+#define NT_MEM_DECOMMIT			(0x4000u)
+#define NT_MEM_RELEASE			(0x8000u)
+
+/* host environment */
+#if defined (MIDIPIX_FREESTANDING)
+#define dalist_errno(x) x
+#define PROT_READ	1
+#define PROT_WRITE	2
+#define MAP_ANON	0x20
+#define MAP_SHARED	0x01
+#else
+#define dalist_errno(x) errno
+#endif
+
+typedef struct _dalist_io_status_block {
+	union {
+		int32_t		status;
+		void *		pointer;
+	};
+	intptr_t		info;
+} dalist_io_status_block, dalist_iosb;
+
+
+typedef int dalist_dbg_write(
+	struct dalist_ex *	dlist,
+	intptr_t		fildes_or_hfile,
+	const void *		buf,
+	size_t			nbyte);
diff --git a/src/dalist_lib_entry_point.c b/src/dalist_lib_entry_point.c
new file mode 100644
index 0000000..d4124ed
--- /dev/null
+++ b/src/dalist_lib_entry_point.c
@@ -0,0 +1,12 @@
+#ifdef MIDIPIX_FREESTANDING
+
+#include <dalist/dalist.h>
+
+int __stdcall dalist_lib_entry_point(
+	void *		hinstance,
+	uint32_t	reason,
+	void *		reserved)
+{
+	return 1;
+}
+#endif
diff --git a/src/dalist_memfn.c b/src/dalist_memfn.c
new file mode 100644
index 0000000..e1fa9f0
--- /dev/null
+++ b/src/dalist_memfn.c
@@ -0,0 +1,267 @@
+/*****************************************************************************/
+/*  dalist: a zero-dependency book-keeping library                           */
+/*  Copyright (C) 2013,2014,2015  Z. Gilboa                                  */
+/*  Released under GPLv2 and GPLv3; see COPYING.DALIST.                      */
+/*****************************************************************************/
+
+#include <dalist/dalist.h>
+#include "dalist_impl.h"
+
+/* private prototypes */
+static void * dalist_alloc(struct dalist_ex * dlist);
+
+static int dalist_memfn_internal(
+	struct dalist_ex *	dlist,
+	void **			addr,
+	size_t *		alloc_size);
+
+
+dalist_api
+int dalist_get_free_node(
+	struct dalist_ex *	dlist,
+	void **			fnode)
+{
+	int			ret;
+	struct dalist_node *	nfree;
+
+	/* in case we fail */
+	*fnode = (void *)0;
+
+	if (dlist->free)
+		/* allocation is not needed */
+		nfree  = (struct dalist_node *)dlist->free;
+	else
+		nfree = (struct dalist_node *)dalist_alloc(dlist);
+
+	if (nfree) {
+		*fnode = nfree;
+		dlist->free = nfree->next;
+
+		if (nfree->next) /* new head of dlist->free */
+			nfree->next->prev = 0;
+
+		/* bookkeeping */
+		dlist->info.free_nodes--;
+
+		/* and for good measure */
+		nfree->prev = nfree->next = 0;
+		ret = DALIST_OK;
+	} else
+		ret = DALIST_EMEMFN;
+
+	return ret;
+}
+
+
+dalist_api
+int dalist_deposit_free_node(
+	struct dalist_ex *	dlist,
+	void *			fnode)
+{
+	int			ret;
+	struct dalist_node *	nfree;
+
+	if (fnode) {
+		nfree       = (struct dalist_node *)fnode;
+		nfree->next = (struct dalist_node *)dlist->free;
+
+		/* fnode is now the head free node */
+		nfree->prev = 0;
+		dlist->free = fnode;
+
+		/* bookkeeping */
+		dlist->info.free_nodes++;
+		ret = DALIST_OK;
+	} else {
+		ret = DALIST_ENODE;
+	}
+
+	return ret;
+}
+
+
+dalist_api
+int dalist_deposit_memory_block(
+	struct dalist_ex *	dlist,
+	void *			addr,
+	size_t			alloc_size)
+{
+	struct dalist_node *	fnode;
+	struct dalist_node *	fnode_next;
+	char *			naddr;
+	char *			naddr_next;
+	char *			naddr_upper;
+	size_t			node_size;
+
+	/* node_size: before alignment */
+	if (dlist->dblock_size == 0)
+		node_size = sizeof(struct dalist_node);
+	else
+		node_size = (size_t)&((struct dalist_node_ex *)0)->dblock
+				+ dlist->dblock_size;
+
+	/* node_size: after alignment */
+	node_size += sizeof(uintptr_t)-1;
+	node_size |= sizeof(uintptr_t)-1;
+	node_size ^= sizeof(uintptr_t)-1;
+
+	/* validate block size */
+	if (alloc_size < node_size)
+		return DALIST_EMEMBLOCK;
+
+	/* marks */
+	naddr       = (char *)addr;
+	naddr_next  = naddr + node_size;
+	naddr_upper = naddr + alloc_size;
+
+	/* chain of free nodes */
+	while ((naddr_next + node_size) < naddr_upper) {
+		fnode      = (struct dalist_node *)naddr;
+		fnode_next = (struct dalist_node *)naddr_next;
+
+		fnode->next      = fnode_next;
+		fnode_next->prev = fnode;
+
+		naddr      += node_size;
+		naddr_next += node_size;
+	}
+
+	/* free nodes block: head and tail */
+	fnode       = (struct dalist_node *)addr;
+	fnode_next  = (struct dalist_node *)naddr;
+
+	if (dlist->free) {
+		/* link with pre-allocated free nodes */
+		fnode_next->next = (struct dalist_node *)dlist->free;
+		((struct dalist_node *)dlist->free)->prev = fnode_next;
+	} else {
+		/* no pre-allocated free nodes */
+		fnode_next->next = 0;
+	}
+
+	/* fnode is now the head free node */
+	fnode->prev = 0;
+	dlist->free = fnode;
+
+	/* bookkeeping */
+	dlist->info.free_nodes += (alloc_size / node_size);
+
+	return DALIST_OK;
+}
+
+
+static void * __cdecl dalist_alloc(struct dalist_ex * dlist)
+{
+	int			ret;
+	void *			addr;
+	size_t			alloc_size;
+	memfn_custom *		pmemfn;
+	struct dalist_node *	fnode;
+
+	/* pmemfn */
+	if (dlist->memfn_method == DALIST_MEMFN_CUSTOM)
+		pmemfn = (dalist_memfn_custom *)dlist->memfn_ptr;
+	else
+		pmemfn = dalist_memfn_internal;
+
+	/* allocate: try */
+	fnode = 0;
+	ret   = pmemfn(dlist,&addr,&alloc_size);
+
+	/* allocate: verify */
+	if (ret == DALIST_OK) {
+		if (dlist->memfn_method == DALIST_MEMFN_MALLOC)
+			fnode = (struct dalist_node *)addr;
+		else if (dalist_deposit_memory_block(
+				dlist,
+				addr,
+				alloc_size) == DALIST_OK)
+			fnode = (struct dalist_node *)dlist->free;
+	}
+
+	return fnode;
+}
+
+
+static int __cdecl dalist_memfn_internal(
+	struct dalist_ex *	dlist,
+	void **			address,
+	size_t *		alloc_size)
+{
+	int		ret;
+	void *		addr;
+	size_t		size;
+
+	memfn_mmap *	pfn_mmap;
+	memfn_malloc *	pfn_malloc;
+	memfn_allocvm * pfn_allocvm;
+
+	switch (dlist->memfn_method) {
+		case DALIST_MEMFN_MALLOC:
+			if (dlist->dblock_size == 0)
+				size = sizeof(struct dalist_node);
+			else
+				size = (size_t)((struct dalist_node_ex *)0)->dblock
+					+ dlist->dblock_size;
+
+			pfn_malloc = (memfn_malloc * )dlist->memfn_ptr;
+			addr = pfn_malloc(size);
+
+			if (addr) {
+				*address = addr;
+				*alloc_size = size;
+				ret = dlist->memfn_status = DALIST_OK;
+			} else {
+				ret = DALIST_EMEMFN;
+				dlist->memfn_status = dalist_errno(ret);
+			}
+			break;
+
+		case DALIST_MEMFN_MMAP:
+			pfn_mmap = (memfn_mmap * )dlist->memfn_ptr;
+
+			addr = pfn_mmap(
+				(void *)0,
+				dlist->lblock_size,
+				PROT_READ | PROT_WRITE,
+				MAP_ANON | MAP_SHARED,
+				0,0);
+
+			if (addr) {
+				*address = addr;
+				*alloc_size = dlist->lblock_size;
+				ret = dlist->memfn_status = DALIST_OK;
+			} else {
+				ret = DALIST_EMEMFN;
+				dlist->memfn_status = dalist_errno(ret);
+			}
+			break;
+
+		case DALIST_MEMFN_NT_ALLOCATE_VIRTUAL_MEMORY:
+			addr       = (void *)0;
+			size = dlist->lblock_size;
+			pfn_allocvm = (memfn_allocvm * )dlist->memfn_ptr;
+
+			dlist->memfn_status = pfn_allocvm(
+				NT_CURRENT_PROCESS_HANDLE,
+				&addr,
+				0,
+				&size,
+				NT_MEM_COMMIT,
+				NT_PAGE_READWRITE);
+
+			if (dlist->memfn_status == NT_STATUS_SUCCESS) {
+				*address = addr;
+				*alloc_size = size;
+				ret = DALIST_OK;
+			} else {
+				ret = DALIST_EMEMFN;
+			}
+			break;
+		default:
+			ret = DALIST_EINTERNAL;
+			break;
+	}
+
+	return ret;
+}