From 58938c980f38a4581b4a0e8a780fffe7ac95bc93 Mon Sep 17 00:00:00 2001 From: Eric Wong Date: Fri, 26 Nov 2010 02:27:17 +0000 Subject: initial --- ext/tdb/djb.c | 26 ++ ext/tdb/extconf.rb | 12 + ext/tdb/fnv.c | 28 +++ ext/tdb/lookup3.c | 429 +++++++++++++++++++++++++++++++++ ext/tdb/murmur1.c | 151 ++++++++++++ ext/tdb/murmur2.c | 290 +++++++++++++++++++++++ ext/tdb/rbtdb.h | 22 ++ ext/tdb/tdb.c | 679 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 1637 insertions(+) create mode 100644 ext/tdb/djb.c create mode 100644 ext/tdb/extconf.rb create mode 100644 ext/tdb/fnv.c create mode 100644 ext/tdb/lookup3.c create mode 100644 ext/tdb/murmur1.c create mode 100644 ext/tdb/murmur2.c create mode 100644 ext/tdb/rbtdb.h create mode 100644 ext/tdb/tdb.c (limited to 'ext') diff --git a/ext/tdb/djb.c b/ext/tdb/djb.c new file mode 100644 index 0000000..83abe34 --- /dev/null +++ b/ext/tdb/djb.c @@ -0,0 +1,26 @@ +#include "rbtdb.h" + +unsigned int rbtdb_djb2(TDB_DATA *data) +{ + unsigned char *key = data->dptr; + size_t len = data->dsize; + unsigned int hash = 5381; + unsigned int i; + + for (i = 0; i < len; ++i) + hash = ((hash << 5) + hash) + key[i]; /* (hash*33) + key[i] */ + + return hash; +} +unsigned int rbtdb_djb3(TDB_DATA *data) +{ + unsigned char *key = data->dptr; + size_t len = data->dsize; + unsigned int hash = 5381; + unsigned int i; + + for (i = 0; i < len; ++i) + hash = ((hash << 5) + hash) ^ key[i]; /* (hash*33) ^ key[i] */ + + return hash; +} diff --git a/ext/tdb/extconf.rb b/ext/tdb/extconf.rb new file mode 100644 index 0000000..32adafe --- /dev/null +++ b/ext/tdb/extconf.rb @@ -0,0 +1,12 @@ +require 'mkmf' + +have_func('rb_thread_blocking_region') +have_func('rb_thread_call_with_gvl') + +dir_config('tdb') +have_header('tdb.h') or abort 'tdb.h missing' +have_library('tdb') or abort 'libtdb missing' +have_func('tdb_jenkins_hash') +have_const('TDB_ERR_NESTING', 'tdb.h') + +create_makefile('tdb_ext') diff --git a/ext/tdb/fnv.c b/ext/tdb/fnv.c new file mode 100644 index 0000000..769a3d7 --- /dev/null +++ b/ext/tdb/fnv.c @@ -0,0 +1,28 @@ +#include "rbtdb.h" + +#define FNV1A_32A_INIT (unsigned int)0x811c9dc5 +#define FNV_32_PRIME (unsigned int)0x01000193 + +unsigned int rbtdb_fnv1a(TDB_DATA * data) +{ + unsigned char *bp = data->dptr; + unsigned char *be = bp + data->dsize; + unsigned int h = FNV1A_32A_INIT; + + /* FNV-1a hash each octet in the buffer */ + while (bp < be) { + + /* xor the bottom with the current octet */ + h ^= (unsigned)*bp++; + + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + h *= FNV_32_PRIME; +#else + h += (h << 1) + (h << 4) + (h << 7) + (h << 8) + (h << 24); +#endif + } + + /* return our new hash value */ + return h; +} diff --git a/ext/tdb/lookup3.c b/ext/tdb/lookup3.c new file mode 100644 index 0000000..23a9088 --- /dev/null +++ b/ext/tdb/lookup3.c @@ -0,0 +1,429 @@ +#include "rbtdb.h" + +/* + * lookup3 implementation copied from tdb.git + * (commit 3258cf3f11bf7c68a2e69e1808c4551cc899725a), + * as that tdb distribution isn't commonly available yet (as of 2010.11.29) + */ +#ifndef HAVE_TDB_JENKINS_HASH + +#ifndef WORDS_BIGENDIAN +# define HASH_LITTLE_ENDIAN 1 +# define HASH_BIG_ENDIAN 0 +#else +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 1 +#endif + +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() +are externally useful functions. Routines to test the hash are included +if SELF_TEST is defined. You can use this free for any purpose. It's in +the public domain. It has no warranty. + +You probably want to use hashlittle(). hashlittle() and hashbig() +hash byte arrays. hashlittle() is is faster than hashbig() on +little-endian machines. Intel and AMD are little-endian machines. +On second thought, you probably want hashlittle2(), which is identical to +hashlittle() except it returns two 32-bit hashes for the price of one. +You could implement hashbig2() if you wanted but I haven't bothered here. + +If you want to find a hash of, say, exactly 7 integers, do + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + final(a,b,c); +then use c as the hash value. If you have a variable length array of +4-byte integers to hash, use hash_word(). If you have a byte array (like +a character string), use hashlittle(). If you have several byte arrays, or +a mix of things, see the comments above hashlittle(). + +Why is this so big? I read 12 bytes at a time into 3 4-byte integers, +then mix those integers. This is fast (you can do a lot more thorough +mixing with 12*3 instructions on 3 integers than you can with 3 instructions +on 1 byte), but shoehorning those bytes into integers efficiently is messy. +*/ + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 14 9 3 7 17 3 +Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing +for "differ" defined as + with a one-bit base and a two-bit delta. I +used http://burtleburtle.net/bob/hash/avalanche.html to choose +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +/* +------------------------------------------------------------------------------- +hashlittle() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + val2 : IN: can be any 4-byte value OUT: second 32 bit hash. +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. Note that the return value is better +mixed than val2, so use that first. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. + +If you are hashing n strings (uint8_t **)k, do it like this: + for (i=0, h=0; i 12) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + */ +#ifndef VALGRIND + + switch (length) { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += k[2] & 0xffffff; + b += k[1]; + a += k[0]; + break; + case 10: + c += k[2] & 0xffff; + b += k[1]; + a += k[0]; + break; + case 9: + c += k[2] & 0xff; + b += k[1]; + a += k[0]; + break; + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += k[1] & 0xffffff; + a += k[0]; + break; + case 6: + b += k[1] & 0xffff; + a += k[0]; + break; + case 5: + b += k[1] & 0xff; + a += k[0]; + break; + case 4: + a += k[0]; + break; + case 3: + a += k[0] & 0xffffff; + break; + case 2: + a += k[0] & 0xffff; + break; + case 1: + a += k[0] & 0xff; + break; + case 0: + return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch (length) { + case 12: + c += k[2]; + b += k[1]; + a += k[0]; + break; + case 11: + c += ((uint32_t) k8[10]) << 16; /* fall through */ + case 10: + c += ((uint32_t) k8[9]) << 8; /* fall through */ + case 9: + c += k8[8]; /* fall through */ + case 8: + b += k[1]; + a += k[0]; + break; + case 7: + b += ((uint32_t) k8[6]) << 16; /* fall through */ + case 6: + b += ((uint32_t) k8[5]) << 8; /* fall through */ + case 5: + b += k8[4]; /* fall through */ + case 4: + a += k[0]; + break; + case 3: + a += ((uint32_t) k8[2]) << 16; /* fall through */ + case 2: + a += ((uint32_t) k8[1]) << 8; /* fall through */ + case 1: + a += k8[0]; + break; + case 0: + return c; + } + +#endif /* !valgrind */ + + } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) { + a += k[0] + (((uint32_t) k[1]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + c += k[4] + (((uint32_t) k[5]) << 16); + mix(a, b, c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch (length) { + case 12: + c += k[4] + (((uint32_t) k[5]) << 16); + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 11: + c += ((uint32_t) k8[10]) << 16; /* fall through */ + case 10: + c += k[4]; + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 9: + c += k8[8]; /* fall through */ + case 8: + b += k[2] + (((uint32_t) k[3]) << 16); + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 7: + b += ((uint32_t) k8[6]) << 16; /* fall through */ + case 6: + b += k[2]; + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 5: + b += k8[4]; /* fall through */ + case 4: + a += k[0] + (((uint32_t) k[1]) << 16); + break; + case 3: + a += ((uint32_t) k8[2]) << 16; /* fall through */ + case 2: + a += k[0]; + break; + case 1: + a += k8[0]; + break; + case 0: + return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) { + a += k[0]; + a += ((uint32_t) k[1]) << 8; + a += ((uint32_t) k[2]) << 16; + a += ((uint32_t) k[3]) << 24; + b += k[4]; + b += ((uint32_t) k[5]) << 8; + b += ((uint32_t) k[6]) << 16; + b += ((uint32_t) k[7]) << 24; + c += k[8]; + c += ((uint32_t) k[9]) << 8; + c += ((uint32_t) k[10]) << 16; + c += ((uint32_t) k[11]) << 24; + mix(a, b, c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch (length) { /* all the case statements fall through */ + case 12: + c += ((uint32_t) k[11]) << 24; + case 11: + c += ((uint32_t) k[10]) << 16; + case 10: + c += ((uint32_t) k[9]) << 8; + case 9: + c += k[8]; + case 8: + b += ((uint32_t) k[7]) << 24; + case 7: + b += ((uint32_t) k[6]) << 16; + case 6: + b += ((uint32_t) k[5]) << 8; + case 5: + b += k[4]; + case 4: + a += ((uint32_t) k[3]) << 24; + case 3: + a += ((uint32_t) k[2]) << 16; + case 2: + a += ((uint32_t) k[1]) << 8; + case 1: + a += k[0]; + break; + case 0: + return c; + } + } + + final(a, b, c); + return c; +} + +unsigned int rbtdb_jenkins_lookup3(TDB_DATA * key) +{ + return hashlittle(key->dptr, key->dsize); +} +#endif /* !HAVE_TDB_JENKINS_HASH */ diff --git a/ext/tdb/murmur1.c b/ext/tdb/murmur1.c new file mode 100644 index 0000000..1880cc6 --- /dev/null +++ b/ext/tdb/murmur1.c @@ -0,0 +1,151 @@ +#include "rbtdb.h" +#include + +/* + * https://sites.google.com/site/murmurhash/ + * + * Public Domain hash functions by Austin Appleby. + * + * Trivially adapted for use with Ruby TDB by Eric Wong. + */ + +/* + * 'm' and 'r' are mixing constants generated offline. + * They're not really 'magic', they just happen to work well. + */ +static const unsigned int m = 0xc6a4a793; +static const int r = 16; +static const unsigned int seed; + +unsigned int rbtdb_murmur1(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + /* Initialize the hash to a 'random' value */ + unsigned int h = seed ^ (len * m); + + while (len >= 4) { + h += *(const unsigned int *)data; + h *= m; + h ^= h >> r; + + data += 4; + len -= 4; + } + + /* Handle the last few bytes of the input array */ + switch (len) { + case 3: + h += data[2] << 16; + case 2: + h += data[1] << 8; + case 1: + h += data[0]; + h *= m; + h ^= h >> r; + }; + + /* + * Do a few final mixes of the hash to ensure the last few + * bytes are well-incorporated. + */ + h *= m; + h ^= h >> 10; + h *= m; + h ^= h >> 17; + + return h; +} + +/* adapted from MurmurHashAligned */ +unsigned int rbtdb_murmur1_aligned(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + unsigned int h = seed ^ (len * m); + union { const unsigned char *byte; int integer; } cast = { data }; + int align = cast.integer & 3; + + if (align & (len >= 4)) { + /* Pre-load the temp registers */ + unsigned int t = 0, d = 0; + int sl, sr, pack; + + switch (align) { + case 1: t |= data[2] << 16; + case 2: t |= data[1] << 8; + case 3: t |= data[0]; + } + + t <<= (8 * align); + + data += 4 - align; + len -= 4 - align; + + sl = 8 * (4 - align); + sr = 8 * align; + + /* Mix */ + while (len >= 4) { + assert((cast.integer & 3) == 0); + + d = *(const unsigned int *)data; + t = (t >> sr) | (d << sl); + h += t; + h *= m; + h ^= h >> r; + t = d; + + data += 4; + len -= 4; + } + + /* Handle leftover data in temp registers */ + pack = len < align ? len : align; + d = 0; + + switch (pack) { + case 3: + d |= data[2] << 16; + case 2: + d |= data[1] << 8; + case 1: + d |= data[0]; + case 0: + h += (t >> sr) | (d << sl); + h *= m; + h ^= h >> r; + } + + data += pack; + len -= pack; + } else { + while (len >= 4) { + h += *(const unsigned int *)data; + h *= m; + h ^= h >> r; + + data += 4; + len -= 4; + } + } + + /* Handle tail bytes */ + switch (len) { + case 3: + h += data[2] << 16; + case 2: + h += data[1] << 8; + case 1: + h += data[0]; + h *= m; + h ^= h >> r; + }; + + h *= m; + h ^= h >> 10; + h *= m; + h ^= h >> 17; + + return h; +} diff --git a/ext/tdb/murmur2.c b/ext/tdb/murmur2.c new file mode 100644 index 0000000..6b6f8a6 --- /dev/null +++ b/ext/tdb/murmur2.c @@ -0,0 +1,290 @@ +#include "rbtdb.h" +/* + * https://sites.google.com/site/murmurhash/ + * + * Public Domain hash functions by Austin Appleby. + * + * Trivially adapted for use with Ruby TDB by Eric Wong. + */ + +/* + * 'm' and 'r' are mixing constants generated offline. + * They're not really 'magic', they just happen to work well. + */ + +static const unsigned int m = 0x5bd1e995; +static const int r = 24; +static const unsigned int seed; + +unsigned int rbtdb_murmur2(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + /* Initialize the hash to a 'random' value */ + unsigned int h = seed ^ len; + + while (len >= 4) { + unsigned int k = *(const unsigned int *)data; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + len -= 4; + } + + /* Handle the last few bytes of the input array */ + switch (len) { + case 3: + h ^= data[2] << 16; + case 2: + h ^= data[1] << 8; + case 1: + h ^= data[0]; + h *= m; + }; + + /* + * Do a few final mixes of the hash to ensure the last few + * bytes are well-incorporated. + */ + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} + +/* + * This is a variant of MurmurHash2 modified to use the Merkle-Damgard + * construction. Bulk speed should be identical to Murmur2, small-key speed + * will be 10%-20% slower due to the added overhead at the end of the hash. + * + * This variant fixes a minor issue where null keys were more likely to + * collide with each other than expected, and also makes the algorithm + * more amenable to incremental implementations. All other caveats from + * MurmurHash2 still apply. + */ + +#define mmix(h,k) do { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } while (0) + +unsigned int rbtdb_murmur2a(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + unsigned int l = (unsigned int)len; + unsigned int h = seed; + unsigned int t = 0; + + while (len >= 4) { + unsigned int k = *(const unsigned int *)data; + + mmix(h, k); + + data += 4; + len -= 4; + } + + switch (len) { + case 3: + t ^= data[2] << 16; + case 2: + t ^= data[1] << 8; + case 1: + t ^= data[0]; + }; + + mmix(h, t); + mmix(h, l); + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} + +/* + * Same algorithm as MurmurHash2, but only does aligned reads - should be safer + * on certain platforms + * + * Performance will be lower than MurmurHash2 + */ + +#define MIX(h,k,m) do { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } while (0) + +unsigned int rbtdb_murmur2_aligned(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + unsigned int h = seed ^ len; + union { const unsigned char *byte; int integer; } cast = { data }; + int align = cast.integer & 3; + + if (align && (len >= 4)) { + /* Pre-load the temp registers */ + unsigned int t = 0, d = 0; + int sl, sr; + + switch (align) { + case 1: + t |= data[2] << 16; + case 2: + t |= data[1] << 8; + case 3: + t |= data[0]; + } + + t <<= (8 * align); + + data += 4 - align; + len -= 4 - align; + + sl = 8 * (4 - align); + sr = 8 * align; + + /* Mix */ + while (len >= 4) { + unsigned int k; + + d = *(const unsigned int *)data; + t = (t >> sr) | (d << sl); + + k = t; + + MIX(h, k, m); + + t = d; + + data += 4; + len -= 4; + } + + /* Handle leftover data in temp registers */ + d = 0; + if (len >= align) { + unsigned int k; + + switch (align) { + case 3: + d |= data[2] << 16; + case 2: + d |= data[1] << 8; + case 1: + d |= data[0]; + } + + k = (t >> sr) | (d << sl); + MIX(h, k, m); + + data += align; + len -= align; + + /* Handle tail bytes */ + switch (len) { + case 3: + h ^= data[2] << 16; + case 2: + h ^= data[1] << 8; + case 1: + h ^= data[0]; + h *= m; + }; + } else { + switch (len) { + case 3: + d |= data[2] << 16; + case 2: + d |= data[1] << 8; + case 1: + d |= data[0]; + case 0: + h ^= (t >> sr) | (d << sl); + h *= m; + } + } + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; + } else { + while (len >= 4) { + unsigned int k = *(const unsigned int *)data; + + MIX(h, k, m); + + data += 4; + len -= 4; + } + + /* Handle tail bytes */ + switch (len) { + case 3: + h ^= data[2] << 16; + case 2: + h ^= data[1] << 8; + case 1: + h ^= data[0]; + h *= m; + }; + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; + } +} + +/* + * Same as MurmurHash2, but endian- and alignment-neutral. + * Half the speed though, alas. + */ +unsigned int rbtdb_murmur2_neutral(TDB_DATA * key) +{ + const unsigned char *data = key->dptr; + int len = (int)key->dsize; + unsigned int h = seed ^ len; + + while (len >= 4) { + unsigned int k; + + k = data[0]; + k |= data[1] << 8; + k |= data[2] << 16; + k |= data[3] << 24; + + k *= m; + k ^= k >> r; + k *= m; + + h *= m; + h ^= k; + + data += 4; + len -= 4; + } + + switch (len) { + case 3: + h ^= data[2] << 16; + case 2: + h ^= data[1] << 8; + case 1: + h ^= data[0]; + h *= m; + }; + + h ^= h >> 13; + h *= m; + h ^= h >> 15; + + return h; +} diff --git a/ext/tdb/rbtdb.h b/ext/tdb/rbtdb.h new file mode 100644 index 0000000..2ddbcd3 --- /dev/null +++ b/ext/tdb/rbtdb.h @@ -0,0 +1,22 @@ +#ifndef RBTDB_H +#define RBTDB_H +#include +#include + +unsigned int rbtdb_murmur1(TDB_DATA *key); +unsigned int rbtdb_murmur1_aligned(TDB_DATA *key); +unsigned int rbtdb_murmur2(TDB_DATA *key); +unsigned int rbtdb_murmur2a(TDB_DATA *key); +unsigned int rbtdb_murmur2_neutral(TDB_DATA *key); +unsigned int rbtdb_murmur2_aligned(TDB_DATA *key); +unsigned int rbtdb_fnv1a(TDB_DATA *key); +unsigned int rbtdb_djb2(TDB_DATA *key); +unsigned int rbtdb_djb3(TDB_DATA *key); +#ifdef HAVE_TDB_JENKINS_HASH +# define rbtdb_jenkins_lookup3 tdb_jenkins_hash +#else +unsigned int rbtdb_jenkins_lookup3(TDB_DATA *key); +#endif +#define rbtdb_default 0 + +#endif /* RBTDB_H */ diff --git a/ext/tdb/tdb.c b/ext/tdb/tdb.c new file mode 100644 index 0000000..cfe7970 --- /dev/null +++ b/ext/tdb/tdb.c @@ -0,0 +1,679 @@ +#include "rbtdb.h" +#include +#include +#include +#include +#ifdef HAVE_RUBY_ST_H +# include +#else +# include +#endif + +static VALUE cTDB, cERR; +static st_table *exc_hash; +static VALUE hashes; + +/* must be a macro to prevent GC from killing converted 'val's */ +#define TO_TDB_DATA(data,val) do { \ + StringValue(val); \ + (data).dptr = (unsigned char *)RSTRING_PTR(val); \ + (data).dsize = RSTRING_LEN(val); \ +} while (0) + +static void init_exc(enum TDB_ERROR ecode, const char *name) +{ + VALUE exc = rb_define_class_under(cERR, name, cERR); + st_insert(exc_hash, (st_data_t)ecode, (st_data_t)exc); +} + +static void init_errors(void) +{ + cERR = rb_define_class_under(cTDB, "ERR", rb_eStandardError); + exc_hash = st_init_numtable(); + + init_exc(TDB_ERR_CORRUPT, "CORRUPT"); + init_exc(TDB_ERR_IO, "IO"); + init_exc(TDB_ERR_LOCK, "LOCK"); + init_exc(TDB_ERR_OOM, "OOM"); + init_exc(TDB_ERR_EXISTS, "EXISTS"), + init_exc(TDB_ERR_NOLOCK, "NOLOCK"); + init_exc(TDB_ERR_LOCK_TIMEOUT, "LOCK_TIMEOUT"); + init_exc(TDB_ERR_EINVAL, "EINVAL"); + init_exc(TDB_ERR_NOEXIST, "NOEXIST"); + init_exc(TDB_ERR_RDONLY, "RDONLY"); +#ifdef HAVE_CONST_TDB_ERR_NESTING + init_exc(TDB_ERR_NESTING, "NESTING"); +#endif /* HAVE_CONST_TDB_ERR_NESTING */ +} + +static void my_raise(struct tdb_context *tdb) +{ + enum TDB_ERROR ecode = tdb_error(tdb); + const char *str = tdb_errorstr(tdb); + VALUE exc; + + switch (ecode) { + case TDB_SUCCESS: + rb_bug("attempted to raise with no error"); + case TDB_ERR_CORRUPT: + case TDB_ERR_IO: + case TDB_ERR_LOCK: + case TDB_ERR_OOM: + case TDB_ERR_EXISTS: + case TDB_ERR_NOLOCK: + case TDB_ERR_LOCK_TIMEOUT: + case TDB_ERR_EINVAL: + case TDB_ERR_NOEXIST: + case TDB_ERR_RDONLY: +#ifdef HAVE_CONST_TDB_ERR_NESTING + case TDB_ERR_NESTING: +#endif /* HAVE_CONST_TDB_ERR_NESTING */ + if (!st_lookup(exc_hash, (st_data_t)ecode, (st_data_t *)&exc)) + rb_bug("no-existent exception: %s\n", str); + } + rb_raise(exc, str); +} + +static void init_hashes(void) +{ +#define HF(x) \ +rb_hash_aset(hashes,ID2SYM(rb_intern(#x)),ULONG2NUM((unsigned long)rbtdb_##x)) + HF(murmur1); + HF(murmur1_aligned); + HF(murmur2); + HF(murmur2a); + HF(murmur2_neutral); + HF(murmur2_aligned); + HF(fnv1a); + HF(djb2); + HF(djb3); + HF(jenkins_lookup3); + HF(default); +} + +#ifndef HAVE_RB_THREAD_BLOCKING_REGION +/* (very) partial emulation of the 1.9 rb_thread_blocking_region under 1.8 */ +# include +typedef VALUE rb_blocking_function_t(void *); +static VALUE my_tbr(rb_blocking_function_t *fn, void *data) +{ + VALUE rv; + + TRAP_BEG; + rv = fn(data); + TRAP_END; + + return rv; +} +#else +static VALUE my_tbr(rb_blocking_function_t *fn, void *data) +{ + return rb_thread_blocking_region(fn, data, RUBY_UBF_IO, 0); +} +#endif /* HAVE_RUBY_THREAD_BLOCKING_REGION */ + +static void gcfree(void *ptr) +{ + struct tdb_context *tdb = ptr; + + if (tdb) + (void)tdb_close(tdb); +} + +static VALUE alloc(VALUE klass) +{ + return Data_Wrap_Struct(klass, NULL, gcfree, NULL); +} + +static struct tdb_context *db(VALUE self, int check_opened) +{ + struct tdb_context *tdb; + + Data_Get_Struct(self, struct tdb_context, tdb); + + if (!tdb && check_opened) + rb_raise(rb_eIOError, "closed database"); + + return tdb; +} + +struct open_args { + const char *name; + int hash_size; + int tdb_flags; + int open_flags; + mode_t mode; + struct tdb_logging_context *log_ctx; + tdb_hash_func hash_fn; +}; + +static VALUE nogvl_open(void *ptr) +{ + struct open_args *o = ptr; + struct tdb_context *tdb; + + tdb = tdb_open_ex(o->name, o->hash_size, o->tdb_flags, + o->open_flags, o->mode, o->log_ctx, o->hash_fn); + + return (VALUE)tdb; +} + +static void set_args(struct open_args *o, VALUE opts) +{ + VALUE tmp; + + o->name = NULL; + o->hash_size = 0; /* default */ + o->tdb_flags = TDB_DEFAULT; + o->open_flags = O_RDWR | O_CREAT; + o->mode = 0666; + o->log_ctx = NULL; + o->hash_fn = NULL; + + if (NIL_P(opts)) + return; + Check_Type(opts, T_HASH); + + tmp = rb_hash_aref(opts, ID2SYM(rb_intern("hash_size"))); + if (!NIL_P(tmp)) + o->hash_size = NUM2INT(tmp); + + tmp = rb_hash_aref(opts, ID2SYM(rb_intern("mode"))); + if (!NIL_P(tmp)) + o->mode = NUM2UINT(tmp); + + tmp = rb_hash_aref(opts, ID2SYM(rb_intern("open_flags"))); + if (!NIL_P(tmp)) + o->open_flags = NUM2INT(tmp); + + tmp = rb_hash_aref(opts, ID2SYM(rb_intern("tdb_flags"))); + if (!NIL_P(tmp)) + o->tdb_flags = NUM2INT(tmp); + + tmp = rb_hash_aref(opts, ID2SYM(rb_intern("hash"))); + if (!NIL_P(tmp)) { + VALUE num = rb_hash_aref(hashes, tmp); + + if (NIL_P(num)) { + tmp = rb_inspect(tmp); + rb_raise(rb_eArgError, + "`%s' is not a valid hash function", + StringValuePtr(tmp)); + } + + o->hash_fn = (tdb_hash_func)NUM2ULONG(num); + } +} + +static VALUE init(int argc, VALUE *argv, VALUE self) +{ + struct tdb_context *tdb = db(self, 0); + VALUE path, opts; + struct open_args o; + + if (tdb) + rb_raise(rb_eRuntimeError, "TDB already initialized"); + rb_scan_args(argc, argv, "11", &path, &opts); + set_args(&o, opts); + + if (NIL_P(path)) + o.tdb_flags |= TDB_INTERNAL; + else + o.name = StringValuePtr(path); + + tdb = (struct tdb_context *)my_tbr(nogvl_open, &o); + if (!tdb) { + switch (errno) { + case ENOMEM: + case EMFILE: + case ENFILE: + rb_gc(); + tdb = (struct tdb_context *)my_tbr(nogvl_open, &o); + } + if (!tdb) + rb_sys_fail("tdb_open_ex"); + } + DATA_PTR(self) = tdb; + + return self; +} + +/* tdb_close can do a lot, including cancel transactions an munmap */ +static VALUE nogvl_close(void *ptr) +{ + struct tdb_context *tdb = ptr; + + return (VALUE)tdb_close(tdb); +} + +static VALUE tdbclose(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + + DATA_PTR(self) = NULL; + + if ((int)my_tbr(nogvl_close, tdb) == -1) + rb_sys_fail("tdb_close"); + + return Qnil; +} + +static VALUE closed(VALUE self) +{ + struct tdb_context *tdb = db(self, 0); + + return tdb ? Qfalse : Qtrue; +} + +#ifdef HAVE_RB_THREAD_CALL_WITH_GVL +/* missing prototype in ruby.h: */ +void *rb_thread_call_with_gvl(void *(*func)(void *), void *data); +#else +static void * my_rb_thread_call_with_gvl(void *(*func)(void *), void *data) +{ + return (*func)(data); +} +#define rb_thread_call_with_gvl my_rb_thread_call_with_gvl +#endif /* !HAVE_RB_THREAD_CALL_WITH_GVL */ + +/* + * We avoid the extra malloc/free pair enforced by tdb_fetch. We + * use tdb_parse_record to give us pointers to (hopefully) mmap-ed + * regions and create a String object directly off that region. + */ +struct fetch_parse_args { + struct tdb_context *tdb; + union { + TDB_DATA key; + TDB_DATA val; + } as; + VALUE value; +}; + +static VALUE str_new_tdb_data(TDB_DATA *val) +{ + return rb_str_new((const char *)val->dptr, val->dsize); +} + +static void *gvl_str_new(void *data) +{ + struct fetch_parse_args *f = data; + + f->value = str_new_tdb_data(&f->as.val); + + return NULL; +} + +static int fetch_parse(TDB_DATA key, TDB_DATA val, void *data) +{ + struct fetch_parse_args *f = data; + + f->as.val = val; + (void)rb_thread_call_with_gvl(gvl_str_new, data); + + return 0; +} + +static VALUE nogvl_parse_record(void *ptr) +{ + struct fetch_parse_args *f = ptr; + + if (tdb_parse_record(f->tdb, f->as.key, fetch_parse, ptr) == -1) + return Qnil; + + return f->value; +} + +static VALUE fetch(VALUE self, VALUE key) +{ + struct fetch_parse_args f; + + f.tdb = db(self, 1); + TO_TDB_DATA(f.as.key, key); + f.value = Qnil; + + return my_tbr(nogvl_parse_record, &f); +} + +struct store_args { + struct tdb_context *tdb; + TDB_DATA key; + TDB_DATA val; + int flag; +}; + +static VALUE nogvl_store(void *ptr) +{ + struct store_args *s = ptr; + + return (VALUE)tdb_store(s->tdb, s->key, s->val, s->flag); +} + +static VALUE rbtdb_store(VALUE self, VALUE key, VALUE val, int flag, int soft) +{ + struct store_args s; + + s.tdb = db(self, 1); + TO_TDB_DATA(s.key, key); + TO_TDB_DATA(s.val, val); + s.flag = flag; + + if ((int)my_tbr(nogvl_store, &s) == -1) { + if (soft) { + int ecode = tdb_error(s.tdb); + + if ((flag == TDB_INSERT) && (ecode == TDB_ERR_EXISTS)) + return Qnil; + if ((flag == TDB_MODIFY) && (ecode == TDB_ERR_NOEXIST)) + return Qnil; + } + my_raise(s.tdb); + } + + return val; +} + +static VALUE store(VALUE self, VALUE key, VALUE val) +{ + return rbtdb_store(self, key, val, 0, 0); +} + +static VALUE insert_bang(VALUE self, VALUE key, VALUE val) +{ + return rbtdb_store(self, key, val, TDB_INSERT, 0); +} + +static VALUE insert(VALUE self, VALUE key, VALUE val) +{ + return rbtdb_store(self, key, val, TDB_INSERT, 1); +} + +static VALUE modify_bang(VALUE self, VALUE key, VALUE val) +{ + return rbtdb_store(self, key, val, TDB_MODIFY, 0); +} + +static VALUE modify(VALUE self, VALUE key, VALUE val) +{ + return rbtdb_store(self, key, val, TDB_MODIFY, 1); +} + +struct exists_args { + struct tdb_context *tdb; + TDB_DATA key; +}; + +static VALUE nogvl_exists(void *ptr) +{ + struct exists_args *e = ptr; + + return tdb_exists(e->tdb, e->key) == 0 ? Qfalse : Qtrue; +} + +static VALUE has_key(VALUE self, VALUE key) +{ + struct exists_args e; + + e.tdb = db(self, 1); + TO_TDB_DATA(e.key, key); + + return my_tbr(nogvl_exists, &e); +} + +struct traverse_args { + struct tdb_context *tdb; + TDB_DATA key; + TDB_DATA val; + int state; +}; + +static VALUE protected_yield(VALUE val) +{ + VALUE *kv = (VALUE *)val; + + return rb_yield_values(2, kv[0], kv[1]); +} + +static void *my_yield(void *data) +{ + struct traverse_args *t = data; + VALUE kv[2]; + + kv[0] = str_new_tdb_data(&t->key); + kv[1] = str_new_tdb_data(&t->val); + + rb_protect(protected_yield, (VALUE)kv, &t->state); + + return NULL; +} + +static int +traverse_fn(struct tdb_context *tdb, TDB_DATA key, TDB_DATA val, void *data) +{ + struct traverse_args *t = data; + + t->key = key; + t->val = val; + (void)rb_thread_call_with_gvl(my_yield, t); + + return t->state; +} + +static VALUE nogvl_traverse(void *ptr) +{ + struct traverse_args *t = ptr; + + (void)tdb_traverse(t->tdb, traverse_fn, t); + + return Qfalse; +} + +static VALUE each(VALUE self) +{ + struct traverse_args t; + + t.tdb = db(self, 1); + t.state = 0; + + my_tbr(nogvl_traverse, &t); + if (t.state) + rb_jump_tag(t.state); + return self; +} + +struct delete_args { + struct tdb_context *tdb; + TDB_DATA key; +}; + +static VALUE nogvl_delete(void *ptr) +{ + struct delete_args *d = ptr; + + return tdb_delete(d->tdb, d->key) == 0 ? Qtrue : Qfalse; +} + +static VALUE nuke(VALUE self, VALUE key) +{ + struct delete_args d; + + d.tdb = db(self, 1); + TO_TDB_DATA(d.key, key); + + return my_tbr(nogvl_delete, &d); +} + +static VALUE delete(VALUE self, VALUE key) +{ + VALUE rc = fetch(self, key); + + if (! NIL_P(rc)) + if (nuke(self, key) == Qfalse) + return Qnil; + return rc; +} + +static VALUE lockall(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_lockall, tdb)) + my_raise(tdb); + + return Qtrue; +} + +static VALUE trylockall(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + void *fn = tdb_lockall_nonblock; + + if ((int)my_tbr((rb_blocking_function_t *)fn, tdb)) { + if (tdb_error(tdb) == TDB_ERR_LOCK) + return Qfalse; + my_raise(tdb); + } + return Qtrue; +} + +static VALUE unlockall(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_unlockall, tdb)) + my_raise(tdb); + return Qtrue; +} + +static VALUE lockall_read(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_lockall_read, tdb)) + my_raise(tdb); + return Qtrue; +} + +static VALUE trylockall_read(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + void *fn = tdb_lockall_read_nonblock; + if ((int)my_tbr((rb_blocking_function_t *)fn, tdb)) { + if (tdb_error(tdb) == TDB_ERR_LOCK) + return Qfalse; + my_raise(tdb); + } + return Qtrue; +} + +static VALUE unlockall_read(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_unlockall_read, tdb)) + my_raise(tdb); + return Qtrue; +} + +static VALUE lockall_mark(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_lockall_mark, tdb)) + my_raise(tdb); + return Qtrue; +} + +static VALUE lockall_unmark(VALUE self) +{ + struct tdb_context *tdb = db(self, 1); + if ((int)my_tbr((rb_blocking_function_t *)tdb_lockall_unmark, tdb)) + my_raise(tdb); + return Qtrue; +} + +void Init_tdb_ext(void) +{ + cTDB = rb_define_class("TDB", rb_cObject); + + hashes = rb_hash_new(); + rb_define_const(cTDB, "HASHES", hashes); + + rb_define_alloc_func(cTDB, alloc); + rb_include_module(cTDB, rb_mEnumerable); + + rb_define_method(cTDB, "initialize", init, -1); + rb_define_method(cTDB, "close", tdbclose, 0); + rb_define_method(cTDB, "closed?", closed, 0); + + rb_define_method(cTDB, "fetch", fetch, 1); + rb_define_method(cTDB, "[]", fetch, 1); + rb_define_method(cTDB, "store", store, 2); + rb_define_method(cTDB, "[]=", store, 2); + rb_define_method(cTDB, "insert!", insert_bang, 2); + rb_define_method(cTDB, "modify!", modify_bang, 2); + rb_define_method(cTDB, "insert", insert, 2); + rb_define_method(cTDB, "modify", modify, 2); + + rb_define_method(cTDB, "key?", has_key, 1); + rb_define_method(cTDB, "has_key?", has_key, 1); + rb_define_method(cTDB, "include?", has_key, 1); + rb_define_method(cTDB, "member?", has_key, 1); + rb_define_method(cTDB, "each", each, 0); + rb_define_method(cTDB, "nuke!", nuke, 1); + rb_define_method(cTDB, "delete", delete, 1); + + rb_define_method(cTDB, "lockall", lockall, 0); + rb_define_method(cTDB, "trylockall", trylockall, 0); + rb_define_method(cTDB, "unlockall", unlockall, 0); + rb_define_method(cTDB, "lockall_read", lockall_read, 0); + rb_define_method(cTDB, "trylockall_read", trylockall_read, 0); + rb_define_method(cTDB, "unlockall_read", unlockall_read, 0); + rb_define_method(cTDB, "lockall_mark", lockall_mark, 0); + rb_define_method(cTDB, "lockall_unmark", lockall_unmark, 0); + + init_errors(); + init_hashes(); + +#define tdb_CONST(x) rb_define_const(cTDB, #x, UINT2NUM(TDB_##x)) + + /* just a readability place holder */ + tdb_CONST(DEFAULT); + + /* clear database if we are the only one with it open */ + tdb_CONST(CLEAR_IF_FIRST); + + /* don't store on disk, use in-memory database */ + tdb_CONST(INTERNAL); + + /* don't do any locking */ + tdb_CONST(NOLOCK); + + /* don't use mmap */ + tdb_CONST(NOMMAP); + + /* convert endian (internal use) */ + tdb_CONST(CONVERT); + + /* header is big-endian (internal use) */ + tdb_CONST(BIGENDIAN); + + /* don't use synchronous transactions */ + tdb_CONST(NOSYNC); + + /* maintain a sequence number */ + tdb_CONST(SEQNUM); + + /* Activate the per-hashchain freelist, default 5 */ + tdb_CONST(VOLATILE); + +#ifdef TDB_ALLOW_NESTING + /* Allow transactions to nest */ + tdb_CONST(ALLOW_NESTING); +#endif + +#ifdef TDB_DISALLOW_NESTING + /* Disallow transactions to nest */ + tdb_CONST(DISALLOW_NESTING); +#endif + +#ifdef TDB_INCOMPATIBLE_HASH + /* Better hashing: can't be opened by tdb < 1.2.6. */ + tdb_CONST(INCOMPATIBLE_HASH); +#endif +} -- cgit v1.2.3-24-ge0c7