folly/folly/container/SparseByteSet.h

/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#pragma once

#include <cassert>
#include <cstdint>

#include <folly/CPortability.h>

namespace folly {

/***
 *  SparseByteSet
 *
 *  A special-purpose data structure representing a set of bytes.
 *  May have better performance than std::bitset<256>, depending on workload.
 *
 *  Operations:
 *  - add(byte)
 *  - remove(byte)
 *  - contains(byte)
 *  - clear()
 *
 *  Performance:
 *  - The entire capacity of the set is inline; the set never allocates.
 *  - The constructor zeros only the first two bytes of the object.
 *  - add and contains both run in constant time w.r.t. the size of the set.
 *    Constant time - not amortized constant - and with small constant factor.
 *
 *  This data structure is ideal for on-stack use.
 *
 *  Aho, Hopcroft, and Ullman refer to this trick in "The Design and Analysis
 *  of Computer Algorithms" (1974), but the best description is here:
 *  http://research.swtch.com/sparse
 *  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.7319
 */
class SparseByteSet { … };

} // namespace folly