folly/experimental/StringKeyedUnorderedMap.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  20
  21 #include <functional>
  22 #include <initializer_list>
  23 #include <memory>
  24 #include <unordered_map>
  25 #include <utility>
  26
  27 #include <folly/Hash.h>
  28 #include <folly/Range.h>
  29 #include <folly/experimental/StringKeyedCommon.h>
  30
  31 namespace folly {
  32
  33 /**
  34  * Wrapper class for unordered_map<string, Value> that can
  35  * perform lookup operations with StringPiece, not only string.
  36  *
  37  * It uses kind of hack: string pointed by StringPiece is copied when
  38  * StringPiece is inserted into map
  39  */
  40 template <
  41     class Value,
  42     class Hash = Hash,
  43     class Eq = std::equal_to<StringPiece>,
  44     class Alloc = std::allocator<std::pair<const StringPiece, Value>>>
  45 class StringKeyedUnorderedMap
  46     : private std::unordered_map<StringPiece, Value, Hash, Eq, Alloc> {
  47  private:
  48   using Base = std::unordered_map<StringPiece, Value, Hash, Eq, Alloc>;
  49
  50 public:
  51   typedef typename Base::key_type key_type;
  52   typedef typename Base::mapped_type mapped_type;
  53   typedef typename Base::value_type value_type;
  54   typedef typename Base::hasher hasher;
  55   typedef typename Base::key_equal key_equal;
  56   typedef typename Base::allocator_type allocator_type;
  57   typedef typename Base::reference reference;
  58   typedef typename Base::const_reference const_reference;
  59   typedef typename Base::pointer pointer;
  60   typedef typename Base::const_pointer const_pointer;
  61   typedef typename Base::iterator iterator;
  62   typedef typename Base::const_iterator const_iterator;
  63   typedef typename Base::size_type size_type;
  64   typedef typename Base::difference_type difference_type;
  65
  66   explicit StringKeyedUnorderedMap() = default;
  67
  68   explicit StringKeyedUnorderedMap(
  69     size_type n,
  70     const hasher& hf = hasher(),
  71     const key_equal& eql = key_equal(),
  72     const allocator_type& alloc = allocator_type())
  73       : Base(n, hf, eql, alloc) {
  74   }
  75
  76   explicit StringKeyedUnorderedMap(const allocator_type& a)
  77       : Base(a) {
  78   }
  79
  80   template <class InputIterator>
  81   StringKeyedUnorderedMap(InputIterator b, InputIterator e) {
  82     for (; b != e; ++b) {
  83       // insert() will carry the duplication
  84       emplace(b->first, b->second);
  85     }
  86   }
  87
  88   template <class InputIterator>
  89   StringKeyedUnorderedMap(
  90     InputIterator b, InputIterator e,
  91     size_type n,
  92     const hasher& hf = hasher(),
  93     const key_equal& eql = key_equal(),
  94     const allocator_type& alloc = allocator_type())
  95       : Base(n, hf, eql, alloc) {
  96     for (; b != e; ++b) {
  97       // insert() will carry the duplication
  98       emplace(b->first, b->second);
  99     }
 100   }
 101
 102   StringKeyedUnorderedMap(const StringKeyedUnorderedMap& rhs)
 103       : StringKeyedUnorderedMap(rhs.begin(), rhs.end(),
 104              rhs.bucket_count(),
 105              rhs.hash_function(),
 106              rhs.key_eq(),
 107              rhs.get_allocator()) {
 108   }
 109
 110   StringKeyedUnorderedMap(StringKeyedUnorderedMap&& rhs) noexcept
 111       : StringKeyedUnorderedMap(std::move(rhs), rhs.get_allocator()) {
 112   }
 113
 114   StringKeyedUnorderedMap(StringKeyedUnorderedMap&& other,
 115                           const allocator_type& /* a */) noexcept
 116       : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
 117
 118   StringKeyedUnorderedMap(std::initializer_list<value_type> il)
 119       : StringKeyedUnorderedMap(il.begin(), il.end()) {
 120   }
 121
 122   StringKeyedUnorderedMap(
 123     std::initializer_list<value_type> il,
 124     size_type n,
 125     const hasher& hf = hasher(),
 126     const key_equal& eql = key_equal(),
 127     const allocator_type& alloc = allocator_type())
 128       : StringKeyedUnorderedMap(il.begin(), il.end(), n, hf, eql, alloc) {
 129   }
 130
 131   StringKeyedUnorderedMap& operator=(const StringKeyedUnorderedMap& other) & {
 132     if (this == &other) {
 133       return *this;
 134     }
 135     return *this = StringKeyedUnorderedMap(other);
 136   }
 137
 138   StringKeyedUnorderedMap&
 139   operator=(StringKeyedUnorderedMap&& other) & noexcept {
 140     assert(this != &other);
 141     clear();
 142     Base::operator=(std::move(other));
 143     return *this;
 144   }
 145
 146   using Base::empty;
 147   using Base::size;
 148   using Base::max_size;
 149   using Base::begin;
 150   using Base::end;
 151   using Base::cbegin;
 152   using Base::cend;
 153
 154   bool operator==(StringKeyedUnorderedMap const& other) const {
 155     Base const& lhs = *this;
 156     Base const& rhs = static_cast<Base const&>(other);
 157     return lhs == rhs;
 158   }
 159
 160   void swap(StringKeyedUnorderedMap& other) & {
 161     return Base::swap(other);
 162   }
 163
 164   // No need for copy/move overload as StringPiece is small struct.
 165   mapped_type& operator[](StringPiece key) {
 166     auto it = find(key);
 167     if (it != end()) {
 168       return it->second;
 169     }
 170     // operator[] will create new (key, value) pair
 171     // we need to allocate memory for key
 172     return Base::operator[](stringPieceDup(key, get_allocator()));
 173   }
 174
 175   using Base::at;
 176   using Base::find;
 177   using Base::count;
 178
 179   template <class... Args>
 180   std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
 181     auto it = find(key);
 182     if (it != end()) {
 183       return {it, false};
 184     }
 185     return Base::emplace(stringPieceDup(key, get_allocator()),
 186                          std::forward<Args>(args)...);
 187   }
 188
 189   std::pair<iterator, bool> insert(value_type val) {
 190     auto it = find(val.first);
 191     if (it != end()) {
 192       return {it, false};
 193     }
 194     auto valCopy = std::make_pair(stringPieceDup(val.first, get_allocator()),
 195                                   std::move(val.second));
 196     return Base::insert(valCopy);
 197   }
 198
 199   iterator erase(const_iterator position) {
 200     auto key = position->first;
 201     auto result = Base::erase(position);
 202     stringPieceDel(key, get_allocator());
 203     return result;
 204   }
 205
 206   size_type erase(StringPiece key) {
 207     auto it = find(key);
 208     if (it == end()) {
 209       return 0;
 210     }
 211     erase(it);
 212     return 1;
 213   }
 214
 215   void clear() noexcept {
 216     for (auto& it : *this) {
 217       stringPieceDel(it.first, get_allocator());
 218     }
 219     Base::clear();
 220   }
 221
 222   using Base::reserve;
 223   using Base::hash_function;
 224   using Base::key_eq;
 225   using Base::get_allocator;
 226   using Base::bucket_count;
 227   using Base::max_bucket_count;
 228   using Base::bucket_size;
 229   using Base::bucket;
 230
 231   ~StringKeyedUnorderedMap() {
 232     // Here we assume that unordered_map doesn't use keys in destructor
 233     for (auto& it : *this) {
 234       stringPieceDel(it.first, get_allocator());
 235     }
 236   }
 237 };
 238
 239 } // folly