|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72332 - in sandbox/bloom_filter/trunk: boost/bloom_filter boost/bloom_filter/hash boost/bloom_filter/murmurhash3 libs/bloom_filter/test
From: cpp.cabrera_at_[hidden]
Date: 2011-06-01 12:32:23
Author: alejandro
Date: 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
New Revision: 72332
URL: http://svn.boost.org/trac/boost/changeset/72332
Log:
Restructured hashing functions. Will separate distinct implementations into separate header files, so that users need only use the implementations that are relevant to them.
Added:
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/hash.hpp (contents, props changed)
- copied, changed from r72326, /sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp (contents, props changed)
- copied, changed from r72326, /sandbox/bloom_filter/trunk/boost/bloom_filter/murmurhash3/murmurhash3.h
Removed:
sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp
sandbox/bloom_filter/trunk/boost/bloom_filter/murmurhash3/murmurhash3.h
Text files modified:
sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp | 2 +-
sandbox/bloom_filter/trunk/boost/bloom_filter/hash/hash.hpp | 2 +-
sandbox/bloom_filter/trunk/libs/bloom_filter/test/murmurhash3.cpp | 2 +-
3 files changed, 3 insertions(+), 3 deletions(-)
Modified: sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/bloom.hpp 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
@@ -23,7 +23,7 @@
#include <boost/mpl/size.hpp>
#include <boost/bloom_filter/detail/apply_hash.hpp>
-#include <boost/bloom_filter/hash.hpp>
+#include <boost/bloom_filter/hash/hash.hpp>
namespace boost {
template <typename T,
Deleted: sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
+++ (empty file)
@@ -1,145 +0,0 @@
-//////////////////////////////////////////////////////////////////////////////
-//
-// (C) Copyright Alejandro Cabrera 2011.
-// Distributed under the Boost
-// Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or
-// copy at http://www.boost.org/LICENSE_1_0.txt)
-//
-// See http://www.boost.org/libs/bloom_filter for documentation.
-//
-//////////////////////////////////////////////////////////////////////////////
-#ifndef BOOST_BLOOM_FILTER_HASH_HPP_
-#define BOOST_BLOOM_FILTER_HASH_HPP_ 1
-/**
- * \author Alejandro Cabrera
- * \brief An alternative implentation of murmurhash3 for users
- * not wishing to rely on the public domain Murmurhash3.
- * \todo Hash many more collisions than public domain version of murmurhash3.
- * \todo Provide 64-bit implementation of murmurhash3.
- */
-#include <cstdint>
-
-#include <boost/functional/hash.hpp>
-
-#include <boost/bloom_filter/murmurhash3/murmurhash3.h>
-
-#include <iostream>
-
-template <typename UnsignedIntT>
-inline UnsignedIntT rotl(const UnsignedIntT x, uint8_t r)
-{
- return (x << r) | (x >> (sizeof(UnsignedIntT) * 4 - r));
-}
-
-inline uint32_t rotl32(const uint32_t x, uint8_t r)
-{
- return rotl<uint32_t>(x,r);
-}
-
-inline uint64_t rotl64(const uint64_t x, uint8_t r)
-{
- return rotl<uint64_t>(x,r);
-}
-
-template <typename UnsignedIntT>
-inline UnsignedIntT get_block(const UnsignedIntT * p, const int i)
-{
- return p[i];
-}
-
-inline uint32_t fmix(uint32_t h)
-{
- h ^= h >> 16;
- h *= 0x85ebca6b;
- h ^= h >> 13;
- h *= 0xc2b2ae35;
- h ^= h >> 16;
-
- return h;
-}
-
-void murmurhash3(const void *const key, const int len,
- const uint32_t seed, void *out)
-{
- static const uint32_t c1 = 0xcc9e2d51;
- static const uint32_t c2 = 0x1b873593;
-
- const uint8_t *const data = static_cast<const uint8_t *const>(key);
-
- uint32_t h1 = seed;
- const uint32_t *const blocks =
- reinterpret_cast<const uint32_t *const >(data + len);
-
- for (int i = -(len/4); i; ++i) {
- uint32_t k1 = blocks[i];
-
- k1 *= c1;
- k1 = rotl32(k1, 15);
- k1 *= c2;
-
- h1 ^= k1;
- h1 = rotl32(h1, 13);
- h1 = h1*5 + 0xe6546b64;
- }
-
- const uint8_t *const tail =
- static_cast<const uint8_t *const>(data + len);
-
- uint32_t k1 = 0;
-
- switch (len & 3) {
- case 3:
- k1 ^= tail[2] << 16;
- case 2:
- k1 ^= tail[1] << 8;
- case 1:
- k1 ^= tail[0];
- k1 *= c1;
- k1 = rotl32(k1, 16);
- k1 *= c2;
- h1 ^= k1;
- }
-
- h1 ^= len;
- h1 = fmix(h1);
-
- *static_cast<uint32_t *>(out) = h1;
-}
-
-template <typename T, size_t Seed>
-struct MurmurHash3 {
- size_t operator()(const T& t) {
- size_t out = 0;
- murmurhash3(static_cast<const void *const>(&t),
- sizeof(t),
- Seed,
- &out);
- return out;
- }
-};
-
-// uses public domain implementation of murmurhash3
-template <typename T, size_t Seed>
-struct OHash {
- size_t operator()(const T& t) {
- size_t out = 0;
- MurmurHash3_x86_32(static_cast<const void *const>(&t),
- sizeof(t),
- Seed,
- &out);
- return out;
- }
-};
-
-namespace boost {
- template <typename T, size_t Seed>
- struct BoostHash {
- size_t operator()(const T& t) {
- size_t seed = Seed;
- boost::hash_combine(seed, t);
- return seed;
- }
- };
-}
-#endif
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/hash/hash.hpp (from r72326, /sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp)
==============================================================================
--- /sandbox/bloom_filter/trunk/boost/bloom_filter/hash.hpp (original)
+++ sandbox/bloom_filter/trunk/boost/bloom_filter/hash/hash.hpp 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
@@ -22,7 +22,7 @@
#include <boost/functional/hash.hpp>
-#include <boost/bloom_filter/murmurhash3/murmurhash3.h>
+#include <boost/bloom_filter/hash/murmurhash3.hpp>
#include <iostream>
Copied: sandbox/bloom_filter/trunk/boost/bloom_filter/hash/murmurhash3.hpp (from r72326, /sandbox/bloom_filter/trunk/boost/bloom_filter/murmurhash3/murmurhash3.h)
==============================================================================
Deleted: sandbox/bloom_filter/trunk/boost/bloom_filter/murmurhash3/murmurhash3.h
==============================================================================
--- sandbox/bloom_filter/trunk/boost/bloom_filter/murmurhash3/murmurhash3.h 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
+++ (empty file)
@@ -1,37 +0,0 @@
-//-----------------------------------------------------------------------------
-// MurmurHash3 was written by Austin Appleby, and is placed in the public
-// domain. The author hereby disclaims copyright to this source code.
-
-#ifndef _MURMURHASH3_H_
-#define _MURMURHASH3_H_
-
-//-----------------------------------------------------------------------------
-// Platform-specific functions and macros
-
-// Microsoft Visual Studio
-
-#if defined(_MSC_VER)
-
-typedef unsigned char uint8_t;
-typedef unsigned long uint32_t;
-typedef unsigned __int64 uint64_t;
-
-// Other compilers
-
-#else // defined(_MSC_VER)
-
-#include <stdint.h>
-
-#endif // !defined(_MSC_VER)
-
-//-----------------------------------------------------------------------------
-
-void MurmurHash3_x86_32 ( const void * key, int len, uint32_t seed, void * out );
-
-void MurmurHash3_x86_128 ( const void * key, int len, uint32_t seed, void * out );
-
-void MurmurHash3_x64_128 ( const void * key, int len, uint32_t seed, void * out );
-
-//-----------------------------------------------------------------------------
-
-#endif // _MURMURHASH3_H_
Modified: sandbox/bloom_filter/trunk/libs/bloom_filter/test/murmurhash3.cpp
==============================================================================
--- sandbox/bloom_filter/trunk/libs/bloom_filter/test/murmurhash3.cpp (original)
+++ sandbox/bloom_filter/trunk/libs/bloom_filter/test/murmurhash3.cpp 2011-06-01 12:32:19 EDT (Wed, 01 Jun 2011)
@@ -7,7 +7,7 @@
// compile and run any of them on any platform, but your performance with the
// non-native version will be less than optimal.
-#include <boost/bloom_filter/murmurhash3/murmurhash3.h>
+#include <boost/bloom_filter/hash/murmurhash3.hpp>
//-----------------------------------------------------------------------------
// Platform-specific functions and macros
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk