/[zanavi_public1]/navit/navit/maptool/quick_hash.c
ZANavi

Contents of /navit/navit/maptool/quick_hash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 57 - (show annotations) (download)
Sun Mar 19 16:46:08 2017 UTC (7 years ago) by zoff99
File MIME type: text/plain
File size: 11161 byte(s)
updates
1 /**
2 * ZANavi, Zoff Android Navigation system.
3 * Copyright (C) 2012-2013 Zoff <zoff@zoff.cc>
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 */
19
20 #include "maptool.h"
21
22 struct quickhash_table {
23 unsigned int num_buckets;
24 unsigned long long num_entries; /* Total number of entries in the table */
25 struct quickhash_bucket *bucket_list; // pointer to list of all buckets
26 };
27
28 struct quickhash_entry {
29 long long key;
30 // void* value_ptr;
31 int value_ptr;
32 };
33
34 struct quickhash_bucket {
35 struct quickhash_entry *entry;
36 unsigned char* mem; // mem that holds the entries
37 unsigned int mem_size; // size of mem in number of entries
38 unsigned int num_entries; /* Total number of entries in this bucket */
39 };
40
41
42 #define QHASH_ENTRY_INC 10
43
44 #define GOOD_PRIME 373587743
45 #define HASH_SEED 373587743
46
47 static const unsigned int mmm__ = 0xc6a4a793;
48 static const int rrr__ = 16;
49
50 unsigned int MurmurHash1Aligned(const void *key, int len, unsigned int seed)
51 {
52
53 const unsigned char * data = (const unsigned char *)key;
54
55 unsigned int h = seed ^ (len * mmm__);
56
57 int align = (uint64_t)data & 3;
58
59 if(align && (len >= 4))
60 {
61 // Pre-load the temp registers
62
63 unsigned int t = 0, d = 0;
64
65 switch(align)
66 {
67 case 1: t |= data[2] << 16;
68 case 2: t |= data[1] << 8;
69 case 3: t |= data[0];
70 }
71
72 t <<= (8 * align);
73
74 data += 4-align;
75 len -= 4-align;
76
77 int sl = 8 * (4-align);
78 int sr = 8 * align;
79
80 // Mix
81
82 while(len >= 4)
83 {
84 d = *(unsigned int *)data;
85 t = (t >> sr) | (d << sl);
86 h += t;
87 h *= mmm__;
88 h ^= h >> rrr__;
89 t = d;
90
91 data += 4;
92 len -= 4;
93 }
94
95 // Handle leftover data in temp registers
96
97 int pack = len < align ? len : align;
98
99 d = 0;
100
101 switch(pack)
102 {
103 case 3: d |= data[2] << 16;
104 case 2: d |= data[1] << 8;
105 case 1: d |= data[0];
106 case 0: h += (t >> sr) | (d << sl);
107 h *= mmm__;
108 h ^= h >> rrr__;
109 }
110
111 data += pack;
112 len -= pack;
113 }
114 else
115 {
116 while(len >= 4)
117 {
118 h += *(unsigned int *)data;
119 h *= mmm__;
120 h ^= h >> rrr__;
121
122 data += 4;
123 len -= 4;
124 }
125 }
126
127 //----------
128 // Handle tail bytes
129
130 switch(len)
131 {
132 case 3: h += data[2] << 16;
133 case 2: h += data[1] << 8;
134 case 1: h += data[0];
135 h *= mmm__;
136 h ^= h >> rrr__;
137 };
138
139 h *= mmm__;
140 h ^= h >> 10;
141 h *= mmm__;
142 h ^= h >> 17;
143
144 return h;
145 }
146
147
148
149
150
151 static uint32_t h1 = (uint32_t)(1) ^ (sizeof (long long));
152 static uint32_t h2 = (uint32_t)(1 >> 32);
153
154 uint64_t MurmurHash64B ( const void * key, int len, uint64_t seed )
155 {
156 const uint32_t m = 0x5bd1e995;
157 const int r = 24;
158
159 // uint32_t h1 = (uint32_t)(seed) ^ len;
160 // uint32_t h2 = (uint32_t)(seed >> 32);
161
162 const uint32_t * data = (const uint32_t *)key;
163
164 while(len >= 8)
165 {
166 uint32_t k1 = *data++;
167 k1 *= m; k1 ^= k1 >> r; k1 *= m;
168 h1 *= m; h1 ^= k1;
169 len -= 4;
170
171 uint32_t k2 = *data++;
172 k2 *= m; k2 ^= k2 >> r; k2 *= m;
173 h2 *= m; h2 ^= k2;
174 len -= 4;
175 }
176
177 if(len >= 4)
178 {
179 uint32_t k1 = *data++;
180 k1 *= m; k1 ^= k1 >> r; k1 *= m;
181 h1 *= m; h1 ^= k1;
182 len -= 4;
183 }
184
185 switch(len)
186 {
187 case 3: h2 ^= ((unsigned char*)data)[2] << 16;
188 case 2: h2 ^= ((unsigned char*)data)[1] << 8;
189 case 1: h2 ^= ((unsigned char*)data)[0];
190 h2 *= m;
191 };
192
193 h1 ^= h2 >> 18; h1 *= m;
194 h2 ^= h1 >> 22; h2 *= m;
195 h1 ^= h2 >> 17; h1 *= m;
196 h2 ^= h1 >> 19; h2 *= m;
197
198 uint64_t h = h1;
199
200 h = (h << 32) | h2;
201
202 return h;
203 }
204
205
206 // input: a 64bit key
207 // returns: bucket number (0 - max_buckets)
208 int quick_hash_hash(struct quickhash_table* table, long long key)
209 {
210 int out;
211 out = MurmurHash64B(&key, sizeof(key), 1);
212 return (out % table->num_buckets);
213 }
214
215
216 void quick_hash_add_entry(struct quickhash_table* table, long long key, int value_ptr)
217 {
218 int bucket;
219 struct quickhash_bucket *cur_bucket;
220 struct quickhash_entry* e;
221 void *tmp_ptr;
222 unsigned int mem_size_old;
223
224 #ifdef HASH_SIMPLE
225 key ^= key >> 33;
226 key *= 0xff51afd7ed558ccd;
227 key ^= key >> 33;
228 //key *= 0xc4ceb9fe1a85ec53;
229 //key ^= key >> 33;
230 bucket = key % table->num_buckets;
231 #else
232 bucket = MurmurHash1Aligned(&key, sizeof(key), HASH_SEED);
233 // bucket = MurmurHash64B(&key, sizeof(key), 1);
234 bucket = bucket % table->num_buckets;
235 #endif
236
237 cur_bucket = table->bucket_list + bucket; // move pointer to wanted bucket list struct
238 //fprintf(stderr, "quick_hash:add_entry:k=%lld bl=%p b=%p bnum=%d\n", key, table->bucket_list, cur_bucket, bucket);
239
240 // init the bucket and its memory
241 if (cur_bucket->mem == NULL)
242 {
243 // cur_bucket->mem = malloc((size_t)(QHASH_ENTRY_INC * sizeof(struct quickhash_entry)));
244 // cur_bucket->mem = calloc(QHASH_ENTRY_INC, sizeof(struct quickhash_entry));
245 cur_bucket->mem = g_new0(struct quickhash_entry, QHASH_ENTRY_INC);
246 cur_bucket->entry = cur_bucket->mem;
247 cur_bucket->mem_size = QHASH_ENTRY_INC;
248 }
249
250 // add more mem for entries
251 if (cur_bucket->mem_size <= cur_bucket->num_entries)
252 {
253 tmp_ptr = cur_bucket->mem;
254 mem_size_old = cur_bucket->mem_size;
255 cur_bucket->mem_size = cur_bucket->mem_size + QHASH_ENTRY_INC;
256 // cur_bucket->mem = realloc((void *)tmp_ptr, (size_t)(cur_bucket->mem_size * sizeof(struct quickhash_entry)));
257 // cur_bucket->mem = malloc((size_t)(cur_bucket->mem_size * sizeof(struct quickhash_entry)));
258 // cur_bucket->mem = (struct quickhash_entry *)g_new0(struct quickhash_entry, cur_bucket->mem_size);
259 // cur_bucket->mem = g_realloc(tmp_ptr, cur_bucket->mem_size * sizeof(struct quickhash_entry));
260 cur_bucket->mem = g_renew(struct quickhash_entry, tmp_ptr, cur_bucket->mem_size);
261 if (!cur_bucket->mem)
262 {
263 cur_bucket->mem = tmp_ptr;
264 cur_bucket->mem_size = mem_size_old;
265 fprintf(stderr, "quick_hash:ERROR-002\n");
266 return;
267 }
268
269 if (tmp_ptr != cur_bucket->mem)
270 {
271 // copy over the memory
272 // *** // memcpy(cur_bucket->mem, tmp_ptr, (size_t)(mem_size_old * QHASH_ENTRY_INC));
273
274 //fprintf(stderr, "quick_hash:add_entry:diff=%d entry=%p mem=%p num entries=%d\n", ((int)cur_bucket->entry - (int)tmp_ptr), cur_bucket->entry, tmp_ptr, cur_bucket->num_entries);
275 // move entry pointer to new mem
276 cur_bucket->entry = cur_bucket->mem;
277 cur_bucket->entry = cur_bucket->entry + cur_bucket->num_entries;
278 //fprintf(stderr, "quick_hash:add_entry:diff=%d entry=%p mem=%p num entries=%d\n", ((int)cur_bucket->entry - (int)cur_bucket->mem), cur_bucket->entry, cur_bucket->mem, cur_bucket->num_entries);
279
280 // free the old mem
281 // *** // g_free(tmp_ptr);
282 }
283 }
284
285 e = (struct quickhash_entry*)cur_bucket->entry;
286 e->key = key;
287 e->value_ptr = value_ptr;
288
289 cur_bucket->num_entries++;
290 cur_bucket->entry++; // move pointer to next free entry
291
292 table->num_entries++;
293 }
294
295 void* quick_hash_print_stats(struct quickhash_table* table)
296 {
297 long long size_all;
298 long long min_entries;
299 long long max_entries;
300 long long empty_buckets;
301 int i;
302 struct quickhash_bucket *cur_bucket = table->bucket_list;
303
304 size_all = (long long)(table->num_buckets * sizeof(struct quickhash_bucket));
305 // size_all = size_all + (table->num_entries * sizeof(struct quickhash_entry));
306
307 min_entries = 1000000;
308 max_entries = 0;
309 empty_buckets = 0;
310 for (i=0;i<table->num_buckets;i++)
311 {
312 size_all = size_all + (cur_bucket->mem_size * sizeof(struct quickhash_entry));
313
314 if (cur_bucket->mem == NULL)
315 {
316 min_entries = 0;
317 empty_buckets++;
318 }
319 else
320 {
321 if (cur_bucket->num_entries == 0)
322 {
323 empty_buckets++;
324 }
325
326 if (cur_bucket->num_entries < min_entries)
327 {
328 min_entries = cur_bucket->num_entries;
329 }
330
331 if (cur_bucket->num_entries > max_entries)
332 {
333 max_entries = cur_bucket->num_entries;
334 }
335 }
336 cur_bucket++;
337 }
338
339 fprintf_(stderr, "quick_hash:size all=%lld MB\n", (long long)(size_all / 1024.0 / 1024.0));
340 fprintf_(stderr, "quick_hash:size entry=%d\n", (sizeof(struct quickhash_bucket)));
341 fprintf_(stderr, "quick_hash:size bucket=%d\n", (sizeof(struct quickhash_entry)));
342 fprintf_(stderr, "quick_hash:item count=%lld\n", table->num_entries);
343 fprintf_(stderr, "quick_hash:minbentries=%d\n", min_entries);
344 fprintf_(stderr, "quick_hash:maxbentries=%d\n", max_entries);
345 fprintf_(stderr, "quick_hash:empty bckts=%lld\n", empty_buckets);
346 }
347
348 int quick_hash_lookup(struct quickhash_table* table, long long key)
349 {
350 int bucket;
351 int i;
352 struct quickhash_bucket *cur_bucket;
353
354 #ifdef HASH_SIMPLE
355 key ^= key >> 33;
356 key *= 0xff51afd7ed558ccd;
357 key ^= key >> 33;
358 //key *= 0xc4ceb9fe1a85ec53;
359 //key ^= key >> 33;
360 bucket = key % table->num_buckets;
361 bucket = bucket % table->num_buckets;
362 #else
363 bucket = MurmurHash1Aligned(&key, sizeof(key), HASH_SEED);
364 // bucket = MurmurHash64B(&key, sizeof(key), 1);
365 bucket = bucket % table->num_buckets;
366 #endif
367
368 cur_bucket = table->bucket_list + bucket; // move pointer to wanted bucket list struct
369 //fprintf(stderr, "quick_hash:lookup:k=%lld bl=%p b=%p bnum=%d\n", key, table->bucket_list, cur_bucket, bucket);
370
371 if (cur_bucket->mem == NULL)
372 {
373 //fprintf(stderr, "quick_hash:lookup:NULL 001\n");
374 return -1;
375 }
376
377 if (cur_bucket->num_entries == 0)
378 {
379 //fprintf(stderr, "quick_hash:lookup:NULL 002\n");
380 return -1;
381 }
382
383 struct quickhash_entry* e = (struct quickhash_entry *)cur_bucket->mem;
384 for(i=0;i<cur_bucket->num_entries;i++)
385 {
386 //fprintf(stderr, "quick_hash:lookup:k=%lld d=%p\n", e->key, e->value_ptr);
387 if (e->key == key)
388 {
389 return e->value_ptr; // found key
390 }
391 e++; // move to next entry
392 }
393
394 return -1;
395 }
396
397 void quick_hash_destroy(struct quickhash_table* table)
398 {
399 int i;
400 struct quickhash_bucket *cur_bucket = table->bucket_list;
401 // struct quickhash_entry* e = cur_bucket->entry;
402
403 for (i=0;i<table->num_buckets;i++)
404 {
405 if (cur_bucket->mem != NULL)
406 {
407 g_free(cur_bucket->mem);
408 }
409 cur_bucket++;
410 }
411
412 g_free(table->bucket_list);
413
414 }
415
416 struct quickhash_table* quick_hash_init(int num_buckets)
417 {
418 int i;
419
420 struct quickhash_table *table=g_new0(struct quickhash_table, 1);
421 table->num_buckets = num_buckets;
422 table->num_entries = 0;
423
424 struct quickhash_bucket *bucket_list=g_new0(struct quickhash_bucket, num_buckets);
425 table->bucket_list = bucket_list;
426
427 struct quickhash_bucket *cur_bucket;
428 cur_bucket = table->bucket_list;
429 for (i=0;i<num_buckets;i++)
430 {
431 cur_bucket->mem = NULL;
432 cur_bucket->num_entries = 0;
433 cur_bucket->entry = NULL;
434 cur_bucket->mem_size = 0;
435 }
436
437 fprintf_(stderr, "quick_hash:size all=%lld\n", (long long)(table->num_buckets * sizeof(struct quickhash_bucket)));
438 fprintf_(stderr, "quick_hash:size entry=%d\n", (sizeof(struct quickhash_bucket)));
439 fprintf_(stderr, "quick_hash:size bucket=%d\n", (sizeof(struct quickhash_entry)));
440
441 return table;
442 }
443
444

   
Visit the ZANavi Wiki