summaryrefslogtreecommitdiff
path: root/legacy
diff options
context:
space:
mode:
authorBoris Faure <billiob@gmail.com>2011-11-10 10:58:19 +0000
committerBoris Faure <billiob@gmail.com>2011-11-10 10:58:19 +0000
commit37efd502fe75883ebb03520ff8761787167343d8 (patch)
tree78e442dcbbc77f6686e8d3af28d4fe92e7e067f7 /legacy
parentc049c0e12b7d38e54fbb6c223c699514918264ec (diff)
eina: add murmur3 hash
SVN revision: 65017
Diffstat (limited to '')
-rw-r--r--legacy/eina/src/include/eina_hash.h4
-rw-r--r--legacy/eina/src/include/eina_inline_hash.x63
-rw-r--r--legacy/eina/src/tests/eina_bench_hash.c49
3 files changed, 114 insertions, 2 deletions
diff --git a/legacy/eina/src/include/eina_hash.h b/legacy/eina/src/include/eina_hash.h
index 71de90ba23..c8eb04861b 100644
--- a/legacy/eina/src/include/eina_hash.h
+++ b/legacy/eina/src/include/eina_hash.h
@@ -1020,7 +1020,9 @@ static inline int eina_hash_int32(const unsigned int *pkey,
1020 int len) EINA_ARG_NONNULL(1); 1020 int len) EINA_ARG_NONNULL(1);
1021static inline int eina_hash_int64(const unsigned long int *pkey, 1021static inline int eina_hash_int64(const unsigned long int *pkey,
1022 int len) EINA_ARG_NONNULL(1); 1022 int len) EINA_ARG_NONNULL(1);
1023 1023/* http://sites.google.com/site/murmurhash/ */
1024static inline int eina_hash_murmur3(const char *key,
1025 int len) EINA_ARG_NONNULL(1);
1024#include "eina_inline_hash.x" 1026#include "eina_inline_hash.x"
1025 1027
1026/** 1028/**
diff --git a/legacy/eina/src/include/eina_inline_hash.x b/legacy/eina/src/include/eina_inline_hash.x
index 0fb992b620..f27060fb3d 100644
--- a/legacy/eina/src/include/eina_inline_hash.x
+++ b/legacy/eina/src/include/eina_inline_hash.x
@@ -85,4 +85,67 @@ eina_hash_int64(const unsigned long int *pkey, int len)
85 return (int) key; 85 return (int) key;
86} 86}
87 87
88static inline unsigned int _rotl32(unsigned int x, char r)
89{
90 return (x << r) | (x >> (32 - r));
91}
92
93static inline unsigned int _fmix32(unsigned int h)
94{
95 h ^= h >> 16;
96 h *= 0x85ebca6b;
97 h ^= h >> 13;
98 h *= 0xc2b2ae35;
99 h ^= h >> 16;
100
101 return h;
102}
103
104int
105eina_hash_murmur3(const char *key, int len)
106{
107 const unsigned char * data = (const unsigned char*)key;
108 const int nblocks = len / 4;
109 unsigned int h1 = 0, k1;
110 unsigned int c1 = 0xcc9e2d51;
111 unsigned int c2 = 0x1b873593;
112 const unsigned int * blocks = (const unsigned int *)(data + nblocks*4);
113 int i;
114 const unsigned char *tail;
115
116 for(i = -nblocks; i; i++)
117 {
118 k1 = blocks[i];
119
120 k1 *= c1;
121 k1 = _rotl32(k1, 15);
122 k1 *= c2;
123
124 h1 ^= k1;
125 h1 = _rotl32(h1, 13);
126 h1 = h1*5+0xe6546b64;
127 }
128
129 tail = (const unsigned char*)(data + nblocks*4);
130
131 k1 = 0;
132
133 switch(len & 3)
134 {
135 case 3:
136 k1 ^= tail[2] << 16;
137 case 2:
138 k1 ^= tail[1] << 8;
139 case 1:
140 k1 ^= tail[0];
141 k1 *= c1;
142 k1 = _rotl32(k1, 16);
143 k1 *= c2;
144 h1 ^= k1;
145 }
146
147 h1 ^= len;
148
149 return _fmix32(h1);
150}
88#endif 151#endif
diff --git a/legacy/eina/src/tests/eina_bench_hash.c b/legacy/eina/src/tests/eina_bench_hash.c
index 46feedc0a8..5b42318eb2 100644
--- a/legacy/eina/src/tests/eina_bench_hash.c
+++ b/legacy/eina/src/tests/eina_bench_hash.c
@@ -144,6 +144,49 @@ eina_bench_lookup_rbtree(int request)
144 eina_rbtree_delete(root, EINA_RBTREE_FREE_CB(_eina_bench_rbtree_free), NULL); 144 eina_rbtree_delete(root, EINA_RBTREE_FREE_CB(_eina_bench_rbtree_free), NULL);
145} 145}
146 146
147static void
148eina_bench_lookup_murmur(int request)
149{
150 Eina_Hash *hash = NULL;
151 int *tmp_val;
152 unsigned int i;
153 unsigned int j;
154
155 hash = eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
156 EINA_KEY_CMP(_eina_string_key_cmp),
157 EINA_KEY_HASH(eina_hash_murmur3),
158 free,
159 8);
160
161 for (i = 0; i < (unsigned int)request; ++i)
162 {
163 char tmp_key[10];
164
165 tmp_val = malloc(sizeof (int));
166
167 if (!tmp_val)
168 continue;
169
170 eina_convert_itoa(i, tmp_key);
171 *tmp_val = i;
172
173 eina_hash_add(hash, tmp_key, tmp_val);
174 }
175
176 srand(time(NULL));
177
178 for (j = 0; j < 200; ++j)
179 for (i = 0; i < (unsigned int)request; ++i)
180 {
181 char tmp_key[10];
182
183 eina_convert_itoa(rand() % request, tmp_key);
184 tmp_val = eina_hash_find(hash, tmp_key);
185 }
186
187 eina_hash_free(hash);
188}
189
147#ifdef CITYHASH_BENCH 190#ifdef CITYHASH_BENCH
148static void 191static void
149eina_bench_lookup_cityhash(int request) 192eina_bench_lookup_cityhash(int request)
@@ -476,10 +519,13 @@ void eina_bench_hash(Eina_Benchmark *bench)
476 eina_benchmark_register(bench, "djb2-lookup-inline", 519 eina_benchmark_register(bench, "djb2-lookup-inline",
477 EINA_BENCHMARK( 520 EINA_BENCHMARK(
478 eina_bench_lookup_djb2_inline), 10, 10000, 10); 521 eina_bench_lookup_djb2_inline), 10, 10000, 10);
522 eina_benchmark_register(bench, "murmur",
523 EINA_BENCHMARK(
524 eina_bench_lookup_murmur), 10, 10000, 10);
479#ifdef CITYHASH_BENCH 525#ifdef CITYHASH_BENCH
480 eina_benchmark_register(bench, "cityhash", 526 eina_benchmark_register(bench, "cityhash",
481 EINA_BENCHMARK( 527 EINA_BENCHMARK(
482 eina_bench_lookup_cityhash), 10, 10000, 10); 528 eina_bench_lookup_cityhash), 10, 10000, 10);
483#endif 529#endif
484 eina_benchmark_register(bench, "rbtree", 530 eina_benchmark_register(bench, "rbtree",
485 EINA_BENCHMARK( 531 EINA_BENCHMARK(
@@ -495,4 +541,5 @@ void eina_bench_hash(Eina_Benchmark *bench)
495 eina_benchmark_register(bench, "ecore-lookup", 541 eina_benchmark_register(bench, "ecore-lookup",
496 EINA_BENCHMARK( 542 EINA_BENCHMARK(
497 eina_bench_lookup_ecore), 10, 10000, 10); 543 eina_bench_lookup_ecore), 10, 10000, 10);
544
498} 545}