xerox CSL-94-10 Ropes Are Better Than Strings free download

File name CSL-94-10_Ropes_Are_Better_Than_Strings.pdf

Ropes Are Better Than Strings Hans-). Boehm, Russ Atkinson and Michael Plass Ropes Are Better Than Strings Hans-J. Boehm, Russ Atkinson and Michael Plass CSL-94-10 Septem ber 1994 [P94-00091 ] @ Copyright 1994 Xerox Corporation. All rights reserved. CR Categories and Subject Descriptors: E.2 [Data Storage Representations]: Primitive Data Items Additional Keywords and Phrases: Strings, Ropes, Trees, Concatenation, Data Structures Xerox Corporation XEROX Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, California 94304 Ropes Are Better Than Strings Hans-J. Boehm Russ Atkinson Michael Plass XeroxPARC Abstract Programming languages generally provide a "string" or "text" type to allow manipulation of sequences of characters. This type is usually of crucial importance, since it is normally mentioned in most interfaces between system components. We claim that the traditional implementations of strings, and often the supported functionality, are not well suited to such general-purpose use. They should be confined to applications with specific, and unusual, performance requirements. We present "ropes" or "heavyweight" strings as an alternative that, in our experience leads to systems that are more robust, both in functionality and in performance. Ropes have been in use in the Cedar environment almost since its inception, but this appears to be neither well-known, nor discussed in the literature. The algorithms have been gradually refined. We have also recently built a second similar, but somewhat lighter weight, C-Ianguage implementation. We describe the algorithms used in both, and give usage examples and performance comparisons for the C version. What's Wrong With Strings? Programming languages such as C and traditional Pascal provide a built-in notion of strings as essentially fixed length arrays of characters. The language itself provides the array primitives for accessing such strings, plus often a collection of library routines for higher level operations such as string concatenation. Thus the implementation is essentially constrained to represent strings as contiguous arrays of characters, with or without additional space for a length, expansion room, etc. There is no question that such data structures are occasionally appropriate, and that an "array of characters" data structure should be provided. On the other hand, since the character string type will be used pervasively to communicate between modules of a larg