Introduction
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 ITEMDATA
.
template<class _ITEMDATA> class CRGTreeT
{
public:
CRGTreeT();
~CRGTreeT();
UINT GetItemCount() const;
UINT GetChildCount( POSITION posParent) const;
POSITION GetRootPosition() const;
POSITION GetParentPosition( POSITION pos) const;
POSITION AddHead( const _ITEMDATA *pItemData,
POSITION posParent=NULL);
POSITION AddTail( const _ITEMDATA *pItemData,
POSITION posParent=NULL);
POSITION InsertAfter( const _ITEMDATA *pItemData,
POSITION posParent=NULL,
POSITION posAfter=NULL);
void RemoveAt( POSITION pos);
void RemoveAll();
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,
BOOL bAscending=TRUE);
POSITION Find( const _ITEMDATA *pItemData,
POSITION posParent);
CompareFunc SetCompareFunc( CompareFunc func);
DeleteFunc SetDeleteFunc( DeleteFunc func, LPARAM lParam);
protected:
void RemoveChilds( POSITION pos);
void QSortA( CTreeItem **pLow, CTreeItem **pHigh);
void QSortD( CTreeItem **pLow, CTreeItem **pHigh);
private:
CTreeItem m_ItemRoot;
UINT m_nCount;
CompareFunc m_pCompareFunc;
DeleteFunc m_pDeleteFunc;
LPARAM m_lParamDeleteFunc;
};
The messages will be processed in its own window procedure. I've implemented some small functions directly, the others exist as standalone 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
:
struct TREE_MAP_STRUCT
{
HWND hwnd;
HWND hWndEdit;
WNDPROC pOldWndProc;
int nItemCount;
int nMaxWidth;
int nVScrollPos;
int nHScrollPos;
HTREEITEM hItemFirstVisible;
HTREEITEM hItemSelected;
HTREEITEM hItemEditing;
HTREEITEM hItemClicked;
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 HFONT
s. You can cache their creation by SetRedraw()
calls.
Next optimization is used in the internal GetItemVisibleIndex()
. With many items, it tries to find the items near the first visible one.
class CItemRectCache
{
public:
CItemRectCache(HWND hWnd);
~CItemRectCache();
void SetItem( RGTVITEM* pItem);
int GetItemTextWidth();
SIZE GetStateImageSize(TREE_MAP_STRUCT *ptms);
SIZE GetNormalImageSizeAndOffset(TREE_MAP_STRUCT *ptms);
protected:
bool m_bHasLinesAtRoot;
bool m_bStateImageSizeInitialized;
SIZE m_StateImageSize;
bool m_bNormalImageSizeInitialized;
SIZE m_NormalImageSize;
HWND m_hWnd;
HDC m_hDC;
HGDIOBJ m_hFont;
HGDIOBJ m_hBoldFont;
HGDIOBJ m_hOldFont;
bool m_bBoldSelected;
RGTVITEM* m_pItemSet;
}
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
TVM_SETSCROLLTIME
- Tooltip support
- Infotips
- 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 SetItem
) - 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 (?)
- With
SetRedraw(false)
before InsertItem()/TVIF_TEXT
system tree returns item's rectangle with 0-widthed text, rgtree
with computed size. System tree needs explicit SetItemText()
or SetRedraw(true)
before 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 your tree control from CRGTree
.
CYourTreeCtrl.h
#include "RGTreeCtrl.h"
class CYourTreeCtrl : public CRGTreeCtrl
change all CTreeCtrl
mentions like...
BEGIN_MESSAGE_MAP(CYourTreeCtrl, CTreeCtrl)
...to CRGTreeCtrl
into CYourTreeCtrl
.* and rebuild. Do not forget to call SetRedraw()
before and after big tree data changes.
If you will create own project for tree sources, do not forget to define RGTREECTRL_EXPORTS
there.
Finally
Generally, the control is usable. Especially, inserting/deleting many items is faster compared to the system one.
If you find corrections, improvements or add functionality, let us know to update this article. At first, we are interested in bugs (with defined situations) and absolutely the best (you are programmers) with possible solutions.
If you're interested in joining us and you don't have problems reading the sources, you're very welcome. Please contact us before your changes to avoid duplicate development.
Update History
InvalidateItemRect()
calls GetItemRect()
with FALSE
OnGetItem()/TVIF_TEXT
fix HitTest()
knows TVHT_TOLEFT
and similar flags WM_MOUSEWHEEL
handler
25 Jan 2002
InsertItem_UpdateVScrollPos()
HitTest()
vs horizontal scroll
2 Mar 2002
SetTVITEMforNotify()
DoScroll()
GetNextItem()/TVGN_LASTVISIBLE
15 Apr 2002
- Edit and scroll timers using
GetDoubleClickTime()
TVS_FULLROWSELECT
works without TVS_HASLINES
only - Drag and drop support
IsBeforeFirstVisibleItem()
23 May 2002
7 Aug 2002
NM_RCLICK
thanks to Doug Garno I_IMAGECALLBACK
thanks to Doug Garno DeleteObject(hBrush)
into OnPaint()
SetItem()
with image change cases
12 Sep 2002
WM_CONTEXTMENU
vs NM_RCLICK
's return Expand()
in SetItem()
without notify GetNextItem(NULL)
and similarly newly will return NULL
and not crash MessageBeep()
for not handled events to OnKeyDown()
- two
TVGN_DROPHILITE
items - second one for "pressed" state (but pressed rgtree
still enables by-tab switching) nmtv.itemNew
corrected to nmtv.itemOld
in 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
- no
WM_CHAR
beeps in editing thanks to Doug Garno EndEditLabelNow()
sends one TVN_ENDLABELEDIT
only thanks to Doug Garno SetTVITEMforNotify()
into OnEditLabel()
uses 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 hBoldFont
into OnPaint()
at request only and derived from WM_GETFONT
not hOldFont
17 Dec 2003
- fixed scrolling problems when inserting items to zero-sized window (
_ScrollAbsolutelyDownWhenRequired
) - new cases into
OnKeyDown()
thanks to Doug Garno
Please search article comments for actual code updates too.