1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc. All rights reserved.
3// https://developers.google.com/protocol-buffers/
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: [email protected] (Kenton Varda)
32
33#ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__
34#define GOOGLE_PROTOBUF_STUBS_HASH_H__
35
36#include <string.h>
37#include <google/protobuf/stubs/common.h>
38
39#include <unordered_map>
40#include <unordered_set>
41
42# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_START \
43 namespace google { \
44 namespace protobuf {
45# define GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END }}
46
47namespace google {
48namespace protobuf {
49
50template <typename Key>
51struct hash : public std::hash<Key> {};
52
53template <typename Key>
54struct hash<const Key*> {
55 inline size_t operator()(const Key* key) const {
56 return reinterpret_cast<size_t>(key);
57 }
58};
59
60// Unlike the old SGI version, the TR1 "hash" does not special-case char*. So,
61// we go ahead and provide our own implementation.
62template <>
63struct hash<const char*> {
64 inline size_t operator()(const char* str) const {
65 size_t result = 0;
66 for (; *str != '\0'; str++) {
67 result = 5 * result + static_cast<size_t>(*str);
68 }
69 return result;
70 }
71};
72
73template<>
74struct hash<bool> {
75 size_t operator()(bool x) const {
76 return static_cast<size_t>(x);
77 }
78};
79
80template <>
81struct hash<string> {
82 inline size_t operator()(const string& key) const {
83 return hash<const char*>()(key.c_str());
84 }
85
86 static const size_t bucket_size = 4;
87 static const size_t min_buckets = 8;
88 inline bool operator()(const string& a, const string& b) const {
89 return a < b;
90 }
91};
92
93template <typename First, typename Second>
94struct hash<std::pair<First, Second> > {
95 inline size_t operator()(const std::pair<First, Second>& key) const {
96 size_t first_hash = hash<First>()(key.first);
97 size_t second_hash = hash<Second>()(key.second);
98
99 // FIXME(kenton): What is the best way to compute this hash? I have
100 // no idea! This seems a bit better than an XOR.
101 return first_hash * ((1 << 16) - 1) + second_hash;
102 }
103
104 static const size_t bucket_size = 4;
105 static const size_t min_buckets = 8;
106 inline bool operator()(const std::pair<First, Second>& a,
107 const std::pair<First, Second>& b) const {
108 return a < b;
109 }
110};
111
112// Used by GCC/SGI STL only. (Why isn't this provided by the standard
113// library? :( )
114struct streq {
115 inline bool operator()(const char* a, const char* b) const {
116 return strcmp(a, b) == 0;
117 }
118};
119
120} // namespace protobuf
121} // namespace google
122
123#endif // GOOGLE_PROTOBUF_STUBS_HASH_H__
124