This is the final part of my series on instant searching and filtering using C#. The only further issue that I wanted to cover was efficiently using a ListView when the items will change so often.
ListViews already have the concept of a virtual mode, where the consumer of the class must supply the items that are displayed.
When the VirtualMode property is set to true, you also need to set the VirtualListSize property to tell the control how many items it needs to think it has.
With this simple starting point, we can have something like the following:
1: _listControl.VirtualMode = true;
2: _listControl.RetrieveVirtualItem +=
3: new RetrieveVirtualItemEventHandler(list_RetrieveVirtualItem);
and list_RetrieveVirtualItem could look like this:
1: void list_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
3: e.Item = new ListViewItem();
4: e.Item.Text = "Item Text Here";
Using this, it would be fairly easy to hook up our filtered results and away we go. But we have a few problems:
- We don’t want to generate a new ListViewItem every time the list control asks us for one. This is extremely wasteful–thousands of objects would be springing to life and dying constantly, which is a very inefficient use of the garbage collector.
- On the other hand, we don’t want to cache a ListViewItem object for every single line of text that was indexed. Only a few of them will be on the screen at a time, and we’ve already cached the text, so we should use that.
Therefore, we need a way to efficiently cache a limited number of ListViewItem objects and use them as necessary, updating their Text and Tag properties as necessary.
With that introduction, let’s get into the code.
Our own ListView
First things first: there’s a bug in the .Net framework that impacts virtual mode on ListView. So let’s derive our own to resolve it:
1: class QuickList : System.Windows.Forms.ListView
3: /// <summary>
4: /// This is needed to fix a bug in the framework
5: /// </summary>
6: public new int VirtualListSize
10: return base.VirtualListSize;
14: if (Items.Count > 0)
18: base.VirtualListSize = value;
That’s all there is to that. If you would like more information about the bug, Shahar Prish wrote up an excellent description and workarounds.
With that out of the way, most of the action we’re concerned with will take place in a separate class, which I’ll call…
This controller class is responsible for coordinating the filter text, filtered results, and their display in the list control. In my own use of these concepts, I’ve further factored out the filtering mechanism to be outside of this controller, but in this sample it’s better to combine it all for ease of understanding.
So how will this work? We want a cache of only the items that will be displayed. Unfortunately, the ListView control is going to ask us for item 30,775 for example, if we’re scrolled down a huge list. We don’t want to cache 30,775 items when only the surrounding 20 items are displayed. Fortunately, it’s easy to track a minimal number of items if we know the first visible index
Here are the fields and properties we’ll need:
1: class QuickListController
3: private int _topIndex = -1;
4: private int _bottomIndex = -1;
5: private IIndexer<string> _indexer;
6: private IList<string> _allLines;
7: private IList<string> _currentResults;
8: private QuickList _listControl;
9: List<ListViewItem> _itemCache = new List<ListViewItem>();
10: private string _filter;
12: #region Properties
13: public IList<string> CurrentResults
17: return _currentResults;
20: public string FilterText
24: return _filter;
28: _filter = value;
31: public IIndexer<string> Indexer
35: return _indexer;
39: _indexer = value;
42: public IList<string> AllLines
46: return _allLines;
50: _allLines = value;
54: //methods, etc.
Ok, lots of boring code. We track the top and bottom indexes of the visible items, we store our indexer, a list of all the results (for when no text is entered–no point in searching for nothing). _currentResults will point to either _allLines or the actual results. _itemCache is a list of ListViewItem objects that will serve as our cache. And, of course, we need the text we want to filter on.
You’ll notice that the filtered results are now strings instead of bools. In previous articles, we didn’t care about the actual results–just a count of them. Now, we need to display them, so the filtered items are the same as the keys–the lines of the text in a file.
Construction is likewise straightforward:
1: public QuickListController(QuickList list)
3: _listControl = list;
4: _listControl.VirtualMode = true;
5: _listControl.CacheVirtualItems +=
6: new CacheVirtualItemsEventHandler(list_CacheVirtualItems);
7: _listControl.RetrieveVirtualItem +=
8: new RetrieveVirtualItemEventHandler(list_RetrieveVirtualItem);
Our controller requires an instance of a QuickList object, which it then sets to virtual mode and listens for two events. The first, CacheVirtualItems, is triggered when the ListView needs a new range of objects. It gives us an opportunity to see what the new top and bottom will be and update our cache accordingly.
The RetrieveVirtualItem event is called when the ListView needs to get the item to display. As we’ll see below, handling both of these events is fairly straightforward.
1: void list_CacheVirtualItems(object sender, CacheVirtualItemsEventArgs e)
3: _topIndex = e.StartIndex;
4: _bottomIndex = e.EndIndex;
6: int sizeNeeded = _bottomIndex - _topIndex + 2;//extra 2
7: int toCreate = sizeNeeded - _itemCache.Count;
8: if (toCreate > 0)
10: if (_itemCache.Capacity < sizeNeeded)
12: _itemCache.Capacity += toCreate;
14: for (int i = 0; i < toCreate; i++)
16: _itemCache.Add(new ListViewItem());
We save the top and bottom indexes (we actually never use the bottom index), and we then calculate how many total items we need, how many new ones we need to create, and then create new ones if necessary.
You’ll notice that there is no mechanism for removing items from the cache. As we know, another name for cache with a bad (no) removal policy is a memory leak, but since the size of this cache is limited by screen characteristics, and in the most dire circumstance shouldn’t be more than a few hundred, we’ll let it slide (just this once).
1: void list_RetrieveVirtualItem(object sender, RetrieveVirtualItemEventArgs e)
3: if (e.ItemIndex < _topIndex)
5: //should never get here
7: _topIndex = e.ItemIndex;
10: e.Item = GetListViewItem(e.ItemIndex, _topIndex);
You’ll notice that if block shouldn’t ever be called, but during debugging I did have an instance where that was the case. It may have been a bug that has since been fixed, but I left it in for safety.
The actual work is done another function:
1: private ListViewItem GetListViewItem(int itemIndex, int topIndex)
3: if (itemIndex < 0 || topIndex < 0)
5: return null;
7: int cacheIndex = itemIndex - topIndex;
9: Debug.Assert(cacheIndex < _itemCache.Count);
10: ListViewItem item = _itemCache[cacheIndex];
11: item.Text = _currentResults[itemIndex];
12: //could set tag if you have more complex objects
13: //item.Tag = _currentResults[itemIndex];
14: return item;
Now that you understand how this is working, this function is really simple. Again, we do a simple sanity check. We calculate the index into our cache, which is simply the offset from the top index. After retrieving the pre-created item, we set its text (you could also set the item’s tag, color, or any other property here).
Now, some of you are wondering, “but wait, where do you set the VirtualListSize property?” Yes, that is rather important, isn’t it? How is the ListView control supposed to know how many items to ask for? For that matter, where is the actual filtering done?
We have one more function, this one a public interface to the class’s consumer:
1: public void RefreshList()
3: if (string.IsNullOrEmpty(_filter))
5: _currentResults = _allLines;
9: _currentResults = _indexer.Lookup(_filter);
11: _listControl.VirtualListSize = _currentResults.Count;
If the filter text is empty, we set our current results to the full set of lines. Otherwise, run the filter. Then we set our control’s virtual size to the number of results.
If you’ve struggled this far, congratulations. If you find anything in any of these articles useful, please leave a comment and let me know! If you find bugs or problems with my approach, I’d love to hear about better ways of accomplishing things.
The project download contains a GUI that hooks up these classes to an easy-to-use interface.
Also, if you’ve found this useful, please Buy me a Lego!
Download the project. (run the GuiSearch project–I changed TestSearch to a library file)
Download Les Misérables for testing.
Check out my latest book, the essential, in-depth guide to performance for all .NET developers:
Writing High-Performance.NET Code, 2nd Edition by Ben Watson. Available for pre-order: