Array-index based devPrivates implementation.

diff --git a/dix/privates.c b/dix/privates.c
index efb3204..ca03317 100644
--- a/dix/privates.c
+++ b/dix/privates.c
@@ -40,9 +40,8 @@ from The Open Group.
 #include "inputstr.h"
 
 struct _Private {
-    DevPrivateKey      key;
-    pointer            value;
-    struct _Private    *next;
+    int state;
+    pointer value;
 };
 
 typedef struct _PrivateDesc {
@@ -50,22 +49,36 @@ typedef struct _PrivateDesc {
     unsigned size;
     CallbackListPtr initfuncs;
     CallbackListPtr deletefuncs;
-    struct _PrivateDesc *next;
 } PrivateDescRec;
 
+#define PRIV_MAX 256
+#define PRIV_STEP 16
+
 /* list of all allocated privates */
-static PrivateDescRec *items = NULL;
+static PrivateDescRec items[PRIV_MAX];
+static int nextPriv;
 
-static _X_INLINE PrivateDescRec *
+static PrivateDescRec *
 findItem(const DevPrivateKey key)
 {
-    PrivateDescRec *item = items;
-    while (item) {
-	if (item->key == key)
-	    return item;
-	item = item->next;
+    if (!*key) {
+	if (nextPriv >= PRIV_MAX)
+	    return NULL;
+
+	items[nextPriv].key = key;
+	*key = nextPriv;
+	nextPriv++;
     }
-    return NULL;
+
+    return items + *key;
+}
+
+static _X_INLINE int
+privateExists(PrivateRec **privates, const DevPrivateKey key)
+{
+    return *key && *privates &&
+	(*privates)[0].state > *key &&
+	(*privates)[*key].state;
 }
 
 /*
@@ -75,21 +88,10 @@ _X_EXPORT int
 dixRequestPrivate(const DevPrivateKey key, unsigned size)
 {
     PrivateDescRec *item = findItem(key);
-    if (item) {
-	if (size > item->size)
-	    item->size = size;
-    } else {
-	item = (PrivateDescRec *)xalloc(sizeof(PrivateDescRec));
-	if (!item)
-	    return FALSE;
-	memset(item, 0, sizeof(PrivateDescRec));
-
-	/* add privates descriptor */
-	item->key = key;
+    if (!item)
+	return FALSE;
+    if (size > item->size)
 	item->size = size;
-	item->next = items;
-	items = item;
-    }
     return TRUE;
 }
 
