Mercurial > hg > freeDiameter

comparison libfdproto/lists.c @ 658:f198d16fa7f4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial commit for 1.1.0: * Restructuring: * libfreeDiameter: - renamed folder & binary into libfdproto - renamed libfD.h into fdproto-internal.h - removed signals management (replaced by triggers in libfdcore) * freeDiameter split into: - libfdcore (most contents) - renamed fD.h into fdcore-internal.h - added core.c for framework init/shutdown. - new triggers mechanism in events.c. - freeDiameterd (main, command line parsing, signals management) * tests: - now in top-level directory tests. * other changes: - fd_dict_new now returns 0 on duplicate identical entries. - fixes in dict_legacy_xml - fixes in some dictionaries - moved FD_DEFAULT_CONF_FILENAME definition to freeDiameter-host.h
author Sebastien Decugis <sdecugis@nict.go.jp>
date Fri, 14 Jan 2011 15:15:23 +0900
parents libfreeDiameter/lists.c@c662d3eb6ff6
children 2e94ef0515d7
comparison
equal deleted inserted replaced
656:5b05d85682f1 658:f198d16fa7f4
1 /*********************************************************************************************************
2 * Software License Agreement (BSD License) *
3 * Author: Sebastien Decugis <sdecugis@nict.go.jp> *
4 * *
5 * Copyright (c) 2009, 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 ASSERT(ref->head == ref);
78 ASSERT(senti->head == senti);
79
80 if (senti->next == senti)
81 return;
82
83 senti->next->prev = ref->prev;
84 ref->prev->next = senti->next;
85 senti->prev->next = ref;
86 ref->prev = senti->prev;
87 senti->prev = senti;
88 senti->next = senti;
89 }
90
91 /* insert before a reference, checks done */
92 static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
93 {
94 item->prev = ref->prev;
95 item->next = ref;
96 item->head = ref->head;
97 ref->prev->next = item;
98 ref->prev = item;
99 }
100
101 /* insert before a reference */
102 void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
103 {
104 ASSERT(item != NULL);
105 ASSERT(ref != NULL);
106 CHECK_SINGLE ( item );
107 ASSERT(ref->head != item);
108 list_insert_before(ref, item);
109 }
110
111 /* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
112 int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (*cmp_fct)(void *, void *), void ** ref_duplicate)
113 {
114 struct fd_list * ptr = head;
115 int cmp;
116
117 /* Some debug sanity checks */
118 ASSERT(head != NULL);
119 ASSERT(item != NULL);
120 ASSERT(cmp_fct != NULL);
121 ASSERT(head->head == head);
122 CHECK_SINGLE ( item );
123
124 /* loop in the list */
125 while (ptr->next != head)
126 {
127 /* Compare the object to insert with the next object in list */
128 cmp = cmp_fct( item->o, ptr->next->o );
129 if (!cmp) {
130 /* An element with the same key already exists */
131 if (ref_duplicate != NULL)
132 *ref_duplicate = ptr->next->o;
133 return EEXIST;
134 }
135
136 if (cmp < 0)
137 break; /* We must insert the element here */
138
139 ptr = ptr->next;
140 }
141
142 /* Now insert the element between ptr and ptr->next */
143 list_insert_after( ptr, item );
144
145 /* Ok */
146 return 0;
147 }
148
149 /* Unlink an object */
150 void fd_list_unlink ( struct fd_list * item )
151 {
152 ASSERT(item != NULL);
153 if (item->head == item)
154 return;
155 /* unlink */
156 item->next->prev = item->prev;
157 item->prev->next = item->next;
158 /* sanitize */
159 item->next = item;
160 item->prev = item;
161 item->head = item;
162 }
163
164
165 /********************************************************************************************************/
166 /* Hash function -- credits to Austin Appleby, thank you ^^ */
167 /* See http://murmurhash.googlepages.com for more information on this function */
168
169 /* the strings are NOT always aligned properly (ex: received in RADIUS message), so we use the aligned MurmurHash2 function as needed */
170 #define _HASH_MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
171 uint32_t fd_hash ( char * string, size_t len )
172 {
173 uint32_t hash = len;
174 char * data = string;
175
176 const unsigned int m = 0x5bd1e995;
177 const int r = 24;
178 int align = (long)string & 3;
179
180 if (!align || (len < 4)) {
181
182 /* In case data is aligned, MurmurHash2 function */
183 while(len >= 4)
184 {
185 /* Mix 4 bytes at a time into the hash */
186 uint32_t k = *(uint32_t *)data; /* We don't care about the byte order */
187
188 _HASH_MIX(hash, k, m);
189
190 data += 4;
191 len -= 4;
192 }
193
194 /* Handle the last few bytes of the input */
195 switch(len) {
196 case 3: hash ^= data[2] << 16;
197 case 2: hash ^= data[1] << 8;
198 case 1: hash ^= data[0];
199 hash *= m;
200 }
201
202 } else {
203 /* Unaligned data, use alignment-safe slower version */
204
205 /* Pre-load the temp registers */
206 uint32_t t = 0, d = 0;
207 switch(align)
208 {
209 case 1: t |= data[2] << 16;
210 case 2: t |= data[1] << 8;
211 case 3: t |= data[0];
212 }
213 t <<= (8 * align);
214
215 data += 4-align;
216 len -= 4-align;
217
218 /* From this point, "data" can be read by chunks of 4 bytes */
219
220 int sl = 8 * (4-align);
221 int sr = 8 * align;
222
223 /* Mix */
224 while(len >= 4)
225 {
226 uint32_t k;
227
228 d = *(unsigned int *)data;
229 k = (t >> sr) | (d << sl);
230
231 _HASH_MIX(hash, k, m);
232
233 t = d;
234
235 data += 4;
236 len -= 4;
237 }
238
239 /* Handle leftover data in temp registers */
240 d = 0;
241 if(len >= align)
242 {
243 uint32_t k;
244
245 switch(align)
246 {
247 case 3: d |= data[2] << 16;
248 case 2: d |= data[1] << 8;
249 case 1: d |= data[0];
250 }
251
252 k = (t >> sr) | (d << sl);
253 _HASH_MIX(hash, k, m);
254
255 data += align;
256 len -= align;
257
258 /* Handle tail bytes */
259
260 switch(len)
261 {
262 case 3: hash ^= data[2] << 16;
263 case 2: hash ^= data[1] << 8;
264 case 1: hash ^= data[0];
265 hash *= m;
266 };
267 }
268 else
269 {
270 switch(len)
271 {
272 case 3: d |= data[2] << 16;
273 case 2: d |= data[1] << 8;
274 case 1: d |= data[0];
275 case 0: hash ^= (t >> sr) | (d << sl);
276 hash *= m;
277 }
278 }
279
280
281 }
282
283 /* Do a few final mixes of the hash to ensure the last few
284 bytes are well-incorporated. */
285 hash ^= hash >> 13;
286 hash *= m;
287 hash ^= hash >> 15;
288
289 return hash;
290 }
"Welcome to our mercurial repository"