Navigation


source: freeDiameter/libfreeDiameter/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 */
39void 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 */
55static 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 */
65void 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 */
75void 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 */
93static 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 */
103void 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 */
113int 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 */
151void 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; }
172uint32_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.