Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/hash.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
rev   line source
jpayne@69 1 // Copyright (c) 2018 Kenton Varda and contributors
jpayne@69 2 // Licensed under the MIT License:
jpayne@69 3 //
jpayne@69 4 // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69 5 // of this software and associated documentation files (the "Software"), to deal
jpayne@69 6 // in the Software without restriction, including without limitation the rights
jpayne@69 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69 8 // copies of the Software, and to permit persons to whom the Software is
jpayne@69 9 // furnished to do so, subject to the following conditions:
jpayne@69 10 //
jpayne@69 11 // The above copyright notice and this permission notice shall be included in
jpayne@69 12 // all copies or substantial portions of the Software.
jpayne@69 13 //
jpayne@69 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69 20 // THE SOFTWARE.
jpayne@69 21
jpayne@69 22 #pragma once
jpayne@69 23
jpayne@69 24 #include "string.h"
jpayne@69 25
jpayne@69 26 KJ_BEGIN_HEADER
jpayne@69 27
jpayne@69 28 namespace kj {
jpayne@69 29 namespace _ { // private
jpayne@69 30
jpayne@69 31 struct HashCoder {
jpayne@69 32 // This is a dummy type with only one instance: HASHCODER (below). To make an arbitrary type
jpayne@69 33 // hashable, define `operator*(HashCoder, T)` to return any other type that is already hashable.
jpayne@69 34 // Be sure to declare the operator in the same namespace as `T` **or** in the global scope.
jpayne@69 35 // You can use the KJ_HASHCODE() macro as syntax sugar for this.
jpayne@69 36 //
jpayne@69 37 // A more usual way to accomplish what we're doing here would be to require that you define
jpayne@69 38 // a function like `hashCode(T)` and then rely on argument-dependent lookup. However, this has
jpayne@69 39 // the problem that it pollutes other people's namespaces and even the global namespace. For
jpayne@69 40 // example, some other project may already have functions called `hashCode` which do something
jpayne@69 41 // different. Declaring `operator*` with `HashCoder` as the left operand cannot conflict with
jpayne@69 42 // anything.
jpayne@69 43
jpayne@69 44 uint operator*(ArrayPtr<const byte> s) const;
jpayne@69 45 inline uint operator*(ArrayPtr<byte> s) const { return operator*(s.asConst()); }
jpayne@69 46
jpayne@69 47 inline uint operator*(ArrayPtr<const char> s) const { return operator*(s.asBytes()); }
jpayne@69 48 inline uint operator*(ArrayPtr<char> s) const { return operator*(s.asBytes()); }
jpayne@69 49 inline uint operator*(const Array<const char>& s) const { return operator*(s.asBytes()); }
jpayne@69 50 inline uint operator*(const Array<char>& s) const { return operator*(s.asBytes()); }
jpayne@69 51 inline uint operator*(const String& s) const { return operator*(s.asBytes()); }
jpayne@69 52 inline uint operator*(const StringPtr& s) const { return operator*(s.asBytes()); }
jpayne@69 53 inline uint operator*(const ConstString& s) const { return operator*(s.asBytes()); }
jpayne@69 54
jpayne@69 55 inline uint operator*(decltype(nullptr)) const { return 0; }
jpayne@69 56 inline uint operator*(bool b) const { return b; }
jpayne@69 57 inline uint operator*(char i) const { return i; }
jpayne@69 58 inline uint operator*(signed char i) const { return i; }
jpayne@69 59 inline uint operator*(unsigned char i) const { return i; }
jpayne@69 60 inline uint operator*(signed short i) const { return i; }
jpayne@69 61 inline uint operator*(unsigned short i) const { return i; }
jpayne@69 62 inline uint operator*(signed int i) const { return i; }
jpayne@69 63 inline uint operator*(unsigned int i) const { return i; }
jpayne@69 64
jpayne@69 65 inline uint operator*(signed long i) const {
jpayne@69 66 if (sizeof(i) == sizeof(uint)) {
jpayne@69 67 return operator*(static_cast<uint>(i));
jpayne@69 68 } else {
jpayne@69 69 return operator*(static_cast<unsigned long long>(i));
jpayne@69 70 }
jpayne@69 71 }
jpayne@69 72 inline uint operator*(unsigned long i) const {
jpayne@69 73 if (sizeof(i) == sizeof(uint)) {
jpayne@69 74 return operator*(static_cast<uint>(i));
jpayne@69 75 } else {
jpayne@69 76 return operator*(static_cast<unsigned long long>(i));
jpayne@69 77 }
jpayne@69 78 }
jpayne@69 79 inline uint operator*(signed long long i) const {
jpayne@69 80 return operator*(static_cast<unsigned long long>(i));
jpayne@69 81 }
jpayne@69 82 inline uint operator*(unsigned long long i) const {
jpayne@69 83 // Mix 64 bits to 32 bits in such a way that if our input values differ primarily in the upper
jpayne@69 84 // 32 bits, we still get good diffusion. (I.e. we cannot just truncate!)
jpayne@69 85 //
jpayne@69 86 // 49123 is an arbitrarily-chosen prime that is vaguely close to 2^16.
jpayne@69 87 //
jpayne@69 88 // TODO(perf): I just made this up. Is it OK?
jpayne@69 89 return static_cast<uint>(i) + static_cast<uint>(i >> 32) * 49123;
jpayne@69 90 }
jpayne@69 91
jpayne@69 92 template <typename T>
jpayne@69 93 uint operator*(T* ptr) const {
jpayne@69 94 static_assert(!isSameType<Decay<T>, char>(), "Wrap in StringPtr if you want to hash string "
jpayne@69 95 "contents. If you want to hash the pointer, cast to void*");
jpayne@69 96 if (sizeof(ptr) == sizeof(uint)) {
jpayne@69 97 // TODO(cleanup): In C++17, make the if() above be `if constexpr ()`, then change this to
jpayne@69 98 // reinterpret_cast<uint>(ptr).
jpayne@69 99 return reinterpret_cast<unsigned long long>(ptr);
jpayne@69 100 } else {
jpayne@69 101 return operator*(reinterpret_cast<unsigned long long>(ptr));
jpayne@69 102 }
jpayne@69 103 }
jpayne@69 104
jpayne@69 105 template <typename T, typename = decltype(instance<const HashCoder&>() * instance<const T&>())>
jpayne@69 106 uint operator*(ArrayPtr<T> arr) const;
jpayne@69 107 template <typename T, typename = decltype(instance<const HashCoder&>() * instance<const T&>())>
jpayne@69 108 uint operator*(const Array<T>& arr) const;
jpayne@69 109 template <typename T, typename = EnableIf<__is_enum(T)>>
jpayne@69 110 inline uint operator*(T e) const;
jpayne@69 111
jpayne@69 112 template <typename T, typename Result = decltype(instance<T>().hashCode())>
jpayne@69 113 inline Result operator*(T&& value) const { return kj::fwd<T>(value).hashCode(); }
jpayne@69 114 };
jpayne@69 115 static KJ_CONSTEXPR(const) HashCoder HASHCODER = HashCoder();
jpayne@69 116
jpayne@69 117 } // namespace _ (private)
jpayne@69 118
jpayne@69 119 #define KJ_HASHCODE(...) operator*(::kj::_::HashCoder, __VA_ARGS__)
jpayne@69 120 // Defines a hash function for a custom type. Example:
jpayne@69 121 //
jpayne@69 122 // class Foo {...};
jpayne@69 123 // inline uint KJ_HASHCODE(const Foo& foo) { return kj::hashCode(foo.x, foo.y); }
jpayne@69 124 //
jpayne@69 125 // This allows Foo to be passed to hashCode().
jpayne@69 126 //
jpayne@69 127 // The function should be declared either in the same namespace as the target type or in the global
jpayne@69 128 // namespace. It can return any type which itself is hashable -- that value will be hashed in turn
jpayne@69 129 // until a `uint` comes out.
jpayne@69 130
jpayne@69 131 inline uint hashCode(uint value) { return value; }
jpayne@69 132 template <typename T>
jpayne@69 133 inline uint hashCode(T&& value) { return hashCode(_::HASHCODER * kj::fwd<T>(value)); }
jpayne@69 134 template <typename T, size_t N>
jpayne@69 135 inline uint hashCode(T (&arr)[N]) {
jpayne@69 136 static_assert(!isSameType<Decay<T>, char>(), "Wrap in StringPtr if you want to hash string "
jpayne@69 137 "contents. If you want to hash the pointer, cast to void*");
jpayne@69 138 static_assert(isSameType<Decay<T>, char>(), "Wrap in ArrayPtr if you want to hash a C array. "
jpayne@69 139 "If you want to hash the pointer, cast to void*");
jpayne@69 140 return 0;
jpayne@69 141 }
jpayne@69 142 template <typename... T>
jpayne@69 143 inline uint hashCode(T&&... values) {
jpayne@69 144 uint hashes[] = { hashCode(kj::fwd<T>(values))... };
jpayne@69 145 return hashCode(kj::ArrayPtr<uint>(hashes).asBytes());
jpayne@69 146 }
jpayne@69 147 // kj::hashCode() is a universal hashing function, like kj::str() is a universal stringification
jpayne@69 148 // function. Throw stuff in, get a hash code.
jpayne@69 149 //
jpayne@69 150 // Hash codes may differ between different processes, even running exactly the same code.
jpayne@69 151 //
jpayne@69 152 // NOT SUITABLE FOR CRYPTOGRAPHY. This is for hash tables, not crypto.
jpayne@69 153
jpayne@69 154 // =======================================================================================
jpayne@69 155 // inline implementation details
jpayne@69 156
jpayne@69 157 namespace _ { // private
jpayne@69 158
jpayne@69 159 template <typename T, typename>
jpayne@69 160 inline uint HashCoder::operator*(ArrayPtr<T> arr) const {
jpayne@69 161 // Hash each array element to create a string of hashes, then murmur2 over those.
jpayne@69 162 //
jpayne@69 163 // TODO(perf): Choose a more-modern hash. (See hash.c++.)
jpayne@69 164
jpayne@69 165 constexpr uint m = 0x5bd1e995;
jpayne@69 166 constexpr uint r = 24;
jpayne@69 167 uint h = arr.size() * sizeof(uint);
jpayne@69 168
jpayne@69 169 for (auto& e: arr) {
jpayne@69 170 uint k = kj::hashCode(e);
jpayne@69 171 k *= m;
jpayne@69 172 k ^= k >> r;
jpayne@69 173 k *= m;
jpayne@69 174 h *= m;
jpayne@69 175 h ^= k;
jpayne@69 176 }
jpayne@69 177
jpayne@69 178 h ^= h >> 13;
jpayne@69 179 h *= m;
jpayne@69 180 h ^= h >> 15;
jpayne@69 181 return h;
jpayne@69 182 }
jpayne@69 183 template <typename T, typename>
jpayne@69 184 inline uint HashCoder::operator*(const Array<T>& arr) const {
jpayne@69 185 return operator*(arr.asPtr());
jpayne@69 186 }
jpayne@69 187
jpayne@69 188 template <typename T, typename>
jpayne@69 189 inline uint HashCoder::operator*(T e) const {
jpayne@69 190 return operator*(static_cast<__underlying_type(T)>(e));
jpayne@69 191 }
jpayne@69 192
jpayne@69 193 } // namespace _ (private)
jpayne@69 194 } // namespace kj
jpayne@69 195
jpayne@69 196 KJ_END_HEADER