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