[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xmlbeans-dev
Subject:    RE: good overview of xmlstore impl?
From:       "Eric Vasilik" <ericvas () bea ! com>
Date:       2004-02-13 20:04:27
Message-ID: 4B2B4C417991364996F035E1EE39E2E11E9EEF () uskiex01 ! amer ! bea ! com
[Download RAW message or body]

I should do this myself, but this kind of info benefits a fairly small
community, is not visible to users, is *totally* changed in v2 and takes
a bit of time to draw all the pictures and get the words clear.  It
would be great if you want to do this.  It would be a great way to learn
the internals of v1.  I'd be glad to give you the information you need
and edit the result.

- Eric

-----Original Message-----
From: David Waite [mailto:mass@akuma.org] 
Sent: Friday, February 13, 2004 11:57 AM
To: xmlbeans-dev@xml.apache.org
Subject: Re: good overview of xmlstore impl?

Actually, this helps quite a bit. If you would like, I can work on a 
document detailing the workings of the store (possibly put on the 
Wiki).

-David Waite

On Feb 13, 2004, at 12:10 PM, Eric Vasilik wrote:

> I've not written much on the architecture of the v1 store.  The v2 
> store
> is significantly different.  Allow me to provide some information to 
> get
> you up to speed.
>
> What are splays?  Splays are nodes in a splay tree.  A splay tree is
an
> unbalanced binary tree which is capable of keeping certain metrics up 
> to
> date in (for n operation) at best O(n) time and at worst O(n log n)
> time.
>
> In order to understand why there is a splay tree here one needs to
> understand how text is stored.  Text for an entire document is stored 
> in
> a single character array.  The array is larger than the actual text,
> anticipating the extra space needed to add text to a document.  Also,
> the additional space in this text buffer is not kept at the end of the
> buffer, but at an arbitrary point inside the buffer, nearest the last
> point the text buffer was modified.  This way, one can insert and 
> remove
> text from the buffer in a given vicinity without suffering the
shifting
> of a lot of text around.  This kind of buffer is sometimes called a 
> "gap
> buffer".
>
> Now, the nodes of the XML document (sans text) are logically arranged 
> in
> a doubly linked list.  Each element of the list can represent a begin
> element, end element, attribute, comment, etc.  Each node does not
> contain any text, but contains the logical offset of its text in the 
> gap
> buffer along with the amount of text (character count) from the text
> buffer associated with this node.  Each node in the list actually
> contains offsets/counts for two pieces of text.  One for the value of
> the node, and another representing the text following the node (called
> the after text).
>
> So, one can imaging loading up a document, producing this text buffer
> and list of nodes such that the offsets and the counts are all correct
> pretty efficiently.  However, consider adding text to a node.  One 
> would
> have to walk all the nodes to the right of the modified node to update
> their text offsets by the amount added to the original node.  This 
> would
> result in O(n^2) performance for n operations.  Bad.
>
> So, what I do is instead of arranging the nodes in a simple doubly
> linked list, I arrange them in a splay tree.  A pre-order walk of the
> tree produces the same order you would find them in the list.  And,
> without getting into details, I can use the characteristics of the 
> splay
> tree to update the offsets in o(n) time.  That, along with the gap
> buffer yields pretty decent performance.
>
> This has been rather terse.  Please let me know what you would like
mor
> information on, and I'll be happy to continue the discussion.
>
> - Eric
>
> -----Original Message-----
> From: David Waite [mailto:mass@akuma.org]
> Sent: Saturday, February 07, 2004 7:48 PM
> To: xmlbeans-dev@xml.apache.org
> Subject: good overview of xmlstore impl?
>
> I've been trying for a substantial amount of time today to figure out
> the underlying objects for xmlbeans (v1). I have a bit of a nebulous
> understanding now, but I am wondering if there is any lower-level
> documents describing what splays and goobers are. I cannot find either
> an architectural document, any diagrams, or (for that matter) comments
> on the actual types being used.
>
> Is there any good overview of what is going on underneath the covers?
> has any of this changed so far for v2?
>
> -David Waite
>
> -
---------------------------------------------------------------------
> To unsubscribe, e-mail:   xmlbeans-dev-unsubscribe@xml.apache.org
> For additional commands, e-mail: xmlbeans-dev-help@xml.apache.org
> Apache XMLBeans Project -- URL: http://xml.apache.org/xmlbeans/
>

- ---------------------------------------------------------------------
To unsubscribe, e-mail:   xmlbeans-dev-unsubscribe@xml.apache.org
For additional commands, e-mail: xmlbeans-dev-help@xml.apache.org
Apache XMLBeans Project -- URL: http://xml.apache.org/xmlbeans/


[prev in list] [next in list] [prev in thread] [next in thread]