summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/pugixml.cpp523
1 files changed, 496 insertions, 27 deletions
diff --git a/src/pugixml.cpp b/src/pugixml.cpp
index 58191ae..c0a2980 100644
--- a/src/pugixml.cpp
+++ b/src/pugixml.cpp
@@ -145,6 +145,13 @@ PUGI__NS_BEGIN
PUGI__NS_END
#endif
+// Micro compact helper
+#ifdef PUGIXML_COMPACT
+# define PUGI__COMPACT(p) ((p).get())
+#else
+# define PUGI__COMPACT(p) (p)
+#endif
+
// Memory allocation
PUGI__NS_BEGIN
PUGI__FN void* default_allocate(size_t size)
@@ -293,6 +300,11 @@ PUGI__NS_BEGIN
result->busy_size = 0;
result->freed_size = 0;
+ #ifdef PUGIXML_COMPACT
+ result->compact_string_base = 0;
+ result->compact_parent = 0;
+ #endif
+
return result;
}
@@ -303,6 +315,11 @@ PUGI__NS_BEGIN
size_t busy_size;
size_t freed_size;
+
+ #ifdef PUGIXML_COMPACT
+ char_t* compact_string_base;
+ void* compact_parent;
+ #endif
};
struct xml_memory_string_header
@@ -315,6 +332,9 @@ PUGI__NS_BEGIN
{
xml_allocator(xml_memory_page* root): _root(root), _busy_size(root->busy_size)
{
+ #ifdef PUGIXML_COMPACT
+ _hash = 0;
+ #endif
}
xml_memory_page* allocate_page(size_t data_size)
@@ -446,6 +466,10 @@ PUGI__NS_BEGIN
xml_memory_page* _root;
size_t _busy_size;
+
+ #ifdef PUGIXML_COMPACT
+ class compact_hash_table* _hash;
+ #endif
};
PUGI__FN_NO_INLINE void* xml_allocator::allocate_memory_oob(size_t size, xml_memory_page*& out_page)
@@ -488,6 +512,429 @@ PUGI__NS_BEGIN
}
PUGI__NS_END
+#ifdef PUGIXML_COMPACT
+size_t pugi_compact_stats[128];
+
+PUGI__NS_BEGIN
+ class compact_hash_table
+ {
+ public:
+ compact_hash_table(): _items(0), _capacity(0), _count(0)
+ {
+ }
+
+ void clear()
+ {
+ if (_items)
+ {
+ xml_memory::deallocate(_items);
+ _items = 0;
+ _capacity = 0;
+ _count = 0;
+ }
+ }
+
+ void** find(const void* key)
+ {
+ assert(key);
+
+ if (_capacity == 0) return 0;
+
+ size_t hashmod = _capacity - 1;
+ size_t bucket = hash(key) & hashmod;
+
+ for (size_t probe = 0; probe <= hashmod; ++probe)
+ {
+ item_t& probe_item = _items[bucket];
+
+ if (probe_item.key == key)
+ return &probe_item.value;
+
+ if (probe_item.key == 0)
+ return 0;
+
+ // hash collision, quadratic probing
+ bucket = (bucket + probe + 1) & hashmod;
+ }
+
+ assert(!"Hash table is full");
+ return 0;
+ }
+
+ void** insert(const void* key, size_t tag)
+ {
+ assert(key);
+
+ if (_count >= _capacity * 3 / 4)
+ rehash();
+
+ size_t hashmod = _capacity - 1;
+ size_t bucket = hash(key) & hashmod;
+
+ for (size_t probe = 0; probe <= hashmod; ++probe)
+ {
+ item_t& probe_item = _items[bucket];
+
+ if (probe_item.key == 0)
+ {
+ if (tag)
+ pugi_compact_stats[tag]++;
+
+ probe_item.key = key;
+ _count++;
+ return &probe_item.value;
+ }
+
+ if (probe_item.key == key)
+ return &probe_item.value;
+
+ // hash collision, quadratic probing
+ bucket = (bucket + probe + 1) & hashmod;
+ }
+
+ assert(!"Hash table is full");
+ return 0;
+ }
+
+ private:
+ struct item_t
+ {
+ const void* key;
+ void* value;
+ };
+
+ item_t* _items;
+ size_t _capacity;
+
+ size_t _count;
+
+ void rehash()
+ {
+ compact_hash_table rt;
+ rt._capacity = (_capacity == 0) ? 256 : _capacity * 2;
+ rt._items = static_cast<item_t*>(xml_memory::allocate(sizeof(item_t) * rt._capacity));
+
+ assert(rt._items);
+
+ memset(rt._items, 0, sizeof(item_t) * rt._capacity);
+
+ for (size_t i = 0; i < _capacity; ++i)
+ if (_items[i].key)
+ *rt.insert(_items[i].key, 0) = _items[i].value;
+
+ if (_items)
+ xml_memory::deallocate(_items);
+
+ _capacity = rt._capacity;
+ _items = rt._items;
+ }
+
+ // http://burtleburtle.net/bob/hash/integer.html
+ static unsigned int hash(const void* key)
+ {
+ unsigned int a = static_cast<unsigned int>(reinterpret_cast<uintptr_t>(key));
+
+ a = (a ^ 61) ^ (a >> 16);
+ a = a + (a << 3);
+ a = a ^ (a >> 4);
+ a = a * 0x27d4eb2d;
+ a = a ^ (a >> 15);
+
+ return a;
+ }
+ };
+
+ typedef uint32_t compact_alignment;
+
+ class compact_header
+ {
+ public:
+ compact_header(xml_memory_page* page, unsigned int flags)
+ {
+ ptrdiff_t page_offset = reinterpret_cast<compact_alignment*>(this) - reinterpret_cast<compact_alignment*>(page);
+ assert(page_offset >= 0 && page_offset < (1 << 16));
+
+ this->page0 = static_cast<unsigned char>(page_offset);
+ this->page1 = static_cast<unsigned char>(page_offset >> 8);
+ this->flags = static_cast<unsigned char>(flags);
+ }
+
+ void operator&=(unsigned int modflags)
+ {
+ flags &= modflags;
+ }
+
+ void operator|=(unsigned int modflags)
+ {
+ flags |= modflags;
+ }
+
+ operator uintptr_t const() const
+ {
+ return reinterpret_cast<uintptr_t>(get_page()) | flags;
+ }
+
+ xml_memory_page* get_page() const
+ {
+ unsigned int page_offset = page0 + (page1 << 8);
+
+ return const_cast<xml_memory_page*>(reinterpret_cast<const xml_memory_page*>(reinterpret_cast<const compact_alignment*>(this) - page_offset));
+ }
+
+ private:
+ unsigned char page0, page1;
+ unsigned char flags;
+ };
+
+ xml_memory_page* compact_get_page(const void* object, int header_offset)
+ {
+ const compact_header* header = reinterpret_cast<const compact_header*>(static_cast<const char*>(object) - header_offset);
+
+ return header->get_page();
+ }
+
+ template <typename T, int header_offset, int direction, int tag> class compact_pointer
+ {
+ public:
+ compact_pointer(): _data(0)
+ {
+ }
+
+ void operator=(const compact_pointer& rhs)
+ {
+ *this = rhs.get();
+ }
+
+ void operator=(T* value_)
+ {
+ if (value_)
+ {
+ compact_alignment* base = get_base();
+ compact_alignment* value = reinterpret_cast<compact_alignment*>(value_);
+
+ if (direction > 0)
+ {
+ if (value >= base && value <= base + 253)
+ _data = static_cast<unsigned char>((value - base) + 1);
+ else
+ {
+ *compact_get_page(this, header_offset)->allocator->_hash->insert(this, tag) = value;
+
+ _data = 255;
+ }
+ }
+ else if (direction < 0)
+ {
+ if (value <= base && value >= base - 252)
+ _data = static_cast<unsigned char>((base - value) + 1);
+ else
+ {
+ 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;
+ }
+ }
+ }
+ else
+ {
+ if (value >= base - 126 && value <= base + 127)
+ _data = static_cast<unsigned char>((value - base) + 127);
+ else
+ {
+ *compact_get_page(this, header_offset)->allocator->_hash->insert(this, tag) = value;
+
+ _data = 255;
+ }
+ }
+ }
+ else
+ _data = 0;
+ }
+
+ operator T* const() const
+ {
+ if (_data)
+ {
+ if (_data == 255)
+ return static_cast<T*>(*compact_get_page(this, header_offset)->allocator->_hash->find(this));
+ else if (direction < 0 && _data == 254)
+ return static_cast<T*>(compact_get_page(this, header_offset)->compact_parent);
+ else
+ {
+ compact_alignment* base = get_base();
+
+ if (direction > 0)
+ return reinterpret_cast<T*>(base + (_data - 1));
+ else if (direction < 0)
+ return reinterpret_cast<T*>(base - (_data - 1));
+ else
+ return reinterpret_cast<T*>(base + (_data - 127));
+ }
+ }
+ else
+ return 0;
+ }
+
+ T* operator->() const
+ {
+ return operator T* const();
+ }
+
+ T* get() const
+ {
+ return operator T* const();
+ }
+
+ private:
+ unsigned char _data;
+
+ compact_alignment* get_base() const
+ {
+ if (direction > 0)
+ return reinterpret_cast<compact_alignment*>((reinterpret_cast<uintptr_t>(this) + sizeof(compact_alignment)) & ~(sizeof(compact_alignment) - 1));
+ else
+ return reinterpret_cast<compact_alignment*>(reinterpret_cast<uintptr_t>(this) & ~(sizeof(compact_alignment) - 1));
+ }
+ };
+
+ template <int header_offset, int tag> class compact_string
+ {
+ public:
+ compact_string(): _data(0)
+ {
+ }
+
+ void operator=(const compact_string& rhs)
+ {
+ *this = rhs.get();
+ }
+
+ void operator=(char_t* value)
+ {
+ if (value)
+ {
+ xml_memory_page* page = compact_get_page(this, header_offset);
+
+ if (page->compact_string_base == 0)
+ {
+ page->compact_string_base = value;
+
+ _data = 1;
+ }
+ else
+ {
+ ptrdiff_t offset = value - page->compact_string_base;
+
+ if (offset >= 0 && offset <= 65533)
+ _data = static_cast<unsigned short>(offset + 1);
+ else
+ {
+ *page->allocator->_hash->insert(this, tag) = value;
+
+ _data = 65535;
+ }
+ }
+ }
+ else
+ _data = 0;
+ }
+
+ operator char_t* const() const
+ {
+ if (_data)
+ {
+ xml_memory_page* page = compact_get_page(this, header_offset);
+
+ if (_data < 65535)
+ {
+ return page->compact_string_base + (_data - 1);
+ }
+ else
+ {
+ return static_cast<char_t*>(*page->allocator->_hash->find(this));
+ }
+ }
+ else
+ return 0;
+ }
+
+ char_t* get() const
+ {
+ return operator char_t* const();
+ }
+
+ private:
+ unsigned short _data;
+ };
+
+PUGI__NS_END
+#endif
+
+#ifdef PUGIXML_COMPACT
+namespace pugi
+{
+ /// A 'name=value' XML attribute structure.
+ struct xml_attribute_struct
+ {
+ /// Default ctor
+ xml_attribute_struct(impl::xml_memory_page* page): header(page, 0)
+ {
+ PUGI__STATIC_ASSERT(sizeof(xml_attribute_struct) == 12);
+
+ pugi_compact_stats[10]++;
+ }
+
+ impl::compact_header header;
+
+ unsigned char padding[3];
+
+ impl::compact_string<6, /*tag*/11> name; ///< Pointer to attribute name.
+ impl::compact_string<8, /*tag*/12> value; ///< Pointer to attribute value.
+
+ impl::compact_pointer<xml_attribute_struct, 10, 0, /*tag*/13> prev_attribute_c; ///< Previous attribute (cyclic list)
+ impl::compact_pointer<xml_attribute_struct, 11, +1, /*tag*/14> next_attribute; ///< Next attribute
+ };
+
+ /// An XML document tree node.
+ struct xml_node_struct
+ {
+ /// Default ctor
+ /// \param type - node type
+ xml_node_struct(impl::xml_memory_page* page, xml_node_type type): header(page, type - 1)
+ {
+ PUGI__STATIC_ASSERT(sizeof(xml_node_struct) == 12);
+
+ pugi_compact_stats[20]++;
+ }
+
+ impl::compact_header header;
+
+ impl::compact_pointer<xml_node_struct, 3, -1, /*tag*/23> parent; ///< Pointer to parent
+
+ impl::compact_string<4, /*tag*/21> name; ///< Pointer to element name.
+ impl::compact_string<6, /*tag*/22> value; ///< Pointer to any associated string data.
+
+ impl::compact_pointer<xml_node_struct, 8, +1, /*tag*/24> first_child; ///< First child
+
+ impl::compact_pointer<xml_node_struct, 9, 0, /*tag*/25> prev_sibling_c; ///< Left brother (cyclic list)
+ impl::compact_pointer<xml_node_struct, 10, +1, /*tag*/26> next_sibling; ///< Right brother
+
+ impl::compact_pointer<xml_attribute_struct, 11, +1, /*tag*/27> first_attribute; ///< First attribute
+ };
+}
+#else
namespace pugi
{
/// A 'name=value' XML attribute structure.
@@ -531,6 +978,7 @@ namespace pugi
xml_attribute_struct* first_attribute; ///< First attribute
};
}
+#endif
PUGI__NS_BEGIN
struct xml_extra_buffer
@@ -543,11 +991,18 @@ PUGI__NS_BEGIN
{
xml_document_struct(xml_memory_page* page): xml_node_struct(page, node_document), xml_allocator(page), buffer(0), extra_buffers(0)
{
+ #ifdef PUGIXML_COMPACT
+ _hash = &hash;
+ #endif
}
const char_t* buffer;
xml_extra_buffer* extra_buffers;
+
+ #ifdef PUGIXML_COMPACT
+ compact_hash_table hash;
+ #endif
};
inline xml_allocator& get_allocator(const xml_node_struct* node)
@@ -1679,7 +2134,8 @@ PUGI__NS_BEGIN
return target_length >= length && (target_length < reuse_threshold || target_length - length < target_length / 2);
}
- PUGI__FN bool strcpy_insitu(char_t*& dest, uintptr_t& header, uintptr_t header_mask, const char_t* source)
+ template <typename String, typename Header>
+ PUGI__FN bool strcpy_insitu(String& dest, Header& header, uintptr_t header_mask, const char_t* source)
{
assert(header);
@@ -2826,7 +3282,7 @@ PUGI__NS_BEGIN
return make_parse_result(PUGI__OPTSET(parse_fragment) ? status_ok : status_no_document_element);
// get last child of the root before parsing
- xml_node_struct* last_root_child = root->first_child ? root->first_child->prev_sibling_c : 0;
+ xml_node_struct* last_root_child = root->first_child ? PUGI__COMPACT(root->first_child->prev_sibling_c) : 0;
// create parser on stack
xml_parser parser(alloc_);
@@ -2854,7 +3310,7 @@ PUGI__NS_BEGIN
return make_parse_result(status_unrecognized_tag, length - 1);
// check if there are any element nodes parsed
- xml_node_struct* first_root_child_parsed = last_root_child ? last_root_child->next_sibling : root->first_child;
+ xml_node_struct* first_root_child_parsed = last_root_child ? PUGI__COMPACT(last_root_child->next_sibling) : root->first_child;
if (!PUGI__OPTSET(parse_fragment) && !has_element_node_siblings(first_root_child_parsed))
return make_parse_result(status_no_document_element, length - 1);
@@ -3612,7 +4068,8 @@ PUGI__NS_BEGIN
return true;
}
- PUGI__FN void node_copy_string(char_t*& dest, uintptr_t& header, uintptr_t header_mask, char_t* source, uintptr_t& source_header, xml_allocator* alloc)
+ template <typename String, typename Header>
+ PUGI__FN void node_copy_string(String& dest, Header& header, uintptr_t header_mask, char_t* source, Header& source_header, xml_allocator* alloc)
{
if (source)
{
@@ -3813,7 +4270,8 @@ PUGI__NS_BEGIN
#endif
// set value with conversion functions
- PUGI__FN bool set_value_buffer(char_t*& dest, uintptr_t& header, uintptr_t header_mask, char (&buf)[128])
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_buffer(String& dest, Header& header, uintptr_t header_mask, char (&buf)[128])
{
#ifdef PUGIXML_WCHAR_MODE
char_t wbuf[128];
@@ -3825,7 +4283,8 @@ PUGI__NS_BEGIN
#endif
}
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, int value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, int value)
{
char buf[128];
sprintf(buf, "%d", value);
@@ -3833,7 +4292,8 @@ PUGI__NS_BEGIN
return set_value_buffer(dest, header, header_mask, buf);
}
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, unsigned int value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, unsigned int value)
{
char buf[128];
sprintf(buf, "%u", value);
@@ -3841,7 +4301,8 @@ PUGI__NS_BEGIN
return set_value_buffer(dest, header, header_mask, buf);
}
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, double value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, double value)
{
char buf[128];
sprintf(buf, "%g", value);
@@ -3849,13 +4310,15 @@ PUGI__NS_BEGIN
return set_value_buffer(dest, header, header_mask, buf);
}
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, bool value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, bool value)
{
return strcpy_insitu(dest, header, header_mask, value ? PUGIXML_TEXT("true") : PUGIXML_TEXT("false"));
}
#ifdef PUGIXML_HAS_LONG_LONG
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, long long value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, long long value)
{
char buf[128];
sprintf(buf, "%lld", value);
@@ -3863,7 +4326,8 @@ PUGI__NS_BEGIN
return set_value_buffer(dest, header, header_mask, buf);
}
- PUGI__FN bool set_value_convert(char_t*& dest, uintptr_t& header, uintptr_t header_mask, unsigned long long value)
+ template <typename String, typename Header>
+ PUGI__FN bool set_value_convert(String& dest, Header& header, uintptr_t header_mask, unsigned long long value)
{
char buf[128];
sprintf(buf, "%llu", value);
@@ -4348,38 +4812,38 @@ namespace pugi
PUGI__FN int xml_attribute::as_int(int def) const
{
- return impl::get_value_int(_attr ? _attr->value : 0, def);
+ return impl::get_value_int(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
PUGI__FN unsigned int xml_attribute::as_uint(unsigned int def) const
{
- return impl::get_value_uint(_attr ? _attr->value : 0, def);
+ return impl::get_value_uint(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
PUGI__FN double xml_attribute::as_double(double def) const
{
- return impl::get_value_double(_attr ? _attr->value : 0, def);
+ return impl::get_value_double(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
PUGI__FN float xml_attribute::as_float(float def) const
{
- return impl::get_value_float(_attr ? _attr->value : 0, def);
+ return impl::get_value_float(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
PUGI__FN bool xml_attribute::as_bool(bool def) const
{
- return impl::get_value_bool(_attr ? _attr->value : 0, def);
+ return impl::get_value_bool(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
#ifdef PUGIXML_HAS_LONG_LONG
PUGI__FN long long xml_attribute::as_llong(long long def) const
{
- return impl::get_value_llong(_attr ? _attr->value : 0, def);
+ return impl::get_value_llong(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
PUGI__FN unsigned long long xml_attribute::as_ullong(unsigned long long def) const
{
- return impl::get_value_ullong(_attr ? _attr->value : 0, def);
+ return impl::get_value_ullong(_attr ? PUGI__COMPACT(_attr->value) : 0, def);
}
#endif
@@ -4546,7 +5010,7 @@ namespace pugi
PUGI__FN xml_node::iterator xml_node::begin() const
{
- return iterator(_root ? _root->first_child : 0, _root);
+ return iterator(_root ? PUGI__COMPACT(_root->first_child) : 0, _root);
}
PUGI__FN xml_node::iterator xml_node::end() const
@@ -4556,7 +5020,7 @@ namespace pugi
PUGI__FN xml_node::attribute_iterator xml_node::attributes_begin() const
{
- return attribute_iterator(_root ? _root->first_attribute : 0, _root);
+ return attribute_iterator(_root ? PUGI__COMPACT(_root->first_attribute) : 0, _root);
}
PUGI__FN xml_node::attribute_iterator xml_node::attributes_end() const
@@ -5452,35 +5916,35 @@ namespace pugi
{
xml_node_struct* d = _data();
- return impl::get_value_int(d ? d->value : 0, def);
+ return impl::get_value_int(d ? PUGI__COMPACT(d->value) : 0, def);
}
PUGI__FN unsigned int xml_text::as_uint(unsigned int def) const
{
xml_node_struct* d = _data();
- return impl::get_value_uint(d ? d->value : 0, def);
+ return impl::get_value_uint(d ? PUGI__COMPACT(d->value) : 0, def);
}
PUGI__FN double xml_text::as_double(double def) const
{
xml_node_struct* d = _data();
- return impl::get_value_double(d ? d->value : 0, def);
+ return impl::get_value_double(d ? PUGI__COMPACT(d->value) : 0, def);
}
PUGI__FN float xml_text::as_float(float def) const
{
xml_node_struct* d = _data();
- return impl::get_value_float(d ? d->value : 0, def);
+ return impl::get_value_float(d ? PUGI__COMPACT(d->value) : 0, def);
}
PUGI__FN bool xml_text::as_bool(bool def) const
{
xml_node_struct* d = _data();
- return impl::get_value_bool(d ? d->value : 0, def);
+ return impl::get_value_bool(d ? PUGI__COMPACT(d->value) : 0, def);
}
#ifdef PUGIXML_HAS_LONG_LONG
@@ -5488,14 +5952,14 @@ namespace pugi
{
xml_node_struct* d = _data();
- return impl::get_value_llong(d ? d->value : 0, def);
+ return impl::get_value_llong(d ? PUGI__COMPACT(d->value) : 0, def);
}
PUGI__FN unsigned long long xml_text::as_ullong(unsigned long long def) const
{
xml_node_struct* d = _data();
- return impl::get_value_ullong(d ? d->value : 0, def);
+ return impl::get_value_ullong(d ? PUGI__COMPACT(d->value) : 0, def);
}
#endif
@@ -5924,6 +6388,11 @@ namespace pugi
page = next;
}
+ #ifdef PUGIXML_COMPACT
+ // destroy hash table
+ static_cast<impl::xml_document_struct*>(_root)->hash.clear();
+ #endif
+
_root = 0;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-06 00:56:05 +0000