Initial commit
Change-Id: I6a4444e3c193dae437cd7929f4c39aba7b749efa
diff --git a/libfdproto/lists.c b/libfdproto/lists.c
new file mode 100644
index 0000000..2aa1429
--- /dev/null
+++ b/libfdproto/lists.c
@@ -0,0 +1,168 @@
+/*********************************************************************************************************
+* Software License Agreement (BSD License) *
+* Author: Sebastien Decugis <sdecugis@freediameter.net> *
+* *
+* Copyright (c) 2013, WIDE Project and NICT *
+* All rights reserved. *
+* *
+* Redistribution and use of this software in source and binary forms, with or without modification, are *
+* permitted provided that the following conditions are met: *
+* *
+* * Redistributions of source code must retain the above *
+* copyright notice, this list of conditions and the *
+* following disclaimer. *
+* *
+* * Redistributions in binary form must reproduce the above *
+* copyright notice, this list of conditions and the *
+* following disclaimer in the documentation and/or other *
+* materials provided with the distribution. *
+* *
+* * Neither the name of the WIDE Project or NICT nor the *
+* names of its contributors may be used to endorse or *
+* promote products derived from this software without *
+* specific prior written permission of WIDE Project and *
+* NICT. *
+* *
+* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
+* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
+* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
+* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
+* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *
+* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
+* TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
+* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
+*********************************************************************************************************/
+
+#include "fdproto-internal.h"
+
+/* Initialize a list element */
+void fd_list_init ( struct fd_list * list, void * obj )
+{
+ memset(list, 0, sizeof(struct fd_list));
+ list->next = list;
+ list->prev = list;
+ list->head = list;
+ list->o = obj;
+}
+
+#define CHECK_SINGLE( li ) { \
+ ASSERT( ((struct fd_list *)(li))->next == (li) ); \
+ ASSERT( ((struct fd_list *)(li))->prev == (li) ); \
+ ASSERT( ((struct fd_list *)(li))->head == (li) ); \
+}
+
+/* insert after a reference, checks done */
+static void list_insert_after( struct fd_list * ref, struct fd_list * item )
+{
+ item->prev = ref;
+ item->next = ref->next;
+ item->head = ref->head;
+ ref->next->prev = item;
+ ref->next = item;
+}
+
+/* insert after a reference */
+void fd_list_insert_after ( struct fd_list * ref, struct fd_list * item )
+{
+ ASSERT(item != NULL);
+ ASSERT(ref != NULL);
+ CHECK_SINGLE ( item );
+ ASSERT(ref->head != item);
+ list_insert_after(ref, item);
+}
+
+/* Move all elements of list senti at the end of list ref */
+void fd_list_move_end(struct fd_list * ref, struct fd_list * senti)
+{
+ struct fd_list * li;
+ ASSERT(ref->head == ref);
+ ASSERT(senti->head == senti);
+
+ if (senti->next == senti)
+ return;
+
+ for (li = senti->next; li != senti; li = li->next)
+ li->head = ref;
+
+ senti->next->prev = ref->prev;
+ ref->prev->next = senti->next;
+ senti->prev->next = ref;
+ ref->prev = senti->prev;
+ senti->prev = senti;
+ senti->next = senti;
+}
+
+/* insert before a reference, checks done */
+static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
+{
+ item->prev = ref->prev;
+ item->next = ref;
+ item->head = ref->head;
+ ref->prev->next = item;
+ ref->prev = item;
+}
+
+/* insert before a reference */
+void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
+{
+ ASSERT(item != NULL);
+ ASSERT(ref != NULL);
+ CHECK_SINGLE ( item );
+ ASSERT(ref->head != item);
+ list_insert_before(ref, item);
+}
+
+/* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
+int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (*cmp_fct)(void *, void *), void ** ref_duplicate)
+{
+ struct fd_list * ptr = head;
+ int cmp;
+
+ /* Some debug sanity checks */
+ ASSERT(head != NULL);
+ ASSERT(item != NULL);
+ ASSERT(cmp_fct != NULL);
+ ASSERT(head->head == head);
+ CHECK_SINGLE ( item );
+
+ /* loop in the list */
+ while (ptr->next != head)
+ {
+ /* Compare the object to insert with the next object in list */
+ cmp = cmp_fct( item->o, ptr->next->o );
+ if (!cmp) {
+ /* An element with the same key already exists */
+ if (ref_duplicate != NULL)
+ *ref_duplicate = ptr->next->o;
+ return EEXIST;
+ }
+
+ if (cmp < 0)
+ break; /* We must insert the element here */
+
+ ptr = ptr->next;
+ }
+
+ /* Now insert the element between ptr and ptr->next */
+ list_insert_after( ptr, item );
+
+ /* Ok */
+ return 0;
+}
+
+/* Unlink an object */
+void fd_list_unlink ( struct fd_list * item )
+{
+ ASSERT(item != NULL);
+ if (item->head == item)
+ return;
+ /* unlink */
+ item->next->prev = item->prev;
+ item->prev->next = item->next;
+ /* sanitize */
+ item->next = item;
+ item->prev = item;
+ item->head = item;
+}
+
+