- linked list now allows inserting and deleting in the middle of the

list
- test for this features written

5 files changed, 273 insertions, 22 deletions

diff --git a/Source/charon/linked_list.c b/Source/charon/linked_list.c
index e583e63e9..c784b9950 100644
--- a/Source/charon/linked_list.c
+++ b/Source/charon/linked_list.c
@@ -425,6 +425,128 @@ static status_t get_last(private_linked_list_t *this, void **item)
 }
 
 /**
+ * @brief implements function insert_before of linked_list_t
+ */
+static status_t insert_before(private_linked_list_t *this, private_linked_list_element_t * next_element, void *item)
+{
+	if (this->count == 0)
+	{
+		return FAILED;
+	}
+
+	private_linked_list_element_t *element =(private_linked_list_element_t *) linked_list_element_create(item);
+	
+	if (element == NULL)
+	{
+		return FAILED;
+	}
+	
+	if (next_element->previous == NULL)
+	{
+		if (this->first != next_element)
+		{
+			element->public.destroy(&(element->public));
+			return FAILED;
+		}
+		
+		next_element->previous = element;
+		element->next = next_element;
+		this->first = element;
+	}
+	else
+	{
+		next_element->previous->next = element;
+		element->previous = next_element->previous;
+		next_element->previous = element;
+		element->next = next_element;
+	}
+	
+	this->count++;
+
+	return SUCCESS;
+}
+
+/**
+ * @brief implements function insert_after of linked_list_t
+ */
+static status_t insert_after(private_linked_list_t *this, private_linked_list_element_t * previous_element, void *item)
+{
+	if (this->count == 0)
+	{
+		return FAILED;
+	}
+
+	private_linked_list_element_t *element =(private_linked_list_element_t *) linked_list_element_create(item);
+	
+	if (element == NULL)
+	{
+		return FAILED;
+	}
+	
+	if (previous_element->next == NULL)
+	{
+		if (this->last != previous_element)
+		{
+			element->public.destroy(&(element->public));
+			return FAILED;
+		}
+		
+		previous_element->next = element;
+		element->previous = previous_element;
+		this->last = element;
+	}
+	else
+	{
+		previous_element->next->previous = element;
+		element->next = previous_element->next;
+		previous_element->next = element;
+		element->previous = previous_element;
+	}
+	
+	this->count++;
+	return SUCCESS;
+}
+
+/**
+ * @brief implements function remove of linked_list_t
+ */
+static status_t linked_list_remove(private_linked_list_t *this, private_linked_list_element_t * element)
+{
+	if (this->count == 0)
+	{
+		return FAILED;
+	}
+	
+	if (element->previous == NULL)
+	{	
+		if (element->next == NULL)
+		{
+			this->first = NULL; 	
+		 	this->last = NULL;
+		}
+		else
+		{
+			element->next->previous = NULL;
+			this->first = element->next;
+		}
+	}
+	else if (element->next == NULL)
+	{
+		element->previous->next = NULL;
+		this->last = element->previous;
+	}
+	else
+	{
+		element->previous->next = element->next;
+		element->next->previous = element->previous;
+	}
+	
+ 	this->count--;
+ 	element->public.destroy(&(element->public));
+ 	return SUCCESS;
+}
+
+/**
  * @brief implements function destroy of linked_list_t
  */
 static status_t linked_list_destroy(private_linked_list_t *this)
@@ -456,8 +578,11 @@ linked_list_t *linked_list_create()
 	this->public.create_iterator = (status_t (*) (linked_list_t *linked_list, linked_list_iterator_t **iterator,bool forward)) create_iterator;
 	this->public.get_first = (status_t (*) (linked_list_t *linked_list, void **item)) get_first;
 	this->public.get_last = (status_t (*) (linked_list_t *linked_list, void **item)) get_last;
