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