Rope Implementation Overview
The rope container type included in SGI's version of the STL is based loosely on the ropes in the Xerox Cedar environment or C "cords", as described in Boehm, Atkinson, and Plass, "Ropes: An Alternative to Strings", Software Practice and Experience 25, 12 (Dec 1995), pp. 1315 - 1330.
A rope is represented as a pointer to
Each tree node contains a size field giving the length of the rope piece, a depth field specifying the depth (or height) of the tree rooted at the node, a boolean field indicating whether the subtree has been balanced, and a tag field indicating which of the four variants or subclasses of
It would have been possible to use virtual functions and/or RTTI to replace the use of the tag field. We chose not to pursue that route, since the tag field can be much smaller than a vtable pointer, and the tag based code is probably also faster in this case.
The 4 subclasses of
Only concatenation nodes have nonzero depth fields. Depth fields are guaranteed to fit into a byte, since we impose a static maximum on rope depth.
Reference Counting and Synchronization
The rope implementation can be compiled in two different ways. Normally __GC will not be defined. In this case each tree node will also contain a reference count field. This keeps track of the number of rope variables, concatenation nodes, or substring nodes that reference the tree node. (We'll see later that references from some iterators are also included.) When the reference count of a tree node becomes zero, the tree node is deallocated, and reference counts of any subtrees are correspondingly decremented.
In a few cases, the reference counts are also used to allow in-place updates of ropes. If the reference counts of all tree nodes on the path from a rope R's root node to the leaf node L holding a specific character are 1, then L occurs exactly once in R, and in no other rope. Thus R can safely be updated by updating L in place.
If the rope implementation is compiled with
The remainder of this section assumes that __GC is not defined, and that reference counts are used.
Since rope nodes can be shared by different ropes, which can be concurrently copied, updated, or destroyed by different threads, reference counts must be updated atomically. This is the only explicit synchronization performed by the implementation, since the reference count is the only part of a potentially shared data structure that is updated.
The synchronization required for reference count updates may consume a significant fraction of the time required for rope operations. Reference count updates should be implemented in terms of an atomic add operation whenever such an operation is available. It is important that the reference count decrement operation not only atomically decrement the count, but also return the result as part of the atomic operation. If the zero test is performed outside the atomic part of the operation, the same tree node may be deallocated twice.
On Irix and win32 platforms, the current implementation maintains reference counts using an atomic add operation. A more generic implementation based on PThread mutexes is also provided. But it is unlikely to provide optimal performance for applications that use ropes extensively.
The rope implementation can use either standard-conforming allocators (compiler permitting) or SGI-style simplified allocators. In the former case and if there are distinct allocator instances of a given allocator type, the allocator instance is stored in each rope tree node, as well as in the rope itself. It is illegal to concatenate ropes built with different allocator instances.
This representation was chosen because it keeps the implementation comparatively clean, and the instance-less case reasonably efficient. The alternative of storing the allocator instance only in the rope would have added additional allocator arguments to many internal functions. It would have been difficult to eliminate this overhead for allocator types that do not have distinct instances.
Basic Algorithms and Rope Balancing
Concatenation is normally implemented by allocating a new concatenation node, and having it refer to the two arguments to the concatenation operation. Thus in most cases its execution time is independent of the length of strings.
The case in which a short rope consisting of a single leaf is concatenated onto the right of a rope which is either a leaf, or a concatenation node whose right child is a leaf, is handled specially. In this case, if the leaves in question are sufficiently short, we may either allocate a new leaf holding the combined contents of the two leaves or, under the right circumstances, even update the left operand in place. In order to allow the destructive update, the actual arrays holding leaf characters are grown in increments of 8.
For example, the rope "abcedefghigklmnopqrstuvwxy" might be concatenated to "z" as shown in the following figure:
Handling this case specially guarantees that ropes built by repeatedly concatenating short strings onto the right will be composed of leaves of a minimum size, and thus can be stored and processed efficiently. It has a similar effect on repeated character insertions in the same position.
Although concatenation is efficient independent of the shape of the tree, some other operations such as retrieving the ith character, are more efficient if the tree representing the rope is approximately balanced. Ropes can be rebalanced either via an explicit call to the
The balance operation proceeds as described in the paper cited above. The operation is non-destructive; rebalanced pieces formerly shared with other ropes are no longer shared after the operation. As a rope is being balanced, the balanced bit is set in each concatenation node that has sufficiently small depth for its length. Tree nodes with the balanced bit set are not examined by further balancing operations. Thus the balance operation tends to not rebalance the same substring.
The worst-case cost of rebalancing is nonetheless linear in the string. However, the observed behavior is that rebalancing typically consumes a small fraction of the running time. Indeed, all natural ways of building a rope of length N by repeated concatenation require total time linear in N. It is possible, but nontrivial, to design concatenation sequences that violate this.
The substring operation is performed differently depending on the tree node representing the root of the rope. The operation is recursive:
Note that this process requires time proportional to the rope depth, and doesn't directly depend on the length. The algorithm only copies pieces of leaf nodes at the beginning and end of the substring, and it builds new concatenation nodes along the paths from the root to either end of the substring. The interior of the substring can remain shared with the original rope.
Iterators generated by the normal
We maintain two kinds of cache information in the iterator:
This implementation differs significantly from that used in the C "cord" package. We do not reserve space inside iterators for a complete path from the root to the current node. This change was made to accommodate STL code that assumes small iterators that can be cheaply passed by value. We try to aid such code further by providing an iterator assignment operation which does not copy the cache part of the iterator unless it has been initialized.
The character buffer in the iterator is needed since there is not another place to cache characters returned for the evaluation of a function node. (This is less of an issue with a garbage collector, since it turns out to be reasonably efficient to maintain such caches in the function object itself. Without a garbage collector, this requires locking around cache accesses, which is usually unacceptable.)
Mutable iterators differ primarily in that they also contain a pointer to the rope itself (i.e. a pointer to the tree node pointer), so that they can be used to perform updates, and in that the rope root pointer is included in the reference count. In this case the rope root pointer is redundant, except that it us used to detect changes in the rope, so that the cached information in the iterator can be invalidated. The rope has changed iff the rope itself no longer points to the same node as the rope root pointer in the iterator. The fact that the iterator is included in the reference count ensures that the root node cannot be dropped and reused. It also prevents the rope from being destructively updated while the iterator must remain valid.