2 * Copyright 2015 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)
19 #ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_
20 #define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_
22 #include <initializer_list>
24 #include <unordered_map>
25 #include <folly/Range.h>
26 #include <folly/experimental/StringKeyedCommon.h>
31 * Wrapper class for unordered_map<string, Value> that can
32 * perform lookup operations with StringPiece, not only string.
34 * It uses kind of hack: string pointed by StringPiece is copied when
35 * StringPiece is inserted into map
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> {
44 using Base = std::unordered_map<StringPiece, Value, Hash, Eq, Alloc>;
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;
62 explicit StringKeyedUnorderedMap() = default;
64 explicit StringKeyedUnorderedMap(
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) {
72 explicit StringKeyedUnorderedMap(const allocator_type& a)
76 template <class InputIterator>
77 StringKeyedUnorderedMap(InputIterator b, InputIterator e) {
79 // insert() will carry the duplication
80 emplace(b->first, b->second);
84 template <class InputIterator>
85 StringKeyedUnorderedMap(
86 InputIterator b, InputIterator e,
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) {
93 // insert() will carry the duplication
94 emplace(b->first, b->second);
98 StringKeyedUnorderedMap(const StringKeyedUnorderedMap& rhs)
99 : StringKeyedUnorderedMap(rhs.begin(), rhs.end(),
103 rhs.get_allocator()) {
106 StringKeyedUnorderedMap(StringKeyedUnorderedMap&& rhs) noexcept
107 : StringKeyedUnorderedMap(std::move(rhs), rhs.get_allocator()) {
110 StringKeyedUnorderedMap(StringKeyedUnorderedMap&& other,
111 const allocator_type& /* a */) noexcept
112 : Base(std::move(other) /*, a*/ /* not supported by gcc */) {}
114 StringKeyedUnorderedMap(std::initializer_list<value_type> il)
115 : StringKeyedUnorderedMap(il.begin(), il.end()) {
118 StringKeyedUnorderedMap(
119 std::initializer_list<value_type> il,
121 const hasher& hf = hasher(),
122 const key_equal& eql = key_equal(),
123 const allocator_type& alloc = allocator_type())
124 : StringKeyedUnorderedMap(il.begin(), il.end(), n, hf, eql, alloc) {
127 StringKeyedUnorderedMap& operator=(const StringKeyedUnorderedMap& other) & {
128 if (this == &other) {
131 return *this = StringKeyedUnorderedMap(other);
134 StringKeyedUnorderedMap&
135 operator=(StringKeyedUnorderedMap&& other) & noexcept {
136 assert(this != &other);
138 Base::operator=(std::move(other));
144 using Base::max_size;
150 bool operator==(const StringKeyedUnorderedMap& rhs) {
151 const Base& lhs = *this;
155 // No need for copy/move overload as StringPiece is small struct.
156 mapped_type& operator[](StringPiece key) {
161 // operator[] will create new (key, value) pair
162 // we need to allocate memory for key
163 return Base::operator[](stringPieceDup(key, get_allocator()));
169 template <class... Args>
170 std::pair<iterator, bool> emplace(StringPiece key, Args&&... args) {
175 return Base::emplace(stringPieceDup(key, get_allocator()),
176 std::forward<Args>(args)...);
179 std::pair<iterator, bool> insert(value_type val) {
180 auto it = find(val.first);
184 auto valCopy = std::make_pair(stringPieceDup(val.first, get_allocator()),
185 std::move(val.second));
186 return Base::insert(valCopy);
189 iterator erase(const_iterator position) {
190 auto key = position->first;
191 auto result = Base::erase(position);
192 stringPieceDel(key, get_allocator());
196 size_type erase(StringPiece key) {
205 void clear() noexcept {
206 for (auto& it : *this) {
207 stringPieceDel(it.first, get_allocator());
213 using Base::hash_function;
215 using Base::get_allocator;
216 using Base::bucket_count;
217 using Base::max_bucket_count;
218 using Base::bucket_size;
221 ~StringKeyedUnorderedMap() {
222 // Here we assume that unordered_map doesn't use keys in destructor
223 for (auto& it : *this) {
224 stringPieceDel(it.first, get_allocator());
231 #endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDMAP_H_ */