home | login | register | DMCA | contacts | help | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


my bookshelf | genres | recommend | rating of books | rating of authors | reviews | new | форум | collections | читалки | авторам | add
fantasy
space fantasy
fantasy is horrors
heroic
prose
  military
  child
  russian
detective
  action
  child
  ironical
  historical
  political
western
adventure
adventure (child)
child's stories
love
religion
antique
Scientific literature
biography
business
home pets
animals
art
history
computers
linguistics
mathematics
religion
home_garden
sport
technique
publicism
philosophy
chemistry
close

Loading...


Iterators

Iterators generated by the normal begin() and end() operations generate const_iterators, i.e. iterators that do not permit updates to the underlying rope. Such iterators basically contain three kinds of information:

1. A pointer to the root node of the rope with which the iterator is associated. This pointer is not included in the reference count, Const_iterators become invalid if the underlying rope is modified or destroyed. (In the garbage collected case they remain valid and continue to refer to the original pre-modification rope.)

2. The position inside the rope.

3. Cached information used to speed up access to sections of the rope close to the current position.

We maintain two kinds of cache information in the iterator:

1. The limits of a contiguous block of storage holding the characters surrounding the current character position, and the current offset within that block. Most iterator references can be resolved with access to only this part of the cache. The referenced block of storage can either be part of a leaf in the rope representation, or it can be a small block of characters reserved inside the iterator itself. The latter is used when the iterator refers to a rope section represented by a function node.

2. The bottom few rope nodes on the path from the root node to the leaf or function node currently referenced by the iterator. This is used to quickly increment or decrement the iterator across node boundaries. We do not cache the entire path, since that would make rope iterators unpleasantly large.

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.


Basic Algorithms and Rope Balancing | Standard Template Library Programmer`s Guide | SGI STL Allocator Design







Loading...