/* * Copyright 2003 Tungsten Graphics, Inc., Cedar Park, Texas. * All Rights Reserved. * * Permission is hereby granted, free of charge, to any person obtaining a * copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sub license, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice (including the * next paragraph) shall be included in all copies or substantial portions * of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */ #ifndef _I915_DRM_H_ #define _I915_DRM_H_ /* Please note that modifications to all structs defined here are * subject to backwards-compatibility constraints. */ #include "drm.h" /* Each region is a minimum of 16k, and there are at most 255 of them. */ #define I915_NR_TEX_REGIONS 255 /* table size 2k - maximum due to use * of chars for next/prev indices */ #define I915_LOG_MIN_TEX_REGION_SIZE 14 typedef struct drm_i915_init { enum { I915_INIT_DMA = 0x01, I915_CLEANUP_DMA = 0x02, I915_RESUME_DMA = 0x03 } func; unsigned int mmio_offset; int sarea_priv_offset; unsigned int ring_start; unsigned int ring_end; unsigned int ring_size; unsigned int front_offset; unsigned int back_offset; unsigned int depth_offset; unsigned int w; unsigned int h; unsigned int pitch; unsigned int pitch_bits; unsigned int back_pitch; unsigned int depth_pitch; unsigned int cpp; unsigned int chipset; } drm_i915_init_t; typedef struct drm_i915_sarea { struct drm_tex_region texList[I915_NR_TEX_REGIONS + 1]; int last_upload; /* last time texture was uploaded */ int last_enqueue; /* last time a buffer was enqueued */ int last_dispatch; /* age of the most recently dispatched buffer */ int ctxOwner; /* last context to upload state */ int texAge; int pf_enabled; /* is pageflipping allowed? */ int pf_active; int pf_current_page; /* which buffer is being displayed? */ int perf_boxes; /* performance boxes to be displayed */ int width, height; /* screen size in pixels */ drm_handle_t front_handle; int front_offset; int front_size; drm_handle_t back_handle; int back_offset; int back_size; drm_handle_t depth_handle; int depth_offset; int depth_size; drm_handle_t tex_handle; int tex_offset; int tex_size; int log_tex_granularity; int pitch; int rotation; /* 0, 90, 180 or 270 */ int rotated_offset; int rotated_size; int rotated_pitch; int virtualX, virtualY; unsigned int front_tiled; unsigned int back_tiled; unsigned int depth_tiled; unsigned int rotated_tiled; unsigned int rotated2_tiled; int planeA_x; int planeA_y; int planeA_w; int planeA_h; int planeB_x; int planeB_y; int planeB_w; int planeB_h; /* Triple buffering */ drm_handle_t third_handle; int third_offset; int third_size; unsigned int third_tiled; } drm_i915_sarea_t; /* Driver specific fence types and classes. */ /* The only fence class we support */ #define DRM_I915_FENCE_CLASS_ACCEL 0 /* Fence type that guarantees read-write flush */ #define DRM_I915_FENCE_TYPE_RW 2 /* MI_FLUSH programmed just before the fence */ #define DRM_I915_FENCE_FLAG_FLUSHED 0x01000000 /* Flags for perf_boxes */ #define I915_BOX_RING_EMPTY 0x1 #define I915_BOX_FLIP 0x2 #define I915_BOX_WAIT 0x4 #define I915_BOX_TEXTURE_LOAD 0x8 #define I915_BOX_LOST_CONTEXT 0x10 /* I915 specific ioctls * The device specific ioctl range is 0x40 to 0x79. */ #define DRM_I915_INIT 0x00 #define DRM_I915_FLUSH 0x01 #define DRM_I915_FLIP 0x02 #define DRM_I915_BATCHBUFFER 0x03 #define DRM_I915_IRQ_EMIT 0x04 #define DRM_I915_IRQ_WAIT 0x05 #define DRM_I915_GETPARAM 0x06 #define DRM_I915_SETPARAM 0x07 #define DRM_I915_ALLOC 0x08 #define DRM_I915_FREE 0x09 #define DRM_I915_INIT_HEAP 0x0a #define DRM_I915_CMDBUFFER 0x0b #define DRM_I915_DESTROY_HEAP 0x0c #define DRM_I915_SET_VBLANK_PIPE 0x0d #define DRM_I915_GET_VBLANK_PIPE 0x0e #define DRM_I915_VBLANK_SWAP 0x0f #define DRM_I915_MMIO 0x10 #define DRM_I915_HWS_ADDR 0x11 #define DRM_I915_EXECBUFFER 0x12 #define DRM_IOCTL_I915_INIT DRM_IOW( DRM_COMMAND_BASE + DRM_I915_INIT, drm_i915_init_t) #define DRM_IOCTL_I915_FLUSH DRM_IO ( DRM_COMMAND_BASE + DRM_I915_FLUSH) #define DRM_IOCTL_I915_FLIP DRM_IOW( DRM_COMMAND_BASE + DRM_I915_FLIP, drm_i915_flip_t) #define DRM_IOCTL_I915_BATCHBUFFER DRM_IOW( DRM_COMMAND_BASE + DRM_I915_BATCHBUFFER, drm_i915_batchbuffer_t) #define DRM_IOCTL_I915_IRQ_EMIT DRM_IOWR(DRM_COMMAND_BASE + DRM_I915_IRQ_EMIT, drm_i915_irq_emit_t) #define DRM_IOCTL_I915_IRQ_WAIT DRM_IOW( DRM_COMMAND_BASE + DRM_I915_IRQ_WAIT, drm_i915_irq_wait_t) #define DRM_IOCTL_I915_GETPARAM DRM_IOWR(DRM_COMMAND_BASE + DRM_I915_GETPARAM, drm_i915_getparam_t) #define DRM_IOCTL_I915_SETPARAM DRM_IOW( DRM_COMMAND_BASE + DRM_I915_SETPARAM, drm_i915_setparam_t) #define DRM_IOCTL_I915_ALLOC DRM_IOWR(DRM_COMMAND_BASE + DRM_I915_ALLOC, drm_i915_mem_alloc_t) #define DRM_IOCTL_I915_FREE DRM_IOW( DRM_COMMAND_BASE + DRM_I915_FREE, drm_i915_mem_free_t) #define DRM_IOCTL_I915_INIT_HEAP DRM_IOW( DRM_COMMAND_BASE + DRM_I915_INIT_HEAP, drm_i915_mem_init_heap_t) #define DRM_IOCTL_I915_CMDBUFFER DRM_IOW( DRM_COMMAND_BASE + DRM_I915_CMDBUFFER, drm_i915_cmdbuffer_t) #define DRM_IOCTL_I915_DESTROY_HEAP DRM_IOW( DRM_COMMAND_BASE + DRM_I915_DESTROY_HEAP, drm_i915_mem_destroy_heap_t) #define DRM_IOCTL_I915_SET_VBLANK_PIPE DRM_IOW( DRM_COMMAND_BASE + DRM_I915_SET_VBLANK_PIPE, drm_i915_vblank_pipe_t) #define DRM_IOCTL_I915_GET_VBLANK_PIPE DRM_IOR( DRM_COMMAND_BASE + DRM_I915_GET_VBLANK_PIPE, drm_i915_vblank_pipe_t) #define DRM_IOCTL_I915_VBLANK_SWAP DRM_IOWR(DRM_COMMAND_BASE + DRM_I915_VBLANK_SWAP, drm_i915_vblank_swap_t) #define DRM_IOCTL_I915_EXECBUFFER DRM_IOWR(DRM_COMMAND_BASE + DRM_I915_EXECBUFFER, struct drm_i915_execbuffer) /* Asynchronous page flipping: */ typedef struct drm_i915_flip { /* * This is really talking about planes, and we could rename it * except for the fact that some of the duplicated i915_drm.h files * out there check for HAVE_I915_FLIP and so might pick up this * version. */ int pipes; } drm_i915_flip_t; /* Allow drivers to submit batchbuffers directly to hardware, relying * on the security mechanisms provided by hardware. */ typedef struct drm_i915_batchbuffer { int start; /* agp offset */ int used; /* nr bytes in use */ int DR1; /* hw flags for GFX_OP_DRAWRECT_INFO */ int DR4; /* window origin for GFX_OP_DRAWRECT_INFO */ int num_cliprects; /* mulitpass with multiple cliprects? */ struct drm_clip_rect __user *cliprects; /* pointer to userspace cliprects */ } drm_i915_batchbuffer_t; /* As above, but pass a pointer to userspace buffer which can be * validated by the kernel prior to sending to hardware. */ typedef struct drm_i915_cmdbuffer { char __user *buf; /* pointer to userspace command buffer */ int sz; /* nr bytes in buf */ int DR1; /* hw flags for GFX_OP_DRAWRECT_INFO */ int DR4; /* window origin for GFX_OP_DRAWRECT_INFO */ int num_cliprects; /* mulitpass with multiple cliprects? */ struct drm_clip_rect __user *cliprects; /* pointer to userspace cliprects */ } drm_i915_cmdbuffer_t; /* Userspace can request & wait on irq's: */ typedef struct drm_i915_irq_emit { int __user *irq_seq; } drm_i915_irq_emit_t; typedef struct drm_i915_irq_wait { int irq_seq; } drm_i915_irq_wait_t; /* Ioctl to query kernel params: */ #define I915_PARAM_IRQ_ACTIVE 1 #define I915_PARAM_ALLOW_BATCHBUFFER 2 #define I915_PARAM_LAST_DISPATCH 3 typedef struct drm_i915_getparam { int param; int __user *value; } drm_i915_getparam_t; /* Ioctl to set kernel params: */ #define I915_SETPARAM_USE_MI_BATCHBUFFER_START 1 #define I915_SETPARAM_TEX_LRU_LOG_GRANULARITY 2 #define I915_SETPARAM_ALLOW_BATCHBUFFER 3 typedef struct drm_i915_setparam { int param; int value; } drm_i915_setparam_t; /* A memory manager for regions of shared memory: */ #define I915_MEM_REGION_AGP 1 typedef struct drm_i915_mem_alloc { int region; int alignment; int size; int __user *region_offset; /* offset from start of fb or agp */ } drm_i915_mem_alloc_t; typedef struct drm_i915_mem_free { int region; int region_offset; } drm_i915_mem_free_t; typedef struct drm_i915_mem_init_heap { int region; int size; int start; } drm_i915_mem_init_heap_t; /* Allow memory manager to be torn down and re-initialized (eg on * rotate): */ typedef struct drm_i915_mem_destroy_heap { int region; } drm_i915_mem_destroy_heap_t; /* Allow X server to configure which pipes to monitor for vblank signals */ #define DRM_I915_VBLANK_PIPE_A 1 #define DRM_I915_VBLANK_PIPE_B 2 typedef struct drm_i915_vblank_pipe { int pipe; } drm_i915_vblank_pipe_t; /* Schedule buffer swap at given vertical blank: */ typedef struct drm_i915_vblank_swap { drm_drawable_t drawable; enum drm_vblank_seq_type seqtype; unsigned int sequence; } drm_i915_vblank_swap_t; #define I915_MMIO_READ 0 #define I915_MMIO_WRITE 1 #define I915_MMIO_MAY_READ 0x1 #define I915_MMIO_MAY_WRITE 0x2 #define MMIO_REGS_IA_PRIMATIVES_COUNT 0 #define MMIO_REGS_IA_VERTICES_COUNT 1 #define MMIO_REGS_VS_INVOCATION_COUNT 2 #define MMIO_REGS_GS_PRIMITIVES_COUNT 3 #define MMIO_REGS_GS_INVOCATION_COUNT 4 #define MMIO_REGS_CL_PRIMITIVES_COUNT 5 #define MMIO_REGS_CL_INVOCATION_COUNT 6 #define MMIO_REGS_PS_INVOCATION_COUNT 7 #define MMIO_REGS_PS_DEPTH_COUNT 8 typedef struct drm_i915_mmio_entry { unsigned int flag; unsigned int offset; unsigned int size; } drm_i915_mmio_entry_t; typedef struct drm_i915_mmio { unsigned int read_write:1; unsigned int reg:31; void __user *data; } drm_i915_mmio_t; typedef struct drm_i915_hws_addr { uint64_t addr; } drm_i915_hws_addr_t; /* * Relocation header is 4 uint32_ts * 0 - (16-bit relocation type << 16)| 16 bit reloc count * 1 - buffer handle for another list of relocs * 2-3 - spare. */ #define I915_RELOC_HEADER 4 /* * type 0 relocation has 4-uint32_t stride * 0 - offset into buffer * 1 - delta to add in * 2 - index into buffer list * 3 - reserved (for optimisations later). */ #define I915_RELOC_TYPE_0 0 #define I915_RELOC0_STRIDE 4 struct drm_i915_op_arg { uint64_t next; uint32_t reloc_handle; int handled; union { struct drm_bo_op_req req; struct drm_bo_arg_rep rep; } d; }; struct drm_i915_execbuffer { uint64_t ops_list; uint32_t num_buffers; struct drm_i915_batchbuffer batch; drm_context_t context; /* for lockless use in the future */ struct drm_fence_arg fence_arg; }; #endif /* _I915_DRM_H_ */ href='#n255'>255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 
/* xf86drmSL.c -- Skip list support
 * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
 *
 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 * 
 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
 *
 * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.3 2000/06/17 00:03:34 martin Exp $
 *
 * DESCRIPTION
 *
 * This file contains a straightforward skip list implementation.n
 *
 * FUTURE ENHANCEMENTS
 *
 * REFERENCES
 *
 * [Pugh90] William Pugh.  Skip Lists: A Probabilistic Alternative to
 * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
 *
 */

#ifdef HAVE_XORG_CONFIG_H
#include <xorg-config.h>
#endif

#define SL_MAIN 0

#if SL_MAIN
# include <stdio.h>
# include <stdlib.h>
#  include <sys/time.h>
#else
# include "drm.h"
# include "xf86drm.h"
# ifdef XFree86LOADER
#  include "xf86.h"
#  include "xf86_ansic.h"
# else
#  include <stdio.h>
#  include <stdlib.h>
# endif
#endif

#define SL_LIST_MAGIC  0xfacade00LU
#define SL_ENTRY_MAGIC 0x00fab1edLU
#define SL_FREED_MAGIC 0xdecea5edLU
#define SL_MAX_LEVEL   16
#define SL_DEBUG       0
#define SL_RANDOM_SEED 0xc01055a1LU

#if SL_MAIN
#define SL_ALLOC malloc
#define SL_FREE  free
#define SL_RANDOM_DECL        static int state = 0;
#define SL_RANDOM_INIT(seed)  if (!state) { srandom(seed); ++state; }
#define SL_RANDOM             random()
#else
#define SL_ALLOC drmMalloc
#define SL_FREE  drmFree
#define SL_RANDOM_DECL        static void *state = NULL
#define SL_RANDOM_INIT(seed)  if (!state) state = drmRandomCreate(seed)
#define SL_RANDOM             drmRandom(state)

