BackgroundContentProvider


1   /*******************************************************************************
2    * Copyright (c) 2005, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.jface.viewers.deferred;
12  
13  import java.util.Comparator  ;
14  
15  import org.eclipse.core.runtime.IProgressMonitor;
16  import org.eclipse.core.runtime.NullProgressMonitor;
17  import org.eclipse.jface.resource.JFaceResources;
18  import org.eclipse.core.runtime.Assert;
19  import org.eclipse.jface.viewers.AcceptAllFilter;
20  import org.eclipse.jface.viewers.IFilter;
21  import org.eclipse.jface.viewers.deferred.ConcurrentTableUpdator.Range;
22  
23  /**
24   * Contains the algorithm for performing background sorting and filtering in a virtual
25   * table. This is the real implementation for <code>DeferredContentProvider</code>.
26   * However, this class will work with anything that implements <code>AbstractVirtualTable</code>
27   * rather than being tied to a <code>TableViewer</code>.
28   * 
29   * <p>
30   * This is package visiblity since it currently only needs to be used in one place,
31   * but it could potentially be made public if there was a need to use the same background
32   * sorting algorithm for something other than a TableViewer. 
33   * </p>
34   * 
35   * <p>
36   * Information flow is like this:
37   * </p>
38   * <ol>
39   * <li>IConcurrentModel sends unordered elements to BackgroundContentProvider (in a background thread)</li>
40   * <li>BackgroundContentProvider sorts, filters, and sends element/index pairs to
41   *     ConcurrentTableUpdator (in a background thread)</li>
42   * <li>ConcurrentTableUpdator batches the updates and sends them to an AbstractVirtualTable 
43   *     (in the UI thread)</li>  
44   * </ol>
45   * 
46   * <p>
47   * Internally, sorting is done using a <code>LazySortedCollection</code>. This data structure
48   * allows the content provider to locate and sort the visible range without fully sorting
49   * all elements in the table. It also supports fast cancellation, allowing the visible range
50   * to change in the middle of a sort without discarding partially-sorted information from
51   * the previous range.
52   * </p>
53   * 
54   * @since 3.1
55   */
56  /* package */ final class BackgroundContentProvider {
57      
58      /**
59       * Sorting message string
60       */
61      private static final String   SORTING = JFaceResources.getString("Sorting"); //$NON-NLS-1$
62  
63      /**
64       * Table limit. -1 if unlimited
65       */
66      private int limit = -1;
67      
68      /**
69       * Model that is currently providing input to this content provider.
70       */
71      private IConcurrentModel model;
72      
73      /**
74       * Current sort order 
75       */
76      private volatile Comparator   sortOrder;
77      
78      /**
79       * True iff the content provider has 
80       */
81      private volatile IFilter filter = AcceptAllFilter.getInstance();
82      
83      /**
84       * Queued changes
85       */
86      private ChangeQueue changeQueue = new ChangeQueue();
87      
88      /**
89       * Listener that gets callbacks from the model
90       */
91      private IConcurrentModelListener listener = new IConcurrentModelListener() {
92          /* (non-Javadoc)
93           * @see org.eclipse.jface.viewers.deferred.IConcurrentModelListener#add(java.lang.Object[])
94           */
95          public void add(Object  [] added) {
96              BackgroundContentProvider.this.add(added);
97          }
98          
99          /* (non-Javadoc)
100          * @see org.eclipse.jface.viewers.deferred.IConcurrentModelListener#remove(java.lang.Object[])
101          */
102         public void remove(Object  [] removed) {
103             BackgroundContentProvider.this.remove(removed);
104         }
105         
106         /* (non-Javadoc)
107          * @see org.eclipse.jface.viewers.deferred.IConcurrentModelListener#setContents(java.lang.Object[])
108          */
109         public void setContents(Object  [] newContents) {
110             BackgroundContentProvider.this.setContents(newContents);
111         }
112         
113         /* (non-Javadoc)
114          * @see org.eclipse.jface.viewers.deferred.IConcurrentModelListener#update(java.lang.Object[])
115          */
116         public void update(Object  [] changed) {
117             BackgroundContentProvider.this.update(changed);
118         }
119         
120     };
121 
122     /**
123      * Object that posts updates to the UI thread. Must synchronize on
124      * sortMutex when accessing. 
125      */
126     private ConcurrentTableUpdator updator;
127     
128     private IProgressMonitor sortingProgressMonitor = new NullProgressMonitor();
129     private Thread   sortThread = null;
130 
131     private volatile FastProgressReporter sortMon = new FastProgressReporter();
132 
133     private volatile Range range = new Range(0,0);
134     
135     /**
136      * Creates a new background content provider
137      *  
138      * @param table table that will receive updates
139      * @param model data source
140      * @param sortOrder initial sort order
141      */
142     public BackgroundContentProvider(AbstractVirtualTable table, 
143             IConcurrentModel model, Comparator   sortOrder) {
144         
145         updator = new ConcurrentTableUpdator(table);
146         this.model = model;
147         this.sortOrder = sortOrder;
148         model.addListener(listener);
149     }
150     
151     /**
152      * Cleans up this content provider, detaches listeners, frees up memory, etc. 
153      * Must be the last public method called on this object.
154      */
155     public void dispose() {
156         cancelSortJob();
157         updator.dispose();
158         model.removeListener(listener);
159     }
160     
161     /**
162      * Force a refresh. Asks the model to re-send its complete contents.
163      */
164     public void refresh() {
165         if (updator.isDisposed()) {
166             return;
167         }
168         model.requestUpdate(listener);
169     }
170 
171     /**
172      * Called from sortJob. Sorts the elements defined by sortStart and sortLength.
173      * Schedules a UI update when finished.
174      * 
175      * @param mon monitor where progress will be reported
176      */
177     private void doSort(IProgressMonitor mon) {        
178         
179         // Workaround for some weirdness in the Jobs framework: if you cancel a monitor
180         // for a job that has ended and reschedule that same job, it will start 
181         // the job with a monitor that is already cancelled. We can workaround this by
182         // removing all references to the progress monitor whenever the job terminates,
183         // but this would require additional synchronize blocks (which are slow) and more
184         // complexity. Instead, we just un-cancel the monitor at the start of each job. 
185         mon.setCanceled(false);
186 
187         mon.beginTask(SORTING, 100);
188         
189         // Create a LazySortedCollection
190         Comparator   order = sortOrder;
191         IFilter f = filter;
192         LazySortedCollection collection = new LazySortedCollection(order);
193         
194         // Fill it in with all existing known objects
195         Object  [] knownObjects = updator.getKnownObjects();
196         for (int i = 0; i < knownObjects.length; i++) {
197             Object   object = knownObjects[i];
198             if (object != null) {
199                 collection.add(object);
200             }
201         }
202 
203         boolean dirty = false;
204         int prevSize = knownObjects.length;
205         updator.setTotalItems(prevSize);
206         
207         // Start processing changes
208         while(true) {
209             // If the sort order has changed, build a new LazySortedCollection with
210             // the new comparator
211             if (order != sortOrder) {
212                 dirty = true;
213                 order = sortOrder;
214                 // Copy all elements from the old collection to the new one 
215                 LazySortedCollection newCollection = new LazySortedCollection(order);
216                 
217                 Object  [] items = collection.getItems(false);
218                 for (int j = 0; j < items.length && order == sortOrder; j++) {
219                     Object   item = items[j];
220                     
221                     newCollection.add(item);
222                 }
223                 
224                 // If the sort order changed again, re-loop
225                 if (order != sortOrder) {
226                     continue;
227                 }
228                 collection = newCollection;
229                 continue;
230             } 
231             
232             // If the filter has changed
233             if (f != filter) {
234                 dirty = true;
235                 f = filter;
236                 
237                 Object  [] items = collection.getItems(false);
238                 
239                 // Remove any items that don't pass the new filter
240                 for (int j = 0; j < items.length && f == filter; j++) {
241                     Object   toTest = items[j];
242                     
243                     if (!f.select(toTest)) {
244                         collection.remove(toTest);
245                     }
246                 }
247                 continue;
248             }
249         
250             // If there are pending changes, process one of them
251             if (!changeQueue.isEmpty()) {
252                 dirty = true;
253                 ChangeQueue.Change next = changeQueue.dequeue();
254                 
255                 switch(next.getType()) {
256                     case ChangeQueue.ADD: {
257                         filteredAdd(collection, next.getElements(), f);
258                         break;
259                     }
260                     case ChangeQueue.REMOVE: {
261                         Object  [] toRemove = next.getElements();
262     
263                         flush(toRemove, collection);
264                         collection.removeAll(toRemove);
265     
266                         break;
267                     }
268                     case ChangeQueue.UPDATE: {
269                         Object  [] items  = next.getElements();
270                         
271                         for (int i = 0; i < items.length; i++) {
272                             Object   item = items[i];
273                             
274                             if (collection.contains(item)) {
275                                 // TODO: write a collection.update(...) method
276                                 collection.remove(item);
277                                 collection.add(item);
278                                 updator.clear(item);                            
279                             }
280                         }
281                             
282                         break;
283                     }
284                     case ChangeQueue.SET: {
285                         Object  [] items = next.getElements();
286                         collection.clear();
287                         filteredAdd(collection, items, f);
288                             
289                         break;
290                     }
291                 }
292                 
293                 continue;
294             }
295             
296             int totalElements = collection.size();
297             if (limit != -1) {
298                 if (totalElements > limit) {
299                     totalElements = limit;
300                 }
301             }
302             
303             if (totalElements != prevSize) {
304                 prevSize = totalElements;
305                 // Send the total items to the updator ASAP -- the user may want
306                 // to scroll to a different section of the table, which would
307                 // cause our sort range to change and cause this job to get cancelled.
308                 updator.setTotalItems(totalElements);
309                 dirty = true;
310             }
311             
312             // Terminate loop
313             if (!dirty) {
314                 break;
315             }
316             
317             try {
318                 ConcurrentTableUpdator.Range updateRange = updator.getVisibleRange();
319                 sortMon = new FastProgressReporter();
320                 range = updateRange;
321                 int sortStart = updateRange.start;
322                 int sortLength = updateRange.length;
323             
324                 if (limit != -1) {
325                     collection.retainFirst(limit, sortMon);
326                 }
327 
328                 sortLength = Math.min(sortLength, totalElements - sortStart);
329                 sortLength = Math.max(sortLength, 0);
330                 
331                 Object  [] objectsOfInterest = new Object  [sortLength];
332              
333                 collection.getRange(objectsOfInterest, sortStart, true, sortMon);
334                 
335                 // Send the new elements to the table
336                 for (int i = 0; i < sortLength; i++) {
337                     Object   object = objectsOfInterest[i];
338                     updator.replace(object, sortStart + i);
339                 }
340                 
341                 objectsOfInterest = new Object  [collection.size()];
342                     
343                 collection.getFirst(objectsOfInterest, true, sortMon);
344                 
345                 // Send the new elements to the table
346                 for (int i = 0; i < totalElements; i++) {
347                     Object   object = objectsOfInterest[i];
348                     updator.replace(object, i);
349                 }
350 
351             } catch (InterruptedException   e) {
352                 continue;
353             }
354             
355             dirty = false;
356         }
357         
358         mon.done();
359     }
360 
361     /**
362      * @param collection
363      * @param toAdd
364      */
365     private static void filteredAdd(LazySortedCollection collection, Object  [] toAdd, IFilter filter) {
366         if (filter != AcceptAllFilter.getInstance()) { 
367             for (int i = 0; i < toAdd.length; i++) {
368                 Object   object = toAdd[i];
369                 
370                 if (filter.select(object)) {
371                     collection.add(object);
372                 }
373             }
374         } else {
375             collection.addAll(toAdd);
376         }
377     }
378     
379     /**
380      * Sets the sort order for this content provider
381      * 
382      * @param sorter sort order
383      */
384     public void setSortOrder(Comparator   sorter) {
385         Assert.isNotNull(sorter);
386         this.sortOrder = sorter;
387         sortMon.cancel();
388         refresh();
389     }
390     
391     /**
392      * Sets the filter for this content provider
393      * 
394      * @param toSet filter to set
395      */
396     public void setFilter(IFilter toSet) {
397         Assert.isNotNull(toSet);
398         this.filter = toSet;
399         sortMon.cancel();
400         refresh();
401     }
402     
403     /**
404      * Sets the maximum table size. Based on the current sort order,
405      * the table will be truncated if it grows beyond this size.
406      * Using a limit improves memory usage and performance, and is
407      * strongly recommended for large tables. 
408      * 
409      * @param limit maximum rows to show in the table or -1 if unbounded
410      */
411     public void setLimit(int limit) {
412         this.limit = limit;
413         refresh();
414     }
415     
416     /**
417      * Returns the maximum table size or -1 if unbounded
418      * 
419      * @return the maximum number of rows in the table or -1 if unbounded
420      */
421     public int getLimit() {
422         return limit;
423     }
424     
425     /**
426      * Checks if currently visible range has changed, and triggers and update
427      * and resort if necessary. Must be called in the UI thread, typically
428      * within a SWT.SetData callback.
429      * @param includeIndex the index that should be included in the visible range.
430      */
431     public void checkVisibleRange(int includeIndex) {
432         updator.checkVisibleRange(includeIndex);
433         ConcurrentTableUpdator.Range newRange = updator.getVisibleRange();
434         ConcurrentTableUpdator.Range oldRange = range;
435         
436         // If we're in the middle of processing an invalid range, cancel the sort
437         if (newRange.start != oldRange.start || newRange.length != oldRange.length) {
438             sortMon.cancel();
439         }
440     }
441     
442     /**
443      * This lock protects the two boolean variables sortThreadStarted and resortScheduled.
444      */
445     private Object   lock = new Object  ();
446 
447     /**
448      * true if the sort thread is running
449      */
450     private boolean sortThreadStarted = false;
451 
452     /**
453      * true if we need to sort
454      */
455     private boolean sortScheduled = false;
456     
457     private final class SortThread extends Thread   {
458         private SortThread(String   name) {
459             super(name);
460         }
461 
462         public void run() {
463             loop: while (true) {
464                 synchronized (lock) {
465                     sortScheduled = false;
466                 }
467                 try {
468                     // this is the main work
469                     doSort(sortingProgressMonitor);
470                 } catch (Exception   ex) {
471                     // ignore
472                 }
473                 synchronized (lock) {
474                     if (sortScheduled) {
475                         continue loop;
476                     }
477                     sortThreadStarted = false;
478                     break loop;
479                 }
480             }
481         }
482     }
483     
484     /**
485      * Must be called whenever the model changes. Dirties this object and triggers a sort
486      * if necessary. 
487      */
488     private void makeDirty() {
489         synchronized (lock) {
490             sortMon.cancel();
491             // request sorting
492             sortScheduled = true;
493             if (!sortThreadStarted) {
494                 sortThreadStarted = true;
495                 sortThread = new SortThread(SORTING);
496                 sortThread.setDaemon(true);
497                 sortThread.setPriority(Thread.NORM_PRIORITY - 1);
498                 sortThread.start();
499             }
500         }
501     }
502     
503     /**
504      * Cancels any sort in progress. Note that we try to use the
505      * FastProgresReporter if possible since this is more responsive than
506      * cancelling the sort job. However, it is not a problem to cancel in both
507      * ways.
508      */
509     private void cancelSortJob() {
510         sortMon.cancel();
511         sortingProgressMonitor.setCanceled(true);
512     }
513     
514     /**
515      * Called when new elements are added to the model.
516      * 
517      * @param toAdd
518      *            newly added elements
519      */
520     private void add(Object  [] toAdd) {
521         changeQueue.enqueue(ChangeQueue.ADD, toAdd);
522         makeDirty();
523     }
524     
525     /**
526      * Called with the complete contents of the model
527      * 
528      * @param contents new contents of the model
529      */
530     private void setContents(Object  [] contents) {
531         changeQueue.enqueue(ChangeQueue.SET, contents);
532         makeDirty();
533     }
534 
535     /**
536      * Called when elements are removed from the model
537      * 
538      * @param toRemove elements removed from the model
539      */
540     private void remove(Object  [] toRemove) {
541         changeQueue.enqueue(ChangeQueue.REMOVE, toRemove);
542         makeDirty();
543         refresh();
544     }
545 
546     /**
547      * Notifies the updator that the given elements have changed 
548      * 
549      * @param toFlush changed elements
550      * @param collection collection of currently-known elements
551      */
552     private void flush(Object  [] toFlush, LazySortedCollection collection) {
553         for (int i = 0; i < toFlush.length; i++) {
554             Object   item = toFlush[i];
555             
556             if (collection.contains(item)) {
557                 updator.clear(item);
558             }
559         }
560     }
561 
562 
563     /**
564      * Called when elements in the model change
565      * 
566      * @param items changed items
567      */
568     private void update(Object  [] items) {
569         changeQueue.enqueue(ChangeQueue.UPDATE, items);
570         makeDirty();
571     }
572 }
573
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags