lists.c @ 25:67ca08d5bc48

Last change on this file since 25:67ca08d5bc48 was 25:67ca08d5bc48, checked in by Sebastien Decugis <sdecugis@nict.go.jp>, 11 years ago
Completed connection context files
File size: 7.7 KB

Line
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 "libfD.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
92	/* insert before a reference, checks done */
93	static void list_insert_before ( struct fd_list * ref, struct fd_list * item )
94	{
95	item->prev = ref->prev;
96	item->next = ref;
97	item->head = ref->head;
98	ref->prev->next = item;
99	ref->prev = item;
100	}
101
102	/* insert before a reference */
103	void fd_list_insert_before ( struct fd_list * ref, struct fd_list * item )
104	{
105	ASSERT(item != NULL);
106	ASSERT(ref != NULL);
107	CHECK_SINGLE ( item );
108	ASSERT(ref->head != item);
109	list_insert_before(ref, item);
110	}
111
112	/* Insert an item in an ordered list -- ordering function provided. If duplicate object found, it is returned in ref_duplicate */
113	int fd_list_insert_ordered( struct fd_list * head, struct fd_list * item, int (cmp_fct)(void , void ), void * ref_duplicate)
114	{
115	struct fd_list * ptr = head;
116	int cmp;
117
118	/* Some debug sanity checks */
119	ASSERT(head != NULL);
120	ASSERT(item != NULL);
121	ASSERT(cmp_fct != NULL);
122	ASSERT(head->head == head);
123	CHECK_SINGLE ( item );
124
125	/* loop in the list */
126	while (ptr->next != head)
127	{
128	/* Compare the object to insert with the next object in list */
129	cmp = cmp_fct( item->o, ptr->next->o );
130	if (!cmp) {
131	/* An element with the same key already exists */
132	if (ref_duplicate != NULL)
133	*ref_duplicate = ptr->next->o;
134	return EEXIST;
135	}
136
137	if (cmp < 0)
138	break; /* We must insert the element here */
139
140	ptr = ptr->next;
141	}
142
143	/* Now insert the element between ptr and ptr->next */
144	list_insert_after( ptr, item );
145
146	/* Ok */
147	return 0;
148	}
149
150	/* Unlink an object */
151	void fd_list_unlink ( struct fd_list * item )
152	{
153	ASSERT(item != NULL);
154	if (item->head == item)
155	return;
156	/* unlink */
157	item->next->prev = item->prev;
158	item->prev->next = item->next;
159	/* sanitize */
160	item->next = item;
161	item->prev = item;
162	item->head = item;
163	}
164
165
166	/********************************************************************************************************/
167	/* Hash function -- credits to Austin Appleby, thank you ^^ */
168	/* See http://murmurhash.googlepages.com for more information on this function */
169
170	/* the strings are NOT always aligned properly (ex: received in RADIUS message), so we use the aligned MurmurHash2 function as needed */
171	#define _HASH_MIX(h,k,m) { k = m; k ^= k >> r; k = m; h *= m; h ^= k; }
172	uint32_t fd_hash ( char * string, size_t len )
173	{
174	uint32_t hash = len;
175	char * data = string;
176
177	const unsigned int m = 0x5bd1e995;
178	const int r = 24;
179	int align = (long)string & 3;
180
181	if (!align \|\| (len < 4)) {
182
183	/* In case data is aligned, MurmurHash2 function */
184	while(len >= 4)
185	{
186	/* Mix 4 bytes at a time into the hash */
187	uint32_t k = (uint32_t )data; /* We don't care about the byte order */
188
189	_HASH_MIX(hash, k, m);
190
191	data += 4;
192	len -= 4;
193	}
194
195	/* Handle the last few bytes of the input */
196	switch(len) {
197	case 3: hash ^= data[2] << 16;
198	case 2: hash ^= data[1] << 8;
199	case 1: hash ^= data[0];
200	hash *= m;
201	}
202
203	} else {
204	/* Unaligned data, use alignment-safe slower version */
205
206	/* Pre-load the temp registers */
207	uint32_t t = 0, d = 0;
208	switch(align)
209	{
210	case 1: t \|= data[2] << 16;
211	case 2: t \|= data[1] << 8;
212	case 3: t \|= data[0];
213	}
214	t <<= (8 * align);
215
216	data += 4-align;
217	len -= 4-align;
218
219	/* From this point, "data" can be read by chunks of 4 bytes */
220
221	int sl = 8 * (4-align);
222	int sr = 8 * align;
223
224	/* Mix */
225	while(len >= 4)
226	{
227	uint32_t k;
228
229	d = (unsigned int )data;
230	k = (t >> sr) \| (d << sl);
231
232	_HASH_MIX(hash, k, m);
233
234	t = d;
235
236	data += 4;
237	len -= 4;
238	}
239
240	/* Handle leftover data in temp registers */
241	d = 0;
242	if(len >= align)
243	{
244	uint32_t k;
245
246	switch(align)
247	{
248	case 3: d \|= data[2] << 16;
249	case 2: d \|= data[1] << 8;
250	case 1: d \|= data[0];
251	}
252
253	k = (t >> sr) \| (d << sl);
254	_HASH_MIX(hash, k, m);
255
256	data += align;
257	len -= align;
258
259	/* Handle tail bytes */
260
261	switch(len)
262	{
263	case 3: hash ^= data[2] << 16;
264	case 2: hash ^= data[1] << 8;
265	case 1: hash ^= data[0];
266	hash *= m;
267	};
268	}
269	else
270	{
271	switch(len)
272	{
273	case 3: d \|= data[2] << 16;
274	case 2: d \|= data[1] << 8;
275	case 1: d \|= data[0];
276	case 0: hash ^= (t >> sr) \| (d << sl);
277	hash *= m;
278	}
279	}
280
281
282	}
283
284	/* Do a few final mixes of the hash to ensure the last few
285	bytes are well-incorporated. */
286	hash ^= hash >> 13;
287	hash *= m;
288	hash ^= hash >> 15;
289
290	return hash;
291	}

Note: See TracBrowser for help on using the repository browser.

Navigation

source: freeDiameter/libfreeDiameter/lists.c @ 25:67ca08d5bc48

Download in other formats: