|
Simple data structures / objects in plain C Snapshot
|
#include <cutils/base.h>Go to the source code of this file.
Defines | |
| #define | HASH_STRING 0xFFFFFFFF |
Typedefs | |
| typedef uint32_t | HASH_VALUE |
Functions | |
| HASH_VALUE | HASHFUNCTION_PJW (void *keydata, ssize_t key_length) |
| P.J. Weinberger hash function. | |
| HASH_VALUE | HASHFUNCTION_rotating (void *keydata, ssize_t key_length) |
| Rotating hash. | |
| HASH_VALUE | HASHFUNCTION_shift_and_xor (void *keydata, ssize_t key_length) |
| Shift and XOR. | |
| HASH_VALUE | HASHFUNCTION_Fowler_Noll_Vo (void *keydata, ssize_t key_length) |
| Fowler/Noll/Vo hash. | |
| HASH_VALUE | HASHFUNCTION_Bob_Jenkins_one_at_a_time (void *keydata, ssize_t key_length) |
| One at a time by Bob Jenkins. | |
| HASH_VALUE | HASHFUNCTION_ELF (void *keydata, ssize_t key_length) |
| ELF hash. | |
| HASH_VALUE | HASHFUNCTION_Bob_Jenkins (void *keydata, ssize_t length) |
| Bob Jenkins. | |
| HASH_VALUE | HASHFUNCTION_sample_hash_func (void *keydata, ssize_t key_length) |
| good for most cases. | |
| #define HASH_STRING 0xFFFFFFFF |
A collection of hash functions, gathered from various places.
Definition at line 20 of file hashfunction.h.
| typedef uint32_t HASH_VALUE |
Definition at line 13 of file hashfunction.h.
| HASH_VALUE HASHFUNCTION_Bob_Jenkins | ( | void * | keydata, |
| ssize_t | length | ||
| ) |
Bob Jenkins.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
Very good hash function. Really very good - passes all sorts of avalanche tests.
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 220 of file hashfunction.c.
{
unsigned char *k = keydata;
unsigned a, b;
unsigned c = BJ_INIT_VAL;
unsigned len = length;
a = b = 0x9e3779b9;
if (length != -1) {
while ( len >= 12 ) {
a += ( k[0] + ( (unsigned)k[1] << 8 )
+ ( (unsigned)k[2] << 16 )
+ ( (unsigned)k[3] << 24 ) );
b += ( k[4] + ( (unsigned)k[5] << 8 )
+ ( (unsigned)k[6] << 16 )
+ ( (unsigned)k[7] << 24 ) );
c += ( k[8] + ( (unsigned)k[9] << 8 )
+ ( (unsigned)k[10] << 16 )
+ ( (unsigned)k[11] << 24 ) );
mix ( a, b, c );
k += 12;
len -= 12;
}
} else {
size_t pos_k = 0;
unsigned char *next_k;
length = 0;
while(1) {
for(pos_k = 0, next_k = (unsigned char *) k;
*next_k && pos_k<12 ;
pos_k++, next_k++);
length += pos_k;
if (pos_k < 12) {
len = pos_k;
break;
}
a += ( k[0] + ( (unsigned)k[1] << 8 )
+ ( (unsigned)k[2] << 16 )
+ ( (unsigned)k[3] << 24 ) );
b += ( k[4] + ( (unsigned)k[5] << 8 )
+ ( (unsigned)k[6] << 16 )
+ ( (unsigned)k[7] << 24 ) );
c += ( k[8] + ( (unsigned)k[9] << 8 )
+ ( (unsigned)k[10] << 16 )
+ ( (unsigned)k[11] << 24 ) );
mix ( a, b, c );
k += 12;
}
}
c += length;
switch ( len ) {
case 11: c += ( (unsigned)k[10] << 24 );
case 10: c += ( (unsigned)k[9] << 16 );
case 9 : c += ( (unsigned)k[8] << 8 );
/* First byte of c reserved for length */
case 8 : b += ( (unsigned)k[7] << 24 );
case 7 : b += ( (unsigned)k[6] << 16 );
case 6 : b += ( (unsigned)k[5] << 8 );
case 5 : b += k[4];
case 4 : a += ( (unsigned)k[3] << 24 );
case 3 : a += ( (unsigned)k[2] << 16 );
case 2 : a += ( (unsigned)k[1] << 8 );
case 1 : a += k[0];
}
mix ( a, b, c );
return c;
}
| HASH_VALUE HASHFUNCTION_Bob_Jenkins_one_at_a_time | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
One at a time by Bob Jenkins.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"This algorithm quickly reaches avalanche (!!!) and performs very well this function is another that should be one of the first to be tested in any application, if not the very first"
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 126 of file hashfunction.c.
{
HASH_VALUE h = 2166136261U;
unsigned char * key = (unsigned char *) keydata;
ssize_t i;
if (key_length != -1) {
for ( i = 0; i < key_length; i++ ) {
h += key[i];
h += ( h << 10 );
h ^= ( h >> 6 );
}
h += ( h << 3 );
h ^= ( h >> 11 );
h += ( h << 15 );
return h;
} else {
for ( ; *key ; ++key ) {
h += *key;
h += ( h << 10 );
h ^= ( h >> 6 );
}
h += ( h << 3 );
h ^= ( h >> 11 );
h += ( h << 15 );
return h;
}
}
| HASH_VALUE HASHFUNCTION_ELF | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
ELF hash.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 164 of file hashfunction.c.
{
HASH_VALUE h = 2166136261U,g;
unsigned char * key = (unsigned char *) keydata;
ssize_t i;
if (key_length != -1) {
for ( i = 0; i < key_length; i++ ) {
h = ( h << 4 ) + key[i];
g = h & 0xf0000000L;
if ( g != 0 )
h ^= g >> 24;
h &= ~g;
}
return h;
} else {
for ( ; *key ;key++ ) {
h = ( h << 4 ) + *key;
g = h & 0xf0000000L;
if ( g != 0 )
h ^= g >> 24;
h &= ~g;
return h;
}
return h;
}
}
| HASH_VALUE HASHFUNCTION_Fowler_Noll_Vo | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
Fowler/Noll/Vo hash.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"Follows the same lines as Bernstein's modified hash with carefully chosen constants"
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 105 of file hashfunction.c.
{
HASH_VALUE hash = 2166136261U;
unsigned char * key = (unsigned char *) keydata;
ssize_t i;
if (key_length != -1) {
for (hash = 0, i=0; i<key_length; ++i) {
hash = ( hash * 16777619U ) ^ key[i];
}
return hash;
} else {
for (hash = 0; *key ; ++key) {
hash = ( hash * 16777619U ) ^ (*key);
}
return hash;
}
}
| HASH_VALUE HASHFUNCTION_PJW | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
P.J. Weinberger hash function.
Source: Compilers Principles Techniques and Tools by Aho,Sethi,Ullman page 436 Good for string keys
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 30 of file hashfunction.c.
{
unsigned char * key = (unsigned char *) keydata;
HASH_VALUE g = 0, hash_val = 0;
if (key_length != -1) {
do {
hash_val = (hash_val<<4) + hash_val + *key++;
g = hash_val & 0xF0000000;
if (g) {
hash_val = hash_val ^ ( g >> 24);
hash_val = hash_val ^ g;
}
key_length --;
} while (key_length != 0);
return hash_val;
} else {
while (*key ) {
hash_val = (hash_val<<4) + hash_val + *key++;
g = hash_val & 0xF0000000;
if (g) {
hash_val = hash_val ^ ( g >> 24);
hash_val = hash_val ^ g;
}
}
return hash_val;
}
}
| HASH_VALUE HASHFUNCTION_rotating | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
Rotating hash.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"Much of the time, the rotating hash is sufficient, and can be considered the minimal acceptable algorithm. Notice that with each improvement, the internal state is being mixed up more and more a key element in a good hash function"
state is being mixed up more and more.
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 62 of file hashfunction.c.
{
HASH_VALUE hash;
unsigned char * key = (unsigned char *) keydata;
ssize_t i;
if (key_length != -1) {
for (hash = key_length, i=0; i<key_length; ++i) {
hash = (hash<<4)^(hash>>28) ^ key[i];
}
return hash;
} else {
for (hash = ((size_t)*key) << 16; *key ; ++key) {
hash = (hash<<4)^(hash>>28) ^ (*key);
}
return hash;
}
}
| HASH_VALUE HASHFUNCTION_sample_hash_func | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
good for most cases.
Source:
| keydata | (in) pointer to key data |
| key_length | (in) the size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Definition at line 7 of file hashfunction.c.
{
unsigned char * key = (unsigned char *) keydata;
HASH_VALUE hash_val = 0;
if (key_length != -1 ) {
do {
hash_val = (hash_val<<5) + hash_val + *key++;
key_length --;
} while (key_length != 0);
return hash_val;
} else {
while (*key ) {
hash_val = (hash_val<<5) + hash_val + *key++;
}
return hash_val;
}
}
| HASH_VALUE HASHFUNCTION_shift_and_xor | ( | void * | keydata, |
| ssize_t | key_length | ||
| ) |
Shift and XOR.
Bernstein hash.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"Very similar to rotating hash. Like many effective hashes, it will fail tests for avalanche, but that does not seem to affect its performance in practice."
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. If value is VHASH_STRING then keydata is treated as null terminated string. |
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"despite that the algorithm itself is not very sound when it comes to avalanche and permutation of the internal state. It has proven very good for small character keys, where it can outperform algorithms that result in a more random distribution: Bernstein's hash should be used with caution. It performs very well in practice, for no apparently known reasons (much like how the constant 33 does better than more logical constants for no apparent reason), but in theory it is not up to snuff. Always test this function with sample data for every application to ensure that it does not encounter a degenerate case and cause excessive collisions."
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. |
Shift and XOR.
Source:
http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx
"despite that the algorithm itself is not very sound when it comes to avalanche and permutation of the internal state. It has proven very good for small character keys, where it can outperform algorithms that result in a more random distribution: Bernstein's hash should be used with caution. It performs very well in practice, for no apparently known reasons (much like how the constant 33 does better than more logical constants for no apparent reason), but in theory it is not up to snuff. Always test this function with sample data for every application to ensure that it does not encounter a degenerate case and cause excessive collisions."
| keydata | (in) pointer to key data |
| key_length | (in) size of key data. |
Definition at line 83 of file hashfunction.c.
{
HASH_VALUE hash;
unsigned char * key = (unsigned char *) keydata;
ssize_t i;
if (key_length != -1) {
for (hash = key_length, i=0; i<key_length; ++i) {
hash ^= (hash<<5) + (hash>>2) + key[i];
}
return hash;
} else {
for (hash = ((size_t)*key) << 16; *key ; ++key) {
hash ^= (hash<<5) + (hash>>2) + (*key);
}
return hash;
}
}
1.7.4