Re: [gtk-list] Glib's trees and FYI: TkText widget

[Leon <leon udmnet ru>]

Derek Simkowiak wrote:

>         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.
>

As you probably remember, I suggested that nodes of tree should keep
chunks of text which are being split in two if bloated up to a certain 
limit. Unfortunately this virtually ignores presense of '\n' in the text 
in the role of line delimiters. But IMHO \n's themselves are outdated. 
They are a thing of 80x25 text terminals era. Nowadays linewrap depends 
on a widget size and varies. That's simply a fact. I'm afraid that 
disposition of chunks of text in tree should have no connection with
linewrap/linebreak. You can see a linebreak ('\n') as a thing that grabs
the whole visible space in the end of line, so forcing a linewrap before 
the next character.
 
>         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.

Not exactly. BTree is simply a container. Nothing more. It's used
because of it's speed. And as any container, it can have an abstracted
interface through which to be talked to. Just think carefully what
operations you want from this data storage and write interface 
functions. That will not be alot, I suppose.These will be operations
of various kind lookup/insert. That's not a big trouble. OTOH, keeping
text together with it's attributes makes them behave like objects. 
That is a Good Thing (tm).

> 
>         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.
> 

That's what i'm talking about. Forget \n - delimited lines as chunks 
and have one big tree of various chunks.

>         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.
> 

This is a question of memory management. It makes no difference where 
you keep your data. What matters is sizes of pieces and how often you
reallocate them. Malloc is the Great Equalizer :)


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

Hmm, I don't see 'tree with subtrees'. I see one Big Binary Balanced 
Tree:)
 
If you are intereted in that ideas you can write directly to me.

Leon.