Piece Chains
OK so I lied about getting the syntax-highlighting implemented this time around. I got bogged down in “regular expression hell” and needed something else to concentrate on. So during the summer period I’ve instead been slowly implementing Neatpad’s text-editing capability. As I hinted at in the very first installment of this tutorial series, I have decided to follow the “Piece Table” design. The aim of this tutorial will be to discuss the rationale behind this decision and also highlight some (but not all) of the implementation details. Note that I will not be discussing issues related to the editing of Unicode text (this will come in the next tutorial). Instead we will look at the design of the piece-table from a low-level perspective, independent of any Unicode concerns.
Several years ago when I started writing HexEdit there was very little information I could find regarding editor design. Google was unheard of and AltaVista was the search-engine of choice. I had a 33k dial-up modem and the single resource I stumbled over at the time was a paper written by a University professor named Charles Crowley. His paper ‘Data Structures for Text Sequences’ and the ‘Piece Table’ approach he described heavily influenced the design of HexEdit, making it one of the slickest hex-editors available. I later documented HexEdit’s piece-table design (or span-table, as I called it then) in my ‘Memory Management for Large File Editors’ article. Today there seems to be a little more information available regarding Piece-Tables - and certainly more evidence of people using this design in their projects:
