§12.4
Performance of quicksort and merge sort 239
Member
HashDictionary<K,V>
TreeDictionary<K,V>
AddSorted(kvs)
O
(
mlog n
)
Comparer
O
(
1
)
Cut(cmp,,,,)
O
(
logn
)
DeleteMax()
O
(
logn
)
DeleteMin()
O
(
logn
)
FindMax()
O
(
logn
)
FindMin()
O
(
logn
)
Keys
O
(
1
)
Predecessor(k)
O
(
logn
)
RangeAll()
O
(
logn
)
RangeFrom(k1)
O
(
logn
)
RangeFromTo(k1, k2)
O
(
logn
)
RangeTo(k2)
O
(
logn
)
RemoveRangeFrom(k1)
O
(
rlog n
)
RemoveRangeFromTo(k1, k2)
O
(
rlog n
)
RemoveRangeTo(k2)
O
(
rlog n
)
Successor(k)
O
(
logn
)
WeakPredecessor(k)
O
(
logn
)
WeakSuccessor(k)
O
(
logn
)
Figure 12.6: Performance of dictionary operations in ISortedDictionary<K,V>.
12.3 Performance of quicksort and merge sort
The sorting algorithm for array lists is introspective quicksort, whose implementa-
tion is described in section 13.2. It has the following performance properties:
 It is as fast as quicksort on random data.
 It is guaranteed fast: The worst-case running time is
O
(
nlog n
), and therefore
much faster than plain quicksort on bad data sets.
 It requires only
O
(
logn
)extra space (in addition to the array list).
The sorting algorithm for linked lists is a stable in-place merge sort, whose imple-
mentation is described in section 13.3. It has the following performance properties:
 It is guaranteed fast: The worst-case running time is
O
(
nlog n
). In practice, it
is slower than quicksort for arrays by a factor of two or so.
 It requires no extra space (in addition to the linked list).
12.4 Performance impact of list views
 Update overhead: Updates to a list may affect the
Offset
or
Count
of views
on the list. To implement this, every update must check for affected views, so
there is a runtime overhead that is proportional to the number of valid views
on the list; see section 13.9. For this reason, it is important to invalidate views
on lists as early as possible; see below.
Pdf to tiff file - application Library tool:C# PDF Convert to Tiff SDK: Convert PDF to tiff images in C#.net, ASP.NET MVC, Ajax, WinForms, WPF
Online C# Tutorial for How to Convert PDF File to Tiff Image File
www.rasteredge.com
Pdf to tiff file - application Library tool:VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.net, ASP.NET MVC, Ajax, WinForms, WPF
Free VB.NET Guide to Render and Convert PDF Document to TIFF
www.rasteredge.com
240 Performance impact of tree snapshots
§12.6
 Space leaks: A range view of a sorted collection or asorted dictionary contains
areference to the underlying collection or dictionary. This may cause a so-
called space leak if a small range view refers to a large underlying collection.
So long as the small range view is kept alive by the program, the underlying
collection is kept alive as well, and the space it occupies cannot be reclaimed
by the garbage collector. To avoid this, do not keep views alive unnecessarily.
 When a view is invalidated, it stops holding on to the underlying list, and
