junrushao1994 commented on a change in pull request #5740:
URL: https://github.com/apache/incubator-tvm/pull/5740#discussion_r439869533
##########
File path: include/tvm/runtime/container.h
##########
@@ -1554,6 +1604,925 @@ struct PackedFuncValueConverter<Optional<T>> {
}
};
+/*! \brief map node content */
+class BaseMapNode : public Object {
+ public:
+ /*! \brief Type of the keys in the hash map */
+ using key_type = ObjectRef;
+ /*! \brief Type of the values in the hash map */
+ using mapped_type = ObjectRef;
+
+ static constexpr const uint32_t _type_index = TypeIndex::kRuntimeMap;
+ static constexpr const char* _type_key = "Map";
+ TVM_DECLARE_FINAL_OBJECT_INFO(BaseMapNode, Object);
+
+ /*!
+ * \brief Number of elements in the MapNode
+ * \return The result
+ */
+ size_t size() const { return size_; }
+
+ protected:
+ /*! \brief Alternative to std::pair with standard layout */
+ struct KVType {
+ template <class K, class V>
+ KVType(const K& k, const V& v) : k(k), v(v) {}
+ template <class K, class V>
+ KVType(K&& k, V&& v) : k(std::forward<K>(k)), v(std::forward<V>(v)) {}
+ template <class K, class V>
+ KVType(const K& k, V&& v) : k(k), v(std::forward<V>(v)) {}
+ template <class K, class V>
+ KVType(K&& k, const V& v) : k(std::forward<K>(k)), v(v) {}
+ /*! \brief The STL type */
+ using TStl = std::pair<key_type, mapped_type>;
+ /*! \brief Converting from STL type */
+ KVType(const TStl& kv) : k(kv.first), v(kv.second) {} // NOLINT(*)
+ /*! \brief Converting to STL type */
+ operator TStl() const { return std::make_pair(k, v); }
+ /*! \brief The key, or std::pair::first */
+ key_type k;
+ /*! \brief The value, or std::pair::second */
+ mapped_type v;
+ };
+ static_assert(sizeof(KVType) == 16 || sizeof(KVType) == 8, "sizeof(KVType)
incorrect");
+ static_assert(std::is_standard_layout<KVType>::value, "KVType is not
standard layout");
+
+ class iterator {
+ public:
+ using iterator_category = std::bidirectional_iterator_tag;
+ using difference_type = int64_t;
+ using value_type = KVType;
+ using pointer = KVType*;
+ using reference = KVType&;
+ /*! \brief Default constructor */
+ iterator() : i(0), self(nullptr) {}
+ /*! \brief Compare iterators */
+ bool operator==(const iterator& other) const { return i == other.i && self
== other.self; }
+ /*! \brief Compare iterators */
+ bool operator!=(const iterator& other) const { return !(*this == other); }
+ /*! \brief De-reference iterators */
+ pointer operator->() const;
+ /*! \brief De-reference iterators */
+ reference operator*() const { return *((*this).operator->()); }
+ /*! \brief Prefix self increment, e.g. ++iter */
+ iterator& operator++();
+ /*! \brief Prefix self decrement, e.g. --iter */
+ iterator& operator--();
+ /*! \brief Suffix self increment */
+ iterator operator++(int) {
+ iterator copy = *this;
+ ++(*this);
+ return copy;
+ }
+ /*! \brief Suffix self decrement */
+ iterator operator--(int) {
+ iterator copy = *this;
+ --(*this);
+ return copy;
+ }
+
+ protected:
+ /*! \brief Construct by value */
+ iterator(uint64_t i, const BaseMapNode* self) : i(i), self(self) {}
+ /*! \brief The position on the array */
+ uint64_t i;
+ /*! \brief The container it points to */
+ const BaseMapNode* self;
+
+ friend class MapNode;
+ };
+
+ /*! \brief number of slots minus 1 */
+ uint64_t slots_;
+ /*! \brief number of entries in the container */
+ uint64_t size_;
+
+ // Reference class
+ template <typename, typename, typename, typename>
+ friend class Map;
+};
+
+template <>
+ObjectPtr<BaseMapNode> make_object<>() = delete;
+
+/*! \brief map node content */
+class MapNode : public BaseMapNode {
+ private:
+ /*! \brief The number of elements in a memory block */
+ static constexpr int kBlockCap = 16;
+ /*! \brief Maximum load factor of the hash map */
+ static constexpr double kMaxLoadFactor = 0.99;
+ /*! \brief Binary representation of the metadata of an empty slot */
+ static constexpr uint8_t kEmptySlot = uint8_t(0b11111111);
+ /*! \brief Binary representation of the metadata of a protected slot */
+ static constexpr uint8_t kProtectedSlot = uint8_t(0b11111110);
+ /*! \brief Number of probing choices available */
+ static constexpr int kNumJumpDists = 126;
+
+ struct Block;
+ struct ListNode;
+
+ // Reference class
+ template <typename, typename, typename, typename>
+ friend class Map;
+ // Parent class
+ friend class BaseMapNode;
+
+ public:
+ using BaseMapNode::iterator;
+
+ /*!
+ * \brief Destroy the MapNode
+ */
+ ~MapNode() { this->Reset(); }
+
+ /*!
+ * \brief Count the number of times a key exists in the MapNode
+ * \param key The indexing key
+ * \return The result, 0 or 1
+ */
+ size_t count(const key_type& key) const { return !Search(key).IsNone(); }
+
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The const reference to the value
+ */
+ const mapped_type& at(const key_type& key) const { return At(key); }
+
+ /*!
+ * \brief Index value associated with a key, throw exception if the key does
not exist
+ * \param key The indexing key
+ * \return The mutable reference to the value
+ */
+ mapped_type& at(const key_type& key) { return At(key); }
+
+ /*! \return begin iterator */
+ iterator begin() const {
+ if (slots_ == 0) {
+ return iterator(0, this);
+ }
+ for (uint64_t i = 0; i <= slots_; ++i) {
+ if (!ListNode(i, this).IsEmpty()) {
+ return iterator(i, this);
+ }
+ }
+ return iterator(slots_ + 1, this);
+ }
+
+ /*! \return end iterator */
+ iterator end() const { return slots_ == 0 ? iterator(0, this) :
iterator(slots_ + 1, this); }
+
+ /*!
+ * \brief Index value associated with a key
+ * \param key The indexing key
+ * \return The iterator of the entry associated with the key, end iterator
if not exists
+ */
+ iterator find(const key_type& key) const {
+ ListNode n = Search(key);
+ return n.IsNone() ? end() : iterator(n.i, this);
+ }
+
+ /*!
+ * \brief Erase the entry associated with the key, do nothing if not exists
+ * \param key The indexing key
+ */
+ void erase(const key_type& key) { Erase(key); }
+
+ /*!
+ * \brief Erase the entry associated with the iterator
+ * \param position The iterator
+ */
+ void erase(const iterator& position) {
+ uint64_t i = position.i;
+ if (position.self != nullptr && i <= this->slots_) {
+ Erase(ListNode(i, this));
+ }
+ }
+
+ private:
+ /*!
+ * \brief Search for the given key
+ * \param key The key
+ * \return ListNode that associated with the key
+ */
+ ListNode Search(const key_type& key) const {
+ if (this->size_ == 0) {
+ return ListNode();
+ }
+ for (ListNode n = GetHead(ObjectHash()(key)); !n.IsNone();
n.MoveToNext(this)) {
+ if (ObjectEqual()(key, n.Key())) {
+ return n;
+ }
+ }
+ return ListNode();
+ }
+
+ /*!
+ * \brief Search for the given key, throw exception if not exists
+ * \param key The key
+ * \return ListNode that associated with the key
+ */
+ mapped_type& At(const key_type& key) const {
+ ListNode n = Search(key);
+ CHECK(!n.IsNone()) << "IndexError: key is not in Map";
+ return n.Val();
+ }
+
+ /*!
+ * \brief Try to insert a key, or do nothing if already exists
+ * \param k The indexing key
+ * \param result The linked-list entry found or just constructed
+ * \return A boolean, indicating if actual insertion happens
+ */
+ bool TryInsert(const key_type& k, ListNode* result) {
Review comment:
Yah I think I should rename those single-character names to more
informative ones, except for loop variables.
----------------------------------------------------------------
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:
[email protected]
