Mercurial > hg > freeDiameter
annotate libfdproto/lists.c @ 662:2e94ef0515d7 1.1.0-rc1
Updated copyright information
| author | Sebastien Decugis <sdecugis@nict.go.jp> |
|---|---|
| date | Fri, 14 Jan 2011 16:27:21 +0900 |
| parents | f198d16fa7f4 |
| children | 4ffbc9f1e922 |
| rev | line source |
|---|---|
| 0 | 1 /********************************************************************************************************* |
| 2 * Software License Agreement (BSD License) * | |
| 3 * Author: Sebastien Decugis <sdecugis@nict.go.jp> * | |
| 4 * * | |
|
662
2e94ef0515d7
Updated copyright information
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
658
diff
changeset
|
5 * Copyright (c) 2011, WIDE Project and NICT * |
| 0 | 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 | |
|
658
f198d16fa7f4
Initial commit for 1.1.0:
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
83
diff
changeset
|
36 #include "fdproto-internal.h" |
| 0 | 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 ) { \ | |
|
14
14cf6daf716d
Some progress on peers module
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
1
diff
changeset
|
49 ASSERT( ((struct fd_list *)(li))->next == (li) ); \ |
|
14cf6daf716d
Some progress on peers module
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
1
diff
changeset
|
50 ASSERT( ((struct fd_list *)(li))->prev == (li) ); \ |
|
14cf6daf716d
Some progress on peers module
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
1
diff
changeset
|
51 ASSERT( ((struct fd_list *)(li))->head == (li) ); \ |
| 0 | 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 | |
|
25
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
74 /* Move all elements of list senti at the end of list ref */ |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
75 void fd_list_move_end(struct fd_list * ref, struct fd_list * senti) |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
76 { |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
77 ASSERT(ref->head == ref); |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
78 ASSERT(senti->head == senti); |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
79 |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
80 if (senti->next == senti) |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
81 return; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
82 |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
83 senti->next->prev = ref->prev; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
84 ref->prev->next = senti->next; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
85 senti->prev->next = ref; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
86 ref->prev = senti->prev; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
87 senti->prev = senti; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
88 senti->next = senti; |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
89 } |
|
67ca08d5bc48
Completed connection context files
Sebastien Decugis <sdecugis@nict.go.jp>
parents:
14
diff
changeset
|
90 |
| 0 | 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 } |