GitList
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
hash_func.c
History View file @ 273ab2955f
1 1 
deleted file mode 100644
... ... 
@@ -1,172 +0,0 @@
1 
-/*
2 
- * Copyright (C) 2001-2003 FhG Fokus
3 
- *
4 
- * This file is part of Kamailio, a free SIP server.
5 
- *
6 
- * Kamailio is free software; you can redistribute it and/or modify
7 
- * it under the terms of the GNU General Public License as published by
8 
- * the Free Software Foundation; either version 2 of the License, or
9 
- * (at your option) any later version
10 
- *
11 
- * Kamailio is distributed in the hope that it will be useful,
12 
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 
- * GNU General Public License for more details.
15 
- *
16 
- * You should have received a copy of the GNU General Public License
17 
- * along with this program; if not, write to the Free Software
18 
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19 
- */
20 
-
21 
-/*!
22 
- * \file
23 
- * \brief Kamailio core :: Hash functions
24 
- * \ingroup core
25 
- * Module: \ref core
26 
- */
27 
-
28 
-
29 
-
30 
-#ifndef _CRC_H_
31 
-#define _CRC_H_
32 
-
33 
-extern unsigned long int crc_32_tab[];
34 
-extern unsigned short int ccitt_tab[];
35 
-extern unsigned short int crc_16_tab[];
36 
-
37 
-#endif
38 
-
39 
-#include <stdio.h>
40 
-#include <string.h>
41 
-#include <stdlib.h>
42 
-#include "hash_func.h"
43 
-#include "dprint.h"
44 
-#include "crc.h"
45 
-#include "ut.h"
46 
-
47 
-
48 
-unsigned int new_hash( str call_id, str cseq_nr )
49 
-{
50 
-	unsigned int hash_code = 0;
51 
-	int i,j, k, third;
52 
-	int ci_len, cs_len;
53 
-	char *ci, *cs;
54 
-
55 
-	/* trim EoLs */
56 
-/*
57 
-	ci_len = call_id.len;
58 
-	while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
59 
-		ci_len--;
60 
-	cs_len = cseq_nr.len;
61 
-	while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
62 
-		cs_len--;
63 
-*/
64 
-	trim_len( ci_len, ci, call_id );
65 
-	trim_len( cs_len, cs, cseq_nr );
66 
-
67 
-	/* run the cycle from the end ... we are interested in the
68 
-	   most-right digits ... and just take the %10 value of it
69 
-	*/
70 
-	third=(ci_len-1)/3;
71 
-	for ( i=ci_len-1, j=2*third, k=third;
72 
-		k>0 ; i--, j--, k-- ) {
73 
-		hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
74 
-			ccitt_tab[(unsigned char)*(ci+k)+63]+
75 
-			ccitt_tab[(unsigned char)*(ci+j)+13];
76 
-	}
77 
-	for( i=0 ; i<cs_len ; i++ )
78 
-		//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
79 
-		hash_code+=ccitt_tab[(unsigned char)*(cs+i)+123];
80 
-
81 
-	/* hash_code conditioning */
82 
-#ifdef _BUG
83 
-	/* not flat ... % 111b has shorter period than
84 
-       & 111b by one and results in different distribution;
85 
-	   ( 7 % 7 == 0, 7 %7 == 1 )
86 
- 	   % is used as a part of the hash function too, not only
87 
-	   for rounding; & is not flat; whoever comes up with
88 
-	   a nicer flat hash function which does not take
89 
-	   costly division is welcome; feel free to verify
90 
-	   distribution using hashtest()
91 
-    */
92 
-	hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
93 
-#endif
94 
-	hash_code=hash_code%(TABLE_ENTRIES-1)+1;
95 
-	return hash_code;
96 
-}
97 
-
98 
-
99 
-
100 
-#if 0
101 
-int new_hash2( str call_id, str cseq_nr )
102 
-{
103 
-#define h_inc h+=v^(v>>3)
104 
-	char* p;
105 
-	register unsigned v;
106 
-	register unsigned h;
107 
-
108 
-	h=0;
109 
-
110 
-
111 
-	for (p=call_id.s; p<=(call_id.s+call_id.len-4); p+=4){
112 
-		v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
113 
-		h_inc;
114 
-	}
115 
-	v=0;
116 
-	for (;p<(call_id.s+call_id.len); p++){ v<<=8; v+=*p;}
117 
-	h_inc;
118 
-
119 
-	for (p=cseq_nr.s; p<=(cseq_nr.s+cseq_nr.len-4); p+=4){
120 
-		v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
121 
-		h_inc;
122 
-	}
123 
-	v=0;
124 
-	for (;p<(cseq_nr.s+cseq_nr.len); p++){ v<<=8; v+=*p;}
125 
-	h_inc;
126 
-
127 
-	h=((h)+(h>>11))+((h>>13)+(h>>23));
128 
-	return (h)&(TABLE_ENTRIES-1);
129 
-}
130 
-#endif
131 
-
132 
-
133 
-
134 
-void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
135 
-{
136 
-	long int i,j,k, l;
137 
-	int  hashv;
138 
-	static char buf1[1024];
139 
-	static char buf2[1024];
140 
-	str call_id;
141 
-	str cseq;
142 
-
143 
-	call_id.s=buf1;
144 
-	cseq.s=buf2;
145 
-
146 
-	for (i=987654328;i<987654328+10;i++)
147 
-		for (j=85296341;j<85296341+10;j++)
148 
-			for (k=987654;k<=987654+10;k++)
149 
-				for (l=101;l<201;l++) {
150 
-					call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
151 
-						(int)k, ip );
152 
-					cseq.len=sprintf( buf2, "%d", (int)l );
153 
-					/* printf("%s\t%s\n", buf1, buf2 ); */
154 
-					hashv=hash( call_id, cseq );
155 
-					hits[ hashv ]++;
156 
-				}
157 
-}
158 
-
159 
-void hashtest(void)
160 
-{
161 
-	int hits[TABLE_ENTRIES+5];
162 
-	int i;
163 
-
164 
-	memset( hits, 0, sizeof hits );
165 
-	hashtest_cycle( hits, "192.168.99.100" );
166 
-	hashtest_cycle( hits, "172.168.99.100" );
167 
-	hashtest_cycle( hits, "142.168.99.100" );
168 
-	for (i=0; i<TABLE_ENTRIES+5; i++)
169 
-		printf("[%d. %d]\n", i, hits[i] );
170 
-	exit(0);
171 
-}
172 
-
Browse code

