folly/folly/synchronization/detail/HazptrUtils.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 <thread>

#include <glog/logging.h>

#include <folly/Portability.h>
#include <folly/synchronization/detail/Sleeper.h>

/// Linked list class templates used in the hazard pointer library:
/// - linked_list: Sequential linked list that uses pre-existing
///   members next() and set_next();.
/// - shared_head_tail_list: Thread-safe linked list that maintains
///   head and tail pointers. Supports push and pop_all.
/// - shared_head_only_list: Thread-safe linked lockable list that
///   maintains only a head pointer. Supports push and pop_all.

namespace folly {
namespace hazptr_detail {

/**
 *  linked_list
 *
 *  Template parameter Node must support set_next
 *
 */
template <typename Node>
class linked_list { … }; // linked_list

/**
 *  shared_head_tail_list
 *
 *  Maintains head and tail pointers. Supports push and pop all
 *  operations. Pop all operation is wait-free.
 */
template <typename Node, template <typename> class Atom = std::atomic>
class shared_head_tail_list { … }; // shared_head_tail_list

/**
 *  shared_head_only_list
 *
 *  A shared singly linked list that maintains only a head pointer. It
 *  supports pop all and push list operations. Optionally the list may
 *  be locked for pop all operations. Pop all operations have locked
 *  and wait-free variants. Push operations are always lock-free.
 *
 *  Not all combinations of operationsa are mutually operable. The
 *  following are valid combinations:
 *  - push(kMayBeLocked), pop_all(kAlsoLock), push_unlock
 *  - push(kMayNotBeLocked), pop_all(kDontLock)
 *
 *  Locking is reentrant to prevent self deadlock.
 */
template <typename Node, template <typename> class Atom = std::atomic>
class shared_head_only_list { … }; // shared_head_only_list

} // namespace hazptr_detail
} // namespace folly