folly/folly/concurrency/container/SingleWriterFixedHashMap.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 <atomic>

#include <folly/lang/Bits.h>

#include <glog/logging.h>

namespace folly {

/// SingleWriterFixedHashMap:
///
/// Minimal single-writer fixed hash map implementation that supports:
/// - Copy construction with optional capacity expansion.
/// - Concurrent read-only lookup.
/// - Concurrent read-only iteration.
///
/// Assumes that higher level code:
/// - Checks availability of empty slots before calling insert
/// - Manages expansion and/or cleanup of tombstones
///
/// Notes on algorithm:
/// - Tombstones are used to mark previously occupied slots.
/// - A slot with a tombstone can only be reused for the same key. The
///   reason for that is to enforce that once a key occupies a slot,
///   that key cannot use any other slot for the lifetime of the
///   map. This is to guarantee that when readers iterate over the map
///   they do not encounter any key more than once.
///
/// Writer-only operations:
/// - insert()
/// - erase()
/// - used()
/// - available()
///
/// This implementation guarantees that a copy from a map with
/// tombstones will have at least one available empty element.
///
template <typename Key, typename Value>
class SingleWriterFixedHashMap { … }; // SingleWriterFixedHashMap

} // namespace folly