diff options
author | Daryll Strauss | 1999-12-04 19:19:48 -0600 |
---|---|---|
committer | Daryll Strauss | 1999-12-04 19:19:48 -0600 |
commit | b3a5766992019fc5f44cc9afd01b2617b76f47a7 (patch) | |
tree | 8c7d4209618d11e15253351a0689de007f0105fe | |
download | external-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.tar.gz external-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.tar.xz external-libgbm-b3a5766992019fc5f44cc9afd01b2617b76f47a7.zip |
Initial revision
-rw-r--r-- | libdrm/xf86drm.c | 1114 | ||||
-rw-r--r-- | libdrm/xf86drmHash.c | 435 | ||||
-rw-r--r-- | libdrm/xf86drmRandom.c | 219 | ||||
-rw-r--r-- | libdrm/xf86drmSL.c | 490 |
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 | ||
60 | extern int xf86InstallSIGIOHandler(int fd, void (*f)(int)); | ||
61 | extern 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 | |||
78 | static void *drmHashTable = NULL; /* Context switch callbacks */ | ||
79 | |||
80 | typedef struct drmHashEntry { | ||
81 | int fd; | ||
82 | void (*f)(int, void *, void *); | ||
83 | void *tagTable; | ||
84 | } drmHashEntry; | ||
85 | |||
86 | void *drmMalloc(int size) | ||
87 | { | ||
88 | void *pt; | ||
89 | if ((pt = _DRM_MALLOC(size))) memset(pt, 0, size); | ||
90 | return pt; | ||
91 | } | ||
92 | |||
93 | void drmFree(void *pt) | ||
94 | { | ||
95 | if (pt) _DRM_FREE(pt); | ||
96 | } | ||
97 | |||
98 | static 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 | |||
119 | static 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 | |||
161 | static 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 | |||
174 | static 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 | |||
196 | static 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 | |||
206 | int 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 | |||
215 | static 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 | |||
230 | static 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 | |||
249 | static 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 | |||
314 | int drmOpenDRM(void) | ||
315 | { | ||
316 | return drmOpen(DRM_NAME, NULL); | ||
317 | } | ||
318 | |||
319 | |||
320 | /* drmClose closes the file descriptor returned from drmOpen. */ | ||
321 | |||
322 | int drmCloseDRM(int fd) | ||
323 | { | ||
324 | return close(fd); | ||
325 | } | ||
326 | |||
327 | void 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 | |||
336 | static 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 | |||
345 | static 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 | |||
361 | drmVersionPtr 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 | |||
407 | void 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 | |||
425 | static 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 | |||
444 | drmListPtr 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 | |||
516 | int 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 | |||
528 | int 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 | |||
541 | int 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 | |||
551 | int 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 | |||
560 | int 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 | |||
579 | int 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 | |||
592 | int 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 | |||
627 | int 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 | |||
637 | int drmOpenSub(const char *busid) | ||
638 | { | ||
639 | return drmOpen(NULL, busid); | ||
640 | } | ||
641 | |||
642 | int 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 | |||
658 | int 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 | |||
669 | int drmUnmap(drmAddress address, drmSize size) | ||
670 | { | ||
671 | return munmap(address, size); | ||
672 | } | ||
673 | |||
674 | drmBufInfoPtr 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 | |||
710 | drmBufMapPtr 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 | |||
744 | int 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 | |||
754 | int 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 | |||
774 | int 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 | |||
792 | int 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 | |||
801 | drmContextPtr 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 | |||
830 | void drmFreeReservedContextList(drmContextPtr pt) | ||
831 | { | ||
832 | drmFree(pt); | ||
833 | } | ||
834 | |||
835 | int 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 | |||
845 | int 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 | |||
854 | int 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 | |||
874 | int 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 | |||
886 | int 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 | |||
894 | int 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 | |||
902 | int 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 | |||
910 | int 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 | |||
926 | int 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 | |||
953 | int 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 | |||
969 | int 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 | |||
982 | int 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 | |||
995 | int 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 | |||
1011 | int 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 | |||
1022 | int 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 | |||
1033 | int drmDelContextTag(int fd, drmContext context) | ||
1034 | { | ||
1035 | drmHashEntry *entry = drmGetEntry(fd); | ||
1036 | |||
1037 | return drmHashDelete(entry->tagTable, context); | ||
1038 | } | ||
1039 | |||
1040 | void *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) | ||
1051 | static 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 | |||
1096 | int 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 | |||
1106 | int 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 | |||
113 | typedef struct HashBucket { | ||
114 | unsigned long key; | ||
115 | void *value; | ||
116 | struct HashBucket *next; | ||
117 | } HashBucket, *HashBucketPtr; | ||
118 | |||
119 | typedef 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 | ||
131 | extern void *N(HashCreate)(void); | ||
132 | extern int N(HashDestroy)(void *t); | ||
133 | extern int N(HashLookup)(void *t, unsigned long key, unsigned long *value); | ||
134 | extern int N(HashInsert)(void *t, unsigned long key, unsigned long value); | ||
135 | extern int N(HashDelete)(void *t, unsigned long key); | ||
136 | #endif | ||
137 | |||
138 | static 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 | |||
165 | void *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 | |||
182 | int 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 | |||
205 | static 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 | |||
233 | int 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 | |||
246 | int 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 | |||
268 | int 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 | |||
285 | int 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 | |||
301 | int 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 | ||
314 | static int dist[DIST_LIMIT]; | ||
315 | |||
316 | static void clear_dist(void) { | ||
317 | int i; | ||
318 | |||
319 | for (i = 0; i < DIST_LIMIT; i++) dist[i] = 0; | ||
320 | } | ||
321 | |||
322 | static int count_entries(HashBucketPtr bucket) | ||
323 | { | ||
324 | int count = 0; | ||
325 | |||
326 | for (; bucket; bucket = bucket->next) ++count; | ||
327 | return count; | ||
328 | } | ||
329 | |||
330 | static void update_dist(int count) | ||
331 | { | ||
332 | if (count >= DIST_LIMIT) ++dist[DIST_LIMIT-1]; | ||
333 | else ++dist[count]; | ||
334 | } | ||
335 | |||
336 | static 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 | |||
354 | static 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 | |||
382 | int 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 | |||
105 | typedef 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 | ||
116 | extern void *N(RandomCreate)(unsigned long seed); | ||
117 | extern int N(RandomDestroy)(void *state); | ||
118 | extern unsigned long N(Random)(void *state); | ||
119 | extern double N(RandomDouble)(void *state); | ||
120 | #endif | ||
121 | |||
122 | void *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 | |||
152 | int N(RandomDestroy)(void *state) | ||
153 | { | ||
154 | RANDOM_FREE(state); | ||
155 | return 0; | ||
156 | } | ||
157 | |||
158 | unsigned 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 | |||
172 | double 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 | ||
180 | static 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 | |||
197 | int 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 | |||
84 | typedef 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 | |||
92 | typedef 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 | ||
101 | extern void *N(SLCreate)(void); | ||
102 | extern int N(SLDestroy)(void *l); | ||
103 | extern int N(SLLookup)(void *l, unsigned long key, void **value); | ||
104 | extern int N(SLInsert)(void *l, unsigned long key, void *value); | ||
105 | extern int N(SLDelete)(void *l, unsigned long key); | ||
106 | extern int N(SLNext)(void *l, unsigned long *key, void **value); | ||
107 | extern int N(SLFirst)(void *l, unsigned long *key, void **value); | ||
108 | extern void N(SLDump)(void *l); | ||
109 | extern 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 | |||
114 | static 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 | |||
131 | static 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 | |||
142 | void *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 | |||
159 | int 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 | |||
179 | static 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 | |||
196 | int 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 | |||
229 | int 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 | |||
256 | int 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 | |||
272 | int 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 | |||
299 | int 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 | |||
318 | int 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. */ | ||
329 | void 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 | ||
364 | static 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 | |||
376 | static 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 | |||
426 | static 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 | |||
441 | int 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 | ||