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 | |
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 | } // namespace folly |
89 | |