no longer affects the execution time of updates. Invalidation of a view
u
can
be requested by calling
u.Dispose()
. If a view variable
u
is allocated by C#’s
using
statement, then
u.Dispose()
is called automatically when the variable
goes out of scope; see pattern 24.
12.5 Performance impact of event handlers
If each call to an event handler executes in constant time, then event handlers will
not change the asymptotic running time of collection operations. That is, an
O
(
1
)
operation does not suddenly become an
O
(
n
)operation just becausean event handler
has been attached to the collection on which the operation is performed.
This is a conscious design decision, one consequence of which is that the
Clear
method on a list view does not raise an ItemsRemoved event for each item removed.
Namely, without event handlers,
list.View(i,n).Clear()
can be performed in con-
stant time when
list
is a linked list, but if an ItemsRemoved event must be per-
formed for each item, then it would become an
O
(n) operation.
As described in section 13.12, the implementation of events is designed to mini-
mize the runtime overhead in the frequent case where no event handlers are asso-
ciated with a collection.
12.6 Performance impact of tree snapshots
Creating a tree snapshot itself takes constant time, independent of the size of the
tree. Each modication to the original tree may take extra time and space as long
as the snapshot is alive. For any single update to the original tree, the time and
space overhead may be
O
(
logn
), where
n
is the size of the tree, but the amortized
run-time andspace cost is
O
(
1
)per update tothe original tree. Over along sequence
of updates, there is just a constant amount of extra work per update.
Oncethe snapshot has been deallocated by the garbage collector, further updates
to the tree does not incur extra time or space costs. Therefore snapshots should
preferably be allocated in a
using
statement so that they get released eagerly; see
section 9.11.
In the worst case, where a snapshot is kept alive indenitely and the original
tree is updated aggressively, the snapshot will end up being a clone of the entire
original tree, after which further updates to the original tree will incur no further
overhead. See section 13.10 for more details on the implementation.
application Library tool:Online Convert PDF file to Tiff. Best free online PDF Tif
Using this .NET PDF to TIFF conversion control, C# developers can render and convert PDF document to TIFF image file with no loss in original file quality.
www.rasteredge.com
application Library tool:Online Convert PDF file to Word. Best free online PDF Conversion
Download Free Trial. Convert a Tiff/Tif File to PDF. Then just wait until the conversion from Tiff/Tif to PDF is complete and download the file.
www.rasteredge.com
Chapter 13
Implementation details
13.1 Organization of source les
File ordirectory
Contents
C5/AssemblyInfo.cs
Versionnumber and similar
C5/BuiltIn.cs
IntComparer, DoubleComparer, ...
C5/Collections.cs
Collection base classes (see chapter14)
C5/Comparer.cs
Comparer<T>, NaturalComparer<T>,...
C5/Delegate.cs
Delegates types Act<A1>, ...,Fun<A1,R>, ...
C5/Dictionaries.cs
Dictionary base classes (see chapter 14)
C5/Enums.cs
Enum types Speed,EnumerationDirection,...
C5/Events.cs
Event handler types and event raising
C5/Exceptions.cs
Exception classes
C5/Formatting.cs
IShowable and formatting
C5/Hashers.cs
EqualityComparer<T>, ...
C5/Interfaces.cs
Collection and dictionary interfaces
C5/Random.cs
C5Random
C5/Records.cs
Record struct typesRec<T1,T2>,...
C5/Sorting.cs
Introspective quicksort,heapsort, ...
C5/WrappedArray.cs
WrappedArray<T>
C5/Wrappers.cs
Guarded collectionsand dictionaries
C5/arrays/ArrayList.cs
Arraylist<T> and ?HashedArrayList<T>
C5/arrays/CircularQueue.cs
CircularQueue<T>
C5/arrays/SortedArray.cs
SortedArray<T>
C5/hashing/HashBag.cs
HashBag<T>
C5/hashing/HashDictionary.cs
HashDictionary<K,V>
C5/hashing/HashTable.cs
HashSet<T>
C5/heaps/IntervalHeap.cs
IntervalHeap<T>
C5/linkedlist/LinkedList.cs
LinkedList<T> and ?HashedLinkedList<T>
C5/trees/RedBlackTreeDictionary.cs
TreeDictionary<K,V>
C5/trees/RedBlackTreeSet.cs
TreeSet<T>and ?TreeBag<T>
The les above are found in the source distribution
C5.src.zip
.The source le for a
241
application Library tool:C# Create PDF from Tiff Library to convert tif images to PDF in C#
TIFFDocument doc = new TIFFDocument(inputFilePath); // Convert loaded TIFF file to PDF document. doc.ConvertToDocument(DocumentType.PDF, outputFilePath);
www.rasteredge.com
application Library tool:Online Convert Excel to PDF file. Best free online export xlsx
Download Free Trial. Convert a Excel File to PDF. Your file will then be instantly converted to PDF and ready to download. The perfect conversion tool.
www.rasteredge.com
242 Implementation of merge sort for linked lists
§13.3
class marked with an asterisk (?) is generated by a preprocessing tool found in le
PreProcess/Program.cs
.The overall structure is the source distribution is this:
File ordirectory
Contents
BUILD.txt
Instructions for building from source
LICENSE.txt
Library license, reproduced on page 3
RELEASE-NOTES.txt
List of changes in current release
C5/
Library source code;see above
docNet/
Files to build online documentation
nunit/
Files to build unit tests,to be runwith NUnit [1].
PreProcess/
Preprocessor to build source for classes marked (?) above
UserGuideExamples/
Source for examples inchapter 11
The C5 library can be built from source on Microsoft’s .NET 2.0 as well as Novell’s
Mono implementation. File
BUILD.txt
in the source distribution contains instruc-
tions for building the library, online documentation and unit tests.
13.2 Implementation of quicksort for array lists
This sorting algorithm works on array lists and is used in the implementation of
the
Sort
methods in class ArrayList<T> and the static
IntroSort
methods in class
Sorting. The algorithm has the following properties:
 It is as fast as quicksort on random data.
 It is guaranteed fast: The worst-case running time is
