/* xf86drmSL.c -- Skip list support
* Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
- * Revised: Thu Jun 3 16:13:01 1999 by faith@precisioninsight.com
*
* Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
* All Rights Reserved.
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*
- * $PI: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.2 1999/06/07 13:01:42 faith Exp $
- * $XFree86: xc/programs/Xserver/hw/xfree86/os-support/linux/drm/xf86drmSL.c,v 1.1 1999/06/14 07:32:02 dawes Exp $
+ * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
*
* DESCRIPTION
*
*
*/
+#include <stdio.h>
+#include <stdlib.h>
+
#define SL_MAIN 0
-#if SL_MAIN
-# include <stdio.h>
-# include <stdlib.h>
-# include <sys/time.h>
-#else
+#if !SL_MAIN
# include "xf86drm.h"
-# ifdef XFree86LOADER
-# include "xf86.h"
-# include "xf86_ansic.h"
-# else
-# include <stdio.h>
-# include <stdlib.h>
-# endif
+#else
+# include <sys/time.h>
#endif
-#define N(x) drm##x
-
#define SL_LIST_MAGIC 0xfacade00LU
#define SL_ENTRY_MAGIC 0x00fab1edLU
#define SL_FREED_MAGIC 0xdecea5edLU
} SkipList, *SkipListPtr;
#if SL_MAIN
-extern void *N(SLCreate)(void);
-extern int N(SLDestroy)(void *l);
-extern int N(SLLookup)(void *l, unsigned long key, void **value);
-extern int N(SLInsert)(void *l, unsigned long key, void *value);
-extern int N(SLDelete)(void *l, unsigned long key);
-extern int N(SLNext)(void *l, unsigned long *key, void **value);
-extern int N(SLFirst)(void *l, unsigned long *key, void **value);
-extern void N(SLDump)(void *l);
-extern int N(SLLookupNeighbors)(void *l, unsigned long key,
+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
return level;
}
-void *N(SLCreate)(void)
+void *drmSLCreate(void)
{
SkipListPtr list;
int i;
return list;
}
-int N(SLDestroy)(void *l)
+int drmSLDestroy(void *l)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr entry;
return entry->forward[0];
}
-int N(SLInsert)(void *l, unsigned long key, void *value)
+int drmSLInsert(void *l, unsigned long key, void *value)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr entry;
return 0; /* Added to table */
}
-int N(SLDelete)(void *l, unsigned long key)
+int drmSLDelete(void *l, unsigned long key)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr update[SL_MAX_LEVEL + 1];
return 0;
}
-int N(SLLookup)(void *l, unsigned long key, void **value)
+int drmSLLookup(void *l, unsigned long key, void **value)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr update[SL_MAX_LEVEL + 1];
return -1;
}
-int N(SLLookupNeighbors)(void *l, unsigned long key,
+int drmSLLookupNeighbors(void *l, unsigned long key,
unsigned long *prev_key, void **prev_value,
unsigned long *next_key, void **next_value)
{
return retcode;
}
-int N(SLNext)(void *l, unsigned long *key, void **value)
+int drmSLNext(void *l, unsigned long *key, void **value)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr entry;
return 0;
}
-int N(SLFirst)(void *l, unsigned long *key, void **value)
+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 N(SLNext)(list, key, value);
+ return drmSLNext(list, key, value);
}
/* Dump internal data structures for debugging. */
-void N(SLDump)(void *l)
+void drmSLDump(void *l)
{
SkipListPtr list = (SkipListPtr)l;
SLEntryPtr entry;
unsigned long key;
void *value;
- if (N(SLFirst)(list, &key, &value)) {
+ if (drmSLFirst(list, &key, &value)) {
do {
printf("key = %5lu, value = %p\n", key, value);
- } while (N(SLNext)(list, &key, &value));
+ } while (drmSLNext(list, &key, &value));
}
}
SL_RANDOM_INIT(12345);
- list = N(SLCreate)();
+ list = drmSLCreate();
for (i = 0; i < size; i++) {
keys[i] = SL_RANDOM;
- N(SLInsert)(list, keys[i], NULL);
+ drmSLInsert(list, keys[i], NULL);
}
previous = 0;
- if (N(SLFirst)(list, &key, &value)) {
+ if (drmSLFirst(list, &key, &value)) {
do {
if (key <= previous) {
printf( "%lu !< %lu\n", previous, key);
}
previous = key;
- } while (N(SLNext)(list, &key, &value));
+ } while (drmSLNext(list, &key, &value));
}
gettimeofday(&start, NULL);
for (j = 0; j < iter; j++) {
for (i = 0; i < size; i++) {
- if (N(SLLookup)(list, keys[i], &value))
+ if (drmSLLookup(list, keys[i], &value))
printf("Error %lu %d\n", keys[i], i);
}
}
printf("%0.2f microseconds for list length %d\n", usec, size);
- N(SLDestroy)(list);
+ drmSLDestroy(list);
return usec;
}
SkipListPtr list;
double usec, usec2, usec3, usec4;
- list = N(SLCreate)();
+ list = drmSLCreate();
printf( "list at %p\n", list);
print(list);
printf("\n==============================\n\n");
- N(SLInsert)(list, 123, NULL);
- N(SLInsert)(list, 213, NULL);
- N(SLInsert)(list, 50, NULL);
+ drmSLInsert(list, 123, NULL);
+ drmSLInsert(list, 213, NULL);
+ drmSLInsert(list, 50, NULL);
print(list);
printf("\n==============================\n\n");
print_neighbors(list, 256);
printf("\n==============================\n\n");
- N(SLDelete)(list, 50);
+ drmSLDelete(list, 50);
print(list);
printf("\n==============================\n\n");
- N(SLDump)(list);
- N(SLDestroy)(list);
+ drmSLDump(list);
+ drmSLDestroy(list);
printf("\n==============================\n\n");
usec = do_time(100, 10000);