summaryrefslogtreecommitdiff
path: root/src/inc/rangetree.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/inc/rangetree.h')
-rw-r--r--src/inc/rangetree.h141
1 files changed, 141 insertions, 0 deletions
diff --git a/src/inc/rangetree.h b/src/inc/rangetree.h
new file mode 100644
index 0000000..7124d21
--- /dev/null
+++ b/src/inc/rangetree.h
@@ -0,0 +1,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_