#endif

typedef struct SLEntry {
    unsigned long     magic;	   /* SL_ENTRY_MAGIC */
    unsigned long     key;
    void              *value;
    int               levels;
    struct SLEntry    *forward[1]; /* variable sized array */
} SLEntry, *SLEntryPtr;

typedef struct SkipList {
    unsigned long    magic;	/* SL_LIST_MAGIC */
    int              level;
    int              count;
    SLEntryPtr       head;
    SLEntryPtr       p0;	/* Position for iteration */
} SkipList, *SkipListPtr;

#if SL_MAIN
extern void *drmSLCreate(void);
extern int  drmSLDestroy(void *l);
extern int  drmSLLookup(void *l, unsigned long key, void **value);
extern int  drmSLInsert(void *l, unsigned long key, void *value);
extern int  drmSLDelete(void *l, unsigned long key);
extern int  drmSLNext(void *l, unsigned long *key, void **value);
extern int  drmSLFirst(void *l, unsigned long *key, void **value);
extern void drmSLDump(void *l);
extern int  drmSLLookupNeighbors(void *l, unsigned long key,
				 unsigned long *prev_key, void **prev_value,
				 unsigned long *next_key, void **next_value);
#endif

static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
{
    SLEntryPtr entry;
    
    if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;

    entry         = SL_ALLOC(sizeof(*entry)
			     + (max_level + 1) * sizeof(entry->forward[0]));
    if (!entry) return NULL;
    entry->magic  = SL_ENTRY_MAGIC;
    entry->key    = key;
    entry->value  = value;
    entry->levels = max_level + 1;

    return entry;
}

