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