Extend list implementation, add test-list.c to test some of it.

svn path=/trunk/dom/; revision=3573

8 files changed, 159 insertions, 19 deletions

diff --git a/test/lib/Makefile b/test/lib/Makefile
index c94c1ae..78e6bff 100644
--- a/test/lib/Makefile
+++ b/test/lib/Makefile
@@ -28,7 +28,7 @@ RELEASE = libdomtest.a
 DEBUG = libdomtest-debug.a
 
 # Objects
-OBJS = list testassert testobject utils
+OBJS = comparators list testassert testobject utils
 
 .PHONY: clean debug export release setup test
 
diff --git a/test/lib/comparators.c b/test/lib/comparators.c
new file mode 100644
index 0000000..c07236d
--- /dev/null
+++ b/test/lib/comparators.c
@@ -0,0 +1,5 @@
+#include "comparators.h"
+
+int int_comparator(const int* a, const int* b) {
+	return (*a) - (*b);
+}
diff --git a/test/lib/comparators.h b/test/lib/comparators.h
new file mode 100644
index 0000000..4cdeb97
--- /dev/null
+++ b/test/lib/comparators.h
@@ -0,0 +1,18 @@
+/*
+ * This file is part of libdom test suite.
+ * Licensed under the MIT License,
+ *                http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2007 James Shaw <jshaw@netsurf-browser.org>
+ */
+
+#ifndef comparators_h_
+#define comparators_h_
+
+/**
+ * A function pointer type for a comparator.
+ */
+typedef int (*comparator)(const void* a, const void* b);
+
+int int_comparator(const int* a, const int* b);
+
+#endif
diff --git a/test/lib/exceptions.h b/test/lib/exceptions.h
index 1c6b8e2..8b98d5b 100644
--- a/test/lib/exceptions.h
+++ b/test/lib/exceptions.h
@@ -1,3 +1,10 @@
+/*
+ * This file is part of libdom test suite.
+ * Licensed under the MIT License,
+ *                http://www.opensource.org/licenses/mit-license.php
+ * Copyright 2007 James Shaw <jshaw@netsurf-browser.org>
+ */
+
 #ifndef exceptions_h_
 #define exceptions_h_
 
@@ -5,7 +12,8 @@
 
 #include <dom/core/exceptions.h>
 
