1 /*********************************************************************************************************
2 * Software License Agreement (BSD License) *
3 * Author: Sebastien Decugis <sdecugis@freediameter.net> *
4 * *
5 * Copyright (c) 2013, WIDE Project and NICT *
6 * All rights reserved. *
7 * *
8 * Redistribution and use of this software in source and binary forms, with or without modification, are *
9 * permitted provided that the following conditions are met: *
10 * *
11 * * Redistributions of source code must retain the above *
12 * copyright notice, this list of conditions and the *
13 * following disclaimer. *
14 * *
15 * * Redistributions in binary form must reproduce the above *
16 * copyright notice, this list of conditions and the *
17 * following disclaimer in the documentation and/or other *
18 * materials provided with the distribution. *
19 * *
20 * * Neither the name of the WIDE Project or NICT nor the *
21 * names of its contributors may be used to endorse or *
22 * promote products derived from this software without *
23 * specific prior written permission of WIDE Project and *
24 * NICT. *
25 * *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED *
27 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
28 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR *
29 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS *
31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR *
32 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF *
33 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
34 *********************************************************************************************************/
35
36 #include "fdproto-internal.h"
37
38 /* Initialize a list element */
fd_list_init(struct fd_list * list,void * obj)39 void fd_list_init ( struct fd_list * list, void * obj )
40 {
41 memset(list, 0, sizeof(struct fd_list));
42 list->next = list;
43 list->prev = list;
44 list->head = list;
45 list->o = obj;
46 }
47
48 #define CHECK_SINGLE( li ) { \
49 ASSERT( ((struct fd_list *)(li))->next == (li) ); \
50 ASSERT( ((struct fd_list *)(li))->prev == (li) ); \
51 ASSERT( ((struct fd_list *)(li))->head == (li) ); \
52 }
53
54 /* insert after a reference, checks done */
list_insert_after(struct fd_list * ref,struct fd_list * item)55 static void list_insert_after( struct fd_list * ref, struct fd_list * item )
56 {
57 item->prev = ref;
58 item->next = ref->next;
59 item->head = ref->head;
60 ref->next->prev = item;
61 ref->next = item;
62 }
63
64 /* insert after a reference */
fd_list_insert_after(struct fd_list * ref,struct fd_list * item)65 void fd_list_insert_after ( struct fd_list * ref, struct fd_list * item )
66 {
67 ASSERT(item != NULL);
68 ASSERT(ref != NULL);
69 CHECK_SINGLE ( item );
70 ASSERT(ref->head != item);
71 list_insert_after(ref, item);
72 }
73
74 /* Move all elements of list senti at the end of list ref */
fd_list_move_end(struct fd_list * ref,struct fd_list * senti)75 void fd_list_move_end(struct fd_list * ref, struct fd_list * senti)
76 {
77 struct fd_list * li;
78 ASSERT(ref->head == ref);
79 ASSERT(senti->head == senti);
80
81 if (senti->next == senti)
82 return;
83
84 for (li = senti->next; li != senti; li = li->next)
85 li->head = ref;
86
87 senti->next->prev = ref->prev;
88 ref->prev->next = senti->next;
89 senti->prev->next = ref;
90 ref->prev = senti->prev;
91 senti->prev = senti;
92 senti->next = senti;
93 }
94
95 /* insert before a reference, checks done */
list_insert_before(struct fd_list * ref,struct fd_list * item)96 static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
97 {
98 item->prev = ref->prev;
99 item->next = ref;
100 item->head = ref->head;
101 ref->prev->next = item;
102 ref->prev = item;
103 }
104
105 /* insert before a reference */
fd_list_insert_before(struct fd_list * ref,struct fd_list * item)106 void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
107 {
108 ASSERT(item != NULL);
109 ASSERT(ref != NULL);
110 CHECK_SINGLE ( item );
111 ASSERT(ref->head != item);
112 list_insert_before(ref, item);
113 }
114
115 /* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
fd_list_insert_ordered(struct fd_list * head,struct fd_list * item,int (* cmp_fct)(void *,void *),void ** ref_duplicate)116 int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (*cmp_fct)(void *, void *), void ** ref_duplicate)
117 {
118 struct fd_list * ptr = head;
119 int cmp;
120
121 /* Some debug sanity checks */
122 ASSERT(head != NULL);
123 ASSERT(item != NULL);
124 ASSERT(cmp_fct != NULL);
125 ASSERT(head->head == head);
126 CHECK_SINGLE ( item );
127
128 /* loop in the list */
129 while (ptr->next != head)
130 {
131 /* Compare the object to insert with the next object in list */
132 cmp = cmp_fct( item->o, ptr->next->o );
133 if (!cmp) {
134 /* An element with the same key already exists */
135 if (ref_duplicate != NULL)
136 *ref_duplicate = ptr->next->o;
137 return EEXIST;
138 }
139
140 if (cmp < 0)
141 break; /* We must insert the element here */
142
143 ptr = ptr->next;
144 }
145
146 /* Now insert the element between ptr and ptr->next */
147 list_insert_after( ptr, item );
148
149 /* Ok */
150 return 0;
151 }
152
153 /* Unlink an object */
fd_list_unlink(struct fd_list * item)154 void fd_list_unlink ( struct fd_list * item )
155 {
156 ASSERT(item != NULL);
157 if (item->head == item)
158 return;
159 /* unlink */
160 item->next->prev = item->prev;
161 item->prev->next = item->next;
162 /* sanitize */
163 item->next = item;
164 item->prev = item;
165 item->head = item;
166 }
167
168
169