-	this->public.insert_first = (status_t (*) (linked_list_t *linked_list, void *item))insert_first;
-	this->public.insert_last = (status_t (*) (linked_list_t *linked_list, void *item))insert_last;
+	this->public.insert_first = (status_t (*) (linked_list_t *linked_list, void *item)) insert_first;
+	this->public.insert_last = (status_t (*) (linked_list_t *linked_list, void *item)) insert_last;
+	this->public.insert_before = (status_t (*) (linked_list_t *linked_list, linked_list_element_t * element, void *item)) insert_before;
+	this->public.insert_after = (status_t (*) (linked_list_t *linked_list, linked_list_element_t * element, void *item)) insert_after;
+	this->public.remove = (status_t (*) (linked_list_t *linked_list, linked_list_element_t * element)) linked_list_remove;
 	this->public.remove_first = (status_t (*) (linked_list_t *linked_list, void **item)) remove_first;
 	this->public.remove_last = (status_t (*) (linked_list_t *linked_list, void **item)) remove_last;
 	this->public.destroy = (status_t (*) (linked_list_t *linked_list)) linked_list_destroy;
diff --git a/Source/charon/linked_list.h b/Source/charon/linked_list.h
index cc7d7a0c5..9240da120 100644
--- a/Source/charon/linked_list.h
+++ b/Source/charon/linked_list.h
@@ -154,6 +154,35 @@ struct linked_list_s {
 	status_t (*insert_first) (linked_list_t *linked_list, void *item);
 	
 	/**
+	 * @brief inserts a new item before the given element
+	 * 
+	 * @param linked_list calling object
+	 * @param element new element is inserted before this element
+	 * @param[in] item value to insert in list
+	 * @returns SUCCESS if succeeded, FAILED otherwise
+	 */
+	status_t (*insert_before) (linked_list_t *linked_list, linked_list_element_t *element, void *item);
+
+	/**
+	 * @brief inserts a new item after the given element
+	 * 
+	 * @param linked_list calling object
+	 * @param element new element is inserted after this element
+	 * @param[in] item value to insert in list
+	 * @returns SUCCESS if succeeded, FAILED otherwise
+	 */
+	status_t (*insert_after) (linked_list_t *linked_list, linked_list_element_t *element, void *item);
+
+	/**
+	 * @brief removes an element from list
+	 * 
+	 * @param linked_list calling object
+	 * @param element element to remove
+	 * @returns SUCCESS if succeeded, FAILED otherwise
+	 */
+	status_t (*remove) (linked_list_t *linked_list, linked_list_element_t *element);
+
+	/**
 	 * @brief removes the first item in the list and returns its value
 	 * 
 	 * @param linked_list calling object
diff --git a/Source/charon/tests/linked_list_test.c b/Source/charon/tests/linked_list_test.c
index ca3cd6b54..f6254b991 100644
--- a/Source/charon/tests/linked_list_test.c
+++ b/Source/charon/tests/linked_list_test.c
@@ -103,7 +103,7 @@ void test_linked_list(tester_t *tester)
  /*
  * Description in header-file
  */
-void test_linked_list_forward_iterator(tester_t *tester)
+void test_linked_list_iterator(tester_t *tester)
 {
 	bool has_next;
 	linked_list_element_t * element;
@@ -116,39 +116,115 @@ void test_linked_list_forward_iterator(tester_t *tester)
 	linked_list->insert_first(linked_list,"five");
 
 	linked_list_iterator_t * iterator;
+	linked_list_iterator_t * iterator2;
 	
 	
-	tester->assert_true(tester,(linked_list->create_iterator(linked_list,&iterator,TRUE) == SUCCESS), "create_iterator call check");
+	tester->assert_true(tester,(linked_list->create_iterator(linked_list,&iterator,TRUE) == SUCCESS), "create_iterator for it 1 call check");
 	
 	iterator->has_next(iterator,&has_next);
-	tester->assert_true(tester,has_next, "has_next value check");	
+	tester->assert_true(tester,has_next, "it 1 has_next value check");	
 	iterator->current(iterator,&element);
-	tester->assert_true(tester,(strcmp((char *) element->value,"five") == 0), "current value check");
+	tester->assert_true(tester,(strcmp((char *) element->value,"five") == 0), "it 1 current value check");
 	
 	iterator->has_next(iterator,&has_next);
-	tester->assert_true(tester,has_next, "has_next value check");	
+	tester->assert_true(tester,has_next, "it 1 has_next value check");	
 	iterator->current(iterator,&element);
-	tester->assert_true(tester,(strcmp((char *) element->value,"four") == 0), "current value check");
+	tester->assert_true(tester,(strcmp((char *) element->value,"four") == 0), "it 1 current value check");
+
+	tester->assert_true(tester,(linked_list->create_iterator(linked_list,&iterator2,FALSE) == SUCCESS), "create_iterator for it 2 call check");
+
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_true(tester,has_next, "it 2 has_next value check");	
+	iterator2->current(iterator2,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"one") == 0), "it 2 current value check");
 
 	iterator->has_next(iterator,&has_next);
