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 */ |
---|
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 */ |
---|
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 */ |
---|
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 */ |
---|
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 */ |
---|
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 */ |
---|
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 */ |
---|
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 */ |
---|
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 | |
---|