1 /* 2 * Copyright (c) Facebook, Inc. and its affiliates. 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 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 28 namespace 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 */ 37 template < 38 class Compare = std::less<StringPiece>, 39 class Alloc = std::allocator<StringPiece>> 40 class 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()) Base(comp,alloc)63 : Base(comp, alloc) {} 64 StringKeyedSetBase(const allocator_type & alloc)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()) Base(comp,alloc)73 : Base(comp, alloc) { 74 for (; b != e; ++b) { 75 emplace(*b); 76 } 77 } 78 StringKeyedSetBase(const StringKeyedSetBase & rhs)79 StringKeyedSetBase(const StringKeyedSetBase& rhs) 80 : StringKeyedSetBase(rhs, rhs.get_allocator()) {} 81 StringKeyedSetBase(const StringKeyedSetBase & rhs,const allocator_type & a)82 StringKeyedSetBase(const StringKeyedSetBase& rhs, const allocator_type& a) 83 : StringKeyedSetBase(rhs.begin(), rhs.end(), rhs.key_comp(), a) {} 84 StringKeyedSetBase(StringKeyedSetBase && other)85 StringKeyedSetBase(StringKeyedSetBase&& other) noexcept 86 : Base(std::move(other)) { 87 assert(other.empty()); 88 } 89 StringKeyedSetBase(StringKeyedSetBase && other,const allocator_type & alloc)90 StringKeyedSetBase( 91 StringKeyedSetBase&& other, const allocator_type& alloc) noexcept 92 : Base(std::move(other), alloc) { 93 assert(other.empty()); 94 } 95 96 StringKeyedSetBase( 97 std::initializer_list<value_type> il, 98 const key_compare& comp = key_compare(), 99 const allocator_type& alloc = allocator_type()) 100 : StringKeyedSetBase(il.begin(), il.end(), comp, alloc) {} 101 102 StringKeyedSetBase& operator=(const StringKeyedSetBase& other) { 103 if (this == &other) { 104 return *this; 105 } 106 return *this = StringKeyedSetBase(other); 107 } 108 109 StringKeyedSetBase& operator=(StringKeyedSetBase&& other) noexcept { 110 assert(this != &other); 111 clear(); 112 Base::operator=(std::move(other)); 113 assert(other.empty()); 114 return *this; 115 } 116 117 using Base::begin; 118 using Base::cbegin; 119 using Base::cend; 120 using Base::count; 121 using Base::empty; 122 using Base::end; 123 using Base::find; 124 using Base::lower_bound; 125 using Base::max_size; 126 using Base::size; 127 using Base::upper_bound; 128 129 bool operator==(StringKeyedSetBase const& other) const { 130 Base const& lhs = *this; 131 Base const& rhs = static_cast<Base const&>(other); 132 return lhs == rhs; 133 } 134 135 template <class... Args> emplace(Args &&...args)136 std::pair<iterator, bool> emplace(Args&&... args) { 137 auto key = StringPiece(std::forward<Args>(args)...); 138 auto it = find(key); 139 if (it != end()) { 140 return {it, false}; 141 } 142 return Base::emplace(stringPieceDup(key, get_allocator())); 143 } 144 insert(value_type val)145 std::pair<iterator, bool> insert(value_type val) { 146 auto it = find(val); 147 if (it != end()) { 148 return {it, false}; 149 } 150 return Base::insert(stringPieceDup(val, get_allocator())); 151 } 152 erase(const_iterator position)153 iterator erase(const_iterator position) { 154 auto key = *position; 155 auto result = Base::erase(position); 156 stringPieceDel(key, get_allocator()); 157 return result; 158 } 159 erase(StringPiece key)160 size_type erase(StringPiece key) { 161 auto it = find(key); 162 if (it == end()) { 163 return 0; 164 } 165 erase(it); 166 return 1; 167 } 168 clear()169 void clear() noexcept { 170 for (auto it : *this) { 171 stringPieceDel(it, get_allocator()); 172 } 173 Base::clear(); 174 } 175 176 using Base::get_allocator; 177 swap(StringKeyedSetBase & other)178 void swap(StringKeyedSetBase& other) & { return Base::swap(other); } 179 ~StringKeyedSetBase()180 ~StringKeyedSetBase() { 181 // Here we assume that set doesn't use keys in destructor 182 for (auto it : *this) { 183 stringPieceDel(it, get_allocator()); 184 } 185 } 186 }; 187 188 using StringKeyedSet = StringKeyedSetBase<>; 189 190 } // namespace folly 191