Select.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Data / System / Data / Select.cs / 1305376 / Select.cs

                            //------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
// [....]
// [....] 
//----------------------------------------------------------------------------- 

namespace System.Data { 
    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data.Common; 
    using System.Diagnostics;
 
    internal sealed class Select { 
        private readonly DataTable table;
        private readonly int[] indexDesc; 
        private readonly IndexField[] IndexFields;
        private DataViewRowState recordStates;
        private DataExpression rowFilter;
        private ExpressionNode expression; 

        private Index index; 
 
        private int[] records;
        private int recordCount; 

        private ExpressionNode linearExpression;
        private bool candidatesForBinarySearch;
 
        private sealed class ColumnInfo {
            public bool       flag = false;               // Misc. Use 
            public bool       equalsOperator = false;     // True when the associated expr has = Operator defined 
            public BinaryNode expr = null;                // Binary Search capable expression associated
        } 
        ColumnInfo[] candidateColumns;
        int nCandidates;
        int matchedCandidates;
 
        public Select(DataTable table, string filterExpression, string sort, DataViewRowState recordStates) {
            this.table = table; 
            IndexFields = table.ParseSortString(sort); 
            this.indexDesc = ConvertIndexFieldtoIndexDesc(IndexFields);
            if (filterExpression != null && filterExpression.Length > 0) { 
                this.rowFilter = new DataExpression(this.table, filterExpression);
                this.expression = this.rowFilter.ExpressionNode;
            }
            this.recordStates = recordStates; 
        }
 
        private bool IsSupportedOperator(int op) { 
            return ((op >= Operators.EqualTo && op <= Operators.LessOrEqual) || op == Operators.Is || op == Operators.IsNot);
        } 

        // [....] : Gathers all linear expressions in to this.linearExpression and all binary expressions in to their respective candidate columns expressions
        private void AnalyzeExpression(BinaryNode expr) {
            if (this.linearExpression == this.expression) 
                return;
 
            if (expr.op == Operators.Or) { 
                this.linearExpression = this.expression;
                return; 
            }
            else
            if (expr.op == Operators.And) {
                bool isLeft=false, isRight=false; 
                if (expr.left is BinaryNode) {
                    AnalyzeExpression((BinaryNode)expr.left); 
                    if (this.linearExpression == this.expression) 
                        return;
                    isLeft = true; 
                }
                else {
                    UnaryNode unaryNode = expr.left as UnaryNode;
                    if (unaryNode != null) { 
                        while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) {
                            unaryNode = (UnaryNode)unaryNode.right; 
                        } 
                        if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
                            AnalyzeExpression((BinaryNode)(unaryNode.right)); 
                            if (this.linearExpression == this.expression) {
                                return;
                            }
                            isLeft = true; 
                        }
                    } 
                } 

