[PATCH 3/5] dix: reduce FirstPointerChild complexity

[Peter Hutterer]

Instead of keeping a flag on each window for the devices that are in this
window, keep a local array that holds the current pointer window for each
device. Benefit: searching for the first descendant of a pointer is a simple
run through the array.

Signed-off-by: Peter Hutterer <peter.hutterer at who-t.net>
---
 dix/enterleave.c    |   64 ++++++++-------------------------------------------
 dix/window.c        |    1 -
 include/windowstr.h |    1 -
 3 files changed, 10 insertions(+), 56 deletions(-)

diff --git a/dix/enterleave.c b/dix/enterleave.c
index fbe7af4..0b15619 100644
--- a/dix/enterleave.c
+++ b/dix/enterleave.c
@@ -54,6 +54,8 @@
  * events may have a subwindow set to other than None.
  */
 
+static WindowPtr PointerWindows[MAXDEVICES];
+
 /**
  * Return TRUE if @win has a pointer within its boundaries, excluding child
  * window.
@@ -63,8 +65,8 @@ HasPointer(WindowPtr win)
 {
     int i;
 
-    for (i = 0; i < sizeof(win->enterleave); i++)
-        if (win->enterleave[i])
+    for (i = 0; i < MAXDEVICES; i++)
+        if (PointerWindows[i] == win)
             return TRUE;
 
     return FALSE;
@@ -80,57 +82,11 @@ HasPointer(WindowPtr win)
 static WindowPtr
 FirstPointerChild(WindowPtr win)
 {
-    static WindowPtr *queue = NULL;
-    static int queue_size  = 256; /* allocated size of queue */
-
-    WindowPtr child = NULL;
-    int queue_len   = 0;          /* no of elements in queue */
-    int queue_head  = 0;          /* pos of current element  */
-
-    if (!win || !win->firstChild)
-        return NULL;
-
-    if (!queue && !(queue = xcalloc(queue_size, sizeof(WindowPtr))))
-        FatalError("[dix] FirstPointerChild: OOM.\n");
-
-    queue[0] = win;
-    queue_head = 0;
-    queue_len  = 1;
-
-    while (queue_len--)
+    int i;
+    for (i = 0; i < MAXDEVICES; i++)
     {
-        if (queue[queue_head] != win && HasPointer(queue[queue_head]))
-            return queue[queue_head];
-
-        child = queue[queue_head]->firstChild;
-        /* pop children onto queue */
-        while(child)
-        {
-            queue_len++;
-            if (queue_len >= queue_size)
-            {
-                const int inc = 256;
-
-                queue = xrealloc(queue, (queue_size + inc) * sizeof(WindowPtr));
-                if (!queue)
-                    FatalError("[dix] FirstPointerChild: OOM.\n");
-
-                /* Are we wrapped around? */
-                if (queue_head + queue_len > queue_size)
-                {
-                    memmove(&queue[queue_head + inc], &queue[queue_head],
-                            (queue_size - queue_head) * sizeof(WindowPtr));
-                    queue_head += inc;
-                }
-
-                queue_size += inc;
-            }
-
-            queue[(queue_head + queue_len) % queue_size] = child;
-            child = child->nextSib;
-        }
-
-        queue_head = (queue_head + 1) % queue_size;
+        if (PointerWindows[i] && IsParent(win, PointerWindows[i]))
+            return PointerWindows[i];
     }
 
     return NULL;
@@ -143,7 +99,7 @@ FirstPointerChild(WindowPtr win)
 void
 EnterWindow(DeviceIntPtr dev, WindowPtr win, int mode)
 {
-    win->enterleave[dev->id/8] |= (1 << (dev->id % 8));
+    PointerWindows[dev->id] = win;
 }
 
 /**
@@ -152,7 +108,7 @@ EnterWindow(DeviceIntPtr dev, WindowPtr win, int mode)
 static void
 LeaveWindow(DeviceIntPtr dev, WindowPtr win, int mode)
 {
-    win->enterleave[dev->id/8] &= ~(1 << (dev->id % 8));
+    PointerWindows[dev->id] = NULL;
 }
 
 
diff --git a/dix/window.c b/dix/window.c
index 88ab5e9..ca07c96 100644
--- a/dix/window.c
+++ b/dix/window.c
@@ -300,7 +300,6 @@ SetWindowToDefaults(WindowPtr pWin)
     pWin->redirectDraw = RedirectDrawNone;
     pWin->forcedBG = FALSE;
 
-    memset(pWin->enterleave, 0, sizeof(pWin->enterleave));
     memset(pWin->focusinout, 0, sizeof(pWin->focusinout));
 
 #ifdef ROOTLESS
diff --git a/include/windowstr.h b/include/windowstr.h
index b39b351..9f86e2c 100644
--- a/include/windowstr.h
+++ b/include/windowstr.h
@@ -183,7 +183,6 @@ typedef struct _Window {
      * FocusIn/Out events for multiple pointers/keyboards. Each device ID
      * corresponds to one bit. If set, the device is in the window/has focus.
      */
-    char                enterleave[(MAXDEVICES + 7)/8];
     char                focusinout[(MAXDEVICES + 7)/8];
 } WindowRec;
 
-- 
1.6.0.6