core Update headers, change "SIP-router" to "Kamailio", update doxygen file headers

Olle E. Johansson authored on 03/01/2015 14:15:58
Showing 1 changed files
hash_func.c
History View file @ 88693a29e2
... ... 
@@ -8,11 +8,6 @@
8 8 
  * the Free Software Foundation; either version 2 of the License, or
9 9 
  * (at your option) any later version
10 10 
  *
11 
- * For a license to use the ser software under conditions
12 
- * other than those described here, or to purchase support for this
13 
- * software, please contact iptel.org by e-mail at the following addresses:
14 
- *    info@iptel.org
15 
- *
16 11 
  * Kamailio is distributed in the hope that it will be useful,
17 12 
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 13 
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
Browse code

Core Removed history, svn $id$ and doxygen udpates on the .c files

Olle E. Johansson authored on 03/01/2015 09:53:17
Showing 1 changed files
hash_func.c
History View file @ 6a0f438258
... ... 
@@ -1,11 +1,9 @@
1 1 
 /*
2 
- * $Id$
3 
- *
4 2 
  * Copyright (C) 2001-2003 FhG Fokus
5 3 
  *
6 
- * This file is part of ser, a free SIP server.
4 
+ * This file is part of Kamailio, a free SIP server.
7 5 
  *
8 
- * ser is free software; you can redistribute it and/or modify
6 
+ * Kamailio is free software; you can redistribute it and/or modify
9 7 
  * it under the terms of the GNU General Public License as published by
10 8 
  * the Free Software Foundation; either version 2 of the License, or
11 9 
  * (at your option) any later version
... ... 
@@ -15,7 +13,7 @@
15 13 
  * software, please contact iptel.org by e-mail at the following addresses:
16 14 
  *    info@iptel.org
17 15 
  *
18 
- * ser is distributed in the hope that it will be useful,
16 
+ * Kamailio is distributed in the hope that it will be useful,
19 17 
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 18 
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
21 19 
  * GNU General Public License for more details.
... ... 
@@ -27,7 +25,7 @@
27 25
28 26 
 /*!
29 27 
  * \file
30 
- * \brief SIP-router core ::
28 
+ * \brief Kamailio core :: Hash functions
31 29 
  * \ingroup core
32 30 
  * Module: \ref core
33 31 
  */