-/* Usage:
+/*  Adapted from http://www.math.princeton.edu/~asnowden/c-except.html
+    Usage:
  	TRY
  		THROW(DOM_NOT_FOUND_ERR);
 		THROW_IF_ERR(dom_document_get_doctype(...));
diff --git a/test/lib/list.c b/test/lib/list.c
index 0b2965f..e72b50c 100644
--- a/test/lib/list.c
+++ b/test/lib/list.c
@@ -10,9 +10,24 @@
 #include <stdio.h>
 #include <stdlib.h>
 
+#include "comparators.h"
 #include "list.h"
 #include "testassert.h"
 
+/**
+ * Private helper function.
+ * Create a new list_elt and initialise it.
+ */
+struct list_elt* list_new_elt(void* data);
+
+struct list_elt* list_new_elt(void* data) {
+	struct list_elt* elt = malloc(sizeof(struct list_elt));
+	assert(elt != NULL);
+	elt->data = data;
+	elt->next = NULL;
+	return elt;
+}
+
 struct list* list_new(void)
 {
 	struct list* list = malloc(sizeof(struct list));
@@ -36,10 +51,7 @@ void list_destroy(struct list* list)
 
 void list_add(struct list* list, void* data)
 {
-	struct list_elt* elt = malloc(sizeof(struct list_elt));
-	assert(elt != NULL);
-	elt->data = data;
-	elt->next = NULL;
+	struct list_elt* elt = list_new_elt(data);
 	struct list_elt* tail = list->tail;
 
 	/* if tail was set, make its 'next' ptr point to elt */
@@ -58,7 +70,50 @@ void list_add(struct list* list, void* data)
 	list->size++;
 }
 
-bool list_contains(struct list* list, void* data, list_compare_func comparator)
+bool list_remove(struct list* list, void* data)
+{	
+	struct list_elt* prevElt = NULL;
+	struct list_elt* elt = list->head;
+	
+	bool found = false;
+	
+	while (elt != NULL) {
+		struct list_elt* nextElt = elt->next;
+		
+		/* if data is identical, fix up pointers, and free the element */
+		if (data == elt->data) {
+			if (prevElt == NULL) {
+				list->head = nextElt;
+			} else {
+				prevElt->next = nextElt;
+			}
+			free(elt);
+			list->size--;
+			found = true;
+			break;
+		}
+		
+		prevElt = elt;
+		elt = nextElt;
+	}
+	
+	return found;
+}
+
+struct list* list_clone(struct list* list)
+{
+	struct list* newList = list_new();
+	struct list_elt* elt = list->head;
+	
+	while (elt != NULL) {
+		list_add(newList, elt->data);
+		elt = elt->next;
+	}
+	
+	return newList;
+}
+
+bool list_contains(struct list* list, void* data, comparator comparator)
 {
 	struct list_elt* elt = list->head;
 	while (elt != NULL) {
@@ -71,15 +126,29 @@ bool list_contains(struct list* list, void* data, list_compare_func comparator)
 }
 
 bool list_contains_all(struct list* superList, struct list* subList, 
-		list_compare_func comparator)
+		comparator comparator)
 {
-	struct list_elt* elt = subList->head;
-	while (elt != NULL) {
-		if (!list_contains(superList, elt->data, comparator)) {
-			return false;
+	struct list_elt* subElt = subList->head;
+	struct list* superListClone = list_clone(superList);
+	
+	bool found = true;
+	
+	while (subElt != NULL) {
+		struct list_elt* superElt = superListClone->head;
+
+		found = false;
+		while (superElt != NULL && found == false) {
+			if (comparator(subElt->data, superElt->data) == 0) {
+				found = true;
+				list_remove(superListClone, superElt->data);
+			}
+			superElt = superElt->next;
 		}
-		elt = elt->next;
+		
+		subElt = subElt->next;
 	}
-	return true;
+	free(superListClone);
+	
+	return found;
 }
 
diff --git a/test/lib/list.h b/test/lib/list.h
index a0a6c6a..7c27796 100644
--- a/test/lib/list.h
+++ b/test/lib/list.h
@@ -8,6 +8,10 @@
 #ifndef list_h_
 #define list_h_
 
+#include <stdbool.h>
+
+#include "comparators.h"
+
 struct list_elt {
 	void* data;
 	struct list_elt* next;
@@ -22,23 +26,32 @@ struct list {
 struct list* list_new(void);
 void list_destroy(struct list* list);
 
-typedef int (*list_compare_func)(const void* a, const void* b);
-
 /**
  * Add data to the tail of the list.
  */
 void list_add(struct list* list, void* data);
 
 /**
+ * Remove element containing data from list.
+ * The list element is freed, but the caller must free the data itself
+ * if necessary.
+ * 
+ * Returns true if data was found in the list.
+ */
+bool list_remove(struct list* list, void* data);
+
+struct list* list_clone(struct list* list);
+
+/**
  * Tests if data is equal to any element in the list.
  */
-bool list_contains(struct list* list, void* data, 
-		int (*comparator)(const void* a, const void* b));
+bool list_contains(struct list* list, void* data,
+		comparator comparator);
 
 /**
  * Tests if superlist contains all elements in sublist.  Order is not important.
  */
 bool list_contains_all(struct list* superList, struct list* subList, 
-		list_compare_func comparator);
+		comparator comparator);
 
 #endif
diff --git a/test/lib/testassert.c b/test/lib/testassert.c
index 2a31ff3..3fd339e 100644
--- a/test/lib/testassert.c
+++ b/test/lib/testassert.c
@@ -9,6 +9,7 @@
 #include <stdlib.h>
 
 #include "testassert.h"
+#include "comparators.h"
 #include "utils.h"
 
 void __assert2(const char *expr, const char *function,
@@ -22,4 +23,22 @@ void __assert2(const char *expr, const char *function,
 	exit(EXIT_FAILURE);
 }
 
+void assert_equals_collection(struct list* expected, struct list* actual,
+		comparator comparator)
+{
+	assert_not_null(expected);
+	assert_not_null(actual);
+	assert_equals(expected->size, actual->size, (int (*)(const void* a, const void* b)) int_comparator);
+	list_contains_all(actual, expected, comparator);
+}
+
+void assert_equals(int expected, int actual, comparator comparator)
+{
+	assert(comparator(&expected, &actual) == 0);
+}
+
+void assert_not_null(void* x)
+{
+	assert(x != NULL);
+}
 
diff --git a/test/lib/testassert.h b/test/lib/testassert.h
index 329feff..8556075 100644
--- a/test/lib/testassert.h
+++ b/test/lib/testassert.h
@@ -8,6 +8,9 @@
 #ifndef testassert_h_
 #define testassert_h_
 
+#include "comparators.h"
+#include "list.h"
+
 /* Redefine assert, so we can simply use the standard assert mechanism
  * within testcases and exit with the right output for the testrunner
  * to do the right thing. */
@@ -17,6 +20,11 @@ void __assert2(const char *expr, const char *function,
 #define assert(expr) \
   ((void) ((expr) || (__assert2 (#expr, __func__, __FILE__, __LINE__), 0)))
 
+void assert_equals_collection(struct list* expected, struct list* actual,
+		comparator comparator);
+void assert_equals(int expected, int actual, comparator comparator);
+void assert_not_null(void* x);
+
 
 #endif