Add testing and start testing hash table functionality.

4 files changed, 704 insertions, 0 deletions

diff --git a/tests/cutest/CuTest.c b/tests/cutest/CuTest.c
new file mode 100644
index 0000000..dc7ebd9
--- /dev/null
+++ b/tests/cutest/CuTest.c
@@ -0,0 +1,339 @@
+#include <assert.h>
+#include <setjmp.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+#include "CuTest.h"
+
+/*-------------------------------------------------------------------------*
+ * CuStr
+ *-------------------------------------------------------------------------*/
+
+char* CuStrAlloc(int size)
+{
+	char* newStr = (char*) malloc( sizeof(char) * (size) );
+	return newStr;
+}
+
+char* CuStrCopy(const char* old)
+{
+	int len = strlen(old);
+	char* newStr = CuStrAlloc(len + 1);
+	strcpy(newStr, old);
+	return newStr;
+}
+
+/*-------------------------------------------------------------------------*
+ * CuString
+ *-------------------------------------------------------------------------*/
+
+void CuStringInit(CuString* str)
+{
+	str->length = 0;
+	str->size = STRING_MAX;
+	str->buffer = (char*) malloc(sizeof(char) * str->size);
+	str->buffer[0] = '\0';
+}
+
+CuString* CuStringNew(void)
+{
+	CuString* str = (CuString*) malloc(sizeof(CuString));
+	str->length = 0;
+	str->size = STRING_MAX;
+	str->buffer = (char*) malloc(sizeof(char) * str->size);
+	str->buffer[0] = '\0';
+	return str;
+}
+
+void CuStringDelete(CuString *str)
+{
+        if (!str) return;
+        free(str->buffer);
+        free(str);
+}
+
+void CuStringResize(CuString* str, int newSize)
+{
+	str->buffer = (char*) realloc(str->buffer, sizeof(char) * newSize);
+	str->size = newSize;
+}
+
+void CuStringAppend(CuString* str, const char* text)
+{
+	int length;
+
+	if (text == NULL) {
+		text = "NULL";
+	}
+
+	length = strlen(text);
+	if (str->length + length + 1 >= str->size)
+		CuStringResize(str, str->length + length + 1 + STRING_INC);
+	str->length += length;
+	strcat(str->buffer, text);
+}
+
+void CuStringAppendChar(CuString* str, char ch)
+{
+	char text[2];
+	text[0] = ch;
+	text[1] = '\0';
+	CuStringAppend(str, text);
+}
+
+void CuStringAppendFormat(CuString* str, const char* format, ...)
+{
+	va_list argp;
+	char buf[HUGE_STRING_LEN];
+	va_start(argp, format);
+	vsprintf(buf, format, argp);
+	va_end(argp);
+	CuStringAppend(str, buf);
+}
+
+void CuStringInsert(CuString* str, const char* text, int pos)
+{
+	int length = strlen(text);
+	if (pos > str->length)
+		pos = str->length;
+	if (str->length + length + 1 >= str->size)
+		CuStringResize(str, str->length + length + 1 + STRING_INC);
+	memmove(str->buffer + pos + length, str->buffer + pos, (str->length - pos) + 1);
+	str->length += length;
+	memcpy(str->buffer + pos, text, length);
+}
+
+/*-------------------------------------------------------------------------*
+ * CuTest
+ *-------------------------------------------------------------------------*/
+
+void CuTestInit(CuTest* t, const char* name, TestFunction function)
+{
+	t->name = CuStrCopy(name);
+	t->failed = 0;
+	t->ran = 0;
+	t->message = NULL;
+	t->function = function;
+	t->jumpBuf = NULL;
+}
+
+CuTest* CuTestNew(const char* name, TestFunction function)
+{
+	CuTest* tc = CU_ALLOC(CuTest);
+	CuTestInit(tc, name, function);
+	return tc;
+}
+
+void CuTestDelete(CuTest *t)
+{
+        if (!t) return;
+        free(t->name);
+        free(t);
+}
+
+void CuTestRun(CuTest* tc)
+{
+	jmp_buf buf;
+	tc->jumpBuf = &buf;
+	if (setjmp(buf) == 0)
+	{
+		tc->ran = 1;
+		(tc->function)(tc);
+	}
+	tc->jumpBuf = 0;
+}
+
+static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* string)
+{
+	char buf[HUGE_STRING_LEN];
+
+	sprintf(buf, "%s:%d: ", file, line);
+	CuStringInsert(string, buf, 0);
+
+	tc->failed = 1;
+	tc->message = string->buffer;
+	if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0);
+}
+
+void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message)
+{
+	CuString string;
+
+	CuStringInit(&string);
+	if (message2 != NULL)
+	{
+		CuStringAppend(&string, message2);
+		CuStringAppend(&string, ": ");
+	}
+	CuStringAppend(&string, message);
+	CuFailInternal(tc, file, line, &string);
+}
+
+void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition)
+{
+	if (condition) return;
+	CuFail_Line(tc, file, line, NULL, message);
+}
+
+void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,
+	const char* expected, const char* actual)
+{
+	CuString string;
+	if ((expected == NULL && actual == NULL) ||
+	    (expected != NULL && actual != NULL &&
+	     strcmp(expected, actual) == 0))
+	{
+		return;
+	}
+
+	CuStringInit(&string);
+	if (message != NULL)
+	{
+		CuStringAppend(&string, message);
+		CuStringAppend(&string, ": ");
+	}
+	CuStringAppend(&string, "expected <");
+	CuStringAppend(&string, expected);
+	CuStringAppend(&string, "> but was <");
+	CuStringAppend(&string, actual);
+	CuStringAppend(&string, ">");
+	CuFailInternal(tc, file, line, &string);
+}
+
+void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,
+	int expected, int actual)
+{
+	char buf[STRING_MAX];
+	if (expected == actual) return;
+	sprintf(buf, "expected <%d> but was <%d>", expected, actual);
+	CuFail_Line(tc, file, line, message, buf);
+}
+
+void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,
+	double expected, double actual, double delta)
+{
+	char buf[STRING_MAX];
+	if (fabs(expected - actual) <= delta) return;
+	sprintf(buf, "expected <%f> but was <%f>", expected, actual);
+
+	CuFail_Line(tc, file, line, message, buf);
+}
+
+void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,
+	void* expected, void* actual)
+{
+	char buf[STRING_MAX];
+	if (expected == actual) return;
+	sprintf(buf, "expected pointer <0x%p> but was <0x%p>", expected, actual);
+	CuFail_Line(tc, file, line, message, buf);
+}
+
+
+/*-------------------------------------------------------------------------*
+ * CuSuite
+ *-------------------------------------------------------------------------*/
+
+void CuSuiteInit(CuSuite* testSuite)
+{
+	testSuite->count = 0;
+	testSuite->failCount = 0;
+        memset(testSuite->list, 0, sizeof(testSuite->list));
+}
+
+CuSuite* CuSuiteNew(void)
+{
+	CuSuite* testSuite = CU_ALLOC(CuSuite);
+	CuSuiteInit(testSuite);
+	return testSuite;
+}
+
+void CuSuiteDelete(CuSuite *testSuite)
+{
+        unsigned int n;
+        for (n=0; n < MAX_TEST_CASES; n++)
+        {
+                if (testSuite->list[n])
+                {
+                        CuTestDelete(testSuite->list[n]);
+                }
+        }
+        free(testSuite);
+
+}
+
+void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase)
+{
+	assert(testSuite->count < MAX_TEST_CASES);
+	testSuite->list[testSuite->count] = testCase;
+	testSuite->count++;
+}
+
+void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2)
+{
+	int i;
+	for (i = 0 ; i < testSuite2->count ; ++i)
+	{
+		CuTest* testCase = testSuite2->list[i];
+		CuSuiteAdd(testSuite, testCase);
+	}
+}
+
+void CuSuiteRun(CuSuite* testSuite)
+{
+	int i;
+	for (i = 0 ; i < testSuite->count ; ++i)
+	{
+		CuTest* testCase = testSuite->list[i];
+		CuTestRun(testCase);
+		if (testCase->failed) { testSuite->failCount += 1; }
+	}
+}
+
+void CuSuiteSummary(CuSuite* testSuite, CuString* summary)
+{
+	int i;
+	for (i = 0 ; i < testSuite->count ; ++i)
+	{
+		CuTest* testCase = testSuite->list[i];
+		CuStringAppend(summary, testCase->failed ? "F" : ".");
+	}
+	CuStringAppend(summary, "\n\n");
+}
+
+void CuSuiteDetails(CuSuite* testSuite, CuString* details)
+{
+	int i;
+	int failCount = 0;
+
+	if (testSuite->failCount == 0)
+	{
+		int passCount = testSuite->count - testSuite->failCount;
+		const char* testWord = passCount == 1 ? "test" : "tests";
+		CuStringAppendFormat(details, "OK (%d %s)\n", passCount, testWord);
+	}
+	else
+	{
+		if (testSuite->failCount == 1)
+			CuStringAppend(details, "There was 1 failure:\n");
+		else
+			CuStringAppendFormat(details, "There were %d failures:\n", testSuite->failCount);
+
+		for (i = 0 ; i < testSuite->count ; ++i)
+		{
+			CuTest* testCase = testSuite->list[i];
+			if (testCase->failed)
+			{
+				failCount++;
+				CuStringAppendFormat(details, "%d) %s: %s\n",
+					failCount, testCase->name, testCase->message);
+			}
+		}
+		CuStringAppend(details, "\n!!!FAILURES!!!\n");
+
+		CuStringAppendFormat(details, "Runs: %d ",   testSuite->count);
+		CuStringAppendFormat(details, "Passes: %d ", testSuite->count - testSuite->failCount);
+		CuStringAppendFormat(details, "Fails: %d\n",  testSuite->failCount);
+	}
+}
diff --git a/tests/cutest/CuTest.h b/tests/cutest/CuTest.h
new file mode 100644
index 0000000..6246eee
--- /dev/null
+++ b/tests/cutest/CuTest.h
@@ -0,0 +1,116 @@
+#ifndef CU_TEST_H
+#define CU_TEST_H
+
+#include <setjmp.h>
+#include <stdarg.h>
+
+#define CUTEST_VERSION  "CuTest 1.5"
+
+/* CuString */
+
+char* CuStrAlloc(int size);
+char* CuStrCopy(const char* old);
+
+#define CU_ALLOC(TYPE)		((TYPE*) malloc(sizeof(TYPE)))
+
+#define HUGE_STRING_LEN	8192
+#define STRING_MAX		256
+#define STRING_INC		256
+
+typedef struct
+{
+	int length;
+	int size;
+	char* buffer;
+} CuString;
+
+void CuStringInit(CuString* str);
+CuString* CuStringNew(void);
+void CuStringRead(CuString* str, const char* path);
+void CuStringAppend(CuString* str, const char* text);
+void CuStringAppendChar(CuString* str, char ch);
+void CuStringAppendFormat(CuString* str, const char* format, ...);
+void CuStringInsert(CuString* str, const char* text, int pos);
+void CuStringResize(CuString* str, int newSize);
+void CuStringDelete(CuString* str);
+
+/* CuTest */
+
+typedef struct CuTest CuTest;
+
+typedef void (*TestFunction)(CuTest *);
+
+struct CuTest
+{
+	char* name;
+	TestFunction function;
+	int failed;
+	int ran;
+	const char* message;
+	jmp_buf *jumpBuf;
+};
+
+void CuTestInit(CuTest* t, const char* name, TestFunction function);
+CuTest* CuTestNew(const char* name, TestFunction function);
+void CuTestRun(CuTest* tc);
+void CuTestDelete(CuTest *t);
+
+/* Internal versions of assert functions -- use the public versions */
+void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message);
+void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition);
+void CuAssertStrEquals_LineMsg(CuTest* tc,
+	const char* file, int line, const char* message,
+	const char* expected, const char* actual);
+void CuAssertIntEquals_LineMsg(CuTest* tc,
+	const char* file, int line, const char* message,
+	int expected, int actual);
+void CuAssertDblEquals_LineMsg(CuTest* tc,
+	const char* file, int line, const char* message,
+	double expected, double actual, double delta);
+void CuAssertPtrEquals_LineMsg(CuTest* tc,
+	const char* file, int line, const char* message,
+	void* expected, void* actual);
+
+/* public assert functions */
+
+#define CuFail(tc, ms)                        CuFail_Line(  (tc), __FILE__, __LINE__, NULL, (ms))
+#define CuAssert(tc, ms, cond)                CuAssert_Line((tc), __FILE__, __LINE__, (ms), (cond))
+#define CuAssertTrue(tc, cond)                CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))
+
+#define CuAssertStrEquals(tc,ex,ac)           CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))
+#define CuAssertStrEquals_Msg(tc,ms,ex,ac)    CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))
+#define CuAssertIntEquals(tc,ex,ac)           CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))
+#define CuAssertIntEquals_Msg(tc,ms,ex,ac)    CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))
+#define CuAssertDblEquals(tc,ex,ac,dl)        CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac),(dl))
+#define CuAssertDblEquals_Msg(tc,ms,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac),(dl))
+#define CuAssertPtrEquals(tc,ex,ac)           CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))
+#define CuAssertPtrEquals_Msg(tc,ms,ex,ac)    CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))
+
+#define CuAssertPtrNotNull(tc,p)        CuAssert_Line((tc),__FILE__,__LINE__,"null pointer unexpected",(p != NULL))
+#define CuAssertPtrNotNullMsg(tc,msg,p) CuAssert_Line((tc),__FILE__,__LINE__,(msg),(p != NULL))
+
+/* CuSuite */
+
+#define MAX_TEST_CASES	1024
+
+#define SUITE_ADD_TEST(SUITE,TEST)	CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))
+
+typedef struct
+{
+	int count;
+	CuTest* list[MAX_TEST_CASES];
+	int failCount;
+
+} CuSuite;
+
+
+void CuSuiteInit(CuSuite* testSuite);
+CuSuite* CuSuiteNew(void);
+void CuSuiteDelete(CuSuite *testSuite);
+void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase);
+void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2);
+void CuSuiteRun(CuSuite* testSuite);
+void CuSuiteSummary(CuSuite* testSuite, CuString* summary);
+void CuSuiteDetails(CuSuite* testSuite, CuString* details);
+
+#endif /* CU_TEST_H */
diff --git a/tests/cutest/README.txt b/tests/cutest/README.txt
new file mode 100644
index 0000000..96e8853
--- /dev/null
+++ b/tests/cutest/README.txt
@@ -0,0 +1,211 @@
+HOW TO USE
+
+You can use CuTest to create unit tests to drive your development
+in the style of Extreme Programming. You can also add unit tests to
+existing code to ensure that it works as you suspect.
+
+Your unit tests are an investment. They let you to change your
+code and add new features confidently without worrying about
+accidentally breaking earlier features.
+
+
+LICENSING
+
+For details on licensing see license.txt.
+
+
+GETTING STARTED
+
+To add unit testing to your C code the only files you need are
+CuTest.c and CuTest.h.
+
+CuTestTest.c and AllTests.c have been included to provide an
+example of how to write unit tests and then how to aggregate them
+into suites and into a single AllTests.c file. Suites allow you
+to put group tests into logical sets. AllTests.c combines all the
+suites and runs them.
+
+You should not have to look inside CuTest.c. Looking in
+CuTestTest.c and AllTests.c (for example usage) should be
+sufficient.
+
+After downloading the sources, run your compiler to create an
+executable called AllTests.exe. For example, if you are using
+Windows with the cl.exe compiler you would type:
+
+    cl.exe AllTests.c CuTest.c CuTestTest.c
+    AllTests.exe
+
+This will run all the unit tests associated with CuTest and print
+the output on the console. You can replace cl.exe with gcc or
+your favorite compiler in the command above.
+
+
+DETAILED EXAMPLE
+
+Here is a more detailed example. We will work through a simple
+test first exercise. The goal is to create a library of string
+utilities. First, lets write a function that converts a
+null-terminated string to all upper case.
+
+Ensure that CuTest.c and CuTest.h are accessible from your C
+project. Next, create a file called StrUtil.c with these
+contents:
+
+    #include "CuTest.h"
+
+    char* StrToUpper(char* str) {
+        return str;
+    }
+
+    void TestStrToUpper(CuTest *tc) {
+        char* input = strdup("hello world");
+        char* actual = StrToUpper(input);
+        char* expected = "HELLO WORLD";
+        CuAssertStrEquals(tc, expected, actual);
+    }
+
+    CuSuite* StrUtilGetSuite() {
+        CuSuite* suite = CuSuiteNew();
+        SUITE_ADD_TEST(suite, TestStrToUpper);
+        return suite;
+    }
+
+Create another file called AllTests.c with these contents:
+
+    #include "CuTest.h"
+
+    CuSuite* StrUtilGetSuite();
+
+    void RunAllTests(void) {
+        CuString *output = CuStringNew();
+        CuSuite* suite = CuSuiteNew();
+
+        CuSuiteAddSuite(suite, StrUtilGetSuite());
+
+        CuSuiteRun(suite);
+        CuSuiteSummary(suite, output);
+        CuSuiteDetails(suite, output);
+        printf("%s\n", output->buffer);
+    }
+
+    int main(void) {
+        RunAllTests();
+    }
+
+Then type this on the command line:
+
+    gcc AllTests.c CuTest.c StrUtil.c
+
+to compile. You can replace gcc with your favorite compiler.
+CuTest should be portable enough to handle all Windows and Unix
+compilers. Then to run the tests type:
+
+    a.out
+
+This will print an error because we haven't implemented the
+StrToUpper function correctly. We are just returning the string
+without changing it to upper case.
+
+    char* StrToUpper(char* str) {
+        return str;
+    }
+
+Rewrite this as follows:
+
+    char* StrToUpper(char* str) {
+        char* p;
+        for (p = str ; *p ; ++p) *p = toupper(*p);
+        return str;
+    }
+
+Recompile and run the tests again. The test should pass this
+time.
+
+
+WHAT TO DO NEXT
+
+At this point you might want to write more tests for the
+StrToUpper function. Here are some ideas:
+
+TestStrToUpper_EmptyString :  pass in ""
+TestStrToUpper_UpperCase   :  pass in "HELLO WORLD"
+TestStrToUpper_MixedCase   :  pass in "HELLO world"
+TestStrToUpper_Numbers     :  pass in "1234 hello"
+
+As you write each one of these tests add it to StrUtilGetSuite
+function. If you don't the tests won't be run. Later as you write
+other functions and write tests for them be sure to include those
+in StrUtilGetSuite also. The StrUtilGetSuite function should
+include all the tests in StrUtil.c
+
+Over time you will create another file called FunkyStuff.c
+containing other functions unrelated to StrUtil. Follow the same
+pattern. Create a FunkyStuffGetSuite function in FunkyStuff.c.
+And add FunkyStuffGetSuite to AllTests.c.
+
+The framework is designed in the way it is so that it is easy to
+organize a lot of tests.
+
+THE BIG PICTURE
+
+Each individual test corresponds to a CuTest. These are grouped
+to form a CuSuite. CuSuites can hold CuTests or other CuSuites.
+AllTests.c collects all the CuSuites in the program into a single
+CuSuite which it then runs as a single CuSuite.
+
+The project is open source so feel free to take a peek under the
+hood at the CuTest.c file to see how it works. CuTestTest.c
+contains tests for CuTest.c. So CuTest tests itself.
+
+Since AllTests.c has a main() you will need to exclude this when
+you are building your product. Here is a nicer way to do this if
+you want to avoid messing with multiple builds. Remove the main()
+in AllTests.c. Note that it just calls RunAllTests(). Instead
+we'll call this directly from the main program.
+
+Now in the main() of the actual program check to see if the
+command line option "--test" was passed. If it was then I call
+RunAllTests() from AllTests.c. Otherwise run the real program.
+
+Shipping the tests with the code can be useful. If you customers
+complain about a problem you can ask them to run the unit tests
+and send you the output. This can help you to quickly isolate the
+piece of your system that is malfunctioning in the customer's
+environment.
+
+CuTest offers a rich set of CuAssert functions. Here is a list:
+
+void CuAssert(CuTest* tc, char* message, int condition);
+void CuAssertTrue(CuTest* tc, int condition);
+void CuAssertStrEquals(CuTest* tc, char* expected, char* actual);
+void CuAssertIntEquals(CuTest* tc, int expected, int actual);
+void CuAssertPtrEquals(CuTest* tc, void* expected, void* actual);
+void CuAssertPtrNotNull(CuTest* tc, void* pointer);
+
+The project is open source and so you can add other more powerful
+asserts to make your tests easier to write and more concise.
+Please feel free to send me changes you make so that I can
+incorporate them into future releases.
+
+If you see any errors in this document please contact me at
+asimjalis@peakprogramming.com.
+
+
+AUTOMATING TEST SUITE GENERATION
+
+make-tests.sh will grep through all the .c files in the current
+directory and generate the code to run all the tests contained in
+them. Using this script you don't have to worry about writing
+AllTests.c or dealing with any of the other suite code.
+
+
+CREDITS
+
+These people have contributed useful code changes to the CuTest project.
+Thanks!
+
+- [02.23.2003] Dave Glowacki <dglo@hyde.ssec.wisc.edu>
+- [04.17.2009] Tobias Lippert <herrmarder@googlemail.com>
+- [11.13.2009] Eli Bendersky <eliben@gmail.com>
+- [12.14.2009] Andrew Brown <abrown@datasci.com>
diff --git a/tests/cutest/license.txt b/tests/cutest/license.txt
new file mode 100644
index 0000000..3d94167
--- /dev/null
+++ b/tests/cutest/license.txt
@@ -0,0 +1,38 @@
+NOTE
+
+The license is based on the zlib/libpng license. For more details see
+http://www.opensource.org/licenses/zlib-license.html. The intent of the
+license is to:
+
+- keep the license as simple as possible
+- encourage the use of CuTest in both free and commercial applications
+  and libraries
+- keep the source code together
+- give credit to the CuTest contributors for their work
+
+If you ship CuTest in source form with your source distribution, the
+following license document must be included with it in unaltered form.
+If you find CuTest useful we would like to hear about it.
+
+LICENSE
+
+Copyright (c) 2003 Asim Jalis
+
+This software is provided 'as-is', without any express or implied
+warranty. In no event will the authors be held liable for any damages
+arising from the use of this software.
+
+Permission is granted to anyone to use this software for any purpose,
+including commercial applications, and to alter it and redistribute it
+freely, subject to the following restrictions:
+
+1. The origin of this software must not be misrepresented; you must not
+claim that you wrote the original software. If you use this software in
+a product, an acknowledgment in the product documentation would be
+appreciated but is not required.
+
+2. Altered source versions must be plainly marked as such, and must not
+be misrepresented as being the original software.
+
+3. This notice may not be removed or altered from any source
+distribution.