Initial revision

4 files changed, 2258 insertions, 0 deletions

diff --git a/libdrm/xf86drm.c b/libdrm/xf86drm.c
new file mode 100644
index 00000000..50b421af
--- /dev/null
+++ b/libdrm/xf86drm.c
@@ -0,0 +1,1114 @@
+/* xf86drm.c -- User-level interface to DRM device
+ * Created: Tue Jan  5 08:16:21 1999 by faith@precisioninsight.com
+ * Revised: Fri Jun 18 09:52:23 1999 by faith@precisioninsight.com
+ *
+ * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ * 
+ * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drm.c,v 1.41 1999/06/21 14:31:20 faith Exp $
+ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drm.c,v 1.3 1999/06/27 14:08:19 dawes Exp $
+ * 
+ */
+
+#ifdef XFree86Server
+# include "xf86.h"
+# include "xf86_OSproc.h"
+# include "xf86_ansic.h"
+# include "xf86Priv.h"
+# define _DRM_MALLOC xalloc
+# define _DRM_FREE   xfree
+# ifndef XFree86LOADER
+#  include <sys/stat.h>
+#  include <sys/mman.h>
+# endif
+#else
+# include <stdio.h>
+# include <stdlib.h>
+# include <unistd.h>
+# include <string.h>
+# include <ctype.h>
+# include <fcntl.h>
+# include <errno.h>
+# include <signal.h>
+# include <sys/types.h>
+# include <sys/stat.h>
+# include <sys/ioctl.h>
+# include <sys/mman.h>
+# include <sys/time.h>
+# ifdef DRM_USE_MALLOC
+#  define _DRM_MALLOC malloc
+#  define _DRM_FREE   free
+extern int xf86InstallSIGIOHandler(int fd, void (*f)(int));
+extern int xf86RemoveSIGIOHandler(int fd);
+# else
+#  include <Xlibint.h>
+#  define _DRM_MALLOC Xmalloc
+#  define _DRM_FREE   Xfree
+# endif
+#endif
+
+/* Not all systems have MAP_FAILED defined */
+#ifndef MAP_FAILED
+#define MAP_FAILED ((void *)-1)
+#endif
+
+#include <sys/sysmacros.h>	/* for makedev() */
+#include "xf86drm.h"
+#include "drm.h"
+
+static void *drmHashTable = NULL; /* Context switch callbacks */
+
+typedef struct drmHashEntry {
+    int      fd;
+    void     (*f)(int, void *, void *);
+    void     *tagTable;
+} drmHashEntry;
+
+void *drmMalloc(int size)
+{
+    void *pt;
+    if ((pt = _DRM_MALLOC(size))) memset(pt, 0, size);
+    return pt;
+}
+
+void drmFree(void *pt)
+{
+    if (pt) _DRM_FREE(pt);
+}
+
+static char *drmStrdup(const char *s)
+{
+    return s ? strdup(s) : NULL;
+}
+
+
+/* drm_lookup searches file for a line tagged with name, and returns the
+   value for that tag.  If busid is NULL, the file format is that used for
+   /proc/devices and /proc/misc, or the first part of /proc/drm/devices:
+ 
+       <value> <whitespace> <tag>
+
+   If the busid is non-NULL, the file format is the extended format used
+   for /proc/drm/devices:
+
+       <value> <whitespace> <name> <whitespace> <busid>
+
+   If both name and busid are non-NULL, both must match.  If either is
+   NULL, then the other is matched.
+*/
+
+static int drm_lookup(const char *file, const char *name, const char *busid)
+{
+    FILE *str;
+    char buf[128];
+    char *pt;
+    int  name_match;
+    int  busid_match;
+    char *namept     = NULL;
+    char *busidpt    = NULL;
+
+    if (!(str = fopen(file, "r"))) return DRM_ERR_NO_DEVICE;
+    while (fgets(buf, sizeof(buf)-1, str)) {
+	buf[sizeof(buf)-1] = '\0';
+	for (pt = buf; *pt && isspace(*pt); ++pt);  /* skip whitespace */
+	for (; *pt && !isspace(*pt); ++pt);         /* next space or null */
+	if (isspace(pt[0]) && pt[1]) {
+	    pt++;
+	    for (; *pt && isspace(*pt); ++pt);      /* skip whitespace */
+	    namept = pt;
+	    for (; *pt && !isspace(*pt); ++pt);	    /* next space or null */
+	    if (isspace(pt[0]) && pt[1]) {          /* busid present */
+		*pt = '\0';		            /* proper termination */
+		pt++;
+		for (; *pt && isspace(*pt); ++pt);  /* skip whitespace */
+		busidpt = pt;
+		for (; *pt && !isspace(*pt); ++pt); /* next space or null */
+	    }
+	    *pt = '\0';		                    /* proper termination */
+	    name_match  = name ? 0 : 1;  /* match if we don't care */
+	    busid_match = busid ? 0 : 1; /* match if we don't care */
+	    if (name && namept && !strcmp(name, namept)) ++name_match;
+	    if (busid && busidpt && !strcmp(busid, busidpt)) ++busid_match;
+	    if (name_match && busid_match) {
+		fclose(str);
+		return atoi(buf); /* stops at whitespace */
+	    }
+	}
+    }
+    fclose(str);
+    return DRM_ERR_NO_DEVICE;
+}
+
+static unsigned long drmGetKeyFromFd(int fd)
+{
+#ifdef XFree86LOADER
+    struct xf86stat st;
+#else
+    struct stat     st;
+#endif
+
+    st.st_rdev = 0;
+    fstat(fd, &st);
+    return st.st_rdev;
+}
+
+static drmHashEntry *drmGetEntry(int fd)
+{
+    unsigned long key = drmGetKeyFromFd(fd);
+    void          *value;
+    drmHashEntry  *entry;
+
+    if (!drmHashTable) drmHashTable = drmHashCreate();
+
+    if (drmHashLookup(drmHashTable, key, &value)) {
+	entry           = drmMalloc(sizeof(*entry));
+	entry->fd       = fd;
+	entry->f        = NULL;
+	entry->tagTable = drmHashCreate();
+	drmHashInsert(drmHashTable, key, entry);
+    } else {
+	entry = value;
+    }
+    return entry;
+}
+
+/* drm_open is used to open the /dev/drm device */
+
+static int drm_open(const char *file)
+{
+    int fd = open(file, O_RDWR, 0);
+
+    if (fd >= 0) return fd;
+    return -errno;
+}
+
+/* drmAvailable looks for /proc/drm, and returns 1 if it is present. */
+
+int drmAvailable(void)
+{
+    if (!access(DRM_PROC_DRM, R_OK)) return 1;
+    return 0;
+}
+
+/* drmGetMajor tries to find the major device number for /dev/drm by
+   searching /proc/devices.  A negative value is returned on error. */
+
+static int drmGetMajor(void)
+{
+    int major;
+
+    if (!drmAvailable()) return DRM_ERR_NO_DEVICE;
+    
+    if ((major = drm_lookup(DRM_PROC_DEVICES, DRM_NAME, NULL)) >= 0)
+	return major;
+    
+    return DRM_ERR_NO_DEVICE;
+}
+
+/* drmGetMinor tries to find the minor device number for name by looking in
+   /proc/drm/devices.  A negative value is retruned on error. */
+
+static int drmGetMinor(const char *name, const char *busid)
+{
+    int  minor;
+    char buf[128];
+     
+    if (!drmAvailable()) return DRM_ERR_NO_DEVICE;
+
+    sprintf(buf, "/proc/%s/%s", DRM_NAME, DRM_DEVICES);
+    
+    if ((minor = drm_lookup(buf, name, busid))) return minor;
+    return 0;
+}
+
+
+/* drmOpen looks up the specified name and/or busid in /proc/drm/devices,
+   and opens the device found.  The entry in /dev is created if necessary
+   (and if root).  A file descriptor is returned.  On error, the return
+   value is negative. */
+
+static int drmOpen(const char *name, const char *busid)
+{
+#ifdef XFree86LOADER
+    struct xf86stat st;
+#else
+    struct stat     st;
+#endif
+    char            path[128];
+    int             major;
+    int             minor;
+    dev_t           dev;
+    
+    if (!drmAvailable())                       return DRM_ERR_NO_DEVICE;
+    if ((major = drmGetMajor()) < 0)           return major;
+    if ((minor = drmGetMinor(name,busid)) < 0) return minor;
+    dev = makedev(major, minor);
+
+    if (!minor) {
+	sprintf(path, "/dev/%s", DRM_NAME );
+    } else {
+	sprintf(path, "/dev/%s%d", DRM_NAME, minor-1 );
+    }
+
+				/* Check device major/minor for match */
+    if (!access(path, F_OK)) {
+	if (stat(path, &st))   return DRM_ERR_NO_ACCESS;
+	if (st.st_rdev == dev) {
+#if defined(XFree86Server)
+	    chmod(path,
+		  xf86ConfigDRI.mode  ? xf86ConfigDRI.mode : DRM_DEV_MODE);
+	    chown(path, DRM_DEV_UID,
+		  xf86ConfigDRI.group ? xf86ConfigDRI.group : DRM_DEV_GID);
+#endif
+#if defined(DRM_USE_MALLOC)
+	    chmod(path, DRM_DEV_MODE);
+	    chown(path, DRM_DEV_UID, DRM_DEV_GID);
+#endif
+	    return drm_open(path);
+	}
+    }
+
+				/* Doesn't exist or match failed, so we
+                                   have to be root to create it. */
+    if (geteuid()) return DRM_ERR_NOT_ROOT;
+    remove(path);
+    if (mknod(path, S_IFCHR | DRM_DEV_MODE, dev)) {
+	remove(path);
+	return DRM_ERR_NOT_ROOT;
+    }
+#if defined(XFree86Server)
+    chmod(path, xf86ConfigDRI.mode ? xf86ConfigDRI.mode : DRM_DEV_MODE);
+    chown(path, DRM_DEV_UID,
+	  xf86ConfigDRI.group ? xf86ConfigDRI.group : DRM_DEV_GID);
+#endif
+#if defined(DRM_USE_MALLOC)
+    chmod(path, DRM_DEV_MODE);
+    chown(path, DRM_DEV_UID, DRM_DEV_GID);
+#endif
+    return drm_open(path);
+}
+
+/* drmOpenDRM returns a file descriptor for the main /dev/drm control
+   device.  The entry in /dev is created if necessary (and if root).  A
+   file descriptor is returned.  On error, the return value is negative. */
+
+int drmOpenDRM(void)
+{
+    return drmOpen(DRM_NAME, NULL);
+}
+
+
+/* drmClose closes the file descriptor returned from drmOpen. */
+   
+int drmCloseDRM(int fd)
+{
+    return close(fd);
+}
+
+void drmFreeVersion(drmVersionPtr v)
+{
+    if (!v) return;
+    if (v->name) drmFree(v->name);
+    if (v->date) drmFree(v->date);
+    if (v->desc) drmFree(v->desc);
+    drmFree(v);
+}
+
+static void drmFreeKernelVersion(drm_version_t *v)
+{
+    if (!v) return;
+    if (v->name) drmFree(v->name);
+    if (v->date) drmFree(v->date);
+    if (v->desc) drmFree(v->desc);
+    drmFree(v);
+}
+
+static void drmCopyVersion(drmVersionPtr d, drm_version_t *s)
+{
+    d->version_major      = s->version_major;
+    d->version_minor      = s->version_minor;
+    d->version_patchlevel = s->version_patchlevel;
+    d->name_len           = s->name_len;
+    d->name               = drmStrdup(s->name);
+    d->date_len           = s->date_len;
+    d->date               = drmStrdup(s->date);
+    d->desc_len           = s->desc_len;
+    d->desc               = drmStrdup(s->desc);
+}
+
+/* drmVersion obtains the version information via an ioctl.  Similar
+ * information is available via /proc/drm. */
+
+drmVersionPtr drmGetVersion(int fd)
+{
+    drmVersionPtr retval;
+    drm_version_t *version = drmMalloc(sizeof(*version));
+
+				/* First, get the lengths */
+    version->name_len    = 0;
+    version->name        = NULL;
+    version->date_len    = 0;
+    version->date        = NULL;
+    version->desc_len    = 0;
+    version->desc        = NULL;
+    
+    if (ioctl(fd, DRM_IOCTL_VERSION, version)) {
+	drmFreeKernelVersion(version);
+	return NULL;
+    }
+
+				/* Now, allocate space and get the data */
+    if (version->name_len)
+	version->name    = drmMalloc(version->name_len + 1);
+    if (version->date_len)
+	version->date    = drmMalloc(version->date_len + 1);
+    if (version->desc_len)
+	version->desc    = drmMalloc(version->desc_len + 1);
+    
+    if (ioctl(fd, DRM_IOCTL_VERSION, version)) {
+	drmFreeKernelVersion(version);
+	return NULL;
+    }
+
+				/* The results might not be null-terminated
+                                   strings, so terminate them. */
+
+    if (version->name_len) version->name[version->name_len] = '\0';
+    if (version->date_len) version->date[version->date_len] = '\0';
+    if (version->desc_len) version->desc[version->desc_len] = '\0';
+
+				/* Now, copy it all back into the
+                                   client-visible data structure... */
+    retval = drmMalloc(sizeof(*retval));
+    drmCopyVersion(retval, version);
+    drmFreeKernelVersion(version);
+    return retval;
+}
+
+void drmFreeVersionList(drmListPtr list)
+{
+    int i;
+    
+    if (!list) return;
+    if (list->version) {
+	for (i = 0; i < list->count; i++) {
+	    if (list->version[i].name) drmFree(list->version[i].name);
+	    if (list->version[i].date) drmFree(list->version[i].date);
+	    if (list->version[i].desc) drmFree(list->version[i].desc);
+	    
+	}
+	drmFree(list->version);
+    }
+    if (list->capability) drmFree(list->capability);
+    drmFree(list);
+}
+
+static void drmFreeKernelVersionList(drm_list_t *list)
+{
+    int i;
+    
+    if (!list) return;
+    if (list->version) {
+	for (i = 0; i < list->count; i++) {
+	    if (list->version[i].name) drmFree(list->version[i].name);
+	    if (list->version[i].date) drmFree(list->version[i].date);
+	    if (list->version[i].desc) drmFree(list->version[i].desc);
+	    
+	}
+	drmFree(list->version);
+    }
+    drmFree(list);
+}
+
+/* drmList obtains a list of all drivers and capabilities via an ioctl. */
+
+drmListPtr drmGetVersionList(int fd)
+{
+    drmListPtr retval;
+    drm_list_t *list = drmMalloc(sizeof(*list));
+    int        i;
+
+    list->count = 0;
+
+				/* First, get the count */
+    
+    if (ioctl(fd, DRM_IOCTL_LIST, list)) {
+	drmFreeKernelVersionList(list);
+	return NULL;
+    }
+
+				/* Next, get the version sizes */
+    for (i = 0; i < list->count; i++) {
+	list->version
+	    = drmMalloc(list->count * sizeof(*list->version));
+	list->version[i].name_len = 0;
+	list->version[i].name     = NULL;
+	list->version[i].date_len = 0;
+	list->version[i].date     = NULL;
+	list->version[i].desc_len = 0;
+	list->version[i].desc     = NULL;
+    }
+
+    if (ioctl(fd, DRM_IOCTL_LIST, list)) {
+	drmFreeKernelVersionList(list);
+	return NULL;
+    }
+    
+				/* Now, allocate space and get the data */
+    for (i = 0; i < list->count; i++) {
+	if (list->version[i].name_len)
+	    list->version[i].name = drmMalloc(list->version[i].name_len + 1);
+	if (list->version[i].date_len)
+	    list->version[i].date = drmMalloc(list->version[i].date_len + 1);
+	if (list->version[i].desc_len)
+	    list->version[i].desc = drmMalloc(list->version[i].desc_len + 1);
+    }
+    
+    if (ioctl(fd, DRM_IOCTL_LIST, list)) {
+	drmFreeKernelVersionList(list);
+	return NULL;
+    }
+
+				/* The results might not be null-terminated
+                                   strings, so terminate them. */
+
+    for (i = 0; i < list->count; i++) {
+	if (list->version[i].name_len)
+	    list->version[i].name[list->version[i].name_len] = '\0';
+	if (list->version[i].date_len)
+	    list->version[i].date[list->version[i].date_len] = '\0';
+	if (list->version[i].desc_len)
+	    list->version[i].desc[list->version[i].desc_len] = '\0';
+    }
+    
+				/* Now, copy it all back into the
+                                   client-visible data structure... */
+    retval = drmMalloc(sizeof(*retval));
+    retval->count      = list->count;
+    retval->version    = drmMalloc(list->count * sizeof(*retval->version));
+    retval->capability = drmMalloc(list->count * sizeof(*retval->capability));
+    for (i = 0; i < list->count; i++) {
+	drmCopyVersion(&retval->version[i], &list->version[i]);
+    }
+    drmFreeKernelVersionList(list);
+    return retval;
+}
+
+int drmCreateSub(int fd, const char *name, const char *busid)
+{
+    drm_request_t request;
+
+    request.device_name  = name;
+    request.device_busid = busid;
+    if (ioctl(fd, DRM_IOCTL_CREATE, &request)) {
+	return -errno;
+    }
+    return 0;
+}
+
+int drmDestroySub(int fd, const char *busid)
+{
+    drm_request_t request;
+
+    request.device_busid = busid;
+    request.device_major = drmGetMajor();
+    request.device_minor = drmGetMinor(NULL, busid);
+    if (ioctl(fd, DRM_IOCTL_DESTROY, &request)) {
+	return -errno;
+    }
+    return 0;
+}
+
+int drmGetMagic(int fd, drmMagicPtr magic)
+{
+    drm_auth_t auth;
+
+    *magic = 0;
+    if (ioctl(fd, DRM_IOCTL_GET_MAGIC, &auth)) return -errno;
+    *magic = auth.magic;
+    return 0;
+}
+
+int drmAuthMagic(int fd, drmMagic magic)
+{
+    drm_auth_t auth;
+
+    auth.magic = magic;
+    if (ioctl(fd, DRM_IOCTL_AUTH_MAGIC, &auth)) return -errno;
+    return 0;
+}
+
+int drmAddMap(int fd,
+	      drmHandle offset,
+	      drmSize size,
+	      drmMapType type,
+	      drmMapFlags flags,
+	      drmHandlePtr handle)
+{
+    drm_map_t map;
+
+    map.offset  = offset;
+    map.size    = size;
+    map.handle  = 0;
+    map.type    = type;
+    map.flags   = flags;
+    if (ioctl(fd, DRM_IOCTL_ADD_MAP, &map)) return -errno;
+    if (handle) *handle = (drmHandle)map.handle;
+    return 0;
+}
+
+int drmAddBufs(int fd, int count, int size, int flags)
+{
+    drm_buf_desc_t request;
+    
+    request.count     = count;
+    request.size      = size;
+    request.low_mark  = 0;
+    request.high_mark = 0;
+    request.flags     = flags;
+    if (ioctl(fd, DRM_IOCTL_ADD_BUFS, &request)) return -errno;
+    return request.count;
+}
+
+int drmMarkBufs(int fd, double low, double high)
+{
+    drm_buf_info_t info;
+    int            i;
+
+    info.count = 0;
+    info.list  = NULL;
+
+    if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) return -EINVAL;
+
+    if (!info.count) return -EINVAL;
+    
+    if (!(info.list = drmMalloc(info.count * sizeof(*info.list))))
+	return -ENOMEM;
+	
+    if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) {
+	int retval = -errno;
+	drmFree(info.list);
+	return retval;
+    }
+    
+    for (i = 0; i < info.count; i++) {
+	info.list[i].low_mark  = low  * info.list[i].count;
+	info.list[i].high_mark = high * info.list[i].count;
+	if (ioctl(fd, DRM_IOCTL_MARK_BUFS, &info.list[i])) {
+	    int retval = -errno;
+	    drmFree(info.list);
+	    return retval;
+	}
+    }
+    drmFree(info.list);
+    
+    return 0;
+}
+
+int drmFreeBufs(int fd, int count, int *list)
+{
+    drm_buf_free_t request;
+
+    request.count = count;
+    request.list  = list;
+    if (ioctl(fd, DRM_IOCTL_FREE_BUFS, &request)) return -errno;
+    return 0;
+}
+
+int drmOpenSub(const char *busid)
+{
+    return drmOpen(NULL, busid);
+}
+
+int drmCloseSub(int fd)
+{
+    unsigned long key    = drmGetKeyFromFd(fd);
+    drmHashEntry  *entry = drmGetEntry(fd);
+
+    drmHashDestroy(entry->tagTable);
+    entry->fd       = 0;
+    entry->f        = NULL;
+    entry->tagTable = NULL;
+
+    drmHashDelete(drmHashTable, key);
+    drmFree(entry);
+
+    return close(fd);
+}
+
+int drmMap(int fd,
+	   drmHandle handle,
+	   drmSize size,
+	   drmAddressPtr address)
+{
+    if (fd < 0) return -EINVAL;
+    *address = mmap(0, size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, handle);
+    if (*address == MAP_FAILED) return -errno;
+    return 0;
+}
+
+int drmUnmap(drmAddress address, drmSize size)
+{
+    return munmap(address, size);
+}
+
+drmBufInfoPtr drmGetBufInfo(int fd)
+{
+    drm_buf_info_t info;
+    drmBufInfoPtr  retval;
+    int            i;
+
+    info.count = 0;
+    info.list  = NULL;
+
+    if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) return NULL;
+
+    if (info.count) {
+	if (!(info.list = drmMalloc(info.count * sizeof(*info.list))))
+	    return NULL;
+	
+	if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) {
+	    drmFree(info.list);
+	    return NULL;
+	}
+				/* Now, copy it all back into the
+                                   client-visible data structure... */
+	retval = drmMalloc(sizeof(*retval));
+	retval->count = info.count;
+	retval->list  = drmMalloc(info.count * sizeof(*retval->list));
+	for (i = 0; i < info.count; i++) {
+	    retval->list[i].count     = info.list[i].count;
+	    retval->list[i].size      = info.list[i].size;
+	    retval->list[i].low_mark  = info.list[i].low_mark;
+	    retval->list[i].high_mark = info.list[i].high_mark;
+	}
+	drmFree(info.list);
+	return retval;
+    }
+    return NULL;
+}
+
+drmBufMapPtr drmMapBufs(int fd)
+{
+    drm_buf_map_t bufs;
+    drmBufMapPtr  retval;
+    int           i;
+    
+    bufs.count = 0;
+    bufs.list  = NULL;
+    if (ioctl(fd, DRM_IOCTL_MAP_BUFS, &bufs)) return NULL;
+
+    if (bufs.count) {
+	if (!(bufs.list = drmMalloc(bufs.count * sizeof(*bufs.list))))
+	    return NULL;
+
+	if (ioctl(fd, DRM_IOCTL_MAP_BUFS, &bufs)) {
+	    drmFree(bufs.list);
+	    return NULL;
+	}
+				/* Now, copy it all back into the
+                                   client-visible data structure... */
+	retval = drmMalloc(sizeof(*retval));
+	retval->count = bufs.count;
+	retval->list  = drmMalloc(bufs.count * sizeof(*retval->list));
+	for (i = 0; i < bufs.count; i++) {
+	    retval->list[i].idx     = bufs.list[i].idx;
+	    retval->list[i].total   = bufs.list[i].total;
+	    retval->list[i].used    = 0;
+	    retval->list[i].address = bufs.list[i].address;
+	}
+	return retval;
+    }
+    return NULL;
+}
+
+int drmUnmapBufs(drmBufMapPtr bufs)
+{
+    int i;
+    
+    for (i = 0; i < bufs->count; i++) {
+	munmap(bufs->list[i].address, bufs->list[i].total);
+    }
+    return 0;
+}
+
+int drmDMA(int fd, drmDMAReqPtr request)
+{
+    drm_dma_t dma;
+
+				/* Copy to hidden structure */
+    dma.context         = request->context;
+    dma.send_count      = request->send_count;
+    dma.send_indices    = request->send_list;
+    dma.send_sizes      = request->send_sizes;
+    dma.flags           = request->flags;
+    dma.request_count   = request->request_count;
+    dma.request_size    = request->request_size;
+    dma.request_indices = request->request_list;
+    dma.request_sizes   = request->request_sizes;
+    if (ioctl(fd, DRM_IOCTL_DMA, &dma)) return -errno;
+    request->granted_count = dma.granted_count;
+    
+    return 0;
+}
+
+int drmGetLock(int fd, drmContext context, drmLockFlags flags)
+{
+    drm_lock_t lock;
+
+    lock.context = context;
+    lock.flags   = 0;
+    if (flags & DRM_LOCK_READY)      lock.flags |= _DRM_LOCK_READY;
+    if (flags & DRM_LOCK_QUIESCENT)  lock.flags |= _DRM_LOCK_QUIESCENT;
+    if (flags & DRM_LOCK_FLUSH)      lock.flags |= _DRM_LOCK_FLUSH;
+    if (flags & DRM_LOCK_FLUSH_ALL)  lock.flags |= _DRM_LOCK_FLUSH_ALL;
+    if (flags & DRM_HALT_ALL_QUEUES) lock.flags |= _DRM_HALT_ALL_QUEUES;
+    if (flags & DRM_HALT_CUR_QUEUES) lock.flags |= _DRM_HALT_CUR_QUEUES;
+    
+    while (ioctl(fd, DRM_IOCTL_LOCK, &lock))
+	;
+    return 0;
+}
+
+int drmUnlock(int fd, drmContext context)
+{
+    drm_lock_t lock;
+
+    lock.context = context;
+    lock.flags   = 0;
+    return ioctl(fd, DRM_IOCTL_UNLOCK, &lock);
+}
+
+drmContextPtr drmGetReservedContextList(int fd, int *count)
+{
+    drm_ctx_res_t res;
+    drm_ctx_t     *list;
+    drmContextPtr retval;
+    int           i;
+
+    res.count    = 0;
+    res.contexts = NULL;
+    if (ioctl(fd, DRM_IOCTL_RES_CTX, &res)) return NULL;
+
+    if (!res.count) return NULL;
+
+    if (!(list   = drmMalloc(res.count * sizeof(*list)))) return NULL;
+    if (!(retval = drmMalloc(res.count * sizeof(*retval)))) {
+	drmFree(list);
+	return NULL;
+    }
+
+    res.contexts = list;
+    if (ioctl(fd, DRM_IOCTL_RES_CTX, &res)) return NULL;
+
+    for (i = 0; i < res.count; i++) retval[i] = list[i].handle;
+    drmFree(list);
+
+    *count = res.count;
+    return retval;
+}
+
+void drmFreeReservedContextList(drmContextPtr pt)
+{
+    drmFree(pt);
+}
+
+int drmCreateContext(int fd, drmContextPtr handle)
+{
+    drm_ctx_t ctx;
+
+    ctx.flags = 0;	/* Modified with functions below */
+    if (ioctl(fd, DRM_IOCTL_ADD_CTX, &ctx)) return -errno;
+    *handle = ctx.handle;
+    return 0;
+}
+
+int drmSwitchToContext(int fd, drmContext context)
+{
+    drm_ctx_t ctx;
+
+    ctx.handle = context;
+    if (ioctl(fd, DRM_IOCTL_SWITCH_CTX, &ctx)) return -errno;
+    return 0;
+}
+
+int drmSetContextFlags(int fd, drmContext context, drmContextFlags flags)
+{
+    drm_ctx_t ctx;
+
+				/* Context preserving means that no context
+                                   switched are done between DMA buffers
+                                   from one context and the next.  This is
+                                   suitable for use in the X server (which
+                                   promises to maintain hardware context,
+                                   or in the client-side library when
+                                   buffers are swapped on behalf of two
+                                   threads. */
+    ctx.handle = context;
+    ctx.flags  = 0;
+    if (flags & DRM_CONTEXT_PRESERVED) ctx.flags |= _DRM_CONTEXT_PRESERVED;
+    if (flags & DRM_CONTEXT_2DONLY)    ctx.flags |= _DRM_CONTEXT_2DONLY;
+    if (ioctl(fd, DRM_IOCTL_MOD_CTX, &ctx)) return -errno;
+    return 0;
+}
+
+int drmGetContextFlags(int fd, drmContext context, drmContextFlagsPtr flags)
+{
+    drm_ctx_t ctx;
+
+    ctx.handle = context;
+    if (ioctl(fd, DRM_IOCTL_GET_CTX, &ctx)) return -errno;
+    *flags = 0;
+    if (ctx.flags & _DRM_CONTEXT_PRESERVED) *flags |= DRM_CONTEXT_PRESERVED;
+    if (ctx.flags & _DRM_CONTEXT_2DONLY)    *flags |= DRM_CONTEXT_2DONLY;
+    return 0;
+}
+    
+int drmDestroyContext(int fd, drmContext handle)
+{
+    drm_ctx_t ctx;
+    ctx.handle = handle;
+    if (ioctl(fd, DRM_IOCTL_RM_CTX, &ctx)) return -errno;
+    return 0;
+}
+
+int drmCreateDrawable(int fd, drmDrawablePtr handle)
+{
+    drm_draw_t draw;
+    if (ioctl(fd, DRM_IOCTL_ADD_DRAW, &draw)) return -errno;
+    *handle = draw.handle;
+    return 0;
+}
+
+int drmDestroyDrawable(int fd, drmDrawable handle)
+{
+    drm_draw_t draw;
+    draw.handle = handle;
+    if (ioctl(fd, DRM_IOCTL_RM_DRAW, &draw)) return -errno;
+    return 0;
+}
+
+int drmError(int err, const char *label)
+{
+    switch (err) {
+    case DRM_ERR_NO_DEVICE: fprintf(stderr, "%s: no device\n", label);   break;
+    case DRM_ERR_NO_ACCESS: fprintf(stderr, "%s: no access\n", label);   break;
+    case DRM_ERR_NOT_ROOT:  fprintf(stderr, "%s: not root\n", label);    break;
+    case DRM_ERR_INVALID:   fprintf(stderr, "%s: invalid args\n", label);break;
+    default:
+	if (err < 0) err = -err;
+	fprintf( stderr, "%s: error %d (%s)\n", label, err, strerror(err) );
+	break;
+    }
+
+    return 1;
+}
+
+int drmCtlAddCommand(int fd, drmCtlDesc desc, int count, int *inst)
+{
+    drm_control_t ctl;
+
+    ctl.func  = DRM_ADD_COMMAND;
+    ctl.irq   = 0;
+    ctl.count = count;
+    ctl.inst  = inst;
+
+    switch (desc) {
+    case DRM_IH_PRE_INST:    ctl.desc = _DRM_IH_PRE_INST;    break;
+    case DRM_IH_POST_INST:   ctl.desc = _DRM_IH_POST_INST;   break;
+    case DRM_IH_SERVICE:     ctl.desc = _DRM_IH_SERVICE;     break;
+    case DRM_IH_PRE_UNINST:  ctl.desc = _DRM_IH_PRE_UNINST;  break;
+    case DRM_IH_POST_UNINST: ctl.desc = _DRM_IH_POST_UNINST; break;
+    case DRM_DMA_DISPATCH:   ctl.desc = _DRM_DMA_DISPATCH;   break;
+    case DRM_DMA_READY:      ctl.desc = _DRM_DMA_READY;      break;
+    case DRM_DMA_IS_READY:   ctl.desc = _DRM_DMA_IS_READY;   break;
+    case DRM_DMA_QUIESCENT:  ctl.desc = _DRM_DMA_QUIESCENT;  break;
+    default:
+	return -EINVAL;
+    }
+
+    if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
+    return 0;
+}
+
+int drmCtlRemoveCommands(int fd)
+{
+    drm_control_t ctl;
+    drm_desc_t    i;
+
+    for (i = 0; i < DRM_DESC_MAX; i++) {
+	ctl.func  = DRM_RM_COMMAND;
+	ctl.desc  = i;
+	ctl.irq   = 0;
+	ctl.count = 0;
+	ctl.inst  = NULL;
+	ioctl(fd, DRM_IOCTL_CONTROL, &ctl);
+    }
+    return 0;
+}
+
+int drmCtlInstHandler(int fd, int irq)
+{
+    drm_control_t ctl;
+
+    ctl.func  = DRM_INST_HANDLER;
+    ctl.desc  = 0;		/* unused */
+    ctl.irq   = irq;
+    ctl.count = 0;
+    ctl.inst  = NULL;
+    if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
+    return 0;
+}
+
+int drmCtlUninstHandler(int fd)
+{
+    drm_control_t ctl;
+
+    ctl.func  = DRM_UNINST_HANDLER;
+    ctl.desc  = 0;		/* unused */
+    ctl.irq   = 0;
+    ctl.count = 0;
+    ctl.inst  = NULL;
+    if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
+    return 0;
+}
+
+int drmFinish(int fd, int context, drmLockFlags flags)
+{
+    drm_lock_t lock;
+
+    lock.context = context;
+    lock.flags   = 0;
+    if (flags & DRM_LOCK_READY)      lock.flags |= _DRM_LOCK_READY;
+    if (flags & DRM_LOCK_QUIESCENT)  lock.flags |= _DRM_LOCK_QUIESCENT;
+    if (flags & DRM_LOCK_FLUSH)      lock.flags |= _DRM_LOCK_FLUSH;
+    if (flags & DRM_LOCK_FLUSH_ALL)  lock.flags |= _DRM_LOCK_FLUSH_ALL;
+    if (flags & DRM_HALT_ALL_QUEUES) lock.flags |= _DRM_HALT_ALL_QUEUES;
+    if (flags & DRM_HALT_CUR_QUEUES) lock.flags |= _DRM_HALT_CUR_QUEUES;
+    if (ioctl(fd, DRM_IOCTL_FINISH, &lock)) return -errno;
+    return 0;
+}
+
+int drmGetInterruptFromBusID(int fd, int busnum, int devnum, int funcnum)
+{
+    drm_irq_busid_t p;
+
+    p.busnum  = busnum;
+    p.devnum  = devnum;
+    p.funcnum = funcnum;
+    if (ioctl(fd, DRM_IOCTL_IRQ_BUSID, &p)) return -errno;
+    return p.irq;
+}
+
+int drmAddContextTag(int fd, drmContext context, void *tag)
+{
+    drmHashEntry  *entry = drmGetEntry(fd);
+
+    if (drmHashInsert(entry->tagTable, context, tag)) {
+	drmHashDelete(entry->tagTable, context);
+	drmHashInsert(entry->tagTable, context, tag);
+    }
+    return 0;
+}
+
+int drmDelContextTag(int fd, drmContext context)
+{
+    drmHashEntry  *entry = drmGetEntry(fd);
+
+    return drmHashDelete(entry->tagTable, context);
+}
+
+void *drmGetContextTag(int fd, drmContext context)
+{
+    drmHashEntry  *entry = drmGetEntry(fd);
+    void          *value;
+    
+    if (drmHashLookup(entry->tagTable, context, &value)) return NULL;
+
+    return value;
+}
+
+#if defined(XFree86Server) || defined(DRM_USE_MALLOC)
+static void drmSIGIOHandler(int interrupt)
+{
+    unsigned long key;
+    void          *value;
+    ssize_t       count;
+    drm_ctx_t     ctx;
+    typedef void  (*_drmCallback)(int, void *, void *);
+    char          buf[256];
+    drmContext    old;
+    drmContext    new;
+    void          *oldctx;
+    void          *newctx;
+    char          *pt;
+    drmHashEntry  *entry;
+
+    if (!drmHashTable) return;
+    if (drmHashFirst(drmHashTable, &key, &value)) {
+	entry = value;
+	do {
+#if 0
+	    fprintf(stderr, "Trying %d\n", entry->fd);
+#endif
+	    if ((count = read(entry->fd, buf, sizeof(buf)))) {
+		buf[count] = '\0';
+#if 0
+		fprintf(stderr, "Got %s\n", buf);
+#endif
+		
+		for (pt = buf; *pt != ' '; ++pt); /* Find first space */
+		++pt;
+		old    = strtol(pt, &pt, 0);
+		new    = strtol(pt, NULL, 0);
+		oldctx = drmGetContextTag(entry->fd, old);
+		newctx = drmGetContextTag(entry->fd, new);
+#if 0
+		fprintf(stderr, "%d %d %p %p\n", old, new, oldctx, newctx);
+#endif
+		((_drmCallback)entry->f)(entry->fd, oldctx, newctx);
+		ctx.handle = new;
+		ioctl(entry->fd, DRM_IOCTL_NEW_CTX, &ctx);
+	    }
+	} while (drmHashNext(drmHashTable, &key, &value));
+    }
+}
+
+int drmInstallSIGIOHandler(int fd, void (*f)(int, void *, void *))
+{
+    drmHashEntry     *entry;
+
+    entry     = drmGetEntry(fd);
+    entry->f  = f;
+
+    return xf86InstallSIGIOHandler(fd, drmSIGIOHandler);
+}
+
+int drmRemoveSIGIOHandler(int fd)
+{
+    drmHashEntry     *entry = drmGetEntry(fd);
+
+    entry->f = NULL;
+    
+    return xf86RemoveSIGIOHandler(fd);
+}
+#endif
diff --git a/libdrm/xf86drmHash.c b/libdrm/xf86drmHash.c
new file mode 100644
index 00000000..a3c9481b
--- /dev/null
+++ b/libdrm/xf86drmHash.c
@@ -0,0 +1,435 @@
+/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
+ * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
+ * Revised: Thu Jun  3 16:11:06 1999 by faith@precisioninsight.com
+ *
+ * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ * 
+ * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.3 1999/06/07 13:01:42 faith Exp $
+ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.1 1999/06/14 07:32:02 dawes Exp $
+ *
+ * DESCRIPTION
+ *
+ * This file contains a straightforward implementation of a fixed-sized
+ * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
+ * collision resolution.  There are two potentially interesting things
+ * about this implementation:
+ *
+ * 1) The table is power-of-two sized.  Prime sized tables are more
+ * traditional, but do not have a significant advantage over power-of-two
+ * sized table, especially when double hashing is not used for collision
+ * resolution.
+ *
+ * 2) The hash computation uses a table of random integers [Hanson97,
+ * pp. 39-41].
+ *
+ * FUTURE ENHANCEMENTS
+ *
+ * With a table size of 512, the current implementation is sufficient for a
+ * few hundred keys.  Since this is well above the expected size of the
+ * tables for which this implementation was designed, the implementation of
+ * dynamic hash tables was postponed until the need arises.  A common (and
+ * naive) approach to dynamic hash table implementation simply creates a
+ * new hash table when necessary, rehashes all the data into the new table,
+ * and destroys the old table.  The approach in [Larson88] is superior in
+ * two ways: 1) only a portion of the table is expanded when needed,
+ * distributing the expansion cost over several insertions, and 2) portions
+ * of the table can be locked, enabling a scalable thread-safe
+ * implementation.
+ *
+ * REFERENCES
+ *
+ * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
+ * Techniques for Creating Reusable Software.  Reading, Massachusetts:
+ * Addison-Wesley, 1997.
+ *
+ * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
+ * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
+ *
+ * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
+ * 1988, pp. 446-457.
+ *
+ */
+
+#define HASH_MAIN 0
+
+#if HASH_MAIN
+# include <stdio.h>
+# include <stdlib.h>
+#else
+# include "xf86drm.h"
+# ifdef XFree86LOADER
+#  include "xf86.h"
+#  include "xf86_ansic.h"
+# else
+#  include <stdio.h>
+#  include <stdlib.h>
+# endif
+#endif
+
+#define N(x)  drm##x
+
+#define HASH_MAGIC 0xdeadbeef
+#define HASH_DEBUG 0
+#define HASH_SIZE  512		/* Good for about 100 entries */
+				/* If you change this value, you probably
+                                   have to change the HashHash hashing
+                                   function! */
+
+#if HASH_MAIN
+#define HASH_ALLOC malloc
+#define HASH_FREE  free
+#define HASH_RANDOM_DECL
+#define HASH_RANDOM_INIT(seed)  srandom(seed)
+#define HASH_RANDOM             random()
+#else
+#define HASH_ALLOC drmMalloc
+#define HASH_FREE  drmFree
+#define HASH_RANDOM_DECL        void *state
+#define HASH_RANDOM_INIT(seed)  state = drmRandomCreate(seed)
+#define HASH_RANDOM             drmRandom(state)
+
+#endif
+
+typedef struct HashBucket {
+    unsigned long     key;
+    void              *value;
+    struct HashBucket *next;
+} HashBucket, *HashBucketPtr;
+
+typedef struct HashTable {
+    unsigned long    magic;
+    unsigned long    entries;
+    unsigned long    hits;	/* At top of linked list */
+    unsigned long    partials;	/* Not at top of linked list */
+    unsigned long    misses;	/* Not in table */
+    HashBucketPtr    buckets[HASH_SIZE];
+    int              p0;
+    HashBucketPtr    p1;
+} HashTable, *HashTablePtr;
+
+#if HASH_MAIN
+extern void *N(HashCreate)(void);
+extern int  N(HashDestroy)(void *t);
+extern int  N(HashLookup)(void *t, unsigned long key, unsigned long *value);
+extern int  N(HashInsert)(void *t, unsigned long key, unsigned long value);
+extern int  N(HashDelete)(void *t, unsigned long key);
+#endif
+
+static unsigned long HashHash(unsigned long key)
+{
+    unsigned long        hash = 0;
+    unsigned long        tmp  = key;
+    static int           init = 0;
+    static unsigned long scatter[256];
+    int                  i;
+
+    if (!init) {
+	HASH_RANDOM_DECL;
+	HASH_RANDOM_INIT(37);
+	for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
+	++init;
+    }
+
+    while (tmp) {
+	hash = (hash << 1) + scatter[tmp & 0xff];
+	tmp >>= 8;
+    }
+
+    hash %= HASH_SIZE;
+#if HASH_DEBUG
+    printf( "Hash(%d) = %d\n", key, hash);
+#endif
+    return hash;
+}
+
+void *N(HashCreate)(void)
+{
+    HashTablePtr table;
+    int          i;
+
+    table           = HASH_ALLOC(sizeof(*table));
+    if (!table) return NULL;
+    table->magic    = HASH_MAGIC;
+    table->entries  = 0;
+    table->hits     = 0;
+    table->partials = 0;
+    table->misses   = 0;
+
+    for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
+    return table;
+}
+
+int N(HashDestroy)(void *t)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    HashBucketPtr bucket;
+    HashBucketPtr next;
+    int           i;
+
+    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
+    
+    for (i = 0; i < HASH_SIZE; i++) {
+	for (bucket = table->buckets[i]; bucket;) {
+	    next = bucket->next;
+	    HASH_FREE(bucket);
+	    bucket = next;
+	}
+    }
+    HASH_FREE(table);
+    return 0;
+}
+
+/* Find the bucket and organize the list so that this bucket is at the
+   top. */
+
+static HashBucketPtr HashFind(HashTablePtr table,
+			      unsigned long key, unsigned long *h)
+{
+    unsigned long hash = HashHash(key);
+    HashBucketPtr prev = NULL;
+    HashBucketPtr bucket;
+
+    if (h) *h = hash;
+
+    for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
+	if (bucket->key == key) {
+	    if (prev) {
+				/* Organize */
+		prev->next           = bucket->next;
+		bucket->next         = table->buckets[hash];
+		table->buckets[hash] = bucket;
+		++table->partials;
+	    } else {
+		++table->hits;
+	    }
+	    return bucket;
+	}
+	prev = bucket;
+    }
+    ++table->misses;
+    return NULL;
+}
+
+int N(HashLookup)(void *t, unsigned long key, void **value)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    HashBucketPtr bucket;
+
+    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
+    
+    bucket = HashFind(table, key, NULL);
+    if (!bucket) return 1;	/* Not found */
+    *value = bucket->value;
+    return 0;			/* Found */
+}
+
+int N(HashInsert)(void *t, unsigned long key, void *value)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    HashBucketPtr bucket;
+    unsigned long hash;
+
+    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
+    
+    if (HashFind(table, key, &hash)) return 1; /* Already in table */
+
+    bucket               = HASH_ALLOC(sizeof(*bucket));
+    if (!bucket) return -1;	/* Error */
+    bucket->key          = key;
+    bucket->value        = value;
+    bucket->next         = table->buckets[hash];
+    table->buckets[hash] = bucket;
+#if HASH_DEBUG
+    printf("Inserted %d at %d/%p\n", key, hash, bucket);
+#endif
+    return 0;			/* Added to table */
+}
+
+int N(HashDelete)(void *t, unsigned long key)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    unsigned long hash;
+    HashBucketPtr bucket;
+
+    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
+    
+    bucket = HashFind(table, key, &hash);
+
+    if (!bucket) return 1;	/* Not found */
+
+    table->buckets[hash] = bucket->next;
+    HASH_FREE(bucket);
+    return 0;
+}
+
+int N(HashNext)(void *t, unsigned long *key, void **value)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    
+    for (; table->p0 < HASH_SIZE;
+	 ++table->p0, table->p1 = table->buckets[table->p0]) {
+	if (table->p1) {
+	    *key       = table->p1->key;
+	    *value     = table->p1->value;
+	    table->p1  = table->p1->next;
+	    return 1;
+	}
+    }
+    return 0;
+}
+
+int N(HashFirst)(void *t, unsigned long *key, void **value)
+{
+    HashTablePtr  table = (HashTablePtr)t;
+    
+    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
+
+    table->p0 = 0;
+    table->p1 = table->buckets[0];
+    return N(HashNext)(table, key, value);
+}
+
+#if HASH_MAIN
+#define DIST_LIMIT 10
+static int dist[DIST_LIMIT];
+
+static void clear_dist(void) {
+    int i;
+
+    for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0;
+}
+
+static int count_entries(HashBucketPtr bucket)
+{
+    int count = 0;
+
+    for (; bucket; bucket = bucket->next) ++count;
+    return count;
+}
+
+static void update_dist(int count)
+{
+    if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1];
+    else                     ++dist[count];
+}
+
+static void compute_dist(HashTablePtr table)
+{
+    int           i;
+    HashBucketPtr bucket;
+    
+    printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
+	   table->entries, table->hits, table->partials, table->misses);
+    clear_dist();
+    for (i = 0; i < HASH_SIZE; i++) {
+	bucket = table->buckets[i];
+	update_dist(count_entries(bucket));
+    }
+    for (i = 0; i < DIST_LIMIT; i++) {
+	if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]);
+	else                   printf("other %10d\n", dist[i]);
+    }
+}
+
+static void check_table(HashTablePtr table,
+			unsigned long key, unsigned long value)
+{
+    unsigned long retval  = 0;
+    int           retcode = N(HashLookup)(table, key, &retval);
+    
+    switch (retcode) {
+    case -1:
+	printf("Bad magic = 0x%08lx:"
+	       " key = %lu, expected = %lu, returned = %lu\n",
+	       table->magic, key, value, retval);
+	break;
+    case 1:
+	printf("Not found: key = %lu, expected = %lu returned = %lu\n",
+	       key, value, retval);
+	break;
+    case 0:
+	if (value != retval)
+	    printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
+		   key, value, retval);
+	break;
+    default:
+	printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
+	       retcode, key, value, retval);
+	break;
+    }
+}
+
+int main(void)
+{
+    HashTablePtr table;
+    int          i;
+
+    printf("\n***** 256 consecutive integers ****\n");
+    table = N(HashCreate)();
+    for (i = 0; i < 256; i++) N(HashInsert)(table, i, i);
+    for (i = 0; i < 256; i++) check_table(table, i, i);
+    for (i = 256; i >= 0; i--) check_table(table, i, i);
+    compute_dist(table);
+    N(HashDestroy)(table);
+    
+    printf("\n***** 1024 consecutive integers ****\n");
+    table = N(HashCreate)();
+    for (i = 0; i < 1024; i++) N(HashInsert)(table, i, i);
+    for (i = 0; i < 1024; i++) check_table(table, i, i);
+    for (i = 1024; i >= 0; i--) check_table(table, i, i);
+    compute_dist(table);
+    N(HashDestroy)(table);
+    
+    printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
+    table = N(HashCreate)();
+    for (i = 0; i < 1024; i++) N(HashInsert)(table, i*4096, i);
+    for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
+    for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
+    compute_dist(table);
+    N(HashDestroy)(table);
+    
+    printf("\n***** 1024 random integers ****\n");
+    table = N(HashCreate)();
+    srandom(0xbeefbeef);
+    for (i = 0; i < 1024; i++) N(HashInsert)(table, random(), i);
+    srandom(0xbeefbeef);
+    for (i = 0; i < 1024; i++) check_table(table, random(), i);
+    srandom(0xbeefbeef);
+    for (i = 0; i < 1024; i++) check_table(table, random(), i);
+    compute_dist(table);
+    N(HashDestroy)(table);
+
+    printf("\n***** 5000 random integers ****\n");
+    table = N(HashCreate)();
+    srandom(0xbeefbeef);
+    for (i = 0; i < 5000; i++) N(HashInsert)(table, random(), i);
+    srandom(0xbeefbeef);
+    for (i = 0; i < 5000; i++) check_table(table, random(), i);
+    srandom(0xbeefbeef);
+    for (i = 0; i < 5000; i++) check_table(table, random(), i);
+    compute_dist(table);
+    N(HashDestroy)(table);
+    
+    return 0;
+}
+#endif
diff --git a/libdrm/xf86drmRandom.c b/libdrm/xf86drmRandom.c
new file mode 100644
index 00000000..dad836d0
--- /dev/null
+++ b/libdrm/xf86drmRandom.c
@@ -0,0 +1,219 @@
+/* xf86drmRandom.c -- "Minimal Standard" PRNG Implementation
+ * Created: Mon Apr 19 08:28:13 1999 by faith@precisioninsight.com
+ * Revised: Thu Jun 24 14:53:45 1999 by faith@precisioninsight.com
+ *
+ * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ * 
+ * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmRandom.c,v 1.4 1999/06/24 18:54:55 faith Exp $
+ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmRandom.c,v 1.2 1999/06/27 14:08:20 dawes Exp $
+ *
+ * DESCRIPTION
+ *
+ * This file contains a simple, straightforward implementation of the Park
+ * & Miller "Minimal Standard" PRNG [PM88, PMS93], which is a Lehmer
+ * multiplicative linear congruential generator (MLCG) with a period of
+ * 2^31-1.
+ *
+ * This implementation is intended to provide a reliable, portable PRNG
+ * that is suitable for testing a hash table implementation and for
+ * implementing skip lists.
+ *
+ * FUTURE ENHANCEMENTS
+ *
+ * If initial seeds are not selected randomly, two instances of the PRNG
+ * can be correlated.  [Knuth81, pp. 32-33] describes a shuffling technique
+ * that can eliminate this problem.
+ *
+ * If PRNGs are used for simulation, the period of the current
+ * implementation may be too short.  [LE88] discusses methods of combining
+ * MLCGs to produce much longer periods, and suggests some alternative
+ * values for A and M.  [LE90 and Sch92] also provide information on
+ * long-period PRNGs.
+ *
+ * REFERENCES
+ *
+ * [Knuth81] Donald E. Knuth. The Art of Computer Programming.  Volume 2:
+ * Seminumerical Algorithms.  Reading, Massachusetts: Addison-Wesley, 1981.
+ *
+ * [LE88] Pierre L'Ecuyer. "Efficient and Portable Combined Random Number
+ * Generators".  CACM 31(6), June 1988, pp. 742-774.
+ *
+ * [LE90] Pierre L'Ecuyer. "Random Numbers for Simulation". CACM 33(10,
+ * October 1990, pp. 85-97.
+ *
+ * [PM88] Stephen K. Park and Keith W. Miller. "Random Number Generators:
+ * Good Ones are Hard to Find". CACM 31(10), October 1988, pp. 1192-1201.
+ *
+ * [Sch92] Bruce Schneier. "Pseudo-Ransom Sequence Generator for 32-Bit
+ * CPUs".  Dr. Dobb's Journal 17(2), February 1992, pp. 34, 37-38, 40.
+ *
+ * [PMS93] Stephen K. Park, Keith W. Miller, and Paul K. Stockmeyer.  In
+ * "Technical Correspondence: Remarks on Choosing and Implementing Random
+ * Number Generators". CACM 36(7), July 1993, pp. 105-110.
+ *
+ */
+
+#define RANDOM_MAIN 0
+
+#if RANDOM_MAIN
+# include <stdio.h>
+# include <stdlib.h>
+#else
+# include "xf86drm.h"
+# ifdef XFree86LOADER
+#  include "xf86.h"
+#  include "xf86_ansic.h"
+# else
+#  include <stdio.h>
+#  include <stdlib.h>
+# endif
+#endif
+
+#define N(x)  drm##x
+
+#define RANDOM_MAGIC 0xfeedbeef
+#define RANDOM_DEBUG 0
+
+#if RANDOM_MAIN
+#define RANDOM_ALLOC malloc
+#define RANDOM_FREE  free
+#else
+#define RANDOM_ALLOC drmMalloc
+#define RANDOM_FREE  drmFree
+#endif
+
+typedef struct RandomState {
+    unsigned long magic;
+    unsigned long a;
+    unsigned long m;
+    unsigned long q;		/* m div a */
+    unsigned long r;		/* m mod a */
+    unsigned long check;
+    long          seed;
+} RandomState;
+
+#if RANDOM_MAIN
+extern void          *N(RandomCreate)(unsigned long seed);
+extern int           N(RandomDestroy)(void *state);
+extern unsigned long N(Random)(void *state);
+extern double        N(RandomDouble)(void *state);
+#endif
+
+void *N(RandomCreate)(unsigned long seed)
+{
+    RandomState  *state;
+
+    state           = RANDOM_ALLOC(sizeof(*state));
+    if (!state) return NULL;
+    state->magic    = RANDOM_MAGIC;
+#if 0
+				/* Park & Miller, October 1988 */
+    state->a        = 16807;
+    state->m        = 2147483647;
+    state->check    = 1043618065; /* After 10000 iterations */
+#else
+				/* Park, Miller, and Stockmeyer, July 1993 */
+    state->a        = 48271;
+    state->m        = 2147483647;
+    state->check    = 399268537; /* After 10000 iterations */
+#endif
+    state->q        = state->m / state->a;
+    state->r        = state->m % state->a;
+
+    state->seed     = seed;
+				/* Check for illegal boundary conditions,
+                                   and choose closest legal value. */
+    if (state->seed <= 0)        state->seed = 1;
+    if (state->seed >= state->m) state->seed = state->m - 1;
+
+    return state;
+}
+
+int N(RandomDestroy)(void *state)
+{
+    RANDOM_FREE(state);
+    return 0;
+}
+
+unsigned long N(Random)(void *state)
+{
+    RandomState   *s = (RandomState *)state;
+    long          hi;
+    long          lo;
+
+    hi      = s->seed / s->q;
+    lo      = s->seed % s->q;
+    s->seed = s->a * lo - s->r * hi;
+    if (s->seed <= 0) s->seed += s->m;
+
+    return s->seed;
+}
+
+double N(RandomDouble)(void *state)
+{
+    RandomState *s = (RandomState *)state;
+    
+    return (double)N(Random)(state)/(double)s->m;
+}
+
+#if RANDOM_MAIN
+static void check_period(long seed)
+{
+    unsigned long count = 0;
+    unsigned long initial;
+    void          *state;
+    
+    state = N(RandomCreate)(seed);
+    initial = N(Random)(state);
+    ++count;
+    while (initial != N(Random)(state)) {
+	if (!++count) break;
+    }
+    printf("With seed of %10ld, period = %10lu (0x%08lx)\n",
+	   seed, count, count);
+    N(RandomDestroy)(state);
+}
+
+int main(void)
+{
+    RandomState   *state;
+    int           i;
+    unsigned long rand;
+
+    state = N(RandomCreate)(1);
+    for (i = 0; i < 10000; i++) {
+	rand = N(Random)(state);
+    }
+    printf("After 10000 iterations: %lu (%lu expected): %s\n",
+	   rand, state->check,
+	   rand - state->check ? "*INCORRECT*" : "CORRECT");
+    N(RandomDestroy)(state);
+
+    printf("Checking periods...\n");
+    check_period(1);
+    check_period(2);
+    check_period(31415926);
+    
+    return 0;
+}
+#endif
diff --git a/libdrm/xf86drmSL.c b/libdrm/xf86drmSL.c
new file mode 100644
index 00000000..d5dd63da
--- /dev/null
+++ b/libdrm/xf86drmSL.c
@@ -0,0 +1,490 @@
+/* xf86drmSL.c -- Skip list support
+ * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
+ * Revised: Thu Jun  3 16:13:01 1999 by faith@precisioninsight.com
+ *
+ * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ * 
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ * 
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+ * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ * 
+ * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.2 1999/06/07 13:01:42 faith Exp $
+ * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.1 1999/06/14 07:32:02 dawes Exp $
+ *
+ * DESCRIPTION
+ *
+ * This file contains a straightforward skip list implementation.n
+ *
+ * FUTURE ENHANCEMENTS
+ *
+ * REFERENCES
+ *
+ * [Pugh90] William Pugh.  Skip Lists: A Probabilistic Alternative to
+ * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
+ *
+ */
+
+#define SL_MAIN 0
+
+#if SL_MAIN
+# include <stdio.h>
+# include <stdlib.h>
+#  include <sys/time.h>
+#else
+# include "xf86drm.h"
+# ifdef XFree86LOADER
+#  include "xf86.h"
+#  include "xf86_ansic.h"
+# else
+#  include <stdio.h>
+#  include <stdlib.h>
+# endif
+#endif
+
+#define N(x)  drm##x
+
+#define SL_LIST_MAGIC  0xfacade00LU
+#define SL_ENTRY_MAGIC 0x00fab1edLU
+#define SL_FREED_MAGIC 0xdecea5edLU
+#define SL_MAX_LEVEL   16
+#define SL_DEBUG       0
+#define SL_RANDOM_SEED 0xc01055a1LU
+
+#if SL_MAIN
+#define SL_ALLOC malloc
+#define SL_FREE  free
+#define SL_RANDOM_DECL        static int state = 0;
+#define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
+#define SL_RANDOM             random()
+#else
+#define SL_ALLOC drmMalloc
+#define SL_FREE  drmFree
+#define SL_RANDOM_DECL        static void *state = NULL
+#define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
+#define SL_RANDOM             drmRandom(state)
+
+#endif
+
+typedef struct SLEntry {
+    unsigned long     magic;	   /* SL_ENTRY_MAGIC */
+    unsigned long     key;
+    void              *value;
+    int               levels;
+    struct SLEntry    *forward[1]; /* variable sized array */
+} SLEntry, *SLEntryPtr;
+
+typedef struct SkipList {
+    unsigned long    magic;	/* SL_LIST_MAGIC */
+    int              level;
+    int              count;
+    SLEntryPtr       head;
+    SLEntryPtr       p0;	/* Position for iteration */
+} SkipList, *SkipListPtr;
+
+#if SL_MAIN
+extern void *N(SLCreate)(void);
+extern int  N(SLDestroy)(void *l);
+extern int  N(SLLookup)(void *l, unsigned long key, void **value);
+extern int  N(SLInsert)(void *l, unsigned long key, void *value);
+extern int  N(SLDelete)(void *l, unsigned long key);
+extern int  N(SLNext)(void *l, unsigned long *key, void **value);
+extern int  N(SLFirst)(void *l, unsigned long *key, void **value);
+extern void N(SLDump)(void *l);
+extern int  N(SLLookupNeighbors)(void *l, unsigned long key,
+				 unsigned long *prev_key, void **prev_value,
+				 unsigned long *next_key, void **next_value);
+#endif
+
+static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
+{
+    SLEntryPtr entry;
+    
+    if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
+
+    entry         = SL_ALLOC(sizeof(*entry)
+			     + (max_level + 1) * sizeof(entry->forward[0]));
+    if (!entry) return NULL;
+    entry->magic  = SL_ENTRY_MAGIC;
+    entry->key    = key;
+    entry->value  = value;
+    entry->levels = max_level + 1;
+
+    return entry;
+}
+
+static int SLRandomLevel(void)
+{
+    int level = 1;
+    SL_RANDOM_DECL;
+
+    SL_RANDOM_INIT(SL_RANDOM_SEED);
+    
+    while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
+    return level;
+}
+
+void *N(SLCreate)(void)
+{
+    SkipListPtr  list;
+    int          i;
+
+    list           = SL_ALLOC(sizeof(*list));
+    if (!list) return NULL;
+    list->magic    = SL_LIST_MAGIC;
+    list->level    = 0;
+    list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
+    list->count    = 0;
+
+    for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
+    
+    return list;
+}
+
+int N(SLDestroy)(void *l)
+{
+    SkipListPtr   list  = (SkipListPtr)l;
+    SLEntryPtr    entry;
+    SLEntryPtr    next;
+
+    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
+
+    for (entry = list->head; entry; entry = next) {
+	if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
+	next         = entry->forward[0];
+	entry->magic = SL_FREED_MAGIC;
+	SL_FREE(entry);
+    }
+
+    list->magic = SL_FREED_MAGIC;
+    SL_FREE(list);
+    return 0;
+}
+
+static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
+{
+    SkipListPtr   list  = (SkipListPtr)l;
+    SLEntryPtr    entry;
+    int           i;
+
+    if (list->magic != SL_LIST_MAGIC) return NULL;
+
+    for (i = list->level, entry = list->head; i >= 0; i--) {
+	while (entry->forward[i] && entry->forward[i]->key < key)
+	    entry = entry->forward[i];
+	update[i] = entry;
+    }
+
+    return entry->forward[0];
+}
+
+int N(SLInsert)(void *l, unsigned long key, void *value)
+{
+    SkipListPtr   list  = (SkipListPtr)l;
+    SLEntryPtr    entry;
+    SLEntryPtr    update[SL_MAX_LEVEL + 1];
+    int           level;
+    int           i;
+
+    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
+
+    entry = SLLocate(list, key, update);
+
+    if (entry && entry->key == key) return 1; /* Already in list */
+
+
+    level = SLRandomLevel();
+    if (level > list->level) {
+	level = ++list->level;
+	update[level] = list->head;
+    }
+
+    entry = SLCreateEntry(level, key, value);
+
+				/* Fix up forward pointers */
+    for (i = 0; i <= level; i++) {
+	entry->forward[i]     = update[i]->forward[i];
+	update[i]->forward[i] = entry;
+    }
+
+    ++list->count;
+    return 0;			/* Added to table */
+}
+
+int N(SLDelete)(void *l, unsigned long key)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    SLEntryPtr    update[SL_MAX_LEVEL + 1];
+    SLEntryPtr    entry;
+    int           i;
+
+    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
+
+    entry = SLLocate(list, key, update);
+
+    if (!entry || entry->key != key) return 1; /* Not found */
+
+				/* Fix up forward pointers */
+    for (i = 0; i <= list->level; i++) {
+	if (update[i]->forward[i] == entry)
+	    update[i]->forward[i] = entry->forward[i];
+    }
+
+    entry->magic = SL_FREED_MAGIC;
+    SL_FREE(entry);
+
+    while (list->level && !list->head->forward[list->level]) --list->level;
+    --list->count;
+    return 0;
+}
+
+int N(SLLookup)(void *l, unsigned long key, void **value)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    SLEntryPtr    update[SL_MAX_LEVEL + 1];
+    SLEntryPtr    entry;
+
+    entry = SLLocate(list, key, update);
+
+    if (entry && entry->key == key) {
+	*value = entry;
+	return 0;
+    }
+    *value = NULL;
+    return -1;
+}
+
+int N(SLLookupNeighbors)(void *l, unsigned long key,
+			 unsigned long *prev_key, void **prev_value,
+			 unsigned long *next_key, void **next_value)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    SLEntryPtr    update[SL_MAX_LEVEL + 1];
+    SLEntryPtr    entry;
+    int           retcode = 0;
+
+    entry = SLLocate(list, key, update);
+
+    *prev_key   = *next_key   = key;
+    *prev_value = *next_value = NULL;
+	
+    if (update[0]) {
+	*prev_key   = update[0]->key;
+	*prev_value = update[0]->value;
+	++retcode;
+	if (update[0]->forward[0]) {
+	    *next_key   = update[0]->forward[0]->key;
+	    *next_value = update[0]->forward[0]->value;
+	    ++retcode;
+	}
+    }
+    return retcode;
+}
+
+int N(SLNext)(void *l, unsigned long *key, void **value)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    SLEntryPtr    entry;
+    
+    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
+
+    entry    = list->p0;
+
+    if (entry) {
+	list->p0 = entry->forward[0];
+	*key     = entry->key;
+	*value   = entry->value;
+	return 1;
+    }
+    list->p0 = NULL;
+    return 0;
+}
+
+int N(SLFirst)(void *l, unsigned long *key, void **value)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    
+    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
+    
+    list->p0 = list->head->forward[0];
+    return N(SLNext)(list, key, value);
+}
+
+/* Dump internal data structures for debugging. */
+void N(SLDump)(void *l)
+{
+    SkipListPtr   list = (SkipListPtr)l;
+    SLEntryPtr    entry;
+    int           i;
+    
+    if (list->magic != SL_LIST_MAGIC) {
+	printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
+	       list->magic, SL_LIST_MAGIC);
+	return;
+    }
+
+    printf("Level = %d, count = %d\n", list->level, list->count);
+    for (entry = list->head; entry; entry = entry->forward[0]) {
+	if (entry->magic != SL_ENTRY_MAGIC) {
+	    printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
+		   list->magic, SL_ENTRY_MAGIC);
+	}
+	printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
+	       entry, entry->key, entry->value, entry->levels);
+	for (i = 0; i < entry->levels; i++) {
+	    if (entry->forward[i]) {
+		printf("   %2d: %p <0x%08lx, %p>\n",
+		       i,
+		       entry->forward[i],
+		       entry->forward[i]->key,
+		       entry->forward[i]->value);
+	    } else {
+		printf("   %2d: %p\n", i, entry->forward[i]);
+	    }
+	}
+    }
+}
+
+#if SL_MAIN
+static void print(SkipListPtr list)
+{
+    unsigned long key;
+    void          *value;
+    
+    if (N(SLFirst)(list, &key, &value)) {
+	do {
+	    printf("key = %5lu, value = %p\n", key, value);
+	} while (N(SLNext)(list, &key, &value));
+    }
+}
+
+static double do_time(int size, int iter)
+{
+    SkipListPtr    list;
+    int            i, j;
+    unsigned long  keys[1000000];
+    unsigned long  previous;
+    unsigned long  key;
+    void           *value;
+    struct timeval start, stop;
+    double         usec;
+    SL_RANDOM_DECL;
+
+    SL_RANDOM_INIT(12345);
+    
+    list = N(SLCreate)();
+
+    for (i = 0; i < size; i++) {
+	keys[i] = SL_RANDOM;
+	N(SLInsert)(list, keys[i], NULL);
+    }
+
+    previous = 0;
+    if (N(SLFirst)(list, &key, &value)) {
+	do {
+	    if (key <= previous) {
+		printf( "%lu !< %lu\n", previous, key);
+	    }
+	    previous = key;
+	} while (N(SLNext)(list, &key, &value));
+    }
+    
+    gettimeofday(&start, NULL);
+    for (j = 0; j < iter; j++) {
+	for (i = 0; i < size; i++) {
+	    if (N(SLLookup)(list, keys[i], &value))
+		printf("Error %lu %d\n", keys[i], i);
+	}
+    }
+    gettimeofday(&stop, NULL);
+    
+    usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
+		    - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
+    
+    printf("%0.2f microseconds for list length %d\n", usec, size);
+
+    N(SLDestroy)(list);
+    
+    return usec;
+}
+
+static void print_neighbors(void *list, unsigned long key)
+{
+    unsigned long prev_key = 0;
+    unsigned long next_key = 0;
+    void          *prev_value;
+    void          *next_value;
+    int           retval;
+
+    retval = drmSLLookupNeighbors(list, key,
+				  &prev_key, &prev_value,
+				  &next_key, &next_value);
+    printf("Neighbors of %5lu: %d %5lu %5lu\n",
+	   key, retval, prev_key, next_key);
+}
+
+int main(void)
+{
+    SkipListPtr    list;
+    double         usec, usec2, usec3, usec4;
+
+    list = N(SLCreate)();
+    printf( "list at %p\n", list);
+
+    print(list);
+    printf("\n==============================\n\n");
+
+    N(SLInsert)(list, 123, NULL);
+    N(SLInsert)(list, 213, NULL);
+    N(SLInsert)(list, 50, NULL);
+    print(list);
+    printf("\n==============================\n\n");
+    
+    print_neighbors(list, 0);
+    print_neighbors(list, 50);
+    print_neighbors(list, 51);
+    print_neighbors(list, 123);
+    print_neighbors(list, 200);
+    print_neighbors(list, 213);
+    print_neighbors(list, 256);
+    printf("\n==============================\n\n");    
+    
+    N(SLDelete)(list, 50);
+    print(list);
+    printf("\n==============================\n\n");
+
+    N(SLDump)(list);
+    N(SLDestroy)(list);
+    printf("\n==============================\n\n");
+
+    usec  = do_time(100, 10000);
+    usec2 = do_time(1000, 500);
+    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
+	   1000.0/100.0, usec2 / usec);
+    
+    usec3 = do_time(10000, 50);
+    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
+	   10000.0/100.0, usec3 / usec);
+    
+    usec4 = do_time(100000, 4);
+    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
+	   100000.0/100.0, usec4 / usec);
+
+    return 0;
+}
+#endif