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 |
|