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