Browse code

all: updated FSF address in GPL text

Anthony Messina authored on 04/07/2014 09:36:37 • Daniel-Constantin Mierla committed on 04/07/2014 09:37:36
Showing 1 changed files
hash_func.c
History View file @ 9e1ff4488a
... ... 
@@ -22,7 +22,7 @@
22 22 
  *
23 23 
  * You should have received a copy of the GNU General Public License
24 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
25 
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
26 26 
  */
27 27
28 28 
 /*!
Browse code

core: Added void to declarations of functions with empty argument list

In C language, a declaration in the form int f(); is equivalent to int f(...);, thus being able to accept an indefinit number of parameters. With the -Wstrict-prototypes GCC options, these declarations are reported as "function declaration isn’t a prototype".
On some cases, this may trick the compiler into generating unoptimized code (like preparing to handle variadic argument list).
In all cases having a declaration int f() and a definition inf f(int) is missleading, even if standard compliant.
This is still Work in Progress. (maybe adding the -Wstrict-prototypes option to default is desireable)

Marius Zbihlei authored on 02/04/2012 14:19:17
Showing 1 changed files
hash_func.c
History View file @ abb01fb410
... ... 
@@ -163,7 +163,7 @@ void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
163 163 
 				}
164 164 
 }
165 165
166 
-void hashtest()
166 
+void hashtest(void)
167 167 
 {
168 168 
 	int hits[TABLE_ENTRIES+5];
169 169 
 	int i;
Browse code

Adding doxygen template to all core .c files

Please fill in after the :: to explain the function of this file.

oej authored on 10/10/2009 13:54:13
Showing 1 changed files
hash_func.c
History View file @ 1d0661db4c
... ... 
@@ -25,6 +25,13 @@
25 25 
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
26 26 
  */
27 27
28 
+/*!
29 
+ * \file
30 
+ * \brief SIP-router core ::
31 
+ * \ingroup core
32 
+ * Module: \ref core
33 
+ */
34 
+
28 35
29 36
30 37 
 #ifndef _CRC_H_
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
hash_func.c
History View file @ e8138515fe
... ... 
@@ -45,9 +45,9 @@ extern unsigned short int crc_16_tab[];
45 45 
 #include "ut.h"
46 46
47 47
48 
-int new_hash( str call_id, str cseq_nr )
48 
+unsigned int new_hash( str call_id, str cseq_nr )
49 49 
 {
50 
-	int hash_code = 0;
50 
+	unsigned int hash_code = 0;
51 51 
 	int i,j, k, third;
52 52 
 	int ci_len, cs_len;
53 53 
 	char *ci, *cs;
... ... 
@@ -71,12 +71,12 @@ int new_hash( str call_id, str cseq_nr )
71 71 
 	for ( i=ci_len-1, j=2*third, k=third;
72 72 
 		k>0 ; i--, j--, k-- ) {
73 73 
 		hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
74 
-			ccitt_tab[*(ci+k)+63]+
75 
-			ccitt_tab[*(ci+j)+13];
74 
+			ccitt_tab[(unsigned char)*(ci+k)+63]+
75 
+			ccitt_tab[(unsigned char)*(ci+j)+13];
76 76 
 	}
77 77 
 	for( i=0 ; i<cs_len ; i++ )
78 78 
 		//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
79 
-		hash_code+=ccitt_tab[*(cs+i)+123];
79 
+		hash_code+=ccitt_tab[(unsigned char)*(cs+i)+123];
80 80
81 81 
 	/* hash_code conditioning */
82 82 
 #ifdef _BUG
... ... 
@@ -92,11 +92,12 @@ int new_hash( str call_id, str cseq_nr )
92 92 
 	hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
93 93 
 #endif
94 94 
 	hash_code=hash_code%(TABLE_ENTRIES-1)+1;
95 
-   	return hash_code;
95 
+	return hash_code;
96 96 
 }
