core, lib, modules: restructured source code tree
[sip-router] / src / core / hashes.h
1 /*
2  * Copyright (C) 2006 iptelorg GmbH 
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 /*!
17 * \file
18 * \brief Kamailio core :: hash support
19 * \author Andrei
20 * \ingroup core
21 * Module: \ref core
22 */
23
24
25 #ifndef _hashes_h
26 #define _hashes_h
27
28 #include "str.h"
29
30
31
32 /** internal use: hash update
33  * params: char* s   - string start,
34  *         char* end - end
35  *         char* p,  and unsigned v temporary vars (used)
36  *         unsigned h - result
37  * h should be initialized (e.g. set it to 0), the result in h */
38 #define hash_update_str(s, end, p, v, h) \
39         do{ \
40                 for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
41                         (v)=(*(p)<<24)+((p)[1]<<16)+((p)[2]<<8)+(p)[3]; \
42                         (h)+=(v)^((v)>>3); \
43                 } \
44                 switch((end)-(p)){\
45                         case 3: \
46                                 (v)=(*(p)<<16)+((p)[1]<<8)+(p)[2]; break; \
47                         case 2: \
48                                 (v)=(*(p)<<8)+p[1]; break; \
49                         case 1: \
50                                 (v)=*p; break; \
51                         default: \
52                                 (v)=0; break; \
53                 } \
54                 (h)+=(v)^((v)>>3); \
55         }while(0)
56
57 /** like hash_update_str, but case insensitive 
58  * params: char* s   - string start,
59  *         char* end - end
60  *         char* p,  and unsigned v temporary vars (used)
61  *         unsigned h - result
62  * h should be initialized (e.g. set it to 0), the result in h */
63 #define hash_update_case_str(s, end, p, v, h) \
64         do{ \
65                 for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
66                         (v)=((*(p)<<24)+((p)[1]<<16)+((p)[2]<<8)+(p)[3])|0x20202020; \
67                         (h)+=(v)^((v)>>3); \
68                 } \
69                 (v)=0; \
70                 for (;(p)<(end); (p)++){ (v)<<=8; (v)+=*(p)|0x20;} \
71                 (h)+=(v)^((v)>>3); \
72         }while(0)
73
74
75 /** internal use: call it to adjust the h from hash_update_str */
76 #define hash_finish(h) (((h)+((h)>>11))+(((h)>>13)+((h)>>23)))
77
78
79
80 /** "raw" 2 strings hash
81  * returns an unsigned int (which you can use modulo table_size as hash value)
82  */
83 inline static unsigned int get_hash2_raw(const str* key1, const str* key2)
84 {
85         char* p;
86         register unsigned v;
87         register unsigned h;
88         
89         h=0;
90         
91         hash_update_str(key1->s, key1->s+key1->len, p, v, h);
92         hash_update_str(key2->s, key2->s+key2->len, p, v, h);
93         return hash_finish(h);
94 }
95
96
97
98 /** "raw" 1 string hash
99  * returns an unsigned int (which you can use modulo table_size as hash value)
100  */
101 inline static unsigned int get_hash1_raw(const char* s, int len)
102 {
103         const char* p;
104         register unsigned v;
105         register unsigned h;
106         
107         h=0;
108         
109         hash_update_str(s, s+len, p, v, h);
110         return hash_finish(h);
111 }
112
113
114
115 /** a little slower than hash_* , but better distribution for 
116  * numbers and about the same for strings */
117 #define hash_update_str2(s, end, p, v, h) \
118         do{ \
119                 for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
120                         (v)=(*(p)*16777213)+((p)[1]*65537)+((p)[2]*257)+(p)[3]; \
121                         (h)=16777259*(h)+((v)^((v)<<17)); \
122                 } \
123                 (v)=0; \
124                 for (;(p)<(end); (p)++){ (v)*=251; (v)+=*(p);} \
125                 (h)=16777259*(h)+((v)^((v)<<17)); \
126         }while(0)
127
128 /**  like hash_update_str2 but case insensitive */
129 #define hash_update_case_str2(s, end, p, v, h) \
130         do{ \
131                 for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
132                         (v)=((*(p)|0x20)*16777213)+(((p)[1]|0x20)*65537)+\
133                                 (((p)[2]|0x20)*257)+((p)[3]|0x20); \
134                         (h)=16777259*(h)+((v)^((v)<<17)); \
135                 } \
136                 (v)=0; \
137                 for (;(p)<(end); (p)++){ (v)*=251; (v)+=*(p)|0x20;} \
138                 (h)=16777259*(h)+((v)^((v)<<17)); \
139         }while(0)
140
141 /** internal use: call it to adjust the h from hash_update_str */
142 #define hash_finish2(h) (((h)+((h)>>7))+(((h)>>13)+((h)>>23)))
143
144
145
146 /** a little slower than get_hash1_raw() , but better distribution for 
147  * numbers and about the same for strings */
148 inline static unsigned int get_hash1_raw2(const char* s, int len)
149 {
150         const char* p;
151         register unsigned v;
152         register unsigned h;
153         
154         h=0;
155         
156         hash_update_str2(s, s+len, p, v, h);
157         return hash_finish2(h);
158 }
159
160
161
162 /* "raw" 2 strings hash optimized for numeric strings (see above)
163  * returns an unsigned int (which you can use modulo table_size as hash value)
164  */
165 inline static unsigned int get_hash2_raw2(const str* key1, const str* key2)
166 {
167         char* p;
168         register unsigned v;
169         register unsigned h;
170         
171         h=0;
172         
173         hash_update_str2(key1->s, key1->s+key1->len, p, v, h);
174         hash_update_str2(key2->s, key2->s+key2->len, p, v, h);
175         return hash_finish2(h);
176 }
177
178
179
180 /* "raw" 2 strings case insensitive hash (like get_hash2_raw but case 
181  * insensitive)
182  * returns an unsigned int (which you can use modulo table_size as hash value)
183  */
184 inline static unsigned int get_hash2_case_raw(const str* key1, const str* key2)
185 {
186         char* p;
187         register unsigned v;
188         register unsigned h;
189         
190         h=0;
191         
192         hash_update_case_str(key1->s, key1->s+key1->len, p, v, h);
193         hash_update_case_str(key2->s, key2->s+key2->len, p, v, h);
194         return hash_finish(h);
195 }
196
197
198
199 /* "raw" 1 string case insensitive hash
200  * returns an unsigned int (which you can use modulo table_size as hash value)
201  */
202 inline static unsigned int get_hash1_case_raw(const char* s, int len)
203 {
204         const char* p;
205         register unsigned v;
206         register unsigned h;
207         
208         h=0;
209         
210         hash_update_case_str(s, s+len, p, v, h);
211         return hash_finish(h);
212 }
213
214
215 /* same as get_hash1_raw2, but case insensitive and slower
216  * returns an unsigned int (which you can use modulo table_size as hash value)
217  */
218 inline static unsigned int get_hash1_case_raw2(const char* s, int len)
219 {
220         const char* p;
221         register unsigned v;
222         register unsigned h;
223         
224         h=0;
225         
226         hash_update_case_str2(s, s+len, p, v, h);
227         return hash_finish2(h);
228 }
229
230
231
232 /* "raw" 2 strings hash optimized for numeric strings (see above)
233  * same as get_hash2_raw2 but case insensitive and slower
234  * returns an unsigned int (which you can use modulo table_size as hash value)
235  */
236 inline static unsigned int get_hash2_case_raw2(const str* key1,
237                                                                                            const str* key2)
238 {
239         char* p;
240         register unsigned v;
241         register unsigned h;
242         
243         h=0;
244         
245         hash_update_case_str2(key1->s, key1->s+key1->len, p, v, h);
246         hash_update_case_str2(key2->s, key2->s+key2->len, p, v, h);
247         return hash_finish2(h);
248 }
249
250
251 /*
252  * generic hashing - from the intial origins of ser
253  */
254 #define ch_h_inc h+=v^(v>>3)
255 #define ch_icase(_c) (((_c)>='A'&&(_c)<='Z')?((_c)|0x20):(_c))
256
257 /*
258  * case sensitive hashing
259  * - s1 - str to hash
260  * - s2 - optional - continue hashing over s2
261  * - size - optional - size of hash table (must be power of 1); if set (!=0),
262  *   instead of hash id, returned value is slot index
263  * return computed hash id or hash table slot index
264  */
265 static inline unsigned int core_hash(const str *s1, const str *s2,
266                 const unsigned int size)
267 {
268         char *p, *end;
269         register unsigned v;
270         register unsigned h;
271
272         h=0;
273
274         end=s1->s+s1->len;
275         for ( p=s1->s ; p<=(end-4) ; p+=4 ){
276                 v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
277                 ch_h_inc;
278         }
279         v=0;
280         for (; p<end ; p++){ v<<=8; v+=*p;}
281         ch_h_inc;
282
283         if (s2) {
284                 end=s2->s+s2->len;
285                 for (p=s2->s; p<=(end-4); p+=4){
286                         v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
287                         ch_h_inc;
288                 }
289                 v=0;
290                 for (; p<end ; p++){ v<<=8; v+=*p;}
291                 ch_h_inc;
292         }
293         h=((h)+(h>>11))+((h>>13)+(h>>23));
294         return size?((h)&(size-1)):h;
295 }
296
297
298 /*
299  * case insensitive hashing
300  * - s1 - str to hash
301  * - s2 - optional - continue hashing over s2
302  * - size - optional - size of hash table (must be power of 1); if set (!=0),
303  *   instead of hash id, returned value is slot index
304  * return computed hash id or hash table slot index
305  */
306 static inline unsigned int core_case_hash( str *s1, str *s2,
307                 unsigned int size)
308 {
309         char *p, *end;
310         register unsigned v;
311         register unsigned h;
312
313         h=0;
314
315         end=s1->s+s1->len;
316         for ( p=s1->s ; p<=(end-4) ; p+=4 ){
317                 v=(ch_icase(*p)<<24)+(ch_icase(p[1])<<16)+(ch_icase(p[2])<<8)
318                         + ch_icase(p[3]);
319                 ch_h_inc;
320         }
321         v=0;
322         for (; p<end ; p++){ v<<=8; v+=ch_icase(*p);}
323         ch_h_inc;
324
325         if (s2) {
326                 end=s2->s+s2->len;
327                 for (p=s2->s; p<=(end-4); p+=4){
328                         v=(ch_icase(*p)<<24)+(ch_icase(p[1])<<16)+(ch_icase(p[2])<<8)
329                                 + ch_icase(p[3]);
330                         ch_h_inc;
331                 }
332                 v=0;
333                 for (; p<end ; p++){ v<<=8; v+=ch_icase(*p);}
334                 ch_h_inc;
335         }
336         h=((h)+(h>>11))+((h>>13)+(h>>23));
337         return size?((h)&(size-1)):h;
338 }
339
340
341 #endif