folly/experimental/StringKeyedSet.h

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