folly/experimental/StringKeyedUnorderedSet.h

   1 /*
   2  * Copyright 2016 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 #ifndef FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_
  20 #define FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_
  21
  22 #include <initializer_list>
  23 #include <memory>
  24 #include <unordered_set>
  25 #include <folly/Range.h>
  26 #include <folly/experimental/StringKeyedCommon.h>
  27
  28 namespace folly {
  29
  30 /**
  31  * Wrapper class for unordered_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 <class Hasher = StringPieceHash,
  38           class Eq = std::equal_to<StringPiece>,
  39           class Alloc = std::allocator<folly::StringPiece>>
  40 class BasicStringKeyedUnorderedSet
  41     : private std::unordered_set<StringPiece, Hasher, Eq, Alloc> {
  42   using Base = std::unordered_set<StringPiece, Hasher, Eq, Alloc>;
  43
  44 public:
  45   typedef typename Base::key_type key_type;
  46   typedef typename Base::value_type value_type;
  47   typedef typename Base::hasher hasher;
  48   typedef typename Base::key_equal key_equal;
  49   typedef typename Base::allocator_type allocator_type;
  50   typedef typename Base::reference reference;
  51   typedef typename Base::const_reference const_reference;
  52   typedef typename Base::pointer pointer;
  53   typedef typename Base::const_pointer const_pointer;
  54   typedef typename Base::iterator iterator;
  55   typedef typename Base::const_iterator const_iterator;
  56   typedef typename Base::size_type size_type;
  57   typedef typename Base::difference_type difference_type;
  58
  59   // Constructors in the same order as in
  60   // http://cplusplus.com/reference/unordered_set/unordered_set/unordered_set/
  61   explicit BasicStringKeyedUnorderedSet() {
  62   }
  63
  64   explicit BasicStringKeyedUnorderedSet(
  65     size_type n,
  66     const hasher& hf = hasher(),
  67     const key_equal& eql = key_equal(),
  68     const allocator_type& alloc = allocator_type())
  69       : Base(n, hf, eql, alloc) {
  70   }
  71
  72   explicit BasicStringKeyedUnorderedSet(const allocator_type& alloc)
  73       : Base(alloc) {
  74   }
  75
  76   template <class InputIterator>
  77   BasicStringKeyedUnorderedSet(InputIterator b, InputIterator e) {
  78     for (; b != e; ++b) {
  79       emplace(*b);
  80     }
  81   }
  82
  83   template <class InputIterator>
  84   BasicStringKeyedUnorderedSet(
  85     InputIterator b, InputIterator e,
  86     size_type n,
  87     const hasher& hf = hasher(),
  88     const key_equal& eql = key_equal(),
  89     const allocator_type& alloc = allocator_type())
  90       : Base(n, hf, eql, alloc) {
  91     for (; b != e; ++b) {
  92       emplace(*b);
  93     }
  94   }
  95
  96   BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs)
  97       : BasicStringKeyedUnorderedSet(rhs, rhs.get_allocator()) {
  98   }
  99
 100   BasicStringKeyedUnorderedSet(const BasicStringKeyedUnorderedSet& rhs,
 101                                const allocator_type& a)
 102       : BasicStringKeyedUnorderedSet(rhs.begin(),
 103                                      rhs.end(),
 104                                      rhs.bucket_count(),
 105                                      rhs.hash_function(),
 106                                      rhs.key_eq(),
 107                                      a) {
 108   }
 109
 110   BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs) noexcept
 111       : Base(std::move(rhs)) {
 112     assert(rhs.empty());
 113   }
 114
 115   BasicStringKeyedUnorderedSet(BasicStringKeyedUnorderedSet&& rhs,
 116                                const allocator_type& /* a */) noexcept
 117       : Base(std::move(rhs) /* , a */ /* not supported by gcc */) {
 118     assert(rhs.empty());
 119   }
 120
 121   BasicStringKeyedUnorderedSet(std::initializer_list<value_type> il)
 122       : BasicStringKeyedUnorderedSet(il.begin(), il.end()) {
 123   }
 124
 125   BasicStringKeyedUnorderedSet(
 126     std::initializer_list<value_type> il,
 127     size_type n,
 128     const hasher& hf = hasher(),
 129     const key_equal& eql = key_equal(),
 130     const allocator_type& alloc = allocator_type())
 131       : BasicStringKeyedUnorderedSet(il.begin(), il.end(), n, hf, eql, alloc) {
 132   }
 133
 134   BasicStringKeyedUnorderedSet&
 135   operator=(const BasicStringKeyedUnorderedSet& rhs) & {
 136     if (this == &rhs) {
 137       return *this;
 138     }
 139     // Cost is as bad as a full copy, so to it via copy + move
 140     return *this = BasicStringKeyedUnorderedSet(rhs);
 141   }
 142
 143   BasicStringKeyedUnorderedSet&
 144   operator=(BasicStringKeyedUnorderedSet&& rhs) & noexcept {
 145     assert(this != &rhs);
 146     clear();
 147     Base::operator=(std::move(rhs));
 148     return *this;
 149   }
 150
 151   using Base::empty;
 152   using Base::size;
 153   using Base::max_size;
 154   using Base::begin;
 155   using Base::end;
 156   using Base::cbegin;
 157   using Base::cend;
 158   using Base::find;
 159
 160   bool operator==(const BasicStringKeyedUnorderedSet& rhs) const {
 161     const Base& lhs = *this;
 162     return lhs == rhs;
 163   }
 164
 165   template <class... Args>
 166   std::pair<iterator, bool> emplace(Args&&... args) {
 167     auto key = StringPiece(std::forward<Args>(args)...);
 168     auto it = find(key);
 169     return it != end()
 170       ? std::make_pair(it, false)
 171       : Base::emplace(stringPieceDup(key, get_allocator()));
 172   }
 173
 174   std::pair<iterator, bool> insert(value_type val) {
 175     auto it = find(val);
 176     return it != end()
 177       ? std::make_pair(it, false)
 178       : Base::insert(stringPieceDup(val, get_allocator()));
 179   }
 180
 181   iterator erase(const_iterator position) {
 182     auto key = *position;
 183     auto result = Base::erase(position);
 184     stringPieceDel(key, get_allocator());
 185     return result;
 186   }
 187
 188   size_type erase(folly::StringPiece key) {
 189     auto it = find(key);
 190     if (it == end()) {
 191       return 0;
 192     }
 193     erase(it);
 194     return 1;
 195   }
 196
 197   void clear() noexcept {
 198     for (auto& it : *this) {
 199       stringPieceDel(it, get_allocator());
 200     }
 201     Base::clear();
 202   }
 203
 204   using Base::reserve;
 205   using Base::hash_function;
 206   using Base::key_eq;
 207   using Base::get_allocator;
 208   using Base::bucket_count;
 209   using Base::max_bucket_count;
 210   using Base::bucket_size;
 211   using Base::bucket;
 212
 213   ~BasicStringKeyedUnorderedSet() {
 214     // Here we assume that unordered_set doesn't use keys in destructor
 215     for (auto& it : *this) {
 216       stringPieceDel(it, get_allocator());
 217     }
 218   }
 219 };
 220
 221 typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet;
 222
 223 } // folly
 224
 225 #endif /* FOLLY_EXPERIMENTAL_STRINGKEYEDUNORDEREDSET_H_ */