folly/container/SparseByteSet.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
  17 #pragma once
  18
  19 #include <cstdint>
  20
  21 #include <glog/logging.h>
  22
  23 namespace folly {
  24
  25 /***
  26  *  SparseByteSet
  27  *
  28  *  A special-purpose data structure representing an insert-only set of bytes.
  29  *  May have better performance than std::bitset<256>, depending on workload.
  30  *
  31  *  Operations:
  32  *  - add(byte)
  33  *  - contains(byte)
  34  *
  35  *  Performance:
  36  *  - The entire capacity of the set is inline; the set never allocates.
  37  *  - The constructor zeros only the first two bytes of the object.
  38  *  - add and contains both run in constant time w.r.t. the size of the set.
  39  *    Constant time - not amortized constant - and with small constant factor.
  40  *
  41  *  This data structure is ideal for on-stack use.
  42  *
  43  *  Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
  44  *  of Computer Algorithms" (1974), but the best description is here:
  45  *  http://research.swtch.com/sparse
  46  *  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319
  47  */
  48 class SparseByteSet {
  49  public:
  50   //  There are this many possible values:
  51   static constexpr uint16_t kCapacity = 256;
  52
  53   //  No init of byte-arrays required!
  54   SparseByteSet() : size_(0) { }
  55
  56   /***
  57    *  add(byte)
  58    *
  59    *  O(1), non-amortized.
  60    */
  61   inline bool add(uint8_t i) {
  62     bool r = !contains(i);
  63     if (r) {
  64       DCHECK_LT(size_, kCapacity);
  65       dense_[size_] = i;
  66       sparse_[i] = uint8_t(size_);
  67       size_++;
  68     }
  69     return r;
  70   }
  71
  72   /***
  73    *  contains(byte)
  74    *
  75    *  O(1), non-amortized.
  76    */
  77   inline bool contains(uint8_t i) const {
  78     return sparse_[i] < size_ && dense_[sparse_[i]] == i;
  79   }
  80
  81  private:
  82   uint16_t size_;  // can't use uint8_t because it would overflow if all
  83                    // possible values were inserted.
  84   uint8_t sparse_[kCapacity];
  85   uint8_t dense_[kCapacity];
  86 };
  87
  88 }