@@ -100,25 +102,52 @@ _X_EXPORT pointer *
 dixAllocatePrivate(PrivateRec **privates, const DevPrivateKey key)
 {
     PrivateDescRec *item = findItem(key);
+    PrivateCallbackRec calldata;
     PrivateRec *ptr;
-    unsigned size = sizeof(PrivateRec);
-    
-    if (item)
-	size += item->size;
+    pointer value;
+    int oldsize, newsize;
+
+    newsize = (*key / PRIV_STEP + 1) * PRIV_STEP;
 
-    ptr = (PrivateRec *)xcalloc(size, 1);
-    if (!ptr)
+    /* resize or init privates array */
+    if (!item)
 	return NULL;
-    ptr->key = key;
-    ptr->value = (size > sizeof(PrivateRec)) ? (ptr + 1) : NULL;
-    ptr->next = *privates;
-    *privates = ptr;
-
-    /* call any init funcs and return */
-    if (item) {
-	PrivateCallbackRec calldata = { key, &ptr->value };
-	CallCallbacks(&item->initfuncs, &calldata);
+
+    /* initialize privates array if necessary */
+    if (!*privates) {
+	ptr = xcalloc(newsize, sizeof(*ptr));
+	if (!ptr)
+	    return NULL;
+	*privates = ptr;
+	(*privates)[0].state = newsize;
+    }
+
+    oldsize = (*privates)[0].state;
+
+    /* resize privates array if necessary */
+    if (*key >= oldsize) {
+	ptr = xrealloc(*privates, newsize * sizeof(*ptr));
+	if (!ptr)
+	    return NULL;
+	memset(ptr + oldsize, 0, (newsize - oldsize) * sizeof(*ptr));
+	*privates = ptr;
+	(*privates)[0].state = newsize;
+    }
+
+    /* initialize slot */
+    ptr = *privates + *key;
+    ptr->state = 1;
+    if (item->size) {
+	value = xcalloc(item->size, 1);
+	if (!value)
+	    return NULL;
+	ptr->value = value;
     }
+
+    calldata.key = key;
+    calldata.value = &ptr->value;
+    CallCallbacks(&item->initfuncs, &calldata);
+
     return &ptr->value;
 }
 
@@ -128,14 +157,10 @@ dixAllocatePrivate(PrivateRec **privates, const DevPrivateKey key)
 _X_EXPORT pointer
 dixLookupPrivate(PrivateRec **privates, const DevPrivateKey key)
 {
-    PrivateRec *rec = *privates;
     pointer *ptr;
 
-    while (rec) {
-	if (rec->key == key)
-	    return rec->value;
-	rec = rec->next;
-    }
+    if (privateExists(privates, key))
+	return (*privates)[*key].value;
 
     ptr = dixAllocatePrivate(privates, key);
     return ptr ? *ptr : NULL;
@@ -147,13 +172,8 @@ dixLookupPrivate(PrivateRec **privates, const DevPrivateKey key)
 _X_EXPORT pointer *
 dixLookupPrivateAddr(PrivateRec **privates, const DevPrivateKey key)
 {
-    PrivateRec *rec = *privates;
-
-    while (rec) {
-	if (rec->key == key)
-	    return &rec->value;
-	rec = rec->next;
-    }
+    if (privateExists(privates, key))
+	return &(*privates)[*key].value;
 
     return dixAllocatePrivate(privates, key);
 }
@@ -164,16 +184,10 @@ dixLookupPrivateAddr(PrivateRec **privates, const DevPrivateKey key)
 _X_EXPORT int
 dixSetPrivate(PrivateRec **privates, const DevPrivateKey key, pointer val)
 {
-    PrivateRec *rec;
-
  top:
-    rec = *privates;
-    while (rec) {
-	if (rec->key == key) {
-	    rec->value = val;
-	    return TRUE;
-	}
-	rec = rec->next;
+    if (privateExists(privates, key)) {
+	(*privates)[*key].value = val;
+	return TRUE;
     }
 
     if (!dixAllocatePrivate(privates, key))
@@ -187,27 +201,23 @@ dixSetPrivate(PrivateRec **privates, const DevPrivateKey key, pointer val)
 _X_EXPORT void
 dixFreePrivates(PrivateRec *privates)
 {
-    PrivateRec *ptr, *next;
-    PrivateDescRec *item;
+    int i;
     PrivateCallbackRec calldata;
 
-    /* first pass calls the delete callbacks */
-    for (ptr = privates; ptr; ptr = ptr->next) {
-	item = findItem(ptr->key);
-	if (item) {
-	    calldata.key = ptr->key;
-	    calldata.value = &ptr->value;
-	    CallCallbacks(&item->deletefuncs, &calldata);
-	}
-    }
-	
-    /* second pass frees the memory */
-    ptr = privates;
-    while (ptr) {
-	next = ptr->next;
-	xfree(ptr);
-	ptr = next;
-    }
+    if (privates)
+	for (i = 1; i < privates->state; i++)
+	    if (privates[i].state) {
+		/* call the delete callbacks */
+		calldata.key = items[i].key;
+		calldata.value = &privates[i].value;
+		CallCallbacks(&items[i].deletefuncs, &calldata);
+
+		/* free pre-allocated memory */
+		if (items[i].size)
+		    xfree(privates[i].value);
+	    }
+
+    xfree(privates);
 }
 
 /*
@@ -218,11 +228,9 @@ dixRegisterPrivateInitFunc(const DevPrivateKey key,
 			   CallbackProcPtr callback, pointer data)
 {
     PrivateDescRec *item = findItem(key);
-    if (!item) {
-	if (!dixRequestPrivate(key, 0))
-	    return FALSE;
-	item = findItem(key);
-    }
+    if (!item)
+	return FALSE;
+
     return AddCallback(&item->initfuncs, callback, data);
 }
 
@@ -231,11 +239,9 @@ dixRegisterPrivateDeleteFunc(const DevPrivateKey key,
 			     CallbackProcPtr callback, pointer data)
 {
     PrivateDescRec *item = findItem(key);
-    if (!item) {
-	if (!dixRequestPrivate(key, 0))
-	    return FALSE;
-	item = findItem(key);
-    }
+    if (!item)
+	return FALSE;
+
     return AddCallback(&item->deletefuncs, callback, data);
 }
 
@@ -292,16 +298,17 @@ dixLookupPrivateOffset(RESTYPE type)
 int
 dixResetPrivates(void)
 {
-    PrivateDescRec *next;
-
-    /* reset internal structures */
-    while (items) {
-	next = items->next;
-	DeleteCallbackList(&items->initfuncs);
-	DeleteCallbackList(&items->deletefuncs);
-	xfree(items);
-	items = next;
+    int i;
+
+    /* reset private descriptors */
+    for (i = 1; i < nextPriv; i++) {
+	*items[i].key = 0;
+	DeleteCallbackList(&items[i].initfuncs);
+	DeleteCallbackList(&items[i].deletefuncs);
     }
+    nextPriv = 1;
+
+    /* reset offsets */
     if (offsets)
 	xfree(offsets);
     offsetsSize = sizeof(offsetDefaults);
diff --git a/include/privates.h b/include/privates.h
index 98d893c..e3fa83c 100644
--- a/include/privates.h
+++ b/include/privates.h
@@ -19,7 +19,7 @@ CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  * STUFF FOR PRIVATES
  *****************************************************************/
 
-typedef void *DevPrivateKey;
+typedef int *DevPrivateKey;
 struct _Private;
 typedef struct _Private PrivateRec;