97 97
98 98
99 99
100 
+#if 0
100 101 
 int new_hash2( str call_id, str cseq_nr )
101 102 
 {
102 103 
 #define h_inc h+=v^(v>>3)
... ... 
@@ -126,6 +127,7 @@ int new_hash2( str call_id, str cseq_nr )
126 127 
 	h=((h)+(h>>11))+((h>>13)+(h>>23));
127 128 
 	return (h)&(TABLE_ENTRIES-1);
128 129 
 }
130 
+#endif
129 131
130 132
131 133
Browse code

- Spelling checked - READMEs updated

Jan Janak authored on 24/08/2004 08:45:09
Showing 1 changed files
hash_func.c
History View file @ 53c7e0f19a
... ... 
@@ -1,7 +1,7 @@
1 1 
 /*
2 2 
  * $Id$
3 3 
  *
4 
- * Copyright (C) 2001-2003 Fhg Fokus
4 
+ * Copyright (C) 2001-2003 FhG Fokus
5 5 
  *
6 6 
  * This file is part of ser, a free SIP server.
7 7 
  *
Browse code

- more tcp stuff and a lot of merging w/ latest cvs - content-length is appended automatically to messages that cross from udp to tcp - tcp2udp and udp2tcp now work under heavy stress (e.g.: throttle 200, 10 ser processes on dual cpu) - tcp performance still sucks, some things like disabling Nagle are still not in yet (for better debugging)

Andrei Pelinescu-Onciul authored on 07/02/2003 17:02:15
Showing 1 changed files
hash_func.c
History View file @ ab130758c9
... ... 
@@ -154,25 +154,11 @@ void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
154 154 
 				}
155 155 
 }
156 156
157 
-int init_hash()
158 
-{
159 
-	if (TABLE_ENTRIES != (1<<10)) {
160 
-		LOG(L_WARN, "WARNING: hash function optimized for %d entries\n",
161 
-			1<<10);
162 
-		LOG(L_WARN, "WARNING: use of %d entries may lead "
163 
-			"to unflat distribution\n", TABLE_ENTRIES );
164 
-	} else {
165 
-		DBG("DEBUG: hash function initialized with optimum table size\n");
166 
-	}
167 
-	return 1;
168 
-}
169 
-
170 157 
 void hashtest()
171 158 
 {
172 159 
 	int hits[TABLE_ENTRIES+5];
173 160 
 	int i;
174 161
175 
-	init_hash();
176 162 
 	memset( hits, 0, sizeof hits );
177 163 
 	hashtest_cycle( hits, "192.168.99.100" );
178 164 
 	hashtest_cycle( hits, "172.168.99.100" );
Browse code

- added new_hash2 (faster & better distrib. hash) - added rev . dns startup interface ip lookups (aliases) - lots of cleanups

Andrei Pelinescu-Onciul authored on 22/10/2002 20:37:29
Showing 1 changed files
hash_func.c
History View file @ d615a5cd9b
... ... 
@@ -44,63 +44,6 @@ extern unsigned short int crc_16_tab[];
44 44 
 #include "crc.h"
45 45 
 #include "ut.h"
46 46
47 
-#ifdef _OBSOLETED
48 
-int old_hash( str  call_id, str cseq_nr )
49 
-{
50 
-   int  hash_code = 0;
51 
-   int  i;
52 
-
53 
-#if 0 /*def i386*/
54 
-   int ci_len, cs_len;
55 
-   char *ci, *cs;
56 
-
57 
-	trim_len( ci_len, ci, call_id );
58 
-	trim_len( cs_len, cs, cseq_nr );
59 
-
60 
-		int dummy1;
61 
-		if (call_id.len>=4){
62 
-			asm(
63 
-				"1: \n\r"
64 
-				"addl (%1), %0 \n\r"
65 
-				"add $4, %1 \n\r"
66 
-				"cmp %2, %1 \n\r"
67 
-				"jl 1b  \n\r"
68 
-				: "=r"(hash_code), "=r"(dummy1)
69 
-				:  "0" (hash_code), "1"(ci),
70 
-				"r"( (ci_len & (~3)) +ci)
71 
-			);
72 
-		}
73 
-#else
74 
-    if ( call_id.len>0 )
75 
-      for( i=0 ; i<call_id.len ; hash_code+=call_id.s[i++]  );
76 
-#endif
77 
-
78 
-#if 0 /*def i386*/
79 
-
80 
-		int dummy2;
81 
-		if (cseq_nr.len>=4){
82 
-			asm(
83 
-				"1: \n\r"
84 
-				"addl (%1), %0 \n\r"
85 
-				"add $4, %1 \n\r"
86 
-				"cmp %2, %1 \n\r"
87 
-				"jl 1b  \n\r"
88 
-				: "=r"(hash_code), "=r"(dummy2)
89 
-				:  "0" (hash_code), "1"(cs),
90 
-				"r"((cs_len & (~3) )+ cs)
91 
-			);
92 
-		}
93 
-#else
94 
-    if ( cseq_nr.len>0 )
95 
-      for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
96 
-#endif
97 
-	/* this is a buggy line, see bellow hot to fix it -- as this
98 
-	   code is obsoleted I dont care anymore
99 
-	*/
100 
-   return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
101 
-}
102 
-
103 
-#endif
104 47
105 48 
 int new_hash( str call_id, str cseq_nr )