static int SLRandomLevel(void)
{
    int level = 1;
    SL_RANDOM_DECL;

    SL_RANDOM_INIT(SL_RANDOM_SEED);
    
    while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
    return level;
}

void *drmSLCreate(void)
{
    SkipListPtr  list;
    int          i;

    list           = SL_ALLOC(sizeof(*list));
    if (!list) return NULL;
    list->magic    = SL_LIST_MAGIC;
    list->level    = 0;
    list->head     = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
    list->count    = 0;

    for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
    
    return list;
}

int drmSLDestroy(void *l)
{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    SLEntryPtr    next;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    for (entry = list->head; entry; entry = next) {
	if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
	next         = entry->forward[0];
	entry->magic = SL_FREED_MAGIC;
	SL_FREE(entry);
    }

    list->magic = SL_FREED_MAGIC;
    SL_FREE(list);
    return 0;
}

static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return NULL;

    for (i = list->level, entry = list->head; i >= 0; i--) {
	while (entry->forward[i] && entry->forward[i]->key < key)
	    entry = entry->forward[i];
	update[i] = entry;
    }

    return entry->forward[0];
}

int drmSLInsert(void *l, unsigned long key, void *value)
{
    SkipListPtr   list  = (SkipListPtr)l;
    SLEntryPtr    entry;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    int           level;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry = SLLocate(list, key, update);

    if (entry && entry->key == key) return 1; /* Already in list */


    level = SLRandomLevel();
    if (level > list->level) {
	level = ++list->level;
	update[level] = list->head;
    }

    entry = SLCreateEntry(level, key, value);

				/* Fix up forward pointers */
    for (i = 0; i <= level; i++) {
	entry->forward[i]     = update[i]->forward[i];
	update[i]->forward[i] = entry;
    }

    ++list->count;
    return 0;			/* Added to table */
}

