OsmAnd
jni/protobuf/google/protobuf/stubs/hash.h
Go to the documentation of this file.
00001 // Protocol Buffers - Google's data interchange format
00002 // Copyright 2008 Google Inc.  All rights reserved.
00003 // http://code.google.com/p/protobuf/
00004 //
00005 // Redistribution and use in source and binary forms, with or without
00006 // modification, are permitted provided that the following conditions are
00007 // met:
00008 //
00009 //     * Redistributions of source code must retain the above copyright
00010 // notice, this list of conditions and the following disclaimer.
00011 //     * Redistributions in binary form must reproduce the above
00012 // copyright notice, this list of conditions and the following disclaimer
00013 // in the documentation and/or other materials provided with the
00014 // distribution.
00015 //     * Neither the name of Google Inc. nor the names of its
00016 // contributors may be used to endorse or promote products derived from
00017 // this software without specific prior written permission.
00018 //
00019 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00020 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00021 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00022 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
00023 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00024 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00025 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00026 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00027 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00028 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00029 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00030 
00031 // Author: kenton@google.com (Kenton Varda)
00032 //
00033 // Deals with the fact that hash_map is not defined everywhere.
00034 
00035 #ifndef GOOGLE_PROTOBUF_STUBS_HASH_H__
00036 #define GOOGLE_PROTOBUF_STUBS_HASH_H__
00037 
00038 #include <string.h>
00039 #include <google/protobuf/stubs/common.h>
00040 #include "config.h"
00041 
00042 #if defined(HAVE_HASH_MAP) && defined(HAVE_HASH_SET)
00043 #include HASH_MAP_H
00044 #include HASH_SET_H
00045 #else
00046 #define MISSING_HASH
00047 #include <map>
00048 #include <set>
00049 #endif
00050 
00051 namespace google {
00052 namespace protobuf {
00053 
00054 #ifdef MISSING_HASH
00055 
00056 // This system doesn't have hash_map or hash_set.  Emulate them using map and
00057 // set.
00058 
00059 // Make hash<T> be the same as less<T>.  Note that everywhere where custom
00060 // hash functions are defined in the protobuf code, they are also defined such
00061 // that they can be used as "less" functions, which is required by MSVC anyway.
00062 template <typename Key>
00063 struct hash {
00064   // Dummy, just to make derivative hash functions compile.
00065   int operator()(const Key& key) {
00066     GOOGLE_LOG(FATAL) << "Should never be called.";
00067     return 0;
00068   }
00069 
00070   inline bool operator()(const Key& a, const Key& b) const {
00071     return a < b;
00072   }
00073 };
00074 
00075 // Make sure char* is compared by value.
00076 template <>
00077 struct hash<const char*> {
00078   // Dummy, just to make derivative hash functions compile.
00079   int operator()(const char* key) {
00080     GOOGLE_LOG(FATAL) << "Should never be called.";
00081     return 0;
00082   }
00083 
00084   inline bool operator()(const char* a, const char* b) const {
00085     return strcmp(a, b) < 0;
00086   }
00087 };
00088 
00089 template <typename Key, typename Data,
00090           typename HashFcn = hash<Key>,
00091           typename EqualKey = int >
00092 class hash_map : public std::map<Key, Data, HashFcn> {
00093 };
00094 
00095 template <typename Key,
00096           typename HashFcn = hash<Key>,
00097           typename EqualKey = int >
00098 class hash_set : public std::set<Key, HashFcn> {
00099 };
00100 
00101 #elif defined(_MSC_VER) && !defined(_STLPORT_VERSION)
00102 
00103 template <typename Key>
00104 struct hash : public HASH_NAMESPACE::hash_compare<Key> {
00105 };
00106 
00107 // MSVC's hash_compare<const char*> hashes based on the string contents but
00108 // compares based on the string pointer.  WTF?
00109 class CstringLess {
00110  public:
00111   inline bool operator()(const char* a, const char* b) const {
00112     return strcmp(a, b) < 0;
00113   }
00114 };
00115 
00116 template <>
00117 struct hash<const char*>
00118   : public HASH_NAMESPACE::hash_compare<const char*, CstringLess> {
00119 };
00120 
00121 template <typename Key, typename Data,
00122           typename HashFcn = hash<Key>,
00123           typename EqualKey = int >
00124 class hash_map : public HASH_NAMESPACE::hash_map<
00125     Key, Data, HashFcn> {
00126 };
00127 
00128 template <typename Key,
00129           typename HashFcn = hash<Key>,
00130           typename EqualKey = int >
00131 class hash_set : public HASH_NAMESPACE::hash_set<
00132     Key, HashFcn> {
00133 };
00134 
00135 #else
00136 
00137 template <typename Key>
00138 struct hash : public HASH_NAMESPACE::hash<Key> {
00139 };
00140 
00141 template <typename Key>
00142 struct hash<const Key*> {
00143   inline size_t operator()(const Key* key) const {
00144     return reinterpret_cast<size_t>(key);
00145   }
00146 };
00147 
00148 // Unlike the old SGI version, the TR1 "hash" does not special-case char*.  So,
00149 // we go ahead and provide our own implementation.
00150 template <>
00151 struct hash<const char*> {
00152   inline size_t operator()(const char* str) const {
00153     size_t result = 0;
00154     for (; *str != '\0'; str++) {
00155       result = 5 * result + *str;
00156     }
00157     return result;
00158   }
00159 };
00160 
00161 template <typename Key, typename Data,
00162           typename HashFcn = hash<Key>,
00163           typename EqualKey = std::equal_to<Key> >
00164 class hash_map : public HASH_NAMESPACE::HASH_MAP_CLASS<
00165     Key, Data, HashFcn, EqualKey> {
00166 };
00167 
00168 template <typename Key,
00169           typename HashFcn = hash<Key>,
00170           typename EqualKey = std::equal_to<Key> >
00171 class hash_set : public HASH_NAMESPACE::HASH_SET_CLASS<
00172     Key, HashFcn, EqualKey> {
00173 };
00174 
00175 #endif
00176 
00177 template <>
00178 struct hash<string> {
00179   inline size_t operator()(const string& key) const {
00180     return hash<const char*>()(key.c_str());
00181   }
00182 
00183   static const size_t bucket_size = 4;
00184   static const size_t min_buckets = 8;
00185   inline size_t operator()(const string& a, const string& b) const {
00186     return a < b;
00187   }
00188 };
00189 
00190 template <typename First, typename Second>
00191 struct hash<pair<First, Second> > {
00192   inline size_t operator()(const pair<First, Second>& key) const {
00193     size_t first_hash = hash<First>()(key.first);
00194     size_t second_hash = hash<Second>()(key.second);
00195 
00196     // FIXME(kenton):  What is the best way to compute this hash?  I have
00197     // no idea!  This seems a bit better than an XOR.
00198     return first_hash * ((1 << 16) - 1) + second_hash;
00199   }
00200 
00201   static const size_t bucket_size = 4;
00202   static const size_t min_buckets = 8;
00203   inline size_t operator()(const pair<First, Second>& a,
00204                            const pair<First, Second>& b) const {
00205     return a < b;
00206   }
00207 };
00208 
00209 // Used by GCC/SGI STL only.  (Why isn't this provided by the standard
00210 // library?  :( )
00211 struct streq {
00212   inline bool operator()(const char* a, const char* b) const {
00213     return strcmp(a, b) == 0;
00214   }
00215 };
00216 
00217 }  // namespace protobuf
00218 }  // namespace google
00219 
00220 #endif  // GOOGLE_PROTOBUF_STUBS_HASH_H__
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines