1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
#ifndef _RANGETREE_
#define _RANGETREE_
#include "utilcode.h"
#include "memorypool.h"
//
// A RangeTree is a self-balancing binary tree of non-overlapping
// ranges [start-end), which provides log N operation time for
// lookup, insertion, and deletion of nodes.
//
// The tree is always balanced in the sense that the left and right
// sides of a node have the same amount of address space allocated to
// them - (for worst case data, the nodes of the tree might actually
// not be balanced).
//
// This address-space balancing means that if all the ranges cover a
// contiguous range of memory, and if lookup occur uniformly throughout
// the overall range covered, the tree provides optimal lookup
// structure.
//
// Another interesting property is that the same set of
// ranges always produces the same tree layout, regardless of
// the order the nodes are added in.
//
// Each node represents a range of the address space (in binary)
// from m0...0 to m1...1, where m is any number of 31 bits or
// less.
//
// Each node has 3 components:
// * a range
// * a 0-child,
// * a 1-child
//
// The range is the numeric range [start,end),
// represented by the node. A range is always assigned to the
// widest possible node (i.e. most bits in m) possible. Thus the
// bits of start and end share the same prefix string m, and
// differ in the next bit after m: the start bound will have a 0
// and the end bound will have a 1 in that position.
//
// Note that any other range which is represented by the same node
// must necessarily intersect the node. Thus, if no overlaps are
// possible, each node can only contain a single range. (To help
// see why this must be, it helps to realize that the node
// represents the transition from m01...1 to m10...0, which any
// range represented by this node must contain.)
//
// All range nodes represented by the form m0... are contained in
// the 0-child subtree, and all nodes represented by the form
// m1... are contained in the 1-child subtree. Either child can
// of course be null.
//
class RangeTree
{
public:
//
// Imbed the RangeTreeNode structure in your data structure
// in order to place it into a RangeTree.
//
struct Node
{
friend class RangeTree;
private:
// start & end (exclusive) of range
SIZE_T start;
SIZE_T end;
// mask of high-order bits which are the same in start & end
SIZE_T mask;
// We could steal a bit from mask or children[] for isIntermediate
BOOL isIntermediate;
#ifdef _DEBUG
// ordinal of when this node was created
DWORD ordinal;
#endif
Node *children[2];
void Init (SIZE_T rangeStart, SIZE_T rangeEnd
DEBUGARG(DWORD ord));
Node** Child(SIZE_T address)
{
LIMITED_METHOD_CONTRACT;
return &children[ ! ! (address & ((~mask>>1)+1))];
}
public:
BOOL IsIntermediate() { return isIntermediate; }
void IsIntermediate(BOOL value) { isIntermediate = value; }
SIZE_T GetStart() { return start; }
SIZE_T GetEnd() { return end; }
};
friend struct Node;
RangeTree();
Node *Lookup(SIZE_T address) const;
Node *LookupEndInclusive(SIZE_T nonStartingAddress);
BOOL Overlaps(SIZE_T start, SIZE_T end);
HRESULT AddNode(Node *addNode, SIZE_T start, SIZE_T end);
HRESULT RemoveNode(Node *removeNode);
void RemoveRange(SIZE_T start, SIZE_T end);
typedef void (*IterationCallback)(Node *next, void *context);
void Iterate(IterationCallback pCallback, void *context = NULL);
void IterateRange(SIZE_T start, SIZE_T end, IterationCallback pCallback, void *context = NULL);
private:
Node * m_root;
MemoryPool m_pool;
#ifdef _DEBUG
DWORD m_nodeCount;
#endif
Node *AddIntermediateNode(Node *node0, Node *node1);
Node *AllocateIntermediate();
void FreeIntermediate(Node *node);
void IterateNode(Node *node, IterationCallback pCallback, void *context);
void IterateRangeNode(Node *node, SIZE_T start, SIZE_T end, SIZE_T mask, IterationCallback pCallback, void *context);
BOOL OverlapsNode(Node *node, SIZE_T start, SIZE_T end, SIZE_T mask);
void RemoveRangeNode(Node **nodePtr, SIZE_T start, SIZE_T end, SIZE_T mask);
static SIZE_T GetRangeCommonMask(SIZE_T start, SIZE_T end);
};
#endif // _RANGETREE_
|