int drmSLDelete(void *l, unsigned long key)
{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    SLEntryPtr    entry;
    int           i;

    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry = SLLocate(list, key, update);

    if (!entry || entry->key != key) return 1; /* Not found */

				/* Fix up forward pointers */
    for (i = 0; i <= list->level; i++) {
	if (update[i]->forward[i] == entry)
	    update[i]->forward[i] = entry->forward[i];
    }

    entry->magic = SL_FREED_MAGIC;
    SL_FREE(entry);

    while (list->level && !list->head->forward[list->level]) --list->level;
    --list->count;
    return 0;
}

int drmSLLookup(void *l, unsigned long key, void **value)
{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    SLEntryPtr    entry;

    entry = SLLocate(list, key, update);

    if (entry && entry->key == key) {
	*value = entry;
	return 0;
    }
    *value = NULL;
    return -1;
}

int drmSLLookupNeighbors(void *l, unsigned long key,
			 unsigned long *prev_key, void **prev_value,
			 unsigned long *next_key, void **next_value)
{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    update[SL_MAX_LEVEL + 1];
    SLEntryPtr    entry;
    int           retcode = 0;

    entry = SLLocate(list, key, update);

    *prev_key   = *next_key   = key;
    *prev_value = *next_value = NULL;
	
    if (update[0]) {
	*prev_key   = update[0]->key;
	*prev_value = update[0]->value;
	++retcode;
	if (update[0]->forward[0]) {
	    *next_key   = update[0]->forward[0]->key;
	    *next_value = update[0]->forward[0]->value;
	    ++retcode;
	}
    }
    return retcode;
}

int drmSLNext(void *l, unsigned long *key, void **value)
{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    entry;
    
    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */

    entry    = list->p0;

    if (entry) {
	list->p0 = entry->forward[0];
	*key     = entry->key;
	*value   = entry->value;
	return 1;
    }
    list->p0 = NULL;
    return 0;
}

int drmSLFirst(void *l, unsigned long *key, void **value)
{
    SkipListPtr   list = (SkipListPtr)l;
    
    if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
    
    list->p0 = list->head->forward[0];
    return drmSLNext(list, key, value);
}

