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

   1 //------------------------------------------------------------------------------
   2 // <copyright file="Selection.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 //------------------------------------------------------------------------------
   8
   9 namespace System.Data {
  10     using System;
  11     using System.Diagnostics;
  12     using System.ComponentModel;
  13     using System.Collections.Generic;
  14     using System.Threading;
  15
  16     internal struct IndexField {
  17         public readonly DataColumn Column;
  18         public readonly bool IsDescending; // false = Asc; true = Desc what is default value for this?
  19
  20         internal IndexField(DataColumn column, bool isDescending) {
  21             Debug.Assert(column != null, "null column");
  22
  23             Column = column;
  24             IsDescending = isDescending;
  25         }
  26
  27         public static bool operator == (IndexField if1, IndexField if2) {
  28             return if1.Column == if2.Column && if1.IsDescending == if2.IsDescending;
  29         }
  30
  31         public static bool operator !=(IndexField if1, IndexField if2) {
  32             return !(if1 == if2);
  33         }
  34
  35         // must override Equals if == operator is defined
  36         public override bool Equals(object obj) {
  37             if (obj is IndexField)
  38                 return this == (IndexField)obj;
  39             else
  40                 return false;
  41         }
  42
  43         // must override GetHashCode if Equals is redefined
  44         public override int GetHashCode() {
  45             return Column.GetHashCode() ^ IsDescending.GetHashCode();
  46         }
  47     }
  48
  49     internal sealed class Index {
  50
  51         private sealed class IndexTree : RBTree<int> {
  52             private readonly Index _index;
  53
  54             internal IndexTree(Index index) : base(TreeAccessMethod.KEY_SEARCH_AND_INDEX) {
  55                 _index = index;
  56             }
  57
  58             protected override int CompareNode (int record1, int record2) {
  59                 return _index.CompareRecords(record1, record2);
  60             }
  61             protected override int CompareSateliteTreeNode (int record1, int record2) {
  62                 return _index.CompareDuplicateRecords(record1, record2);
  63             }
  64         }
  65
  66         // these constants are used to update a DataRow when the record and Row are known, but don't match
  67         private const int DoNotReplaceCompareRecord  = 0;
  68         private const int ReplaceNewRecordForCompare = 1;
  69         private const int ReplaceOldRecordForCompare = 2;
  70
  71         private readonly DataTable table;
  72         internal readonly IndexField[] IndexFields;
  73
  74         /// <summary>Allow a user implemented comparision of two DataRow</summary>
  75         /// <remarks>User must use correct DataRowVersion in comparison or index corruption will happen</remarks>
  76         private readonly System.Comparison<DataRow> _comparison;
  77
  78         private readonly DataViewRowState recordStates;
  79         private WeakReference rowFilter;
  80         private IndexTree records;
  81         private int recordCount;
  82         private int refCount;
  83
  84         private Listeners<DataViewListener> _listeners;
  85
  86         private bool suspendEvents;
  87
  88         private readonly static object[] zeroObjects = new object[0];
  89         private readonly bool isSharable;
  90         private readonly bool _hasRemoteAggregate;
  91
  92         internal const Int32 MaskBits     = unchecked((int)0x7FFFFFFF);
  93
  94         private static int _objectTypeCount; // Bid counter
  95         private readonly int _objectID = System.Threading.Interlocked.Increment(ref _objectTypeCount);
  96
  97         public Index(DataTable table, IndexField[] indexFields, DataViewRowState recordStates, IFilter rowFilter)
  98             : this(table, indexFields, null, recordStates, rowFilter) { }
  99
 100         public Index(DataTable table, System.Comparison<DataRow> comparison, DataViewRowState recordStates, IFilter rowFilter)
 101             : this(table, GetAllFields(table.Columns), comparison, recordStates, rowFilter) { }
 102
 103         // for the delegate methods, we don't know what the dependent columns are - so all columns are dependent
 104         private static IndexField[] GetAllFields(DataColumnCollection columns) {
 105             IndexField[] fields = new IndexField[columns.Count];
 106             for(int i = 0; i < fields.Length; ++i) {
 107                 fields[i] = new IndexField(columns[i], false);
 108             }
 109             return fields;
 110         }
 111
 112         private Index(DataTable table, IndexField[] indexFields, System.Comparison<DataRow> comparison, DataViewRowState recordStates, IFilter rowFilter) {
 113             Bid.Trace("<ds.Index.Index|API> %d#, table=%d, recordStates=%d{ds.DataViewRowState}\n",
 114                             ObjectID, (table != null) ? table.ObjectID : 0, (int)recordStates);
 115             Debug.Assert(indexFields != null);
 116             Debug.Assert(null != table, "null table");
 117             if ((recordStates &
 118                  (~(DataViewRowState.CurrentRows | DataViewRowState.OriginalRows))) != 0) {
 119                 throw ExceptionBuilder.RecordStateRange();
 120             }
 121             this.table = table;
 122             _listeners = new Listeners<DataViewListener>(ObjectID,
 123                 delegate(DataViewListener listener)
 124                 {
 125                     return (null != listener);
 126                 });
 127
 128             IndexFields = indexFields;
 129             this.recordStates = recordStates;
 130             _comparison = comparison;
 131
 132             DataColumnCollection columns = table.Columns;
 133             isSharable = (rowFilter == null) && (comparison == null); // a filter or comparison make an index unsharable
 134             if (null != rowFilter) {
 135                 this.rowFilter = new WeakReference(rowFilter);
 136                 DataExpression expr = (rowFilter as DataExpression);
 137                 if (null != expr) {
 138                     _hasRemoteAggregate = expr.HasRemoteAggregate();
 139                 }
 140             }
 141             InitRecords(rowFilter);
 142
 143             // do not AddRef in ctor, every caller should be responsible to AddRef it
 144             // if caller does not AddRef, it is expected to be a one-time read operation because the index won't be maintained on writes
 145         }
 146
 147         public bool Equal(IndexField[] indexDesc, DataViewRowState recordStates, IFilter rowFilter) {
 148             if (
 149                 !isSharable ||
 150                 IndexFields.Length != indexDesc.Length ||
 151                 this.recordStates     != recordStates     ||
 152                 null                  != rowFilter
 153             ) {
 154                 return false;
 155             }
 156
 157             for (int loop = 0; loop < IndexFields.Length; loop++) {
 158                 if (IndexFields[loop].Column!= indexDesc[loop].Column ||
 159                     IndexFields[loop].IsDescending != indexDesc[loop].IsDescending) {
 160                     return false;
 161                 }
 162             }
 163
 164             return true;
 165         }
 166
 167         internal bool HasRemoteAggregate {
 168             get {
 169                 return _hasRemoteAggregate;
 170             }
 171         }
 172
 173         internal int ObjectID {
 174             get {
 175                 return _objectID;
 176             }
 177         }
 178
 179         public DataViewRowState RecordStates {
 180             get { return recordStates; }
 181         }
 182
 183         public IFilter RowFilter {
 184             get { return (IFilter)((null != rowFilter) ? rowFilter.Target : null); }
 185         }
 186
 187         public int GetRecord(int recordIndex) {
 188             Debug.Assert (recordIndex >= 0 && recordIndex < recordCount, "recordIndex out of range");
 189             return records[recordIndex];
 190         }
 191
 192         public bool HasDuplicates {
 193             get {
 194                 return records.HasDuplicates;
 195             }
 196         }
 197
 198         public int RecordCount {
 199             get {
 200                 return recordCount;
 201             }
 202         }
 203
 204         public bool IsSharable {
 205             get {
 206                 return isSharable;
 207             }
 208         }
 209
 210
 211         private bool AcceptRecord(int record) {
 212             return AcceptRecord(record, RowFilter);
 213         }
 214
 215         private bool AcceptRecord(int record, IFilter filter) {
 216             Bid.Trace("<ds.Index.AcceptRecord|API> %d#, record=%d\n", ObjectID, record);
 217             if (filter == null)
 218                 return true;
 219
 220             DataRow row = table.recordManager[record];
 221
 222             if (row == null)
 223                 return true;
 224
 225             //
 226
 227             DataRowVersion version = DataRowVersion.Default;
 228             if (row.oldRecord == record) {
 229                 version = DataRowVersion.Original;
 230             }
 231             else if (row.newRecord == record) {
 232                 version = DataRowVersion.Current;
 233             }
 234             else if (row.tempRecord == record) {
 235                 version = DataRowVersion.Proposed;
 236             }
 237
 238             return filter.Invoke(row, version);
 239         }
 240
 241         /// <remarks>Only call from inside a lock(this)</remarks>
 242         internal void ListChangedAdd(DataViewListener listener) {
 243             _listeners.Add(listener);
 244         }
 245
 246         /// <remarks>Only call from inside a lock(this)</remarks>
 247         internal void ListChangedRemove(DataViewListener listener) {
 248             _listeners.Remove(listener);
 249         }
 250
 251         public int RefCount {
 252             get {
 253                 return refCount;
 254             }
 255         }
 256
 257         public void AddRef() {
 258             Bid.Trace("<ds.Index.AddRef|API> %d#\n", ObjectID);
 259             LockCookie lc = table.indexesLock.UpgradeToWriterLock(-1);
 260             try {
 261                 Debug.Assert(0 <= refCount, "AddRef on disposed index");
 262                 Debug.Assert(null != records, "null records");
 263                 if (refCount == 0) {
 264                     table.ShadowIndexCopy();
 265                     table.indexes.Add(this);
 266                 }
 267                 refCount++;
 268             }
 269             finally {
 270                 table.indexesLock.DowngradeFromWriterLock(ref lc);
 271             }
 272         }
 273
 274         public int RemoveRef() {
 275             Bid.Trace("<ds.Index.RemoveRef|API> %d#\n", ObjectID);
 276             int count;
 277             LockCookie lc = table.indexesLock.UpgradeToWriterLock(-1);
 278             try {
 279                 count = --refCount;
 280                 if (refCount <= 0) {
 281                     table.ShadowIndexCopy();
 282                     table.indexes.Remove(this);
 283                 }
 284             }
 285             finally {
 286                 table.indexesLock.DowngradeFromWriterLock(ref lc);
 287             }
 288             return count;
 289         }
 290
 291         private void ApplyChangeAction(int record, int action, int changeRecord) {
 292             if (action != 0) {
 293                 if (action > 0) {
 294                     if (AcceptRecord(record)) {
 295                         InsertRecord(record, true);
 296                     }
 297                 }
 298                 else if ((null != _comparison) && (-1 != record)) {
 299                     // when removing a record, the DataRow has already been updated to the newer record
 300                     // depending on changeRecord, either the new or old record needs be backdated to record
 301                     // for Comparison<DataRow> to operate correctly
 302                     DeleteRecord(GetIndex(record, changeRecord));
 303                 }
 304                 else {
 305                     // unnecessary codepath other than keeping original code path for redbits
 306                     DeleteRecord(GetIndex(record));
 307                 }
 308             }
 309         }
 310
 311         public bool CheckUnique() {
 312 #if DEBUG
 313             Debug.Assert(records.CheckUnique(records.root) != HasDuplicates, "CheckUnique difference");
 314 #endif
 315             return !HasDuplicates;
 316         }
 317
 318 // only used for main tree compare, not satalite tree
 319         private int CompareRecords(int record1, int record2) {
 320             if (null != _comparison) {
 321                 return CompareDataRows(record1, record2);
 322             }
 323             if (0 < IndexFields.Length) {
 324                 for (int i = 0; i < IndexFields.Length; i++) {
 325                     int c = IndexFields[i].Column.Compare(record1, record2);
 326                     if (c != 0) {
 327                         return (IndexFields[i].IsDescending ? -c : c);
 328                     }
 329                 }
 330                 return 0;
 331             }
 332             else {
 333                 Debug.Assert(null != table.recordManager[record1], "record1 no datarow");
 334                 Debug.Assert(null != table.recordManager[record2], "record2 no datarow");
 335
 336                 // DataRow needs to always updated appropriately via GetIndex(int,int)
 337                 //table.recordManager.VerifyRecord(record1, table.recordManager[record1]);
 338                 //table.recordManager.VerifyRecord(record2, table.recordManager[record2]);
 339
 340                 // Need to use compare because subtraction will wrap
 341                 // to positive for very large neg numbers, etc.
 342                 return table.Rows.IndexOf(table.recordManager[record1]).CompareTo(table.Rows.IndexOf(table.recordManager[record2]));
 343             }
 344         }
 345
 346         private int CompareDataRows(int record1, int record2)
 347         {
 348             table.recordManager.VerifyRecord(record1, table.recordManager[record1]);
 349             table.recordManager.VerifyRecord(record2, table.recordManager[record2]);
 350             return _comparison(table.recordManager[record1], table.recordManager[record2]);
 351         }
 352
 353
 354 // PS: same as previous CompareRecords, except it compares row state if needed
 355 // only used for satalite tree compare
 356         private int CompareDuplicateRecords(int record1, int record2) {
 357 #if DEBUG
 358             if (null != _comparison) {
 359                 Debug.Assert(0 == CompareDataRows(record1, record2), "duplicate record not a duplicate by user function");
 360             }
 361             else if (record1 != record2) {
 362                 for (int i = 0; i < IndexFields.Length; i++) {
 363                     int c = IndexFields[i].Column.Compare(record1, record2);
 364                     Debug.Assert(0 == c, "duplicate record not a duplicate");
 365                 }
 366             }
 367 #endif
 368             Debug.Assert(null != table.recordManager[record1], "record1 no datarow");
 369             Debug.Assert(null != table.recordManager[record2], "record2 no datarow");
 370
 371             // DataRow needs to always updated appropriately via GetIndex(int,int)
 372             //table.recordManager.VerifyRecord(record1, table.recordManager[record1]);
 373             //table.recordManager.VerifyRecord(record2, table.recordManager[record2]);
 374
 375             if (null == table.recordManager[record1]) {
 376                 return ((null == table.recordManager[record2]) ? 0 : -1);
 377             }
 378             else if (null == table.recordManager[record2]) {
 379                 return 1;
 380             }
 381
 382             // Need to use compare because subtraction will wrap
 383             // to positive for very large neg numbers, etc.
 384             int diff = table.recordManager[record1].rowID.CompareTo(table.recordManager[record2].rowID);
 385
 386             // if they're two records in the same row, we need to be able to distinguish them.
 387             if ((diff == 0) && (record1 != record2)) {
 388                 diff = ((int)table.recordManager[record1].GetRecordState(record1)).CompareTo((int)table.recordManager[record2].GetRecordState(record2));
 389             }
 390             return diff;
 391         }
 392
 393         private int CompareRecordToKey(int record1, object[] vals) {
 394             for (int i = 0; i < IndexFields.Length; i++) {
 395                 int c = IndexFields[i].Column.CompareValueTo(record1, vals[i]);
 396                 if (c != 0) {
 397                     return (IndexFields[i].IsDescending ? -c : c);
 398                 }
 399             }
 400             return 0;
 401         }
 402
 403 // DeleteRecordFromIndex deletes the given record from index and does not fire any Event. IT SHOULD NOT FIRE EVENT
 404 // I added this since I can not use existing DeleteRecord which is not silent operation
 405         public  void DeleteRecordFromIndex(int recordIndex) { // this is for expression use, to maintain expression columns's sort , filter etc. do not fire event
 406             DeleteRecord(recordIndex, false);
 407         }
 408 // old and existing DeleteRecord behavior, we can not use this for silently deleting
 409         private void DeleteRecord(int recordIndex) {
 410             DeleteRecord(recordIndex, true);
 411         }
 412         private void DeleteRecord(int recordIndex, bool fireEvent) {
 413             Bid.Trace("<ds.Index.DeleteRecord|INFO> %d#, recordIndex=%d, fireEvent=%d{bool}\n", ObjectID, recordIndex, fireEvent);
 414
 415             if (recordIndex >= 0) {
 416                 recordCount--;
 417                 int record = records.DeleteByIndex(recordIndex);
 418
 419                 MaintainDataView(ListChangedType.ItemDeleted, record, !fireEvent);
 420
 421                 if (fireEvent) {
 422                     // 1) Webdata 104939 do not fix this, it would be breaking change
 423                     // 2) newRecord = -1, oldrecord = recordIndex;
 424                     OnListChanged(ListChangedType.ItemDeleted, recordIndex);
 425                 }
 426             }
 427         }
 428
 429         // SQLBU 428961: Serious performance issue when creating DataView
 430         // this improves performance by allowing DataView to iterating instead of computing for records over index
 431         // this will also allow Linq over DataSet to enumerate over the index
 432         // avoid boxing by returning RBTreeEnumerator (a struct) instead of IEnumerator<int>
 433         public RBTree<int>.RBTreeEnumerator GetEnumerator(int startIndex) {
 434             return new IndexTree.RBTreeEnumerator(records, startIndex);
 435         }
 436
 437         // What it actually does is find the index in the records[] that
 438         // this record inhabits, and if it doesn't, suggests what index it would
 439         // inhabit while setting the high bit.
 440         //
 441
 442         public int GetIndex(int record) {
 443             int index = records.GetIndexByKey(record);
 444             return index;
 445         }
 446
 447         /// <summary>
 448         /// When searching by value for a specific record, the DataRow may require backdating to reflect the appropriate state
 449         /// otherwise on Delete of a DataRow in the Added state, would result in the <see cref="System.Comparison&lt;DataRow&gt;"/> where the row
 450         /// reflection record would be in the Detatched instead of Added state.
 451         /// </summary>
 452         private int GetIndex(int record, int changeRecord) {
 453             Debug.Assert(null != _comparison, "missing comparison");
 454
 455             int index;
 456             DataRow row = table.recordManager[record];
 457
 458             int a = row.newRecord;
 459             int b = row.oldRecord;
 460             try {
 461                 switch(changeRecord) {
 462                 case ReplaceNewRecordForCompare:
 463                     row.newRecord = record;
 464                     break;
 465                 case ReplaceOldRecordForCompare:
 466                      row.oldRecord = record;
 467                      break;
 468                 }
 469                 table.recordManager.VerifyRecord(record, row);
 470
 471                 index = records.GetIndexByKey(record);
 472             }
 473             finally {
 474                 switch(changeRecord) {
 475                 case ReplaceNewRecordForCompare:
 476                     Debug.Assert(record == row.newRecord, "newRecord has change during GetIndex");
 477                     row.newRecord = a;
 478                     break;
 479                 case ReplaceOldRecordForCompare:
 480                     Debug.Assert(record == row.oldRecord, "oldRecord has change during GetIndex");
 481                      row.oldRecord = b;
 482                      break;
 483                 }
 484 #if DEBUG
 485                 if (-1 != a) {
 486                     table.recordManager.VerifyRecord(a, row);
 487                 }
 488 #endif
 489             }
 490             return index;
 491         }
 492
 493         public object[] GetUniqueKeyValues() {
 494             if (IndexFields == null || IndexFields.Length == 0) {
 495                 return zeroObjects;
 496             }
 497             List<object[]> list = new List<object[]>();
 498             GetUniqueKeyValues(list, records.root);
 499             return list.ToArray();
 500         }
 501
 502         /// <summary>
 503         /// Find index of maintree node that matches key in record
 504         /// </summary>
 505         public int FindRecord(int record) {
 506             int nodeId = records.Search(record);
 507             if (nodeId!=IndexTree.NIL)
 508                 return records.GetIndexByNode(nodeId); //always returns the First record index
 509             else
 510                 return -1;
 511         }
 512
 513         public int FindRecordByKey(object key) {
 514             int nodeId = FindNodeByKey(key);
 515             if (IndexTree.NIL != nodeId) {
 516                 return records.GetIndexByNode(nodeId);
 517             }
 518             return -1; // return -1 to user indicating record not found
 519         }
 520
 521         public int FindRecordByKey(object[] key) {
 522             int nodeId = FindNodeByKeys(key);
 523             if (IndexTree.NIL != nodeId) {
 524                 return records.GetIndexByNode(nodeId);
 525             }
 526             return -1; // return -1 to user indicating record not found
 527         }
 528
 529         private int FindNodeByKey(object originalKey) {
 530             int x, c;
 531             if (IndexFields.Length != 1) {
 532                 throw ExceptionBuilder.IndexKeyLength(IndexFields.Length, 1);
 533             }
 534
 535             x = records.root;
 536             if (IndexTree.NIL != x) { // otherwise storage may not exist
 537                 DataColumn column = IndexFields[0].Column;
 538                 object key = column.ConvertValue(originalKey);
 539
 540                 x = records.root;
 541                 if (IndexFields[0].IsDescending) {
 542                     while (IndexTree.NIL != x) {
 543                         c = column.CompareValueTo(records.Key(x), key);
 544                         if (c == 0) { break; }
 545                         if (c < 0) { x = records.Left(x); } // < for decsending
 546                         else { x = records.Right(x); }
 547                     }
 548                 }
 549                 else {
 550                     while (IndexTree.NIL != x) {
 551                         c = column.CompareValueTo(records.Key(x), key);
 552                         if (c == 0) { break; }
 553                         if (c > 0) { x = records.Left(x); } // > for ascending
 554                         else { x = records.Right(x); }
 555                     }
 556                 }
 557             }
 558             return x;
 559         }
 560
 561         private int FindNodeByKeys(object[] originalKey) {
 562             int x, c;
 563             c = ((null != originalKey) ? originalKey.Length : 0);
 564             if ((0 == c) || (IndexFields.Length != c)) {
 565                 throw ExceptionBuilder.IndexKeyLength(IndexFields.Length, c);
 566             }
 567
 568             x = records.root;
 569             if (IndexTree.NIL != x) { // otherwise storage may not exist
 570                 // copy array to avoid changing original
 571                 object[] key = new object[originalKey.Length];
 572                 for(int i = 0; i < originalKey.Length; ++i) {
 573                     key[i] = IndexFields[i].Column.ConvertValue(originalKey[i]);
 574                 }
 575
 576                 x = records.root;
 577                 while (IndexTree.NIL != x) {
 578                     c = CompareRecordToKey(records.Key(x), key);
 579                     if (c == 0) { break; }
 580                     if (c > 0) { x = records.Left(x); }
 581                     else { x = records.Right(x); }
 582                 }
 583             }
 584             return x;
 585         }
 586
 587         private int FindNodeByKeyRecord(int record) {
 588             int x, c;
 589             x = records.root;
 590             if (IndexTree.NIL != x) { // otherwise storage may not exist
 591                 x = records.root;
 592                 while (IndexTree.NIL != x) {
 593                     c = CompareRecords(records.Key(x), record);
 594                     if (c == 0) { break; }
 595                     if (c > 0) { x = records.Left(x); }
 596                     else { x = records.Right(x); }
 597                 }
 598             }
 599             return x;
 600         }
 601
 602
 603         internal delegate int ComparisonBySelector<TKey,TRow>(TKey key, TRow row) where TRow:DataRow;
 604
 605         /// <summary>This method exists for LinqDataView to keep a level of abstraction away from the RBTree</summary>
 606         internal Range FindRecords<TKey,TRow>(ComparisonBySelector<TKey,TRow> comparison, TKey key) where TRow:DataRow
 607         {
 608             int x = records.root;
 609             while (IndexTree.NIL != x)
 610             {
 611                 int c = comparison(key, (TRow)table.recordManager[records.Key(x)]);
 612                 if (c == 0) { break; }
 613                 if (c < 0) { x = records.Left(x); }
 614                 else { x = records.Right(x); }
 615             }
 616             return GetRangeFromNode(x);
 617         }
 618
 619         private Range GetRangeFromNode(int nodeId)
 620         {
 621             // fill range with the min and max indexes of matching record (i.e min and max of satelite tree)
 622             // min index is the index of the node in main tree, and max is the min + size of satelite tree-1
 623
 624             if (IndexTree.NIL == nodeId) {
 625                 return new Range();
 626             }
 627             int recordIndex = records.GetIndexByNode(nodeId);
 628
 629             if (records.Next (nodeId) == IndexTree.NIL)
 630                 return new Range (recordIndex, recordIndex);
 631
 632             int span = records.SubTreeSize(records.Next(nodeId));
 633             return new Range (recordIndex, recordIndex + span - 1);
 634         }
 635
 636         public Range FindRecords(object key) {
 637             int nodeId = FindNodeByKey (key);    // main tree node associated with key
 638             return GetRangeFromNode(nodeId);
 639         }
 640
 641         public Range FindRecords(object[] key) {
 642             int nodeId = FindNodeByKeys (key);    // main tree node associated with key
 643             return GetRangeFromNode(nodeId);
 644         }
 645
 646         internal void FireResetEvent() {
 647             Bid.Trace("<ds.Index.FireResetEvent|API> %d#\n", ObjectID);
 648             if (DoListChanged) {
 649                 OnListChanged(DataView.ResetEventArgs);
 650             }
 651         }
 652
 653         private int GetChangeAction(DataViewRowState oldState, DataViewRowState newState) {
 654             int oldIncluded = ((int)recordStates & (int)oldState) == 0? 0: 1;
 655             int newIncluded = ((int)recordStates & (int)newState) == 0? 0: 1;
 656             return newIncluded - oldIncluded;
 657         }
 658
 659         /// <summary>Determine if the record that needs backdating is the newRecord or oldRecord or neither</summary>
 660         private static int GetReplaceAction(DataViewRowState oldState)
 661         {
 662             return ((0 != (DataViewRowState.CurrentRows & oldState)) ? ReplaceNewRecordForCompare :    // Added/ModifiedCurrent/Unchanged
 663                     ((0 != (DataViewRowState.OriginalRows & oldState)) ? ReplaceOldRecordForCompare :   // Deleted/ModififedOriginal
 664                       DoNotReplaceCompareRecord));                                                      // None
 665         }
 666
 667         public DataRow GetRow(int i) {
 668             return table.recordManager[GetRecord(i)];
 669         }
 670
 671         public DataRow[] GetRows(Object[] values) {
 672             return GetRows(FindRecords(values));
 673         }
 674
 675         public DataRow[] GetRows(Range range) {
 676             DataRow[] newRows = table.NewRowArray(range.Count);
 677             if (0 < newRows.Length) {
 678                 RBTree<int>.RBTreeEnumerator iterator = GetEnumerator(range.Min);
 679                 for (int i = 0; i < newRows.Length && iterator.MoveNext(); i++) {
 680                     newRows[i] = table.recordManager[iterator.Current];
 681                 }
 682             }
 683             return newRows;
 684         }
 685
 686         private void InitRecords(IFilter filter) {
 687             DataViewRowState states = recordStates;
 688
 689             // SQLBU 428961: Serious performance issue when creating DataView
 690             // this improves performance when the is no filter, like with the default view (creating after rows added)
 691             // we know the records are in the correct order, just append to end, duplicates not possible
 692             bool append = (0 == IndexFields.Length);
 693
 694             records = new IndexTree(this);
 695
 696             recordCount = 0;
 697
 698             // SQLBU 428961: Serious performance issue when creating DataView
 699             // this improves performance by iterating of the index instead of computing record by index
 700             foreach(DataRow b in table.Rows)
 701             {
 702                 int record = -1;
 703                 if (b.oldRecord == b.newRecord) {
 704                     if ((int)(states & DataViewRowState.Unchanged) != 0) {
 705                         record = b.oldRecord;
 706                     }
 707                 }
 708                 else if (b.oldRecord == -1) {
 709                     if ((int)(states & DataViewRowState.Added) != 0) {
 710                         record = b.newRecord;
 711                     }
 712                 }
 713                 else if (b.newRecord == -1) {
 714                     if ((int)(states & DataViewRowState.Deleted) != 0) {
 715                         record = b.oldRecord;
 716                     }
 717                 }
 718                 else {
 719                     if ((int)(states & DataViewRowState.ModifiedCurrent) != 0) {
 720                         record = b.newRecord;
 721                     }
 722                     else if ((int)(states & DataViewRowState.ModifiedOriginal) != 0) {
 723                         record = b.oldRecord;
 724                     }
 725                 }
 726                 if (record != -1 && AcceptRecord(record, filter))
 727                 {
 728                     records.InsertAt(-1, record, append);
 729                     recordCount++;
 730                 }
 731             }
 732         }
 733
 734
 735 // InsertRecordToIndex inserts the given record to index and does not fire any Event. IT SHOULD NOT FIRE EVENT
 736 // I added this since I can not use existing InsertRecord which is not silent operation
 737 // it returns the position that record is inserted
 738         public  int  InsertRecordToIndex(int record) {
 739             int pos = -1;
 740             if (AcceptRecord(record)) {
 741                 pos = InsertRecord(record,  false);
 742             }
 743             return pos;
 744         }
 745
 746 // existing functionality, it calls the overlaod with fireEvent== true, so it still fires the event
 747         private int InsertRecord(int record, bool fireEvent) {
 748             Bid.Trace("<ds.Index.InsertRecord|INFO> %d#, record=%d, fireEvent=%d{bool}\n", ObjectID, record, fireEvent);
 749
 750             // SQLBU 428961: Serious performance issue when creating DataView
 751             // this improves performance when the is no filter, like with the default view (creating before rows added)
 752             // we know can append when the new record is the last row in table, normal insertion pattern
 753             bool append = false;
 754             if ((0 == IndexFields.Length) && (null != table))
 755             {
 756                 DataRow row = table.recordManager[record];
 757                 append = (table.Rows.IndexOf(row)+1 == table.Rows.Count);
 758             }
 759             int nodeId = records.InsertAt(-1, record, append);
 760
 761             recordCount++;
 762
 763             MaintainDataView(ListChangedType.ItemAdded, record, !fireEvent);
 764
 765             if (fireEvent) {
 766                 if (DoListChanged) {
 767                     OnListChanged(ListChangedType.ItemAdded, records.GetIndexByNode(nodeId));
 768                 }
 769                 return 0;
 770             }
 771             else {
 772                 return records.GetIndexByNode(nodeId);
 773             }
 774         }
 775
 776
 777     // Search for specified key
 778         public bool IsKeyInIndex(object key) {
 779             int x_id = FindNodeByKey(key);
 780             return (IndexTree.NIL != x_id);
 781         }
 782
 783         public bool IsKeyInIndex(object[] key) {
 784             int x_id = FindNodeByKeys(key);
 785             return (IndexTree.NIL != x_id);
 786         }
 787
 788         public bool IsKeyRecordInIndex(int record) {
 789             int x_id = FindNodeByKeyRecord(record);
 790             return (IndexTree.NIL != x_id);
 791         }
 792
 793         private bool DoListChanged {
 794             get { return (!suspendEvents && _listeners.HasListeners && !table.AreIndexEventsSuspended); }
 795         }
 796
 797         private void OnListChanged(ListChangedType changedType, int newIndex, int oldIndex) {
 798             if (DoListChanged) {
 799                 OnListChanged(new ListChangedEventArgs(changedType, newIndex, oldIndex));
 800             }
 801         }
 802
 803         private void OnListChanged(ListChangedType changedType, int index) {
 804             if (DoListChanged) {
 805                 OnListChanged(new ListChangedEventArgs(changedType, index));
 806             }
 807         }
 808
 809         private void OnListChanged(ListChangedEventArgs e) {
 810             Bid.Trace("<ds.Index.OnListChanged|INFO> %d#\n", ObjectID);
 811             Debug.Assert(DoListChanged, "supposed to check DoListChanged before calling to delay create ListChangedEventArgs");
 812
 813             _listeners.Notify(e, false, false,
 814                 delegate(DataViewListener listener, ListChangedEventArgs args, bool arg2, bool arg3)
 815                 {
 816                     listener.IndexListChanged(args);
 817                 });
 818         }
 819
 820         private void MaintainDataView(ListChangedType changedType, int record, bool trackAddRemove) {
 821             Debug.Assert(-1 <= record, "bad record#");
 822
 823             _listeners.Notify(changedType, ((0 <= record) ? table.recordManager[record] : null), trackAddRemove,
 824                 delegate(DataViewListener listener, ListChangedType type, DataRow row, bool track)
 825                 {
 826                     listener.MaintainDataView(changedType, row, track);
 827                 });
 828         }
 829
 830         public void Reset() {
 831             Bid.Trace("<ds.Index.Reset|API> %d#\n", ObjectID);
 832             InitRecords(RowFilter);
 833             MaintainDataView(ListChangedType.Reset, -1, false); // SQLBU 360388
 834             FireResetEvent();
 835         }
 836
 837         public void RecordChanged(int record) {
 838             Bid.Trace("<ds.Index.RecordChanged|API> %d#, record=%d\n", ObjectID, record);
 839             if (DoListChanged) {
 840                 int index = GetIndex(record);
 841                 if (index >= 0) {
 842                     OnListChanged(ListChangedType.ItemChanged, index);
 843                 }
 844             }
 845         }
 846 // new RecordChanged which takes oldIndex and newIndex and fires onListChanged
 847         public void RecordChanged(int oldIndex, int newIndex) {
 848             Bid.Trace("<ds.Index.RecordChanged|API> %d#, oldIndex=%d, newIndex=%d\n", ObjectID, oldIndex, newIndex);
 849
 850             if (oldIndex > -1 || newIndex > -1) { // no need to fire if it was not and will not be in index: this check means at least one version should be in index
 851                 if (oldIndex  == newIndex ) {
 852                     OnListChanged(ListChangedType.ItemChanged, newIndex, oldIndex);
 853                 }
 854                 else if (oldIndex == -1) { // it is added
 855                     OnListChanged(ListChangedType.ItemAdded, newIndex, oldIndex);
 856                 }
 857                 else  if (newIndex == -1) { // its deleted
 858                     // Do not fix this. see bug Bug 271076 for explanation.
 859                     OnListChanged(ListChangedType.ItemDeleted, oldIndex);
 860                 }
 861                 else {
 862                     OnListChanged(ListChangedType.ItemMoved, newIndex, oldIndex);
 863                 }
 864             }
 865         }
 866
 867         public void RecordStateChanged(int record, DataViewRowState oldState, DataViewRowState newState) {
 868             Bid.Trace("<ds.Index.RecordStateChanged|API> %d#, record=%d, oldState=%d{ds.DataViewRowState}, newState=%d{ds.DataViewRowState}\n", ObjectID, record, (int)oldState, (int)newState);
 869
 870             int action = GetChangeAction(oldState, newState);
 871             ApplyChangeAction(record, action, GetReplaceAction(oldState));
 872         }
 873
 874         public void RecordStateChanged(int oldRecord, DataViewRowState oldOldState, DataViewRowState oldNewState,
 875                                        int newRecord, DataViewRowState newOldState, DataViewRowState newNewState) {
 876
 877             Bid.Trace("<ds.Index.RecordStateChanged|API> %d#, oldRecord=%d, oldOldState=%d{ds.DataViewRowState}, oldNewState=%d{ds.DataViewRowState}, newRecord=%d, newOldState=%d{ds.DataViewRowState}, newNewState=%d{ds.DataViewRowState}\n", ObjectID,oldRecord, (int)oldOldState, (int)oldNewState, newRecord, (int)newOldState, (int)newNewState);
 878
 879             Debug.Assert((-1 == oldRecord) || (-1 == newRecord) ||
 880                          table.recordManager[oldRecord] == table.recordManager[newRecord],
 881                          "not the same DataRow when updating oldRecord and newRecord");
 882
 883             int oldAction = GetChangeAction(oldOldState, oldNewState);
 884             int newAction = GetChangeAction(newOldState, newNewState);
 885             if (oldAction == -1 && newAction == 1 && AcceptRecord(newRecord)) {
 886
 887                 int oldRecordIndex;
 888                 if ((null != _comparison) && oldAction < 0)
 889                 { // when oldRecord is being removed, allow GetIndexByKey updating the DataRow for Comparison<DataRow>
 890                     oldRecordIndex = GetIndex (oldRecord, GetReplaceAction(oldOldState));
 891                 }
 892                 else {
 893                     oldRecordIndex = GetIndex (oldRecord);
 894                 }
 895
 896                 if ((null == _comparison) && oldRecordIndex != -1 && CompareRecords(oldRecord, newRecord)==0) {
 897                     records.UpdateNodeKey(oldRecord, newRecord);    //change in place, as Both records have same key value
 898
 899                     int commonIndexLocation = GetIndex(newRecord);
 900                     OnListChanged(ListChangedType.ItemChanged, commonIndexLocation, commonIndexLocation);
 901                 }
 902                 else {
 903                     suspendEvents = true;
 904                     if (oldRecordIndex != -1) {
 905                         records.DeleteByIndex(oldRecordIndex); // DeleteByIndex doesn't require searching by key
 906                         recordCount--;
 907                     }
 908
 909                     records.Insert(newRecord);
 910                     recordCount++;
 911
 912                     suspendEvents = false;
 913
 914                     int newRecordIndex = GetIndex (newRecord);
 915                     if(oldRecordIndex == newRecordIndex) { // if the position is the same
 916                         OnListChanged (ListChangedType.ItemChanged, newRecordIndex, oldRecordIndex); // be carefull remove oldrecord index if needed
 917                     }
 918                     else {
 919                         if (oldRecordIndex == -1) {
 920                             MaintainDataView(ListChangedType.ItemAdded, newRecord, false);
 921                             OnListChanged(ListChangedType.ItemAdded, GetIndex(newRecord)); // oldLocation would be -1
 922                         }
 923                         else {
 924                             OnListChanged (ListChangedType.ItemMoved, newRecordIndex, oldRecordIndex);
 925                         }
 926                     }
 927                 }
 928             }
 929             else {
 930                 ApplyChangeAction(oldRecord, oldAction, GetReplaceAction(oldOldState));
 931                 ApplyChangeAction(newRecord, newAction, GetReplaceAction(newOldState));
 932             }
 933         }
 934
 935         internal DataTable Table {
 936             get {
 937                 return table;
 938             }
 939         }
 940
 941         private void GetUniqueKeyValues(List<object[]> list, int curNodeId) {
 942             if (curNodeId != IndexTree.NIL) {
 943                 GetUniqueKeyValues(list, records.Left(curNodeId));
 944
 945                 int record = records.Key(curNodeId);
 946                 object[] element = new object[IndexFields.Length]; // number of columns in PK
 947                 for (int j = 0; j < element.Length; ++j) {
 948                     element[j] = IndexFields[j].Column[record];
 949                 }
 950                 list.Add(element);
 951
 952                 GetUniqueKeyValues(list, records.Right(curNodeId));
 953             }
 954         }
 955
 956         internal static int IndexOfReference<T>(List<T> list, T item) where T : class {
 957             if (null != list) {
 958                 for (int i = 0; i < list.Count; ++i) {
 959                     if (Object.ReferenceEquals(list[i], item)) {
 960                         return i;
 961                     }
 962                 }
 963             }
 964             return -1;
 965         }
 966         internal static bool ContainsReference<T>(List<T> list, T item) where T : class {
 967             return (0 <= IndexOfReference(list, item));
 968         }
 969     }
 970
 971     internal sealed class Listeners<TElem> where TElem : class
 972     {
 973         private readonly List<TElem> listeners;
 974         private readonly Func<TElem, bool> filter;
 975         private readonly int ObjectID;
 976         private int _listenerReaderCount;
 977
 978         /// <summary>Wish this was defined in mscorlib.dll instead of System.Core.dll</summary>
 979         internal delegate void Action<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4);
 980
 981         /// <summary>Wish this was defined in mscorlib.dll instead of System.Core.dll</summary>
 982         internal delegate TResult Func<T1, TResult>(T1 arg1);
 983
 984         internal Listeners(int ObjectID, Func<TElem, bool> notifyFilter) {
 985             listeners = new List<TElem>();
 986             filter = notifyFilter;
 987             this.ObjectID = ObjectID;
 988             _listenerReaderCount = 0;
 989         }
 990
 991         internal bool HasListeners {
 992             get { return (0 < listeners.Count); }
 993         }
 994
 995
 996         /// <remarks>Only call from inside a lock</remarks>
 997         internal void Add(TElem listener) {
 998             Debug.Assert(null != listener, "null listener");
 999             Debug.Assert(!Index.ContainsReference(listeners, listener), "already contains reference");
1000             listeners.Add(listener);
1001         }
1002
1003         internal int IndexOfReference(TElem listener) {
1004             return Index.IndexOfReference(listeners, listener);
1005         }
1006
1007         /// <remarks>Only call from inside a lock</remarks>
1008         internal void Remove(TElem listener) {
1009             Debug.Assert(null != listener, "null listener");
1010
1011             int index = IndexOfReference(listener);
1012             Debug.Assert(0 <= index, "listeners don't contain listener");
1013             listeners[index] = null;
1014
1015             if (0 == _listenerReaderCount) {
1016                 listeners.RemoveAt(index);
1017                 listeners.TrimExcess();
1018             }
1019         }
1020
1021         /// <summary>
1022         /// Write operation which means user must control multi-thread and we can assume single thread
1023         /// </summary>
1024         internal void Notify<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3, Action<TElem, T1, T2, T3> action) {
1025             Debug.Assert(null != action, "no action");
1026             Debug.Assert(0 <= _listenerReaderCount, "negative _listEventCount");
1027
1028             int count = listeners.Count;
1029             if (0 < count) {
1030                 int nullIndex = -1;
1031
1032                 // protect against listeners shrinking via Remove
1033                 _listenerReaderCount++;
1034                 try {
1035                     // protect against listeners growing via Add since new listeners will already have the Notify in progress
1036                     for (int i = 0; i < count; ++i) {
1037                         // protect against listener being set to null (instead of being removed)
1038                         TElem listener = listeners[i];
1039                         if (filter(listener)) {
1040                             // perform the action on each listener
1041                             // some actions may throw an exception blocking remaning listeners from being notified (just like events)
1042                             action(listener, arg1, arg2, arg3);
1043                         }
1044                         else {
1045                             listeners[i] = null;
1046                             nullIndex = i;
1047                         }
1048                     }
1049                 }
1050                 finally {
1051                     _listenerReaderCount--;
1052                 }
1053                 if (0 == _listenerReaderCount) {
1054                     RemoveNullListeners(nullIndex);
1055                 }
1056             }
1057         }
1058
1059         private void RemoveNullListeners(int nullIndex) {
1060             Debug.Assert((-1 == nullIndex) || (null == listeners[nullIndex]), "non-null listener");
1061             Debug.Assert(0 == _listenerReaderCount, "0 < _listenerReaderCount");
1062             for (int i = nullIndex; 0 <= i; --i) {
1063                 if (null == listeners[i]) {
1064                     listeners.RemoveAt(i);
1065                 }
1066             }
1067         }
1068     }
1069 }