sparse_vector.h | Explore in Territory

// Copyright 2023 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_SPARSE_VECTOR_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_SPARSE_VECTOR_H_

#include <limits>
#include <type_traits>

#include "third_party/blink/renderer/platform/heap/collection_support/heap_vector.h"
#include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"

namespace blink {

namespace internal {

template <typename VectorType>
class NonTraceableSparseVectorFields { … };

template <typename VectorType>
class TraceableSparseVectorFields { … };

}  // namespace internal

// This class is logically like an array of FieldType instances, indexed by the
// FieldId enum, but is optimized to save memory when only a small number of
// the possible fields are being used.
//
// This class is implemented using a vector containing the FieldType instances
// that are being used, and a bitfield to indicate which fields are being used.
// The popcount cpu instruction is critical for the O(1) lookup performance, as
// and allows us to determine the vector index of a field using the bitfield.
// For example:
// enum class FieldId {
//   kFirst = 0, ... kMiddle = 7, ... kLast = 15, kNumFields = kLast + 1,
// }
// SparseVector<FieldId, int> sparse_vector;
// A sparse vector with kFirst, kMiddle, and kLast populated will have:
// fields_bitfield_: 0b00000000000000001000000100000001
// Vector: [int for kFirst, int for kMiddle, int for kLast]
//
// Template parameters:
//   FieldId: must be an enum type (enforced below) and have a kNumFields entry
//            with value equal to 1 + maximum value in the enum.
//   FieldType: the intention is that it can be an arbitrary type, typically
//              either an class or a managed pointer to a class.
//   inline_capacity (optional): size of the inline buffer.
//   VectorType (optional): The type of the internal vector.
//   BitfieldType (optional): The type of the internal bitfield. Must be big
//                            enough to contain FieldId::kNumFields bits.
//
// Time complexity:
//   Query: O(1)
//   Modify existing field: O(1)
//   Add/erase: O(1) (at the end of the vector) to O(N) (N = number of
//              existing fields)
// It's efficient when the number of existing fields is much smaller than
// FieldId::kNumFields, add/erase operations mostly happen at the end of the
// vector, and the set of existing fields seldom changes.
template <typename FieldId,
          typename FieldType,
          wtf_size_t inline_capacity = 0,
          typename VectorType =
              std::conditional_t<WTF::IsMemberType<FieldType>::value ||
                                     WTF::IsTraceable<FieldType>::value,
                                 HeapVector<FieldType, inline_capacity>,
                                 Vector<FieldType, inline_capacity>>,
          typename BitfieldType =
              std::conditional_t<static_cast<unsigned>(FieldId::kNumFields) <=
                                     std::numeric_limits<uint32_t>::digits,
                                 uint32_t,
                                 uint64_t>>
class SparseVector :
    // The conditional inheritance approach prevents types like
    // SparseVector<Enum, int> from being treated as traceable by the blinkgc
    // clang plugin. `requires` clause on the `Trace` method doesn't work.
    public std::conditional_t<
        WTF::IsTraceable<VectorType>::value,
        internal::TraceableSparseVectorFields<VectorType>,
        internal::NonTraceableSparseVectorFields<VectorType>> {
  static_assert(std::is_enum_v<FieldId>);
  static_assert(std::is_unsigned_v<BitfieldType>);
  static_assert(std::numeric_limits<BitfieldType>::digits >=
                    static_cast<unsigned>(FieldId::kNumFields),
                "BitfieldType must be big enough to have a bit for each "
                "field in FieldId.");
  static_assert(inline_capacity <= static_cast<unsigned>(FieldId::kNumFields));

 public:
  wtf_size_t capacity() const { … }
  wtf_size_t size() const { … }
  bool empty() const { … }

  void reserve(wtf_size_t capacity) { … }

  void clear() { … }

  // Returns whether the field exists. Time complexity is O(1).
  bool HasField(FieldId field_id) const { … }

  // Returns the value of existing field. Time complexity is O(1).
  const FieldType& GetField(FieldId field_id) const { … }
  FieldType& GetField(FieldId field_id) { … }

  // Adds a field if it's not existing (time complexity is O(1) (if the new
  // field is at the end) to O(N) (N = number of existing fields)), or modifies
  // the existing field (time complexity is O(1)).
  void SetField(FieldId field_id, FieldType&& field) { … }

  // Erases a field. Returns `true` if the field was previously existing and
  // is actually erased. Time complexity is O(1) (if the field doesn't exist
  // or the erased field is at the end) to O(N) (N = number of existing fields).
  bool EraseField(FieldId field_id) { … }

 private:
  static BitfieldType FieldIdMask(FieldId field_id) { … }

  // Returns the index in `fields_` that `field_id` is stored in. If `fields_`
  // isn't storing a field for `field_id`, then this returns the index which
  // the data for `field_id` should be inserted into.
  wtf_size_t GetFieldIndex(FieldId field_id) const { … }

  BitfieldType fields_bitfield_ = 0;
};

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_SPARSE_VECTOR_H_
chromium/third_party/blink/renderer/platform/sparse_vector.h
