{"id":9033,"date":"2011-11-25T07:00:00","date_gmt":"2011-11-25T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2011\/11\/25\/how-to-insert-a-large-number-of-items-into-a-treeview-efficiently\/"},"modified":"2011-11-25T07:00:00","modified_gmt":"2011-11-25T07:00:00","slug":"how-to-insert-a-large-number-of-items-into-a-treeview-efficiently","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20111125-00\/?p=9033","title":{"rendered":"How to insert a large number of items into a treeview efficiently"},"content":{"rendered":"

\nJust a quick tip today.\n<\/p>\n

\nIf you need to insert a large number of items into a treeview,\nlike tens of thousands,\nthen it’s much more efficient to insert them “backwards”.\n(I’m ignoring for now the usability question of having a treeview\nthat large in the first place.)\nIn other words, instead of\n<\/p>\n

\nfor (i = 0; i < array.Count(); i++) {\n TVINSERTSTRUCT tvis;\n tvis.hParent = hParentNode;\n tvis.hInsertAfter = TVIF_LAST;\n tvis.item.mask = TVIF_TEXT;\n item.item.pszText = array[i].Text();\n TreeView_InsertItem(hwndTreeView, &tvis);\n}\n<\/pre>\n
do it this way:<\/p>\n
\nfor (i = array.Count() - 1; i >= 0; i--<\/font>) {\n TVINSERTSTRUCT tvis;\n tvis.hParent = hParentNode;\n tvis.hInsertAfter = TVIF_FIRST<\/font>;\n tvis.item.mask = TVIF_TEXT;\n item.item.pszText = array[i].Text();\n TreeView_InsertItem(hwndTreeView, &tvis);\n}\n<\/pre>\n
\nWhy is backwards-insertion faster?\n<\/p>\n
\nIt has to do with the annoying\nhInsert­After<\/code> parameter.\nTo validate that the\nhInsert­After<\/code> parameter is valid,\nthe treeview needs to verify that the\nhInsert­After<\/code> is a valid child of the\nhParent<\/code>,\nand this is done by walking the parent’s children\nlooking for a match.\nThe sooner you find the match, the faster the validation completes.\n(And if you pass\nTVI_LAST<\/code>,\nthen the treeview needs to walk to the end of the child list.)\n<\/p>\n
\nYou’d think that you could verify the parent\/child relationship\nby just doing a\nTree­View_Get­Parent(hInsert­After)<\/code>,\nbut that turns out not to be strict enough, because\nhInsert­After<\/code> might itself not be a valid parameter.\nIf hInsert­After<\/code> is a bogus value,\nthen you may crash when you try to read its Parent property.\nThat’s if you’re lucky.\nIf you’re not lucky,\nthen the random memory that\nhInsert­After<\/code> points to might look just enough\nlike a valid HTREEITEM<\/code> that you end up inserting\nthe new node after a completely bogus node,\nand now the treeview has become corrupted.\n<\/p>\n
\nSure, you got the same problem if you passed a garbage\nHTREEITEM<\/code> to\nTree­View_Get­Parent<\/code>,\nbut in that case, it’s just garbage in garbage out.\nNothing gets corrupted;\nthe application just gets a garbage result.\nBut in the case of\nTree­View_Insert­Item<\/code>,\nthe treeview is going to update its internal data structures\nbased on the garbage you passed in,\nand that means that the treeview winds up corrupted.\n<\/p>\n
\nTo ensure that the value passed in is valid,\nthe treeview checks it against the list of valid values for\nhInsert­After<\/code>.\nAnd therefore, you get better performance if the valid value\nyou pass is the one that it checks first.\n<\/p>\n
\n(As it happens, a lot<\/i> of programs pass garbage\nfor hInsert­After<\/code>,\nso this defensive validation step is absolutely necessary.)\n<\/p>\n
\nYou might say that the treeview could have a one-off optimization\nfor the special\nTVI_LAST<\/code> value by remembering the last child\nso it can be located quickly.\nThe question is whether the complexity of adding that optimization\nis worth the cost:\nAny tree rearranging function would have to update the\ncached value, and if you miss a spot,\nthen the treeview ends up corrupted.\nThat’s a pretty high-risk optimization you’re suggesting there.\n<\/p>\n
\nAnd think about it this way:\nYou’re worrying about a tree where a single node\nhas tens of thousands of children,\nsomething which (I am no longer ignoring) is a horrible user interface.\nThat’s like a list box with tens of thousands of items,\nor a dialog box with tens of thousands of checkboxes.\nYou’ll probably want to consider a better way of presenting\nthe information than in a tree view that goes on for\nhundreds of screens.\nThe treeview isn’t optimized for this case because\n\nyou don’t optimize for the case where somebody is mis-using your system<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Just a quick tip today. If you need to insert a large number of items into a treeview, like tens of thousands, then it’s much more efficient to insert them “backwards”. (I’m ignoring for now the usability question of having a treeview that large in the first place.) In other words, instead of for (i […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-9033","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Just a quick tip today. If you need to insert a large number of items into a treeview, like tens of thousands, then it’s much more efficient to insert them “backwards”. (I’m ignoring for now the usability question of having a treeview that large in the first place.) In other words, instead of for (i […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/9033","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=9033"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/9033\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=9033"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=9033"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=9033"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}