jkh@ardent.UUCP (07/06/88)
The way memory is allocated and manipulated for string source text widgets begins to lose rapidly as the amount of text manipulated grows. For example, open a compose window with xmh and use M-I to insert a reasonably large file (like /etc/termcap). Go back to the top and insert a few characters. chomp chomp. I haven't had occasion to use disk source widgets yet, so I don't know if they're a significant win in this regard (though there will always be situations where paging from a file is impractical). Anyway.. This isn't so much a flame as it is a question. Is anyone working on a different storage mechanism for string source widgets? It seems a pity to provide a widget that lends itself so well to general editing and then make it impractical to do so. Jordan
gringort@decwrl.dec.com (Joel Gringorten) (07/07/88)
In article <8807052356.AA00142@scrod.ardent.com> jkh@ardent.UUCP writes: >The way memory is allocated and manipulated for string source text widgets >begins to lose rapidly as the amount of text manipulated grows. Your observation is well founded. StringSource is really designed for small text strings. [article trimmed to save space] Is anyone working on a different >storage mechanism for string source widgets? >a widget that lends itself so well to general editing and then make it >impractical to do so. > > Jordan You might want to take a look at the PieceSource which I wrote for xedit (on the MIT tapes). The piece source works on the piece table principle, where you maintain a table of "pieces" of your text. When you create a piece source you supply two input sources -- a read-only source and an append-only source. A piece merely contains the start and end positions and the source where the data is actually located. The input source gets loaded with the original file bits, using say, the disk source. Keystrokes and other new text to be edited into the file, simply get added to the append-only source. Any change to the piece source is just a change in the table. The piece source implementation uses a linked list of pieces with some simple heuristics for speeding up piece location. Real programmers often use a balanced binary tree for this operation. PieceSource also has built-in undo/redo operations, which simply undo or redo the pointer manipulations which were done by the changes. No actual data is ever moved, once the new data has been entered into the append source. Performance is independant of buffer size, although degrades in random piece location as the number of changes increases. This is where the binary tree would be useful. There are certainly a multitude of ways to organize the internal data in a text source, including line tables, empty-hole buffers, etc. Maybe the PieceSource will get you started. If you come up with anything really spectacular, be sure to let us know. -- -joel