From 80d6f5a7d0e1e60b928573d783192186613a42a8 Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Tue, 7 Oct 2014 20:16:32 -0700 Subject: Rework compact_pointer implementation Split the implementation into a generic one with adjustable range and a special implementation for parent (may need to use 2 bytes on that one later). Optimize compact_string and compact_pointer to use minimal amount of math and move slow hash paths into no-inline functions so that compiler can inline the fast-paths. Merge compact_pointer_generic and compact_pointer_forward and optimize. --- src/pugixml.cpp | 186 +++++++++++++++++++++++++++++++------------------------- 1 file changed, 103 insertions(+), 83 deletions(-) (limited to 'src') diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 9d75b20..bdb8425 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -639,6 +639,8 @@ PUGI__NS_BEGIN } }; + static const unsigned int compact_alignment_log2 = 2; + typedef uint32_t compact_alignment; class compact_header @@ -681,14 +683,24 @@ PUGI__NS_BEGIN unsigned char flags; }; - xml_memory_page* compact_get_page(const void* object, int header_offset) + PUGI__FN xml_memory_page* compact_get_page(const void* object, int header_offset) { const compact_header* header = reinterpret_cast(static_cast(object) - header_offset); return header->get_page(); } - template class compact_pointer + template PUGI__FN_NO_INLINE T* compact_get_value(const void* object) + { + return static_cast(*compact_get_page(object, header_offset)->allocator->_hash->find(object)); + } + + template PUGI__FN_NO_INLINE void compact_set_value(const void* object, T* value) + { + *compact_get_page(object, header_offset)->allocator->_hash->insert(object, tag) = value; + } + + template class compact_pointer { public: compact_pointer(): _data(0) @@ -700,6 +712,63 @@ PUGI__NS_BEGIN *this = rhs + 0; } + void operator=(T* value) + { + if (value) + { + ptrdiff_t offset = ((reinterpret_cast(value) - reinterpret_cast(this) + int(sizeof(compact_alignment) - 1)) >> compact_alignment_log2) - start; + + if (static_cast(offset) <= 253) + _data = static_cast(offset + 1); + else + { + compact_set_value(this, value); + + _data = 255; + } + } + else + _data = 0; + } + + operator T* const() const + { + if (_data) + { + if (_data < 255) + { + uintptr_t base = reinterpret_cast(this) & ~(sizeof(compact_alignment) - 1); + + return reinterpret_cast(base + ((_data - (1 - start)) << compact_alignment_log2)); + } + else + return compact_get_value(this); + } + else + return 0; + } + + T* operator->() const + { + return operator T* const(); + } + + private: + unsigned char _data; + }; + + template class compact_pointer_parent + { + public: + compact_pointer_parent(): _data(0) + { + } + + void operator=(const compact_pointer_parent& rhs) + { + *this = rhs + 0; + } + void operator=(T* value_) { if (value_) @@ -707,49 +776,24 @@ PUGI__NS_BEGIN compact_alignment* base = get_base(); compact_alignment* value = reinterpret_cast(value_); - if (direction > 0) + if (value <= base && value >= base - 252) + _data = static_cast((base - value) + 1); + else { - if (value >= base && value <= base + 253) - _data = static_cast((value - base) + 1); - else - { - *compact_get_page(this, header_offset)->allocator->_hash->insert(this, tag) = value; + xml_memory_page* page = compact_get_page(this, header_offset); - _data = 255; + if (page->compact_parent == 0) + { + page->compact_parent = value; + _data = 254; } - } - else if (direction < 0) - { - if (value <= base && value >= base - 252) - _data = static_cast((base - value) + 1); - else + else if (page->compact_parent == value) { - xml_memory_page* page = compact_get_page(this, header_offset); - - if (page->compact_parent == 0) - { - page->compact_parent = value; - _data = 254; - } - else if (page->compact_parent == value) - { - _data = 254; - } - else - { - *page->allocator->_hash->insert(this, tag) = value; - _data = 255; - } + _data = 254; } - } - else - { - if (value >= base - 126 && value <= base + 127) - _data = static_cast((value - base) + 127); else { - *compact_get_page(this, header_offset)->allocator->_hash->insert(this, tag) = value; - + compact_set_value(this, value); _data = 255; } } @@ -763,19 +807,14 @@ PUGI__NS_BEGIN if (_data) { if (_data == 255) - return static_cast(*compact_get_page(this, header_offset)->allocator->_hash->find(this)); - else if (direction < 0 && _data == 254) + return compact_get_value(this); + else if (_data == 254) return static_cast(compact_get_page(this, header_offset)->compact_parent); else { compact_alignment* base = get_base(); - if (direction > 0) - return reinterpret_cast(base + (_data - 1)); - else if (direction < 0) - return reinterpret_cast(base - (_data - 1)); - else - return reinterpret_cast(base + (_data - 127)); + return reinterpret_cast(base - (_data - 1)); } } else @@ -792,10 +831,7 @@ PUGI__NS_BEGIN compact_alignment* get_base() const { - if (direction > 0) - return reinterpret_cast((reinterpret_cast(this) + sizeof(compact_alignment)) & ~(sizeof(compact_alignment) - 1)); - else - return reinterpret_cast(reinterpret_cast(this) & ~(sizeof(compact_alignment) - 1)); + return reinterpret_cast(reinterpret_cast(this) & ~(sizeof(compact_alignment) - 1)); } }; @@ -818,32 +854,20 @@ PUGI__NS_BEGIN xml_memory_page* page = compact_get_page(this, header_offset); if (page->compact_string_base == 0) - { page->compact_string_base = value; - _data0 = 1; - _data1 = 0; - _data2 = 0; - } - else - { - ptrdiff_t offset = value - page->compact_string_base; + ptrdiff_t offset = value - page->compact_string_base; - if (offset >= 0 && offset <= 1677213) - { - _data0 = static_cast(offset + 1); - _data1 = static_cast((offset + 1) >> 8); - _data2 = static_cast((offset + 1) >> 16); - } - else - { - *page->allocator->_hash->insert(this, tag) = value; + if (static_cast(offset) >= 16777213) + { + compact_set_value(this, value); - _data0 = 255; - _data1 = 255; - _data2 = 255; - } + offset = 16777214; } + + _data0 = static_cast(offset + 1); + _data1 = static_cast((offset + 1) >> 8); + _data2 = static_cast((offset + 1) >> 16); } else { @@ -862,13 +886,9 @@ PUGI__NS_BEGIN xml_memory_page* page = compact_get_page(this, header_offset); if (data < 16777215) - { return page->compact_string_base + (data - 1); - } else - { - return static_cast(*page->allocator->_hash->find(this)); - } + return compact_get_value(this); } else return 0; @@ -904,8 +924,8 @@ namespace pugi impl::compact_string<4, /*tag*/11> name; ///< Pointer to attribute name. impl::compact_string<7, /*tag*/12> value; ///< Pointer to attribute value. - impl::compact_pointer prev_attribute_c; ///< Previous attribute (cyclic list) - impl::compact_pointer next_attribute; ///< Next attribute + impl::compact_pointer prev_attribute_c; ///< Previous attribute (cyclic list) + impl::compact_pointer next_attribute; ///< Next attribute }; /// An XML document tree node. @@ -926,14 +946,14 @@ namespace pugi impl::compact_string<4, /*tag*/21> contents; ///< Pointer to element name. - impl::compact_pointer parent; ///< Pointer to parent + impl::compact_pointer_parent parent; ///< Pointer to parent - impl::compact_pointer first_child; ///< First child + impl::compact_pointer first_child; ///< First child - impl::compact_pointer prev_sibling_c; ///< Left brother (cyclic list) - impl::compact_pointer next_sibling; ///< Right brother + impl::compact_pointer prev_sibling_c; ///< Left brother (cyclic list) + impl::compact_pointer next_sibling; ///< Right brother - impl::compact_pointer first_attribute; ///< First attribute + impl::compact_pointer first_attribute; ///< First attribute }; } #else -- cgit v1.2.3