00001 /* -*- mode:C++; c-basic-offset:4 -*- 00002 Shore-MT -- Multi-threaded port of the SHORE storage manager 00003 00004 Copyright (c) 2007-2009 00005 Data Intensive Applications and Systems Labaratory (DIAS) 00006 Ecole Polytechnique Federale de Lausanne 00007 00008 All Rights Reserved. 00009 00010 Permission to use, copy, modify and distribute this software and 00011 its documentation is hereby granted, provided that both the 00012 copyright notice and this permission notice appear in all copies of 00013 the software, derivative works or modified versions, and any 00014 portions thereof, and that both notices appear in supporting 00015 documentation. 00016 00017 This code is distributed in the hope that it will be useful, but 00018 WITHOUT ANY WARRANTY; without even the implied warranty of 00019 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS 00020 DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER 00021 RESULTING FROM THE USE OF THIS SOFTWARE. 00022 */ 00023 00024 /*<std-header orig-src='shore' incl-file-exclusion='W_RC_H'> 00025 00026 $Id: w_hashing.h,v 1.2 2010/05/26 01:20:25 nhall Exp $ 00027 00028 SHORE -- Scalable Heterogeneous Object REpository 00029 00030 Copyright (c) 1994-99 Computer Sciences Department, University of 00031 Wisconsin -- Madison 00032 All Rights Reserved. 00033 00034 Permission to use, copy, modify and distribute this software and its 00035 documentation is hereby granted, provided that both the copyright 00036 notice and this permission notice appear in all copies of the 00037 software, derivative works or modified versions, and any portions 00038 thereof, and that both notices appear in supporting documentation. 00039 00040 THE AUTHORS AND THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY 00041 OF WISCONSIN - MADISON ALLOW FREE USE OF THIS SOFTWARE IN ITS 00042 "AS IS" CONDITION, AND THEY DISCLAIM ANY LIABILITY OF ANY KIND 00043 FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE. 00044 00045 This software was developed with support by the Advanced Research 00046 Project Agency, ARPA order number 018 (formerly 8230), monitored by 00047 the U.S. Army Research Laboratory under contract DAAB07-91-C-Q518. 00048 Further funding for this work was provided by DARPA through 00049 Rome Research Laboratory Contract No. F30602-97-2-0247. 00050 00051 */ 00052 00053 #include "w_defines.h" 00054 00055 /* -- do not edit anything above this line -- </std-header>*/ 00056 00057 #ifndef W_CUCKOOHASHFUNCS_H 00058 #define W_CUCKOOHASHFUNCS_H 00059 00060 /** \brief A namespace to contain types related to hashing. 00061 */ 00062 namespace w_hashing { 00063 00064 /** \brief A "universal hash" class based on a random-number generator. 00065 * \details 00066 * Helper class for other hashing classes. 00067 */ 00068 class uhash 00069 { 00070 public: 00071 /*!Members a and b are public only for the 00072 * purpose of compiling test programs */ 00073 typedef w_base_t::uint8_t u64; 00074 u64 a; 00075 u64 b; 00076 private: 00077 static const int bitshift= 16; 00078 static u64 init() 00079 { 00080 return ((u64) sthread_t::rand() << 32) | sthread_t::rand(); 00081 } 00082 public: 00083 /// Initializes with two random numbers. 00084 uhash() : a(init()), b(init()) { } 00085 ~uhash() { } 00086 /// Returns a hash of the argument. 00087 u64 operator()(u64 x) const { return (a*x+b) >> bitshift; } 00088 }; 00089 00090 /* Note from FRJ re: conversation with Ken Ross: 00091 Oh, and he said the best way to use a multiplicative hash 00092 is: h(x) = (a*x+b)>>16. Apparently bits 16-31 are the best, 00093 but bits 32-47 are still far better than 0-15 or 48-63. 00094 */ 00095 00096 00097 /**\brief Wrapper for uhash. 00098 * \details 00099 * A hash class. The operator() is the 00100 * hash function. It uses two "universal" 00101 * random-number-based hash functions to produce the 00102 * hash value. 00103 */ 00104 class hash2 { 00105 public: 00106 /*!Members a and b are public only for the 00107 * purpose of compiling test programs */ 00108 uhash a; 00109 uhash b; 00110 public: 00111 #ifdef ARCH_LP64 00112 unsigned operator()(unsigned x) const { return a(x) ^ b(x); } 00113 #else 00114 w_base_t::uint8_t operator()(unsigned x) const { 00115 return w_base_t::uint8_t (a(x) ^ b(x)); } 00116 #endif 00117 }; 00118 00119 } /* namespace w_hashing */ 00120 00121 #endif