Files
dotnet-bot adf899c629 Adding System.Data..., System.ServiceModel..., and System.Web...
Adding reference source for
System.Data
System.Data.DataSetExtensions
System.Data.Entity
System.Data.Entity.Design
System.Data.Linq
System.Data.SqlXml
System.ServiceModel
System.ServiceModel.Activation
System.ServiceModel.Activities
System.ServiceModel.Channels
System.ServiceModel.Discovery
System.ServiceModel.Internals
System.ServiceModel.Routing
System.ServiceModel.WasHosting
System.ServiceModel.Web
System.Web
System.Web.ApplicationServices
System.Web.DynamicData
System.Web.Entity
System.Web.Entity.Design
System.Web.Extensions
System.Web.Mobile
System.Web.Routing
System.Web.Services
System.Xml
System.Xml.Linq
2016-05-03 00:07:37 +02:00

1186 lines
33 KiB
C#

//------------------------------------------------------------
// Copyright (c) Microsoft Corporation. All rights reserved.
//------------------------------------------------------------
namespace System.ServiceModel.Dispatcher
{
using System.Collections;
using System.Collections.Generic;
using System.Runtime;
// Based on the Paper: The IBS Tree: A Datastructure for finding all intervals that overlap a point.
// by Eric Hanson & Moez Chaabouni, Nov, 1994
internal enum IntervalOp : byte
{
LessThan,
LessThanEquals
}
internal class Interval
{
QueryBranch branch;
double lowerBound;
IntervalOp lowerOp;
double upperBound;
IntervalOp upperOp;
// Converts expressions of the form:
// x < 5 => -infinity <= x and x < 5
// x <= 5 => -infinity <= x and x <= 5
// x > 5 => 5 < x <= infinity
// x >= 5 => 5 <= x <= infinity
//
// The variable is always to the left
internal Interval(double literal, RelationOperator op)
{
this.lowerBound = double.MinValue;
this.upperBound = double.MaxValue;
this.lowerOp = IntervalOp.LessThanEquals;
this.upperOp = IntervalOp.LessThanEquals;
Fx.Assert(RelationOperator.Eq != op && RelationOperator.Ne != op, "");
switch (op)
{
case RelationOperator.Lt:
this.upperBound = literal;
this.upperOp = IntervalOp.LessThan;
break;
case RelationOperator.Le:
this.upperBound = literal;
break;
case RelationOperator.Gt:
this.lowerBound = literal;
this.lowerOp = IntervalOp.LessThan;
break;
case RelationOperator.Ge:
this.lowerBound = literal;
break;
}
}
#if NO
internal Interval(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
Fx.Assert(lowerBound <= upperBound, "");
this.lowerBound = lowerBound;
this.upperBound = upperBound;
if (this.lowerBound == this.upperBound)
{
this.lowerOp = IntervalOp.LessThanEquals;
this.upperOp = IntervalOp.LessThanEquals;
}
else
{
this.lowerOp = lowerOp;
this.upperOp = upperOp;
}
}
#endif
internal QueryBranch Branch
{
get
{
return this.branch;
}
set
{
this.branch = value;
}
}
internal double LowerBound
{
get
{
return this.lowerBound;
}
}
internal IntervalOp LowerOp
{
get
{
return this.lowerOp;
}
}
internal double UpperBound
{
get
{
return this.upperBound;
}
}
internal IntervalOp UpperOp
{
get
{
return this.upperOp;
}
}
#if NO
internal bool Equals(Interval interval)
{
Fx.Assert(null != interval, "");
return this.Equals(interval.lowerBound, interval.lowerOp, interval.upperBound, interval.upperOp);
}
#endif
internal bool Equals(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
return (this.lowerBound == lowerBound && this.lowerOp == lowerOp && this.upperBound == upperBound && this.upperOp == upperOp);
}
internal bool HasMatchingEndPoint(double endpoint)
{
return (this.lowerBound == endpoint || this.upperBound == endpoint);
}
}
/// <summary>
/// IntervalCollection
/// All Contains/Find operations are currently linear, since they are required only during
/// Inserts/Removes from the Interval Tree, which is not anticipated to be performance critical.
/// </summary>
internal class IntervalCollection : ArrayList
{
internal IntervalCollection()
: base(1)
{
}
internal bool HasIntervals
{
get
{
return (this.Count > 0);
}
}
internal new Interval this[int index]
{
get
{
return (Interval)base[index];
}
}
internal int Add(Interval interval)
{
Fx.Assert(null != interval, "");
this.Capacity = this.Count + 1;
return base.Add(interval);
}
internal int AddUnique(Interval interval)
{
Fx.Assert(null != interval, "");
int index = this.IndexOf(interval);
if (-1 == index)
{
return this.Add(interval);
}
return index;
}
internal IntervalCollection GetIntervalsWithEndPoint(double endPoint)
{
IntervalCollection matches = new IntervalCollection();
int count = this.Count;
for (int i = 0; i < count; ++i)
{
Interval interval = this[i];
if (interval.HasMatchingEndPoint(endPoint))
{
matches.Add(interval);
}
}
return matches;
}
internal int IndexOf(Interval interval)
{
Fx.Assert(null != interval, "");
return base.IndexOf(interval);
}
internal int IndexOf(double endPoint)
{
int count = this.Count;
for (int i = 0; i < count; ++i)
{
Interval interval = this[i];
if (interval.HasMatchingEndPoint(endPoint))
{
return i;
}
}
return -1;
}
internal int IndexOf(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
int count = this.Count;
for (int i = 0; i < count; ++i)
{
if (this[i].Equals(lowerBound, lowerOp, upperBound, upperOp))
{
return i;
}
}
return -1;
}
internal void Remove(Interval interval)
{
Fx.Assert(null != interval, "");
base.Remove(interval);
this.TrimToSize();
}
internal void Trim()
{
this.TrimToSize();
}
}
internal class IntervalBoundary
{
IntervalCollection eqSlot;
IntervalCollection gtSlot;
IntervalBoundary left;
IntervalCollection ltSlot;
IntervalBoundary parent;
IntervalBoundary right;
double val;
internal IntervalBoundary(double val, IntervalBoundary parent)
{
this.val = val;
this.parent = parent;
}
internal IntervalCollection EqSlot
{
get
{
return this.eqSlot;
}
}
internal IntervalCollection GtSlot
{
get
{
return this.gtSlot;
}
}
internal IntervalBoundary Left
{
get
{
return this.left;
}
set
{
this.left = value;
}
}
internal IntervalCollection LtSlot
{
get
{
return this.ltSlot;
}
}
internal IntervalBoundary Parent
{
get
{
return this.parent;
}
set
{
this.parent = value;
}
}
internal IntervalBoundary Right
{
get
{
return this.right;
}
set
{
this.right = value;
}
}
internal double Value
{
get
{
return this.val;
}
set
{
this.val = value;
}
}
internal void AddToEqSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.AddToSlot(ref this.eqSlot, interval);
}
internal void AddToGtSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.AddToSlot(ref this.gtSlot, interval);
}
internal void AddToLtSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.AddToSlot(ref this.ltSlot, interval);
}
void AddToSlot(ref IntervalCollection slot, Interval interval)
{
if (null == slot)
{
slot = new IntervalCollection();
}
slot.AddUnique(interval);
}
internal IntervalBoundary EnsureLeft(double val)
{
if (null == this.left)
{
this.left = new IntervalBoundary(val, this);
}
return this.left;
}
internal IntervalBoundary EnsureRight(double val)
{
if (null == this.right)
{
this.right = new IntervalBoundary(val, this);
}
return this.right;
}
#if NO
internal Interval GetInterval(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
Interval interval;
if (
null != (interval = this.GetIntervalFromSlot(this.eqSlot, lowerBound, lowerOp, upperBound, upperOp))
|| null != (interval = this.GetIntervalFromSlot(this.ltSlot, lowerBound, lowerOp, upperBound, upperOp))
|| null != (interval = this.GetIntervalFromSlot(this.gtSlot, lowerBound, lowerOp, upperBound, upperOp))
)
{
return interval;
}
return null;
}
internal Interval GetIntervalByData(object data)
{
Interval interval;
if (
null != (interval = this.GetIntervalFromSlot(this.eqSlot, data))
|| null != (interval = this.GetIntervalFromSlot(this.ltSlot, data))
|| null != (interval = this.GetIntervalFromSlot(this.gtSlot, data))
)
{
return interval;
}
return null;
}
Interval GetIntervalFromSlot(IntervalCollection slot, object data)
{
int index;
if (null != slot && -1 != (index = slot.IndexOf(data)))
{
return slot[index];
}
return null;
}
Interval GetIntervalFromSlot(IntervalCollection slot, double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
int index;
if (null != slot && -1 != (index = slot.IndexOf(lowerBound, lowerOp, upperBound, upperOp)))
{
return slot[index];
}
return null;
}
#endif
internal void RemoveFromEqSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.RemoveFromSlot(ref this.eqSlot, interval);
}
internal void RemoveFromGtSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.RemoveFromSlot(ref this.gtSlot, interval);
}
internal void RemoveFromLtSlot(Interval interval)
{
Fx.Assert(null != interval, "");
this.RemoveFromSlot(ref this.ltSlot, interval);
}
void RemoveFromSlot(ref IntervalCollection slot, Interval interval)
{
if (null != slot)
{
slot.Remove(interval);
if (!slot.HasIntervals)
{
slot = null;
}
}
}
internal void Trim()
{
if (this.eqSlot != null)
{
this.eqSlot.Trim();
}
if (this.gtSlot != null)
{
this.gtSlot.Trim();
}
if (this.ltSlot != null)
{
this.ltSlot.Trim();
}
if (this.left != null)
{
this.left.Trim();
}
if (this.right != null)
{
this.right.Trim();
}
}
}
internal struct IntervalTreeTraverser
{
IntervalBoundary currentNode;
IntervalBoundary nextNode;
IntervalCollection slot;
double val;
internal IntervalTreeTraverser(double val, IntervalBoundary root)
{
Fx.Assert(null != root, "");
this.currentNode = null;
this.slot = null;
this.nextNode = root;
this.val = val;
}
internal IntervalCollection Slot
{
get
{
return this.slot;
}
}
internal bool MoveNext()
{
while (null != this.nextNode)
{
this.currentNode = this.nextNode;
double currentVal = this.currentNode.Value;
if (val < currentVal)
{
this.slot = this.currentNode.LtSlot;
this.nextNode = this.currentNode.Left;
}
else if (val > currentVal)
{
this.slot = this.currentNode.GtSlot;
this.nextNode = this.currentNode.Right;
}
else
{
this.slot = this.currentNode.EqSlot;
this.nextNode = null;
}
if (null != this.slot)
{
return true;
}
}
return false;
}
}
internal class IntervalTree
{
IntervalCollection intervals;
IntervalBoundary root;
internal IntervalTree()
{
}
internal int Count
{
get
{
return (null != this.intervals) ? this.intervals.Count : 0;
}
}
internal IntervalCollection Intervals
{
get
{
if (null == this.intervals)
{
return new IntervalCollection();
}
return this.intervals;
}
}
#if NO
internal bool IsEmpty
{
get
{
return (this.root == null);
}
}
#endif
internal IntervalBoundary Root
{
get
{
return this.root;
}
}
internal void Add(Interval interval)
{
Fx.Assert(null != interval, "");
this.AddIntervalToTree(interval);
this.EnsureIntervals();
this.intervals.Add(interval);
}
void AddIntervalToTree(Interval interval)
{
this.EditLeft(interval, true);
this.EditRight(interval, true);
}
#if NO
internal bool Contains(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
if (null != this.intervals)
{
return (this.intervals.IndexOf(lowerBound, lowerOp, upperBound, upperOp) >= 0);
}
return false;
}
#endif
void EditLeft(Interval interval, bool add)
{
if (add)
{
this.EnsureRoot(interval.LowerBound);
}
IntervalBoundary root = this.root;
IntervalBoundary leftAncestor = null;
while (true)
{
double rootVal = root.Value;
if (rootVal < interval.LowerBound)
{
// root is outside the interval range because it is < the lower bound
root = add ? root.EnsureRight(interval.LowerBound) : root.Right;
continue;
}
// rootVal is >= to interval.lowerBound
//
// All values in thee subtree at 'root' are < leftAncestor.Value
// All values to the left of this node cannot be in the interval because they are < the interval's
// lower bound.
// Values to the right of this node lie in range (root.Value to leftAncestor.Value)
// Thus, the entire right subtree of root will be inside the range if the interval.upperBound
// is >= leftAncestor.Value
if (null != leftAncestor && leftAncestor.Value <= interval.UpperBound)
{
if (add)
{
root.AddToGtSlot(interval);
}
else
{
root.RemoveFromGtSlot(interval);
}
}
if (rootVal > interval.LowerBound)
{ // This node itself lies in the range if it is also < the upper bound
if (rootVal < interval.UpperBound)
{
if (add)
{
root.AddToEqSlot(interval);
}
else
{
root.RemoveFromEqSlot(interval);
}
}
leftAncestor = root;
root = add ? root.EnsureLeft(interval.LowerBound) : root.Left;
continue;
}
// lowerBound == rootVal. We're done.
if (IntervalOp.LessThanEquals == interval.LowerOp)
{
// If the range is inclusive of the lower bound (>=), then since this node == lowerBound,
// it must be in the range.
if (add)
{
root.AddToEqSlot(interval);
}
else
{
root.RemoveFromEqSlot(interval);
}
}
break;
}
}
void EditRight(Interval interval, bool add)
{
if (add)
{
this.EnsureRoot(interval.UpperBound);
}
IntervalBoundary root = this.root;
IntervalBoundary rightAncestor = null;
while (true)
{
double rootVal = root.Value;
if (rootVal > interval.UpperBound)
{
// root is outside the interval range because it is > the upper bound
root = add ? root.EnsureLeft(interval.UpperBound) : root.Left;
continue;
}
// rootVal is <= to interval.UpperBound
//
// All values in the subtree at 'root' are > leftAncestor.Value
// All values to the right of this node cannot be in the interval because they are > the interval's
// upper bound.
// Values to the left of this node lie in range (rightAncestor.Value to root.Value)
// Thus, the entire left subtree of root will be inside the range if the interval.lowerBound
// is <= rightAncestor.Value
if (null != rightAncestor && rightAncestor.Value >= interval.LowerBound)
{
if (add)
{
root.AddToLtSlot(interval);
}
else
{
root.RemoveFromLtSlot(interval);
}
}
if (rootVal < interval.UpperBound)
{
// This node itself lies in the range if it is also > the lower bound
if (rootVal > interval.LowerBound)
{
if (add)
{
root.AddToEqSlot(interval);
}
else
{
root.RemoveFromEqSlot(interval);
}
}
rightAncestor = root;
root = add ? root.EnsureRight(interval.UpperBound) : root.Right;
continue;
}
// upperBound == rootVal. We're done.
// If upperBound == lowerBound, we already inserted this when doing AddLeft
if (IntervalOp.LessThanEquals == interval.UpperOp)
{
// If the range is inclusive of the upper bound, then since this node == upperBound,
// it must be in the range.
if (add)
{
root.AddToEqSlot(interval);
}
else
{
root.RemoveFromEqSlot(interval);
}
}
break;
}
}
void EnsureIntervals()
{
if (null == this.intervals)
{
this.intervals = new IntervalCollection();
}
}
void EnsureRoot(double val)
{
if (null == this.root)
{
this.root = new IntervalBoundary(val, null);
}
}
internal IntervalBoundary FindBoundaryNode(double val)
{
return this.FindBoundaryNode(root, val);
}
internal IntervalBoundary FindBoundaryNode(IntervalBoundary root, double val)
{
IntervalBoundary boundary = null;
if (null != root)
{
if (root.Value == val)
{
boundary = root;
}
else
{
if (null == (boundary = this.FindBoundaryNode(root.Left, val)))
{
boundary = this.FindBoundaryNode(root.Right, val);
}
}
}
return boundary;
}
internal Interval FindInterval(Interval interval)
{
return this.FindInterval(interval.LowerBound, interval.LowerOp, interval.UpperBound, interval.UpperOp);
}
internal Interval FindInterval(double lowerBound, IntervalOp lowerOp, double upperBound, IntervalOp upperOp)
{
if (null != this.intervals)
{
int index;
if (-1 != (index = this.intervals.IndexOf(lowerBound, lowerOp, upperBound, upperOp)))
{
return this.intervals[index];
}
}
return null;
}
/// <summary>
/// An interval has been removed. Prune the tree appropriately
/// </summary>
/// <param name="intervalRemoved">interval that was removed</param>
void PruneTree(Interval intervalRemoved)
{
// Delete endpoints if no other intervals have them
int index;
if (-1 == (index = this.intervals.IndexOf(intervalRemoved.LowerBound)))
{
this.RemoveBoundary(this.FindBoundaryNode(intervalRemoved.LowerBound));
}
if (intervalRemoved.LowerBound != intervalRemoved.UpperBound && -1 == (index = this.intervals.IndexOf(intervalRemoved.UpperBound)))
{
this.RemoveBoundary(this.FindBoundaryNode(intervalRemoved.UpperBound));
}
}
internal void Remove(Interval interval)
{
Fx.Assert(null != interval, "");
Fx.Assert(null != this.intervals, "");
// First, delete all occurences of interval in the tree. Note: we do a reference equals
this.RemoveIntervalFromTree(interval);
// Remove interval from interval collection
this.intervals.Remove(interval);
// It may be possible to prune the tree.. this will do the necessary, if required
this.PruneTree(interval);
}
void RemoveBoundary(IntervalBoundary boundary)
{
IntervalCollection replacementIntervals = null;
int replacementCount = 0;
if (null != boundary.Left && null != boundary.Right)
{
// Neither left/right are null. Typical binary tree node removal - replace the removed node
// with the symmetric order predecessor
IntervalBoundary replacement = boundary.Left;
while (null != replacement.Right)
{
replacement = replacement.Right;
}
// Find all intervals with endpoint y in the tree
replacementIntervals = this.intervals.GetIntervalsWithEndPoint(replacement.Value);
// Remove the intervals from the tree
replacementCount = replacementIntervals.Count;
for (int i = 0; i < replacementCount; ++i)
{
this.RemoveIntervalFromTree(replacementIntervals[i]);
}
double val = boundary.Value;
boundary.Value = replacement.Value;
replacement.Value = val;
boundary = replacement;
}
if (null != boundary.Left)
{
this.Replace(boundary, boundary.Left);
}
else
{
this.Replace(boundary, boundary.Right);
}
// Discard the node
boundary.Parent = null;
boundary.Left = null;
boundary.Right = null;
// Reinstall Intervals
for (int i = 0; i < replacementCount; ++i)
{
this.AddIntervalToTree(replacementIntervals[i]);
}
}
void RemoveIntervalFromTree(Interval interval)
{
this.EditLeft(interval, false);
this.EditRight(interval, false);
}
void Replace(IntervalBoundary replace, IntervalBoundary with)
{
IntervalBoundary parent = replace.Parent;
if (null != parent)
{
if (replace == parent.Left)
{
parent.Left = with;
}
else if (replace == parent.Right)
{
parent.Right = with;
}
}
else
{
// Replacing root
this.root = with;
}
if (null != with)
{
with.Parent = parent;
}
}
internal void Trim()
{
this.intervals.Trim();
this.root.Trim();
}
}
internal class NumberRelationOpcode : LiteralRelationOpcode
{
double literal;
RelationOperator op;
internal NumberRelationOpcode(double literal, RelationOperator op)
: this(OpcodeID.NumberRelation, literal, op)
{
}
protected NumberRelationOpcode(OpcodeID id, double literal, RelationOperator op)
: base(id)
{
this.literal = literal;
this.op = op;
}
#if NO
internal override ValueDataType DataType
{
get
{
return ValueDataType.Double;
}
}
#endif
internal override object Literal
{
get
{
return this.literal;
}
}
#if NO
internal RelationOperator Op
{
get
{
return this.op;
}
}
#endif
internal override bool Equals(Opcode opcode)
{
if (base.Equals(opcode))
{
NumberRelationOpcode numOp = (NumberRelationOpcode)opcode;
return (numOp.op == this.op && numOp.literal == this.literal);
}
return false;
}
internal override Opcode Eval(ProcessingContext context)
{
Value[] values = context.Values;
StackFrame arg = context.TopArg;
for (int i = arg.basePtr; i <= arg.endPtr; ++i)
{
values[i].Update(context, values[i].CompareTo(this.literal, op));
}
return this.next;
}
internal Interval ToInterval()
{
return new Interval(this.literal, this.op);
}
}
internal class NumberIntervalOpcode : NumberRelationOpcode
{
Interval interval;
internal NumberIntervalOpcode(double literal, RelationOperator op)
: base(OpcodeID.NumberInterval, literal, op)
{
}
internal override object Literal
{
get
{
if (null == this.interval)
{
this.interval = this.ToInterval();
}
return this.interval;
}
}
internal override void Add(Opcode op)
{
NumberIntervalOpcode intervalOp = op as NumberIntervalOpcode;
if (null == intervalOp)
{
base.Add(op);
return;
}
Fx.Assert(null != this.prev, "");
NumberIntervalBranchOpcode branch = new NumberIntervalBranchOpcode();
this.prev.Replace(this, branch);
branch.Add(this);
branch.Add(intervalOp);
}
}
internal class IntervalBranchIndex : QueryBranchIndex
{
IntervalTree intervalTree;
internal IntervalBranchIndex()
{
this.intervalTree = new IntervalTree();
}
internal override int Count
{
get
{
return this.intervalTree.Count;
}
}
internal override QueryBranch this[object key]
{
get
{
Interval interval = this.intervalTree.FindInterval((Interval)key);
if (null != interval)
{
return interval.Branch;
}
return null;
}
set
{
Interval interval = (Interval)key;
interval.Branch = value;
this.intervalTree.Add(interval);
}
}
internal override void CollectXPathFilters(ICollection<MessageFilter> filters)
{
for (int i = 0; i < this.intervalTree.Intervals.Count; ++i)
{
this.intervalTree.Intervals[i].Branch.Branch.CollectXPathFilters(filters);
}
}
#if NO
internal override IEnumerator GetEnumerator()
{
return this.intervalTree.Intervals.GetEnumerator();
}
#endif
void Match(int valIndex, double point, QueryBranchResultSet results)
{
IntervalTreeTraverser traverser = new IntervalTreeTraverser(point, this.intervalTree.Root);
while (traverser.MoveNext())
{
IntervalCollection matches = traverser.Slot;
for (int i = 0, count = matches.Count; i < count; ++i)
{
QueryBranch branch = matches[i].Branch;
if (null != branch)
{
results.Add(branch, valIndex);
}
}
}
}
internal override void Match(int valIndex, ref Value val, QueryBranchResultSet results)
{
if (ValueDataType.Sequence == val.Type)
{
NodeSequence sequence = val.Sequence;
for (int i = 0; i < sequence.Count; ++i)
{
this.Match(valIndex, sequence.Items[i].NumberValue(), results);
}
}
else
{
this.Match(valIndex, val.ToDouble(), results);
}
}
internal override void Remove(object key)
{
this.intervalTree.Remove((Interval)key);
}
internal override void Trim()
{
this.intervalTree.Trim();
}
}
internal class NumberIntervalBranchOpcode : QueryConditionalBranchOpcode
{
internal NumberIntervalBranchOpcode()
: base(OpcodeID.NumberIntervalBranch, new IntervalBranchIndex())
{
}
internal override LiteralRelationOpcode ValidateOpcode(Opcode opcode)
{
NumberIntervalOpcode numOp = opcode as NumberIntervalOpcode;
if (null != numOp)
{
return numOp;
}
return null;
}
}
}