[PATCH 4/4] user32/listbox: Implement LBS_NODATA for multi-selection listboxes

[Gabriel Ivăncescu]

Use a byte array to store selection state of items, since we don't need any
other data for LBS_NODATA multi-selection listboxes. This improves memory
usage dramatically for large lists, and performance boosts are nice too.

Signed-off-by: Gabriel Ivăncescu 
---
 dlls/user32/listbox.c | 48 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 41 insertions(+), 7 deletions(-)

diff --git a/dlls/user32/listbox.c b/dlls/user32/listbox.c
index 0e9f97c..cc06238 100644
--- a/dlls/user32/listbox.c
+++ b/dlls/user32/listbox.c
@@ -17,8 +17,6 @@
  * License along with this library; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  *
- * TODO:
- *    - LBS_NODATA for multi-selection listboxes
  */

#include <string.h>
@@ -122,6 +120,15 @@ static TIMER_DIRECTION LISTBOX_Timer = LB_TIMER_NONE;

static LRESULT LISTBOX_GetItemRect( const LB_DESCR *descr, INT index, RECT *rect );

+/*
+   Resize the item storage array if needed.
+
+   For single-selection LBS_NODATA listboxes, no storage is allocated,
+   and thus descr->items will always be NULL.
+
+   For multi-selection LBS_NODATA listboxes, one byte per item is stored
+   for the item's selection state, instead of the usual LB_ITEMDATA.
+*/
 static BOOL resize_storage(LB_DESCR *descr, UINT items_size)
 {
     LB_ITEMDATA *items;
@@ -132,7 +139,10 @@ static BOOL resize_storage(LB_DESCR *descr, UINT items_size)
         items_size = (items_size + LB_ARRAY_GRANULARITY - 1) & ~(LB_ARRAY_GRANULARITY - 1);
         if ((descr->style & (LBS_NODATA | LBS_MULTIPLESEL | LBS_EXTENDEDSEL)) != LBS_NODATA)
         {
-            items = heap_realloc(descr->items, items_size * sizeof(LB_ITEMDATA));
+            size_t size = items_size;
+            if (!(descr->style & LBS_NODATA)) size *= sizeof(LB_ITEMDATA);
+
+            items = heap_realloc(descr->items, size);
             if (!items)
             {
                 SEND_NOTIFICATION(descr, LBN_ERRSPACE);
@@ -145,8 +155,7 @@ static BOOL resize_storage(LB_DESCR *descr, UINT items_size)

if ((descr->style & LBS_NODATA) && descr->items && items_size > descr->nb_items)
     {
-        memset(&descr->items[descr->nb_items], 0,
-               (items_size - descr->nb_items) * sizeof(LB_ITEMDATA));
+        memset((BYTE*)descr->items + descr->nb_items, 0, items_size - descr->nb_items);
     }
     return TRUE;
 }
@@ -175,13 +184,21 @@ static BOOL is_item_selected( const LB_DESCR *descr, UINT index )
 {
     if (!(descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL)))
         return index == descr->selected_item;
-    return descr->items[index].selected;
+    if (descr->style & LBS_NODATA)
+        return ((BYTE*)descr->items)[index];
+    else
+        return descr->items[index].selected;
 }

static void set_item_selected_state(LB_DESCR *descr, UINT index, BOOL state)
 {
     if (descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL))
-        descr->items[index].selected = state;
+    {
+        if (descr->style & LBS_NODATA)
+            ((BYTE*)descr->items)[index] = state;
+        else
+            descr->items[index].selected = state;
+    }
 }

static void insert_item_data(LB_DESCR *descr, UINT index, WCHAR *str, ULONG_PTR data)
@@ -189,6 +206,15 @@ static void insert_item_data(LB_DESCR *descr, UINT index, WCHAR *str, ULONG_PTR
     LB_ITEMDATA *item;

if (!descr->items) return;
+    if (descr->style & LBS_NODATA)
+    {
+        BYTE *item = (BYTE*)descr->items + index;
+
+        if (index < descr->nb_items)
+            memmove(item + 1, item, descr->nb_items - index);
+        *item = FALSE;
+        return;
+    }

item = descr->items + index;
     if (index < descr->nb_items)
@@ -205,6 +231,14 @@ static void remove_item_data(LB_DESCR *descr, UINT index)
     LB_ITEMDATA *item;

if (!descr->items) return;
+    if (descr->style & LBS_NODATA)
+    {
+        BYTE *item = (BYTE*)descr->items + index;
+
+        if (index < descr->nb_items)
+            memmove(item, item + 1, descr->nb_items - index);
+        return;
+    }

item = descr->items + index;
     if (index < descr->nb_items)