mcs/class/referencesource/System.Data/System/Data/Select.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="Select.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 // <owner current="true" primary="false">Microsoft</owner>
   7 // <owner current="false" primary="false">Microsoft</owner>
   8 //------------------------------------------------------------------------------
   9
  10 namespace System.Data {
  11     using System;
  12     using System.Collections.Generic;
  13     using System.ComponentModel;
  14     using System.Data.Common;
  15     using System.Diagnostics;
  16
  17     internal sealed class Select {
  18         private readonly DataTable table;
  19         private readonly IndexField[] IndexFields;
  20         private DataViewRowState recordStates;
  21         private DataExpression rowFilter;
  22         private ExpressionNode expression;
  23
  24         private Index index;
  25
  26         private int[] records;
  27         private int recordCount;
  28
  29         private ExpressionNode linearExpression;
  30         private bool candidatesForBinarySearch;
  31
  32         private sealed class ColumnInfo {
  33             public bool       flag = false;               // Misc. Use
  34             public bool       equalsOperator = false;     // True when the associated expr has = Operator defined
  35             public BinaryNode expr = null;                // Binary Search capable expression associated
  36         }
  37         ColumnInfo[] candidateColumns;
  38         int nCandidates;
  39         int matchedCandidates;
  40
  41         public Select(DataTable table, string filterExpression, string sort, DataViewRowState recordStates) {
  42             this.table = table;
  43             IndexFields = table.ParseSortString(sort);
  44             if (filterExpression != null && filterExpression.Length > 0) {
  45                 this.rowFilter = new DataExpression(this.table, filterExpression);
  46                 this.expression = this.rowFilter.ExpressionNode;
  47             }
  48             this.recordStates = recordStates;
  49         }
  50
  51         private bool IsSupportedOperator(int op) {
  52             return ((op >= Operators.EqualTo && op <= Operators.LessOrEqual) || op == Operators.Is || op == Operators.IsNot);
  53         }
  54
  55         // Microsoft : Gathers all linear expressions in to this.linearExpression and all binary expressions in to their respective candidate columns expressions
  56         private void AnalyzeExpression(BinaryNode expr) {
  57             if (this.linearExpression == this.expression)
  58                 return;
  59
  60             if (expr.op == Operators.Or) {
  61                 this.linearExpression = this.expression;
  62                 return;
  63             }
  64             else
  65             if (expr.op == Operators.And) {
  66                 bool isLeft=false, isRight=false;
  67                 if (expr.left is BinaryNode) {
  68                     AnalyzeExpression((BinaryNode)expr.left);
  69                     if (this.linearExpression == this.expression)
  70                         return;
  71                     isLeft = true;
  72                 }
  73                 else {
  74                     UnaryNode unaryNode = expr.left as UnaryNode;
  75                     if (unaryNode != null) {
  76                         while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) {
  77                             unaryNode = (UnaryNode)unaryNode.right;
  78                         }
  79                         if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
  80                             AnalyzeExpression((BinaryNode)(unaryNode.right));
  81                             if (this.linearExpression == this.expression) {
  82                                 return;
  83                             }
  84                             isLeft = true;
  85                         }
  86                     }
  87                 }
  88
  89                 if (expr.right is BinaryNode) {
  90                     AnalyzeExpression((BinaryNode)expr.right);
  91                     if (this.linearExpression == this.expression)
  92                         return;
  93                     isRight = true;
  94                 }
  95                 else {
  96                     UnaryNode unaryNode = expr.right as UnaryNode;
  97                     if (unaryNode != null) {
  98                         while (unaryNode.op == Operators.Noop && unaryNode.right is UnaryNode && ((UnaryNode)unaryNode.right).op == Operators.Noop) {
  99                             unaryNode = (UnaryNode)unaryNode.right;
 100                         }
 101                         if (unaryNode.op == Operators.Noop && unaryNode.right is BinaryNode) {
 102                             AnalyzeExpression((BinaryNode)(unaryNode.right));
 103                             if (this.linearExpression == this.expression) {
 104                                 return;
 105                             }
 106                             // SQLBU 497534: DataTable.Select() returns incorrect results with multiple statements depending '(' and ')'
 107                             // from copy paste error fixing SQLBU 342141
 108                             isRight = true;
 109                         }
 110                     }
 111                 }
 112
 113                 if (isLeft && isRight)
 114                     return;
 115
 116                 ExpressionNode e = isLeft ? expr.right : expr.left;
 117                 this.linearExpression = (this.linearExpression == null ? e : new BinaryNode(table, Operators.And, e, this.linearExpression));
 118                 return;
 119             }
 120             else
 121             if (IsSupportedOperator(expr.op)) {
 122                 if (expr.left is NameNode && expr.right is ConstNode) {
 123                     ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal];
 124                     canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
 125                     if (expr.op == Operators.EqualTo) {
 126                         canColumn.equalsOperator = true;
 127                     }
 128                     candidatesForBinarySearch = true;
 129                     return;
 130                 }
 131                 else
 132                 if (expr.right is NameNode && expr.left is ConstNode) {
 133                     ExpressionNode temp = expr.left;
 134                     expr.left = expr.right;
 135                     expr.right = temp;
 136                     switch(expr.op) {
 137                         case Operators.GreaterThen:     expr.op = Operators.LessThen; break;
 138                         case Operators.LessThen:        expr.op = Operators.GreaterThen; break;
 139                         case Operators.GreaterOrEqual:  expr.op = Operators.LessOrEqual; break;
 140                         case Operators.LessOrEqual:     expr.op = Operators.GreaterOrEqual; break;
 141                         default : break;
 142                     }
 143                     ColumnInfo canColumn = (ColumnInfo)candidateColumns[((NameNode)(expr.left)).column.Ordinal];
 144                     canColumn.expr = (canColumn.expr == null ? expr : new BinaryNode(table, Operators.And, expr, canColumn.expr));
 145                     if (expr.op == Operators.EqualTo) {
 146                         canColumn.equalsOperator = true;
 147                     }
 148                     candidatesForBinarySearch = true;
 149                     return;
 150                 }
 151             }
 152
 153             this.linearExpression = (this.linearExpression == null ? expr : new BinaryNode(table, Operators.And, expr, this.linearExpression));
 154             return;
 155         }
 156
 157         private bool CompareSortIndexDesc(IndexField[] fields) {
 158             if (fields.Length < IndexFields.Length)
 159                 return false;
 160             int j=0;
 161             for (int i = 0; i < fields.Length && j < IndexFields.Length; i++) {
 162                 if (fields[i] == IndexFields[j]) {
 163                     j++;
 164                 }
 165                 else {
 166                     ColumnInfo canColumn = candidateColumns[fields[i].Column.Ordinal];
 167                     if (!(canColumn != null && canColumn.equalsOperator))
 168                         return false;
 169                 }
 170             }
 171             return j == IndexFields.Length;
 172         }
 173
 174         private bool FindSortIndex() {
 175             index = null;
 176             this.table.indexesLock.AcquireReaderLock(-1);
 177              try{
 178                 int count = this.table.indexes.Count;
 179                 int rowsCount = this.table.Rows.Count;
 180                 for (int i = 0; i < count; i++) {
 181                     Index ndx = (Index)table.indexes[i];
 182                     if (ndx.RecordStates != recordStates)
 183                         continue;
 184                     if(!ndx.IsSharable) {
 185                         continue;
 186                     }
 187                     if (CompareSortIndexDesc(ndx.IndexFields)) {
 188                         index = ndx;
 189                         return true;
 190                     }
 191                 }
 192              }
 193             finally {
 194                 this.table.indexesLock.ReleaseReaderLock();
 195             }
 196             return false;
 197         }
 198
 199         // Returns no. of columns that are matched
 200         private int CompareClosestCandidateIndexDesc(IndexField[] fields) {
 201             int count = (fields.Length < nCandidates ? fields.Length : nCandidates);
 202             int i = 0;
 203             for (; i < count; i++) {
 204                 ColumnInfo canColumn = candidateColumns[fields[i].Column.Ordinal];
 205                 if (canColumn == null || canColumn.expr == null) {
 206                     break;
 207                 }
 208                 else
 209                 if (!canColumn.equalsOperator) {
 210                     return i+1;
 211                 }
 212             }
 213             return i;
 214         }
 215
 216         // Returns whether the found index (if any) is a sort index as well
 217         private bool FindClosestCandidateIndex() {
 218             index = null;
 219             matchedCandidates = 0;
 220             bool sortPriority = true;
 221             this.table.indexesLock.AcquireReaderLock(-1);
 222             try {
 223                 int count = this.table.indexes.Count;
 224                 int rowsCount = this.table.Rows.Count;
 225                 for (int i = 0; i < count; i++) {
 226                     Index ndx = (Index)table.indexes[i];
 227                     if (ndx.RecordStates != recordStates)
 228                         continue;
 229                     if(!ndx.IsSharable)
 230                         continue;
 231                     int match = CompareClosestCandidateIndexDesc(ndx.IndexFields);
 232                     if (match > matchedCandidates || (match == matchedCandidates && !sortPriority)) {
 233                         matchedCandidates = match;
 234                         index = ndx;
 235                         sortPriority = CompareSortIndexDesc(ndx.IndexFields);
 236                         if (matchedCandidates == nCandidates && sortPriority) {
 237                             return true;
 238                         }
 239                     }
 240                 }
 241             }
 242             finally {
 243         this.table.indexesLock.ReleaseReaderLock();
 244         }
 245
 246             return (index != null ? sortPriority : false);
 247         }
 248
 249         // Initialize candidate columns to new columnInfo and leave all non candidate columns to null
 250         private void InitCandidateColumns() {
 251             nCandidates = 0;
 252             candidateColumns = new ColumnInfo[this.table.Columns.Count];
 253             if (this.rowFilter == null)
 254                 return;
 255             DataColumn[] depColumns = rowFilter.GetDependency();
 256             for (int i = 0; i < depColumns.Length; i++) {
 257                 if (depColumns[i].Table == this.table) {
 258                     candidateColumns[depColumns[i].Ordinal] = new ColumnInfo();
 259                     nCandidates++;
 260                 }
 261             }
 262         }
 263
 264         // 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
 265         private void CreateIndex() {
 266             if (index == null) {
 267                 if (nCandidates == 0) {
 268                     index = new Index(table, IndexFields, recordStates, null);
 269                     index.AddRef();
 270                 }
 271                 else {
 272                     int i;
 273                     int lenCanColumns = candidateColumns.Length;
 274                     int lenIndexDesc = IndexFields.Length;
 275                     bool equalsOperator = true;
 276                     for (i=0; i<lenCanColumns; i++) {
 277                         if (candidateColumns[i] != null) {
 278                             if (!candidateColumns[i].equalsOperator) {
 279                                 equalsOperator = false;
 280                                 break;
 281                             }
 282                         }
 283                     }
 284
 285                     int j=0;
 286                     for (i=0; i < lenIndexDesc; i++) {
 287                         ColumnInfo candidateColumn = candidateColumns[IndexFields[i].Column.Ordinal];
 288                         if (candidateColumn != null) {
 289                             candidateColumn.flag = true;
 290                             j++;
 291                         }
 292                     }
 293                     int indexNotInCandidates = lenIndexDesc - j;
 294                     int candidatesNotInIndex = nCandidates - j;
 295                     IndexField[] ndxFields = new IndexField[nCandidates + indexNotInCandidates];
 296
 297                     if (equalsOperator) {
 298                         j=0;
 299                         for (i=0; i<lenCanColumns; i++) {
 300                             if (candidateColumns[i] != null) {
 301                                 ndxFields[j++] = new IndexField(this.table.Columns[i], isDescending: false);
 302                                 candidateColumns[i].flag = false;// this means it is processed
 303                             }
 304                         }
 305                         for (i=0; i<lenIndexDesc; i++) {
 306                             ColumnInfo canColumn = candidateColumns[IndexFields[i].Column.Ordinal];
 307                             if (canColumn == null || canColumn.flag) { // if sort column is not a filter col , or not processed
 308                                 ndxFields[j++] = IndexFields[i];
 309                                 if (canColumn != null) {
 310                                     canColumn.flag = false;
 311                                 }
 312                             }
 313                         }
 314
 315                         for(i = 0; i < candidateColumns.Length; i++) {
 316                             if (candidateColumns[i] != null) {
 317                                 candidateColumns[i].flag = false;// same as before, it is false when it returns
 318                             }
 319
 320                         }
 321
 322                         // Debug.Assert(j == candidatesNotInIndex, "Whole ndxDesc should be filled!");
 323
 324                         index = new Index(table, ndxFields, recordStates, null);
 325                         if (!IsOperatorIn(this.expression)) {
 326                             // if the expression contains an 'IN' operator, the index will not be shared
 327                             // therefore we do not need to index.AddRef, also table would track index consuming more memory until first write
 328                             index.AddRef();
 329                         }
 330
 331
 332                         matchedCandidates = nCandidates;
 333                      }
 334                      else {
 335                         for (i=0; i<lenIndexDesc; i++) {
 336                             ndxFields[i] = IndexFields[i];
 337                             ColumnInfo canColumn = candidateColumns[IndexFields[i].Column.Ordinal];
 338                             if (canColumn != null)
 339                                 canColumn.flag = true;
 340                         }
 341                          j=i;
 342                         for (i=0; i<lenCanColumns; i++) {
 343                             if (candidateColumns[i] != null) {
 344                                 if(!candidateColumns[i].flag) {
 345                                     ndxFields[j++] = new IndexField(this.table.Columns[i], isDescending: false);
 346                                 }
 347                                 else {
 348                                     candidateColumns[i].flag = false;
 349                                 }
 350                             }
 351                         }
 352 //                        Debug.Assert(j == nCandidates+indexNotInCandidates, "Whole ndxDesc should be filled!");
 353
 354                         index = new Index(table, ndxFields, recordStates, null);
 355                         matchedCandidates = 0;
 356                         if (this.linearExpression != this.expression) {
 357                             IndexField[] fields = index.IndexFields;
 358                             while (matchedCandidates < j) { // Microsoft : j = index.IndexDesc.Length
 359                                 ColumnInfo canColumn = candidateColumns[fields[matchedCandidates].Column.Ordinal];
 360                                 if (canColumn == null || canColumn.expr == null)
 361                                     break;
 362                                 matchedCandidates++;
 363                                 if (!canColumn.equalsOperator)
 364                                     break;
 365                             }
 366                         }
 367                         for(i = 0; i < candidateColumns.Length; i++) {
 368                             if (candidateColumns[i] != null) {
 369                                 candidateColumns[i].flag = false;// same as before, it is false when it returns
 370                             }
 371                         }
 372                     }
 373                 }
 374             }
 375         }
 376
 377
 378         private bool IsOperatorIn(ExpressionNode enode) {
 379             BinaryNode bnode = (enode as BinaryNode);
 380             if (null != bnode) {
 381                 if (Operators.In == bnode.op  ||
 382                     IsOperatorIn(bnode.right) ||
 383                     IsOperatorIn(bnode.left))
 384                 {
 385                     return true;
 386                 }
 387             }
 388             return false;
 389         }
 390
 391
 392
 393         // Based on the current index and candidate columns settings, build the linear expression; Should be called only when there is atleast something for Binary Searching
 394         private void BuildLinearExpression() {
 395             int i;
 396             IndexField[] fields = index.IndexFields;
 397             int lenId = fields.Length;
 398             Debug.Assert(matchedCandidates > 0 && matchedCandidates <= lenId, "BuildLinearExpression : Invalid Index");
 399             for (i=0; i<matchedCandidates; i++) {
 400                 ColumnInfo canColumn = candidateColumns[fields[i].Column.Ordinal];
 401                 Debug.Assert(canColumn != null && canColumn.expr != null, "BuildLinearExpression : Must be a matched candidate");
 402                 canColumn.flag = true;
 403             }
 404             //this is invalid assert, assumption was that all equals operator exists at the begining of candidateColumns
 405             // but with QFE 1704, this assumption is not true anymore
 406 //            Debug.Assert(matchedCandidates==1 || candidateColumns[matchedCandidates-1].equalsOperator, "BuildLinearExpression : Invalid matched candidates");
 407             int lenCanColumns = candidateColumns.Length;
 408             for (i=0; i<lenCanColumns; i++) {
 409                 if (candidateColumns[i] != null) {
 410                     if (!candidateColumns[i].flag) {
 411                         if (candidateColumns[i].expr != null) {
 412                             this.linearExpression = (this.linearExpression == null ? candidateColumns[i].expr : new BinaryNode(table, Operators.And, candidateColumns[i].expr, this.linearExpression));
 413                         }
 414                     }
 415                     else {
 416                         candidateColumns[i].flag = false;
 417                     }
 418                 }
 419             }
 420 //            Debug.Assert(this.linearExpression != null, "BuildLinearExpression : How come there is nothing to search linearly");
 421         }
 422
 423         public DataRow[] SelectRows() {
 424             bool needSorting = true;
 425
 426             InitCandidateColumns();
 427
 428             if (this.expression is BinaryNode) {
 429                 AnalyzeExpression((BinaryNode)this.expression);
 430                 if (!candidatesForBinarySearch) {
 431                     this.linearExpression = this.expression;
 432                 }
 433                 if (this.linearExpression == this.expression) {
 434                     for (int i=0; i<candidateColumns.Length; i++) {
 435                         if (candidateColumns[i] != null) {
 436                             candidateColumns[i].equalsOperator = false;
 437                             candidateColumns[i].expr = null;
 438                         }
 439                     }
 440                 }
 441                 else {
 442                     needSorting = !FindClosestCandidateIndex();
 443                 }
 444             }
 445             else {
 446                 this.linearExpression = this.expression;
 447             }
 448
 449             if (index == null && (IndexFields.Length > 0 || this.linearExpression == this.expression)) {
 450                 needSorting = !FindSortIndex();
 451             }
 452
 453             if (index == null) {
 454                 CreateIndex();
 455                 needSorting = false;
 456             }
 457
 458             if (index.RecordCount == 0)
 459                 return table.NewRowArray(0);
 460
 461             Range range;
 462             if (matchedCandidates == 0) { // Microsoft : Either dont have rowFilter or only linear search expression
 463                 range = new Range(0, index.RecordCount-1);
 464                 Debug.Assert(!needSorting, "What are we doing here if no real reuse of this index ?");
 465                 this.linearExpression = this.expression;
 466                 return GetLinearFilteredRows(range);
 467             }
 468             else {
 469                 range = GetBinaryFilteredRecords();
 470                 if (range.Count == 0)
 471                     return table.NewRowArray(0);
 472                 if (matchedCandidates < nCandidates) {
 473                     BuildLinearExpression();
 474                 }
 475                 if (!needSorting) {
 476                     return GetLinearFilteredRows(range);
 477                 }
 478                 else {
 479                     this.records = GetLinearFilteredRecords(range);
 480                     this.recordCount = this.records.Length;
 481                     if (this.recordCount == 0)
 482                         return table.NewRowArray(0);
 483                     Sort(0, this.recordCount-1);
 484                     return GetRows();
 485                 }
 486             }
 487         }
 488
 489         public DataRow[] GetRows() {
 490             DataRow[] newRows = table.NewRowArray(recordCount);
 491             for (int i = 0; i < newRows.Length; i++) {
 492                 newRows[i] = table.recordManager[records[i]];
 493             }
 494             return newRows;
 495         }
 496
 497         private bool AcceptRecord(int record) {
 498             DataRow row = table.recordManager[record];
 499
 500             if (row == null)
 501                 return true;
 502
 503             //
 504
 505             DataRowVersion version = DataRowVersion.Default;
 506             if (row.oldRecord == record) {
 507                 version = DataRowVersion.Original;
 508             }
 509             else if (row.newRecord == record) {
 510                 version = DataRowVersion.Current;
 511             }
 512             else if (row.tempRecord == record) {
 513                 version = DataRowVersion.Proposed;
 514             }
 515
 516             object val = this.linearExpression.Eval(row, version);
 517             bool result;
 518             try {
 519                 result = DataExpression.ToBoolean(val);
 520             }
 521             catch (Exception e) {
 522                 //
 523                 if (!ADP.IsCatchableExceptionType(e)) {
 524                     throw;
 525                 }
 526                 throw ExprException.FilterConvertion(this.rowFilter.Expression);
 527             }
 528             return result;
 529         }
 530
 531         private int Eval(BinaryNode expr, DataRow row, DataRowVersion version) {
 532             if (expr.op == Operators.And) {
 533                 int lResult = Eval((BinaryNode)expr.left,row,version);
 534                 if (lResult != 0)
 535                     return lResult;
 536                 int rResult = Eval((BinaryNode)expr.right,row,version);
 537                 if (rResult != 0)
 538                     return rResult;
 539                 return 0;
 540             }
 541
 542             long c = 0;
 543             object vLeft  = expr.left.Eval(row, version);
 544             if (expr.op != Operators.Is && expr.op != Operators.IsNot) {
 545                 object vRight = expr.right.Eval(row, version);
 546                 bool isLConst = (expr.left is ConstNode);
 547                 bool isRConst = (expr.right is ConstNode);
 548
 549                 if ((vLeft == DBNull.Value)||(expr.left.IsSqlColumn && DataStorage.IsObjectSqlNull(vLeft)))
 550                     return -1;
 551                 if ((vRight == DBNull.Value)||(expr.right.IsSqlColumn && DataStorage.IsObjectSqlNull(vRight)))
 552                     return 1;
 553
 554                 StorageType leftType = DataStorage.GetStorageType(vLeft.GetType());
 555                 if (StorageType.Char == leftType) {
 556                     if ((isRConst)||(!expr.right.IsSqlColumn))
 557                         vRight = Convert.ToChar(vRight, table.FormatProvider);
 558                     else
 559                        vRight = SqlConvert.ChangeType2(vRight, StorageType.Char, typeof(char), table.FormatProvider);
 560                 }
 561
 562                 StorageType rightType = DataStorage.GetStorageType(vRight.GetType());
 563                 StorageType resultType;
 564                 if (expr.left.IsSqlColumn || expr.right.IsSqlColumn) {
 565                     resultType = expr.ResultSqlType(leftType, rightType, isLConst, isRConst, expr.op);
 566                 }
 567                 else {
 568                     resultType = expr.ResultType(leftType, rightType, isLConst, isRConst, expr.op);
 569                 }
 570                 if (StorageType.Empty == resultType) {
 571                     expr.SetTypeMismatchError(expr.op, vLeft.GetType(), vRight.GetType());
 572                 }
 573
 574                 // if comparing a Guid column value against a string literal
 575                 // use InvariantCulture instead of DataTable.Locale because in the Danish related cultures
 576                 // sorting a Guid as a string has different results than in Invariant and English related cultures.
 577                 // This fix is restricted to DataTable.Select("GuidColumn = 'string literal'") types of queries
 578                 NameNode namedNode = null;
 579                 System.Globalization.CompareInfo comparer =
 580                     ((isLConst && !isRConst && (leftType == StorageType.String) && (rightType == StorageType.Guid) && (null != (namedNode = expr.right as NameNode)) && (namedNode.column.DataType == typeof(Guid))) ||
 581                      (isRConst && !isLConst && (rightType == StorageType.String) && (leftType == StorageType.Guid) && (null != (namedNode = expr.left as NameNode)) && (namedNode.column.DataType == typeof(Guid))))
 582                      ? System.Globalization.CultureInfo.InvariantCulture.CompareInfo : null;
 583
 584                 c = expr.BinaryCompare(vLeft, vRight, resultType, expr.op, comparer);
 585             }
 586             switch(expr.op) {
 587                 case Operators.EqualTo:         c = (c == 0 ? 0 : c < 0  ? -1 :  1); break;
 588                 case Operators.GreaterThen:     c = (c > 0  ? 0 : -1); break;
 589                 case Operators.LessThen:        c = (c < 0  ? 0 : 1); break;
 590                 case Operators.GreaterOrEqual:  c = (c >= 0 ? 0 : -1); break;
 591                 case Operators.LessOrEqual:     c = (c <= 0 ? 0 : 1); break;
 592                 case Operators.Is:              c = (vLeft == DBNull.Value ? 0 : -1); break;
 593                 case Operators.IsNot:           c = (vLeft != DBNull.Value ? 0 : 1);  break;
 594                 default:                        Debug.Assert(true, "Unsupported Binary Search Operator!"); break;
 595             }
 596             return (int)c;
 597         }
 598
 599         private int Evaluate(int record) {
 600             DataRow row = table.recordManager[record];
 601
 602             if (row == null)
 603                 return 0;
 604
 605             //
 606
 607             DataRowVersion version = DataRowVersion.Default;
 608             if (row.oldRecord == record) {
 609                 version = DataRowVersion.Original;
 610             }
 611             else if (row.newRecord == record) {
 612                 version = DataRowVersion.Current;
 613             }
 614             else if (row.tempRecord == record) {
 615                 version = DataRowVersion.Proposed;
 616             }
 617
 618             IndexField[] fields = index.IndexFields;
 619             for (int i=0; i < matchedCandidates; i++) {
 620                 int columnOrdinal = fields[i].Column.Ordinal;
 621                 Debug.Assert(candidateColumns[columnOrdinal] != null, "How come this is not a candidate column");
 622                 Debug.Assert(candidateColumns[columnOrdinal].expr != null, "How come there is no associated expression");
 623                 int c = Eval(candidateColumns[columnOrdinal].expr, row, version);
 624                 if (c != 0)
 625                     return fields[i].IsDescending ? -c : c;
 626             }
 627             return 0;
 628         }
 629
 630         private int FindFirstMatchingRecord() {
 631             int rec = -1;
 632             int lo = 0;
 633             int hi = index.RecordCount - 1;
 634             while (lo <= hi) {
 635                 int i = lo + hi >> 1;
 636                 int recNo = index.GetRecord(i);
 637                 int c = Evaluate(recNo);
 638                 if (c == 0) { rec = i; }
 639                 if (c < 0) lo = i + 1;
 640                 else hi = i - 1;
 641             }
 642             return rec;
 643         }
 644
 645         private int FindLastMatchingRecord(int lo) {
 646             int rec = -1;
 647             int hi = index.RecordCount - 1;
 648             while (lo <= hi) {
 649                 int i = lo + hi >> 1;
 650                 int recNo = index.GetRecord(i);
 651                 int c = Evaluate(recNo);
 652                 if (c == 0) { rec = i; }
 653                 if (c <= 0) lo = i + 1;
 654                 else hi = i - 1;
 655             }
 656             return rec;
 657         }
 658
 659         private Range GetBinaryFilteredRecords() {
 660             if (matchedCandidates == 0) {
 661                 return new Range(0, index.RecordCount-1);
 662             }
 663             Debug.Assert(matchedCandidates <= index.IndexFields.Length, "GetBinaryFilteredRecords : Invalid Index");
 664             int lo = FindFirstMatchingRecord();
 665             if (lo == -1) {
 666                 return new Range();
 667             }
 668             int hi = FindLastMatchingRecord(lo);
 669             Debug.Assert (lo <= hi, "GetBinaryFilteredRecords : Invalid Search Results");
 670             return new Range(lo, hi);
 671         }
 672
 673         private int[] GetLinearFilteredRecords(Range range) {
 674             if (this.linearExpression == null) {
 675                 int[] resultRecords = new int[range.Count];
 676                 RBTree<int>.RBTreeEnumerator iterator = index.GetEnumerator(range.Min);
 677                 for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
 678                     resultRecords[i] = iterator.Current;
 679                 }
 680                 return resultRecords;
 681             }
 682             else {
 683                 List<int> matchingRecords = new List<int>();
 684                 RBTree<int>.RBTreeEnumerator iterator = index.GetEnumerator(range.Min);
 685                 for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
 686                     if (AcceptRecord(iterator.Current)) {
 687                         matchingRecords.Add(iterator.Current);
 688                     }
 689                 }
 690                 return matchingRecords.ToArray();
 691             }
 692         }
 693
 694         private DataRow[] GetLinearFilteredRows(Range range) {
 695             DataRow[] resultRows;
 696             if (this.linearExpression == null) {
 697                 return index.GetRows(range);
 698             }
 699
 700             List<DataRow> matchingRows = new List<DataRow>();
 701             RBTree<int>.RBTreeEnumerator iterator = index.GetEnumerator(range.Min);
 702             for (int i = 0; i < range.Count && iterator.MoveNext(); i++) {
 703                 if (AcceptRecord(iterator.Current)) {
 704                     matchingRows.Add(table.recordManager[iterator.Current]);
 705                 }
 706             }
 707             resultRows = table.NewRowArray(matchingRows.Count);
 708             matchingRows.CopyTo(resultRows);
 709             return resultRows;
 710         }
 711
 712
 713         private int CompareRecords(int record1, int record2) {
 714             int lenIndexDesc = IndexFields.Length;
 715             for (int i = 0; i < lenIndexDesc; i++) {
 716                 int c = IndexFields[i].Column.Compare(record1, record2);
 717                 if (c != 0) {
 718                     if (IndexFields[i].IsDescending) c = -c;
 719                     return c;
 720                 }
 721             }
 722
 723             long id1 = table.recordManager[record1] == null? 0: table.recordManager[record1].rowID;
 724             long id2 = table.recordManager[record2] == null ? 0 : table.recordManager[record2].rowID;
 725             int diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
 726
 727             // if they're two records in the same row, we need to be able to distinguish them.
 728             if (diff == 0 && record1 != record2 &&
 729                 table.recordManager[record1] != null && table.recordManager[record2] != null) {
 730                 id1 = (int)table.recordManager[record1].GetRecordState(record1);
 731                 id2 = (int)table.recordManager[record2].GetRecordState(record2);
 732                 diff = (id1 < id2) ? -1 : ((id2 < id1) ? 1 : 0);
 733             }
 734
 735             return diff;
 736         }
 737
 738         private void Sort(int left, int right) {
 739             int i, j;
 740             int record;
 741             do {
 742                 i = left;
 743                 j = right;
 744                 record = records[i + j >> 1];
 745                 do {
 746                     while (CompareRecords(records[i], record) < 0) i++;
 747                     while (CompareRecords(records[j], record) > 0) j--;
 748                     if (i <= j) {
 749                         int r = records[i];
 750                         records[i] = records[j];
 751                         records[j] = r;
 752                         i++;
 753                         j--;
 754                     }
 755                 } while (i <= j);
 756                 if (left < j) Sort(left, j);
 757                 left = i;
 758             } while (i < right);
 759         }
 760     }
 761 }