diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/dalist.c | 297 | ||||
| -rw-r--r-- | src/dalist_debug.c | 213 | ||||
| -rw-r--r-- | src/dalist_impl.h | 43 | ||||
| -rw-r--r-- | src/dalist_lib_entry_point.c | 12 | ||||
| -rw-r--r-- | src/dalist_memfn.c | 267 |
5 files changed, 832 insertions, 0 deletions
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; +} |