-	tester->assert_true(tester,has_next, "has_next value check");	
+	tester->assert_true(tester,has_next, "it 1 has_next value check");	
 	iterator->current(iterator,&element);
-	tester->assert_true(tester,(strcmp((char *) element->value,"three") == 0), "current value check");
+	tester->assert_true(tester,(strcmp((char *) element->value,"three") == 0), "it 1 current value check");
+
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_true(tester,has_next, "it 2 has_next value check");	
+	iterator2->current(iterator2,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"two") == 0), "it 2 current value check");
 
 	iterator->has_next(iterator,&has_next);
-	tester->assert_true(tester,has_next, "has_next value check");	
+	tester->assert_true(tester,has_next, "it 1 has_next value check");	
 	iterator->current(iterator,&element);
-	tester->assert_true(tester,(strcmp((char *) element->value,"two") == 0), "current value check");
+	tester->assert_true(tester,(strcmp((char *) element->value,"two") == 0), "it 1 current value check");
+
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_true(tester,has_next, "it 2 has_next value check");	
+	iterator2->current(iterator2,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"three") == 0), "it 2 current value check");
 
 	iterator->has_next(iterator,&has_next);
-	tester->assert_true(tester,has_next, "has_next value check");	
+	tester->assert_true(tester,has_next, "it 1 has_next value check");	
 	iterator->current(iterator,&element);
-	tester->assert_true(tester,(strcmp((char *) element->value,"one") == 0), "current value check");
+	tester->assert_true(tester,(strcmp((char *) element->value,"one") == 0), "it 1 current value check");
 
 	iterator->has_next(iterator,&has_next);
-	tester->assert_false(tester,has_next, "has_next value check");
+	tester->assert_false(tester,has_next, "it 1 has_next value check");
+
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_true(tester,has_next, "it 2 has_next value check");	
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_true(tester,has_next, "it 2 has_next value check");	
+	iterator2->has_next(iterator2,&has_next);
+	tester->assert_false(tester,has_next, "it 2 has_next value check");	
 
