summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2014-09-22 21:52:15 +0000
committerDavid Robillard <d@drobilla.net>2014-09-22 21:52:15 +0000
commit624b19b492df58075e64572bb0630693f447f2ce (patch)
treeba583a27d5abb161bd6ca294c93f74fc756a3613
parentb5896fff67d150e6ba96cea7d3679f9958b787ea (diff)
downloadzix-624b19b492df58075e64572bb0630693f447f2ce.tar.gz
zix-624b19b492df58075e64572bb0630693f447f2ce.tar.bz2
zix-624b19b492df58075e64572bb0630693f447f2ce.zip
Gracefully handle memory allocation failure.
100% test coverage for hash.c. git-svn-id: http://svn.drobilla.net/zix/trunk@85 df6676b4-ccc9-40e5-b5d6-7c4628a128e3
-rw-r--r--test/hash_test.c50
-rw-r--r--wscript4
-rw-r--r--zix/btree.c56
-rw-r--r--zix/hash.c21
4 files changed, 99 insertions, 32 deletions
diff --git a/test/hash_test.c b/test/hash_test.c
index 9b48db1..aeafc06 100644
--- a/test/hash_test.c
+++ b/test/hash_test.c
@@ -1,5 +1,5 @@
/*
- Copyright 2011 David Robillard <http://drobilla.net>
+ Copyright 2011-2014 David Robillard <http://drobilla.net>
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
@@ -18,8 +18,11 @@
#include <stdio.h>
#include <string.h>
+#include "test_malloc.h"
#include "zix/hash.h"
+static bool expect_failure = false;
+
static const char* strings[] = {
"one", "two", "three", "four", "five", "six", "seven", "eight",
"2one", "2two", "2three", "2four", "2five", "2six", "2seven", "2eight",
@@ -39,6 +42,9 @@ static const char* strings[] = {
static int
test_fail(const char* fmt, ...)
{
+ if (expect_failure) {
+ return 0;
+ }
va_list args;
va_start(args, fmt);
fprintf(stderr, "error: ");
@@ -77,27 +83,41 @@ string_ptr_equal(const void* a, const void* b)
return !strcmp(*(const char*const*)a, *(const char*const*)b);
}
-int
-main(int argc, char** argv)
+static int
+stress(void)
{
ZixHash* hash = zix_hash_new(
string_ptr_hash, string_ptr_equal, sizeof(const char*));
+ if (!hash) {
+ return test_fail("Failed to allocate hash\n");
+ }
const size_t n_strings = sizeof(strings) / sizeof(const char*);
// Insert each string
for (size_t i = 0; i < n_strings; ++i) {
- ZixStatus st = zix_hash_insert(hash, &strings[i], NULL);
+ const void* inserted = NULL;
+ ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
if (st) {
return test_fail("Failed to insert `%s'\n", strings[i]);
+ } else if (*(const void*const*)inserted != strings[i]) {
+ return test_fail("Corrupt insertion %s != %s\n",
+ strings[i], *(const char*const*)inserted);
}
}
+ // Ensure hash size is correct
+ if (zix_hash_size(hash) != n_strings) {
+ return test_fail("Hash size %zu != %zu\n",
+ zix_hash_size(hash), n_strings);
+ }
+
//zix_hash_print_dot(hash, stdout);
// Attempt to insert each string again
for (size_t i = 0; i < n_strings; ++i) {
- ZixStatus st = zix_hash_insert(hash, &strings[i], NULL);
+ const void* inserted = NULL;
+ ZixStatus st = zix_hash_insert(hash, &strings[i], &inserted);
if (st != ZIX_STATUS_EXISTS) {
return test_fail("Double inserted `%s'\n", strings[i]);
}
@@ -176,3 +196,23 @@ main(int argc, char** argv)
return 0;
}
+
+int
+main(int argc, char** argv)
+{
+ if (stress()) {
+ return 1;
+ }
+
+ const size_t total_n_allocs = test_malloc_get_n_allocs();
+ printf("Testing 0 ... %zu failed allocations\n", total_n_allocs);
+ expect_failure = true;
+ for (size_t i = 0; i < total_n_allocs; ++i) {
+ test_malloc_reset(i);
+ stress();
+ }
+
+ test_malloc_reset((size_t)-1);
+
+ return 0;
+}
diff --git a/wscript b/wscript
index 63259fa..f3e350d 100644
--- a/wscript
+++ b/wscript
@@ -124,7 +124,7 @@ def build(bld):
'-DZIX_INTERNAL'])
if bld.env.BUILD_TESTS:
- test_libs = ['pthread']
+ test_libs = ['pthread', 'dl']
test_cflags = []
if bld.env.MSVC_COMPILER:
test_libs = []
@@ -146,7 +146,7 @@ def build(bld):
# Unit test programs
for i in tests:
obj = bld(features = 'c cprogram',
- source = 'test/%s.c' % i,
+ source = ['test/%s.c' % i, 'test/test_malloc.c'],
includes = ['.'],
use = 'libzix_profiled',
lib = test_libs,
diff --git a/zix/btree.c b/zix/btree.c
index 5c4d2a9..b9c001c 100644
--- a/zix/btree.c
+++ b/zix/btree.c
@@ -92,12 +92,14 @@ print_tree(const ZixBTreeNode* parent, const ZixBTreeNode* node, int level)
#endif // ZIX_BTREE_DEBUG
ZIX_PRIVATE ZixBTreeNode*
-zix_btree_alloc_node(const bool leaf)
+zix_btree_node_new(const bool leaf)
{
assert(sizeof(ZixBTreeNode) == ZIX_BTREE_PAGE_SIZE);
ZixBTreeNode* node = (ZixBTreeNode*)malloc(sizeof(ZixBTreeNode));
- node->is_leaf = leaf;
- node->n_vals = 0;
+ if (node) {
+ node->is_leaf = leaf;
+ node->n_vals = 0;
+ }
return node;
}
@@ -107,12 +109,14 @@ zix_btree_new(const ZixComparator cmp,
const ZixDestroyFunc destroy)
{
ZixBTree* t = (ZixBTree*)malloc(sizeof(ZixBTree));
- t->root = zix_btree_alloc_node(true);
- t->destroy = destroy;
- t->cmp = cmp;
- t->cmp_data = cmp_data;
- t->size = 0;
- t->height = 1;
+ if (t) {
+ t->root = zix_btree_node_new(true);
+ t->destroy = destroy;
+ t->cmp = cmp;
+ t->cmp_data = cmp_data;
+ t->size = 0;
+ t->height = 1;
+ }
return t;
}
@@ -192,8 +196,11 @@ zix_btree_split_child(ZixBTreeNode* const n,
assert(i < n->n_vals + 1);
assert(n->children[i] == lhs);
- ZixBTreeNode* rhs = zix_btree_alloc_node(lhs->is_leaf);
const unsigned max_n_vals = zix_btree_max_vals(lhs);
+ ZixBTreeNode* rhs = zix_btree_node_new(lhs->is_leaf);
+ if (!rhs) {
+ return NULL;
+ }
// LHS and RHS get roughly half, less the middle value which moves up
lhs->n_vals = max_n_vals / 2;
@@ -258,13 +265,20 @@ zix_btree_insert(ZixBTree* const t, void* const e)
// Node is full, split to ensure there is space for a leaf split
if (!parent) {
// Root is full, grow tree upwards
- t->root = parent = zix_btree_alloc_node(false);
+ if (!(parent = zix_btree_node_new(false))) {
+ return ZIX_STATUS_NO_MEM;
+ }
+ t->root = parent;
parent->children[0] = n;
++t->height;
}
ZixBTreeNode* const rhs = zix_btree_split_child(parent, i, n);
- const int cmp = t->cmp(e, parent->vals[i], t->cmp_data);
+ if (!rhs) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
+ const int cmp = t->cmp(e, parent->vals[i], t->cmp_data);
if (cmp == 0) {
return ZIX_STATUS_EXISTS;
} else if (cmp > 0) {
@@ -504,9 +518,11 @@ zix_btree_remove(ZixBTree* const t, const void* const e)
ZIX_PRIVATE ZixBTreeIter*
zix_btree_iter_new(const ZixBTree* const t)
{
- ZixBTreeIter* const i = (ZixBTreeIter*)malloc(
- sizeof(ZixBTreeIter) + t->height * sizeof(ZixBTreeIterFrame));
- i->level = 0;
+ const size_t s = t->height * sizeof(ZixBTreeIterFrame);
+ ZixBTreeIter* const i = (ZixBTreeIter*)malloc(sizeof(ZixBTreeIter) + s);
+ if (i) {
+ i->level = 0;
+ }
return i;
}
@@ -518,6 +534,10 @@ zix_btree_find(const ZixBTree* const t,
ZixBTreeNode* n = t->root;
*ti = zix_btree_iter_new(t);
+ if (!*ti) {
+ return ZIX_STATUS_NO_MEM;
+ }
+
while (n) {
bool equal = false;
const unsigned i = zix_btree_node_find(t, n, e, &equal);
@@ -553,7 +573,9 @@ ZIX_API ZixBTreeIter*
zix_btree_begin(const ZixBTree* const t)
{
ZixBTreeIter* const i = zix_btree_iter_new(t);
- if (t->size == 0) {
+ if (!i) {
+ return NULL;
+ } else if (t->size == 0) {
i->stack[0].node = NULL;
} else {
ZixBTreeNode* n = t->root;
@@ -572,7 +594,7 @@ zix_btree_begin(const ZixBTree* const t)
ZIX_API bool
zix_btree_iter_is_end(const ZixBTreeIter* const i)
{
- return i->stack[0].node == NULL;
+ return !i || i->stack[0].node == NULL;
}
ZIX_API void
diff --git a/zix/hash.c b/zix/hash.c
index b24ee78..5d2b18c 100644
--- a/zix/hash.c
+++ b/zix/hash.c
@@ -1,5 +1,5 @@
/*
- Copyright 2011 David Robillard <http://drobilla.net>
+ Copyright 2011-2014 David Robillard <http://drobilla.net>
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
@@ -58,13 +58,18 @@ zix_hash_new(ZixHashFunc hash_func,
size_t value_size)
{
ZixHash* hash = (ZixHash*)malloc(sizeof(ZixHash));
- hash->hash_func = hash_func;
- hash->equal_func = equal_func;
- hash->n_buckets = &sizes[0];
- hash->value_size = value_size;
- hash->count = 0;
- hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
- sizeof(ZixHashEntry*));
+ if (hash) {
+ hash->hash_func = hash_func;
+ hash->equal_func = equal_func;
+ hash->n_buckets = &sizes[0];
+ hash->value_size = value_size;
+ hash->count = 0;
+ if (!(hash->buckets = (ZixHashEntry**)calloc(*hash->n_buckets,
+ sizeof(ZixHashEntry*)))) {
+ free(hash);
+ return NULL;
+ }
+ }
return hash;
}