Make StringKeyed* more complete
[folly.git] / folly / experimental / StringKeyedSet.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 <initializer_list>
22 #include <memory>
23 #include <set>
24 #include <folly/Range.h>
25 #include <folly/experimental/StringKeyedCommon.h>
26
27 namespace folly {
28
29 /**
30  * Wrapper class for set<string> that can
31  * perform lookup operations with StringPiece, not only string.
32  *
33  * It uses kind of hack: string pointed by StringPiece is copied when
34  * StringPiece is inserted into set
35  */
36 template <class Compare = std::less<StringPiece>,
37           class Alloc = std::allocator<StringPiece>>
38 class StringKeyedSetBase
39     : private std::set<StringPiece, Compare, Alloc> {
40 private:
41   using Base = std::set<StringPiece, Compare, Alloc>;
42
43 public:
44   typedef typename Base::key_type key_type;
45   typedef typename Base::value_type value_type;
46   typedef typename Base::key_compare key_compare;
47   typedef typename Base::allocator_type allocator_type;
48   typedef typename Base::reference reference;
49   typedef typename Base::const_reference const_reference;
50   typedef typename Base::pointer pointer;
51   typedef typename Base::const_pointer const_pointer;
52   typedef typename Base::iterator iterator;
53   typedef typename Base::const_iterator const_iterator;
54   typedef typename Base::reverse_iterator reverse_iterator;
55   typedef typename Base::const_reverse_iterator const_reverse_iterator;
56   typedef typename Base::size_type size_type;
57   typedef typename Base::difference_type difference_type;
58
59   explicit StringKeyedSetBase(
60     const key_compare& comp = key_compare(),
61     const allocator_type& alloc = allocator_type())
62       : Base(comp, alloc) {
63   }
64
65   explicit StringKeyedSetBase(const allocator_type& alloc)
66       : Base(alloc) {
67   }
68
69   template <class InputIterator>
70   StringKeyedSetBase(
71     InputIterator b, InputIterator e,
72     const key_compare& comp = key_compare(),
73     const allocator_type& alloc = allocator_type())
74       : Base(comp, alloc) {
75     for (; b != e; ++b) {
76       emplace(*b);
77     }
78   }
79
80   StringKeyedSetBase(const StringKeyedSetBase& rhs)
81       : StringKeyedSetBase(rhs, rhs.get_allocator()) {
82   }
83
84   StringKeyedSetBase(const StringKeyedSetBase& rhs,
85                      const allocator_type& a)
86       : StringKeyedSetBase(rhs.begin(), rhs.end(), rhs.key_comp(), a) {
87   }
88
89   StringKeyedSetBase(StringKeyedSetBase&& other) noexcept
90       : Base(std::move(other)) {
91     assert(other.empty());
92   }
93
94   StringKeyedSetBase(StringKeyedSetBase&& other,
95                      const allocator_type& alloc) noexcept
96       : Base(std::move(other), alloc) {
97     assert(other.empty());
98   }
99
100   StringKeyedSetBase(
101     std::initializer_list<value_type> il,
102     const key_compare& comp = key_compare(),
103     const allocator_type& alloc = allocator_type())
104       : StringKeyedSetBase(il.begin(), il.end(), comp, alloc) {
105   }
106
107   StringKeyedSetBase& operator=(const StringKeyedSetBase& other) {
108     if (this == &other) {
109       return *this;
110     }
111     return *this = StringKeyedSetBase(other);
112   }
113
114   StringKeyedSetBase& operator=(StringKeyedSetBase&& other) noexcept {
115     assert(this != &other);
116     clear();
117     Base::operator=(std::move(other));
118     assert(other.empty());
119     return *this;
120   }
121
122   using Base::empty;
123   using Base::size;
124   using Base::max_size;
125   using Base::begin;
126   using Base::end;
127   using Base::cbegin;
128   using Base::cend;
129   using Base::find;
130   using Base::count;
131   using Base::lower_bound;
132   using Base::upper_bound;
133
134   bool operator==(StringKeyedSetBase const& other) const {
135     Base const& lhs = *this;
136     Base const& rhs = static_cast<Base const&>(other);
137     return lhs == rhs;
138   }
139
140   template <class... Args>
141   std::pair<iterator, bool> emplace(Args&&... args) {
142     auto key = StringPiece(std::forward<Args>(args)...);
143     auto it = find(key);
144     if (it != end()) {
145       return {it, false};
146     }
147     return Base::emplace(stringPieceDup(key, get_allocator()));
148   }
149
150   std::pair<iterator, bool> insert(value_type val) {
151     auto it = find(val);
152     if (it != end()) {
153       return {it, false};
154     }
155     return Base::insert(stringPieceDup(val, get_allocator()));
156   }
157
158   iterator erase(const_iterator position) {
159     auto key = *position;
160     auto result = Base::erase(position);
161     stringPieceDel(key, get_allocator());
162     return result;
163   }
164
165   size_type erase(StringPiece key) {
166     auto it = find(key);
167     if (it == end()) {
168       return 0;
169     }
170     erase(it);
171     return 1;
172   }
173
174   void clear() noexcept {
175     for (auto it : *this) {
176       stringPieceDel(it, get_allocator());
177     }
178     Base::clear();
179   }
180
181   using Base::get_allocator;
182
183   void swap(StringKeyedSetBase& other) & {
184     return Base::swap(other);
185   }
186
187   ~StringKeyedSetBase() {
188     // Here we assume that set doesn't use keys in destructor
189     for (auto it : *this) {
190       stringPieceDel(it, get_allocator());
191     }
192   }
193 };
194
195 using StringKeyedSet = StringKeyedSetBase<>;
196
197 } // folly