summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--libdrm/xf86drm.c1114
-rw-r--r--libdrm/xf86drmHash.c435
-rw-r--r--libdrm/xf86drmRandom.c219
-rw-r--r--libdrm/xf86drmSL.c490
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-24 18:14:00 +0000