106 49 
 {
... ... 
@@ -152,6 +95,40 @@ int new_hash( str call_id, str cseq_nr )
152 95 
    	return hash_code;
153 96 
 }
154 97
98 
+
99 
+
100 
+int new_hash2( str call_id, str cseq_nr )
101 
+{
102 
+#define h_inc h+=v^(v>>3)
103 
+	char* p;
104 
+	register unsigned v;
105 
+	register unsigned h;
106 
+
107 
+	h=0;
108 
+
109 
+
110 
+	for (p=call_id.s; p<=(call_id.s+call_id.len-4); p+=4){
111 
+		v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
112 
+		h_inc;
113 
+	}
114 
+	v=0;
115 
+	for (;p<(call_id.s+call_id.len); p++){ v<<=8; v+=*p;}
116 
+	h_inc;
117 
+
118 
+	for (p=cseq_nr.s; p<=(cseq_nr.s+cseq_nr.len-4); p+=4){
119 
+		v=(*p<<24)+(p[1]<<16)+(p[2]<<8)+p[3];
120 
+		h_inc;
121 
+	}
122 
+	v=0;
123 
+	for (;p<(cseq_nr.s+cseq_nr.len); p++){ v<<=8; v+=*p;}
124 
+	h_inc;
125 
+
126 
+	h=((h)+(h>>11))+((h>>13)+(h>>23));
127 
+	return (h)&(TABLE_ENTRIES-1);
128 
+}
129 
+
130 
+
131 
+
155 132 
 void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
