4fc1b71032ac4dbd7881b686e202b7d3fccf1240
[folly.git] / folly / experimental / StringKeyedUnorderedSet.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 <functional>
22 #include <initializer_list>
23 #include <memory>
24 #include <unordered_set>
25 #include <utility>
26
27 #include <folly/Hash.h>
28 #include <folly/Range.h>
29 #include <folly/experimental/StringKeyedCommon.h>
30
31 namespace folly {
32
33 /**
34  * Wrapper class for unordered_set<string> that can
35  * perform lookup operations with StringPiece, not only string.
36  *
37  * It uses kind of hack: string pointed by StringPiece is copied when
38  * StringPiece is inserted into set
39  */
40 template <
41     class Hasher = Hash,
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>;
47
48  public:
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;
62
63   // Constructors in the same order as in
64   // http://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/
65   explicit BasicStringKeyedUnorderedSet() {
66   }
67
68   explicit BasicStringKeyedUnorderedSet(
69     size_type n,
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) {
74   }
75
76   explicit BasicStringKeyedUnorderedSet(const allocator_type& alloc)
77       : Base(alloc) {
78   }
79
80   template <class InputIterator>
81   BasicStringKeyedUnorderedSet(InputIterator b, InputIterator e) {
82     for (; b != e; ++b) {
83       emplace(*b);
84     }
85   }
86
87   template <class InputIterator>
88   BasicStringKeyedUnorderedSet(
89     InputIterator b, InputIterator e,
90     size_type n,
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) {
95     for (; b != e; ++b) {
96       emplace(*b);
97     }
98   }
99
100   BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs)
101       : BasicStringKeyedUnorderedSet(rhs, rhs.get_allocator()) {
102   }
103
104   BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs,
105                                const allocator_type& a)
106       : BasicStringKeyedUnorderedSet(rhs.begin(),
107                                      rhs.end(),
108                                      rhs.bucket_count(),
109                                      rhs.hash_function(),
110                                      rhs.key_eq(),
111                                      a) {
112   }
113
114   BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs) noexcept
115       : Base(std::move(rhs)) {
116     assert(rhs.empty());
117   }
118
119   BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs,
120                                const allocator_type& /* a */) noexcept
121       : Base(std::move(rhs) /* , a */ /* not supported by gcc */) {
122     assert(rhs.empty());
123   }
124
125   BasicStringKeyedUnorderedSet(std::initializer_list<value_type> il)
126       : BasicStringKeyedUnorderedSet(il.begin(), il.end()) {
127   }
128
129   BasicStringKeyedUnorderedSet(
130     std::initializer_list<value_type> il,
131     size_type n,
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) {
136   }
137
138   BasicStringKeyedUnorderedSet&
139   operator=(const BasicStringKeyedUnorderedSet& rhs) & {
140     if (this == &rhs) {
141       return *this;
142     }
143     // Cost is as bad as a full copy, so to it via copy + move
144     return *this = BasicStringKeyedUnorderedSet(rhs);
145   }
146
147   BasicStringKeyedUnorderedSet&
148   operator=(BasicStringKeyedUnorderedSet&& rhs) & noexcept {
149     assert(this != &rhs);
150     clear();
151     Base::operator=(std::move(rhs));
152     return *this;
153   }
154
155   using Base::empty;
156   using Base::size;
157   using Base::max_size;
158   using Base::begin;
159   using Base::end;
160   using Base::cbegin;
161   using Base::cend;
162   using Base::find;
163   using Base::count;
164
165   bool operator==(const BasicStringKeyedUnorderedSet& other) const {
166     Base const& lhs = *this;
167     Base const& rhs = static_cast<Base const&>(other);
168     return lhs == rhs;
169   }
170
171   template <class... Args>
172   std::pair<iterator, bool> emplace(Args&&... args) {
173     auto key = StringPiece(std::forward<Args>(args)...);
174     auto it = find(key);
175     return it != end()
176       ? std::make_pair(it, false)
177       : Base::emplace(stringPieceDup(key, get_allocator()));
178   }
179
180   std::pair<iterator, bool> insert(value_type val) {
181     auto it = find(val);
182     return it != end()
183       ? std::make_pair(it, false)
184       : Base::insert(stringPieceDup(val, get_allocator()));
185   }
186
187   iterator erase(const_iterator position) {
188     auto key = *position;
189     auto result = Base::erase(position);
190     stringPieceDel(key, get_allocator());
191     return result;
192   }
193
194   size_type erase(folly::StringPiece key) {
195     auto it = find(key);
196     if (it == end()) {
197       return 0;
198     }
199     erase(it);
200     return 1;
201   }
202
203   void clear() noexcept {
204     for (auto& it : *this) {
205       stringPieceDel(it, get_allocator());
206     }
207     Base::clear();
208   }
209
210   using Base::reserve;
211   using Base::hash_function;
212   using Base::key_eq;
213   using Base::get_allocator;
214   using Base::bucket_count;
215   using Base::max_bucket_count;
216   using Base::bucket_size;
217   using Base::bucket;
218
219   void swap(BasicStringKeyedUnorderedSet& other) & {
220     return Base::swap(other);
221   }
222
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());
227     }
228   }
229 };
230
231 typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet;
232
233 } // folly