I'm writing an application for exploring the registry. Therefore I need the tree control. First I used
InsertItem directly with the registry keys. Inserting an item in the SysTree is fast enough but deleting the items is very slow. I used optimizations described in Tibors article, but it wouldn't be much faster. Then I used text callback items, but the same.
For example: Adding about 50000 registry keys to system tree control needs about 6 sec, deleting these items needs about 22 sec (!) on my Thunderbird 1200.
Because each quick tree control I've found I must pay for and the free controls I've found aren't faster than the standard tree control, I decided to write my own. The tree control should work like the system tree control.
The control internally
The control data storage is based on the
template CRGTreeT<_ITEMDATA>. It's an object implementing a bi-directional linked list of elements, each containing a member of type
template<class _ITEMDATA> class CRGTreeT
UINT GetItemCount() const;
UINT GetChildCount( POSITION posParent) const;
POSITION GetRootPosition() const;
POSITION GetParentPosition( POSITION pos) const;
POSITION AddHead( const _ITEMDATA *pItemData,
POSITION AddTail( const _ITEMDATA *pItemData,
POSITION InsertAfter( const _ITEMDATA *pItemData,
void RemoveAt( POSITION pos);
POSITION GetChildPosition( POSITION posParent,
BOOL bFirst=TRUE) const;
POSITION GetNextPosition( POSITION pos) const;
POSITION GetPrevPosition( POSITION pos) const
void GetAt( POSITION pos, _ITEMDATA* pItemData) const;
_ITEMDATA* GetAt( POSITION pos);
void SetAt( POSITION pos, const _ITEMDATA* pItemData);
BOOL SortChildren( POSITION posParent,
POSITION Find( const _ITEMDATA *pItemData,
CompareFunc SetCompareFunc( CompareFunc func);
DeleteFunc SetDeleteFunc( DeleteFunc func, LPARAM lParam);
void RemoveChilds( POSITION pos);
void QSortA( CTreeItem **pLow, CTreeItem **pHigh);
void QSortD( CTreeItem **pLow, CTreeItem **pHigh);
The messages will be processed in its own window procedure. Some small functions I've implemented directly, the others exists as stand alone functions with the following form
LRESULT On[MessageName]( HWND hwnd, TREE_MAP_STRUCT *ptms,
WPARAM wParam, LPARAM lParam)
There is a data structure holding the characteristics for each tree
HWND hwnd; HWND hWndEdit; WNDPROC pOldWndProc; int nItemCount; int nMaxWidth; int nVScrollPos; int nHScrollPos; HTREEITEM hItemFirstVisible; HTREEITEM hItemSelected;
HIMAGELIST hNormalImageList; HIMAGELIST hStateImageList;
bool bRedrawFlag; _rgTree rgTree; };
For faster calculating of the item widths Tibor has written class holding repeatable used objects, especially the
HDC and the
HFONTs. You can cache their creation by
Next optimization is used in the internal
GetItemVisibleIndex(). With many items it tries to find the items near the first visible one.
void SetItem( RGTVITEM* pItem);
SIZE GetStateImageSize(TREE_MAP_STRUCT *ptms);
SIZE GetNormalImageSizeAndOffset(TREE_MAP_STRUCT *ptms);
Known to-dos and limitations
- Full(er) TreeCtrl functionality. At the moment we have only implemented cases interesting for us. The main missing cases are:
- Custom drawing
- TVM_INSERTITEM with TVI_SORT
- Tooltip support
- Keyboard notification and incremental search
- Slower sorting because the quicksort algorithm is used and an array of all items to sort must be built and after sorting the previous/next position of an item must be updated
- More straight code without duplicities and not commented parts
- More 1:1 implementation
- Are cases when hItemFirstVisible after Expand call is not the same like in system tree.
- Edit control size and position depending on horizontal scrollbar position.
- More and more intelligent done user interface optimization
- Can be sometimes more redraws than necessary.
- More searches can be optimized (see
__GetItemVisibleIndex call in
- See bInSetScrollBars usage as horror example.
- Absolutely correct code
- Now change of item's
TVIS_BOLD state not recomputes horizontal scrollbar.
- Directly defined
ID_EDIT can conflict with your dialog control id (?).
InsertItem()/TVIF_TEXT system tree returns item's rectangle with 0-widthed text, rgtree with computed size. System tree needs explicit
GetItemRect(... , true).
The demo project
I've written a demo project comparing the speed of the
CRGTreeCtrl with the standard tree control. It measures the time for inserting, sorting and deleting items.
At first you must build RGTree than TreeDlg configuration.
We spent some time searching why the release version is slower than debug in
DeleteAllItems(). You will not believe it was in the
delete pItemData->pszText call. The funny thing is all is ok when you do not run it from developer studio (why did we not find it sooner?).
How to use in your project
If you want to use it build (release) RGTree.dll. This will produce import library RGTree.lib. Include it into Project\Settings\Link\General\Object/Library modules. Derive you tree control from
class CYourTreeCtrl : public CRGTreeCtrl
CTreeCtrl mentions like
CYourTreeCtrl.* and rebuild. Do not forget call
SetRedraw() before and after big tree data changes.
If you will create own project for tree sources do not forget define
Generally the control is usable. Especially inserting/deleting many items is faster comparing to the system one.
If you find corrections, improvements or add functionality let know to update this article. At first we are interested for bugs (with defined situations) and absolutely the best (you are programmers) with possible solutions.
If you're interested to join us and you don't have problems reading the sources, you're very welcome. Please contact us before your changes to avoid duplicate development.
TVHT_TOLEFT and similar flags
25 Jan 2002:
HitTest() vs horizontal scroll
2 Mar 2002:
15 Apr 2002:
- edit and scroll timers using
TVS_FULLROWSELECT works without
- drag and drop support
23 May 2002:
7 Aug 2002:
NM_RCLICK thanks to Doug Garno
I_IMAGECALLBACK thanks to Doug Garno
SetItem() with image change cases
12 Sep 2002:
SetItem() without notify
GetNextItem(NULL) and similars newly will return NULL and not crash
MessageBeep() for not handled events to
TVGN_DROPHILITE items - second one for "pressed" state (but pressed rgtree still enables by-tab switching)
nmtv.itemNew corrected to
TVN_DELETEITEM thanks to Doug Garno
(mask | TVIS) corrected to
(mask & TVIS) in
SetTVITEMforNotify() thanks to Doug Garno
13 Sep 2002:
GetChildItem(NULL) returns root item and not
NULL thanks to Doug Garno
9 Dec 2002:
WM_CHAR beeps in editing thanks to Doug Garno
EndEditLabelNow() sends one
TVN_ENDLABELEDIT only thanks to Doug Garno
lParam instead of
ptms->hItemEditing thanks to Doug Garno
- font handling made more straight
28 Mar 2003:
- better (but still not 1:1)
MessageBeep() for not handled events to
OnKeyDown() - see article comment
OnPaint() at request only and derived from
17 Dec 2003:
- fixed scrolling problems when inserting items to zero-sized window (
- new cases into
OnKeyDown() thanks to Doug Garno
Please search article comments for actual code updates too.