O
(
nlog n
), and therefore
much faster than quicksort on bad data sets.
 It requires only
O
(
logn
)extra space in addition to the array being sorted.
 It is not stable: two items in the given array that compare equal may be
swapped in the sorted result. For a stable sorting algoritm, use merge sort
on linked lists (section 13.3).
The algorithm is due to Musser [23]. It is basically a quicksort that keeps track of
its own recursion depth. Then it switches to using heap sort when the recursion
depth becomes too large, which is a sign that the partitioning performed by the
quicksort has repeatedly turned out bad.
13.3 Implementation of merge sort for linked lists
This sorting algorithm works on linked lists andis usedin the implementation ofthe
Sort
methods in class LinkedList<T>. The algorithm has the following properties:
 It is stable: The order ofequal items in the given list is preserved in the sorted
list. This permits multi-key (lexicographic) sorting to be performed in several
passes, starting with the least signicant key in the lexicographic ordering
and ending with the most signicant key.
application Library tool:VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Also able to uncompress PDF file in VB.NET programs. Offer flexible and royalty-free developing library license for VB.NET programmers to compress PDF file.
www.rasteredge.com
application Library tool:C# PDF File Split Library: Split, seperate PDF into multiple files
Application. Best and professional adobe PDF file splitting SDK for Visual Studio .NET. outputOps); Divide PDF File into Two Using C#.
www.rasteredge.com
§13.5
Implementation of hash-based collections 243
 It is in-place: It requires no extra space besides the linked list’s nodes.
 It is guaranteed fast: The worst-case running time is
