source: trunk/ARBDB/gb_hashindex.h

Last change on this file was 11598, checked in by epruesse, 11 years ago

add DJB2 as hash function for GB_hash (needs #define change to activate)

Based on a trace of the GB_hash calls executed when GB_open'ing a large SILVA
database, I've tried a few hashing methods. GB_hash fares better than
stl::unordered_map, and the DJB2 function got the best results among the
hash functions I tested.
File size: 3.8 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : gb_hashindex.h                                    //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#ifndef GB_HASHINDEX_H
12#define GB_HASHINDEX_H
13
14#ifndef GB_LOCAL_H
15#include "gb_local.h"
16#endif
17
18// -------------------------------
19//      hash index calculation
20
21extern const uint32_t crctab[];
22//#define USE_DJB2_HASH
23#define USE_ARB_CRC_HASH
24#ifdef USE_ARB_CRC_HASH
25
26#define GB_CALC_HASH_INDEX_CASE_SENSITIVE(string, index, size) do {     \
27        const char *local_ptr = (string);                               \
28        int local_i;                                                    \
29        (index) = 0xffffffffL;                                          \
30        while ((local_i=(*(local_ptr++)))) {                            \
31            (index) = crctab[((int)(index)^local_i) & 0xff] ^ ((index) >> 8); \
32        }                                                               \
33        (index) = (index) % (size);                                     \
34    } while (0)
35
36#define GB_CALC_HASH_INDEX_CASE_IGNORED(string, index, size) do {       \
37        const char *local_ptr = (string);                               \
38        int local_i;                                                    \
39        (index) = 0xffffffffL;                                          \
40        while ((local_i = *(local_ptr++))) {                            \
41            (index) = crctab[((int) (index) ^ toupper(local_i)) & 0xff] ^ ((index) >> 8); \
42        }                                                               \
43        (index) = (index) % (size);                                     \
44    } while (0)
45
46#elif defined(USE_DJB2_HASH)
47
48#define GB_CALC_HASH_INDEX_CASE_SENSITIVE(string, index, size) do {     \
49        const char *local_ptr = (string);                               \
50        (index) = 5381;                                                 \
51        int local_i;                                                    \
52        while ((local_i = *(local_ptr++))) {                            \
53            (index) = (((index) << 5) + (index))+ local_i;              \
54        }                                                               \
55        (index) = (index) % (size);                                     \
56    } while (0)
57
58#define GB_CALC_HASH_INDEX_CASE_IGNORED(string, index, size) do {       \
59        const char *local_ptr = (string);                               \
60        int local_i;                                                    \
61        (index) = 5381;                                                 \
62        while ((local_i = *(local_ptr++))) {                            \
63            (index) = (((index) << 5) + (index))+ toupper(local_i);     \
64        }                                                               \
65        (index) = (index) % (size);                                     \
66    } while (0)
67
68#endif
69
70#define GB_CALC_HASH_INDEX(string, index, size, caseSens) do {          \
71        if ((caseSens) == GB_IGNORE_CASE)                               \
72            GB_CALC_HASH_INDEX_CASE_IGNORED(string, index, size);       \
73        else                                                            \
74            GB_CALC_HASH_INDEX_CASE_SENSITIVE(string, index, size);     \
75    } while (0)
76
77
78
79#else
80#error gb_hashindex.h included twice
81#endif // GB_HASHINDEX_H
Note: See TracBrowser for help on using the repository browser.