Browse code

core, lib, modules: restructured source code tree

- new folder src/ to hold the source code for main project applications
- main.c is in src/
- all core files are subfolder are in src/core/
- modules are in src/modules/
- libs are in src/lib/
- application Makefiles are in src/
- application binary is built in src/ (src/kamailio)

Daniel-Constantin Mierla authored on 07/12/2016 11:03:51
Showing 1 changed files
1 1
deleted file mode 100644
... ...
@@ -1,341 +0,0 @@
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
Browse code

core : Update include files - delete IDs, update doxygen, delete history

Olle E. Johansson authored on 03/01/2015 10:55:48
Showing 1 changed files
... ...
@@ -1,6 +1,4 @@
1 1
 /*
2
- * $Id$
3
- *
4 2
  * Copyright (C) 2006 iptelorg GmbH 
5 3
  *
6 4
  * Permission to use, copy, modify, and distribute this software for any
... ...
@@ -15,14 +13,13 @@
15 13
  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 14
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 15
  */
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
- */
16
+/*!
17
+* \file
18
+* \brief Kamailio core :: hash support
19
+* \author Andrei
20
+* \ingroup core
21
+* Module: \ref core
22
+*/
26 23
 
27 24
 
28 25
 #ifndef _hashes_h
... ...
@@ -32,7 +29,7 @@
32 29
 
33 30
 
34 31
 
35
-/* internal use: hash update
32
+/** internal use: hash update
36 33
  * params: char* s   - string start,
37 34
  *         char* end - end
38 35
  *         char* p,  and unsigned v temporary vars (used)
... ...
@@ -57,7 +54,7 @@
57 54
 		(h)+=(v)^((v)>>3); \
58 55
 	}while(0)
59 56
 
60
-/* like hash_update_str, but case insensitive 
57
+/** like hash_update_str, but case insensitive 
61 58
  * params: char* s   - string start,
62 59
  *         char* end - end
63 60
  *         char* p,  and unsigned v temporary vars (used)
... ...
@@ -75,12 +72,12 @@
75 72
 	}while(0)
76 73
 
77 74
 
78
-/* internal use: call it to adjust the h from hash_update_str */
75
+/** internal use: call it to adjust the h from hash_update_str */
79 76
 #define hash_finish(h) (((h)+((h)>>11))+(((h)>>13)+((h)>>23)))
80 77
 
81 78
 
82 79
 
83
-/* "raw" 2 strings hash
80
+/** "raw" 2 strings hash
84 81
  * returns an unsigned int (which you can use modulo table_size as hash value)
85 82
  */
86 83
 inline static unsigned int get_hash2_raw(const str* key1, const str* key2)
... ...
@@ -98,7 +95,7 @@ inline static unsigned int get_hash2_raw(const str* key1, const str* key2)
98 95
 
99 96
 
100 97
 
101
-/* "raw" 1 string hash
98
+/** "raw" 1 string hash
102 99
  * returns an unsigned int (which you can use modulo table_size as hash value)
103 100
  */
104 101
 inline static unsigned int get_hash1_raw(const char* s, int len)
... ...
@@ -115,7 +112,7 @@ inline static unsigned int get_hash1_raw(const char* s, int len)
115 112
 
116 113
 
117 114
 
118
-/* a little slower than hash_* , but better distribution for 
115
+/** a little slower than hash_* , but better distribution for 
119 116
  * numbers and about the same for strings */
120 117
 #define hash_update_str2(s, end, p, v, h) \
121 118
 	do{ \
... ...
@@ -128,7 +125,7 @@ inline static unsigned int get_hash1_raw(const char* s, int len)
128 125
 		(h)=16777259*(h)+((v)^((v)<<17)); \
129 126
 	}while(0)
130 127
 
131
-/*  like hash_update_str2 but case insensitive */
128
+/**  like hash_update_str2 but case insensitive */
132 129
 #define hash_update_case_str2(s, end, p, v, h) \
133 130
 	do{ \
134 131
 		for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
... ...
@@ -141,12 +138,12 @@ inline static unsigned int get_hash1_raw(const char* s, int len)
141 138
 		(h)=16777259*(h)+((v)^((v)<<17)); \
142 139
 	}while(0)
