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}; 94 95template <typename Key, 96 typename HashFcn = hash<Key>, 97 typename EqualKey = int > 98class hash_set : public std::set<Key, HashFcn> { 99}; 100 101#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION) 102 103template <typename Key> 104struct hash : public HASH_NAMESPACE::hash_compare<Key> { 105}; 106 107// MSVC's hash_compare<const char*> hashes based on the string contents but 108// compares based on the string pointer. WTF? 109class CstringLess { 110 public: 111 inline bool operator()(const char* a, const char* b) const { 112 return strcmp(a, b) < 0; 113 } 114}; 115 116template <> 117struct hash<const char*> 118 : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> { 119}; 120 121template <typename Key, typename Data, 122 typename HashFcn = hash<Key>, 123 typename EqualKey = int > 124class hash_map : public HASH_NAMESPACE::hash_map< 125 Key, Data, HashFcn> { 126}; 127 128template <typename Key, 129 typename HashFcn = hash<Key>, 130 typename EqualKey = int > 131class hash_set : public HASH_NAMESPACE::hash_set< 132 Key, HashFcn> { 133}; 134 135#else 136 137template <typename Key> 138struct hash : public HASH_NAMESPACE::hash<Key> { 139}; 140 141template <typename Key> 142struct hash<const Key*> { 143 inline size_t operator()(const Key* key) const { 144 return reinterpret_cast<size_t>(key); 145 } 146}; 147 148// Unlike the old SGI version, the TR1 "hash" does not special-case char*. So, 149// we go ahead and provide our own implementation. 150template <> 151struct hash<const char*> { 152 inline size_t operator()(const char* str) const { 153 size_t result = 0; 154 for (; *str != '\0'; str++) { 155 result = 5 * result + *str; 156 } 157 return result; 158 } 159}; 160 161template <typename Key, typename Data, 162 typename HashFcn = hash<Key>, 163 typename EqualKey = std::equal_to<Key> > 164class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS< 165 Key, Data, HashFcn, EqualKey> { 166}; 167 168template <typename Key, 169 typename HashFcn = hash<Key>, 170 typename EqualKey = std::equal_to<Key> > 171class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS< 172 Key, HashFcn, EqualKey> { 173}; 174 175#endif 176 177template <> 178struct hash<string> { 179 inline size_t operator()(const string& key) const { 180 return hash<const char*>()(key.c_str()); 181 } 182 183 static const size_t bucket_size = 4; 184 static const size_t min_buckets = 8; 185 inline size_t operator()(const string& a, const string& b) const { 186 return a < b; 187 } 188}; 189 190template <typename First, typename Second> 191struct hash<pair<First, Second> > { 192 inline size_t operator()(const pair<First, Second>& key) const { 193 size_t first_hash = hash<First>()(key.first); 194 size_t second_hash = hash<Second>()(key.second); 195 196 // FIXME(kenton): What is the best way to compute this hash? I have 197 // no idea! This seems a bit better than an XOR. 198 return first_hash * ((1 << 16) - 1) + second_hash; 199 } 200 201 static const size_t bucket_size = 4; 202 static const size_t min_buckets = 8; 203 inline size_t operator()(const pair<First, Second>& a, 204 const pair<First, Second>& b) const { 205 return a < b; 206 } 207}; 208 209// Used by GCC/SGI STL only. (Why isn't this provided by the standard 210// library? :( ) 211struct streq { 212 inline bool operator()(const char* a, const char* b) const { 213 return strcmp(a, b) == 0; 214 } 215}; 216 217} // namespace protobuf 218} // namespace google 219 220#endif // GOOGLE_PROTOBUF_STUBS_HASH_H__ 221