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...


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 __GC defined, it will assume that there is an underlying garbage collector and inaccessible tree nodes will be automatically reclaimed. In this case rope must be instantiated with a suitable garbage-collecting allocator, and no reference count is maintained. Thus the above optimization for in-place updates is also not implemented. Since even non-destructive updates copy only portions of a rope, and since many rope clients will use them purely as immutable strings, this is often not a serious loss. But it may be for some applications.

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.


Rope Implementation Overview | Standard Template Library Programmer`s Guide | Allocator Use







Loading...