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
 164   bool operator==(const BasicStringKeyedUnorderedSet& rhs) const {
 165     const Base& lhs = *this;
 166     return lhs == rhs;
 167   }
 168
 169   template <class... Args>
 170   std::pair<iterator, bool> emplace(Args&&... args) {
 171     auto key = StringPiece(std::forward<Args>(args)...);
 172     auto it = find(key);
 173     return it != end()
 174       ? std::make_pair(it, false)
 175       : Base::emplace(stringPieceDup(key, get_allocator()));
 176   }
 177
 178   std::pair<iterator, bool> insert(value_type val) {
 179     auto it = find(val);
 180     return it != end()
 181       ? std::make_pair(it, false)
 182       : Base::insert(stringPieceDup(val, get_allocator()));
 183   }
 184
 185   iterator erase(const_iterator position) {
 186     auto key = *position;
 187     auto result = Base::erase(position);
 188     stringPieceDel(key, get_allocator());
 189     return result;
 190   }
 191
 192   size_type erase(folly::StringPiece key) {
 193     auto it = find(key);
 194     if (it == end()) {
 195       return 0;
 196     }
 197     erase(it);
 198     return 1;
 199   }
 200
 201   void clear() noexcept {
 202     for (auto& it : *this) {
 203       stringPieceDel(it, get_allocator());
 204     }
 205     Base::clear();
 206   }
 207
 208   using Base::reserve;
 209   using Base::hash_function;
 210   using Base::key_eq;
 211   using Base::get_allocator;
 212   using Base::bucket_count;
 213   using Base::max_bucket_count;
 214   using Base::bucket_size;
 215   using Base::bucket;
 216
 217   ~BasicStringKeyedUnorderedSet() {
 218     // Here we assume that unordered_set doesn't use keys in destructor
 219     for (auto& it : *this) {
 220       stringPieceDel(it, get_allocator());
 221     }
 222   }
 223 };
 224
 225 typedef BasicStringKeyedUnorderedSet<> StringKeyedUnorderedSet;
 226
 227 } // folly