chromium/v8/src/base/intrusive-set.h

// Copyright 2023 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_BASE_INTRUSIVE_SET_H_
#define V8_BASE_INTRUSIVE_SET_H_

#include <iterator>
#include <limits>
#include <type_traits>

#include "src/base/logging.h"

namespace v8::base {

class IntrusiveSetIndex { … };

// A set of pointer-like values (`T`) that point to memory containing the
// position inside of the set (`IntrusiveSetIndex`), to allow for O(1) insertion
// and removal without using a hash table. This set is intrusive in the sense
// that elements need to know their position inside of the set by storing an
// `IntrusiveSetIndex` somewhere. In particular, all copies of a `T` value
// should point to the same `IntrusiveSetIndex` instance. `GetIntrusiveSetIndex`
// has to be a functor that produces `IntrusiveSetIndex&` given a `T`. The
// reference has to remain valid and refer to the same memory location while the
// element is in the set and until we finish iterating over the data structure
// if the element is removed during iteration.
//
// Add(T):     amortized O(1)
// Contain(T): O(1)
// Remove(T):  O(1)
template <class T, class GetIntrusiveSetIndex, class Container>
class IntrusiveSet { … };

}  // namespace v8::base

#endif  // V8_BASE_INTRUSIVE_SET_H_