2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 // Copyright 2013-present Facebook. All Rights Reserved.
17 // @author: Pavlo Kushnir (pavlo)
22 #include <initializer_list>
24 #include <unordered_map>
27 #include <folly/Range.h>
28 #include <folly/experimental/StringKeyedCommon.h>
29 #include <folly/hash/Hash.h>
34 * Wrapper class for unordered_map<string, Value> that can
35 * perform lookup operations with StringPiece, not only string.
37 * It uses kind of hack: string pointed by StringPiece is copied when
38 * StringPiece is inserted into map
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> {
48 using Base = std::unordered_map<StringPiece, Value, Hash, Eq, Alloc>;
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;
66 explicit StringKeyedUnorderedMap() = default;
68 explicit StringKeyedUnorderedMap(
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) {
76 explicit StringKeyedUnorderedMap(const allocator_type& a)
80 template <class InputIterator>
81 StringKeyedUnorderedMap(InputIterator b, InputIterator e) {
83 // insert() will carry the duplication
84 emplace(b->first, b->second);
88 template <class InputIterator>
89 StringKeyedUnorderedMap(
90 InputIterator b, InputIterator e,
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) {
97 // insert() will carry the duplication
98 emplace(b->first, b->second);
102 StringKeyedUnorderedMap(const StringKeyedUnorderedMap& rhs)
103 : StringKeyedUnorderedMap(rhs.begin(), rhs.end(),
107 rhs.get_allocator()) {
110 StringKeyedUnorderedMap(StringKeyedUnorderedMap&& rhs) noexcept
111 : StringKeyedUnorderedMap(std::move(rhs), rhs.get_allocator()) {
114 StringKeyedUnorderedMap(StringKeyedUnorderedMap&& other,
115 const allocator_type& /* a */) noexcept
116 : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
118 StringKeyedUnorderedMap(std::initializer_list<value_type> il)
119 : StringKeyedUnorderedMap(il.begin(), il.end()) {
122 StringKeyedUnorderedMap(
123 std::initializer_list<value_type> il,
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) {
131 StringKeyedUnorderedMap& operator=(const StringKeyedUnorderedMap& other) & {
132 if (this == &other) {
135 return *this = StringKeyedUnorderedMap(other);
138 StringKeyedUnorderedMap&
139 operator=(StringKeyedUnorderedMap&& other) & noexcept {
140 assert(this != &other);
142 Base::operator=(std::move(other));
148 using Base::max_size;
154 bool operator==(StringKeyedUnorderedMap const& other) const {
155 Base const& lhs = *this;
156 Base const& rhs = static_cast<Base const&>(other);
160 void swap(StringKeyedUnorderedMap& other) & {
161 return Base::swap(other);
164 // No need for copy/move overload as StringPiece is small struct.
165 mapped_type& operator[](StringPiece key) {
170 // operator[] will create new (key, value) pair
171 // we need to allocate memory for key
172 return Base::operator[](stringPieceDup(key, get_allocator()));
179 template <class... Args>
180 std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
185 return Base::emplace(stringPieceDup(key, get_allocator()),
186 std::forward<Args>(args)...);
189 std::pair<iterator, bool> insert(value_type val) {
190 auto it = find(val.first);
194 auto valCopy = std::make_pair(stringPieceDup(val.first, get_allocator()),
195 std::move(val.second));
196 return Base::insert(valCopy);
199 iterator erase(const_iterator position) {
200 auto key = position->first;
201 auto result = Base::erase(position);
202 stringPieceDel(key, get_allocator());
206 size_type erase(StringPiece key) {
215 void clear() noexcept {
216 for (auto& it : *this) {
217 stringPieceDel(it.first, get_allocator());
223 using Base::hash_function;
225 using Base::get_allocator;
226 using Base::bucket_count;
227 using Base::max_bucket_count;
228 using Base::bucket_size;
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());