143 140
 
144
-/* internal use: call it to adjust the h from hash_update_str */
141
+/** internal use: call it to adjust the h from hash_update_str */
145 142
 #define hash_finish2(h) (((h)+((h)>>7))+(((h)>>13)+((h)>>23)))
146 143
 
147 144
 
148 145
 
149
-/* a little slower than get_hash1_raw() , but better distribution for 
146
+/** a little slower than get_hash1_raw() , but better distribution for 
150 147
  * numbers and about the same for strings */
151 148
 inline static unsigned int get_hash1_raw2(const char* s, int len)
152 149
 {
Browse code

lib/kcore: cleaned up unused code

- local route and errinfo related code were not used for long time
- also moved some bits of code to more appropriate location

Daniel-Constantin Mierla authored on 10/02/2012 12:42:59
Showing 1 changed files
... ...
@@ -251,5 +251,94 @@ inline static unsigned int get_hash2_case_raw2(const str* key1,
251 251
 }
252 252
 
253 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
+
254 343
 
255 344
 #endif
Browse code

core: use const char*/str* for hash functions

Andrei Pelinescu-Onciul authored on 26/08/2010 19:40:45
Showing 1 changed files
... ...
@@ -83,7 +83,7 @@
83 83
 /* "raw" 2 strings hash
84 84
  * returns an unsigned int (which you can use modulo table_size as hash value)
85 85
  */
86
-inline static unsigned int get_hash2_raw(str* key1, str* key2)
86
+inline static unsigned int get_hash2_raw(const str* key1, const str* key2)
87 87
 {
88 88
 	char* p;
89 89
 	register unsigned v;
... ...
@@ -101,9 +101,9 @@ inline static unsigned int get_hash2_raw(str* key1, str* key2)
101 101
 /* "raw" 1 string hash
102 102
  * returns an unsigned int (which you can use modulo table_size as hash value)
103 103
  */
104
-inline static unsigned int get_hash1_raw(char* s, int len)
104
+inline static unsigned int get_hash1_raw(const char* s, int len)
105 105
 {
106
-	char* p;
106
+	const char* p;
107 107
 	register unsigned v;
108 108
 	register unsigned h;
109 109
 	
... ...
@@ -148,9 +148,9 @@ inline static unsigned int get_hash1_raw(char* s, int len)
148 148
 
149 149
 /* a little slower than get_hash1_raw() , but better distribution for 
150 150
  * numbers and about the same for strings */
151
-inline static unsigned int get_hash1_raw2(char* s, int len)
151
+inline static unsigned int get_hash1_raw2(const char* s, int len)
152 152
 {
153
-	char* p;
153
+	const char* p;
154 154
 	register unsigned v;
155 155
 	register unsigned h;
156 156
 	
... ...
@@ -165,7 +165,7 @@ inline static unsigned int get_hash1_raw2(char* s, int len)
165 165
 /* "raw" 2 strings hash optimized for numeric strings (see above)
166 166
  * returns an unsigned int (which you can use modulo table_size as hash value)
167 167
  */
168
-inline static unsigned int get_hash2_raw2(str* key1, str* key2)
168
+inline static unsigned int get_hash2_raw2(const str* key1, const str* key2)
169 169
 {
170 170
 	char* p;
171 171
 	register unsigned v;
... ...
@@ -184,7 +184,7 @@ inline static unsigned int get_hash2_raw2(str* key1, str* key2)
184 184
  * insensitive)
185 185
  * returns an unsigned int (which you can use modulo table_size as hash value)
186 186
  */
187
-inline static unsigned int get_hash2_case_raw(str* key1, str* key2)
187
+inline static unsigned int get_hash2_case_raw(const str* key1, const str* key2)
188 188
 {
189 189
 	char* p;
190 190
 	register unsigned v;
... ...
@@ -202,9 +202,9 @@ inline static unsigned int get_hash2_case_raw(str* key1, str* key2)
202 202
 /* "raw" 1 string case insensitive hash
203 203
  * returns an unsigned int (which you can use modulo table_size as hash value)
204 204
  */
205
-inline static unsigned int get_hash1_case_raw(char* s, int len)
205
+inline static unsigned int get_hash1_case_raw(const char* s, int len)
206 206
 {
207
-	char* p;
207
+	const char* p;
208 208
 	register unsigned v;
209 209
 	register unsigned h;
210 210
 	
... ...
@@ -218,9 +218,9 @@ inline static unsigned int get_hash1_case_raw(char* s, int len)
218 218
 /* same as get_hash1_raw2, but case insensitive and slower
219 219
  * returns an unsigned int (which you can use modulo table_size as hash value)
220 220
  */
221
-inline static unsigned int get_hash1_case_raw2(char* s, int len)
221
+inline static unsigned int get_hash1_case_raw2(const char* s, int len)
222 222
 {
223
-	char* p;
223
+	const char* p;
224 224
 	register unsigned v;
225 225
 	register unsigned h;
226 226
 	
... ...
@@ -236,7 +236,8 @@ inline static unsigned int get_hash1_case_raw2(char* s, int len)
236 236
  * same as get_hash2_raw2 but case insensitive and slower
237 237
  * returns an unsigned int (which you can use modulo table_size as hash value)
238 238
  */
239
-inline static unsigned int get_hash2_case_raw2(str* key1, str* key2)
239
+inline static unsigned int get_hash2_case_raw2(const str* key1,
240
+											   const str* key2)
240 241
 {
241 242
 	char* p;
242 243
 	register unsigned v;
Browse code

- attempt to unroll one of the hash loops

Andrei Pelinescu-Onciul authored on 06/06/2007 21:56:27
Showing 1 changed files
... ...
@@ -44,8 +44,16 @@
44 44
 			(v)=(*(p)<<24)+((p)[1]<<16)+((p)[2]<<8)+(p)[3]; \
45 45
 			(h)+=(v)^((v)>>3); \
46 46
 		} \
47
-		(v)=0; \
48
-		for (;(p)<(end); (p)++){ (v)<<=8; (v)+=*(p);} \
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
+		} \
49 57
 		(h)+=(v)^((v)>>3); \
50 58
 	}while(0)
51 59
 
Browse code

- added case-insensitive hash functions - replaced dns case insensitve hash calc. with the version from hashes.h (and fixed a "paste error" in dns hash calculation in the process)

Andrei Pelinescu-Onciul authored on 22/02/2007 20:58:32
Showing 1 changed files
... ...
@@ -21,6 +21,7 @@
21 21
  *  2006-02-02  created by andrei
22 22
  *  2006-11-24  added numeric string optimized hash function (andrei)
23 23
  *  2006-12-13  split into hashes.h (more generic) and str_hash.h (andrei)
24
+ *  2007-02-22  added case insensitive versions (andrei)
24 25
  */
25 26
 
26 27
 
... ...
@@ -48,6 +49,23 @@
48 49
 		(h)+=(v)^((v)>>3); \
49 50
 	}while(0)
50 51
 
52
+/* like hash_update_str, but case insensitive 
53
+ * params: char* s   - string start,
54
+ *         char* end - end
55
+ *         char* p,  and unsigned v temporary vars (used)
56
+ *         unsigned h - result
57
+ * h should be initialized (e.g. set it to 0), the result in h */
58
+#define hash_update_case_str(s, end, p, v, h) \
59
+	do{ \
60
+		for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
61
+			(v)=((*(p)<<24)+((p)[1]<<16)+((p)[2]<<8)+(p)[3])|0x20202020; \
62
+			(h)+=(v)^((v)>>3); \
63
+		} \
64
+		(v)=0; \
65
+		for (;(p)<(end); (p)++){ (v)<<=8; (v)+=*(p)|0x20;} \
66
+		(h)+=(v)^((v)>>3); \
67
+	}while(0)
68
+
51 69
 
52 70
 /* internal use: call it to adjust the h from hash_update_str */
53 71
 #define hash_finish(h) (((h)+((h)>>11))+(((h)>>13)+((h)>>23)))
... ...
@@ -102,6 +120,19 @@ inline static unsigned int get_hash1_raw(char* s, int len)
102 120
 		(h)=16777259*(h)+((v)^((v)<<17)); \
103 121
 	}while(0)
104 122
 
123
+/*  like hash_update_str2 but case insensitive */
124
+#define hash_update_case_str2(s, end, p, v, h) \
125
+	do{ \
126
+		for ((p)=(s); (p)<=((end)-4); (p)+=4){ \
127
+			(v)=((*(p)|0x20)*16777213)+(((p)[1]|0x20)*65537)+\
128
+				(((p)[2]|0x20)*257)+((p)[3]|0x20); \
129
+			(h)=16777259*(h)+((v)^((v)<<17)); \
130
+		} \
131
+		(v)=0; \
132
+		for (;(p)<(end); (p)++){ (v)*=251; (v)+=*(p)|0x20;} \
133
+		(h)=16777259*(h)+((v)^((v)<<17)); \
134
+	}while(0)
135
+
105 136
 /* internal use: call it to adjust the h from hash_update_str */
106 137
 #define hash_finish2(h) (((h)+((h)>>7))+(((h)>>13)+((h)>>23)))
107 138
 
... ...
@@ -136,9 +167,80 @@ inline static unsigned int get_hash2_raw2(str* key1, str* key2)
136 167
 	
137 168
 	hash_update_str2(key1->s, key1->s+key1->len, p, v, h);
138 169
 	hash_update_str2(key2->s, key2->s+key2->len, p, v, h);
170
+	return hash_finish2(h);
171
+}
172
+
173
+
174
+
175
+/* "raw" 2 strings case insensitive hash (like get_hash2_raw but case 
176
+ * insensitive)
177
+ * returns an unsigned int (which you can use modulo table_size as hash value)
178
+ */
179
+inline static unsigned int get_hash2_case_raw(str* key1, str* key2)
180
+{
181
+	char* p;
182
+	register unsigned v;
183
+	register unsigned h;
184
+	
185
+	h=0;
186
+	
187
+	hash_update_case_str(key1->s, key1->s+key1->len, p, v, h);
188
+	hash_update_case_str(key2->s, key2->s+key2->len, p, v, h);
139 189
 	return hash_finish(h);
140 190
 }
141 191
 
142 192
 
143 193
 
194
+/* "raw" 1 string case insensitive hash
195
+ * returns an unsigned int (which you can use modulo table_size as hash value)
196
+ */
197
+inline static unsigned int get_hash1_case_raw(char* s, int len)
198
+{
199
+	char* p;
200
+	register unsigned v;
201
+	register unsigned h;
202
+	
203
+	h=0;
204
+	
205
+	hash_update_case_str(s, s+len, p, v, h);
206
+	return hash_finish(h);
207
+}
208
+
209
+
210
+/* same as get_hash1_raw2, but case insensitive and slower
211
+ * returns an unsigned int (which you can use modulo table_size as hash value)
212
+ */
213
+inline static unsigned int get_hash1_case_raw2(char* s, int len)
214
+{
215
+	char* p;
216
+	register unsigned v;
217
+	register unsigned h;
218
+	
219
+	h=0;
220
+	
221
+	hash_update_case_str2(s, s+len, p, v, h);
222
+	return hash_finish2(h);
223
+}
224
+
225
+
226
+
227
+/* "raw" 2 strings hash optimized for numeric strings (see above)
228
+ * same as get_hash2_raw2 but case insensitive and slower
229
+ * returns an unsigned int (which you can use modulo table_size as hash value)
230
+ */
231
+inline static unsigned int get_hash2_case_raw2(str* key1, str* key2)
232
+{
233
+	char* p;
234
+	register unsigned v;
235
+	register unsigned h;
236
+	
237
+	h=0;
238
+	
239
+	hash_update_case_str2(key1->s, key1->s+key1->len, p, v, h);
240
+	hash_update_case_str2(key2->s, key2->s+key2->len, p, v, h);
241
+	return hash_finish2(h);
242
+}
243
+
244
+
245
+
144 246
 #endif
Browse code

- hash cleanup/cosmetics: - use the "raw" hash functions from hashes.h as base for the other hashes (e.g. tm hash). This doesn't change the hash functions, just removes some extra copies. - split old hashes.h into hashes.h (more generic stuff) and str_hash.h - new_hash() is safer now (nobody uses it, but just in case...)

Andrei Pelinescu-Onciul authored on 13/12/2006 22:50:46
Showing 1 changed files
... ...
@@ -20,6 +20,7 @@
20 20
  * --------
21 21
  *  2006-02-02  created by andrei
22 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)
23 24
  */
