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
17#pragma once
18
19#include <cstdint>
20
21#include <glog/logging.h>
22
23namespace 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 */
48class 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} // namespace folly
89