[Spice-devel] [PATCH 7/8] Store surfaces_used in a bit-array

[alexl at redhat.com]

From: Alexander Larsson <alexl at redhat.com>

This is smaller than a byte array, and allows us to skip full
blocks of 32 ids in one check.
---
 display/qxldd.h   |    2 +-
 display/res.c     |    2 +-
 display/surface.h |   55 +++++++++++++++++++++++++++++++++++++++++++---------
 3 files changed, 47 insertions(+), 12 deletions(-)

diff --git a/display/qxldd.h b/display/qxldd.h
index 7984fc8..aa20ef4 100644
--- a/display/qxldd.h
+++ b/display/qxldd.h
@@ -192,7 +192,7 @@ typedef struct DevRes {
     UINT32 num_palettes;
 
     SurfaceInfo *surfaces_info;
-    UINT8 *surfaces_used;
+    UINT32 *surfaces_used;
 
     HANDLE driver;
 #ifdef DBG
diff --git a/display/res.c b/display/res.c
index 7773e40..4569315 100644
--- a/display/res.c
+++ b/display/res.c
@@ -402,7 +402,7 @@ static void InitRes(PDev *pdev)
         PANIC(pdev, "Res dynamic allocation failed\n");
     }
 
-    pdev->Res.surfaces_used = EngAllocMem(FL_ZERO_MEMORY, sizeof(UINT8) * pdev->n_surfaces,
+    pdev->Res.surfaces_used = EngAllocMem(FL_ZERO_MEMORY, sizeof(UINT32) * ((pdev->n_surfaces + 31) / 32),
                                           ALLOC_TAG);
     if (!pdev->Res.surfaces_used) {
         PANIC(pdev, "Res surfaces_used allocation failed\n");
diff --git a/display/surface.h b/display/surface.h
index 14c67b0..2b23272 100644
--- a/display/surface.h
+++ b/display/surface.h
@@ -32,28 +32,63 @@ static _inline UINT32 GetSurfaceId(SURFOBJ *surf)
 
 static _inline void FreeSurface(PDev *pdev, UINT32 surface_id)
 {
-   pdev->Res.surfaces_used[surface_id] = 0;
+    UINT32 i, bitmask;
+
+    i = surface_id / 32;
+    bitmask = (~0x80000000) >> (surface_id % 32);
+
+    pdev->Res.surfaces_used[i] &= bitmask;
 }
 
 
 static UINT32 GetFreeSurface(PDev *pdev)
 {
-    UINT32 x;
-
-    //not effective, fix me
-    for (x = 1; x < pdev->n_surfaces; ++x) {
-        if (!pdev->Res.surfaces_used[x]) {
-            pdev->Res.surfaces_used[x] = 1;
-            return x;
+    UINT32 start = 1;
+    UINT32 bit;
+    UINT32 i, end_i;
+    UINT32 bitmask;
+    UINT32 used_mask;
+    UINT32 res = 0;
+
+    i = start / 32;
+    end_i = (pdev->n_surfaces + 31) / 32;
+    bit = start % 32;
+    bitmask = (0x80000000) >> (bit % 32);
+
+    while (i < end_i) {
+        used_mask = pdev->Res.surfaces_used[i];
+        /* Avoid checks early if no unused */
+        if (used_mask == 0xffffffff) {
+            while (bit < 32) {
+                if ((used_mask & bitmask) == 0) {
+                    res = i*32 + bit;
+                    pdev->Res.surfaces_used[i] |= bitmask;
+                    break;
+                }
+                bit++;
+                bitmask >>= 1;
+            }
         }
+        i++;
+        bit = 0;
+        bitmask = 0x80000000;
     }
 
-    return 0;
+    if (res > pdev->n_surfaces) {
+        /* Could happen in the last word if n_surfaces is not a multiple of 32 */
+        res = 0;
+    }
+
+    return res;
 }
 
 static BOOL SurfaceInUse(PDev *pdev, UINT32 id)
 {
-  return pdev->Res.surfaces_used[id];
+    UINT32 i, bitmask;
+
+    i = id / 32;
+    bitmask = 0x80000000 >> (id % 32);
+    return (pdev->Res.surfaces_used[id] & bitmask) != 0;
 }
 
 enum {
-- 
1.7.2.1