/* Dump internal data structures for debugging. */
void drmSLDump(void *l)
{
    SkipListPtr   list = (SkipListPtr)l;
    SLEntryPtr    entry;
    int           i;
    
    if (list->magic != SL_LIST_MAGIC) {
	printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
	       list->magic, SL_LIST_MAGIC);
	return;
    }

    printf("Level = %d, count = %d\n", list->level, list->count);
    for (entry = list->head; entry; entry = entry->forward[0]) {
	if (entry->magic != SL_ENTRY_MAGIC) {
	    printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
		   list->magic, SL_ENTRY_MAGIC);
	}
	printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
	       entry, entry->key, entry->value, entry->levels);
	for (i = 0; i < entry->levels; i++) {
	    if (entry->forward[i]) {
		printf("   %2d: %p <0x%08lx, %p>\n",
		       i,
		       entry->forward[i],
		       entry->forward[i]->key,
		       entry->forward[i]->value);
	    } else {
		printf("   %2d: %p\n", i, entry->forward[i]);
	    }
	}
    }
}

#if SL_MAIN
static void print(SkipListPtr list)
{
    unsigned long key;
    void          *value;
    
    if (drmSLFirst(list, &key, &value)) {
	do {
	    printf("key = %5lu, value = %p\n", key, value);
	} while (drmSLNext(list, &key, &value));
    }
}

static double do_time(int size, int iter)
{
    SkipListPtr    list;
    int            i, j;
    unsigned long  keys[1000000];
    unsigned long  previous;
    unsigned long  key;
    void           *value;
    struct timeval start, stop;
    double         usec;
    SL_RANDOM_DECL;

    SL_RANDOM_INIT(12345);
    
    list = drmSLCreate();

    for (i = 0; i < size; i++) {
	keys[i] = SL_RANDOM;
	drmSLInsert(list, keys[i], NULL);
    }

    previous = 0;
    if (drmSLFirst(list, &key, &value)) {
	do {
	    if (key <= previous) {
		printf( "%lu !< %lu\n", previous, key);
	    }
	    previous = key;
	} while (drmSLNext(list, &key, &value));
    }
    
    gettimeofday(&start, NULL);
    for (j = 0; j < iter; j++) {
	for (i = 0; i < size; i++) {
	    if (drmSLLookup(list, keys[i], &value))
		printf("Error %lu %d\n", keys[i], i);
	}
    }
    gettimeofday(&stop, NULL);
    
    usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec
		    - start.tv_sec * 1000000 - start.tv_usec) / (size * iter);
    
    printf("%0.2f microseconds for list length %d\n", usec, size);

    drmSLDestroy(list);
    
    return usec;
}

static void print_neighbors(void *list, unsigned long key)
{
    unsigned long prev_key = 0;
    unsigned long next_key = 0;
    void          *prev_value;
    void          *next_value;
    int           retval;

    retval = drmSLLookupNeighbors(list, key,
				  &prev_key, &prev_value,
				  &next_key, &next_value);
    printf("Neighbors of %5lu: %d %5lu %5lu\n",
	   key, retval, prev_key, next_key);
}

int main(void)
{
    SkipListPtr    list;
    double         usec, usec2, usec3, usec4;

    list = drmSLCreate();
    printf( "list at %p\n", list);

    print(list);
    printf("\n==============================\n\n");

    drmSLInsert(list, 123, NULL);
    drmSLInsert(list, 213, NULL);
    drmSLInsert(list, 50, NULL);
    print(list);
    printf("\n==============================\n\n");
    
    print_neighbors(list, 0);
    print_neighbors(list, 50);
    print_neighbors(list, 51);
    print_neighbors(list, 123);
    print_neighbors(list, 200);
    print_neighbors(list, 213);
    print_neighbors(list, 256);
    printf("\n==============================\n\n");    
    
    drmSLDelete(list, 50);
    print(list);
    printf("\n==============================\n\n");

    drmSLDump(list);
    drmSLDestroy(list);
    printf("\n==============================\n\n");

    usec  = do_time(100, 10000);
    usec2 = do_time(1000, 500);
    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
	   1000.0/100.0, usec2 / usec);
    
    usec3 = do_time(10000, 50);
    printf("Table size increased by %0.2f, search time increased by %0.2f\n",
	   10000.0/100.0, usec3 / usec);
    
    usec4 = do_time(100000, 4);