2 * Copyright 2016 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_FAST_BYTE_SET_H_
18 #define FOLLY_FAST_BYTE_SET_H_
21 #include <glog/logging.h>
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.
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.
41 * This data structure is ideal for on-stack use.
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
50 // There are this many possible values:
51 static constexpr uint16_t kCapacity = 256;
53 // No init of byte-arrays required!
54 SparseByteSet() : size_(0) { }
59 * O(1), non-amortized.
61 inline bool add(uint8_t i) {
62 bool r = !contains(i);
64 DCHECK_LT(size_, kCapacity);
75 * O(1), non-amortized.
77 inline bool contains(uint8_t i) const {
78 return sparse_[i] < size_ && dense_[sparse_[i]] == i;
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];