156 133 
 {
157 134 
 	long int i,j,k, l;
Browse code

GPLization banner introduced to *.[hc] files

Jiri Kuthan authored on 19/09/2002 12:23:52
Showing 1 changed files
hash_func.c
History View file @ 7dd0b34273
... ... 
@@ -1,8 +1,32 @@
1 1 
 /*
2 2 
  * $Id$
3 
+ *
4 
+ * Copyright (C) 2001-2003 Fhg Fokus
5 
+ *
6 
+ * This file is part of ser, a free SIP server.
7 
+ *
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
3 26 
  */
4 27
5 28
29 
+
6 30 
 #ifndef _CRC_H_
7 31 
 #define _CRC_H_
8 32
Browse code

few comments on hash distribution added

Jiri Kuthan authored on 29/08/2002 18:22:49
Showing 1 changed files
hash_func.c
History View file @ 73c6728d46
... ... 
@@ -111,15 +111,24 @@ int new_hash( str call_id, str cseq_nr )
111 111 
 		//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
112 112 
 		hash_code+=ccitt_tab[*(cs+i)+123];
113 113
114 
+	/* hash_code conditioning */
114 115 
 #ifdef _BUG
116 
+	/* not flat ... % 111b has shorter period than
117 
+       & 111b by one and results in different distribution;
118 
+	   ( 7 % 7 == 0, 7 %7 == 1 )
119 
+ 	   % is used as a part of the hash function too, not only
120 
+	   for rounding; & is not flat; whoever comes up with
121 
+	   a nicer flat hash function which does not take
122 
+	   costly division is welcome; feel free to verify
123 
+	   distribution using hashtest()
124 
+    */
115 125 
 	hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
116 126 
 #endif
117 
-	/* hash_code conditioning */
118 127 
 	hash_code=hash_code%(TABLE_ENTRIES-1)+1;
119 128 
    	return hash_code;
120 129 
 }
121 130
122 
-void hashtest_cycle( int hits[TABLE_ENTRIES], char *ip )
131 
+void hashtest_cycle( int hits[TABLE_ENTRIES+5], char *ip )
123 132 
 {
124 133 
 	long int i,j,k, l;
125 134 
 	int  hashv;
... ... 
@@ -151,20 +160,23 @@ int init_hash()
151 160 
 			1<<10);
152 161 
 		LOG(L_WARN, "WARNING: use of %d entries may lead "
153 162 
 			"to unflat distribution\n", TABLE_ENTRIES );
163 
+	} else {
164 
+		DBG("DEBUG: hash function initialized with optimum table size\n");
154 165 
 	}
155 166 
 	return 1;
156 167 
 }
157 168
158 169 
 void hashtest()
159 170 
 {
160 
-	int hits[TABLE_ENTRIES];
171 
+	int hits[TABLE_ENTRIES+5];
161 172 
 	int i;
162 
-
173 
+
174 
+	init_hash();
163 175 
 	memset( hits, 0, sizeof hits );
164 176 
 	hashtest_cycle( hits, "192.168.99.100" );
165 177 
 	hashtest_cycle( hits, "172.168.99.100" );
166 178 
 	hashtest_cycle( hits, "142.168.99.100" );
167 
-	for (i=0; i<TABLE_ENTRIES; i++)
179 
+	for (i=0; i<TABLE_ENTRIES+5; i++)
168 180 
 		printf("[%d. %d]\n", i, hits[i] );
169 181 
 	exit(0);
170 182 
 }
Browse code

bug_fix: hash function's distribution flatened and singular value 0 no more used (caused troubles when generating branch)

Jiri Kuthan authored on 28/08/2002 13:48:50
Showing 1 changed files
hash_func.c
History View file @ 9df1213c46
... ... 
@@ -20,6 +20,7 @@ extern unsigned short int crc_16_tab[];
20 20 
 #include "crc.h"
21 21 
 #include "ut.h"
22 22
23 
+#ifdef _OBSOLETED
23 24 
 int old_hash( str  call_id, str cseq_nr )
24 25 
 {
25 26 
    int  hash_code = 0;
... ... 
@@ -69,9 +70,14 @@ int old_hash( str  call_id, str cseq_nr )
69 70 
     if ( cseq_nr.len>0 )
70 71 
       for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
71 72 
 #endif
73 
+	/* this is a buggy line, see bellow hot to fix it -- as this
74 
+	   code is obsoleted I dont care anymore
75 
+	*/
72 76 
    return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
73 77 
 }
74 78
79 
+#endif
80 
+
75 81 
 int new_hash( str call_id, str cseq_nr )
