15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Protocol Buffers - Google's data interchange format
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2008 Google Inc.  All rights reserved.
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://code.google.com/p/protobuf/
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met:
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions of source code must retain the above copyright
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer.
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions in binary form must reproduce the above
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution.
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Neither the name of Google Inc. nor the names of its
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission.
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: kenton@google.com (Kenton Varda)
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Deals with the fact that hash_map is not defined everywhere.
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define GOOGLE_PROTOBUF_STUBS_HASH_H__
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h>
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <google/protobuf/stubs/common.h>
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config.h"
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET)
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include HASH_MAP_H
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include HASH_SET_H
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MISSING_HASH
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <map>
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <set>
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace google {
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace protobuf {
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef MISSING_HASH
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This system doesn't have hash_map or hash_set.  Emulate them using map and
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// set.
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Make hash<T> be the same as less<T>.  Note that everywhere where custom
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// hash functions are defined in the protobuf code, they are also defined such
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that they can be used as "less" functions, which is required by MSVC anyway.
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key>
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash {
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Dummy, just to make derivative hash functions compile.
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int operator()(const Key& key) {
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    GOOGLE_LOG(FATAL) << "Should never be called.";
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return 0;
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline bool operator()(const Key& a, const Key& b) const {
715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return a < b;
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Make sure char* is compared by value.
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <>
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<const char*> {
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Dummy, just to make derivative hash functions compile.
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int operator()(const char* key) {
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    GOOGLE_LOG(FATAL) << "Should never be called.";
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return 0;
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline bool operator()(const char* a, const char* b) const {
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return strcmp(a, b) < 0;
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key, typename Data,
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = int >
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_map : public std::map<Key, Data, HashFcn> {
93ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
94ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_map(int = 0) {}
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key,
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = int >
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_set : public std::set<Key, HashFcn> {
101ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
102ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_set(int = 0) {}
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key>
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash : public HASH_NAMESPACE::hash_compare<Key> {
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// MSVC's hash_compare<const char*> hashes based on the string contents but
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// compares based on the string pointer.  WTF?
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class CstringLess {
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline bool operator()(const char* a, const char* b) const {
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return strcmp(a, b) < 0;
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <>
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<const char*>
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key, typename Data,
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = int >
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_map : public HASH_NAMESPACE::hash_map<
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Key, Data, HashFcn> {
130ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
131ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_map(int = 0) {}
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key,
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = int >
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_set : public HASH_NAMESPACE::hash_set<
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Key, HashFcn> {
139ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
140ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_set(int = 0) {}
1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else
1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key>
1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash : public HASH_NAMESPACE::hash<Key> {
1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key>
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<const Key*> {
1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const Key* key) const {
1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return reinterpret_cast<size_t>(key);
1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unlike the old SGI version, the TR1 "hash" does not special-case char*.  So,
1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// we go ahead and provide our own implementation.
1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <>
1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<const char*> {
1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const char* str) const {
1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    size_t result = 0;
1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    for (; *str != '\0'; str++) {
1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      result = 5 * result + *str;
1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return result;
1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key, typename Data,
1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = std::equal_to<Key> >
1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Key, Data, HashFcn, EqualKey> {
174ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
175ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_map(int = 0) {}
1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Key,
1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename HashFcn = hash<Key>,
1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          typename EqualKey = std::equal_to<Key> >
1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Key, HashFcn, EqualKey> {
183ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch public:
184ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  hash_set(int = 0) {}
1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <>
1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<string> {
1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const string& key) const {
1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return hash<const char*>()(key.c_str());
1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const size_t bucket_size = 4;
1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const size_t min_buckets = 8;
1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const string& a, const string& b) const {
1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return a < b;
1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename First, typename Second>
2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct hash<pair<First, Second> > {
2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const pair<First, Second>& key) const {
2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    size_t first_hash = hash<First>()(key.first);
2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    size_t second_hash = hash<Second>()(key.second);
2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // FIXME(kenton):  What is the best way to compute this hash?  I have
2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // no idea!  This seems a bit better than an XOR.
2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return first_hash * ((1 << 16) - 1) + second_hash;
2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const size_t bucket_size = 4;
2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static const size_t min_buckets = 8;
2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline size_t operator()(const pair<First, Second>& a,
2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                           const pair<First, Second>& b) const {
2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return a < b;
2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Used by GCC/SGI STL only.  (Why isn't this provided by the standard
2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// library?  :( )
2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct streq {
2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  inline bool operator()(const char* a, const char* b) const {
2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return strcmp(a, b) == 0;
2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace protobuf
2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace google
2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif  // GOOGLE_PROTOBUF_STUBS_HASH_H__
233