1f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu/* xf86drmSL.c -- Skip list support 2f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com 3f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 4f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas. 5f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * All Rights Reserved. 6f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 7f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Permission is hereby granted, free of charge, to any person obtaining a 8f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * copy of this software and associated documentation files (the "Software"), 9f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * to deal in the Software without restriction, including without limitation 10f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * the rights to use, copy, modify, merge, publish, distribute, sublicense, 11f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * and/or sell copies of the Software, and to permit persons to whom the 12f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Software is furnished to do so, subject to the following conditions: 13f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 14f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * The above copyright notice and this permission notice (including the next 15f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * paragraph) shall be included in all copies or substantial portions of the 16f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Software. 17f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 18f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 20f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 21f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR 22f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 23f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 24f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * DEALINGS IN THE SOFTWARE. 25f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 26f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Authors: Rickard E. (Rik) Faith <faith@valinux.com> 27f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 28f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * DESCRIPTION 29f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 30f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * This file contains a straightforward skip list implementation.n 31f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 32f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * FUTURE ENHANCEMENTS 33f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 34f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * REFERENCES 35f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 36f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to 37f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * Balanced Trees. CACM 33(6), June 1990, pp. 668-676. 38f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu * 39f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu */ 40f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 41f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#include <stdio.h> 42f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#include <stdlib.h> 43f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 44f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_MAIN 0 45f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 46f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#if !SL_MAIN 47f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu# include "xf86drm.h" 48f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#else 49f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu# include <sys/time.h> 50f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#endif 51f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 52f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_LIST_MAGIC 0xfacade00LU 53f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_ENTRY_MAGIC 0x00fab1edLU 54f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_FREED_MAGIC 0xdecea5edLU 55f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_MAX_LEVEL 16 56f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_DEBUG 0 57f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM_SEED 0xc01055a1LU 58f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 59f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#if SL_MAIN 60f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_ALLOC malloc 61f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_FREE free 62f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM_DECL static int state = 0; 63f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM_INIT(seed) if (!state) { srandom(seed); ++state; } 64f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM random() 65f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#else 66f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_ALLOC drmMalloc 67f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_FREE drmFree 68f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM_DECL static void *state = NULL 69f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed) 70f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#define SL_RANDOM drmRandom(state) 71f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 72f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#endif 73f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 74f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryutypedef struct SLEntry { 75f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long magic; /* SL_ENTRY_MAGIC */ 76f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long key; 77f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu void *value; 78f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int levels; 79f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu struct SLEntry *forward[1]; /* variable sized array */ 80f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} SLEntry, *SLEntryPtr; 81f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 82f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryutypedef struct SkipList { 83f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long magic; /* SL_LIST_MAGIC */ 84f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int level; 85f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int count; 86f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr head; 87f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr p0; /* Position for iteration */ 88f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} SkipList, *SkipListPtr; 89f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 90f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#if SL_MAIN 91f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern void *drmSLCreate(void); 92f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLDestroy(void *l); 93f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLLookup(void *l, unsigned long key, void **value); 94f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLInsert(void *l, unsigned long key, void *value); 95f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLDelete(void *l, unsigned long key); 96f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLNext(void *l, unsigned long *key, void **value); 97f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLFirst(void *l, unsigned long *key, void **value); 98f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern void drmSLDump(void *l); 99f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuextern int drmSLLookupNeighbors(void *l, unsigned long key, 100f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long *prev_key, void **prev_value, 101f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long *next_key, void **next_value); 102f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#endif 103f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 104f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value) 105f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 106f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 107f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 108f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL; 109f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 110f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SL_ALLOC(sizeof(*entry) 111f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu + (max_level + 1) * sizeof(entry->forward[0])); 112f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (!entry) return NULL; 113f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->magic = SL_ENTRY_MAGIC; 114f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->key = key; 115f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->value = value; 116f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->levels = max_level + 1; 117f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 118f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return entry; 119f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 120f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 121f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic int SLRandomLevel(void) 122f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 123f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int level = 1; 124f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_RANDOM_DECL; 125f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 126f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_RANDOM_INIT(SL_RANDOM_SEED); 127f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 128f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level; 129f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return level; 130f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 131f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 132f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuvoid *drmSLCreate(void) 133f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 134f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list; 135f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i; 136f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 137f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list = SL_ALLOC(sizeof(*list)); 138f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (!list) return NULL; 139f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->magic = SL_LIST_MAGIC; 140f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->level = 0; 141f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL); 142f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->count = 0; 143f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 144f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL; 145f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 146f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return list; 147f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 148f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 149f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLDestroy(void *l) 150f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 151f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 152f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 153f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr next; 154f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 155f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 156f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 157f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (entry = list->head; entry; entry = next) { 158f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */ 159f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu next = entry->forward[0]; 160f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->magic = SL_FREED_MAGIC; 161f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_FREE(entry); 162f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 163f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 164f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->magic = SL_FREED_MAGIC; 165f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_FREE(list); 166f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; 167f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 168f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 169f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update) 170f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 171f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 172f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 173f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i; 174f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 175f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return NULL; 176f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 177f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = list->level, entry = list->head; i >= 0; i--) { 178f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu while (entry->forward[i] && entry->forward[i]->key < key) 179f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = entry->forward[i]; 180f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu update[i] = entry; 181f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 182f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 183f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return entry->forward[0]; 184f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 185f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 186f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLInsert(void *l, unsigned long key, void *value) 187f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 188f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 189f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 190f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr update[SL_MAX_LEVEL + 1]; 191f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int level; 192f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i; 193f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 194f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 195f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 196f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SLLocate(list, key, update); 197f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 198f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry && entry->key == key) return 1; /* Already in list */ 199f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 200f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 201f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu level = SLRandomLevel(); 202f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (level > list->level) { 203f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu level = ++list->level; 204f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu update[level] = list->head; 205f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 206f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 207f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SLCreateEntry(level, key, value); 208f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 209f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu /* Fix up forward pointers */ 210f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i <= level; i++) { 211f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->forward[i] = update[i]->forward[i]; 212f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu update[i]->forward[i] = entry; 213f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 214f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 215f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu ++list->count; 216f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; /* Added to table */ 217f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 218f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 219f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLDelete(void *l, unsigned long key) 220f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 221f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 222f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr update[SL_MAX_LEVEL + 1]; 223f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 224f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i; 225f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 226f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 227f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 228f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SLLocate(list, key, update); 229f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 230f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (!entry || entry->key != key) return 1; /* Not found */ 231f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 232f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu /* Fix up forward pointers */ 233f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i <= list->level; i++) { 234f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (update[i]->forward[i] == entry) 235f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu update[i]->forward[i] = entry->forward[i]; 236f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 237f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 238f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->magic = SL_FREED_MAGIC; 239f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_FREE(entry); 240f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 241f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu while (list->level && !list->head->forward[list->level]) --list->level; 242f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu --list->count; 243f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; 244f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 245f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 246f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLLookup(void *l, unsigned long key, void **value) 247f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 248f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 249f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr update[SL_MAX_LEVEL + 1]; 250f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 251f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 252f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SLLocate(list, key, update); 253f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 254f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry && entry->key == key) { 255f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *value = entry; 256f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; 257f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 258f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *value = NULL; 259f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return -1; 260f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 261f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 262f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLLookupNeighbors(void *l, unsigned long key, 263f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long *prev_key, void **prev_value, 264f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long *next_key, void **next_value) 265f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 266f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 267f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr update[SL_MAX_LEVEL + 1]; 268f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 269f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int retcode = 0; 270f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 271f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = SLLocate(list, key, update); 272f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 273f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *prev_key = *next_key = key; 274f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *prev_value = *next_value = NULL; 275f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 276f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (update[0]) { 277f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *prev_key = update[0]->key; 278f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *prev_value = update[0]->value; 279f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu ++retcode; 280f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (update[0]->forward[0]) { 281f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *next_key = update[0]->forward[0]->key; 282f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *next_value = update[0]->forward[0]->value; 283f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu ++retcode; 284f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 285f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 286f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return retcode; 287f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 288f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 289f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLNext(void *l, unsigned long *key, void **value) 290f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 291f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 292f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 293f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 294f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 295f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 296f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry = list->p0; 297f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 298f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry) { 299f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->p0 = entry->forward[0]; 300f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *key = entry->key; 301f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu *value = entry->value; 302f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 1; 303f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 304f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->p0 = NULL; 305f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; 306f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 307f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 308f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint drmSLFirst(void *l, unsigned long *key, void **value) 309f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 310f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 311f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 312f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */ 313f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 314f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->p0 = list->head->forward[0]; 315f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return drmSLNext(list, key, value); 316f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 317f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 318f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu/* Dump internal data structures for debugging. */ 319f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuvoid drmSLDump(void *l) 320f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 321f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list = (SkipListPtr)l; 322f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SLEntryPtr entry; 323f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i; 324f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 325f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (list->magic != SL_LIST_MAGIC) { 326f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", 327f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->magic, SL_LIST_MAGIC); 328f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return; 329f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 330f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 331f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Level = %d, count = %d\n", list->level, list->count); 332f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (entry = list->head; entry; entry = entry->forward[0]) { 333f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry->magic != SL_ENTRY_MAGIC) { 334f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Bad magic: 0x%08lx (expected 0x%08lx)\n", 335f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list->magic, SL_ENTRY_MAGIC); 336f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 337f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\nEntry %p <0x%08lx, %p> has %2d levels\n", 338f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry, entry->key, entry->value, entry->levels); 339f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i < entry->levels; i++) { 340f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (entry->forward[i]) { 341f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf(" %2d: %p <0x%08lx, %p>\n", 342f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu i, 343f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->forward[i], 344f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->forward[i]->key, 345f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu entry->forward[i]->value); 346f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } else { 347f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf(" %2d: %p\n", i, entry->forward[i]); 348f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 349f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 350f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 351f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 352f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 353f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#if SL_MAIN 354f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic void print(SkipListPtr list) 355f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 356f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long key; 357f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu void *value; 358f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 359f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (drmSLFirst(list, &key, &value)) { 360f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu do { 361f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("key = %5lu, value = %p\n", key, value); 362f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } while (drmSLNext(list, &key, &value)); 363f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 364f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 365f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 366f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic double do_time(int size, int iter) 367f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 368f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list; 369f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int i, j; 370f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long keys[1000000]; 371f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long previous; 372f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long key; 373f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu void *value; 374f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu struct timeval start, stop; 375f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu double usec; 376f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_RANDOM_DECL; 377f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 378f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SL_RANDOM_INIT(12345); 379f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 380f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list = drmSLCreate(); 381f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 382f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i < size; i++) { 383f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu keys[i] = SL_RANDOM; 384f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLInsert(list, keys[i], NULL); 385f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 386f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 387f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu previous = 0; 388f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (drmSLFirst(list, &key, &value)) { 389f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu do { 390f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (key <= previous) { 391f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf( "%lu !< %lu\n", previous, key); 392f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 393f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu previous = key; 394f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } while (drmSLNext(list, &key, &value)); 395f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 396f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 397f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu gettimeofday(&start, NULL); 398f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (j = 0; j < iter; j++) { 399f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu for (i = 0; i < size; i++) { 400f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu if (drmSLLookup(list, keys[i], &value)) 401f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Error %lu %d\n", keys[i], i); 402f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 403f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu } 404f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu gettimeofday(&stop, NULL); 405f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 406f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu usec = (double)(stop.tv_sec * 1000000 + stop.tv_usec 407f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu - start.tv_sec * 1000000 - start.tv_usec) / (size * iter); 408f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 409f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("%0.2f microseconds for list length %d\n", usec, size); 410f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 411f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLDestroy(list); 412f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 413f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return usec; 414f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 415f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 416f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryustatic void print_neighbors(void *list, unsigned long key) 417f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 418f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long prev_key = 0; 419f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu unsigned long next_key = 0; 420f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu void *prev_value; 421f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu void *next_value; 422f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu int retval; 423f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 424f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu retval = drmSLLookupNeighbors(list, key, 425f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu &prev_key, &prev_value, 426f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu &next_key, &next_value); 427f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Neighbors of %5lu: %d %5lu %5lu\n", 428f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu key, retval, prev_key, next_key); 429f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 430f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 431f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryuint main(void) 432f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu{ 433f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu SkipListPtr list; 434f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu double usec, usec2, usec3, usec4; 435f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 436f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu list = drmSLCreate(); 437f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf( "list at %p\n", list); 438f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 439f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print(list); 440f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\n==============================\n\n"); 441f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 442f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLInsert(list, 123, NULL); 443f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLInsert(list, 213, NULL); 444f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLInsert(list, 50, NULL); 445f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print(list); 446f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\n==============================\n\n"); 447f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 448f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 0); 449f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 50); 450f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 51); 451f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 123); 452f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 200); 453f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 213); 454f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print_neighbors(list, 256); 455f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\n==============================\n\n"); 456f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 457f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLDelete(list, 50); 458f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu print(list); 459f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\n==============================\n\n"); 460f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 461f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLDump(list); 462f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu drmSLDestroy(list); 463f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("\n==============================\n\n"); 464f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 465f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu usec = do_time(100, 10000); 466f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu usec2 = do_time(1000, 500); 467f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Table size increased by %0.2f, search time increased by %0.2f\n", 468f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 1000.0/100.0, usec2 / usec); 469f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 470f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu usec3 = do_time(10000, 50); 471f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Table size increased by %0.2f, search time increased by %0.2f\n", 472f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 10000.0/100.0, usec3 / usec); 473f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 474f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu usec4 = do_time(100000, 4); 475f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu printf("Table size increased by %0.2f, search time increased by %0.2f\n", 476f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 100000.0/100.0, usec4 / usec); 477f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu 478f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu return 0; 479f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu} 480f0352d4fde4ec179ffe04c3f834199d3bad36087Ho-Eun Ryu#endif 481