O
(
nlog n
).
In practice, merge sort is two to three times slower than introspective quicksort
(section 13.2). Our in-place merge sort algorithm builds an outer list of runs, where
arun is an inner list ofnodes whoseitems appear in (weakly)increasing order. Then
theruns are repeatedly mergedpairwise in order of appearance, creating longer and
longer runs, until all nodes make up a single run: the sorted list.
The inner lists and the outer lists are singly-linked, because they need to be tra-
versed in only one direction. The nodes of each inner list are linked together using
thenext-node reference ofthe participating LinkedList<T> nodes, terminating with
a
null
next-node reference. The nodes of the outer list (which is a list of inner lists)
are linked together using the previous-node reference in the rst node of each inner
list. Hence no extra space is required.
13.4 Implementation of hash-based collections
For experimental purposes the source code contains several variations of linear
hashing, namely linear probing and linear chaining [9] in combination with both
reference type bucket cells and value type bucket cells. The combination actually
used is determined by preprocessor ags
LINEARPROBING
,which determines whether
the code uses linear probing or linear chaining, and
REFBUCKET
which determines
whether the rst bucket is of reference type (pointed to from the collection’s array)
or value type (stored directly in that array).
The choice of trying these variations oflinear hashing was based on the ndings
of Pagh and Rodler [24]. All implementations have the usual theoretical complex-
ities:
O
(
1
)expected time for lookups and
O
(
1
)expected amortized time for update
operations. There are other linear hashing strategies such as double hashing, but
we have not implemented those.
The current compilation default is to use linear chaining and reference type
buckets; over a range of experiments this seems to offer the best performance. A
hash-based collection is therefore implemented by an array, each item of which con-
tains
null
or a reference to a bucket. With linear chaining, a bucket contains an
item, the item’s cached hash code, and a reference that is
null
or refers to an over-
ow bucket.
The array size always is a power of two, and the index for an item (bucket) is
computed from the hash value using auniversal hash function family mentioned by
Pagh and Rodler [24]:
index = (k * hashval) % tablesize
Here
k
is constant overat least thelifetimeofa specic array. The preprocessor ags
INTERHASHER
and
RANDOMINTERHASHER
determine whether
k
is a large odd compile
time constant or a random odd integer. The last choice should provide the good,
randomized expected complexity asymptotics.
application Library tool:VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
Combine multiple specified PDF pages in into single one file. VB.NET Components to combine various scanned images to PDF, such as tiff, jpg, png, gif, bmp
www.rasteredge.com
application Library tool:VB.NET PDF File Split Library: Split, seperate PDF into multiple
Professional VB.NET PDF file splitting SDK for Visual Studio and .NET framework 2.0. Split PDF file into two or multiple files in ASP.NET webpage online.
www.rasteredge.com
244 Implementation of linked lists
§13.8
13.5 Implementation of array lists
An array list consists of an underlying extensible array and an indication of the
number of items actually in the array list.
Aview of an array list consists of a reference to its underlying array list, an
offset relative to that array list, an item count, and an indication whether the view
is valid. A view and its underlying array list have the same underlying extensible
array.
Aproper array list (not a view) has a list all its views, so that it can update
any affected views whenever the array list is updated. For instance, insertions and
deletions may affect the offset and the count of a view, and sorting, shufing and
subrange reversal may invalidate a view. The list contains weak references to the
views, so that the views are not kept alive longer than necessary.
13.6 Implementation of hashed array lists
Class HashedArrayList<T> is implemented as an arraylist that additionally has a
hash dictionary that maps an item to the unique index of that item in the list, if
any. The hash dictionary is shared between the hashed arraylist and all views of it.
Still,
view.Contains(x)
,where
view
is a view on list
list
,can be implemented in
expected constant time, as follows. First the index of
x
is looked up in the hash dic-
tionary, and if it is there, then it is checked that the index is between the endpoints
of
view
,using two integer comparisons.
13.7 Implementation of linked lists
Alinked list is implemented as a doubly linked list of nodes, each node holding an
item. A doubly linked list is preferred over a singly linked one because it permits
efcient insertion and deletion at either end, and efcient insertion and deletion at
views inside the list.
There is an articial sentinel node at each end of the double linked list, and a
LinkedList<T> object always has non-
null
references to these sentinel nodes. This
signicantly reduces the number of cases that must be considered in operations.
Aview of a linked list consists of a reference to its underlying linked list, refer-
ences to start andend sentinel nodes (which aresimply nodes in theunderlying list),
an offset relative to the underlying list, an item count, and an indication whether
the viewis valid. All nodes of aview, including the sentinel nodes, belong also to the
underlying linked list.
Aproper linked list (not a view) further has a list all its views, so that it can up-
dateany affected views whenever the linkedlist is updated. For instance, insertions
and deletions may affect the offset andthecount ofa view, and sorting, shufing and
subrangereversal may invalidate a view. The list uses weak references totheviews,
so that views are not kept alive longer than necessary.
§13.8
Implementation of hashed linked lists 245
13.8 Implementation of hashed linked lists
Class HashedLinkedList<T> is a linked list that additionally has a hash dictionary
that maps an item to the unique list node containing that item, if any. The hash
dictionary is shared between the hashed linked list and all views of it.
Obtaining the best asymptotic performance for the combination of list views and
hash indexing is rather challenging. Namely, if
view
is a view on a list
list
,then
view.Contains(x)
should befast and should return false if
x
is in the underlying list
but not inside the view. Therefore, when the hash dictionary maps
x
to a list node
we must be able to decide quickly whether that node is inside the view. For array
lists this was easy: simply check whether the node’s index is between the endpoints
of the view, using integer comparisons. For linked lists, computing the index of
x
’s
node, or traversing the view to see whether
x
’s node falls within the view would be
slow and would completely defeat the purpose of the hash dictionary.
Our solution uses a list-ordering algorithm of Sleator and Dietz [29] in the ver-
sion described by Bender et al. [4].
The basic idea is simple. We give each node an integer tag and make sure the
tags are always in increasing order. First, whenever we insert a node in the list we
give it a tag that is between its neighbors, say the mean of the two. If there is not
enough room to make the tags distinct, we redistribute the tags of part of the list
to make room. The only problem is how to choose the amount of renumbering to
balance with the frequency of renumbering. The answer of Bender et al. [4] is the
following. When we run out of room we follow the list both ways comparing binary
prexes of tags, counting the segments of the list that have common prexes of
length
w
1
;
w
2
;:::;
w
b
where
w
is the word size (here 32). Let
k
be a parameter
tobe dened. For the least
b
where the segment is of size at most
k
b
,we redistribute
the tags in that segment uniformly. We need
n
k
w
to be sure such a
b
is found,
and
k
<
2
to be sure there are sizable gaps after tag redistribution, so we choose
k
=
w
p
n
<
2
.
The cost of this redistribution is
O
(
k
b
). Note that before this redistribution the
segment of common prex length
w
(
b
1
)had at least
k
b
1
nodes, and after re-
distribution it has
k
b
=
2
. Thus there must be at least
k
b
1
k
b
=
2
=
k
b
(
2
k
)=(
2k
)in-
sertions before we need to redistribute this segment again, and the amortized cost
of redistributions of tags at a given
b
is
O
(
k
=(
2
k
)) per insertion into the list. As
long as
n
is not close to
2
w
,this is
O
(
1
)per distinct value of
b
and hence the total
amortizedcost ofredistributions of tags will be
O
(
w
)per insertion into the list. Note,
however, that the typical case of always inserting at the end of the list seems to be
close to the worst-case scenario for maintaining the tags.
The tagging scheme used for hashed linked lists is a further renement of this
basic scheme. The reason is that although the basic scheme is simple and has low
overhead on those operations that do not cause tag redistributions, in the worst
case all tags must be redistributed and the complete list traversed, which is bad for
locality of memory references.
To get to
O
(
1
)amortizedcost per list update of tag maintenance we use instead a
two-level grouping scheme: Use the above basic scheme to maintain tags on groups
246 Implementation of tree-based collections
§13.10
of consecutive list nodes, and use a second tag inside each group. If the number
of groups are kept at
O
(
n
=
w
), say by making at least every other group be of size
W
(
w
), then the amortized cost of maintaining the top level tags will be
O
(
1
). It is
not hard to see that putting an extra
O
(
1
)charge on insertions will pay for splitting
and renumbering groups when we miss room in the low level tags; and an extra
charge on deletions will pay for joining groups when a group that gets below the
W
(
w
)threshold has a neighbor also below that threshold. In total we get an
O
(
1
)
amortized cost per list update of tag maintenance at the cost of a much more com-
plicated algorithm. Performance measurements indicated that this scheme never-
theless performs better at large list sizes, so this rened two-level grouping scheme
is the one used in the library.
Note that HashedLinkedList<T> is not a subclass of LinkedList<T>, as that
would require linked list nodes to carry elds used only in hashed linked list, in-
curring a considerable space overhead.
13.9 Implementation of list views
The implementation of views of array lists and of linked lists is described in sec-
tions 13.5 and 13.7 above. Here we describe how the
Offset
and
Count
properties of
aview are maintained when the underlying list is updated, possibly through one of
its views.
For this purpose, a proper list maintains a list of its views, in order of creation,
using weak references so as not to keep the views alive unnecessarily. Adding a
newly created view to this list, or removing the view when disposed, takes constant
time.
For ArrayList<T>, HashedArrayList<T> and LinkedList<T>, maintenance in
connection with an update is done by going through the list of all live views, and
determining from the each view’s
Offset
and
Count
whether it is affected by the up-
date, taking intoaccount alsowhether the update was made through theview itself;
see section 8.1.5. This is done after insertions and before removals.
For HashedLinkedList<T>, the
Offset
eld of a view is not necessarily known.
However, the tagging scheme described in section 13.8 can be used to determine
in constant time whether one node precedes another, and hence to determine for a
view whether it is affected by an update.
13.10 Implementation of tree-based collections
The tree-based collections TreeSet<T>, TreeBag<T> and TreeDictionary<K,V> are
implemented as red-black trees, following Tarjan [31]. The operations are done in
bottom-up style and there are no parent pointers in the tree nodes.
In contrast to tree-based collections from the standard libraries of C#, Java or
Smalltalk, ours have support for persistence, using techniques from Driscoll et al.
§13.10
Implementation of tree-based collections 247
[10]. Namely, the
Snapshot
method creates a read-only snapshot of a tree in con-
stant time, at the expense of making subsequent updates to the original tree some-
what slower.
Treesnapshots can beimplemented in at least twoways, namely using node copy
persistence or path copy persistence. To illustrate the difference, assume we have a
tree, make a (read-only) snapshot of it, and then insert a new node in the tree.
 With path copy persistence, all nodes on the path from the root to the inserted