                if (expr.right is BinaryNode) { 
                    AnalyzeExpression((BinaryNode)expr.right);
                    if (this.linearExpression == this.expression)
                        return;
                    isRight = true; 
                }
                else { 
                    UnaryNode unaryNode = expr.right as UnaryNode; 
                    if (unaryNode != null) {
                        while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) { 
                            unaryNode = (UnaryNode)unaryNode.right;
                        }
                        if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
                            AnalyzeExpression((BinaryNode)(unaryNode.right)); 
                            if (this.linearExpression == this.expression) {
                                return; 
                            } 
                            // SQLBU 497534: DataTable.Select() returns incorrect results with multiple statements depending '(' and ')'
                            // from copy paste error fixing SQLBU 342141 
                            isRight = true;
                        }
                    }
                } 

                if (isLeft && isRight) 
                    return; 

                ExpressionNode e = isLeft ? expr.right : expr.left; 
                this.linearExpression = (this.linearExpression == null ? e : new BinaryNode(table, Operators.And, e, this.linearExpression));
                return;
            }
            else 
            if (IsSupportedOperator(expr.op)) {
                if (expr.left is NameNode && expr.right is ConstNode) { 
                    ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal]; 
                    canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
                    if (expr.op == Operators.EqualTo) { 
                        canColumn.equalsOperator = true;
                    }
                    candidatesForBinarySearch = true;
                    return; 
                }
                else 
                if (expr.right is NameNode && expr.left is ConstNode) { 
                    ExpressionNode temp = expr.left;
                    expr.left = expr.right; 
                    expr.right = temp;
                    switch(expr.op) {
                        case Operators.GreaterThen:     expr.op = Operators.LessThen; break;
                        case Operators.LessThen:        expr.op = Operators.GreaterThen; break; 
                        case Operators.GreaterOrEqual:  expr.op = Operators.LessOrEqual; break;
                        case Operators.LessOrEqual:     expr.op = Operators.GreaterOrEqual; break; 
                        default : break; 
                    }
                    ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal]; 
                    canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
                    if (expr.op == Operators.EqualTo) {
                        canColumn.equalsOperator = true;
                    } 
                    candidatesForBinarySearch = true;
                    return; 
                } 
            }
 
            this.linearExpression = (this.linearExpression == null ? expr : new BinaryNode(table, Operators.And, expr, this.linearExpression));
            return;
        }
 
        private bool CompareSortIndexDesc(int[] id) {
            if (id.Length < indexDesc.Length) 
                return false; 
            int j=0;
            for (int i = 0; i < id.Length && j < indexDesc.Length; i++) { 
                if (id[i] == indexDesc[j]) {
                    j++;
                }
                else { 
                    ColumnInfo canColumn = candidateColumns[DataKey.ColumnOrder(id[i])];
                    if (!(canColumn != null && canColumn.equalsOperator)) 
                        return false; 
                }
            } 
            return j == indexDesc.Length;
        }

        internal static Int32[] ConvertIndexFieldtoIndexDesc(IndexField[] fields) { 
            Int32[] desc = new Int32[fields.Length];
            for(int i = 0; i < fields.Length; i++) { 
                desc[i] = fields[i].Column.Ordinal |(fields[i].IsDescending? DataKey.DESCENDING : 0); 
            }
            return desc; 
        }

        private bool FindSortIndex() {
            index = null; 
            this.table.indexesLock.AcquireReaderLock(-1);
             try{ 
                int count = this.table.indexes.Count; 
                int rowsCount = this.table.Rows.Count;
                for (int i = 0; i < count; i++) { 
                    Index ndx = (Index)table.indexes[i];
                    if (ndx.RecordStates != recordStates)
                        continue;
                    if(!ndx.IsSharable) { 
                        continue;
                    } 
                    if (CompareSortIndexDesc(ndx.IndexDesc)) { 
                        index = ndx;
                        return true; 
                    }
                }
             }
            finally { 
                this.table.indexesLock.ReleaseReaderLock();
            } 
            return false; 
        }
 
        // Returns no. of columns that are matched
        private int CompareClosestCandidateIndexDesc(int[] id) {
            int count = (id.Length < nCandidates ? id.Length : nCandidates);
            int i = 0; 
            for (; i < count; i++) {
                ColumnInfo canColumn = candidateColumns[DataKey.ColumnOrder(id[i])]; 
                if (canColumn == null || canColumn.expr == null) { 
                    break;
                } 
                else
                if (!canColumn.equalsOperator) {
                    return i+1;
                } 
            }
            return i; 
        } 

        // Returns whether the found index (if any) is a sort index as well 
        private bool FindClosestCandidateIndex() {
            index = null;
            matchedCandidates = 0;
            bool sortPriority = true; 
            this.table.indexesLock.AcquireReaderLock(-1);
            try { 
                int count = this.table.indexes.Count; 
                int rowsCount = this.table.Rows.Count;
                for (int i = 0; i < count; i++) { 
                    Index ndx = (Index)table.indexes[i];
                    if (ndx.RecordStates != recordStates)
                        continue;
                    if(!ndx.IsSharable) 
                        continue;
                    int match = CompareClosestCandidateIndexDesc(ndx.IndexDesc); 
                    if (match > matchedCandidates || (match == matchedCandidates && !sortPriority)) { 
                        matchedCandidates = match;
                        index = ndx; 
                        sortPriority = CompareSortIndexDesc(ndx.IndexDesc);
                        if (matchedCandidates == nCandidates && sortPriority) {
                            return true;
                        } 
                    }
                } 
            } 
            finally {
        this.table.indexesLock.ReleaseReaderLock(); 
        }

            return (index != null ? sortPriority : false);
        } 

        // Initialize candidate columns to new columnInfo and leave all non candidate columns to null 
        private void InitCandidateColumns() { 
            nCandidates = 0;
            candidateColumns = new ColumnInfo[this.table.Columns.Count]; 
            if (this.rowFilter == null)
                return;
            DataColumn[] depColumns = rowFilter.GetDependency();
            for (int i = 0; i < depColumns.Length; i++) { 
                if (depColumns[i].Table == this.table) {
                    candidateColumns[depColumns[i].Ordinal] = new ColumnInfo(); 
                    nCandidates++; 
                }
            } 
        }

        // Based on the required sorting and candidate columns settings, create a new index; Should be called only when there is no existing index to be reused
        private void CreateIndex() { 
            if (index == null) {
                if (nCandidates == 0) { 
                    index = new Index(table, IndexFields, recordStates, null); 
                    index.AddRef();
                } 
                else {
                    int i;
                    int lenCanColumns = candidateColumns.Length;
                    int lenIndexDesc = indexDesc.Length; 
                    bool equalsOperator = true;
                    for (i=0; i 0 && matchedCandidates <= lenId, "BuildLinearExpression : Invalid Index");
            for (i=0; i 0 || this.linearExpression == this.expression)) { 
                needSorting = !FindSortIndex();
            }

            if (index == null) { 
                CreateIndex();
                needSorting = false; 
            } 

            if (index.RecordCount == 0) 
                return table.NewRowArray(0);

            Range range;
            if (matchedCandidates == 0) { // [....] : Either dont have rowFilter or only linear search expression 
                range = new Range(0, index.RecordCount-1);
                Debug.Assert(!needSorting, "What are we doing here if no real reuse of this index ?"); 
                this.linearExpression = this.expression; 
                return GetLinearFilteredRows(range);
            } 
            else {
                range = GetBinaryFilteredRecords();
                if (range.Count == 0)
                    return table.NewRowArray(0); 
                if (matchedCandidates < nCandidates) {
                    BuildLinearExpression(); 
                } 
                if (!needSorting) {
                    return GetLinearFilteredRows(range); 
                }
                else {
                    this.records = GetLinearFilteredRecords(range);
                    this.recordCount = this.records.Length; 
                    if (this.recordCount == 0)
                        return table.NewRowArray(0); 
                    Sort(0, this.recordCount-1); 
                    return GetRows();
                } 
            }
        }

        public DataRow[] GetRows() { 
            DataRow[] newRows = table.NewRowArray(recordCount);
            for (int i = 0; i < newRows.Length; i++) { 
                newRows[i] = table.recordManager[records[i]]; 
            }
            return newRows; 
        }

        private bool AcceptRecord(int record) {
            DataRow row = table.recordManager[record]; 

            if (row == null) 
                return true; 

            // 

            DataRowVersion version = DataRowVersion.Default;
            if (row.oldRecord == record) {
                version = DataRowVersion.Original; 
            }
            else if (row.newRecord == record) { 
                version = DataRowVersion.Current; 
            }
            else if (row.tempRecord == record) { 
                version = DataRowVersion.Proposed;
            }

            object val = this.linearExpression.Eval(row, version); 
            bool result;
            try { 
                result = DataExpression.ToBoolean(val); 
            }
            catch (Exception e) { 
                //
                if (!ADP.IsCatchableExceptionType(e)) {
                    throw;
                } 
                throw ExprException.FilterConvertion(this.rowFilter.Expression);
            } 
            return result; 
        }
 
        private int Eval(BinaryNode expr, DataRow row, DataRowVersion version) {
            if (expr.op == Operators.And) {
                int lResult = Eval((BinaryNode)expr.left,row,version);
                if (lResult != 0) 
                    return lResult;
                int rResult = Eval((BinaryNode)expr.right,row,version); 
                if (rResult != 0) 
                    return rResult;
                return 0; 
            }

            long c = 0;
            object vLeft  = expr.left.Eval(row, version); 
            if (expr.op != Operators.Is && expr.op != Operators.IsNot) {
                object vRight = expr.right.Eval(row, version); 
                bool isLConst = (expr.left is ConstNode); 
                bool isRConst = (expr.right is ConstNode);
 
                if ((vLeft == DBNull.Value)||(expr.left.IsSqlColumn && DataStorage.IsObjectSqlNull(vLeft)))
                    return -1;
                if ((vRight == DBNull.Value)||(expr.right.IsSqlColumn && DataStorage.IsObjectSqlNull(vRight)))
                    return 1; 

                StorageType leftType = DataStorage.GetStorageType(vLeft.GetType()); 
                if (StorageType.Char == leftType) { 
                    if ((isRConst)||(!expr.right.IsSqlColumn))
                        vRight = Convert.ToChar(vRight, table.FormatProvider); 
                    else
                       vRight = SqlConvert.ChangeType2(vRight, StorageType.Char, typeof(char), table.FormatProvider);
                }
 
                StorageType rightType = DataStorage.GetStorageType(vRight.GetType());
                StorageType resultType; 
                if (expr.left.IsSqlColumn || expr.right.IsSqlColumn) { 
                    resultType = expr.ResultSqlType(leftType, rightType, isLConst, isRConst, expr.op);
                } 
                else {
                    resultType = expr.ResultType(leftType, rightType, isLConst, isRConst, expr.op);
                }
                if (StorageType.Empty == resultType) { 
                    expr.SetTypeMismatchError(expr.op, vLeft.GetType(), vRight.GetType());
                } 
 
                c = expr.BinaryCompare(vLeft, vRight, resultType, expr.op);
            } 
            switch(expr.op) {
                case Operators.EqualTo:         c = (c == 0 ? 0 : c < 0  ? -1 :  1); break;
                case Operators.GreaterThen:     c = (c > 0  ? 0 : -1); break;
                case Operators.LessThen:        c = (c < 0  ? 0 : 1); break; 
                case Operators.GreaterOrEqual:  c = (c >= 0 ? 0 : -1); break;
                case Operators.LessOrEqual:     c = (c <= 0 ? 0 : 1); break; 
                case Operators.Is:              c = (vLeft == DBNull.Value ? 0 : -1); break; 
                case Operators.IsNot:           c = (vLeft != DBNull.Value ? 0 : 1);  break;
                default:                        Debug.Assert(true, "Unsupported Binary Search Operator!"); break; 
            }
            return (int)c;
        }
 
        private int Evaluate(int record) {
            DataRow row = table.recordManager[record]; 
 
            if (row == null)
                return 0; 

            //

            DataRowVersion version = DataRowVersion.Default; 
            if (row.oldRecord == record) {
                version = DataRowVersion.Original; 
            } 
            else if (row.newRecord == record) {
                version = DataRowVersion.Current; 
            }
            else if (row.tempRecord == record) {
                version = DataRowVersion.Proposed;
            } 

            int[] id = index.IndexDesc; 
            for (int i=0; i < matchedCandidates; i++) { 
                Debug.Assert(candidateColumns[DataKey.ColumnOrder(id[i])] != null, "How come this is not a candidate column");
                Debug.Assert(candidateColumns[DataKey.ColumnOrder(id[i])].expr != null, "How come there is no associated expression"); 
                int c = Eval(candidateColumns[DataKey.ColumnOrder(id[i])].expr, row, version);
                if (c != 0)
                    return DataKey.SortDecending(id[i]) ? -c : c;
            } 
            return 0;
        } 
 
        private int FindFirstMatchingRecord() {
            int rec = -1; 
            int lo = 0;
            int hi = index.RecordCount - 1;
            while (lo <= hi) {
                int i = lo + hi >> 1; 
                int recNo = index.GetRecord(i);
                int c = Evaluate(recNo); 
                if (c == 0) { rec = i; } 
                if (c < 0) lo = i + 1;
                else hi = i - 1; 
            }
            return rec;
        }
 
        private int FindLastMatchingRecord(int lo) {
            int rec = -1; 
            int hi = index.RecordCount - 1; 
            while (lo <= hi) {
                int i = lo + hi >> 1; 
                int recNo = index.GetRecord(i);
                int c = Evaluate(recNo);
                if (c == 0) { rec = i; }
                if (c <= 0) lo = i + 1; 
                else hi = i - 1;
            } 
            return rec; 
        }
 
        private Range GetBinaryFilteredRecords() {
            if (matchedCandidates == 0) {
                return new Range(0, index.RecordCount-1);
            } 
            Debug.Assert(matchedCandidates <= index.IndexDesc.Length, "GetBinaryFilteredRecords : Invalid Index");
            int lo = FindFirstMatchingRecord(); 
            if (lo == -1) { 
                return new Range();
            } 
            int hi = FindLastMatchingRecord(lo);
            Debug.Assert (lo <= hi, "GetBinaryFilteredRecords : Invalid Search Results");
            return new Range(lo, hi);
        } 

        private int[] GetLinearFilteredRecords(Range range) { 
            if (this.linearExpression == null) { 
                int[] resultRecords = new int[range.Count];
                RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min); 
                for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
                    resultRecords[i] = iterator.Current;
                }
                return resultRecords; 
            }
            else { 
                List matchingRecords = new List(); 
                RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min);
                for (int i = 0; i < range.Count && iterator.MoveNext(); i++) { 
                    if (AcceptRecord(iterator.Current)) {
                        matchingRecords.Add(iterator.Current);
                    }
                } 
                return matchingRecords.ToArray();
            } 
        } 

        private DataRow[] GetLinearFilteredRows(Range range) { 
            DataRow[] resultRows;
            if (this.linearExpression == null) {
                return index.GetRows(range);
            } 

            List matchingRows = new List(); 
            RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min); 
            for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
                if (AcceptRecord(iterator.Current)) { 
                    matchingRows.Add(table.recordManager[iterator.Current]);
                }
            }
            resultRows = table.NewRowArray(matchingRows.Count); 
            matchingRows.CopyTo(resultRows);
            return resultRows; 
        } 

 
        private int CompareRecords(int record1, int record2) {
            int lenIndexDesc = indexDesc.Length;
            for (int i = 0; i < lenIndexDesc; i++) {
                Int32 d = indexDesc[i]; 
                int c = table.Columns[DataKey.ColumnOrder(d)].Compare(record1, record2);
                if (c != 0) { 
                    if (DataKey.SortDecending(d)) c = -c; 
                    return c;
                } 
            }

            long id1 = table.recordManager[record1] == null? 0: table.recordManager[record1].rowID;
            long id2 = table.recordManager[record2] == null ? 0 : table.recordManager[record2].rowID; 
            int diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
 
            // if they're two records in the same row, we need to be able to distinguish them. 
            if (diff == 0 && record1 != record2 &&
                table.recordManager[record1] != null && table.recordManager[record2] != null) { 
                id1 = (int)table.recordManager[record1].GetRecordState(record1);
                id2 = (int)table.recordManager[record2].GetRecordState(record2);
                diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
            } 

            return diff; 
        } 

        private void Sort(int left, int right) { 
            int i, j;
            int record;
            do {
                i = left; 
                j = right;
                record = records[i + j >> 1]; 
                do { 
                    while (CompareRecords(records[i], record) < 0) i++;
                    while (CompareRecords(records[j], record) > 0) j--; 
                    if (i <= j) {
                        int r = records[i];
                        records[i] = records[j];
                        records[j] = r; 
                        i++;
                        j--; 
                    } 
                } while (i <= j);
                if (left < j) Sort(left, j); 
                left = i;
            } while (i < right);
        }
    } 
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//------------------------------------------------------------------------------ 
// 
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// [....] 
// [....]
// [....] 
//----------------------------------------------------------------------------- 

