src/hash_map.h

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef NINJA_MAP_H_
  16 #define NINJA_MAP_H_
  17
  18 #include <algorithm>
  19 #include <string.h>
  20 #include "string_piece.h"
  21
  22 // MurmurHash2, by Austin Appleby
  23 static inline
  24 unsigned int MurmurHash2(const void* key, size_t len) {
  25   static const unsigned int seed = 0xDECAFBAD;
  26   const unsigned int m = 0x5bd1e995;
  27   const int r = 24;
  28   unsigned int h = seed ^ len;
  29   const unsigned char* data = (const unsigned char*)key;
  30   while (len >= 4) {
  31     unsigned int k;
  32     memcpy(&k, data, sizeof k);
  33     k *= m;
  34     k ^= k >> r;
  35     k *= m;
  36     h *= m;
  37     h ^= k;
  38     data += 4;
  39     len -= 4;
  40   }
  41   switch (len) {
  42   case 3: h ^= data[2] << 16;
  43   case 2: h ^= data[1] << 8;
  44   case 1: h ^= data[0];
  45     h *= m;
  46   };
  47   h ^= h >> 13;
  48   h *= m;
  49   h ^= h >> 15;
  50   return h;
  51 }
  52
  53 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
  54 #include <unordered_map>
  55
  56 namespace std {
  57 template<>
  58 struct hash<StringPiece> {
  59   typedef StringPiece argument_type;
  60   typedef size_t result_type;
  61
  62   size_t operator()(StringPiece key) const {
  63     return MurmurHash2(key.str_, key.len_);
  64   }
  65 };
  66 }
  67
  68 #elif defined(_MSC_VER)
  69 #include <hash_map>
  70
  71 using stdext::hash_map;
  72 using stdext::hash_compare;
  73
  74 struct StringPieceCmp : public hash_compare<StringPiece> {
  75   size_t operator()(const StringPiece& key) const {
  76     return MurmurHash2(key.str_, key.len_);
  77   }
  78   bool operator()(const StringPiece& a, const StringPiece& b) const {
  79     int cmp = strncmp(a.str_, b.str_, min(a.len_, b.len_));
  80     if (cmp < 0) {
  81       return true;
  82     } else if (cmp > 0) {
  83       return false;
  84     } else {
  85       return a.len_ < b.len_;
  86     }
  87   }
  88 };
  89
  90 #else
  91 #include <ext/hash_map>
  92
  93 using __gnu_cxx::hash_map;
  94
  95 namespace __gnu_cxx {
  96 template<>
  97 struct hash<StringPiece> {
  98   size_t operator()(StringPiece key) const {
  99     return MurmurHash2(key.str_, key.len_);
 100   }
 101 };
 102 }
 103 #endif
 104
 105 /// A template for hash_maps keyed by a StringPiece whose string is
 106 /// owned externally (typically by the values).  Use like:
 107 /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash
 108 /// mapping StringPiece => Foo*.
 109 template<typename V>
 110 struct ExternalStringHashMap {
 111 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
 112   typedef std::unordered_map<StringPiece, V> Type;
 113 #elif defined(_MSC_VER)
 114   typedef hash_map<StringPiece, V, StringPieceCmp> Type;
 115 #else
 116   typedef hash_map<StringPiece, V> Type;
 117 #endif
 118 };
 119
 120 #endif // NINJA_MAP_H_