From a6dc5ff70b4940e3b6e7eb2cb0f046a85697a2fa Mon Sep 17 00:00:00 2001 From: "arseny.kapoulkine" Date: Mon, 10 May 2010 16:38:22 +0000 Subject: Optimized memory consumption (removed last_child and last_attribute, sibling/attribute lists are now one-way cyclic) git-svn-id: http://pugixml.googlecode.com/svn/trunk@405 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 114 ++++++++++++++++++++++++++++++++------------------------ 1 file changed, 65 insertions(+), 49 deletions(-) (limited to 'src') diff --git a/src/pugixml.cpp b/src/pugixml.cpp index d14016f..aa10bbc 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -411,7 +411,7 @@ namespace pugi struct xml_attribute_struct { /// Default ctor - xml_attribute_struct(xml_memory_page* page): header(reinterpret_cast(page)), name(0), value(0), prev_attribute(0), next_attribute(0) + xml_attribute_struct(xml_memory_page* page): header(reinterpret_cast(page)), name(0), value(0), prev_attribute_c(0), next_attribute(0) { } @@ -420,7 +420,7 @@ namespace pugi char_t* name; ///< Pointer to attribute name. char_t* value; ///< Pointer to attribute value. - xml_attribute_struct* prev_attribute; ///< Previous attribute + xml_attribute_struct* prev_attribute_c; ///< Previous attribute (cyclic list) xml_attribute_struct* next_attribute; ///< Next attribute }; @@ -429,7 +429,7 @@ namespace pugi { /// Default ctor /// \param type - node type - xml_node_struct(xml_memory_page* page, xml_node_type type): header(reinterpret_cast(page) | type), parent(0), name(0), value(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), first_attribute(0), last_attribute(0) + xml_node_struct(xml_memory_page* page, xml_node_type type): header(reinterpret_cast(page) | type), parent(0), name(0), value(0), first_child(0), prev_sibling_c(0), next_sibling(0), first_attribute(0) { } @@ -441,13 +441,11 @@ namespace pugi char_t* value; ///< Pointer to any associated string data. xml_node_struct* first_child; ///< First child - xml_node_struct* last_child; ///< Last child - xml_node_struct* prev_sibling; ///< Left brother + xml_node_struct* prev_sibling_c; ///< Left brother (cyclic list) xml_node_struct* next_sibling; ///< Right brother xml_attribute_struct* first_attribute; ///< First attribute - xml_attribute_struct* last_attribute; ///< Last attribute }; struct xml_document_struct: public xml_node_struct @@ -532,14 +530,22 @@ namespace { xml_node_struct* child = allocate_node(alloc, type); child->parent = node; + + xml_node_struct* first_child = node->first_child; - if (node->last_child) + if (first_child) + { + xml_node_struct* last_child = first_child->prev_sibling_c; + + last_child->next_sibling = child; + child->prev_sibling_c = last_child; + first_child->prev_sibling_c = child; + } + else { - node->last_child->next_sibling = child; - child->prev_sibling = node->last_child; - node->last_child = child; + node->first_child = child; + child->prev_sibling_c = child; } - else node->first_child = node->last_child = child; return child; } @@ -548,13 +554,21 @@ namespace { xml_attribute_struct* a = allocate_attribute(alloc); - if (node->last_attribute) + xml_attribute_struct* first_attribute = node->first_attribute; + + if (first_attribute) { - node->last_attribute->next_attribute = a; - a->prev_attribute = node->last_attribute; - node->last_attribute = a; + xml_attribute_struct* last_attribute = first_attribute->prev_attribute_c; + + last_attribute->next_attribute = a; + a->prev_attribute_c = last_attribute; + first_attribute->prev_attribute_c = a; + } + else + { + node->first_attribute = a; + a->prev_attribute_c = a; } - else node->first_attribute = node->last_attribute = a; return a; } @@ -2974,7 +2988,7 @@ namespace pugi xml_attribute xml_attribute::previous_attribute() const { - return _attr ? xml_attribute(_attr->prev_attribute) : xml_attribute(); + return _attr && _attr->prev_attribute_c->next_attribute ? xml_attribute(_attr->prev_attribute_c) : xml_attribute(); } int xml_attribute::as_int() const @@ -3189,7 +3203,7 @@ namespace pugi xml_node::iterator xml_node::end() const { - return _root ? iterator(0, _root->last_child) : iterator(); + return _root && _root->first_child ? iterator(0, _root->first_child->prev_sibling_c) : iterator(); } xml_node::attribute_iterator xml_node::attributes_begin() const @@ -3199,7 +3213,7 @@ namespace pugi xml_node::attribute_iterator xml_node::attributes_end() const { - return _root ? attribute_iterator(0, _root->last_attribute) : attribute_iterator(); + return _root && _root->first_attribute ? attribute_iterator(0, _root->first_attribute->prev_attribute_c) : attribute_iterator(); } bool xml_node::operator==(const xml_node& r) const @@ -3333,7 +3347,7 @@ namespace pugi { if (!_root) return xml_node(); - for (xml_node_struct* i = _root->prev_sibling; i; i = i->prev_sibling) + for (xml_node_struct* i = _root->prev_sibling_c; i->next_sibling; i = i->prev_sibling_c) if (i->name && impl::strequal(name, i->name)) return xml_node(i); return xml_node(); @@ -3343,7 +3357,7 @@ namespace pugi { if (!_root) return xml_node(); - for (xml_node_struct* i = _root->prev_sibling; i; i = i->prev_sibling) + for (xml_node_struct* i = _root->prev_sibling_c; i->next_sibling; i = i->prev_sibling_c) if (i->name && impl::strequalwild(name, i->name)) return xml_node(i); return xml_node(); @@ -3353,7 +3367,7 @@ namespace pugi { if (!_root) return xml_node(); - if (_root->prev_sibling) return xml_node(_root->prev_sibling); + if (_root->prev_sibling_c->next_sibling) return xml_node(_root->prev_sibling_c); else return xml_node(); } @@ -3406,7 +3420,7 @@ namespace pugi xml_attribute xml_node::last_attribute() const { - return _root ? xml_attribute(_root->last_attribute) : xml_attribute(); + return _root && _root->first_attribute ? xml_attribute(_root->first_attribute->prev_attribute_c) : xml_attribute(); } xml_node xml_node::first_child() const @@ -3416,7 +3430,7 @@ namespace pugi xml_node xml_node::last_child() const { - return _root ? xml_node(_root->last_child) : xml_node(); + return _root && _root->first_child ? xml_node(_root->first_child->prev_sibling_c) : xml_node(); } bool xml_node::set_name(const char_t* rhs) @@ -3469,21 +3483,21 @@ namespace pugi // check that attribute belongs to *this xml_attribute_struct* cur = attr._attr; - while (cur->prev_attribute) cur = cur->prev_attribute; + while (cur->prev_attribute_c->next_attribute) cur = cur->prev_attribute_c; if (cur != _root->first_attribute) return xml_attribute(); xml_attribute a(allocate_attribute(get_allocator())); a.set_name(name); - if (attr._attr->prev_attribute) - attr._attr->prev_attribute->next_attribute = a._attr; + if (attr._attr->prev_attribute_c->next_attribute) + attr._attr->prev_attribute_c->next_attribute = a._attr; else _root->first_attribute = a._attr; - a._attr->prev_attribute = attr._attr->prev_attribute; + a._attr->prev_attribute_c = attr._attr->prev_attribute_c; a._attr->next_attribute = attr._attr; - attr._attr->prev_attribute = a._attr; + attr._attr->prev_attribute_c = a._attr; return a; } @@ -3495,7 +3509,7 @@ namespace pugi // check that attribute belongs to *this xml_attribute_struct* cur = attr._attr; - while (cur->prev_attribute) cur = cur->prev_attribute; + while (cur->prev_attribute_c->next_attribute) cur = cur->prev_attribute_c; if (cur != _root->first_attribute) return xml_attribute(); @@ -3503,12 +3517,12 @@ namespace pugi a.set_name(name); if (attr._attr->next_attribute) - attr._attr->next_attribute->prev_attribute = a._attr; + attr._attr->next_attribute->prev_attribute_c = a._attr; else - _root->last_attribute = a._attr; + _root->first_attribute->prev_attribute_c = a._attr; a._attr->next_attribute = attr._attr->next_attribute; - a._attr->prev_attribute = attr._attr; + a._attr->prev_attribute_c = attr._attr; attr._attr->next_attribute = a._attr; return a; @@ -3559,14 +3573,14 @@ namespace pugi xml_node n(allocate_node(get_allocator(), type)); n._root->parent = _root; - if (node._root->prev_sibling) - node._root->prev_sibling->next_sibling = n._root; + if (node._root->prev_sibling_c->next_sibling) + node._root->prev_sibling_c->next_sibling = n._root; else _root->first_child = n._root; - n._root->prev_sibling = node._root->prev_sibling; + n._root->prev_sibling_c = node._root->prev_sibling_c; n._root->next_sibling = node._root; - node._root->prev_sibling = n._root; + node._root->prev_sibling_c = n._root; return n; } @@ -3580,12 +3594,12 @@ namespace pugi n._root->parent = _root; if (node._root->next_sibling) - node._root->next_sibling->prev_sibling = n._root; + node._root->next_sibling->prev_sibling_c = n._root; else - _root->last_child = n._root; + _root->first_child->prev_sibling_c = n._root; n._root->next_sibling = node._root->next_sibling; - n._root->prev_sibling = node._root; + n._root->prev_sibling_c = node._root; node._root->next_sibling = n._root; return n; @@ -3630,14 +3644,14 @@ namespace pugi // check that attribute belongs to *this xml_attribute_struct* attr = a._attr; - while (attr->prev_attribute) attr = attr->prev_attribute; + while (attr->prev_attribute_c->next_attribute) attr = attr->prev_attribute_c; if (attr != _root->first_attribute) return; - if (a._attr->next_attribute) a._attr->next_attribute->prev_attribute = a._attr->prev_attribute; - else _root->last_attribute = a._attr->prev_attribute; + if (a._attr->next_attribute) a._attr->next_attribute->prev_attribute_c = a._attr->prev_attribute_c; + else if (_root->first_attribute) _root->first_attribute->prev_attribute_c = a._attr->prev_attribute_c; - if (a._attr->prev_attribute) a._attr->prev_attribute->next_attribute = a._attr->next_attribute; + if (a._attr->prev_attribute_c->next_attribute) a._attr->prev_attribute_c->next_attribute = a._attr->next_attribute; else _root->first_attribute = a._attr->next_attribute; destroy_attribute(a._attr, get_allocator()); @@ -3652,10 +3666,10 @@ namespace pugi { if (!_root || n.parent() != *this) return; - if (n._root->next_sibling) n._root->next_sibling->prev_sibling = n._root->prev_sibling; - else _root->last_child = n._root->prev_sibling; + if (n._root->next_sibling) n._root->next_sibling->prev_sibling_c = n._root->prev_sibling_c; + else if (_root->first_child) _root->first_child->prev_sibling_c = n._root->prev_sibling_c; - if (n._root->prev_sibling) n._root->prev_sibling->next_sibling = n._root->next_sibling; + if (n._root->prev_sibling_c->next_sibling) n._root->prev_sibling_c->next_sibling = n._root->next_sibling; else _root->first_child = n._root->next_sibling; destroy_node(n._root, get_allocator()); @@ -3958,7 +3972,7 @@ namespace pugi const xml_node_iterator& xml_node_iterator::operator--() { - if (_wrap._root) _wrap = xml_node(_wrap._root->prev_sibling); + if (_wrap._root) _wrap = _wrap.previous_sibling(); else _wrap = _prev; return *this; } @@ -4022,7 +4036,7 @@ namespace pugi const xml_attribute_iterator& xml_attribute_iterator::operator--() { - if (_wrap._attr) _wrap = xml_attribute(_wrap._attr->prev_attribute); + if (_wrap._attr) _wrap = _wrap.previous_attribute(); else _wrap = _prev; return *this; } @@ -4094,6 +4108,8 @@ namespace pugi _root = allocate_document(alloc); + _root->prev_sibling_c = _root; + // setup allocator xml_allocator& a = static_cast(_root)->allocator; a = alloc; -- cgit v1.2.3