-	tester->assert_true(tester,(iterator->destroy(iterator) == SUCCESS), "destroy call check");
+	tester->assert_true(tester,(iterator->destroy(iterator) == SUCCESS), "it 1 destroy call check");
+	
+	tester->assert_true(tester,(iterator2->destroy(iterator2) == SUCCESS), "it 2 destroy call check");
+	
+	linked_list->destroy(linked_list);
+}
+
+ /*
+ * Description in header-file
+ */
+void test_linked_list_insert_and_remove(tester_t *tester)
+{
+	bool has_next;
+	linked_list_element_t * element;
+	linked_list_iterator_t * iterator;
+	
+	linked_list_t *linked_list = linked_list_create();
+	linked_list->insert_first(linked_list,"one");
+	linked_list->insert_first(linked_list,"two");
+	
+	linked_list->insert_first(linked_list,"three");
+	linked_list->insert_first(linked_list,"four");
+	linked_list->insert_first(linked_list,"five");
+	
+
+	
+	linked_list->create_iterator(linked_list,&iterator,TRUE);
+	
+	iterator->has_next(iterator,&has_next);
+	iterator->has_next(iterator,&has_next);
+	iterator->has_next(iterator,&has_next);
+	iterator->current(iterator,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"three") == 0), "current value check");
+
+	tester->assert_true(tester,(linked_list->insert_before(linked_list,element,"before_three") == SUCCESS), "insert_before call check");
+
+	tester->assert_true(tester,(linked_list->insert_after(linked_list,element,"after_three") == SUCCESS), "insert_after call check");
+	
+	tester->assert_true(tester,(linked_list->remove(linked_list,element) == SUCCESS), "remove call check");
+	
+	iterator->reset(iterator);
+	
+	iterator->has_next(iterator,&has_next);
+	iterator->has_next(iterator,&has_next);
+	iterator->has_next(iterator,&has_next);
+	iterator->current(iterator,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"before_three") == 0), "current value check");
+	iterator->has_next(iterator,&has_next);
+	iterator->current(iterator,&element);
+	tester->assert_true(tester,(strcmp((char *) element->value,"after_three") == 0), "current value check");
+	
+	iterator->destroy(iterator);
 	
 	linked_list->destroy(linked_list);
 }
diff --git a/Source/charon/tests/linked_list_test.h b/Source/charon/tests/linked_list_test.h
index 0ecdf40d7..4038e0917 100644
--- a/Source/charon/tests/linked_list_test.h
+++ b/Source/charon/tests/linked_list_test.h
@@ -37,7 +37,7 @@
 void test_linked_list(tester_t *tester);
 
 /**
- * @brief Test function for the type linked_list_t and its forward iterator
+ * @brief Test function for the type linked_list_t and its iterator
  *
  * Performs different kinds of assertions to check the functionality
  * of the linked_list_t and its iterator in a Single-Threaded environment. 
@@ -47,7 +47,21 @@ void test_linked_list(tester_t *tester);
  *  
  * @param tester tester object
  */
-void test_linked_list_forward_iterator(tester_t *tester);
+void test_linked_list_iterator(tester_t *tester);
+
+/**
+ * @brief Test function for the type linked_list_t and its insert and remove
+ * 		  functions
+ *
+ * Performs different kinds of assertions to check the functionality
+ * of the linked_list_t and its insert and remove functions
+ * 
+ * @warning To be usable in multi-threaded software 
+ * this list has to get protected with locks.
+ *  
+ * @param tester tester object
+ */
+void test_linked_list_insert_and_remove(tester_t *tester);
 
 /**
  * Test for linked_list_t
@@ -57,6 +71,12 @@ test_t linked_list_test = {test_linked_list,"Linked List"};
 /**
  * Test for linked_list_t with iterator
  */
-test_t linked_list_forward_iterator_test = {test_linked_list_forward_iterator,"Linked List Forward Iterator"};
+test_t linked_list_iterator_test = {test_linked_list_iterator,"Linked List Iterator"};
+
+/**
+ * Test for linked_list_t insert and remove
+ */
+test_t linked_list_insert_and_remove_test = {test_linked_list_insert_and_remove,"Linked List Insert and remove"};
+
 
 #endif /*LINKED_LIST_TEST_H_*/
diff --git a/Source/charon/tests/tests.h b/Source/charon/tests/tests.h
index 6091fbbb8..d3ac30982 100644
--- a/Source/charon/tests/tests.h
+++ b/Source/charon/tests/tests.h
@@ -36,9 +36,10 @@
  */
 test_t *tests[] ={
 	&linked_list_test,
-	&linked_list_forward_iterator_test,
-//	&thread_pool_test,
-//	&job_queue_test1,
+	&linked_list_iterator_test,
+	&linked_list_insert_and_remove_test,
+	&thread_pool_test,
+	&job_queue_test1,
 	NULL
 };