76 82 
 {
77 83 
 	int hash_code = 0;
... ... 
@@ -105,7 +111,11 @@ int new_hash( str call_id, str cseq_nr )
105 111 
 		//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
106 112 
 		hash_code+=ccitt_tab[*(cs+i)+123];
107 113
114 
+#ifdef _BUG
108 115 
 	hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
116 
+#endif
117 
+	/* hash_code conditioning */
118 
+	hash_code=hash_code%(TABLE_ENTRIES-1)+1;
109 119 
    	return hash_code;
110 120 
 }
111 121
... ... 
@@ -128,12 +138,23 @@ void hashtest_cycle( int hits[TABLE_ENTRIES], char *ip )
128 138 
 					call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
129 139 
 						(int)k, ip );
130 140 
 					cseq.len=sprintf( buf2, "%d", (int)l );
131 
-					printf("%s\t%s\n", buf1, buf2 );
141 
+					/* printf("%s\t%s\n", buf1, buf2 ); */
132 142 
 					hashv=hash( call_id, cseq );
133 143 
 					hits[ hashv ]++;
134 144 
 				}
135 145 
 }
136 146
147 
+int init_hash()
148 
+{
149 
+	if (TABLE_ENTRIES != (1<<10)) {
150 
+		LOG(L_WARN, "WARNING: hash function optimized for %d entries\n",
151 
+			1<<10);
152 
+		LOG(L_WARN, "WARNING: use of %d entries may lead "
153 
+			"to unflat distribution\n", TABLE_ENTRIES );
154 
+	}
155 
+	return 1;
156 
+}
157 
+
137 158 
 void hashtest()
