Glib's trees and FYI: TkText widget

[Derek Simkowiak <dereks kd-dev com>]

	I am one of the people working on a GtkText replacement widget.

	Havoc suggested I examine the TkText widget (as in Tcl/Tk) as a
possible model for the new GtkText.  It turns out to have a nice design,
using a BTree to store the data.

	The BTree holds nodes of "lines", where a line is a \n-deliniated
section of text.  Each tree node ("line") contains a linked list of
"segments", where a segment is a section of text, a tag, an image, an
embedded widget, or basically anything the renderer would need to draw.  
Each of the these 'segments' knows how to draw itself.

	The widget spends a large amount of time in these linked lists of
segments.  Also, the TkText falls apart if you do not have \n's
distributed semi-regularly throughout your text.

	Using lines as nodes of the BTree is a good idea because it makes
for easy line-drawing code, and scrolling and selections become much
easier to deal with (and fast).  If the 'segments' (i.e., text properties
and such) were made part of the BTree then drawing lines and related code
would require walking up and down the tree, and would be fairly
complicated, so getting around the linked lists by having everything in
the tree is a bad idea.

	I'm considering using the same general scheme (i.e., a BTree of
lines) for the new GtkText, but then instead of using a linked list within
the nodes of the lines, I'd like to use a sub-tree that contained the
segments of each "line" node.  This would give the speed and efficiency of
the TkText, without getting bogged down in linked lists.  For now, I'd
just have a text-property segment (font/color info) but in the future we
could have images, tables, whatever.

	My question is regarding Glib's n-ary trees.  If I have a tree, in
which the nodes each have sub-trees, what will happen to the system's
memory?  I'm concerned about fragmentation and access times.

	I know that, with linked lists, if you add and remove large
numbers of items you can walk through memory unless you use a pool of
pointers.  I believe Glib handles this with its GAllocator, but I'm not
sure.  Are there any similar issues with a tree?

	Could there be any weird side-effects caused by having a tree at
each node of a tree?

	Finally, below is the response I got from Brent Welch when I asked
him about the TkText design.


Thank You,
Derek Simkowiak
dereks@kd-dev.com


On Mon, 3 Jan 2000, Brent Welch wrote:

> John Ousterhout built the Text widget, and I did some dabbling in the code
> so I had to understand its data structures.
> Scott Stanton did the i18n work on it.  I'm probably the best person to
> contact because Ousterhout is quite busy.
> 
> The Gtk crew should seriously consider a Tcl interface to it - perhaps
> it exists already.  But you cannot ignore that Tk basically crushed
> Motif.  Unfortunately, folks have been building new widget sets like
> Gtk instead of enhancing the Tk widget set.  I've programmed everything
> from device drivers, network protocols, distributed file systems,
> to user interfaces for email and web servers.  If found Tcl/Tk to be
> the most productive!
> 
> The high-level view of the Text widget is that the B-Tree is used for lines,
> but each line is a linked list of "segments".  Each segment holds either
> text (up to a newline), a "mark", or a "tag on"/"tag olff", or an image,
> or an embedded widget.  Each of this objects has methods to displaay 
> themselves,
> etc.
> 
> A cool trick, which I helped to optimize, is the way the tag information
> is stored.  At each node in the B-Tree is a list of tags that are active
> below that point.  This way you can search from a leaf to the root and
> figure out all tags that are "on".  Also, you can quickly skip from range
> to range of a tag.  John invented this, I just optimized the storage for it.
> 
> There are two main flaws in the current design.
> 
> 1) Ousterhout didn't predict that text widget lines would become complex,
> but in fact i found lines with many segments (order 20).  So, the code spends
> a lot of time searching these singly linked lists of segments.  I've long
> wanted to ditch the segment list and move them into the B-Tree as well.
> For example, if you have a megabyte of text with no newline characters
> then it will all be one line!
> 
> 2) The scrolling is line oriented, not pixel oriented.  This means that pages
> with large embedded images don't scroll as users expect.  This requires more
> ripping and tearing at the code, but it might not be so bad.
> 
> 3) More minor - you really want to be able to ask the text widget how
> big it wants to be to display all its text.  Sort of a -width 0 -height 0
> that automatically sizes.  This is mandatory if you want to use the
> text widget to emulate HTML tables.
> 
> >>>Derek Simkowiak said:
>  >      Hello,
>  > 	My name is Derek Simkowiak.  I am trying to get in touch with the
>  > author/designer of the TkText widget.  The RCS $Id tag shows the username
>  > 'stanton'.
>  > 
>  > 	I am working on the Gtk+ toolkit (http://www.gtk.org), and we need
>  > a decent text widget.  After much looking around, it appears that the Tk
>  > widget is one of the best, fastest designs out there.  It is the only text
>  > editor I have seen that uses a BTree to store the data, instead of a
>  > gapped text buffer (or something else lame, like a linked list of some
>  > sort).
>  > 
>  > 	I am considering trying to port the Tk text widget to Gtk+, but I
>  > have some questions about the design, so I'd like to email a couple of
>  > questions to the author.  Also, if there is any documenation on the
>  > widget's design, layout, or operation (other than the source code itself)
>  > please point me towards it.
>  > 
>  > 	Any help is greatly appreciated.
>  > 
>  > 
>  > Thank You,
>  > Derek Simkowiak
>  > dereks@kd-dev.com
>  > 
>  > 
> 
> --	Brent Welch	<welch@scriptics.com>
> 	http://www.scriptics.com
> 	Scriptics: The Tcl Platform Company
> 
>