summaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile.in14
-rw-r--r--config.lzy28
-rwxr-xr-xconfigure115
-rw-r--r--dalist.lzy127
-rw-r--r--include/dalist/dalist.h256
-rw-r--r--include/dalist/dalist_api.h32
-rw-r--r--include/dalist/dalist_env.h25
-rw-r--r--src/dalist.c297
-rw-r--r--src/dalist_debug.c213
-rw-r--r--src/dalist_impl.h43
-rw-r--r--src/dalist_lib_entry_point.c12
-rw-r--r--src/dalist_memfn.c267
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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-21 18:04:38 +0000