junrushao1994 commented on a change in pull request #5585:
URL: https://github.com/apache/incubator-tvm/pull/5585#discussion_r426002612
##########
File path: include/tvm/runtime/container.h
##########
@@ -188,6 +188,709 @@ class InplaceArrayBase {
return data_start + idx * sizeof(ElemType);
}
};
+} // namespace runtime
+} // namespace tvm
+
+namespace tvm {
+namespace runtime {
+
+/*!
+ * \brief iterator adapter that adapts TIter to return another type.
+ * \tparam Converter a struct that contains converting function
+ * \tparam TIter the content iterator type.
+ */
+template <typename Converter, typename TIter>
+class IterAdapter {
+ public:
+ using difference_type = typename
std::iterator_traits<TIter>::difference_type;
+ using value_type = typename Converter::ResultType;
+ using pointer = typename Converter::ResultType*;
+ using reference = typename Converter::ResultType&; // NOLINT(*)
+ using iterator_category = typename
std::iterator_traits<TIter>::iterator_category;
+
+ explicit IterAdapter(TIter iter) : iter_(iter) {}
+ inline IterAdapter& operator++() {
+ ++iter_;
+ return *this;
+ }
+ inline IterAdapter& operator--() {
+ --iter_;
+ return *this;
+ }
+ inline IterAdapter& operator++(int) {
+ IterAdapter copy = *this;
+ ++iter_;
+ return copy;
+ }
+ inline IterAdapter& operator--(int) {
+ IterAdapter copy = *this;
+ --iter_;
+ return copy;
+ }
+
+ inline IterAdapter operator+(difference_type offset) const { return
IterAdapter(iter_ + offset); }
+
+ template <typename T = IterAdapter>
+ typename std::enable_if<std::is_same<iterator_category,
std::random_access_iterator_tag>::value,
+ typename T::difference_type>::type inline
+ operator-(const IterAdapter& rhs) const {
+ return iter_ - rhs.iter_;
+ }
+
+ inline bool operator==(IterAdapter other) const { return iter_ ==
other.iter_; }
+ inline bool operator!=(IterAdapter other) const { return !(*this == other); }
+ inline const value_type operator*() const { return
Converter::convert(*iter_); }
+
+ private:
+ TIter iter_;
+};
+
+/*!
+ * \brief iterator adapter that adapts TIter to return another type.
+ * \tparam Converter a struct that contains converting function
+ * \tparam TIter the content iterator type.
+ */
+template <typename Converter, typename TIter>
+class ReverseIterAdapter {
+ public:
+ using difference_type = typename
std::iterator_traits<TIter>::difference_type;
+ using value_type = typename Converter::ResultType;
+ using pointer = typename Converter::ResultType*;
+ using reference = typename Converter::ResultType&; // NOLINT(*)
+ using iterator_category = typename
std::iterator_traits<TIter>::iterator_category;
+
+ explicit ReverseIterAdapter(TIter iter) : iter_(iter) {}
+ inline ReverseIterAdapter& operator++() {
+ --iter_;
+ return *this;
+ }
+ inline ReverseIterAdapter& operator--() {
+ ++iter_;
+ return *this;
+ }
+ inline ReverseIterAdapter& operator++(int) {
+ ReverseIterAdapter copy = *this;
+ --iter_;
+ return copy;
+ }
+ inline ReverseIterAdapter& operator--(int) {
+ ReverseIterAdapter copy = *this;
+ ++iter_;
+ return copy;
+ }
+ inline ReverseIterAdapter operator+(difference_type offset) const {
+ return ReverseIterAdapter(iter_ - offset);
+ }
+
+ template <typename T = ReverseIterAdapter>
+ typename std::enable_if<std::is_same<iterator_category,
std::random_access_iterator_tag>::value,
+ typename T::difference_type>::type inline
+ operator-(const ReverseIterAdapter& rhs) const {
+ return rhs.iter_ - iter_;
+ }
+
+ inline bool operator==(ReverseIterAdapter other) const { return iter_ ==
other.iter_; }
+ inline bool operator!=(ReverseIterAdapter other) const { return !(*this ==
other); }
+ inline const value_type operator*() const { return
Converter::convert(*iter_); }
+
+ private:
+ TIter iter_;
+};
+
+} // namespace runtime
+} // namespace tvm
+
+namespace tvm {
+
+// forward-declare a friend method of ArrayNode.
+TVM_DLL runtime::ObjectRef LoadJSON(std::string json_str);
+
+namespace runtime {
+
+/*! \brief array node content in array */
+class ArrayNode : public Object, public InplaceArrayBase<ArrayNode, ObjectRef>
{
+ public:
+ /*! \return The size of the array */
+ inline size_t size() const { return this->size_; }
+
+ /*!
+ * \brief Read i-th element from array.
+ * \param i The index
+ * \return the i-th element.
+ */
+ inline const ObjectRef at(const int64_t i) const { return
this->operator[](i); }
+
+ /*! \return begin constant iterator */
+ inline const ObjectRef* begin() const {
+ return static_cast<ObjectRef*>(InplaceArrayBase::AddressOf(0));
+ }
+
+ /*! \return end constant iterator */
+ inline const ObjectRef* end() const { return begin() + size_; }
+
+ /*!
+ * \brief Set i-th element of the array in-place
+ * \param i The index
+ * \param item The value to be set
+ */
+ inline void SetItem(const int64_t i, ObjectRef item) { this->operator[](i) =
std::move(item); }
+
+ static constexpr const uint32_t _type_index = TypeIndex::kRuntimeArray;
+ static constexpr const char* _type_key = "Array";
+ TVM_DECLARE_FINAL_OBJECT_INFO(ArrayNode, Object);
+
+ private:
+ /*! \return Size of initialized memory, used by InplaceArrayBase. */
+ size_t GetSize() const { return this->size_; }
+
+ /*!
+ * \brief Create an ArrayNode with the given capacity.
+ * \param cap Required capacity
+ * \return Ref-counted ArrayNode requested
+ */
+ static inline ObjectPtr<ArrayNode> make(const int64_t cap = INIT_SIZE) {
+ ObjectPtr<ArrayNode> p = make_inplace_array_object<ArrayNode,
ObjectRef>(cap);
+ p->capacity_ = cap;
+ p->size_ = 0;
+ return p;
+ }
+
+ /*! \return begin mutable iterator */
+ inline ObjectRef* MutableBegin() const {
+ return static_cast<ObjectRef*>(InplaceArrayBase::AddressOf(0));
+ }
+
+ /*! \return end mutable iterator */
+ inline ObjectRef* MutableEnd() const { return MutableBegin() + size_; }
+
+ /*! \brief Release reference to all the elements */
+ inline void clear() {
+ for (ObjectRef* itr = MutableEnd(); size_; --size_) {
+ (*--itr).~ObjectRef();
+ }
+ }
+
+ /*! \brief Number of elements used */
+ int64_t size_;
+
+ /*! \brief Number of elements allocated */
+ int64_t capacity_;
+
+ /*! \brief Initial size of ArrayNode */
+ static const constexpr int64_t INIT_SIZE = 16;
+
+ /*! \brief Expansion factor of the Array */
+ static const constexpr int64_t INC_FACTOR = 2;
+
+ // CRTP parent class
+ friend InplaceArrayBase<ArrayNode, ObjectRef>;
+
+ // Reference class
+ template <typename, typename>
+ friend class Array;
+
+ // To specialize make_object<ArrayNode>
+ friend ObjectPtr<ArrayNode> make_object<>();
+
+ // This method requires access to `size_` and `make`
+ friend ObjectRef tvm::LoadJSON(std::string json_str);
+};
+
+/*!
+ * \brief Array container of ObjectRef in DSL graph.
+ * Array implements copy-on-write semantics, which means array is mutable
+ * but copy will happen when array is referenced in more than two places.
+ *
+ * operator[] only provide const acces, use Set to mutate the content.
+ * \tparam T The content ObjectRef type.
+ */
+template <typename T,
+ typename = typename std::enable_if<std::is_base_of<ObjectRef,
T>::value>::type>
+class Array : public ObjectRef {
+ public:
+ // constructors
+ /*!
+ * \brief default constructor
+ */
+ Array() { data_ = ArrayNode::make(); }
+
+ /*!
+ * \brief move constructor
+ * \param other source
+ */
+ Array(Array<T>&& other) : ObjectRef() { // NOLINT(*)
+ data_ = std::move(other.data_);
+ }
+
+ /*!
+ * \brief copy constructor
+ * \param other source
+ */
+ Array(const Array<T>& other) : ObjectRef() { // NOLINT(*)
+ data_ = other.data_;
+ }
+
+ /*!
+ * \brief constructor from pointer
+ * \param n the container pointer
+ */
+ explicit Array(ObjectPtr<Object> n) : ObjectRef(n) {}
+
+ /*!
+ * \brief constructor from iterator
+ * \param begin begin of iterator
+ * \param end end of iterator
+ * \tparam IterType The type of iterator
+ */
+ template <typename IterType>
+ Array(IterType begin, IterType end) {
+ Assign(begin, end);
+ }
+
+ /*!
+ * \brief constructor from initializer list
+ * \param init The initalizer list
+ */
+ Array(std::initializer_list<T> init) { // NOLINT(*)
+ Assign(init.begin(), init.end());
+ }
+
+ /*!
+ * \brief constructor from vector
+ * \param init The vector
+ */
+ Array(const std::vector<T>& init) { // NOLINT(*)
+ Assign(init.begin(), init.end());
+ }
+
+ /*!
+ * \brief Constructs a container with n elements. Each element is a copy of
val
+ * \param n The size of the container
+ * \param val The init value
+ */
+ explicit Array(const size_t n, const T& val) {
+ ObjectPtr<ArrayNode> p = ArrayNode::make(static_cast<int64_t>(n));
+ for (int64_t& i = p->size_ = 0; i < static_cast<int64_t>(n); ++i) {
+ p->EmplaceInit(i, val);
+ }
+ data_ = std::move(p);
+ }
+
+ /*!
+ * \brief move assign operator
+ * \param other The source of assignment
+ * \return reference to self.
+ */
+ Array<T>& operator=(Array<T>&& other) {
+ data_ = std::move(other.data_);
+ return *this;
+ }
+
+ /*!
+ * \brief copy assign operator
+ * \param other The source of assignment
+ * \return reference to self.
+ */
+ Array<T>& operator=(const Array<T>& other) {
+ data_ = other.data_;
+ return *this;
+ }
+
+ public:
+ // iterators
+ struct ValueConverter {
+ using ResultType = T;
+ static inline T convert(const ObjectRef& n) { return
DowncastNoCheck<T>(n); }
+ };
+
+ using iterator = IterAdapter<ValueConverter, const ObjectRef*>;
+ using reverse_iterator = ReverseIterAdapter<ValueConverter, const
ObjectRef*>;
+
+ /*! \return begin iterator */
+ inline iterator begin() const { return iterator(GetArrayNode()->begin()); }
+
+ /*! \return end iterator */
+ inline iterator end() const { return iterator(GetArrayNode()->end()); }
+
+ /*! \return rbegin iterator */
+ inline reverse_iterator rbegin() const { return
reverse_iterator(GetArrayNode()->end() - 1); }
+
+ /*! \return rend iterator */
+ inline reverse_iterator rend() const { return
reverse_iterator(GetArrayNode()->begin() - 1); }
+
+ public:
+ // const methods in std::vector
+ /*!
+ * \brief Immutably read i-th element from array.
+ * \param i The index
+ * \return the i-th element.
+ */
+ inline const T operator[](const int64_t i) const {
+ ArrayNode* data = GetArrayNode();
+ CHECK(data != nullptr) << "ValueError: cannot index a null Array";
+ return DowncastNoCheck<T>((*data)[i]);
+ }
+
+ /*! \return The size of the array */
+ inline size_t size() const {
+ ArrayNode* p = GetArrayNode();
+ return p == nullptr ? 0 : GetArrayNode()->size_;
+ }
+
+ /*! \return The capacity of the array */
+ inline size_t capacity() const {
+ ArrayNode* p = GetArrayNode();
+ return p == nullptr ? 0 : GetArrayNode()->capacity_;
+ }
+
+ /*! \return Whether array is empty */
+ inline bool empty() const { return size() == 0; }
+
+ public:
+ // mutation in std::vector, implements copy-on-write
+
+ /*! \brief Release reference to all the elements */
+ inline void clear() {
+ if (data_ != nullptr) {
+ ArrayNode* p = CopyOnWrite();
+ p->clear();
+ }
+ }
+
+ /*!
+ * \brief Make sure the list has the capacity of at least n
+ * \param n lower bound of the capacity
+ */
+ inline void reserve(const int64_t n) {
+ if (data_ == nullptr || n > GetArrayNode()->capacity_) {
+ SwitchContainer(n);
+ }
+ CHECK_GE(GetArrayNode()->capacity_, n);
+ }
+
+ /*!
+ * \brief Resize the array.
+ * \param n The new size.
+ */
+ inline void resize(const int64_t n) {
+ // corner case: do nothing
+ if (data_ == nullptr) {
+ SwitchContainer(n);
+ }
+ if (GetArrayNode()->size_ == n) {
+ return;
+ }
+ // ensure enough capacity
+ CHECK_GE(n, 0) << "ValueError: cannot resize an Array to negative size";
+ reserve(n);
+ // mutate by expanding or shrinking
+ ArrayNode* p = CopyOnWrite();
+ ObjectRef* iter = p->MutableBegin() + (p->size_ - 1);
+ int64_t& cur_size = p->size_;
+ if (n > cur_size) {
+ for (; cur_size < n; ++cur_size) {
+ new (++iter) ObjectRef(nullptr);
+ }
+ } else {
+ for (; cur_size > n; --cur_size) {
+ (*iter--).~ObjectRef();
+ }
+ }
+ CHECK_EQ(GetArrayNode()->size_, n);
+ }
+
+ /*!
+ * \brief Insert an element into the given position
+ * \param position An iterator pointing to the insertion point
+ * \param val The element to insert
+ */
+ inline void insert(iterator position, const T& val) {
+ CHECK(data_ != nullptr) << "ValueError: cannot insert a null Array";
+ const int64_t idx = std::distance(begin(), position);
+ MoveBackwards(idx, 1);
+ ObjectRef* begin = GetArrayNode()->MutableBegin();
+ ObjectRef ref = val;
+ new (begin + idx) ObjectRef(std::move(ref));
+ }
+
+ /*!
+ * \brief Insert a range of elements into the given position
+ * \param position An iterator pointing to the insertion point
+ * \param first The begin iterator of the range
+ * \param last The end iterator of the range
+ */
+ template <typename IterType>
+ inline void insert(iterator position, IterType first, IterType last) {
+ if (first == last) {
+ return;
+ }
+ CHECK(data_ != nullptr) << "ValueError: cannot insert a null Array";
+ const int64_t idx = std::distance(begin(), position);
+ const int64_t numel = std::distance(first, last);
+ MoveBackwards(idx, numel);
+ ObjectRef* begin = GetArrayNode()->MutableBegin();
+ for (int64_t i = idx; i < idx + numel; ++i, ++first) {
+ ObjectRef ref = *first;
+ new (begin + i) ObjectRef(std::move(ref));
+ }
+ }
+
+ /*!
+ * \brief Erase an element on the given position
+ * \param position An iterator pointing to the element to be erased
+ */
+ inline void erase(iterator position) {
+ CHECK(data_ != nullptr) << "ValueError: cannot erase a null Array";
+ const int64_t size = GetArrayNode()->size_;
+ const int64_t idx = std::distance(begin(), position);
+ CHECK(0 <= idx && idx < size) << "ValueError: cannot erase at index " <<
idx
+ << ", because Array size is " << size;
+ RemoveRange(idx, idx + 1);
+ }
+
+ /*!
+ * \brief Erase a given range of elements
+ * \param first The begin iterator of the range
+ * \param last The end iterator of the range
+ */
+ inline void erase(iterator first, iterator last) {
+ if (first == last) {
+ return;
+ }
+ CHECK(data_ != nullptr) << "ValueError: cannot erase a null Array";
+ const int64_t size = GetArrayNode()->size_;
+ const int64_t st = std::distance(begin(), first);
+ const int64_t ed = std::distance(begin(), last);
+ CHECK_LT(st, ed) << "ValueError: cannot erase Array in range [" << st <<
", " << ed << ")";
+ CHECK(0 <= st && st <= size && 0 <= ed && ed <= size)
+ << "ValueError: cannot erase Array in range [" << st << ", " << ed <<
")"
+ << ", because Array size is " << size;
+ RemoveRange(st, ed);
+ }
+
+ /*!
+ * \brief push a new item to the back of the list
+ * \param item The item to be pushed.
+ */
+ inline void push_back(const T& item) {
+ ArrayNode* p = nullptr;
+ if (data_ == nullptr) {
+ SwitchContainer(ArrayNode::INIT_SIZE);
+ } else {
+ p = GetArrayNode();
+ if (p->size_ == p->capacity_) {
+ int64_t cap = p->capacity_ * ArrayNode::INC_FACTOR;
+ cap = std::max(cap, ArrayNode::INIT_SIZE);
+ cap = std::max(cap, p->size_ + 1);
+ SwitchContainer(cap);
+ }
+ }
+ p = CopyOnWrite();
+ p->EmplaceInit(p->size_++, item);
+ }
+
+ /*! \brief Remove the last item of the list */
+ inline void pop_back() {
+ CHECK(data_ != nullptr) << "ValueError: cannot pop_back because Array is
null";
+ const int64_t size = GetArrayNode()->size_;
+ CHECK_GT(size, 0) << "ValueError: cannot pop_back because Array is empty";
+ ArrayNode* p = CopyOnWrite();
+ ObjectRef* del = p->MutableBegin() + (--p->size_);
+ (*del).~ObjectRef();
+ }
+
+ public:
+ // Array's own methods
+
+ /*!
+ * \brief copy on write semantics
+ * Do nothing if current handle is the unique copy of the array.
+ * Otherwise make a new copy of the array to ensure the current handle
+ * hold a unique copy.
+ *
+ * \return Handle to the internal node container(which ganrantees to be
unique)
+ */
+ inline ArrayNode* CopyOnWrite() {
+ if (data_ == nullptr) {
+ SwitchContainer(ArrayNode::INIT_SIZE);
+ }
+ if (!data_.unique()) {
+ SwitchContainer(capacity());
+ }
+ return GetArrayNode();
+ }
+
+ /*!
+ * \brief set i-th element of the array.
+ * \param i The index
+ * \param value The value to be setted.
+ */
+ inline void Set(const int64_t i, const T& value) {
+ ArrayNode* p = this->CopyOnWrite();
+ (*p)[i] = value;
+ }
+
+ /*! \return The underlying ArrayNode */
+ inline ArrayNode* GetArrayNode() const { return
static_cast<ArrayNode*>(data_.get()); }
+
+ /*!
+ * \brief Helper function to apply fmutate to mutate an array.
+ * \param fmutate The transformation function T -> T.
+ * \tparam F the type of the mutation function.
+ * \note This function performs copy on write optimization.
+ */
+ template <typename F>
+ inline void MutateByApply(F fmutate) {
+ if (data_ == nullptr) {
+ return;
+ }
+ ArrayNode* p = GetArrayNode();
+ ObjectRef* iter = p->MutableBegin();
+ if (data_.unique()) {
+ for (int64_t i = 0; i < p->size_; ++i) {
+ T old_elem = DowncastNoCheck<T>(std::move(*iter));
+ T new_elem = fmutate(std::move(old_elem));
+ *iter++ = std::move(new_elem);
+ }
+ } else {
+ for (int64_t i = 0; i < p->size_; ++i) {
+ T old_elem = DowncastNoCheck<T>(*iter);
+ T new_elem = fmutate(old_elem);
+ // do nothing until the first real mutation begins.
+ if (new_elem.same_as(*iter++)) {
+ continue;
+ }
+ ObjectPtr<ArrayNode> copy = ArrayNode::make(p->capacity_);
+ // copy [0, i)
+ int64_t& size = copy->size_ = 0;
+ for (ObjectRef* old_iter = p->MutableBegin(); size < i;) {
+ copy->EmplaceInit(size++, *old_iter++);
+ }
+ // copy [i]
+ copy->EmplaceInit(size++, std::move(new_elem));
+ // complete transformation in (i, size)
+ while (size < p->size_) {
+ T old_elem = DowncastNoCheck<T>(*iter++);
+ T new_elem = fmutate(old_elem);
+ copy->EmplaceInit(size++, std::move(new_elem));
+ }
+ data_ = std::move(copy);
+ break;
+ }
+ }
+ }
+
+ /*!
+ * \brief reset the array to content from iterator.
+ * \param begin begin of iterator
+ * \param end end of iterator
+ * \tparam IterType The type of iterator
+ */
+ template <typename IterType>
+ inline void Assign(IterType begin, IterType end) {
+ const int64_t cap = std::distance(begin, end);
+ CHECK_GE(cap, 0) << "ValueError: cannot construct an Array of negative
size";
+ ObjectPtr<ArrayNode> p = ArrayNode::make(cap);
+ for (int64_t& i = p->size_ = 0; begin != end; ++i, ++begin) {
+ p->EmplaceInit(i, *begin);
+ }
+ data_ = std::move(p);
+ }
+
+ /*! \brief specify container node */
+ using ContainerType = ArrayNode;
+
+ private:
+ /*!
+ * \brief Move or copy the ArrayNode to new address with the given capacity
+ * \param capacity The capacity requirement of the new address
+ */
+ inline void SwitchContainer(const int64_t capacity) {
+ CHECK_GE(capacity, 0);
+ ObjectPtr<ArrayNode> p = ArrayNode::make(capacity);
+ if (data_ != nullptr) {
+ ArrayNode* data = GetArrayNode();
+ int64_t size = data->size_;
+ ObjectRef* from = data->MutableBegin();
+ ObjectRef* to = p->MutableBegin();
+ if (data_.unique()) {
+ for (int64_t& i = p->size_ = 0; i < size; ++i) {
+ new (to++) ObjectRef(std::move(*from++));
+ }
+ } else {
+ for (int64_t& i = p->size_ = 0; i < size; ++i) {
+ new (to++) ObjectRef(*from++);
+ }
+ }
+ }
+ data_ = std::move(p);
+ }
+
+ /*!
+ * \brief Move elements in [idx, size) backward by `numel`
+ * \param idx The position of the first element to be moved
+ * \param numel The distance for the moving
+ */
+ inline void MoveBackwards(const int64_t idx, const int64_t numel) {
Review comment:
The problem of memmove-like method is that it still has to take care of
source-destination overlaps. If an extra buffer is not introduced, it still
requires us to discuss the two cases (move forward and move backward)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
