1// Protocol Buffers - Google's data interchange format 2// Copyright 2008 Google Inc. All rights reserved. 3// http://code.google.com/p/protobuf/ 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions are 7// met: 8// 9// * Redistributions of source code must retain the above copyright 10// notice, this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above 12// copyright notice, this list of conditions and the following disclaimer 13// in the documentation and/or other materials provided with the 14// distribution. 15// * Neither the name of Google Inc. nor the names of its 16// contributors may be used to endorse or promote products derived from 17// this software without specific prior written permission. 18// 19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31// Author: kenton@google.com (Kenton Varda) 32// 33// Deals with the fact that hash_map is not defined everywhere. 34 35#ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__ 36#define GOOGLE_PROTOBUF_STUBS_HASH_H__ 37 38#include <string.h> 39#include <google/protobuf/stubs/common.h> 40#include "config.h" 41 42#if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET) 43#include HASH_MAP_H 44#include HASH_SET_H 45#else 46#define MISSING_HASH 47#include <map> 48#include <set> 49#endif 50 51namespace google { 52namespace protobuf { 53 54#ifdef MISSING_HASH 55 56// This system doesn't have hash_map or hash_set. Emulate them using map and 57// set. 58 59// Make hash<T> be the same as less<T>. Note that everywhere where custom 60// hash functions are defined in the protobuf code, they are also defined such 61// that they can be used as "less" functions, which is required by MSVC anyway. 62template <typename Key> 63struct hash { 64 // Dummy, just to make derivative hash functions compile. 65 int operator()(const Key& key) { 66 GOOGLE_LOG(FATAL) << "Should never be called."; 67 return 0; 68 } 69 70 inline bool operator()(const Key& a, const Key& b) const { 71 return a < b; 72 } 73}; 74 75// Make sure char* is compared by value. 76template <> 77struct hash<const char*> { 78 // Dummy, just to make derivative hash functions compile. 79 int operator()(const char* key) { 80 GOOGLE_LOG(FATAL) << "Should never be called."; 81 return 0; 82 } 83 84 inline bool operator()(const char* a, const char* b) const { 85 return strcmp(a, b) < 0; 86 } 87}; 88 89template <typename Key, typename Data, 90 typename HashFcn = hash<Key>, 91 typename EqualKey = int > 92class hash_map : public std::map<Key, Data, HashFcn> { 93 public: 94 hash_map(int = 0) {} 95}; 96 97template <typename Key, 98 typename HashFcn = hash<Key>, 99 typename EqualKey = int > 100class hash_set : public std::set<Key, HashFcn> { 101 public: 102 hash_set(int = 0) {} 103}; 104 105#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) 106 107template <typename Key> 108struct hash : public HASH_NAMESPACE::hash_compare<Key> { 109}; 110 111// MSVC's hash_compare<const char*> hashes based on the string contents but 112// compares based on the string pointer. WTF? 113class CstringLess { 114 public: 115 inline bool operator()(const char* a, const char* b) const { 116 return strcmp(a, b) < 0; 117 } 118}; 119 120template <> 121struct hash<const char*> 122 : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> { 123}; 124 125template <typename Key, typename Data, 126 typename HashFcn = hash<Key>, 127 typename EqualKey = int > 128class hash_map : public HASH_NAMESPACE::hash_map< 129 Key, Data, HashFcn> { 130 public: 131 hash_map(int = 0) {} 132}; 133 134template <typename Key, 135 typename HashFcn = hash<Key>, 136 typename EqualKey = int > 137class hash_set : public HASH_NAMESPACE::hash_set< 138 Key, HashFcn> { 139 public: 140 hash_set(int = 0) {} 141}; 142 143#else 144 145template <typename Key> 146struct hash : public HASH_NAMESPACE::hash<Key> { 147}; 148 149template <typename Key> 150struct hash<const Key*> { 151 inline size_t operator()(const Key* key) const { 152 return reinterpret_cast<size_t>(key); 153 } 154}; 155 156// Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, 157// we go ahead and provide our own implementation. 158template <> 159struct hash<const char*> { 160 inline size_t operator()(const char* str) const { 161 size_t result = 0; 162 for (; *str != '\0'; str++) { 163 result = 5 * result + *str; 164 } 165 return result; 166 } 167}; 168 169template <typename Key, typename Data, 170 typename HashFcn = hash<Key>, 171 typename EqualKey = std::equal_to<Key> > 172class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS< 173 Key, Data, HashFcn, EqualKey> { 174 public: 175 hash_map(int = 0) {} 176}; 177 178template <typename Key, 179 typename HashFcn = hash<Key>, 180 typename EqualKey = std::equal_to<Key> > 181class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS< 182 Key, HashFcn, EqualKey> { 183 public: 184 hash_set(int = 0) {} 185}; 186 187#endif 188 189template <> 190struct hash<string> { 191 inline size_t operator()(const string& key) const { 192 return hash<const char*>()(key.c_str()); 193 } 194 195 static const size_t bucket_size = 4; 196 static const size_t min_buckets = 8; 197 inline size_t operator()(const string& a, const string& b) const { 198 return a < b; 199 } 200}; 201 202template <typename First, typename Second> 203struct hash<pair<First, Second> > { 204 inline size_t operator()(const pair<First, Second>& key) const { 205 size_t first_hash = hash<First>()(key.first); 206 size_t second_hash = hash<Second>()(key.second); 207 208 // FIXME(kenton): What is the best way to compute this hash? I have 209 // no idea! This seems a bit better than an XOR. 210 return first_hash * ((1 << 16) - 1) + second_hash; 211 } 212 213 static const size_t bucket_size = 4; 214 static const size_t min_buckets = 8; 215 inline size_t operator()(const pair<First, Second>& a, 216 const pair<First, Second>& b) const { 217 return a < b; 218 } 219}; 220 221// Used by GCC/SGI STL only. (Why isn't this provided by the standard 222// library? :( ) 223struct streq { 224 inline bool operator()(const char* a, const char* b) const { 225 return strcmp(a, b) == 0; 226 } 227}; 228 229} // namespace protobuf 230} // namespace google 231 232#endif // GOOGLE_PROTOBUF_STUBS_HASH_H__ 233