138 159 
 {
139 160 
 	int hits[TABLE_ENTRIES];
Browse code

bigbang

Jiri Kuthan authored on 15/08/2002 12:57:47
Showing 1 changed files
hash_func.c
History View file @ 3828f84113
1 1 
new file mode 100644
... ... 
@@ -0,0 +1,150 @@
1 
+/*
2 
+ * $Id$
3 
+ */
4 
+
5 
+
6 
+#ifndef _CRC_H_
7 
+#define _CRC_H_
8 
+
9 
+extern unsigned long int crc_32_tab[];
10 
+extern unsigned short int ccitt_tab[];
11 
+extern unsigned short int crc_16_tab[];
12 
+
13 
+#endif
14 
+
15 
+#include <stdio.h>
16 
+#include <string.h>
17 
+#include <stdlib.h>
18 
+#include "hash_func.h"
19 
+#include "dprint.h"
20 
+#include "crc.h"
21 
+#include "ut.h"
22 
+
23 
+int old_hash( str  call_id, str cseq_nr )
24 
+{
25 
+   int  hash_code = 0;
26 
+   int  i;
27 
+
28 
+#if 0 /*def i386*/
29 
+   int ci_len, cs_len;
30 
+   char *ci, *cs;
31 
+
32 
+	trim_len( ci_len, ci, call_id );
33 
+	trim_len( cs_len, cs, cseq_nr );
34 
+
35 
+		int dummy1;
36 
+		if (call_id.len>=4){
37 
+			asm(
38 
+				"1: \n\r"
39 
+				"addl (%1), %0 \n\r"
40 
+				"add $4, %1 \n\r"
41 
+				"cmp %2, %1 \n\r"
42 
+				"jl 1b  \n\r"
43 
+				: "=r"(hash_code), "=r"(dummy1)
44 
+				:  "0" (hash_code), "1"(ci),
45 
+				"r"( (ci_len & (~3)) +ci)
46 
+			);
47 
+		}
48 
+#else
49 
+    if ( call_id.len>0 )
50 
+      for( i=0 ; i<call_id.len ; hash_code+=call_id.s[i++]  );
51 
+#endif
52 
+
53 
+#if 0 /*def i386*/
54 
+
55 
+		int dummy2;
56 
+		if (cseq_nr.len>=4){
57 
+			asm(
58 
+				"1: \n\r"
59 
+				"addl (%1), %0 \n\r"
60 
+				"add $4, %1 \n\r"
61 
+				"cmp %2, %1 \n\r"
62 
+				"jl 1b  \n\r"
63 
+				: "=r"(hash_code), "=r"(dummy2)
64 
+				:  "0" (hash_code), "1"(cs),
65 
+				"r"((cs_len & (~3) )+ cs)
66 
+			);
67 
+		}
68 
+#else
69 
+    if ( cseq_nr.len>0 )
70 
+      for( i=0 ; i<cseq_nr.len ; hash_code+=cseq_nr.s[i++] );
71 
+#endif
72 
+   return hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
73 
+}
74 
+
75 
+int new_hash( str call_id, str cseq_nr )
76 
+{
77 
+	int hash_code = 0;
78 
+	int i,j, k, third;
79 
+	int ci_len, cs_len;
80 
+	char *ci, *cs;
81 
+
82 
+	/* trim EoLs */
83 
+/*
84 
+	ci_len = call_id.len;
85 
+	while (ci_len && ((c=call_id.s[ci_len-1])==0 || c=='\r' || c=='\n'))
86 
+		ci_len--;
87 
+	cs_len = cseq_nr.len;
88 
+	while (cs_len && ((c=cseq_nr.s[cs_len-1])==0 || c=='\r' || c=='\n'))
89 
+		cs_len--;
90 
+*/
91 
+	trim_len( ci_len, ci, call_id );
92 
+	trim_len( cs_len, cs, cseq_nr );
93 
+
94 
+	/* run the cycle from the end ... we are interested in the
95 
+	   most-right digits ... and just take the %10 value of it
96 
+	*/
97 
+	third=(ci_len-1)/3;
98 
+	for ( i=ci_len-1, j=2*third, k=third;
99 
+		k>0 ; i--, j--, k-- ) {
100 
+		hash_code+=crc_16_tab[(unsigned char)(*(ci+i)) /*+7*/ ]+
101 
+			ccitt_tab[*(ci+k)+63]+
102 
+			ccitt_tab[*(ci+j)+13];
103 
+	}
104 
+	for( i=0 ; i<cs_len ; i++ )
105 
+		//hash_code+=crc_32_tab[(cseq_nr.s[i]+hash_code)%243];
106 
+		hash_code+=ccitt_tab[*(cs+i)+123];
107 
+
108 
+	hash_code &= (TABLE_ENTRIES-1); /* TABLE_ENTRIES = 2^k */
109 
+   	return hash_code;
110 
+}
111 
+
112 
+void hashtest_cycle( int hits[TABLE_ENTRIES], char *ip )
113 
+{
114 
+	long int i,j,k, l;
115 
+	int  hashv;
116 
+	static char buf1[1024];
117 
+	static char buf2[1024];
118 
+	str call_id;
119 
+	str cseq;
120 
+
121 
+	call_id.s=buf1;
122 
+	cseq.s=buf2;
123 
+
124 
+	for (i=987654328;i<987654328+10;i++)
125 
+		for (j=85296341;j<85296341+10;j++)
126 
+			for (k=987654;k<=987654+10;k++)
127 
+				for (l=101;l<201;l++) {
128 
+					call_id.len=sprintf( buf1, "%d-%d-%d@%s",(int)i,(int)j,
129 
+						(int)k, ip );
130 
+					cseq.len=sprintf( buf2, "%d", (int)l );
131 
+					printf("%s\t%s\n", buf1, buf2 );
132 
+					hashv=hash( call_id, cseq );
133 
+					hits[ hashv ]++;
134 
+				}
135 
+}
136 
+
137 
+void hashtest()
138 
+{
139 
+	int hits[TABLE_ENTRIES];
140 
+	int i;
141 
+
142 
+	memset( hits, 0, sizeof hits );
143 
+	hashtest_cycle( hits, "192.168.99.100" );
144 
+	hashtest_cycle( hits, "172.168.99.100" );
145 
+	hashtest_cycle( hits, "142.168.99.100" );
146 
+	for (i=0; i<TABLE_ENTRIES; i++)
147 
+		printf("[%d. %d]\n", i, hits[i] );
148 
+	exit(0);
149 
+}
150 
+