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

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;
 }