node would be copied. Thus only completely unchanged subtrees are shared
between a snapshot and the updated tree. This scheme is simple and has the
advantage that each node can keep an accurate node count for the subtree
of which it is a root. The main drawback is the aggressive copying of nodes;
an update to the tree will on average allocate a number of new nodes that is
logarithmic in the collection size.
 With node copy persistence, each node can have up to two left children or up
to two right children: an old one (
oldref
,see below) belonging to a snapshot,
and a new one belonging to the updated tree. Each node is created with an
extra child reference, initially unused. At an insertion into the tree, one must
consider the nodes on thepath to the inserted node. Anodethat has an unused
childreference need not be copied; oneonly needs to copy anodeif it extrachild
reference is already in use. Thus a snapshot and the updated tree may share
anode even though its children have been updated. The main advantage of
this is efciency: the amortized number of new nodes created per update is
constant. The main disadvantages are that the scheme is more complicated,
and that one cannot easily maintain subtree node counts in a snapshot. For
that reason, snapshots do not support efcient item access by index, and the
type of a snapshot is ISorted<T> even though the original collection was an
IIndexedSorted<T>.
We chose node copy persistence for the C5 library after extensive performance stud-
ies [18]. Our implementation is based on ideas from Driscoll et al. [10]. Remember
that we implement partial persistence; snapshots are read-only historic documents,
not mutable clones.
To support persistence, a tree collection has the following additional elds:
bool isSnapShot
is false for a proper tree collection, true for snapshots.
int generation
is initially
0
,andis incrementedevery timeasnapshot is made
from the tree. For a snapshot, this always equals the tree’s
generation
at the
time the snapshot was made; a snapshot cannot be made from a snapshot.
SnapRef snapList
for a tree registers all the tree’s non-disposed snapshots,
using weak references. For a snapshort,
snapList
refers to thesnapshot’s entry
in the underlying tree’s
snapList
so the snapshot can be disposed in constant
time.
248 Implementation of tree-based collections
§13.10
int maxsnapid
is the maximal generation number of any non-disposed snap-
shot of this tree, or  
1
if there are no snapshots, so
snapList
is empty.
As in a standard red-black tree, a node has a color (red or black), an item, and
optional left and right child node references. To support persistence, each node has
the following additional elds:
int generation
,initialized from the tree’s
generation
number when the node
is created.
int lastgeneration
,initially  
1
,but updated to the current
maxsnapid
if the
node is snapshotted and subsequently updated. That is, this is the generation
of the most recent snapshot to which the node belongs.
Node oldref
,initially
null
,but non-
null
if the node has been snapshotted and
subsequently updated.
bool leftnode
indicates whether the
oldref
,if non-
null
,refers toan overwrit-
ten left node (true) or right node (false).
Asnapshot object is a shallow clone of a tree object (but not its nodes) having the
tree’s old generation number, and with
isSnapShot
set to true. If more than
2
31
snapshots are made from a tree, the 32 bit signed generation number may wrap
around, which will not be handled gracefully by the library.
We will now describe how the additional node elds are used for dening a spe-
cic generation snapshot, that is, howtoenumerate aspecic generation ofthetree.
Just after a node has been created, its generation number equals that of the tree,
and such a node will never be encountered during enumeration of an older snap-
shot. The item of a node encountered during enumeration of a snapshot will always
be valid, but thenode’s red-black color eld is not necessarily valid for the snapshot;
in fact, the color is only needed for updates, which do not happen for snapshots. If
anode with
generation
equal to
g
0
,and
lastgeneration
equal to
g
1
is encountered
when enumerating a younger snapshot of generation
g
2
>
g
1
,then both child refer-
ences in the node are valid. If thesnapshot being enumerated is older, so
g
0
g
2
g
1
,
then one of the child references in the node is not valid for that snapshot; instead
the valid child reference is in the
oldref
eld, and the
leftnode
eld tells which of
the child references is held in
oldref
.
Now we will explain how updates are affected by node copy persistence, assum-
ing that the reader is familiar with updates to non-persistent red-black trees. As-
sumewe are about toupdatea node that belongs toalivesnapshot, soits
generation
eld is less than or equal to the
maxsnapid
eld of the tree. If the update is a color
change, just do it. If the update is a change of the item, make a copy of the node,
update the item in the new node and update the reference in the parent node to
point to the new node; this node will have the generation number of the tree we
are updating. If the update is a change of a child reference and the
lastgeneration
eld of the node is still  
1
,we update
lastgeneration
to
maxsnapid
,set the
leftnode
eld to true if it is the left child we are updating, copy the old child reference to the
Documents you may be interested
Documents you may be interested