namespace System.Data { 
    using System;
    using System.Collections.Generic;
    using System.ComponentModel;
    using System.Data.Common; 
    using System.Diagnostics;
 
    internal sealed class Select { 
        private readonly DataTable table;
        private readonly int[] indexDesc; 
        private readonly IndexField[] IndexFields;
        private DataViewRowState recordStates;
        private DataExpression rowFilter;
        private ExpressionNode expression; 

        private Index index; 
 
        private int[] records;
        private int recordCount; 

        private ExpressionNode linearExpression;
        private bool candidatesForBinarySearch;
 
        private sealed class ColumnInfo {
            public bool       flag = false;               // Misc. Use 
            public bool       equalsOperator = false;     // True when the associated expr has = Operator defined 
            public BinaryNode expr = null;                // Binary Search capable expression associated
        } 
        ColumnInfo[] candidateColumns;
        int nCandidates;
        int matchedCandidates;
 
        public Select(DataTable table, string filterExpression, string sort, DataViewRowState recordStates) {
            this.table = table; 
            IndexFields = table.ParseSortString(sort); 
            this.indexDesc = ConvertIndexFieldtoIndexDesc(IndexFields);
            if (filterExpression != null && filterExpression.Length > 0) { 
                this.rowFilter = new DataExpression(this.table, filterExpression);
                this.expression = this.rowFilter.ExpressionNode;
            }
            this.recordStates = recordStates; 
        }
 
