aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDaryll Strauss1999-12-04 19:19:48 -0600
committerDaryll Strauss1999-12-04 19:19:48 -0600
commitb3a5766992019fc5f44cc9afd01b2617b76f47a7 (patch)
tree8c7d4209618d11e15253351a0689de007f0105fe
downloadexternal-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.tar.gz
external-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.tar.xz
external-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.zip
Initial revision
-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 @@
1/* xf86drm.c -- User-level interface to DRM device
2 * Created: Tue Jan 5 08:16:21 1999 by faith@precisioninsight.com
3 * Revised: Fri Jun 18 09:52:23 1999 by faith@precisioninsight.com
4 *
5 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
6 * All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25 * DEALINGS IN THE SOFTWARE.
26 *
27 * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drm.c,v 1.41 1999/06/21 14:31:20 faith Exp $
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drm.c,v 1.3 1999/06/27 14:08:19 dawes Exp $
29 *
30 */
31
32#ifdef XFree86Server
33# include "xf86.h"
34# include "xf86_OSproc.h"
35# include "xf86_ansic.h"
36# include "xf86Priv.h"
37# define _DRM_MALLOC xalloc
38# define _DRM_FREE xfree
39# ifndef XFree86LOADER
40# include <sys/stat.h>
41# include <sys/mman.h>
42# endif
43#else
44# include <stdio.h>
45# include <stdlib.h>
46# include <unistd.h>
47# include <string.h>
48# include <ctype.h>
49# include <fcntl.h>
50# include <errno.h>
51# include <signal.h>
52# include <sys/types.h>
53# include <sys/stat.h>
54# include <sys/ioctl.h>
55# include <sys/mman.h>
56# include <sys/time.h>
57# ifdef DRM_USE_MALLOC
58# define _DRM_MALLOC malloc
59# define _DRM_FREE free
60extern int xf86InstallSIGIOHandler(int fd, void (*f)(int));
61extern int xf86RemoveSIGIOHandler(int fd);
62# else
63# include <Xlibint.h>
64# define _DRM_MALLOC Xmalloc
65# define _DRM_FREE Xfree
66# endif
67#endif
68
69/* Not all systems have MAP_FAILED defined */
70#ifndef MAP_FAILED
71#define MAP_FAILED ((void *)-1)
72#endif
73
74#include <sys/sysmacros.h> /* for makedev() */
75#include "xf86drm.h"
76#include "drm.h"
77
78static void *drmHashTable = NULL; /* Context switch callbacks */
79
80typedef struct drmHashEntry {
81 int fd;
82 void (*f)(int, void *, void *);
83 void *tagTable;
84} drmHashEntry;
85
86void *drmMalloc(int size)
87{
88 void *pt;
89 if ((pt = _DRM_MALLOC(size))) memset(pt, 0, size);
90 return pt;
91}
92
93void drmFree(void *pt)
94{
95 if (pt) _DRM_FREE(pt);
96}
97
98static char *drmStrdup(const char *s)
99{
100 return s ? strdup(s) : NULL;
101}
102
103
104/* drm_lookup searches file for a line tagged with name, and returns the
105 value for that tag. If busid is NULL, the file format is that used for
106 /proc/devices and /proc/misc, or the first part of /proc/drm/devices:
107
108 <value> <whitespace> <tag>
109
110 If the busid is non-NULL, the file format is the extended format used
111 for /proc/drm/devices:
112
113 <value> <whitespace> <name> <whitespace> <busid>
114
115 If both name and busid are non-NULL, both must match. If either is
116 NULL, then the other is matched.
117*/
118
119static int drm_lookup(const char *file, const char *name, const char *busid)
120{
121 FILE *str;
122 char buf[128];
123 char *pt;
124 int name_match;
125 int busid_match;
126 char *namept = NULL;
127 char *busidpt = NULL;
128
129 if (!(str = fopen(file, "r"))) return DRM_ERR_NO_DEVICE;
130 while (fgets(buf, sizeof(buf)-1, str)) {
131 buf[sizeof(buf)-1] = '\0';
132 for (pt = buf; *pt && isspace(*pt); ++pt); /* skip whitespace */
133 for (; *pt && !isspace(*pt); ++pt); /* next space or null */
134 if (isspace(pt[0]) && pt[1]) {
135 pt++;
136 for (; *pt && isspace(*pt); ++pt); /* skip whitespace */
137 namept = pt;
138 for (; *pt && !isspace(*pt); ++pt); /* next space or null */
139 if (isspace(pt[0]) && pt[1]) { /* busid present */
140 *pt = '\0'; /* proper termination */
141 pt++;
142 for (; *pt && isspace(*pt); ++pt); /* skip whitespace */
143 busidpt = pt;
144 for (; *pt && !isspace(*pt); ++pt); /* next space or null */
145 }
146 *pt = '\0'; /* proper termination */
147 name_match = name ? 0 : 1; /* match if we don't care */
148 busid_match = busid ? 0 : 1; /* match if we don't care */
149 if (name && namept && !strcmp(name, namept)) ++name_match;
150 if (busid && busidpt && !strcmp(busid, busidpt)) ++busid_match;
151 if (name_match && busid_match) {
152 fclose(str);
153 return atoi(buf); /* stops at whitespace */
154 }
155 }
156 }
157 fclose(str);
158 return DRM_ERR_NO_DEVICE;
159}
160
161static unsigned long drmGetKeyFromFd(int fd)
162{
163#ifdef XFree86LOADER
164 struct xf86stat st;
165#else
166 struct stat st;
167#endif
168
169 st.st_rdev = 0;
170 fstat(fd, &st);
171 return st.st_rdev;
172}
173
174static drmHashEntry *drmGetEntry(int fd)
175{
176 unsigned long key = drmGetKeyFromFd(fd);
177 void *value;
178 drmHashEntry *entry;
179
180 if (!drmHashTable) drmHashTable = drmHashCreate();
181
182 if (drmHashLookup(drmHashTable, key, &value)) {
183 entry = drmMalloc(sizeof(*entry));
184 entry->fd = fd;
185 entry->f = NULL;
186 entry->tagTable = drmHashCreate();
187 drmHashInsert(drmHashTable, key, entry);
188 } else {
189 entry = value;
190 }
191 return entry;
192}
193
194/* drm_open is used to open the /dev/drm device */
195
196static int drm_open(const char *file)
197{
198 int fd = open(file, O_RDWR, 0);
199
200 if (fd >= 0) return fd;
201 return -errno;
202}
203
204/* drmAvailable looks for /proc/drm, and returns 1 if it is present. */
205
206int drmAvailable(void)
207{
208 if (!access(DRM_PROC_DRM, R_OK)) return 1;
209 return 0;
210}
211
212/* drmGetMajor tries to find the major device number for /dev/drm by
213 searching /proc/devices. A negative value is returned on error. */
214
215static int drmGetMajor(void)
216{
217 int major;
218
219 if (!drmAvailable()) return DRM_ERR_NO_DEVICE;
220
221 if ((major = drm_lookup(DRM_PROC_DEVICES, DRM_NAME, NULL)) >= 0)
222 return major;
223
224 return DRM_ERR_NO_DEVICE;
225}
226
227/* drmGetMinor tries to find the minor device number for name by looking in
228 /proc/drm/devices. A negative value is retruned on error. */
229
230static int drmGetMinor(const char *name, const char *busid)
231{
232 int minor;
233 char buf[128];
234
235 if (!drmAvailable()) return DRM_ERR_NO_DEVICE;
236
237 sprintf(buf, "/proc/%s/%s", DRM_NAME, DRM_DEVICES);
238
239 if ((minor = drm_lookup(buf, name, busid))) return minor;
240 return 0;
241}
242
243
244/* drmOpen looks up the specified name and/or busid in /proc/drm/devices,
245 and opens the device found. The entry in /dev is created if necessary
246 (and if root). A file descriptor is returned. On error, the return
247 value is negative. */
248
249static int drmOpen(const char *name, const char *busid)
250{
251#ifdef XFree86LOADER
252 struct xf86stat st;
253#else
254 struct stat st;
255#endif
256 char path[128];
257 int major;
258 int minor;
259 dev_t dev;
260
261 if (!drmAvailable()) return DRM_ERR_NO_DEVICE;
262 if ((major = drmGetMajor()) < 0) return major;
263 if ((minor = drmGetMinor(name,busid)) < 0) return minor;
264 dev = makedev(major, minor);
265
266 if (!minor) {
267 sprintf(path, "/dev/%s", DRM_NAME );
268 } else {
269 sprintf(path, "/dev/%s%d", DRM_NAME, minor-1 );
270 }
271
272 /* Check device major/minor for match */
273 if (!access(path, F_OK)) {
274 if (stat(path, &st)) return DRM_ERR_NO_ACCESS;
275 if (st.st_rdev == dev) {
276#if defined(XFree86Server)
277 chmod(path,
278 xf86ConfigDRI.mode ? xf86ConfigDRI.mode : DRM_DEV_MODE);
279 chown(path, DRM_DEV_UID,
280 xf86ConfigDRI.group ? xf86ConfigDRI.group : DRM_DEV_GID);
281#endif
282#if defined(DRM_USE_MALLOC)
283 chmod(path, DRM_DEV_MODE);
284 chown(path, DRM_DEV_UID, DRM_DEV_GID);
285#endif
286 return drm_open(path);
287 }
288 }
289
290 /* Doesn't exist or match failed, so we
291 have to be root to create it. */
292 if (geteuid()) return DRM_ERR_NOT_ROOT;
293 remove(path);
294 if (mknod(path, S_IFCHR | DRM_DEV_MODE, dev)) {
295 remove(path);
296 return DRM_ERR_NOT_ROOT;
297 }
298#if defined(XFree86Server)
299 chmod(path, xf86ConfigDRI.mode ? xf86ConfigDRI.mode : DRM_DEV_MODE);
300 chown(path, DRM_DEV_UID,
301 xf86ConfigDRI.group ? xf86ConfigDRI.group : DRM_DEV_GID);
302#endif
303#if defined(DRM_USE_MALLOC)
304 chmod(path, DRM_DEV_MODE);
305 chown(path, DRM_DEV_UID, DRM_DEV_GID);
306#endif
307 return drm_open(path);
308}
309
310/* drmOpenDRM returns a file descriptor for the main /dev/drm control
311 device. The entry in /dev is created if necessary (and if root). A
312 file descriptor is returned. On error, the return value is negative. */
313
314int drmOpenDRM(void)
315{
316 return drmOpen(DRM_NAME, NULL);
317}
318
319
320/* drmClose closes the file descriptor returned from drmOpen. */
321
322int drmCloseDRM(int fd)
323{
324 return close(fd);
325}
326
327void drmFreeVersion(drmVersionPtr v)
328{
329 if (!v) return;
330 if (v->name) drmFree(v->name);
331 if (v->date) drmFree(v->date);
332 if (v->desc) drmFree(v->desc);
333 drmFree(v);
334}
335
336static void drmFreeKernelVersion(drm_version_t *v)
337{
338 if (!v) return;
339 if (v->name) drmFree(v->name);
340 if (v->date) drmFree(v->date);
341 if (v->desc) drmFree(v->desc);
342 drmFree(v);
343}
344
345static void drmCopyVersion(drmVersionPtr d, drm_version_t *s)
346{
347 d->version_major = s->version_major;
348 d->version_minor = s->version_minor;
349 d->version_patchlevel = s->version_patchlevel;
350 d->name_len = s->name_len;
351 d->name = drmStrdup(s->name);
352 d->date_len = s->date_len;
353 d->date = drmStrdup(s->date);
354 d->desc_len = s->desc_len;
355 d->desc = drmStrdup(s->desc);
356}
357
358/* drmVersion obtains the version information via an ioctl. Similar
359 * information is available via /proc/drm. */
360
361drmVersionPtr drmGetVersion(int fd)
362{
363 drmVersionPtr retval;
364 drm_version_t *version = drmMalloc(sizeof(*version));
365
366 /* First, get the lengths */
367 version->name_len = 0;
368 version->name = NULL;
369 version->date_len = 0;
370 version->date = NULL;
371 version->desc_len = 0;
372 version->desc = NULL;
373
374 if (ioctl(fd, DRM_IOCTL_VERSION, version)) {
375 drmFreeKernelVersion(version);
376 return NULL;
377 }
378
379 /* Now, allocate space and get the data */
380 if (version->name_len)
381 version->name = drmMalloc(version->name_len + 1);
382 if (version->date_len)
383 version->date = drmMalloc(version->date_len + 1);
384 if (version->desc_len)
385 version->desc = drmMalloc(version->desc_len + 1);
386
387 if (ioctl(fd, DRM_IOCTL_VERSION, version)) {
388 drmFreeKernelVersion(version);
389 return NULL;
390 }
391
392 /* The results might not be null-terminated
393 strings, so terminate them. */
394
395 if (version->name_len) version->name[version->name_len] = '\0';
396 if (version->date_len) version->date[version->date_len] = '\0';
397 if (version->desc_len) version->desc[version->desc_len] = '\0';
398
399 /* Now, copy it all back into the
400 client-visible data structure... */
401 retval = drmMalloc(sizeof(*retval));
402 drmCopyVersion(retval, version);
403 drmFreeKernelVersion(version);
404 return retval;
405}
406
407void drmFreeVersionList(drmListPtr list)
408{
409 int i;
410
411 if (!list) return;
412 if (list->version) {
413 for (i = 0; i < list->count; i++) {
414 if (list->version[i].name) drmFree(list->version[i].name);
415 if (list->version[i].date) drmFree(list->version[i].date);
416 if (list->version[i].desc) drmFree(list->version[i].desc);
417
418 }
419 drmFree(list->version);
420 }
421 if (list->capability) drmFree(list->capability);
422 drmFree(list);
423}
424
425static void drmFreeKernelVersionList(drm_list_t *list)
426{
427 int i;
428
429 if (!list) return;
430 if (list->version) {
431 for (i = 0; i < list->count; i++) {
432 if (list->version[i].name) drmFree(list->version[i].name);
433 if (list->version[i].date) drmFree(list->version[i].date);
434 if (list->version[i].desc) drmFree(list->version[i].desc);
435
436 }
437 drmFree(list->version);
438 }
439 drmFree(list);
440}
441
442/* drmList obtains a list of all drivers and capabilities via an ioctl. */
443
444drmListPtr drmGetVersionList(int fd)
445{
446 drmListPtr retval;
447 drm_list_t *list = drmMalloc(sizeof(*list));
448 int i;
449
450 list->count = 0;
451
452 /* First, get the count */
453
454 if (ioctl(fd, DRM_IOCTL_LIST, list)) {
455 drmFreeKernelVersionList(list);
456 return NULL;
457 }
458
459 /* Next, get the version sizes */
460 for (i = 0; i < list->count; i++) {
461 list->version
462 = drmMalloc(list->count * sizeof(*list->version));
463 list->version[i].name_len = 0;
464 list->version[i].name = NULL;
465 list->version[i].date_len = 0;
466 list->version[i].date = NULL;
467 list->version[i].desc_len = 0;
468 list->version[i].desc = NULL;
469 }
470
471 if (ioctl(fd, DRM_IOCTL_LIST, list)) {
472 drmFreeKernelVersionList(list);
473 return NULL;
474 }
475
476 /* Now, allocate space and get the data */
477 for (i = 0; i < list->count; i++) {
478 if (list->version[i].name_len)
479 list->version[i].name = drmMalloc(list->version[i].name_len + 1);
480 if (list->version[i].date_len)
481 list->version[i].date = drmMalloc(list->version[i].date_len + 1);
482 if (list->version[i].desc_len)
483 list->version[i].desc = drmMalloc(list->version[i].desc_len + 1);
484 }
485
486 if (ioctl(fd, DRM_IOCTL_LIST, list)) {
487 drmFreeKernelVersionList(list);
488 return NULL;
489 }
490
491 /* The results might not be null-terminated
492 strings, so terminate them. */
493
494 for (i = 0; i < list->count; i++) {
495 if (list->version[i].name_len)
496 list->version[i].name[list->version[i].name_len] = '\0';
497 if (list->version[i].date_len)
498 list->version[i].date[list->version[i].date_len] = '\0';
499 if (list->version[i].desc_len)
500 list->version[i].desc[list->version[i].desc_len] = '\0';
501 }
502
503 /* Now, copy it all back into the
504 client-visible data structure... */
505 retval = drmMalloc(sizeof(*retval));
506 retval->count = list->count;
507 retval->version = drmMalloc(list->count * sizeof(*retval->version));
508 retval->capability = drmMalloc(list->count * sizeof(*retval->capability));
509 for (i = 0; i < list->count; i++) {
510 drmCopyVersion(&retval->version[i], &list->version[i]);
511 }
512 drmFreeKernelVersionList(list);
513 return retval;
514}
515
516int drmCreateSub(int fd, const char *name, const char *busid)
517{
518 drm_request_t request;
519
520 request.device_name = name;
521 request.device_busid = busid;
522 if (ioctl(fd, DRM_IOCTL_CREATE, &request)) {
523 return -errno;
524 }
525 return 0;
526}
527
528int drmDestroySub(int fd, const char *busid)
529{
530 drm_request_t request;
531
532 request.device_busid = busid;
533 request.device_major = drmGetMajor();
534 request.device_minor = drmGetMinor(NULL, busid);
535 if (ioctl(fd, DRM_IOCTL_DESTROY, &request)) {
536 return -errno;
537 }
538 return 0;
539}
540
541int drmGetMagic(int fd, drmMagicPtr magic)
542{
543 drm_auth_t auth;
544
545 *magic = 0;
546 if (ioctl(fd, DRM_IOCTL_GET_MAGIC, &auth)) return -errno;
547 *magic = auth.magic;
548 return 0;
549}
550
551int drmAuthMagic(int fd, drmMagic magic)
552{
553 drm_auth_t auth;
554
555 auth.magic = magic;
556 if (ioctl(fd, DRM_IOCTL_AUTH_MAGIC, &auth)) return -errno;
557 return 0;
558}
559
560int drmAddMap(int fd,
561 drmHandle offset,
562 drmSize size,
563 drmMapType type,
564 drmMapFlags flags,
565 drmHandlePtr handle)
566{
567 drm_map_t map;
568
569 map.offset = offset;
570 map.size = size;
571 map.handle = 0;
572 map.type = type;
573 map.flags = flags;
574 if (ioctl(fd, DRM_IOCTL_ADD_MAP, &map)) return -errno;
575 if (handle) *handle = (drmHandle)map.handle;
576 return 0;
577}
578
579int drmAddBufs(int fd, int count, int size, int flags)
580{
581 drm_buf_desc_t request;
582
583 request.count = count;
584 request.size = size;
585 request.low_mark = 0;
586 request.high_mark = 0;
587 request.flags = flags;
588 if (ioctl(fd, DRM_IOCTL_ADD_BUFS, &request)) return -errno;
589 return request.count;
590}
591
592int drmMarkBufs(int fd, double low, double high)
593{
594 drm_buf_info_t info;
595 int i;
596
597 info.count = 0;
598 info.list = NULL;
599
600 if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) return -EINVAL;
601
602 if (!info.count) return -EINVAL;
603
604 if (!(info.list = drmMalloc(info.count * sizeof(*info.list))))
605 return -ENOMEM;
606
607 if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) {
608 int retval = -errno;
609 drmFree(info.list);
610 return retval;
611 }
612
613 for (i = 0; i < info.count; i++) {
614 info.list[i].low_mark = low * info.list[i].count;
615 info.list[i].high_mark = high * info.list[i].count;
616 if (ioctl(fd, DRM_IOCTL_MARK_BUFS, &info.list[i])) {
617 int retval = -errno;
618 drmFree(info.list);
619 return retval;
620 }
621 }
622 drmFree(info.list);
623
624 return 0;
625}
626
627int drmFreeBufs(int fd, int count, int *list)
628{
629 drm_buf_free_t request;
630
631 request.count = count;
632 request.list = list;
633 if (ioctl(fd, DRM_IOCTL_FREE_BUFS, &request)) return -errno;
634 return 0;
635}
636
637int drmOpenSub(const char *busid)
638{
639 return drmOpen(NULL, busid);
640}
641
642int drmCloseSub(int fd)
643{
644 unsigned long key = drmGetKeyFromFd(fd);
645 drmHashEntry *entry = drmGetEntry(fd);
646
647 drmHashDestroy(entry->tagTable);
648 entry->fd = 0;
649 entry->f = NULL;
650 entry->tagTable = NULL;
651
652 drmHashDelete(drmHashTable, key);
653 drmFree(entry);
654
655 return close(fd);
656}
657
658int drmMap(int fd,
659 drmHandle handle,
660 drmSize size,
661 drmAddressPtr address)
662{
663 if (fd < 0) return -EINVAL;
664 *address = mmap(0, size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, handle);
665 if (*address == MAP_FAILED) return -errno;
666 return 0;
667}
668
669int drmUnmap(drmAddress address, drmSize size)
670{
671 return munmap(address, size);
672}
673
674drmBufInfoPtr drmGetBufInfo(int fd)
675{
676 drm_buf_info_t info;
677 drmBufInfoPtr retval;
678 int i;
679
680 info.count = 0;
681 info.list = NULL;
682
683 if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) return NULL;
684
685 if (info.count) {
686 if (!(info.list = drmMalloc(info.count * sizeof(*info.list))))
687 return NULL;
688
689 if (ioctl(fd, DRM_IOCTL_INFO_BUFS, &info)) {
690 drmFree(info.list);
691 return NULL;
692 }
693 /* Now, copy it all back into the
694 client-visible data structure... */
695 retval = drmMalloc(sizeof(*retval));
696 retval->count = info.count;
697 retval->list = drmMalloc(info.count * sizeof(*retval->list));
698 for (i = 0; i < info.count; i++) {
699 retval->list[i].count = info.list[i].count;
700 retval->list[i].size = info.list[i].size;
701 retval->list[i].low_mark = info.list[i].low_mark;
702 retval->list[i].high_mark = info.list[i].high_mark;
703 }
704 drmFree(info.list);
705 return retval;
706 }
707 return NULL;
708}
709
710drmBufMapPtr drmMapBufs(int fd)
711{
712 drm_buf_map_t bufs;
713 drmBufMapPtr retval;
714 int i;
715
716 bufs.count = 0;
717 bufs.list = NULL;
718 if (ioctl(fd, DRM_IOCTL_MAP_BUFS, &bufs)) return NULL;
719
720 if (bufs.count) {
721 if (!(bufs.list = drmMalloc(bufs.count * sizeof(*bufs.list))))
722 return NULL;
723
724 if (ioctl(fd, DRM_IOCTL_MAP_BUFS, &bufs)) {
725 drmFree(bufs.list);
726 return NULL;
727 }
728 /* Now, copy it all back into the
729 client-visible data structure... */
730 retval = drmMalloc(sizeof(*retval));
731 retval->count = bufs.count;
732 retval->list = drmMalloc(bufs.count * sizeof(*retval->list));
733 for (i = 0; i < bufs.count; i++) {
734 retval->list[i].idx = bufs.list[i].idx;
735 retval->list[i].total = bufs.list[i].total;
736 retval->list[i].used = 0;
737 retval->list[i].address = bufs.list[i].address;
738 }
739 return retval;
740 }
741 return NULL;
742}
743
744int drmUnmapBufs(drmBufMapPtr bufs)
745{
746 int i;
747
748 for (i = 0; i < bufs->count; i++) {
749 munmap(bufs->list[i].address, bufs->list[i].total);
750 }
751 return 0;
752}
753
754int drmDMA(int fd, drmDMAReqPtr request)
755{
756 drm_dma_t dma;
757
758 /* Copy to hidden structure */
759 dma.context = request->context;
760 dma.send_count = request->send_count;
761 dma.send_indices = request->send_list;
762 dma.send_sizes = request->send_sizes;
763 dma.flags = request->flags;
764 dma.request_count = request->request_count;
765 dma.request_size = request->request_size;
766 dma.request_indices = request->request_list;
767 dma.request_sizes = request->request_sizes;
768 if (ioctl(fd, DRM_IOCTL_DMA, &dma)) return -errno;
769 request->granted_count = dma.granted_count;
770
771 return 0;
772}
773
774int drmGetLock(int fd, drmContext context, drmLockFlags flags)
775{
776 drm_lock_t lock;
777
778 lock.context = context;
779 lock.flags = 0;
780 if (flags & DRM_LOCK_READY) lock.flags |= _DRM_LOCK_READY;
781 if (flags & DRM_LOCK_QUIESCENT) lock.flags |= _DRM_LOCK_QUIESCENT;
782 if (flags & DRM_LOCK_FLUSH) lock.flags |= _DRM_LOCK_FLUSH;
783 if (flags & DRM_LOCK_FLUSH_ALL) lock.flags |= _DRM_LOCK_FLUSH_ALL;
784 if (flags & DRM_HALT_ALL_QUEUES) lock.flags |= _DRM_HALT_ALL_QUEUES;
785 if (flags & DRM_HALT_CUR_QUEUES) lock.flags |= _DRM_HALT_CUR_QUEUES;
786
787 while (ioctl(fd, DRM_IOCTL_LOCK, &lock))
788 ;
789 return 0;
790}
791
792int drmUnlock(int fd, drmContext context)
793{
794 drm_lock_t lock;
795
796 lock.context = context;
797 lock.flags = 0;
798 return ioctl(fd, DRM_IOCTL_UNLOCK, &lock);
799}
800
801drmContextPtr drmGetReservedContextList(int fd, int *count)
802{
803 drm_ctx_res_t res;
804 drm_ctx_t *list;
805 drmContextPtr retval;
806 int i;
807
808 res.count = 0;
809 res.contexts = NULL;
810 if (ioctl(fd, DRM_IOCTL_RES_CTX, &res)) return NULL;
811
812 if (!res.count) return NULL;
813
814 if (!(list = drmMalloc(res.count * sizeof(*list)))) return NULL;
815 if (!(retval = drmMalloc(res.count * sizeof(*retval)))) {
816 drmFree(list);
817 return NULL;
818 }
819
820 res.contexts = list;
821 if (ioctl(fd, DRM_IOCTL_RES_CTX, &res)) return NULL;
822
823 for (i = 0; i < res.count; i++) retval[i] = list[i].handle;
824 drmFree(list);
825
826 *count = res.count;
827 return retval;
828}
829
830void drmFreeReservedContextList(drmContextPtr pt)
831{
832 drmFree(pt);
833}
834
835int drmCreateContext(int fd, drmContextPtr handle)
836{
837 drm_ctx_t ctx;
838
839 ctx.flags = 0; /* Modified with functions below */
840 if (ioctl(fd, DRM_IOCTL_ADD_CTX, &ctx)) return -errno;
841 *handle = ctx.handle;
842 return 0;
843}
844
845int drmSwitchToContext(int fd, drmContext context)
846{
847 drm_ctx_t ctx;
848
849 ctx.handle = context;
850 if (ioctl(fd, DRM_IOCTL_SWITCH_CTX, &ctx)) return -errno;
851 return 0;
852}
853
854int drmSetContextFlags(int fd, drmContext context, drmContextFlags flags)
855{
856 drm_ctx_t ctx;
857
858 /* Context preserving means that no context
859 switched are done between DMA buffers
860 from one context and the next. This is
861 suitable for use in the X server (which
862 promises to maintain hardware context,
863 or in the client-side library when
864 buffers are swapped on behalf of two
865 threads. */
866 ctx.handle = context;
867 ctx.flags = 0;
868 if (flags & DRM_CONTEXT_PRESERVED) ctx.flags |= _DRM_CONTEXT_PRESERVED;
869 if (flags & DRM_CONTEXT_2DONLY) ctx.flags |= _DRM_CONTEXT_2DONLY;
870 if (ioctl(fd, DRM_IOCTL_MOD_CTX, &ctx)) return -errno;
871 return 0;
872}
873
874int drmGetContextFlags(int fd, drmContext context, drmContextFlagsPtr flags)
875{
876 drm_ctx_t ctx;
877
878 ctx.handle = context;
879 if (ioctl(fd, DRM_IOCTL_GET_CTX, &ctx)) return -errno;
880 *flags = 0;
881 if (ctx.flags & _DRM_CONTEXT_PRESERVED) *flags |= DRM_CONTEXT_PRESERVED;
882 if (ctx.flags & _DRM_CONTEXT_2DONLY) *flags |= DRM_CONTEXT_2DONLY;
883 return 0;
884}
885
886int drmDestroyContext(int fd, drmContext handle)
887{
888 drm_ctx_t ctx;
889 ctx.handle = handle;
890 if (ioctl(fd, DRM_IOCTL_RM_CTX, &ctx)) return -errno;
891 return 0;
892}
893
894int drmCreateDrawable(int fd, drmDrawablePtr handle)
895{
896 drm_draw_t draw;
897 if (ioctl(fd, DRM_IOCTL_ADD_DRAW, &draw)) return -errno;
898 *handle = draw.handle;
899 return 0;
900}
901
902int drmDestroyDrawable(int fd, drmDrawable handle)
903{
904 drm_draw_t draw;
905 draw.handle = handle;
906 if (ioctl(fd, DRM_IOCTL_RM_DRAW, &draw)) return -errno;
907 return 0;
908}
909
910int drmError(int err, const char *label)
911{
912 switch (err) {
913 case DRM_ERR_NO_DEVICE: fprintf(stderr, "%s: no device\n", label); break;
914 case DRM_ERR_NO_ACCESS: fprintf(stderr, "%s: no access\n", label); break;
915 case DRM_ERR_NOT_ROOT: fprintf(stderr, "%s: not root\n", label); break;
916 case DRM_ERR_INVALID: fprintf(stderr, "%s: invalid args\n", label);break;
917 default:
918 if (err < 0) err = -err;
919 fprintf( stderr, "%s: error %d (%s)\n", label, err, strerror(err) );
920 break;
921 }
922
923 return 1;
924}
925
926int drmCtlAddCommand(int fd, drmCtlDesc desc, int count, int *inst)
927{
928 drm_control_t ctl;
929
930 ctl.func = DRM_ADD_COMMAND;
931 ctl.irq = 0;
932 ctl.count = count;
933 ctl.inst = inst;
934
935 switch (desc) {
936 case DRM_IH_PRE_INST: ctl.desc = _DRM_IH_PRE_INST; break;
937 case DRM_IH_POST_INST: ctl.desc = _DRM_IH_POST_INST; break;
938 case DRM_IH_SERVICE: ctl.desc = _DRM_IH_SERVICE; break;
939 case DRM_IH_PRE_UNINST: ctl.desc = _DRM_IH_PRE_UNINST; break;
940 case DRM_IH_POST_UNINST: ctl.desc = _DRM_IH_POST_UNINST; break;
941 case DRM_DMA_DISPATCH: ctl.desc = _DRM_DMA_DISPATCH; break;
942 case DRM_DMA_READY: ctl.desc = _DRM_DMA_READY; break;
943 case DRM_DMA_IS_READY: ctl.desc = _DRM_DMA_IS_READY; break;
944 case DRM_DMA_QUIESCENT: ctl.desc = _DRM_DMA_QUIESCENT; break;
945 default:
946 return -EINVAL;
947 }
948
949 if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
950 return 0;
951}
952
953int drmCtlRemoveCommands(int fd)
954{
955 drm_control_t ctl;
956 drm_desc_t i;
957
958 for (i = 0; i < DRM_DESC_MAX; i++) {
959 ctl.func = DRM_RM_COMMAND;
960 ctl.desc = i;
961 ctl.irq = 0;
962 ctl.count = 0;
963 ctl.inst = NULL;
964 ioctl(fd, DRM_IOCTL_CONTROL, &ctl);
965 }
966 return 0;
967}
968
969int drmCtlInstHandler(int fd, int irq)
970{
971 drm_control_t ctl;
972
973 ctl.func = DRM_INST_HANDLER;
974 ctl.desc = 0; /* unused */
975 ctl.irq = irq;
976 ctl.count = 0;
977 ctl.inst = NULL;
978 if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
979 return 0;
980}
981
982int drmCtlUninstHandler(int fd)
983{
984 drm_control_t ctl;
985
986 ctl.func = DRM_UNINST_HANDLER;
987 ctl.desc = 0; /* unused */
988 ctl.irq = 0;
989 ctl.count = 0;
990 ctl.inst = NULL;
991 if (ioctl(fd, DRM_IOCTL_CONTROL, &ctl)) return -errno;
992 return 0;
993}
994
995int drmFinish(int fd, int context, drmLockFlags flags)
996{
997 drm_lock_t lock;
998
999 lock.context = context;
1000 lock.flags = 0;
1001 if (flags & DRM_LOCK_READY) lock.flags |= _DRM_LOCK_READY;
1002 if (flags & DRM_LOCK_QUIESCENT) lock.flags |= _DRM_LOCK_QUIESCENT;
1003 if (flags & DRM_LOCK_FLUSH) lock.flags |= _DRM_LOCK_FLUSH;
1004 if (flags & DRM_LOCK_FLUSH_ALL) lock.flags |= _DRM_LOCK_FLUSH_ALL;
1005 if (flags & DRM_HALT_ALL_QUEUES) lock.flags |= _DRM_HALT_ALL_QUEUES;
1006 if (flags & DRM_HALT_CUR_QUEUES) lock.flags |= _DRM_HALT_CUR_QUEUES;
1007 if (ioctl(fd, DRM_IOCTL_FINISH, &lock)) return -errno;
1008 return 0;
1009}
1010
1011int drmGetInterruptFromBusID(int fd, int busnum, int devnum, int funcnum)
1012{
1013 drm_irq_busid_t p;
1014
1015 p.busnum = busnum;
1016 p.devnum = devnum;
1017 p.funcnum = funcnum;
1018 if (ioctl(fd, DRM_IOCTL_IRQ_BUSID, &p)) return -errno;
1019 return p.irq;
1020}
1021
1022int drmAddContextTag(int fd, drmContext context, void *tag)
1023{
1024 drmHashEntry *entry = drmGetEntry(fd);
1025
1026 if (drmHashInsert(entry->tagTable, context, tag)) {
1027 drmHashDelete(entry->tagTable, context);
1028 drmHashInsert(entry->tagTable, context, tag);
1029 }
1030 return 0;
1031}
1032
1033int drmDelContextTag(int fd, drmContext context)
1034{
1035 drmHashEntry *entry = drmGetEntry(fd);
1036
1037 return drmHashDelete(entry->tagTable, context);
1038}
1039
1040void *drmGetContextTag(int fd, drmContext context)
1041{
1042 drmHashEntry *entry = drmGetEntry(fd);
1043 void *value;
1044
1045 if (drmHashLookup(entry->tagTable, context, &value)) return NULL;
1046
1047 return value;
1048}
1049
1050#if defined(XFree86Server) || defined(DRM_USE_MALLOC)
1051static void drmSIGIOHandler(int interrupt)
1052{
1053 unsigned long key;
1054 void *value;
1055 ssize_t count;
1056 drm_ctx_t ctx;
1057 typedef void (*_drmCallback)(int, void *, void *);
1058 char buf[256];
1059 drmContext old;
1060 drmContext new;
1061 void *oldctx;
1062 void *newctx;
1063 char *pt;
1064 drmHashEntry *entry;
1065
1066 if (!drmHashTable) return;
1067 if (drmHashFirst(drmHashTable, &key, &value)) {
1068 entry = value;
1069 do {
1070#if 0
1071 fprintf(stderr, "Trying %d\n", entry->fd);
1072#endif
1073 if ((count = read(entry->fd, buf, sizeof(buf)))) {
1074 buf[count] = '\0';
1075#if 0
1076 fprintf(stderr, "Got %s\n", buf);
1077#endif
1078
1079 for (pt = buf; *pt != ' '; ++pt); /* Find first space */
1080 ++pt;
1081 old = strtol(pt, &pt, 0);
1082 new = strtol(pt, NULL, 0);
1083 oldctx = drmGetContextTag(entry->fd, old);
1084 newctx = drmGetContextTag(entry->fd, new);
1085#if 0
1086 fprintf(stderr, "%d %d %p %p\n", old, new, oldctx, newctx);
1087#endif
1088 ((_drmCallback)entry->f)(entry->fd, oldctx, newctx);
1089 ctx.handle = new;
1090 ioctl(entry->fd, DRM_IOCTL_NEW_CTX, &ctx);
1091 }
1092 } while (drmHashNext(drmHashTable, &key, &value));
1093 }
1094}
1095
1096int drmInstallSIGIOHandler(int fd, void (*f)(int, void *, void *))
1097{
1098 drmHashEntry *entry;
1099
1100 entry = drmGetEntry(fd);
1101 entry->f = f;
1102
1103 return xf86InstallSIGIOHandler(fd, drmSIGIOHandler);
1104}
1105
1106int drmRemoveSIGIOHandler(int fd)
1107{
1108 drmHashEntry *entry = drmGetEntry(fd);
1109
1110 entry->f = NULL;
1111
1112 return xf86RemoveSIGIOHandler(fd);
1113}
1114#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 @@
1/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
2 * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
3 * Revised: Thu Jun 3 16:11:06 1999 by faith@precisioninsight.com
4 *
5 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
6 * All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25 * DEALINGS IN THE SOFTWARE.
26 *
27 * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.3 1999/06/07 13:01:42 faith Exp $
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmHash.c,v 1.1 1999/06/14 07:32:02 dawes Exp $
29 *
30 * DESCRIPTION
31 *
32 * This file contains a straightforward implementation of a fixed-sized
33 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
34 * collision resolution. There are two potentially interesting things
35 * about this implementation:
36 *
37 * 1) The table is power-of-two sized. Prime sized tables are more
38 * traditional, but do not have a significant advantage over power-of-two
39 * sized table, especially when double hashing is not used for collision
40 * resolution.
41 *
42 * 2) The hash computation uses a table of random integers [Hanson97,
43 * pp. 39-41].
44 *
45 * FUTURE ENHANCEMENTS
46 *
47 * With a table size of 512, the current implementation is sufficient for a
48 * few hundred keys. Since this is well above the expected size of the
49 * tables for which this implementation was designed, the implementation of
50 * dynamic hash tables was postponed until the need arises. A common (and
51 * naive) approach to dynamic hash table implementation simply creates a
52 * new hash table when necessary, rehashes all the data into the new table,
53 * and destroys the old table. The approach in [Larson88] is superior in
54 * two ways: 1) only a portion of the table is expanded when needed,
55 * distributing the expansion cost over several insertions, and 2) portions
56 * of the table can be locked, enabling a scalable thread-safe
57 * implementation.
58 *
59 * REFERENCES
60 *
61 * [Hanson97] David R. Hanson. C Interfaces and Implementations:
62 * Techniques for Creating Reusable Software. Reading, Massachusetts:
63 * Addison-Wesley, 1997.
64 *
65 * [Knuth73] Donald E. Knuth. The Art of Computer Programming. Volume 3:
66 * Sorting and Searching. Reading, Massachusetts: Addison-Wesley, 1973.
67 *
68 * [Larson88] Per-Ake Larson. "Dynamic Hash Tables". CACM 31(4), April
69 * 1988, pp. 446-457.
70 *
71 */
72
73#define HASH_MAIN 0
74
75#if HASH_MAIN
76# include <stdio.h>
77# include <stdlib.h>
78#else
79# include "xf86drm.h"
80# ifdef XFree86LOADER
81# include "xf86.h"
82# include "xf86_ansic.h"
83# else
84# include <stdio.h>
85# include <stdlib.h>
86# endif
87#endif
88
89#define N(x) drm##x
90
91#define HASH_MAGIC 0xdeadbeef
92#define HASH_DEBUG 0
93#define HASH_SIZE 512 /* Good for about 100 entries */
94 /* If you change this value, you probably
95 have to change the HashHash hashing
96 function! */
97
98#if HASH_MAIN
99#define HASH_ALLOC malloc
100#define HASH_FREE free
101#define HASH_RANDOM_DECL
102#define HASH_RANDOM_INIT(seed) srandom(seed)
103#define HASH_RANDOM random()
104#else
105#define HASH_ALLOC drmMalloc
106#define HASH_FREE drmFree
107#define HASH_RANDOM_DECL void *state
108#define HASH_RANDOM_INIT(seed) state = drmRandomCreate(seed)
109#define HASH_RANDOM drmRandom(state)
110
111#endif
112
113typedef struct HashBucket {
114 unsigned long key;
115 void *value;
116 struct HashBucket *next;
117} HashBucket, *HashBucketPtr;
118
119typedef struct HashTable {
120 unsigned long magic;
121 unsigned long entries;
122 unsigned long hits; /* At top of linked list */
123 unsigned long partials; /* Not at top of linked list */
124 unsigned long misses; /* Not in table */
125 HashBucketPtr buckets[HASH_SIZE];
126 int p0;
127 HashBucketPtr p1;
128} HashTable, *HashTablePtr;
129
130#if HASH_MAIN
131extern void *N(HashCreate)(void);
132extern int N(HashDestroy)(void *t);
133extern int N(HashLookup)(void *t, unsigned long key, unsigned long *value);
134extern int N(HashInsert)(void *t, unsigned long key, unsigned long value);
135extern int N(HashDelete)(void *t, unsigned long key);
136#endif
137
138static unsigned long HashHash(unsigned long key)
139{
140 unsigned long hash = 0;
141 unsigned long tmp = key;
142 static int init = 0;
143 static unsigned long scatter[256];
144 int i;
145
146 if (!init) {
147 HASH_RANDOM_DECL;
148 HASH_RANDOM_INIT(37);
149 for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
150 ++init;
151 }
152
153 while (tmp) {
154 hash = (hash << 1) + scatter[tmp & 0xff];
155 tmp >>= 8;
156 }
157
158 hash %= HASH_SIZE;
159#if HASH_DEBUG
160 printf( "Hash(%d) = %d\n", key, hash);
161#endif
162 return hash;
163}
164
165void *N(HashCreate)(void)
166{
167 HashTablePtr table;
168 int i;
169
170 table = HASH_ALLOC(sizeof(*table));
171 if (!table) return NULL;
172 table->magic = HASH_MAGIC;
173 table->entries = 0;
174 table->hits = 0;
175 table->partials = 0;
176 table->misses = 0;
177
178 for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
179 return table;
180}
181
182int N(HashDestroy)(void *t)
183{
184 HashTablePtr table = (HashTablePtr)t;
185 HashBucketPtr bucket;
186 HashBucketPtr next;
187 int i;
188
189 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
190
191 for (i = 0; i < HASH_SIZE; i++) {
192 for (bucket = table->buckets[i]; bucket;) {
193 next = bucket->next;
194 HASH_FREE(bucket);
195 bucket = next;
196 }
197 }
198 HASH_FREE(table);
199 return 0;
200}
201
202/* Find the bucket and organize the list so that this bucket is at the
203 top. */
204
205static HashBucketPtr HashFind(HashTablePtr table,
206 unsigned long key, unsigned long *h)
207{
208 unsigned long hash = HashHash(key);
209 HashBucketPtr prev = NULL;
210 HashBucketPtr bucket;
211
212 if (h) *h = hash;
213
214 for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
215 if (bucket->key == key) {
216 if (prev) {
217 /* Organize */
218 prev->next = bucket->next;
219 bucket->next = table->buckets[hash];
220 table->buckets[hash] = bucket;
221 ++table->partials;
222 } else {
223 ++table->hits;
224 }
225 return bucket;
226 }
227 prev = bucket;
228 }
229 ++table->misses;
230 return NULL;
231}
232
233int N(HashLookup)(void *t, unsigned long key, void **value)
234{
235 HashTablePtr table = (HashTablePtr)t;
236 HashBucketPtr bucket;
237
238 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
239
240 bucket = HashFind(table, key, NULL);
241 if (!bucket) return 1; /* Not found */
242 *value = bucket->value;
243 return 0; /* Found */
244}
245
246int N(HashInsert)(void *t, unsigned long key, void *value)
247{
248 HashTablePtr table = (HashTablePtr)t;
249 HashBucketPtr bucket;
250 unsigned long hash;
251
252 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
253
254 if (HashFind(table, key, &hash)) return 1; /* Already in table */
255
256 bucket = HASH_ALLOC(sizeof(*bucket));
257 if (!bucket) return -1; /* Error */
258 bucket->key = key;
259 bucket->value = value;
260 bucket->next = table->buckets[hash];
261 table->buckets[hash] = bucket;
262#if HASH_DEBUG
263 printf("Inserted %d at %d/%p\n", key, hash, bucket);
264#endif
265 return 0; /* Added to table */
266}
267
268int N(HashDelete)(void *t, unsigned long key)
269{
270 HashTablePtr table = (HashTablePtr)t;
271 unsigned long hash;
272 HashBucketPtr bucket;
273
274 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
275
276 bucket = HashFind(table, key, &hash);
277
278 if (!bucket) return 1; /* Not found */
279
280 table->buckets[hash] = bucket->next;
281 HASH_FREE(bucket);
282 return 0;
283}
284
285int N(HashNext)(void *t, unsigned long *key, void **value)
286{
287 HashTablePtr table = (HashTablePtr)t;
288
289 for (; table->p0 < HASH_SIZE;
290 ++table->p0, table->p1 = table->buckets[table->p0]) {
291 if (table->p1) {
292 *key = table->p1->key;
293 *value = table->p1->value;
294 table->p1 = table->p1->next;
295 return 1;
296 }
297 }
298 return 0;
299}
300
301int N(HashFirst)(void *t, unsigned long *key, void **value)
302{
303 HashTablePtr table = (HashTablePtr)t;
304
305 if (table->magic != HASH_MAGIC) return -1; /* Bad magic */
306
307 table->p0 = 0;
308 table->p1 = table->buckets[0];
309 return N(HashNext)(table, key, value);
310}
311
312#if HASH_MAIN
313#define DIST_LIMIT 10
314static int dist[DIST_LIMIT];
315
316static void clear_dist(void) {
317 int i;
318
319 for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0;
320}
321
322static int count_entries(HashBucketPtr bucket)
323{
324 int count = 0;
325
326 for (; bucket; bucket = bucket->next) ++count;
327 return count;
328}
329
330static void update_dist(int count)
331{
332 if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1];
333 else ++dist[count];
334}
335
336static void compute_dist(HashTablePtr table)
337{
338 int i;
339 HashBucketPtr bucket;
340
341 printf("Entries = %ld, hits = %ld, partials = %ld, misses = %ld\n",
342 table->entries, table->hits, table->partials, table->misses);
343 clear_dist();
344 for (i = 0; i < HASH_SIZE; i++) {
345 bucket = table->buckets[i];
346 update_dist(count_entries(bucket));
347 }
348 for (i = 0; i < DIST_LIMIT; i++) {
349 if (i != DIST_LIMIT-1) printf("%5d %10d\n", i, dist[i]);
350 else printf("other %10d\n", dist[i]);
351 }
352}
353
354static void check_table(HashTablePtr table,
355 unsigned long key, unsigned long value)
356{
357 unsigned long retval = 0;
358 int retcode = N(HashLookup)(table, key, &retval);
359
360 switch (retcode) {
361 case -1:
362 printf("Bad magic = 0x%08lx:"
363 " key = %lu, expected = %lu, returned = %lu\n",
364 table->magic, key, value, retval);
365 break;
366 case 1:
367 printf("Not found: key = %lu, expected = %lu returned = %lu\n",
368 key, value, retval);
369 break;
370 case 0:
371 if (value != retval)
372 printf("Bad value: key = %lu, expected = %lu, returned = %lu\n",
373 key, value, retval);
374 break;
375 default:
376 printf("Bad retcode = %d: key = %lu, expected = %lu, returned = %lu\n",
377 retcode, key, value, retval);
378 break;
379 }
380}
381
382int main(void)
383{
384 HashTablePtr table;
385 int i;
386
387 printf("\n***** 256 consecutive integers ****\n");
388 table = N(HashCreate)();
389 for (i = 0; i < 256; i++) N(HashInsert)(table, i, i);
390 for (i = 0; i < 256; i++) check_table(table, i, i);
391 for (i = 256; i >= 0; i--) check_table(table, i, i);
392 compute_dist(table);
393 N(HashDestroy)(table);
394
395 printf("\n***** 1024 consecutive integers ****\n");
396 table = N(HashCreate)();
397 for (i = 0; i < 1024; i++) N(HashInsert)(table, i, i);
398 for (i = 0; i < 1024; i++) check_table(table, i, i);
399 for (i = 1024; i >= 0; i--) check_table(table, i, i);
400 compute_dist(table);
401 N(HashDestroy)(table);
402
403 printf("\n***** 1024 consecutive page addresses (4k pages) ****\n");
404 table = N(HashCreate)();
405 for (i = 0; i < 1024; i++) N(HashInsert)(table, i*4096, i);
406 for (i = 0; i < 1024; i++) check_table(table, i*4096, i);
407 for (i = 1024; i >= 0; i--) check_table(table, i*4096, i);
408 compute_dist(table);
409 N(HashDestroy)(table);
410
411 printf("\n***** 1024 random integers ****\n");
412 table = N(HashCreate)();
413 srandom(0xbeefbeef);
414 for (i = 0; i < 1024; i++) N(HashInsert)(table, random(), i);
415 srandom(0xbeefbeef);
416 for (i = 0; i < 1024; i++) check_table(table, random(), i);
417 srandom(0xbeefbeef);
418 for (i = 0; i < 1024; i++) check_table(table, random(), i);
419 compute_dist(table);
420 N(HashDestroy)(table);
421
422 printf("\n***** 5000 random integers ****\n");
423 table = N(HashCreate)();
424 srandom(0xbeefbeef);
425 for (i = 0; i < 5000; i++) N(HashInsert)(table, random(), i);
426 srandom(0xbeefbeef);
427 for (i = 0; i < 5000; i++) check_table(table, random(), i);
428 srandom(0xbeefbeef);
429 for (i = 0; i < 5000; i++) check_table(table, random(), i);
430 compute_dist(table);
431 N(HashDestroy)(table);
432
433 return 0;
434}
435#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 @@
1/* xf86drmRandom.c -- "Minimal Standard" PRNG Implementation
2 * Created: Mon Apr 19 08:28:13 1999 by faith@precisioninsight.com
3 * Revised: Thu Jun 24 14:53:45 1999 by faith@precisioninsight.com
4 *
5 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
6 * All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25 * DEALINGS IN THE SOFTWARE.
26 *
27 * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmRandom.c,v 1.4 1999/06/24 18:54:55 faith Exp $
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmRandom.c,v 1.2 1999/06/27 14:08:20 dawes Exp $
29 *
30 * DESCRIPTION
31 *
32 * This file contains a simple, straightforward implementation of the Park
33 * & Miller "Minimal Standard" PRNG [PM88, PMS93], which is a Lehmer
34 * multiplicative linear congruential generator (MLCG) with a period of
35 * 2^31-1.
36 *
37 * This implementation is intended to provide a reliable, portable PRNG
38 * that is suitable for testing a hash table implementation and for
39 * implementing skip lists.
40 *
41 * FUTURE ENHANCEMENTS
42 *
43 * If initial seeds are not selected randomly, two instances of the PRNG
44 * can be correlated. [Knuth81, pp. 32-33] describes a shuffling technique
45 * that can eliminate this problem.
46 *
47 * If PRNGs are used for simulation, the period of the current
48 * implementation may be too short. [LE88] discusses methods of combining
49 * MLCGs to produce much longer periods, and suggests some alternative
50 * values for A and M. [LE90 and Sch92] also provide information on
51 * long-period PRNGs.
52 *
53 * REFERENCES
54 *
55 * [Knuth81] Donald E. Knuth. The Art of Computer Programming. Volume 2:
56 * Seminumerical Algorithms. Reading, Massachusetts: Addison-Wesley, 1981.
57 *
58 * [LE88] Pierre L'Ecuyer. "Efficient and Portable Combined Random Number
59 * Generators". CACM 31(6), June 1988, pp. 742-774.
60 *
61 * [LE90] Pierre L'Ecuyer. "Random Numbers for Simulation". CACM 33(10,
62 * October 1990, pp. 85-97.
63 *
64 * [PM88] Stephen K. Park and Keith W. Miller. "Random Number Generators:
65 * Good Ones are Hard to Find". CACM 31(10), October 1988, pp. 1192-1201.
66 *
67 * [Sch92] Bruce Schneier. "Pseudo-Ransom Sequence Generator for 32-Bit
68 * CPUs". Dr. Dobb's Journal 17(2), February 1992, pp. 34, 37-38, 40.
69 *
70 * [PMS93] Stephen K. Park, Keith W. Miller, and Paul K. Stockmeyer. In
71 * "Technical Correspondence: Remarks on Choosing and Implementing Random
72 * Number Generators". CACM 36(7), July 1993, pp. 105-110.
73 *
74 */
75
76#define RANDOM_MAIN 0
77
78#if RANDOM_MAIN
79# include <stdio.h>
80# include <stdlib.h>
81#else
82# include "xf86drm.h"
83# ifdef XFree86LOADER
84# include "xf86.h"
85# include "xf86_ansic.h"
86# else
87# include <stdio.h>
88# include <stdlib.h>
89# endif
90#endif
91
92#define N(x) drm##x
93
94#define RANDOM_MAGIC 0xfeedbeef
95#define RANDOM_DEBUG 0
96
97#if RANDOM_MAIN
98#define RANDOM_ALLOC malloc
99#define RANDOM_FREE free
100#else
101#define RANDOM_ALLOC drmMalloc
102#define RANDOM_FREE drmFree
103#endif
104
105typedef struct RandomState {
106 unsigned long magic;
107 unsigned long a;
108 unsigned long m;
109 unsigned long q; /* m div a */
110 unsigned long r; /* m mod a */
111 unsigned long check;
112 long seed;
113} RandomState;
114
115#if RANDOM_MAIN
116extern void *N(RandomCreate)(unsigned long seed);
117extern int N(RandomDestroy)(void *state);
118extern unsigned long N(Random)(void *state);
119extern double N(RandomDouble)(void *state);
120#endif
121
122void *N(RandomCreate)(unsigned long seed)
123{
124 RandomState *state;
125
126 state = RANDOM_ALLOC(sizeof(*state));
127 if (!state) return NULL;
128 state->magic = RANDOM_MAGIC;
129#if 0
130 /* Park & Miller, October 1988 */
131 state->a = 16807;
132 state->m = 2147483647;
133 state->check = 1043618065; /* After 10000 iterations */
134#else
135 /* Park, Miller, and Stockmeyer, July 1993 */
136 state->a = 48271;
137 state->m = 2147483647;
138 state->check = 399268537; /* After 10000 iterations */
139#endif
140 state->q = state->m / state->a;
141 state->r = state->m % state->a;
142
143 state->seed = seed;
144 /* Check for illegal boundary conditions,
145 and choose closest legal value. */
146 if (state->seed <= 0) state->seed = 1;
147 if (state->seed >= state->m) state->seed = state->m - 1;
148
149 return state;
150}
151
152int N(RandomDestroy)(void *state)
153{
154 RANDOM_FREE(state);
155 return 0;
156}
157
158unsigned long N(Random)(void *state)
159{
160 RandomState *s = (RandomState *)state;
161 long hi;
162 long lo;
163
164 hi = s->seed / s->q;
165 lo = s->seed % s->q;
166 s->seed = s->a * lo - s->r * hi;
167 if (s->seed <= 0) s->seed += s->m;
168
169 return s->seed;
170}
171
172double N(RandomDouble)(void *state)
173{
174 RandomState *s = (RandomState *)state;
175
176 return (double)N(Random)(state)/(double)s->m;
177}
178
179#if RANDOM_MAIN
180static void check_period(long seed)
181{
182 unsigned long count = 0;
183 unsigned long initial;
184 void *state;
185
186 state = N(RandomCreate)(seed);
187 initial = N(Random)(state);
188 ++count;
189 while (initial != N(Random)(state)) {
190 if (!++count) break;
191 }
192 printf("With seed of %10ld, period = %10lu (0x%08lx)\n",
193 seed, count, count);
194 N(RandomDestroy)(state);
195}
196
197int main(void)
198{
199 RandomState *state;
200 int i;
201 unsigned long rand;
202
203 state = N(RandomCreate)(1);
204 for (i = 0; i < 10000; i++) {
205 rand = N(Random)(state);
206 }
207 printf("After 10000 iterations: %lu (%lu expected): %s\n",
208 rand, state->check,
209 rand - state->check ? "*INCORRECT*" : "CORRECT");
210 N(RandomDestroy)(state);
211
212 printf("Checking periods...\n");
213 check_period(1);
214 check_period(2);
215 check_period(31415926);
216
217 return 0;
218}
219#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 @@
1/* xf86drmSL.c -- Skip list support
2 * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
3 * Revised: Thu Jun 3 16:13:01 1999 by faith@precisioninsight.com
4 *
5 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
6 * All Rights Reserved.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
23 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
24 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25 * DEALINGS IN THE SOFTWARE.
26 *
27 * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.2 1999/06/07 13:01:42 faith Exp $
28 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.1 1999/06/14 07:32:02 dawes Exp $
29 *
30 * DESCRIPTION
31 *
32 * This file contains a straightforward skip list implementation.n
33 *
34 * FUTURE ENHANCEMENTS
35 *
36 * REFERENCES
37 *
38 * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to
39 * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
40 *
41 */
42
43#define SL_MAIN 0
44
45#if SL_MAIN
46# include <stdio.h>
47# include <stdlib.h>
48# include <sys/time.h>
49#else
50# include "xf86drm.h"
51# ifdef XFree86LOADER
52# include "xf86.h"
53# include "xf86_ansic.h"
54# else
55# include <stdio.h>
56# include <stdlib.h>
57# endif
58#endif
59
60#define N(x) drm##x
61
62#define SL_LIST_MAGIC 0xfacade00LU
63#define SL_ENTRY_MAGIC 0x00fab1edLU
64#define SL_FREED_MAGIC 0xdecea5edLU
65#define SL_MAX_LEVEL 16
66#define SL_DEBUG 0
67#define SL_RANDOM_SEED 0xc01055a1LU
68
69#if SL_MAIN
70#define SL_ALLOC malloc
71#define SL_FREE free
72#define SL_RANDOM_DECL static int state = 0;
73#define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; }
74#define SL_RANDOM random()
75#else
76#define SL_ALLOC drmMalloc
77#define SL_FREE drmFree
78#define SL_RANDOM_DECL static void *state = NULL
79#define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
80#define SL_RANDOM drmRandom(state)
81
82#endif
83
84typedef struct SLEntry {
85 unsigned long magic; /* SL_ENTRY_MAGIC */
86 unsigned long key;
87 void *value;
88 int levels;
89 struct SLEntry *forward[1]; /* variable sized array */
90} SLEntry, *SLEntryPtr;
91
92typedef struct SkipList {
93 unsigned long magic; /* SL_LIST_MAGIC */
94 int level;
95 int count;
96 SLEntryPtr head;
97 SLEntryPtr p0; /* Position for iteration */
98} SkipList, *SkipListPtr;
99
100#if SL_MAIN
101extern void *N(SLCreate)(void);
102extern int N(SLDestroy)(void *l);
103extern int N(SLLookup)(void *l, unsigned long key, void **value);
104extern int N(SLInsert)(void *l, unsigned long key, void *value);
105extern int N(SLDelete)(void *l, unsigned long key);
106extern int N(SLNext)(void *l, unsigned long *key, void **value);
107extern int N(SLFirst)(void *l, unsigned long *key, void **value);
108extern void N(SLDump)(void *l);
109extern int N(SLLookupNeighbors)(void *l, unsigned long key,
110 unsigned long *prev_key, void **prev_value,
111 unsigned long *next_key, void **next_value);
112#endif
113
114static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
115{
116 SLEntryPtr entry;
117
118 if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
119
120 entry = SL_ALLOC(sizeof(*entry)
121 + (max_level + 1) * sizeof(entry->forward[0]));
122 if (!entry) return NULL;
123 entry->magic = SL_ENTRY_MAGIC;
124 entry->key = key;
125 entry->value = value;
126 entry->levels = max_level + 1;
127
128 return entry;
129}
130
131static int SLRandomLevel(void)
132{
133 int level = 1;
134 SL_RANDOM_DECL;
135
136 SL_RANDOM_INIT(SL_RANDOM_SEED);
137
138 while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
139 return level;
140}
141
142void *N(SLCreate)(void)
143{
144 SkipListPtr list;
145 int i;
146
147 list = SL_ALLOC(sizeof(*list));
148 if (!list) return NULL;
149 list->magic = SL_LIST_MAGIC;
150 list->level = 0;
151 list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
152 list->count = 0;
153
154 for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
155
156 return list;
157}
158
159int N(SLDestroy)(void *l)
160{
161 SkipListPtr list = (SkipListPtr)l;
162 SLEntryPtr entry;
163 SLEntryPtr next;
164
165 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
166
167 for (entry = list->head; entry; entry = next) {
168 if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
169 next = entry->forward[0];
170 entry->magic = SL_FREED_MAGIC;
171 SL_FREE(entry);
172 }
173
174 list->magic = SL_FREED_MAGIC;
175 SL_FREE(list);
176 return 0;
177}
178
179static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
180{
181 SkipListPtr list = (SkipListPtr)l;
182 SLEntryPtr entry;
183 int i;
184
185 if (list->magic != SL_LIST_MAGIC) return NULL;
186
187 for (i = list->level, entry = list->head; i >= 0; i--) {
188 while (entry->forward[i] && entry->forward[i]->key < key)
189 entry = entry->forward[i];
190 update[i] = entry;
191 }
192
193 return entry->forward[0];
194}
195
196int N(SLInsert)(void *l, unsigned long key, void *value)
197{
198 SkipListPtr list = (SkipListPtr)l;
199 SLEntryPtr entry;
200 SLEntryPtr update[SL_MAX_LEVEL + 1];
201 int level;
202 int i;
203
204 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
205
206 entry = SLLocate(list, key, update);
207
208 if (entry && entry->key == key) return 1; /* Already in list */
209
210
211 level = SLRandomLevel();
212 if (level > list->level) {
213 level = ++list->level;
214 update[level] = list->head;
215 }
216
217 entry = SLCreateEntry(level, key, value);
218
219 /* Fix up forward pointers */
220 for (i = 0; i <= level; i++) {
221 entry->forward[i] = update[i]->forward[i];
222 update[i]->forward[i] = entry;
223 }
224
225 ++list->count;
226 return 0; /* Added to table */
227}
228
229int N(SLDelete)(void *l, unsigned long key)
230{
231 SkipListPtr list = (SkipListPtr)l;
232 SLEntryPtr update[SL_MAX_LEVEL + 1];
233 SLEntryPtr entry;
234 int i;
235
236 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
237
238 entry = SLLocate(list, key, update);
239
240 if (!entry || entry->key != key) return 1; /* Not found */
241
242 /* Fix up forward pointers */
243 for (i = 0; i <= list->level; i++) {
244 if (update[i]->forward[i] == entry)
245 update[i]->forward[i] = entry->forward[i];
246 }
247
248 entry->magic = SL_FREED_MAGIC;
249 SL_FREE(entry);
250
251 while (list->level && !list->head->forward[list->level]) --list->level;
252 --list->count;
253 return 0;
254}
255
256int N(SLLookup)(void *l, unsigned long key, void **value)
257{
258 SkipListPtr list = (SkipListPtr)l;
259 SLEntryPtr update[SL_MAX_LEVEL + 1];
260 SLEntryPtr entry;
261
262 entry = SLLocate(list, key, update);
263
264 if (entry && entry->key == key) {
265 *value = entry;
266 return 0;
267 }
268 *value = NULL;
269 return -1;
270}
271
272int N(SLLookupNeighbors)(void *l, unsigned long key,
273 unsigned long *prev_key, void **prev_value,
274 unsigned long *next_key, void **next_value)
275{
276 SkipListPtr list = (SkipListPtr)l;
277 SLEntryPtr update[SL_MAX_LEVEL + 1];
278 SLEntryPtr entry;
279 int retcode = 0;
280
281 entry = SLLocate(list, key, update);
282
283 *prev_key = *next_key = key;
284 *prev_value = *next_value = NULL;
285
286 if (update[0]) {
287 *prev_key = update[0]->key;
288 *prev_value = update[0]->value;
289 ++retcode;
290 if (update[0]->forward[0]) {
291 *next_key = update[0]->forward[0]->key;
292 *next_value = update[0]->forward[0]->value;
293 ++retcode;
294 }
295 }
296 return retcode;
297}
298
299int N(SLNext)(void *l, unsigned long *key, void **value)
300{
301 SkipListPtr list = (SkipListPtr)l;
302 SLEntryPtr entry;
303
304 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
305
306 entry = list->p0;
307
308 if (entry) {
309 list->p0 = entry->forward[0];
310 *key = entry->key;
311 *value = entry->value;
312 return 1;
313 }
314 list->p0 = NULL;
315 return 0;
316}
317
318int N(SLFirst)(void *l, unsigned long *key, void **value)
319{
320 SkipListPtr list = (SkipListPtr)l;
321
322 if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
323
324 list->p0 = list->head->forward[0];
325 return N(SLNext)(list, key, value);
326}
327
328/* Dump internal data structures for debugging. */
329void N(SLDump)(void *l)
330{
331 SkipListPtr list = (SkipListPtr)l;
332 SLEntryPtr entry;
333 int i;
334
335 if (list->magic != SL_LIST_MAGIC) {
336 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
337 list->magic, SL_LIST_MAGIC);
338 return;
339 }
340
341 printf("Level = %d, count = %d\n", list->level, list->count);
342 for (entry = list->head; entry; entry = entry->forward[0]) {
343 if (entry->magic != SL_ENTRY_MAGIC) {
344 printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
345 list->magic, SL_ENTRY_MAGIC);
346 }
347 printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
348 entry, entry->key, entry->value, entry->levels);
349 for (i = 0; i < entry->levels; i++) {
350 if (entry->forward[i]) {
351 printf(" %2d: %p <0x%08lx, %p>\n",
352 i,
353 entry->forward[i],
354 entry->forward[i]->key,
355 entry->forward[i]->value);
356 } else {
357 printf(" %2d: %p\n", i, entry->forward[i]);
358 }
359 }
360 }
361}
362
363#if SL_MAIN
364static void print(SkipListPtr list)
365{
366 unsigned long key;
367 void *value;
368
369 if (N(SLFirst)(list, &key, &value)) {
370 do {
371 printf("key = %5lu, value = %p\n", key, value);
372 } while (N(SLNext)(list, &key, &value));
373 }
374}
375
376static double do_time(int size, int iter)
377{
378 SkipListPtr list;
379 int i, j;
380 unsigned long keys[1000000];
381 unsigned long previous;
382 unsigned long key;
383 void *value;
384 struct timeval start, stop;
385 double usec;
386 SL_RANDOM_DECL;
387
388 SL_RANDOM_INIT(12345);
389
390 list = N(SLCreate)();
391
392 for (i = 0; i < size; i++) {
393 keys[i] = SL_RANDOM;
394 N(SLInsert)(list, keys[i], NULL);
395 }
396
397 previous = 0;
398 if (N(SLFirst)(list, &key, &value)) {
399 do {
400 if (key <= previous) {
401 printf( "%lu !< %lu\n", previous, key);
402 }
403 previous = key;
404 } while (N(SLNext)(list, &key, &value));
405 }
406
407 gettimeofday(&start, NULL);
408 for (j = 0; j < iter; j++) {
409 for (i = 0; i < size; i++) {
410 if (N(SLLookup)(list, keys[i], &value))
411 printf("Error %lu %d\n", keys[i], i);
412 }
413 }
414 gettimeofday(&stop, NULL);
415
416 usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
417 - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
418
419 printf("%0.2f microseconds for list length %d\n", usec, size);
420
421 N(SLDestroy)(list);
422
423 return usec;
424}
425
426static void print_neighbors(void *list, unsigned long key)
427{
428 unsigned long prev_key = 0;
429 unsigned long next_key = 0;
430 void *prev_value;
431 void *next_value;
432 int retval;
433
434 retval = drmSLLookupNeighbors(list, key,
435 &prev_key, &prev_value,
436 &next_key, &next_value);
437 printf("Neighbors of %5lu: %d %5lu %5lu\n",
438 key, retval, prev_key, next_key);
439}
440
441int main(void)
442{
443 SkipListPtr list;
444 double usec, usec2, usec3, usec4;
445
446 list = N(SLCreate)();
447 printf( "list at %p\n", list);
448
449 print(list);
450 printf("\n==============================\n\n");
451
452 N(SLInsert)(list, 123, NULL);
453 N(SLInsert)(list, 213, NULL);
454 N(SLInsert)(list, 50, NULL);
455 print(list);
456 printf("\n==============================\n\n");
457
458 print_neighbors(list, 0);
459 print_neighbors(list, 50);
460 print_neighbors(list, 51);
461 print_neighbors(list, 123);
462 print_neighbors(list, 200);
463 print_neighbors(list, 213);
464 print_neighbors(list, 256);
465 printf("\n==============================\n\n");
466
467 N(SLDelete)(list, 50);
468 print(list);
469 printf("\n==============================\n\n");
470
471 N(SLDump)(list);
472 N(SLDestroy)(list);
473 printf("\n==============================\n\n");
474
475 usec = do_time(100, 10000);
476 usec2 = do_time(1000, 500);
477 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
478 1000.0/100.0, usec2 / usec);
479
480 usec3 = do_time(10000, 50);
481 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
482 10000.0/100.0, usec3 / usec);
483
484 usec4 = do_time(100000, 4);
485 printf("Table size increased by %0.2f, search time increased by %0.2f\n",
486 100000.0/100.0, usec4 / usec);
487
488 return 0;
489}
490#endif