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_set>
27 #include <folly/Hash.h>
28 #include <folly/Range.h>
29 #include <folly/experimental/StringKeyedCommon.h>
34 * Wrapper class for unordered_set<string> 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 set
42 class Eq = std::equal_to<StringPiece>,
43 class Alloc = std::allocator<folly::StringPiece>>
44 class BasicStringKeyedUnorderedSet
45 : private std::unordered_set<StringPiece, Hasher, Eq, Alloc> {
46 using Base = std::unordered_set<StringPiece, Hasher, Eq, Alloc>;
49 typedef typename Base::key_type key_type;
50 typedef typename Base::value_type value_type;
51 typedef typename Base::hasher hasher;
52 typedef typename Base::key_equal key_equal;
53 typedef typename Base::allocator_type allocator_type;
54 typedef typename Base::reference reference;
55 typedef typename Base::const_reference const_reference;
56 typedef typename Base::pointer pointer;
57 typedef typename Base::const_pointer const_pointer;
58 typedef typename Base::iterator iterator;
59 typedef typename Base::const_iterator const_iterator;
60 typedef typename Base::size_type size_type;
61 typedef typename Base::difference_type difference_type;
63 // Constructors in the same order as in
64 // http://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/
65 explicit BasicStringKeyedUnorderedSet() {
68 explicit BasicStringKeyedUnorderedSet(
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 BasicStringKeyedUnorderedSet(const allocator_type& alloc)
80 template <class InputIterator>
81 BasicStringKeyedUnorderedSet(InputIterator b, InputIterator e) {
87 template <class InputIterator>
88 BasicStringKeyedUnorderedSet(
89 InputIterator b, InputIterator e,
91 const hasher& hf = hasher(),
92 const key_equal& eql = key_equal(),
93 const allocator_type& alloc = allocator_type())
94 : Base(n, hf, eql, alloc) {
100 BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs)
101 : BasicStringKeyedUnorderedSet(rhs, rhs.get_allocator()) {
104 BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs,
105 const allocator_type& a)
106 : BasicStringKeyedUnorderedSet(rhs.begin(),
114 BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs) noexcept
115 : Base(std::move(rhs)) {
119 BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs,
120 const allocator_type& /* a */) noexcept
121 : Base(std::move(rhs) /* , a */ /* not supported by gcc */) {
125 BasicStringKeyedUnorderedSet(std::initializer_list<value_type> il)
126 : BasicStringKeyedUnorderedSet(il.begin(), il.end()) {
129 BasicStringKeyedUnorderedSet(
130 std::initializer_list<value_type> il,
132 const hasher& hf = hasher(),
133 const key_equal& eql = key_equal(),
134 const allocator_type& alloc = allocator_type())
135 : BasicStringKeyedUnorderedSet(il.begin(), il.end(), n, hf, eql, alloc) {
138 BasicStringKeyedUnorderedSet&
139 operator=(const BasicStringKeyedUnorderedSet& rhs) & {
143 // Cost is as bad as a full copy, so to it via copy + move
144 return *this = BasicStringKeyedUnorderedSet(rhs);
147 BasicStringKeyedUnorderedSet&
148 operator=(BasicStringKeyedUnorderedSet&& rhs) & noexcept {
149 assert(this != &rhs);
151 Base::operator=(std::move(rhs));
157 using Base::max_size;
165 bool operator==(const BasicStringKeyedUnorderedSet& other) const {
166 Base const& lhs = *this;
167 Base const& rhs = static_cast<Base const&>(other);
171 template <class... Args>
172 std::pair<iterator, bool> emplace(Args&&... args) {
173 auto key = StringPiece(std::forward<Args>(args)...);
176 ? std::make_pair(it, false)
177 : Base::emplace(stringPieceDup(key, get_allocator()));
180 std::pair<iterator, bool> insert(value_type val) {
183 ? std::make_pair(it, false)
184 : Base::insert(stringPieceDup(val, get_allocator()));
187 iterator erase(const_iterator position) {
188 auto key = *position;
189 auto result = Base::erase(position);
190 stringPieceDel(key, get_allocator());
194 size_type erase(folly::StringPiece key) {
203 void clear() noexcept {
204 for (auto& it : *this) {
205 stringPieceDel(it, get_allocator());
211 using Base::hash_function;
213 using Base::get_allocator;
214 using Base::bucket_count;
215 using Base::max_bucket_count;
216 using Base::bucket_size;
219 void swap(BasicStringKeyedUnorderedSet& other) & {
220 return Base::swap(other);
223 ~BasicStringKeyedUnorderedSet() {
224 // Here we assume that unordered_set doesn't use keys in destructor
225 for (auto& it : *this) {
226 stringPieceDel(it, get_allocator());
231 typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet;