/[resiprocate]/main/resip/stack/test/testHashCasen.cxx
ViewVC logotype

Contents of /main/resip/stack/test/testHashCasen.cxx

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5948 - (show annotations) (download)
Fri Feb 17 15:30:16 2006 UTC (13 years, 8 months ago) by dworley
File MIME type: text/plain
File size: 6340 byte(s)
Setting more svn: properties, and adding EOLs to the ends of files
that need it.

1 #include <iostream>
2 #include <string>
3 #include <assert.h>
4
5 // djb2 hash swiped from the net, credited to bernstein
6 unsigned int
7 hash(const char *str, unsigned int len)
8 {
9 unsigned int hash = 5381;
10 int c;
11 int i = 0;
12
13 while (c = *str++)
14 {
15 if (i == len)
16 {
17 break;
18 }
19 hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
20 }
21 hash = ((hash << 5) + hash) + len;
22 return hash;
23 }
24
25 // unrolled and case insensitized
26 unsigned int
27 hashcasen(const char* data,
28 unsigned int len)
29 {
30 unsigned int x = 5381;
31 switch (len)
32 {
33 case 1 :
34 return (x << 5) + x + (0x40 | *data);
35 case 2 :
36 {
37 x = (x << 5) + x + (0x40 | *data);
38 return (x << 5) + x + (0x40 | *(data+1));
39 }
40 case 3 :
41 {
42 x = (x << 5) + x + (0x40 | *data);
43 x = (x << 5) + x + (0x40 | *(data+1));
44 return (x << 5) + x + (0x40 | *(data+2));
45 }
46 default :
47 {
48 x = (x << 5) + x + (0x40 | *data);
49 x = (x << 5) + x + (0x40 | *(data+len-1));
50 x = (x << 5) + x + (0x40 | *(data+2));
51 x = (x << 5) + x + (0x40 | *(data+len-2));
52 return (x << 5) + x + len;
53 }
54 }
55 }
56
57 // strategy:
58 // use sparse parallel arrays of size num_buckets + 1
59 // name => enum
60 // the name is stored by hashcasen(name) % num_buckets
61 // if the position is occupied, move up the array until a free spot is found
62 // on lookup:
63 // if the name array [hash] is empty, return UNKNOWN
64 // if the name array[hash] is occupied and equal, found, return enum[hash]
65 // if the name array[hash] is occupied and !equal, try hash++
66
67 int
68 main()
69 {
70 std::string parameters[17] =
71 {
72 "transport",
73 "user",
74 "method",
75 "ttl",
76 "maddr",
77 "lr",
78 "q",
79 "purpose",
80 "expires",
81 "handling",
82 "tag",
83 "duration",
84 "branch",
85 "received",
86 "comp",
87 "rport"
88 };
89
90 std::string PARAMETERS[17] =
91 {
92 "TRANSPORT",
93 "USER",
94 "METHOD",
95 "TTL",
96 "MADDR",
97 "LR",
98 "Q",
99 "PURPOSE",
100 "EXPIRES",
101 "HANDLING",
102 "TAG",
103 "DURATION",
104 "BRANCH",
105 "RECEIVED",
106 "COMP",
107 "RPORT"
108 };
109
110
111 for (int i = 0; i < 16; i++)
112 {
113 std::cerr << parameters[i] << " => " << hashcasen(parameters[i].c_str(), parameters[i].size()) % 73 << std::endl;
114 assert(hashcasen(parameters[i].c_str(), parameters[i].size()) == hashcasen(parameters[i].c_str(), PARAMETERS[i].size()));
115 }
116 std::cerr << std::endl;
117 std::cerr << std::endl;
118
119 std::string headers[] =
120 {
121 "Body",
122 "CSeq",
123 "Call_ID",
124 "Contact",
125 "Content_Length",
126 "Expires",
127 "From",
128 "Max_Forwards",
129 "Route",
130 "Subject",
131 "To",
132 "Via",
133 "Accept",
134 "Accept_Encoding",
135 "Accept_Language",
136 "Alert_Info",
137 "Allow",
138 "Authentication_Info",
139 "Authorization",
140 "Call_Info",
141 "Content_Disposition",
142 "Content_Encoding",
143 "Content_Language",
144 "Content_Type",
145 "Date",
146 "Error_Info",
147 "In_Reply_To",
148 "Min_Expires",
149 "MIME_Version",
150 "Organization",
151 "Priority",
152 "Proxy_Authenticate",
153 "Proxy_Authorization",
154 "Proxy_Require",
155 "Record_Route",
156 "Reply_To",
157 "Require",
158 "Retry_After",
159 "Server",
160 "Supported",
161 "Timestamp",
162 "Unsupported",
163 "User_Agent",
164 "Warning",
165 "WWW_Authenticate",
166 "Subscription_State"
167 };
168
169 for (int i = 0; i < 46; i++)
170 {
171 std::cerr << headers[i] << " => " << hashcasen(headers[i].c_str(), headers[i].size()) % 505 << std::endl;
172 }
173 }
174
175
176
177
178 /* ====================================================================
179 * The Vovida Software License, Version 1.0
180 *
181 * Copyright (c) 2000 Vovida Networks, Inc. All rights reserved.
182 *
183 * Redistribution and use in source and binary forms, with or without
184 * modification, are permitted provided that the following conditions
185 * are met:
186 *
187 * 1. Redistributions of source code must retain the above copyright
188 * notice, this list of conditions and the following disclaimer.
189 *
190 * 2. Redistributions in binary form must reproduce the above copyright
191 * notice, this list of conditions and the following disclaimer in
192 * the documentation and/or other materials provided with the
193 * distribution.
194 *
195 * 3. The names "VOCAL", "Vovida Open Communication Application Library",
196 * and "Vovida Open Communication Application Library (VOCAL)" must
197 * not be used to endorse or promote products derived from this
198 * software without prior written permission. For written
199 * permission, please contact vocal@vovida.org.
200 *
201 * 4. Products derived from this software may not be called "VOCAL", nor
202 * may "VOCAL" appear in their name, without prior written
203 * permission of Vovida Networks, Inc.
204 *
205 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
206 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
207 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE AND
208 * NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT SHALL VOVIDA
209 * NETWORKS, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT DAMAGES
210 * IN EXCESS OF $1,000, NOR FOR ANY INDIRECT, INCIDENTAL, SPECIAL,
211 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
212 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
213 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
214 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
215 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
216 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
217 * DAMAGE.
218 *
219 * ====================================================================
220 *
221 * This software consists of voluntary contributions made by Vovida
222 * Networks, Inc. and many individuals on behalf of Vovida Networks,
223 * Inc. For more information on Vovida Networks, Inc., please see
224 * <http://www.vovida.org/>.
225 *
226 */

Properties

Name Value
svn:eol-style native
svn:mime-type text/plain

webmaster AT resiprocate DOT org
ViewVC Help
Powered by ViewVC 1.1.27