24 25
 
25 26
 
... ...
@@ -27,8 +28,6 @@
27 28
 #define _hashes_h
28 29
 
29 30
 #include "str.h"
30
-#include "mem/mem.h"
31
-#include "clist.h"
32 31
 
33 32
 
34 33
 
... ...
@@ -142,84 +141,4 @@ inline static unsigned int get_hash2_raw2(str* key1, str* key2)
142 141
 
143 142
 
144 143
 
145
-/* generic, simple str keyed hash */
146
-
147
-struct str_hash_entry{
148
-	struct str_hash_entry* next;
149
-	struct str_hash_entry* prev;
150
-	str key;
151
-	unsigned int flags;
152
-	union{
153
-		void* p;
154
-		char* s;
155
-		int   n;
156
-		char  data[sizeof(void*)];
157
-	}u;
158
-};
159
-
160
-
161
-struct str_hash_head{
162
-	struct str_hash_entry* next;
163
-	struct str_hash_entry* prev;
164
-};
165
-
166
-
167
-struct str_hash_table{
168
-	struct str_hash_head* table;
169
-	int size;
170
-};
171
-
172
-
173
-
174
-/* returns 0 on success, <0 on failure */
175
-inline static int str_hash_alloc(struct str_hash_table* ht, int size)
176
-{
177
-	ht->table=pkg_malloc(sizeof(struct str_hash_head)*size);
178
-	if (ht->table==0)
179
-		return -1;
180
-	ht->size=size;
181
-	return 0;
182
-}
183
-
184
-
185
-
186
-inline static void str_hash_init(struct str_hash_table* ht)
187
-{
188
-	int r;
189
-	
190
-	for (r=0; r<ht->size; r++) clist_init(&(ht->table[r]), next, prev);
191
-}
192
-
193
-
194
-
195
-inline static void str_hash_add(struct str_hash_table* ht, 
196
-								struct str_hash_entry* e)
197
-{
198
-	int h;
199
-	
200
-	h=get_hash1_raw(e->key.s, e->key.len) % ht->size;
201
-	clist_insert(&ht->table[h], e, next, prev);
202
-}
203
-
204
-
205
-
206
-inline static struct str_hash_entry* str_hash_get(struct str_hash_table* ht,
207
-									char* key, int len)
208
-{
209
-	int h;
210
-	struct str_hash_entry* e;
211
-	
212
-	h=get_hash1_raw(key, len) % ht->size;
213
-	clist_foreach(&ht->table[h], e, next){
214
-		if ((e->key.len==len) && (memcmp(e->key.s, key, len)==0))
215
-			return e;
216
-	}
217
-	return 0;
218
-}
219
-
220
-
221
-#define str_hash_del(e) clist_rm(e, next, prev)
222
-
223
-
224
-
225 144
 #endif
Browse code

- usrloc hash fix (performace): switched to a numeric string optimized hash function (which also has very good distribution for strings) - added the new hash to core's hashes.h & changes hashes.h license to openbsd style (so that anybody can use the hash functions without being forced to gpl the code)

Andrei Pelinescu-Onciul authored on 24/11/2006 17:20:08
Showing 1 changed files
... ...
@@ -3,31 +3,23 @@
3 3
  *
4 4
  * Copyright (C) 2006 iptelorg GmbH 
5 5
  *
6
- * This file is part of ser, a free SIP server.
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.
7 9
  *
8
- * ser is free software; you can redistribute it and/or modify
9
- * it under the terms of the GNU General Public License as published by
10
- * the Free Software Foundation; either version 2 of the License, or
11
- * (at your option) any later version
12
- *
13
- * For a license to use the ser software under conditions
14
- * other than those described here, or to purchase support for this
15
- * software, please contact iptel.org by e-mail at the following addresses:
16
- *    info@iptel.org
17
- *
18
- * ser is distributed in the hope that it will be useful,
19
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
20
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21
- * GNU General Public License for more details.
22
- *
23
- * You should have received a copy of the GNU General Public License 
24
- * along with this program; if not, write to the Free Software 
25
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
10
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES