folly/experimental/StringKeyedMap.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 <initializer_list>
  22 #include <map>
  23 #include <memory>
  24
  25 #include <folly/Range.h>
  26 #include <folly/experimental/StringKeyedCommon.h>
  27
  28 namespace folly {
  29
  30 /**
  31  * Wrapper class for 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 <
  38     class Value,
  39     class Compare = std::less<StringPiece>,
  40     class Alloc = std::allocator<std::pair<const StringPiece, Value>>>
  41 class StringKeyedMap
  42     : private std::map<StringPiece, Value, Compare, Alloc> {
  43  private:
  44   using Base = std::map<StringPiece, Value, Compare, 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::key_compare key_compare;
  51   typedef typename Base::allocator_type allocator_type;
  52   typedef typename Base::reference reference;
  53   typedef typename Base::const_reference const_reference;
  54   typedef typename Base::pointer pointer;
  55   typedef typename Base::const_pointer const_pointer;
  56   typedef typename Base::iterator iterator;
  57   typedef typename Base::const_iterator const_iterator;
  58   typedef typename Base::reverse_iterator reverse_iterator;
  59   typedef typename Base::const_reverse_iterator const_reverse_iterator;
  60   typedef typename Base::difference_type difference_type;
  61   typedef typename Base::size_type size_type;
  62
  63   using Base::get_allocator;
  64
  65   // Ctors in the same order as
  66   // http://cplusplus.com/reference/map/map/map/
  67   explicit StringKeyedMap(
  68     const key_compare& comp = key_compare(),
  69     const allocator_type& alloc = allocator_type())
  70       : Base(comp, alloc) {
  71   }
  72
  73   explicit StringKeyedMap(const allocator_type& alloc)
  74       : Base(alloc) {
  75   }
  76
  77   template <class InputIterator>
  78   explicit StringKeyedMap(
  79     InputIterator b, InputIterator e,
  80     const key_compare& comp = key_compare(),
  81     const allocator_type& alloc = allocator_type())
  82       : Base(comp, alloc) {
  83     for (; b != e; ++b) {
  84       // emplace() will carry the duplication
  85       emplace(b->first, b->second);
  86     }
  87   }
  88
  89   StringKeyedMap(const StringKeyedMap& rhs)
  90       : StringKeyedMap(rhs, rhs.get_allocator()) {
  91   }
  92
  93   StringKeyedMap(const StringKeyedMap& rhs, const allocator_type& a)
  94       : StringKeyedMap(rhs.begin(), rhs.end(), rhs.key_comp(), a) {
  95   }
  96
  97   StringKeyedMap(StringKeyedMap&& other) noexcept
  98     : Base(std::move(other)) {
  99   }
 100
 101   StringKeyedMap(StringKeyedMap&& other, const allocator_type& /* a */) noexcept
 102       : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
 103
 104   StringKeyedMap(std::initializer_list<value_type> il,
 105      const key_compare& comp = key_compare(),
 106      const allocator_type& alloc = allocator_type())
 107       : StringKeyedMap(il.begin(), il.end(), comp, alloc) {
 108   }
 109
 110   StringKeyedMap& operator=(const StringKeyedMap& other) & {
 111     if (this == &other) {
 112       return *this;
 113     }
 114     return *this = StringKeyedMap(other);
 115   }
 116
 117   StringKeyedMap& operator=(StringKeyedMap&& other) & noexcept {
 118     assert(this != &other);
 119     clear();
 120     Base::operator=(std::move(other));
 121     return *this;
 122   }
 123
 124   using Base::empty;
 125   using Base::size;
 126   using Base::max_size;
 127   using Base::begin;
 128   using Base::end;
 129   using Base::rbegin;
 130   using Base::rend;
 131   using Base::cbegin;
 132   using Base::cend;
 133   using Base::crbegin;
 134   using Base::crend;
 135
 136   bool operator==(StringKeyedMap const& other) const {
 137     Base const& lhs = *this;
 138     Base const& rhs = static_cast<Base const&>(other);
 139     return lhs == rhs;
 140   }
 141
 142   // no need for copy/move overload as StringPiece is small struct
 143   mapped_type& operator[](StringPiece key) {
 144     auto it = find(key);
 145     if (it != end()) {
 146       return it->second;
 147     }
 148     // operator[] will create new (key, value) pair
 149     // we need to allocate memory for key
 150     return Base::operator[](stringPieceDup(key, get_allocator()));
 151   }
 152
 153   using Base::at;
 154   using Base::find;
 155   using Base::count;
 156   using Base::lower_bound;
 157   using Base::upper_bound;
 158
 159   template <class... Args>
 160   std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
 161     auto it = find(key);
 162     if (it != end()) {
 163       return {it, false};
 164     }
 165     return Base::emplace(stringPieceDup(key, get_allocator()),
 166                          std::forward<Args>(args)...);
 167   }
 168
 169   std::pair<iterator, bool> insert(value_type val) {
 170     auto it = find(val.first);
 171     if (it != end()) {
 172       return {it, false};
 173     }
 174     return Base::insert(
 175       std::make_pair(stringPieceDup(val.first, get_allocator()),
 176                      std::move(val.second)));
 177   }
 178
 179   iterator erase(const_iterator position) {
 180     auto key = position->first;
 181     auto result = Base::erase(position);
 182     stringPieceDel(key, get_allocator());
 183     return result;
 184   }
 185
 186   size_type erase(StringPiece key) {
 187     auto it = find(key);
 188     if (it == end()) {
 189       return 0;
 190     }
 191     erase(it);
 192     return 1;
 193   }
 194
 195   void clear() noexcept {
 196     for (auto& it : *this) {
 197       stringPieceDel(it.first, get_allocator());
 198     }
 199     Base::clear();
 200   }
 201
 202   void swap(StringKeyedMap& other) & {
 203     return Base::swap(other);
 204   }
 205
 206   ~StringKeyedMap() {
 207     // Here we assume that map doesn't use keys in destructor
 208     for (auto& it : *this) {
 209       stringPieceDel(it.first, get_allocator());
 210     }
 211   }
 212 };
 213
 214 } // namespace folly