folly/experimental/StringKeyedUnorderedMap.h

   1 /*
   2  * Copyright 2015 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 // Copyright 2013-present Facebook. All Rights Reserved.
  17 // @author: Pavlo Kushnir (pavlo)
  18
  19 #ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_
  20 #define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_
  21
  22 #include <initializer_list>
  23 #include <memory>
  24 #include <unordered_map>
  25 #include <folly/Range.h>
  26 #include <folly/experimental/StringKeyedCommon.h>
  27
  28 namespace folly {
  29
  30 /**
  31  * Wrapper class for unordered_map<string, Value> that can
  32  * perform lookup operations with StringPiece, not only string.
  33  *
  34  * It uses kind of hack: string pointed by StringPiece is copied when
  35  * StringPiece is inserted into map
  36  */
  37 template <class Value,
  38           class Hash = StringPieceHash,
  39           class Eq = std::equal_to<StringPiece>,
  40           class Alloc = std::allocator<std::pair<const StringPiece, Value>>>
  41 class StringKeyedUnorderedMap
  42     : private std::unordered_map<StringPiece, Value, Hash, Eq, Alloc> {
  43 private:
  44   using Base = std::unordered_map<StringPiece, Value, Hash, Eq, Alloc>;
  45
  46 public:
  47   typedef typename Base::key_type key_type;
  48   typedef typename Base::mapped_type mapped_type;
  49   typedef typename Base::value_type value_type;
  50   typedef typename Base::hasher hasher;
  51   typedef typename Base::key_equal key_equal;
  52   typedef typename Base::allocator_type allocator_type;
  53   typedef typename Base::reference reference;
  54   typedef typename Base::const_reference const_reference;
  55   typedef typename Base::pointer pointer;
  56   typedef typename Base::const_pointer const_pointer;
  57   typedef typename Base::iterator iterator;
  58   typedef typename Base::const_iterator const_iterator;
  59   typedef typename Base::size_type size_type;
  60   typedef typename Base::difference_type difference_type;
  61
  62   explicit StringKeyedUnorderedMap() = default;
  63
  64   explicit StringKeyedUnorderedMap(
  65     size_type n,
  66     const hasher& hf = hasher(),
  67     const key_equal& eql = key_equal(),
  68     const allocator_type& alloc = allocator_type())
  69       : Base(n, hf, eql, alloc) {
  70   }
  71
  72   explicit StringKeyedUnorderedMap(const allocator_type& a)
  73       : Base(a) {
  74   }
  75
  76   template <class InputIterator>
  77   StringKeyedUnorderedMap(InputIterator b, InputIterator e) {
  78     for (; b != e; ++b) {
  79       // insert() will carry the duplication
  80       emplace(b->first, b->second);
  81     }
  82   }
  83
  84   template <class InputIterator>
  85   StringKeyedUnorderedMap(
  86     InputIterator b, InputIterator e,
  87     size_type n,
  88     const hasher& hf = hasher(),
  89     const key_equal& eql = key_equal(),
  90     const allocator_type& alloc = allocator_type())
  91       : Base(n, hf, eql, alloc) {
  92     for (; b != e; ++b) {
  93       // insert() will carry the duplication
  94       emplace(b->first, b->second);
  95     }
  96   }
  97
  98   StringKeyedUnorderedMap(const StringKeyedUnorderedMap& rhs)
  99       : StringKeyedUnorderedMap(rhs.begin(), rhs.end(),
 100              rhs.bucket_count(),
 101              rhs.hash_function(),
 102              rhs.key_eq(),
 103              rhs.get_allocator()) {
 104   }
 105
 106   StringKeyedUnorderedMap(StringKeyedUnorderedMap&& rhs) noexcept
 107       : StringKeyedUnorderedMap(std::move(rhs), rhs.get_allocator()) {
 108   }
 109
 110   StringKeyedUnorderedMap(StringKeyedUnorderedMap&& other,
 111                           const allocator_type& a) noexcept
 112       : Base(std::move(other)/*, a*/ /* not supported by gcc */) {
 113   }
 114
 115   StringKeyedUnorderedMap(std::initializer_list<value_type> il)
 116       : StringKeyedUnorderedMap(il.begin(), il.end()) {
 117   }
 118
 119   StringKeyedUnorderedMap(
 120     std::initializer_list<value_type> il,
 121     size_type n,
 122     const hasher& hf = hasher(),
 123     const key_equal& eql = key_equal(),
 124     const allocator_type& alloc = allocator_type())
 125       : StringKeyedUnorderedMap(il.begin(), il.end(), n, hf, eql, alloc) {
 126   }
 127
 128   StringKeyedUnorderedMap& operator=(const StringKeyedUnorderedMap& other) & {
 129     if (this == &other) {
 130       return *this;
 131     }
 132     return *this = StringKeyedUnorderedMap(other);
 133   }
 134
 135   StringKeyedUnorderedMap&
 136   operator=(StringKeyedUnorderedMap&& other) & noexcept {
 137     assert(this != &other);
 138     clear();
 139     Base::operator=(std::move(other));
 140     return *this;
 141   }
 142
 143   using Base::empty;
 144   using Base::size;
 145   using Base::max_size;
 146   using Base::begin;
 147   using Base::end;
 148   using Base::cbegin;
 149   using Base::cend;
 150
 151   bool operator==(const StringKeyedUnorderedMap& rhs) {
 152     const Base& lhs = *this;
 153     return lhs == rhs;
 154   }
 155
 156   // No need for copy/move overload as StringPiece is small struct.
 157   mapped_type& operator[](StringPiece key) {
 158     auto it = find(key);
 159     if (it != end()) {
 160       return it->second;
 161     }
 162     // operator[] will create new (key, value) pair
 163     // we need to allocate memory for key
 164     return Base::operator[](stringPieceDup(key, get_allocator()));
 165   }
 166
 167   using Base::at;
 168   using Base::find;
 169
 170   template <class... Args>
 171   std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
 172     auto it = find(key);
 173     if (it != end()) {
 174       return {it, false};
 175     }
 176     return Base::emplace(stringPieceDup(key, get_allocator()),
 177                          std::forward<Args>(args)...);
 178   }
 179
 180   std::pair<iterator, bool> insert(value_type val) {
 181     auto it = find(val.first);
 182     if (it != end()) {
 183       return {it, false};
 184     }
 185     auto valCopy = std::make_pair(stringPieceDup(val.first, get_allocator()),
 186                                   std::move(val.second));
 187     return Base::insert(valCopy);
 188   }
 189
 190   iterator erase(const_iterator position) {
 191     auto key = position->first;
 192     auto result = Base::erase(position);
 193     stringPieceDel(key, get_allocator());
 194     return result;
 195   }
 196
 197   size_type erase(StringPiece key) {
 198     auto it = find(key);
 199     if (it == end()) {
 200       return 0;
 201     }
 202     erase(it);
 203     return 1;
 204   }
 205
 206   void clear() noexcept {
 207     for (auto& it : *this) {
 208       stringPieceDel(it.first, get_allocator());
 209     }
 210     Base::clear();
 211   }
 212
 213   using Base::reserve;
 214   using Base::hash_function;
 215   using Base::key_eq;
 216   using Base::get_allocator;
 217   using Base::bucket_count;
 218   using Base::max_bucket_count;
 219   using Base::bucket_size;
 220   using Base::bucket;
 221
 222   ~StringKeyedUnorderedMap() {
 223     // Here we assume that unordered_map doesn't use keys in destructor
 224     for (auto& it : *this) {
 225       stringPieceDel(it.first, get_allocator());
 226     }
 227   }
 228 };
 229
 230 } // folly
 231
 232 #endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_ */