1
    2
    3
    4
    5
    6
    7
    8
    9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50
   51
   52
   53
   54
   55
   56
   57
   58
   59
   60
   61
   62
   63
   64
   65
   66
   67
   68
   69
   70
   71
   72
   73
   74
   75
   76
   77
   78
   79
   80
   81
   82
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97
   98
   99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197

cc / base / list_container_helper.h [blame]

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

#ifndef CC_BASE_LIST_CONTAINER_HELPER_H_
#define CC_BASE_LIST_CONTAINER_HELPER_H_

#include <stddef.h>

#include <memory>

#include "base/memory/raw_ptr_exclusion.h"
#include "cc/base/base_export.h"

namespace cc {

// Helper class for ListContainer non-templated logic. All methods are private,
// and only exposed to friend classes.
// For usage, see comments in ListContainer (list_container.h).
class CC_BASE_EXPORT ListContainerHelper final {
 private:
  template <typename T>
  friend class ListContainer;

  explicit ListContainerHelper(size_t alignment,
                               size_t max_size_for_derived_class,
                               size_t num_of_elements_to_reserve_for);
  ListContainerHelper(const ListContainerHelper&) = delete;
  ~ListContainerHelper();

  ListContainerHelper& operator=(const ListContainerHelper&) = delete;

  // This class deals only with char* and void*. It does allocation and passing
  // out raw pointers, as well as memory deallocation when being destroyed.
  class CharAllocator;

  // This class points to a certain position inside memory of
  // CharAllocator. It is a base class for ListContainer iterators.
  struct CC_BASE_EXPORT PositionInCharAllocator {
    // `ptr_to_container` is not a raw_ptr<...> for performance reasons (based
    // on analysis of sampling profiler data and tab_search:top100:2020).
    RAW_PTR_EXCLUSION CharAllocator* ptr_to_container = nullptr;

    size_t vector_index = 0;

    // `item_iterator` is not a raw_ptr<...> for performance reasons (based on
    // analysis of sampling profiler data and tab_search:top100:2020).
    RAW_PTR_EXCLUSION char* item_iterator = nullptr;

    PositionInCharAllocator() = default;

    PositionInCharAllocator(const PositionInCharAllocator& other);
    PositionInCharAllocator& operator=(const PositionInCharAllocator& other);

    PositionInCharAllocator(CharAllocator* container,
                            size_t vector_ind,
                            char* item_iter);

    bool operator==(const PositionInCharAllocator& other) const;
    bool operator!=(const PositionInCharAllocator& other) const;

    PositionInCharAllocator Increment();
    PositionInCharAllocator ReverseIncrement();
  };

  // Iterator classes that can be used to access data.
  /////////////////////////////////////////////////////////////////
  class CC_BASE_EXPORT Iterator : public PositionInCharAllocator {
    // This class is only defined to forward iterate through
    // CharAllocator.
   public:
    Iterator() = default;

    Iterator(CharAllocator* container,
             size_t vector_ind,
             char* item_iter,
             size_t index);
    ~Iterator();

    size_t index() const;

   protected:
    // This is used to track how many increment has happened since begin(). It
    // is used to avoid double increment at places an index reference is
    // needed. For iterator this means begin() corresponds to index 0 and end()
    // corresponds to index |size|.
    size_t index_ = 0;
  };

  class CC_BASE_EXPORT ConstIterator : public PositionInCharAllocator {
    // This class is only defined to forward iterate through
    // CharAllocator.
   public:
    ConstIterator() = default;

    ConstIterator(CharAllocator* container,
                  size_t vector_ind,
                  char* item_iter,
                  size_t index);
    ConstIterator(const Iterator& other);  // NOLINT
    ~ConstIterator();

    size_t index() const;

   protected:
    // This is used to track how many increment has happened since begin(). It
    // is used to avoid double increment at places an index reference is
    // needed. For iterator this means begin() corresponds to index 0 and end()
    // corresponds to index |size|.
    size_t index_ = 0;
  };

  class CC_BASE_EXPORT ReverseIterator : public PositionInCharAllocator {
    // This class is only defined to reverse iterate through
    // CharAllocator.
   public:
    ReverseIterator() = default;

    ReverseIterator(CharAllocator* container,
                    size_t vector_ind,
                    char* item_iter,
                    size_t index);
    ~ReverseIterator();

    size_t index() const;

   protected:
    // This is used to track how many increment has happened since rbegin(). It
    // is used to avoid double increment at places an index reference is
    // needed. For reverse iterator this means rbegin() corresponds to index 0
    // and rend() corresponds to index |size|.
    size_t index_ = 0;
  };

  class CC_BASE_EXPORT ConstReverseIterator : public PositionInCharAllocator {
    // This class is only defined to reverse iterate through
    // CharAllocator.
   public:
    ConstReverseIterator() = default;

    ConstReverseIterator(CharAllocator* container,
                         size_t vector_ind,
                         char* item_iter,
                         size_t index);
    ConstReverseIterator(const ReverseIterator& other);  // NOLINT
    ~ConstReverseIterator();

    size_t index() const;

   protected:
    // This is used to track how many increment has happened since rbegin(). It
    // is used to avoid double increment at places an index reference is
    // needed. For reverse iterator this means rbegin() corresponds to index 0
    // and rend() corresponds to index |size|.
    size_t index_ = 0;
  };

  // Unlike the ListContainer methods, these do not invoke element destructors.
  void RemoveLast();
  void EraseAndInvalidateAllPointers(Iterator* position);
  void InsertBeforeAndInvalidateAllPointers(Iterator* position,
                                            size_t number_of_elements);

  ConstReverseIterator crbegin() const;
  ConstReverseIterator crend() const;
  ReverseIterator rbegin();
  ReverseIterator rend();
  ConstIterator cbegin() const;
  ConstIterator cend() const;
  Iterator begin();
  Iterator end();

  Iterator IteratorAt(size_t index);
  ConstIterator IteratorAt(size_t index) const;

  size_t size() const;
  bool empty() const;

  size_t MaxSizeForDerivedClass() const;

  size_t GetCapacityInBytes() const;

  // Unlike the ListContainer method, this one does not invoke element
  // destructors.
  void clear();

  size_t AvailableSizeWithoutAnotherAllocationForTesting() const;

  // Hands out memory location for an element at the end of data structure.
  void* Allocate(size_t alignment, size_t size_of_actual_element_in_bytes);

  std::unique_ptr<CharAllocator> data_;
};

}  // namespace cc

#endif  // CC_BASE_LIST_CONTAINER_HELPER_H_