        private bool IsSupportedOperator(int op) { 
            return ((op >= Operators.EqualTo && op <= Operators.LessOrEqual) || op == Operators.Is || op == Operators.IsNot);
        } 

        // [....] : Gathers all linear expressions in to this.linearExpression and all binary expressions in to their respective candidate columns expressions
        private void AnalyzeExpression(BinaryNode expr) {
            if (this.linearExpression == this.expression) 
                return;
 
            if (expr.op == Operators.Or) { 
                this.linearExpression = this.expression;
                return; 
            }
            else
            if (expr.op == Operators.And) {
                bool isLeft=false, isRight=false; 
                if (expr.left is BinaryNode) {
                    AnalyzeExpression((BinaryNode)expr.left); 
                    if (this.linearExpression == this.expression) 
                        return;
                    isLeft = true; 
                }
                else {
                    UnaryNode unaryNode = expr.left as UnaryNode;
                    if (unaryNode != null) { 
                        while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) {
                            unaryNode = (UnaryNode)unaryNode.right; 
                        } 
                        if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
                            AnalyzeExpression((BinaryNode)(unaryNode.right)); 
                            if (this.linearExpression == this.expression) {
                                return;
                            }
                            isLeft = true; 
                        }
                    } 
                } 

                if (expr.right is BinaryNode) { 
                    AnalyzeExpression((BinaryNode)expr.right);
                    if (this.linearExpression == this.expression)
                        return;
                    isRight = true; 
                }
                else { 
                    UnaryNode unaryNode = expr.right as UnaryNode; 
                    if (unaryNode != null) {
                        while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) { 
                            unaryNode = (UnaryNode)unaryNode.right;
                        }
                        if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
                            AnalyzeExpression((BinaryNode)(unaryNode.right)); 
                            if (this.linearExpression == this.expression) {
                                return; 
                            } 
                            // SQLBU 497534: DataTable.Select() returns incorrect results with multiple statements depending '(' and ')'
                            // from copy paste error fixing SQLBU 342141 
                            isRight = true;
                        }
                    }
                } 

                if (isLeft && isRight) 
                    return; 

                ExpressionNode e = isLeft ? expr.right : expr.left; 
                this.linearExpression = (this.linearExpression == null ? e : new BinaryNode(table, Operators.And, e, this.linearExpression));
                return;
            }
            else 
            if (IsSupportedOperator(expr.op)) {
                if (expr.left is NameNode && expr.right is ConstNode) { 
                    ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal]; 
                    canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
                    if (expr.op == Operators.EqualTo) { 
                        canColumn.equalsOperator = true;
                    }
                    candidatesForBinarySearch = true;
                    return; 
                }
                else 
                if (expr.right is NameNode && expr.left is ConstNode) { 
                    ExpressionNode temp = expr.left;
                    expr.left = expr.right; 
                    expr.right = temp;
                    switch(expr.op) {
                        case Operators.GreaterThen:     expr.op = Operators.LessThen; break;
                        case Operators.LessThen:        expr.op = Operators.GreaterThen; break; 
                        case Operators.GreaterOrEqual:  expr.op = Operators.LessOrEqual; break;
                        case Operators.LessOrEqual:     expr.op = Operators.GreaterOrEqual; break; 
                        default : break; 
                    }
                    ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal]; 
                    canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
                    if (expr.op == Operators.EqualTo) {
                        canColumn.equalsOperator = true;
                    } 
                    candidatesForBinarySearch = true;
                    return; 
                } 
            }
 
            this.linearExpression = (this.linearExpression == null ? expr : new BinaryNode(table, Operators.And, expr, this.linearExpression));
            return;
        }
 
        private bool CompareSortIndexDesc(int[] id) {
            if (id.Length < indexDesc.Length) 
                return false; 
            int j=0;
            for (int i = 0; i < id.Length && j < indexDesc.Length; i++) { 
                if (id[i] == indexDesc[j]) {
                    j++;
                }
                else { 
                    ColumnInfo canColumn = candidateColumns[DataKey.ColumnOrder(id[i])];
                    if (!(canColumn != null && canColumn.equalsOperator)) 
                        return false; 
                }
            } 
            return j == indexDesc.Length;
        }

        internal static Int32[] ConvertIndexFieldtoIndexDesc(IndexField[] fields) { 
            Int32[] desc = new Int32[fields.Length];
            for(int i = 0; i < fields.Length; i++) { 
                desc[i] = fields[i].Column.Ordinal |(fields[i].IsDescending? DataKey.DESCENDING : 0); 
            }
            return desc; 
        }

        private bool FindSortIndex() {
            index = null; 
            this.table.indexesLock.AcquireReaderLock(-1);
             try{ 
                int count = this.table.indexes.Count; 
                int rowsCount = this.table.Rows.Count;
                for (int i = 0; i < count; i++) { 
                    Index ndx = (Index)table.indexes[i];
                    if (ndx.RecordStates != recordStates)
                        continue;
                    if(!ndx.IsSharable) { 
                        continue;
                    } 
                    if (CompareSortIndexDesc(ndx.IndexDesc)) { 
                        index = ndx;
                        return true; 
                    }
                }
             }
            finally { 
                this.table.indexesLock.ReleaseReaderLock();
            } 
            return false; 
        }
 
        // Returns no. of columns that are matched
        private int CompareClosestCandidateIndexDesc(int[] id) {
            int count = (id.Length < nCandidates ? id.Length : nCandidates);
            int i = 0; 
            for (; i < count; i++) {
                ColumnInfo canColumn = candidateColumns[DataKey.ColumnOrder(id[i])]; 
                if (canColumn == null || canColumn.expr == null) { 
                    break;
                } 
                else
                if (!canColumn.equalsOperator) {
                    return i+1;
                } 
            }
            return i; 
        } 

        // Returns whether the found index (if any) is a sort index as well 
        private bool FindClosestCandidateIndex() {
            index = null;
            matchedCandidates = 0;
            bool sortPriority = true; 
            this.table.indexesLock.AcquireReaderLock(-1);
            try { 
                int count = this.table.indexes.Count; 
                int rowsCount = this.table.Rows.Count;
                for (int i = 0; i < count; i++) { 
                    Index ndx = (Index)table.indexes[i];
                    if (ndx.RecordStates != recordStates)
                        continue;
                    if(!ndx.IsSharable) 
                        continue;
                    int match = CompareClosestCandidateIndexDesc(ndx.IndexDesc); 
                    if (match > matchedCandidates || (match == matchedCandidates && !sortPriority)) { 
                        matchedCandidates = match;
                        index = ndx; 
                        sortPriority = CompareSortIndexDesc(ndx.IndexDesc);
                        if (matchedCandidates == nCandidates && sortPriority) {
                            return true;
                        } 
                    }
                } 
            } 
            finally {
        this.table.indexesLock.ReleaseReaderLock(); 
        }

            return (index != null ? sortPriority : false);
        } 

        // Initialize candidate columns to new columnInfo and leave all non candidate columns to null 
        private void InitCandidateColumns() { 
            nCandidates = 0;
            candidateColumns = new ColumnInfo[this.table.Columns.Count]; 
            if (this.rowFilter == null)
                return;
            DataColumn[] depColumns = rowFilter.GetDependency();
            for (int i = 0; i < depColumns.Length; i++) { 
                if (depColumns[i].Table == this.table) {
                    candidateColumns[depColumns[i].Ordinal] = new ColumnInfo(); 
                    nCandidates++; 
                }
            } 
        }

        // Based on the required sorting and candidate columns settings, create a new index; Should be called only when there is no existing index to be reused
        private void CreateIndex() { 
            if (index == null) {
                if (nCandidates == 0) { 
                    index = new Index(table, IndexFields, recordStates, null); 
                    index.AddRef();
                } 
                else {
                    int i;
                    int lenCanColumns = candidateColumns.Length;
                    int lenIndexDesc = indexDesc.Length; 
                    bool equalsOperator = true;
                    for (i=0; i 0 && matchedCandidates <= lenId, "BuildLinearExpression : Invalid Index");
            for (i=0; i 0 || this.linearExpression == this.expression)) { 
                needSorting = !FindSortIndex();
            }

            if (index == null) { 
                CreateIndex();
                needSorting = false; 
            } 

            if (index.RecordCount == 0) 
                return table.NewRowArray(0);

            Range range;
            if (matchedCandidates == 0) { // [....] : Either dont have rowFilter or only linear search expression 
                range = new Range(0, index.RecordCount-1);
                Debug.Assert(!needSorting, "What are we doing here if no real reuse of this index ?"); 
                this.linearExpression = this.expression; 
                return GetLinearFilteredRows(range);
            } 
            else {
                range = GetBinaryFilteredRecords();
                if (range.Count == 0)
                    return table.NewRowArray(0); 
                if (matchedCandidates < nCandidates) {
                    BuildLinearExpression(); 
                } 
                if (!needSorting) {
                    return GetLinearFilteredRows(range); 
                }
                else {
                    this.records = GetLinearFilteredRecords(range);
                    this.recordCount = this.records.Length; 
                    if (this.recordCount == 0)
                        return table.NewRowArray(0); 
                    Sort(0, this.recordCount-1); 
                    return GetRows();
                } 
            }
        }

        public DataRow[] GetRows() { 
            DataRow[] newRows = table.NewRowArray(recordCount);
            for (int i = 0; i < newRows.Length; i++) { 
                newRows[i] = table.recordManager[records[i]]; 
            }
            return newRows; 
        }

        private bool AcceptRecord(int record) {
            DataRow row = table.recordManager[record]; 

            if (row == null) 
                return true; 

            // 

            DataRowVersion version = DataRowVersion.Default;
            if (row.oldRecord == record) {
                version = DataRowVersion.Original; 
            }
            else if (row.newRecord == record) { 
                version = DataRowVersion.Current; 
            }
            else if (row.tempRecord == record) { 
                version = DataRowVersion.Proposed;
            }

            object val = this.linearExpression.Eval(row, version); 
            bool result;
            try { 
                result = DataExpression.ToBoolean(val); 
            }
            catch (Exception e) { 
                //
                if (!ADP.IsCatchableExceptionType(e)) {
                    throw;
                } 
                throw ExprException.FilterConvertion(this.rowFilter.Expression);
            } 
            return result; 
        }
 
        private int Eval(BinaryNode expr, DataRow row, DataRowVersion version) {
            if (expr.op == Operators.And) {
                int lResult = Eval((BinaryNode)expr.left,row,version);
                if (lResult != 0) 
                    return lResult;
                int rResult = Eval((BinaryNode)expr.right,row,version); 
                if (rResult != 0) 
                    return rResult;
                return 0; 
            }

            long c = 0;
            object vLeft  = expr.left.Eval(row, version); 
            if (expr.op != Operators.Is && expr.op != Operators.IsNot) {
                object vRight = expr.right.Eval(row, version); 
                bool isLConst = (expr.left is ConstNode); 
                bool isRConst = (expr.right is ConstNode);
 
                if ((vLeft == DBNull.Value)||(expr.left.IsSqlColumn && DataStorage.IsObjectSqlNull(vLeft)))
                    return -1;
                if ((vRight == DBNull.Value)||(expr.right.IsSqlColumn && DataStorage.IsObjectSqlNull(vRight)))
                    return 1; 

                StorageType leftType = DataStorage.GetStorageType(vLeft.GetType()); 
                if (StorageType.Char == leftType) { 
                    if ((isRConst)||(!expr.right.IsSqlColumn))
                        vRight = Convert.ToChar(vRight, table.FormatProvider); 
                    else
                       vRight = SqlConvert.ChangeType2(vRight, StorageType.Char, typeof(char), table.FormatProvider);
                }
 
                StorageType rightType = DataStorage.GetStorageType(vRight.GetType());
                StorageType resultType; 
                if (expr.left.IsSqlColumn || expr.right.IsSqlColumn) { 
                    resultType = expr.ResultSqlType(leftType, rightType, isLConst, isRConst, expr.op);
                } 
                else {
                    resultType = expr.ResultType(leftType, rightType, isLConst, isRConst, expr.op);
                }
                if (StorageType.Empty == resultType) { 
                    expr.SetTypeMismatchError(expr.op, vLeft.GetType(), vRight.GetType());
                } 
 
                c = expr.BinaryCompare(vLeft, vRight, resultType, expr.op);
            } 
            switch(expr.op) {
                case Operators.EqualTo:         c = (c == 0 ? 0 : c < 0  ? -1 :  1); break;
                case Operators.GreaterThen:     c = (c > 0  ? 0 : -1); break;
                case Operators.LessThen:        c = (c < 0  ? 0 : 1); break; 
                case Operators.GreaterOrEqual:  c = (c >= 0 ? 0 : -1); break;
                case Operators.LessOrEqual:     c = (c <= 0 ? 0 : 1); break; 
                case Operators.Is:              c = (vLeft == DBNull.Value ? 0 : -1); break; 
                case Operators.IsNot:           c = (vLeft != DBNull.Value ? 0 : 1);  break;
                default:                        Debug.Assert(true, "Unsupported Binary Search Operator!"); break; 
            }
            return (int)c;
        }
 
        private int Evaluate(int record) {
            DataRow row = table.recordManager[record]; 
 
            if (row == null)
                return 0; 

            //

            DataRowVersion version = DataRowVersion.Default; 
            if (row.oldRecord == record) {
                version = DataRowVersion.Original; 
            } 
            else if (row.newRecord == record) {
                version = DataRowVersion.Current; 
            }
            else if (row.tempRecord == record) {
                version = DataRowVersion.Proposed;
            } 

            int[] id = index.IndexDesc; 
            for (int i=0; i < matchedCandidates; i++) { 
                Debug.Assert(candidateColumns[DataKey.ColumnOrder(id[i])] != null, "How come this is not a candidate column");
                Debug.Assert(candidateColumns[DataKey.ColumnOrder(id[i])].expr != null, "How come there is no associated expression"); 
                int c = Eval(candidateColumns[DataKey.ColumnOrder(id[i])].expr, row, version);
                if (c != 0)
                    return DataKey.SortDecending(id[i]) ? -c : c;
            } 
            return 0;
        } 
 
        private int FindFirstMatchingRecord() {
            int rec = -1; 
            int lo = 0;
            int hi = index.RecordCount - 1;
            while (lo <= hi) {
                int i = lo + hi >> 1; 
                int recNo = index.GetRecord(i);
                int c = Evaluate(recNo); 
                if (c == 0) { rec = i; } 
                if (c < 0) lo = i + 1;
                else hi = i - 1; 
            }
            return rec;
        }
 
        private int FindLastMatchingRecord(int lo) {
            int rec = -1; 
            int hi = index.RecordCount - 1; 
            while (lo <= hi) {
                int i = lo + hi >> 1; 
                int recNo = index.GetRecord(i);
                int c = Evaluate(recNo);
                if (c == 0) { rec = i; }
                if (c <= 0) lo = i + 1; 
                else hi = i - 1;
            } 
            return rec; 
        }
 
        private Range GetBinaryFilteredRecords() {
            if (matchedCandidates == 0) {
                return new Range(0, index.RecordCount-1);
            } 
            Debug.Assert(matchedCandidates <= index.IndexDesc.Length, "GetBinaryFilteredRecords : Invalid Index");
            int lo = FindFirstMatchingRecord(); 
            if (lo == -1) { 
                return new Range();
            } 
            int hi = FindLastMatchingRecord(lo);
            Debug.Assert (lo <= hi, "GetBinaryFilteredRecords : Invalid Search Results");
            return new Range(lo, hi);
        } 

        private int[] GetLinearFilteredRecords(Range range) { 
            if (this.linearExpression == null) { 
                int[] resultRecords = new int[range.Count];
                RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min); 
                for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
                    resultRecords[i] = iterator.Current;
                }
                return resultRecords; 
            }
            else { 
                List matchingRecords = new List(); 
                RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min);
                for (int i = 0; i < range.Count && iterator.MoveNext(); i++) { 
                    if (AcceptRecord(iterator.Current)) {
                        matchingRecords.Add(iterator.Current);
                    }
                } 
                return matchingRecords.ToArray();
            } 
        } 

        private DataRow[] GetLinearFilteredRows(Range range) { 
            DataRow[] resultRows;
            if (this.linearExpression == null) {
                return index.GetRows(range);
            } 

            List matchingRows = new List(); 
            RBTree.RBTreeEnumerator iterator = index.GetEnumerator(range.Min); 
            for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
                if (AcceptRecord(iterator.Current)) { 
                    matchingRows.Add(table.recordManager[iterator.Current]);
                }
            }
            resultRows = table.NewRowArray(matchingRows.Count); 
            matchingRows.CopyTo(resultRows);
            return resultRows; 
        } 

 
        private int CompareRecords(int record1, int record2) {
            int lenIndexDesc = indexDesc.Length;
            for (int i = 0; i < lenIndexDesc; i++) {
                Int32 d = indexDesc[i]; 
                int c = table.Columns[DataKey.ColumnOrder(d)].Compare(record1, record2);
                if (c != 0) { 
                    if (DataKey.SortDecending(d)) c = -c; 
                    return c;
                } 
            }

            long id1 = table.recordManager[record1] == null? 0: table.recordManager[record1].rowID;
            long id2 = table.recordManager[record2] == null ? 0 : table.recordManager[record2].rowID; 
            int diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
 
            // if they're two records in the same row, we need to be able to distinguish them. 
            if (diff == 0 && record1 != record2 &&
                table.recordManager[record1] != null && table.recordManager[record2] != null) { 
                id1 = (int)table.recordManager[record1].GetRecordState(record1);
                id2 = (int)table.recordManager[record2].GetRecordState(record2);
                diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
            } 

            return diff; 
        } 

        private void Sort(int left, int right) { 
            int i, j;
            int record;
            do {
                i = left; 
                j = right;
                record = records[i + j >> 1]; 
                do { 
                    while (CompareRecords(records[i], record) < 0) i++;
                    while (CompareRecords(records[j], record) > 0) j--; 
                    if (i <= j) {
                        int r = records[i];
                        records[i] = records[j];
                        records[j] = r; 
                        i++;
                        j--; 
                    } 
                } while (i <= j);
                if (left < j) Sort(left, j); 
                left = i;
            } while (i < right);
        }
    } 
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK