Merge lp:~stefan.goetz-deactivatedaccount/hipl/hip-ll-extensions into lp:hipl

[Stefan Götz]

Simplifies and extends the linked list implementation. These extensions are needed in other branches.

[Diego Biurrun (diego-biurrun)]

 review needs-fixing

On Sat, Apr 02, 2011 at 01:16:36AM +0000, Stefan Götz wrote:
> Stefan Götz has proposed merging lp:~stefan.goetz/hipl/hip-ll-extensions into lp:hipl.

OK, I will try to bother you into splitting off some changes and
pushing them into trunk right away. I'd ask you to follow along.
Let's try this as an experiment and see if it leads to branches
getting merged quicker.

> --- hipd/hip_socket.c 2011-02-25 15:18:27 +0000
> +++ hipd/hip_socket.c 2011-04-02 01:16:32 +0000
> @@ -251,8 +251,8 @@
>
> int hip_get_highest_descriptor(void)
> {
> - int highest_descriptor = 0;
> - struct hip_ll_node *iter = NULL;
> + int highest_descriptor = 0;
> + const struct hip_ll_node *iter = NULL;

Push right away.

> @@ -269,7 +269,7 @@
>
> void hip_prepare_fd_set(fd_set *read_fdset)
> {
> - struct hip_ll_node *iter = NULL;
> + const struct hip_ll_node *iter = NULL;

ditto

> @@ -296,8 +296,8 @@
> */
> void hip_run_socket_handles(fd_set *read_fdset, struct hip_packet_context *ctx)
> {
> - struct hip_ll_node *iter = NULL;
> - int socketfd;
> + const struct hip_ll_node *iter = NULL;
> + int socketfd;

same

> --- hipd/maintenance.c 2011-02-14 19:20:39 +0000
> +++ hipd/maintenance.c 2011-04-02 01:16:32 +0000
> @@ -224,8 +224,8 @@
> */
> static int hip_run_maint_functions(void)
> {
> - int err = 0;
> - struct hip_ll_node *iter = NULL;
> + int err = 0;
> + const struct hip_ll_node *iter = NULL;

same

> --- hipd/pkt_handling.c 2011-02-14 18:40:02 +0000
> +++ hipd/pkt_handling.c 2011-04-02 01:16:32 +0000
> @@ -139,8 +139,8 @@
> {
> - int err = 0;
> - struct hip_ll_node *iter = NULL;
> + int err = 0;
> + const struct hip_ll_node *iter = NULL;

same

> --- hipd/registration.c 2011-03-29 19:46:16 +0000
> +++ hipd/registration.c 2011-04-02 01:16:32 +0000
> @@ -104,7 +104,7 @@
> int idx = 0;
> time_t now = time(NULL);
> - struct hip_ll_node *iter = NULL;
> + const struct hip_ll_node *iter = NULL;

this as well

> @@ -241,8 +241,8 @@
> */
> int hip_del_pending_request(struct hip_hadb_state *entry)
> {
> - int idx = 0;
> - struct hip_ll_node *iter = NULL;
> + int idx = 0;
> + const struct hip_ll_node *iter = NULL;

and this

> @@ -276,7 +276,7 @@
> {
> int idx = 0;
> - struct hip_ll_node *iter = NULL;
> + const struct hip_ll_node *iter = NULL;

and this

> @@ -308,7 +308,7 @@
> int hip_replace_pending_requests(struct hip_hadb_state *entry_old,
> struct hip_hadb_state *entry_new)
> {
> - struct hip_ll_node *iter = 0;
> + const struct hip_ll_node *iter = 0;

again

> @@ -338,8 +338,8 @@
> static int hip_get_pending_requests(struct hip_hadb_state *entry,
> struct hip_pending_request *requests[])
> {
> - struct hip_ll_node *iter ...

review: Needs Fixing

[Stefan Götz (stefan.goetz-deactivatedaccount)]

Hi Diego!

> OK, I will try to bother you into splitting off some changes and
> pushing them into trunk right away. I'd ask you to follow along.
> Let's try this as an experiment and see if it leads to branches
> getting merged quicker.

I agree with you: smaller merge proposals are easier to review and get into trunk more quickly. Where we apparently disagree is how far this approach should be taken. My personal guideline for grouping commits into a branch/merge proposal is that these commits need to be related to each other under a common topic which should make it easier to review them in context of each other as opposed to separately.

In the case of this branch, this means: this branch cleans up the hip_ll implementation. A changeset of 973 lines is not nothing, admittedly, plus one could factor out the new function with the unit tests because it's not cleanup. But this whole thing is neatly divided into well-documented commits. Turning each commit into a separate branch/merge proposal is detrimental to reviews in my opinion, because it breaks the common context which these commits share and which actually helps during review.

So I fully buy the approach to committing minor, unrelated stuff to trunk right away. It's just that I think that nothing here qualifies as 'unrelated'.

Apart from that, I agree with all your other comments except where noted below.

>> + unsigned i = 0;
>> + struct hip_ll_node *p = NULL;
>> + struct hip_ll_node *node;
>
> struct hip_ll_node *p = NULL; *node;
>
> save those precious lines :)

I couldn't find this policy in doc/HACKING. Its sample code actually follows the 'one declaration per line' style. Personally, I prefer that style, too, because a) I don't overlook declarations as easily and b) it keeps diffs cleaner and c) when I can choose between fewer lines and more readable code, I guess it's obvious which choice I'd make :-) Sorry for being a difficult customer today.

>> +/**
>> + * Get the list node with the specified index.
>> + *
>> + * @param list points to the list to search. The result of calling this
>> + * this function with list == NULL is undefined.
>> + * @param idx the index of the list node to retrieve. The first node element
>> + * has the index 0. The result of calling this function with an idx
>> + * value greater than or equal to the number of nodes in the list
>> + * is undefined.
>> + * @return the list node with the index idx.
>
> nit: s/.//

A sed expression that says 'Delete the first character of each line'? Delete all full stops? Delete the full stop at the end of each paragraph? And in any case: why? :-)

Stefan

[Diego Biurrun (diego-biurrun)]

On Sat, Apr 02, 2011 at 03:12:31PM +0000, Stefan Götz wrote:
>
> > OK, I will try to bother you into splitting off some changes and
> > pushing them into trunk right away. I'd ask you to follow along.
> > Let's try this as an experiment and see if it leads to branches
> > getting merged quicker.
>
> I agree with you: smaller merge proposals are easier to review and get
> into trunk more quickly. Where we apparently disagree is how far this
> approach should be taken. My personal guideline for grouping commits
> into a branch/merge proposal is that these commits need to be related
> to each other under a common topic which should make it easier to
> review them in context of each other as opposed to separately.
>
> In the case of this branch, this means: this branch cleans up the
> hip_ll implementation. A changeset of 973 lines is not nothing,
> admittedly, plus one could factor out the new function with the unit
> tests because it's not cleanup. But this whole thing is neatly divided
> into well-documented commits. Turning each commit into a separate
> branch/merge proposal is detrimental to reviews in my opinion, because
> it breaks the common context which these commits share and which
> actually helps during review.
>
> So I fully buy the approach to committing minor, unrelated stuff to
> trunk right away. It's just that I think that nothing here qualifies
> as 'unrelated'.

The word "unrelated" is obscuring my point it seems. I mean all changes
that are independent and can be broken out of a merge proposal should be
broken out and committed separately.

I have just done this as a proof of concept for your branch. Splitting
off the const correctness changes by manually editing the diff file,
applying to a vanilla branch, recompiling, recompiling to run all tests,
writing a commit message and committing with you as author took no more
than 15 minutes.

If you go ahead and rebase your tree against trunk now your merge request
will shrink considerably and it will be quicker for me and all others to
review it.

The point is that before I had to rereview changes again that I had already
approved. I cannot just skip them since I cannot be sure they are exactly
the same as before, your tree might have changed.

After doublechecking now I see that this amounts to more or less the first
commit in your branch, which you could have pushed to trunk more easily.
Well, so possibly this has not saved much time, *but* we have more const
correctness in trunk now, not just hidden away in your branch :)

> >> +/**
> >> + * Get the list node with the specified index.
> >> + *
> >> + * @param list points to the list to search. The result of calling this
> >> + * this function with list == NULL is undefined.
> >> + * @param idx the index of the list node to retrieve. The first node element
> >> + * has the index 0. The result of calling this function with an idx
> >> + * value greater than or equal to the number of nodes in the list
> >> + * is undefined.
> >> + * @return the list node with the index idx.
> >
> > nit: s/.//
>
> A sed expression that says 'Delete the first character of each line'?
> Dele...

Unmerged revisions

5816. By Stefan Götz on 2011-04-02

Add function for deleting a linked list element that matches specific payload data.
Add unit tests to cover this new functionality.

5815. By Stefan Götz on 2011-04-02

Add an internal, more generic function for deleting a list node from a linked list.
Simplify the hip_ll_del() function by re-using the added internal function.

5814. By Stefan Götz on 2011-04-02

Add internal functions for retrieving list nodes.
Simplify the existing functions hip_ll_add() and hip_ll_get() by re-using the added functions.

5813. By Stefan Götz on 2011-04-02

Simplify hip_ll_uninit() to re-use existing code instead of re-implementing it.

5812. By Stefan Götz on 2011-04-01

Fixed const correctness of linked list implementation. Adapted code using linked lists where necessary.

=== modified file 'Makefile.am'
--- Makefile.am	2011-03-25 17:51:40 +0000
+++ Makefile.am	2011-04-02 01:16:32 +0000
@@ -205,6 +205,7 @@
 
 test_check_lib_core_SOURCES = test/check_lib_core.c          \
                               test/lib/core/hit.c            \
+                              test/lib/core/linkedlist.c     \
                               test/lib/core/straddr.c
 
 # Include module Makefile.am's.

=== modified file 'hipd/hip_socket.c'
--- hipd/hip_socket.c	2011-02-25 15:18:27 +0000
+++ hipd/hip_socket.c	2011-04-02 01:16:32 +0000
@@ -251,8 +251,8 @@
 
 int hip_get_highest_descriptor(void)
 {
-    int                 highest_descriptor = 0;
-    struct hip_ll_node *iter               = NULL;
+    int                       highest_descriptor = 0;
+    const struct hip_ll_node *iter               = NULL;
 
     if (hip_sockets) {
         while ((iter = hip_ll_iterate(hip_sockets, iter))) {
@@ -269,7 +269,7 @@
 
 void hip_prepare_fd_set(fd_set *read_fdset)
 {
-    struct hip_ll_node *iter = NULL;
+    const struct hip_ll_node *iter = NULL;
 
     FD_ZERO(read_fdset);
 
@@ -296,8 +296,8 @@
  */
 void hip_run_socket_handles(fd_set *read_fdset, struct hip_packet_context *ctx)
 {
-    struct hip_ll_node *iter = NULL;
-    int                 socketfd;
+    const struct hip_ll_node *iter = NULL;
+    int                       socketfd;
 
     if (hip_sockets) {
         while ((iter = hip_ll_iterate(hip_sockets, iter))) {

=== modified file 'hipd/maintenance.c'
--- hipd/maintenance.c	2011-02-14 19:20:39 +0000
+++ hipd/maintenance.c	2011-04-02 01:16:32 +0000
@@ -224,8 +224,8 @@
  */
 static int hip_run_maint_functions(void)
 {
-    int                 err  = 0;
-    struct hip_ll_node *iter = NULL;
+    int                       err  = 0;
+    const struct hip_ll_node *iter = NULL;
 
     if (hip_maintenance_functions) {
         while ((iter = hip_ll_iterate(hip_maintenance_functions, iter))) {

=== modified file 'hipd/pkt_handling.c'
--- hipd/pkt_handling.c	2011-02-14 18:40:02 +0000
+++ hipd/pkt_handling.c	2011-04-02 01:16:32 +0000
@@ -139,8 +139,8 @@
                              const uint32_t ha_state,
                              struct hip_packet_context *ctx)
 {
-    int                 err  = 0;
-    struct hip_ll_node *iter = NULL;
+    int                       err  = 0;
+    const struct hip_ll_node *iter = NULL;
 
     HIP_IFEL(packet_type > HIP_MAX_PACKET_TYPE,
              -1,

=== modified file 'hipd/registration.c'
--- hipd/registration.c	2011-03-29 19:46:16 +0000
+++ hipd/registration.c	2011-04-02 01:16:32 +0000
@@ -104,7 +104,7 @@
 {
     int                         idx     = 0;
     time_t                      now     = time(NULL);
-    struct hip_ll_node         *iter    = NULL;
+    const struct hip_ll_node   *iter    = NULL;
     struct hip_pending_request *request = NULL;
 
     /* See hip_del_pending_request() for a comment. */
@@ -241,8 +241,8 @@
  */
 int hip_del_pending_request(struct hip_hadb_state *entry)
 {
-    int                 idx  = 0;
-    struct hip_ll_node *iter = NULL;
+    int                       idx  = 0;
+    const struct hip_ll_node *iter = NULL;
 
     /* Iterate through the linked list. The iterator itself can't be used
      * for deleting nodes from the list. Therefore, we just get the index of
@@ -276,7 +276,7 @@
                                            uint8_t reg_type)
 {
     int                         idx     = 0;
-    struct hip_ll_node         *iter    = NULL;
+    const struct hip_ll_node   *iter    = NULL;
     struct hip_pending_request *request = NULL;
 
     /* See hip_del_pending_request() for a comment. */
@@ -308,7 +308,7 @@
 int hip_replace_pending_requests(struct hip_hadb_state *entry_old,
                                  struct hip_hadb_state *entry_new)
 {
-    struct hip_ll_node *iter = 0;
+    const struct hip_ll_node *iter = 0;
 
     while ((iter = hip_ll_iterate(&pending_requests, iter)) != NULL) {
         if (((struct hip_pending_request *) (iter->ptr))->entry == entry_old) {
@@ -338,8 +338,8 @@
 static int hip_get_pending_requests(struct hip_hadb_state *entry,
                                     struct hip_pending_request *requests[])
 {
-    struct hip_ll_node *iter          = 0;
-    int                 request_count = 0;
+    const struct hip_ll_node *iter          = 0;
+    int                       request_count = 0;
 
     if (requests == NULL) {
         return -1;
@@ -368,8 +368,8 @@
  */
 static int hip_get_pending_request_count(struct hip_hadb_state *entry)
 {
-    struct hip_ll_node *iter          = 0;
-    int                 request_count = 0;
+    const struct hip_ll_node *iter          = 0;
+    int                       request_count = 0;
 
     while ((iter = hip_ll_iterate(&pending_requests, iter)) != NULL) {
         if (((struct hip_pending_request *) (iter->ptr))->entry == entry) {

=== modified file 'hipd/user.c'
--- hipd/user.c	2011-03-24 17:34:21 +0000
+++ hipd/user.c	2011-04-02 01:16:32 +0000
@@ -185,7 +185,7 @@
                          struct hip_common *msg,
                          struct sockaddr_in6 *src)
 {
-    struct hip_ll_node *iter = NULL;
+    const struct hip_ll_node *iter = NULL;
 
     if (!hip_user_msg_handles[msg_type] ||
         !hip_ll_get_size(hip_user_msg_handles[msg_type])) {

=== modified file 'lib/core/linkedlist.c'
--- lib/core/linkedlist.c	2011-03-29 17:55:57 +0000
+++ lib/core/linkedlist.c	2011-04-02 01:16:32 +0000
@@ -43,7 +43,7 @@
  *
  * @param linkedlist the list to init.
  */
-void hip_ll_init(struct hip_ll *linkedlist)
+void hip_ll_init(struct hip_ll *const linkedlist)
 {
     if (linkedlist != NULL) {
         *linkedlist = (struct hip_ll) HIP_LL_INIT;
@@ -72,34 +72,15 @@
  *                     invoking this function, and then call this function with
  *                     NULL as @c free_element.
  */
-void hip_ll_uninit(struct hip_ll *linkedlist, free_elem_fn free_element)
+void hip_ll_uninit(struct hip_ll *const linkedlist, free_elem_fn free_element)
 {
-    struct hip_ll_node *pointer = NULL;
-
-    if (linkedlist == NULL || linkedlist->head == NULL) {
-        return;
-    }
-
-    /* Free the node currently at list head and move the next item to list
-     * head. Continue this until the item at list head is NULL. If
-     * free_element() is non-NULL we also free the memory allocated for the
-     * actual element. */
-    if (free_element != NULL) {
-        while (linkedlist->head != NULL) {
-            pointer = linkedlist->head->next;
-            free_element(linkedlist->head->ptr);
-            free(linkedlist->head);
-            linkedlist->head = pointer;
-        }
-    } else {
-        while (linkedlist->head != NULL) {
-            pointer = linkedlist->head->next;
-            free(linkedlist->head);
-            linkedlist->head = pointer;
-        }
-    }
-
-    linkedlist->element_count = 0;
+    if (linkedlist) {
+        while (linkedlist->head) {
+            hip_ll_del_first(linkedlist, free_element);
+        }
+        HIP_ASSERT(!linkedlist->head);
+        HIP_ASSERT(!linkedlist->element_count);
+    }
 }
 
 /**
@@ -108,7 +89,7 @@
  * @param  linkedlist the list whose node count is to be returned.
  * @return number of nodes in the list.
  */
-unsigned int hip_ll_get_size(const struct hip_ll *linkedlist)
+unsigned int hip_ll_get_size(const struct hip_ll *const linkedlist)
 {
     if (linkedlist == NULL) {
         return 0;
@@ -118,77 +99,184 @@
 }
 
 /**
+ * Get the list node with the specified index and its predecessor node.
+ *
+ * This function helps to avoid re-implementing the linear search for different
+ * purposes.
+ *
+ * @param list points to the list to search. The result of calling this
+ *             this function with list == NULL is undefined.
+ * @param idx  the index of the list node to retrieve. The first node element
+ *             has the index 0. The result of calling this function with an idx
+ *             value greater than or equal to the number of nodes in the list
+ *             is undefined.
+ * @param prev points to a struct hip_ll_node pointer. If this function returns
+ *             successfully, the value of prev is set to point to the
+ *             predecessor node of the returned node. It is set to NULL, of the
+ *             returned node is the first node in the list.
+ * @return     the list node with the index idx.
+ */
+static struct hip_ll_node *hip_ll_get_node_with_prev(const struct hip_ll *const list,
+                                                     const unsigned idx,
+                                                     struct hip_ll_node **const prev)
+{
+    unsigned            i = 0;
+    struct hip_ll_node *p = NULL;
+    struct hip_ll_node *node;
+
+    HIP_ASSERT(list);
+    HIP_ASSERT((list->element_count == 0 && !list->head) ||
+               (list->element_count == 1 && list->head && !list->head->next) ||
+               (list->element_count > 1 && list->head && list->head->next));
+    HIP_ASSERT(idx < list->element_count);
+    HIP_ASSERT(prev);
+
+    for (node = list->head; node; node = node->next) {
+        if (i != idx) {
+            p  = node;
+            i += 1;
+        } else {
+            *prev = p;
+            break;
+        }
+    }
+
+    HIP_ASSERT(node &&
+               ((idx == 0 && !*prev) ||
+                (*prev && (*prev)->next == node)));
+
+    return node;
+}
+
+/**
+ * Get the list node with the specified index.
+ *
+ * @param list points to the list to search. The result of calling this
+ *             this function with list == NULL is undefined.
+ * @param idx  the index of the list node to retrieve. The first node element
+ *             has the index 0. The result of calling this function with an idx
+ *             value greater than or equal to the number of nodes in the list
+ *             is undefined.
+ * @return     the list node with the index idx.
+ */
+static struct hip_ll_node *hip_ll_get_node(const struct hip_ll *const list,
+                                           const unsigned idx)
+{
+    struct hip_ll_node *p = NULL;
+
+    return hip_ll_get_node_with_prev(list, idx, &p);
+}
+
+/**
+ * Find the first list node associated with the specified payload data and
+ * return the list node, its index, and the predecessor node.
+ *
+ * This function helps to avoid re-implementing the linear search for different
+ * purposes.
+ *
+ * @param list points to the list to search. The result of calling this
+ *             this function with list == NULL is undefined.
+ * @param ptr  the payload pointer to find in the list. ptr may be NULL.
+ * @param idx  points to an unsigned integer object. If this function returns
+ *             successfully, the value of the integer is set to the index of
+ *             the found list item. The result of calling this function with
+ *             idx == NULL is undefined.
+ * @param prev points to a struct hip_ll_node pointer. If this function returns
+ *             successfully, the value of the node pointer is set to point to
+ *             the predecessor node of the returned node. It is set to NULL,
+ *             if the returned node is the first node in the list.
+ * @return     the first list node that points to the same payload data as ptr.
+ *             If no such list node can be found, this function returns NULL.
+ */
+static struct hip_ll_node *hip_ll_find_node_with_prev(const struct hip_ll *const list,
+                                                      const void *const ptr,
+                                                      unsigned *const idx,
+                                                      struct hip_ll_node **const prev)
+{
+    unsigned            i = 0;
+    struct hip_ll_node *p = NULL;
+    struct hip_ll_node *node;
+
+    HIP_ASSERT(list);
+    HIP_ASSERT((list->element_count == 0 && !list->head) ||
+               (list->element_count == 1 && list->head && !list->head->next) ||
+               (list->element_count > 1 && list->head && list->head->next));
+    HIP_ASSERT(idx);
+    HIP_ASSERT(prev);
+
+    for (node = list->head; node; node = node->next) {
+        if (node->ptr != ptr) {
+            p  = node;
+            i += 1;
+        } else {
+            *idx  = i;
+            *prev = p;
+            break;
+        }
+    }
+
+    HIP_ASSERT(!node ||
+               (*idx == 0 && !*prev) ||
+               (*idx > 0 && *idx < list->element_count && *prev &&
+                (*prev)->next == node));
+
+    return node;
+}
+
+/**
  * Adds a new node to a linked list. Adds a new node at @c index to the
- * parameter @c linkedlist with payload data @c ptr. If there are less than
- * (<code>index  -1</code>) elements in the list, the element will be added as
- * the last element of the list.
+ * parameter @c linkedlist with payload data @c ptr. If there are exactly
+ * <code>index</code> elements in the list, the element is added as the last
+ * element of the list.
  *
  * <b>Example:</b>
  *
- * <code>hip_ll_add(&mylist, 2, mydata);</code> will add @c mydata as the
- * third item of the list when there are more than two elements in @c mylist.
- * When there are less than two items in the list @c mydata will be added as
- * the last element of @c mylist.
+ * <code>hip_ll_add(&mylist, 2, mydata);</code> adds @c mydata as the
+ * third item of the list when there are two or more elements in @c mylist.
  *
  * @param  linkedlist the list where to add the new node.
  * @param  index      the list index where to store the node. Indexing starts
  *                    from zero.
  * @param  ptr        a pointer to the data to be stored.
  * @return            zero on success, -1 if @c linkedlist or @c ptr is NULL or
- *                    if there was an error when allocating memory to the new
- *                    node.
+ *                    index is greater than the size of list or if there is an
+ *                    error when allocating memory for the new node.
  */
-int hip_ll_add(struct hip_ll *linkedlist, const unsigned int index, void *ptr)
+int hip_ll_add(struct hip_ll *const linkedlist, const unsigned int index, void *const ptr)
 {
-    struct hip_ll_node *newnode       = NULL, *pointer = NULL;
-    unsigned int        current_index = 0;
-
-    if (linkedlist == NULL || ptr == NULL) {
-        return -1;
-    }
-
-    if ((newnode = malloc(sizeof(struct hip_ll_node))) == NULL) {
-        HIP_ERROR("Error on allocating memory for a linked list node.\n");
-        return -1;
-    }
-
-    newnode->ptr = ptr;
-    pointer      = linkedlist->head;
-
-    /* Item to add is the first item of the list or it is to be added as the
-     * first one. */
-    if (pointer == NULL || index == 0) {
-        newnode->next    = pointer;
-        linkedlist->head = newnode;
-        linkedlist->element_count++;
-    }
-    /* There exist at least one element in the list and the new element is
-     * not to be added as the first one. */
-    else {
-        struct hip_ll_node *previous = pointer;
-
-        /* Loop until "pointer" is at the last item. */
-        while (pointer->next != NULL) {
-            previous = pointer;
-            pointer  = pointer->next;
-            current_index++;
-
-            /* We have reached the target index and the index is not
-             * the index of the last item in the list. */
-            if (current_index == index) {
-                newnode->next  = pointer;
-                previous->next = newnode;
-                linkedlist->element_count++;
-                return 0;
+    if (linkedlist && index <= linkedlist->element_count && ptr) {
+        struct hip_ll_node *newnode;
+        if ((newnode = malloc(sizeof(*newnode)))) {
+            newnode->ptr = ptr;
+
+            if (index == 0) {
+                newnode->next    = linkedlist->head;
+                linkedlist->head = newnode;
+            } else {
+                // newnode is to be inserted after prev and before next
+                struct hip_ll_node *next = NULL;
+                struct hip_ll_node *prev = NULL;
+
+                if (index != linkedlist->element_count) {
+                    next = hip_ll_get_node_with_prev(linkedlist, index, &prev);
+                } else {
+                    prev = hip_ll_get_node(linkedlist, index - 1);
+                    next = NULL;
+                }
+                HIP_ASSERT(prev->next == next);
+                prev->next    = newnode;
+                newnode->next = next;
             }
+
+            linkedlist->element_count += 1;
+
+            return 0;
+        } else {
+            HIP_ERROR("Error on allocating memory for a linked list node.\n");
         }
-        /* The node is to be added as the last item of the list. */
-        newnode->next = NULL;
-        pointer->next = newnode;
-        linkedlist->element_count++;
     }
 
-    return 0;
+    return -1;
 }
 
 /**
@@ -201,7 +289,7 @@
  *                    if there was an error when allocating memory to the new
  *                    node.
  */
-int hip_ll_add_first(struct hip_ll *linkedlist, void *ptr)
+int hip_ll_add_first(struct hip_ll *const linkedlist, void *const ptr)
 {
     return hip_ll_add(linkedlist, 0, ptr);
 }
@@ -216,12 +304,55 @@
  *                    if there was an error when allocating memory to the new
  *                    node.
  */
-int hip_ll_add_last(struct hip_ll *linkedlist, void *ptr)
+int hip_ll_add_last(struct hip_ll *const linkedlist, void *const ptr)
 {
     return hip_ll_add(linkedlist, linkedlist->element_count, ptr);
 }
 
 /**
+ * Remove a node from a list and free the node memory (not the payload data).
+ *
+ * Since this function expects to be given the predecessor of the node to
+ * delete, this function has a runtime complexity of O(1).
+ *
+ * @param list the list from which to delete the node. The result of calling
+ *             this function with list == NULL is undefined.
+ * @param node the node to delete. The result of calling this function with
+ *             list == NULL is undefined.
+ * @param prev the predecessor node of the node to delete. prev must be NULL
+ *             iff node is the first node in the list. The result of calling
+ *             this function under the violation of this condition is
+ *             undefined.
+ * @return     pointer to the payload data the deleted list node was associated
+ *             with.
+ */
+static void *hip_ll_del_node(struct hip_ll *const list,
+                             struct hip_ll_node *const node,
+                             struct hip_ll_node *const prev)
+{
+    void *payload;
+
+    HIP_ASSERT(list);
+    HIP_ASSERT(node);
+    HIP_ASSERT((prev && prev->next == node) ||
+               (!prev && list->head == node));
+    HIP_ASSERT((list->element_count == 1 && list->head && !list->head->next) ||
+               (list->element_count > 1 && list->head && list->head->next));
+
+    payload = node->ptr;
+
+    if (prev) {
+        prev->next = node->next;
+    } else {
+        list->head = node->next;
+    }
+    free(node);
+    list->element_count -= 1;
+
+    return payload;
+}
+
+/**
  * Deletes a node from a linked list. Deletes a node at @c index and frees the
  * memory allocated for the node from the parameter @c linkedlist. If there are
  * less than (<code>index  -1</code>) nodes in the list no action will be taken. If
@@ -244,58 +375,25 @@
  *                     element itself is deleted. NULL is also returned when
  *                     the list @c linkedlist itself is NULL.
  */
-void *hip_ll_del(struct hip_ll *linkedlist, const unsigned int index,
+void *hip_ll_del(struct hip_ll *const linkedlist, const unsigned int index,
                  free_elem_fn free_element)
 {
-    struct hip_ll_node *pointer       = NULL, *previous = NULL;
-    void               *ptr           = NULL;
-    unsigned int        current_index = 0;
-
-    if (linkedlist == NULL || linkedlist->head == NULL) {
-        return NULL;
-    } else if (index > (linkedlist->element_count - 1)) {
-        return NULL;
-    }
-
-    if (index == 0) {
-        ptr     = linkedlist->head->ptr;
-        pointer = linkedlist->head->next;
-        if (free_element != NULL) {
-            free_element(ptr);
-            ptr = NULL;
-        }
-        free(linkedlist->head);
-        linkedlist->head = pointer;
-        linkedlist->element_count--;
-        return ptr;
-    }
-
-    pointer = previous = linkedlist->head;
-
-    while (pointer->next != NULL) {
-        previous = pointer;
-        pointer  = pointer->next;
-        current_index++;
-
-        /* We have reached the target index. */
-        if (current_index == index) {
-            if (pointer == NULL) {
-                previous->next = NULL;
-            } else {
-                previous->next = pointer->next;
-            }
-            ptr = pointer->ptr;
-            if (free_element != NULL) {
-                free_element(ptr);
-                ptr = NULL;
-            }
-            free(pointer);
-            linkedlist->element_count--;
-            break;
-        }
-    }
-
-    return ptr;
+    if (linkedlist && index < linkedlist->element_count) {
+        struct hip_ll_node *node = NULL;
+        struct hip_ll_node *prev = NULL;
+        void               *payload;
+
+        node    = hip_ll_get_node_with_prev(linkedlist, index, &prev);
+        payload = hip_ll_del_node(linkedlist, node, prev);
+        if (free_element) {
+            free_element(payload);
+            return NULL;
+        } else {
+            return payload;
+        }
+    } else {
+        return NULL;
+    }
 }
 
 /**
@@ -317,13 +415,60 @@
  *                     deleted. NULL is also returned when the list
  *                     @c linkedlist itself is NULL.
  */
-void *hip_ll_del_first(struct hip_ll *linkedlist,
+void *hip_ll_del_first(struct hip_ll *const linkedlist,
                        free_elem_fn free_element)
 {
     return hip_ll_del(linkedlist, 0, free_element);
 }
 
 /**
+ * Delete the first list element which contains the specified payload data
+ * item from a linked list.
+ *
+ * @param list         points to the list from which to delete the element.
+ *                     The result of calling this function with
+ *                     list == NULL is undefined.
+ * @param ptr          points to payload data which has previously been added
+ *                     to list via one of the hip_ll_add() functions. If
+ *                     no list element contains ptr, no list element is deleted.
+ * @param free_element points to an optional callback function that is called
+ *                     when a list element matches ptr, typically in order to
+ *                     free the memory associated with ptr. If free_element is
+ *                     NULL, the list element is removed from list but
+ *                     the memory associated with the list element is not freed
+ *                     and returned by this function instead. If free_element
+ *                     is not NULL, the payload ptr should have been added to
+ *                     list only once. Otherwise, the latter list
+ *                     elements referring to ptr point to de-allocated memory.
+ * @return             NULL if the payload ptr is not in list. Returns
+ *                     NULL if the payload ptr is found in list and
+ *                     free_element is not NULL. Returns ptr if the payload ptr
+ *                     is found in the list and free_element is NULL.
+ */
+void *hip_ll_del_by_payload(struct hip_ll *const list,
+                            void *const ptr,
+                            free_elem_fn free_element)
+{
+    if (list) {
+        struct hip_ll_node *node = NULL;
+        struct hip_ll_node *prev = NULL;
+        unsigned            idx  = 0;
+
+        node = hip_ll_find_node_with_prev(list, ptr, &idx, &prev);
+        if (node) {
+            hip_ll_del_node(list, node, prev);
+            if (!free_element) {
+                return ptr;
+            } else {
+                free_element(ptr);
+            }
+        }
+    }
+
+    return NULL;
+}
+
+/**
  * Gets an element from a linked list. Returns a pointer to the payload data
  * stored in node at @c index. When there are less than (<code>index  -1</code>)
  * nodes in the list, no action will be taken.
@@ -334,27 +479,15 @@
  * @return           the next element or NULL if the list end has been reached
  *                   or if @c linkedlist is NULL.
  */
-void *hip_ll_get(struct hip_ll *linkedlist, const unsigned int index)
+void *hip_ll_get(const struct hip_ll *const linkedlist, const unsigned int index)
 {
-    struct hip_ll_node *pointer       = linkedlist->head;
-    unsigned int        current_index = 0;
-
-    if (linkedlist == NULL || linkedlist->head == NULL) {
-        return NULL;
-    } else if (index > (linkedlist->element_count - 1)) {
-        return NULL;
-    }
-
-    while (pointer != NULL) {
-        if (current_index == index) {
-            break;
-        }
-
-        pointer = pointer->next;
-        current_index++;
-    }
-
-    return pointer->ptr;
+    if (linkedlist && index < linkedlist->element_count) {
+        struct hip_ll_node *const node = hip_ll_get_node(linkedlist, index);
+        HIP_ASSERT(node);
+        return node->ptr;
+    } else {
+        return NULL;
+    }
 }
 
 /**
@@ -379,8 +512,8 @@
  *                    using this function.</span> Consider hip_ll_del() or
  *                    hip_ll_uninit() for deleting nodes and elements.
  */
-struct hip_ll_node *hip_ll_iterate(const struct hip_ll *linkedlist,
-                                   struct hip_ll_node *current)
+const struct hip_ll_node *hip_ll_iterate(const struct hip_ll *const linkedlist,
+                                         const struct hip_ll_node *const current)
 {
     if (linkedlist == NULL) {
         return NULL;

=== modified file 'lib/core/linkedlist.h'
--- lib/core/linkedlist.h	2011-03-29 16:48:08 +0000
+++ lib/core/linkedlist.h	2011-04-02 01:16:32 +0000
@@ -61,19 +61,21 @@
 #define HIP_LL_INIT { 0, NULL }
 
 /** Linked list element memory deallocator function pointer. */
-typedef void (*free_elem_fn)(void *ptr);
+typedef void (*free_elem_fn)(void *const ptr);
 
-void hip_ll_init(struct hip_ll *linkedlist);
-void hip_ll_uninit(struct hip_ll *linkedlist, free_elem_fn free_element);
-unsigned int hip_ll_get_size(const struct hip_ll *linkedlist);
-int hip_ll_add(struct hip_ll *linkedlist, const unsigned int index, void *ptr);
-int hip_ll_add_first(struct hip_ll *linkedlist, void *ptr);
-int hip_ll_add_last(struct hip_ll *linkedlist, void *ptr);
-void *hip_ll_del(struct hip_ll *linkedlist, const unsigned int index,
+void hip_ll_init(struct hip_ll *const linkedlist);
+void hip_ll_uninit(struct hip_ll *const linkedlist, free_elem_fn free_element);
+unsigned int hip_ll_get_size(const struct hip_ll *const linkedlist);
+int hip_ll_add(struct hip_ll *const linkedlist, const unsigned int index, void *const ptr);
+int hip_ll_add_first(struct hip_ll *const linkedlist, void *const ptr);
+int hip_ll_add_last(struct hip_ll *const linkedlist, void *const ptr);
+void *hip_ll_del(struct hip_ll *const linkedlist, const unsigned int index,
                  free_elem_fn free_element);
-void *hip_ll_del_first(struct hip_ll *linkedlist, free_elem_fn free_element);
-void *hip_ll_get(struct hip_ll *linkedlist, const unsigned int index);
-struct hip_ll_node *hip_ll_iterate(const struct hip_ll *linkedlist,
-                                   struct hip_ll_node *current);
+void *hip_ll_del_first(struct hip_ll *const linkedlist, free_elem_fn free_element);
+void *hip_ll_del_by_payload(struct hip_ll *const list, void *const ptr,
+                            free_elem_fn free_element);
+void *hip_ll_get(const struct hip_ll *const linkedlist, const unsigned int index);
+const struct hip_ll_node *hip_ll_iterate(const struct hip_ll *const linkedlist,
+                                         const struct hip_ll_node *const current);
 
 #endif /* HIP_LIB_CORE_LINKEDLIST_H */

=== modified file 'lib/core/modularization.c'
--- lib/core/modularization.c	2011-04-01 12:30:35 +0000
+++ lib/core/modularization.c	2011-04-02 01:16:32 +0000
@@ -165,8 +165,8 @@
  */
 void lmod_init_state_items(struct modular_state *state)
 {
-    struct hip_ll_node *iter = NULL;
-    int                 (*init_function)(struct modular_state *state) = NULL;
+    const struct hip_ll_node *iter = NULL;
+    int                       (*init_function)(struct modular_state *state) = NULL;
 
     while ((iter = hip_ll_iterate(&state_init_functions, iter))) {
         init_function = iter->ptr;
@@ -300,9 +300,9 @@
                                       void *entry,
                                       const uint16_t priority)
 {
-    int                 idx      = 0;
-    struct hip_ll      *new_list = NULL;
-    struct hip_ll_node *iter     = NULL;
+    int                       idx      = 0;
+    struct hip_ll            *new_list = NULL;
+    const struct hip_ll_node *iter     = NULL;
 
     if (!list) {
         if (!(new_list = malloc(sizeof(struct hip_ll)))) {
@@ -342,8 +342,8 @@
  */
 int lmod_unregister_function(struct hip_ll *list, const void *function)
 {
-    int                 idx  = 0;
-    struct hip_ll_node *iter = NULL;
+    int                       idx  = 0;
+    const struct hip_ll_node *iter = NULL;
 
     if (!list) {
         return -1;
@@ -440,8 +440,8 @@
  */
 int lmod_packet_type_exists(const uint8_t packet_type)
 {
-    int                 idx  = 0;
-    struct hip_ll_node *iter = NULL;
+    int                       idx  = 0;
+    const struct hip_ll_node *iter = NULL;
 
     while ((iter = hip_ll_iterate(&packet_types, iter))) {
         if (packet_type == ((struct packet_type *) iter->ptr)->num) {
@@ -461,7 +461,7 @@
  */
 const char *lmod_get_packet_identifier(const uint8_t packet_type)
 {
-    struct hip_ll_node *iter = NULL;
+    const struct hip_ll_node *iter = NULL;
     HIP_DEBUG("Name search for packet type %d \n", packet_type);
 
     while ((iter = hip_ll_iterate(&packet_types, iter))) {
@@ -489,9 +489,9 @@
 int lmod_register_packet_type(const uint8_t packet_type,
                               const char *const identifier)
 {
-    int                 idx       = 0;
-    struct hip_ll_node *iter      = NULL;
-    struct packet_type *new_entry = NULL;
+    int                       idx       = 0;
+    const struct hip_ll_node *iter      = NULL;
+    struct packet_type       *new_entry = NULL;
 
     if (!identifier || (lmod_packet_type_exists(packet_type) != -1)) {
         return -1;
@@ -559,8 +559,8 @@
  */
 int lmod_parameter_type_exists(const uint16_t parameter_type)
 {
-    int                 index = 0;
-    struct hip_ll_node *iter  = NULL;
+    int                       index = 0;
+    const struct hip_ll_node *iter  = NULL;
 
     while ((iter = hip_ll_iterate(&parameter_types, iter))) {
         if (parameter_type == ((struct parameter_type *) iter->ptr)->num) {
@@ -589,10 +589,10 @@
 int lmod_register_parameter_type(const uint16_t parameter_type,
                                  const char *const identifier)
 {
-    int                    index     = 0;
-    struct hip_ll_node    *iter      = NULL;
-    struct parameter_type *new_entry = NULL;
-    int                    err       = 0;
+    int                       index     = 0;
+    const struct hip_ll_node *iter      = NULL;
+    struct parameter_type    *new_entry = NULL;
+    int                       err       = 0;
 
     HIP_IFEL(!identifier || (lmod_parameter_type_exists(parameter_type) != -1),
              -1, "Missing identifier or parameter type already registered.\n");
@@ -633,7 +633,7 @@
  */
 const char *lmod_get_parameter_identifier(const uint16_t parameter_type)
 {
-    struct hip_ll_node *iter = NULL;
+    const struct hip_ll_node *iter = NULL;
     HIP_DEBUG("Name search for parameter type %d \n", parameter_type);
 
     while ((iter = hip_ll_iterate(&parameter_types, iter))) {

=== modified file 'test/check_lib_core.c'
--- test/check_lib_core.c	2011-02-18 14:39:38 +0000
+++ test/check_lib_core.c	2011-04-02 01:16:32 +0000
@@ -38,6 +38,7 @@
 {
     int      number_failed;
     SRunner *sr = srunner_create(lib_core_hit());
+    srunner_add_suite(sr, lib_core_linkedlist());
     srunner_add_suite(sr, lib_core_straddr());
 
     srunner_run_all(sr, CK_NORMAL);

=== added file 'test/lib/core/linkedlist.c'
--- test/lib/core/linkedlist.c	1970-01-01 00:00:00 +0000
+++ test/lib/core/linkedlist.c	2011-04-02 01:16:32 +0000
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2010 Aalto University and RWTH Aachen University.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * @file
+ * @author Stefan Goetz <[e-mail]>
+ */
+
+#include <check.h>
+#include <stdlib.h>
+
+#include "lib/core/linkedlist.h"
+#include "test_suites.h"
+
+static struct hip_ll *list;
+
+static void cleanup(void *const p)
+{
+    fail_unless(p == list);
+};
+
+START_TEST(test_hip_ll_del_by_payload_without_cleanup)
+{
+    struct hip_ll l;
+    hip_ll_init(&l);
+    hip_ll_add_first(&l, &l);
+    fail_unless(hip_ll_del_by_payload(&l, &l, NULL) == &l, NULL);
+    fail_unless(hip_ll_get_size(&l) == 0, NULL);
+}
+END_TEST START_TEST(test_hip_ll_del_by_payload_with_cleanup)
+{
+    list = malloc(sizeof(*list));
+    hip_ll_init(list);
+    hip_ll_add_first(list, list);
+    fail_unless(hip_ll_del_by_payload(list, list, cleanup) == NULL, NULL);
+    fail_unless(hip_ll_get_size(list) == 0, NULL);
+    free(list);
+}
+
+END_TEST START_TEST(test_hip_ll_del_by_payload_with_invalid_payload)
+{
+    struct hip_ll l;
+    hip_ll_init(&l);
+    hip_ll_add_first(&l, &l);
+    fail_unless(hip_ll_del_by_payload(&l, NULL, NULL) == NULL, NULL);
+    fail_unless(hip_ll_get_size(&l) == 1, NULL);
+}
+
+END_TEST START_TEST(test_hip_ll_del_by_payload_with_invalid_list)
+{
+    fail_unless(hip_ll_del_by_payload(NULL, NULL, NULL) == NULL, NULL);
+}
+
+END_TEST
+
+Suite *lib_core_linkedlist(void)
+{
+    Suite *s = suite_create("lib/core/linkedlist");
+
+    TCase *tc_linkedlist = tcase_create("Linked List");
+    tcase_add_test(tc_linkedlist, test_hip_ll_del_by_payload_without_cleanup);
+    tcase_add_test(tc_linkedlist, test_hip_ll_del_by_payload_with_cleanup);
+    tcase_add_test(tc_linkedlist, test_hip_ll_del_by_payload_with_invalid_payload);
+    tcase_add_test(tc_linkedlist, test_hip_ll_del_by_payload_with_invalid_list);
+    suite_add_tcase(s, tc_linkedlist);
+
+    return s;
+}

=== modified file 'test/lib/core/test_suites.h'
--- test/lib/core/test_suites.h	2011-02-18 14:39:38 +0000
+++ test/lib/core/test_suites.h	2011-04-02 01:16:32 +0000
@@ -29,6 +29,7 @@
 #include <check.h>
 
 Suite *lib_core_hit(void);
+Suite *lib_core_linkedlist(void);
 Suite *lib_core_straddr(void);
 
 #endif /* HIP_TEST_LIB_CORE_TEST_SUITES_H */