xf86drmSL.c 8.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319
  1. /* xf86drmSL.c -- Skip list support
  2. * Created: Mon May 10 09:28:13 1999 by faith@precisioninsight.com
  3. *
  4. * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
  5. * All Rights Reserved.
  6. *
  7. * Permission is hereby granted, free of charge, to any person obtaining a
  8. * copy of this software and associated documentation files (the "Software"),
  9. * to deal in the Software without restriction, including without limitation
  10. * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  11. * and/or sell copies of the Software, and to permit persons to whom the
  12. * Software is furnished to do so, subject to the following conditions:
  13. *
  14. * The above copyright notice and this permission notice (including the next
  15. * paragraph) shall be included in all copies or substantial portions of the
  16. * Software.
  17. *
  18. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19. * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20. * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  21. * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  22. * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  23. * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24. * DEALINGS IN THE SOFTWARE.
  25. *
  26. * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
  27. *
  28. * DESCRIPTION
  29. *
  30. * This file contains a straightforward skip list implementation.n
  31. *
  32. * FUTURE ENHANCEMENTS
  33. *
  34. * REFERENCES
  35. *
  36. * [Pugh90] William Pugh. Skip Lists: A Probabilistic Alternative to
  37. * Balanced Trees. CACM 33(6), June 1990, pp. 668-676.
  38. *
  39. */
  40. #include <stdio.h>
  41. #include <stdlib.h>
  42. #include "libdrm_macros.h"
  43. #include "xf86drm.h"
  44. #define SL_LIST_MAGIC 0xfacade00LU
  45. #define SL_ENTRY_MAGIC 0x00fab1edLU
  46. #define SL_FREED_MAGIC 0xdecea5edLU
  47. #define SL_MAX_LEVEL 16
  48. #define SL_RANDOM_SEED 0xc01055a1LU
  49. #define SL_RANDOM_DECL static void *state = NULL
  50. #define SL_RANDOM_INIT(seed) if (!state) state = drmRandomCreate(seed)
  51. #define SL_RANDOM drmRandom(state)
  52. typedef struct SLEntry {
  53. unsigned long magic; /* SL_ENTRY_MAGIC */
  54. unsigned long key;
  55. void *value;
  56. int levels;
  57. struct SLEntry *forward[1]; /* variable sized array */
  58. } SLEntry, *SLEntryPtr;
  59. typedef struct SkipList {
  60. unsigned long magic; /* SL_LIST_MAGIC */
  61. int level;
  62. int count;
  63. SLEntryPtr head;
  64. SLEntryPtr p0; /* Position for iteration */
  65. } SkipList, *SkipListPtr;
  66. static SLEntryPtr SLCreateEntry(int max_level, unsigned long key, void *value)
  67. {
  68. SLEntryPtr entry;
  69. if (max_level < 0 || max_level > SL_MAX_LEVEL) max_level = SL_MAX_LEVEL;
  70. entry = drmMalloc(sizeof(*entry)
  71. + (max_level + 1) * sizeof(entry->forward[0]));
  72. if (!entry) return NULL;
  73. entry->magic = SL_ENTRY_MAGIC;
  74. entry->key = key;
  75. entry->value = value;
  76. entry->levels = max_level + 1;
  77. return entry;
  78. }
  79. static int SLRandomLevel(void)
  80. {
  81. int level = 1;
  82. SL_RANDOM_DECL;
  83. SL_RANDOM_INIT(SL_RANDOM_SEED);
  84. while ((SL_RANDOM & 0x01) && level < SL_MAX_LEVEL) ++level;
  85. return level;
  86. }
  87. drm_public void *drmSLCreate(void)
  88. {
  89. SkipListPtr list;
  90. int i;
  91. list = drmMalloc(sizeof(*list));
  92. if (!list) return NULL;
  93. list->magic = SL_LIST_MAGIC;
  94. list->level = 0;
  95. list->head = SLCreateEntry(SL_MAX_LEVEL, 0, NULL);
  96. list->count = 0;
  97. for (i = 0; i <= SL_MAX_LEVEL; i++) list->head->forward[i] = NULL;
  98. return list;
  99. }
  100. drm_public int drmSLDestroy(void *l)
  101. {
  102. SkipListPtr list = (SkipListPtr)l;
  103. SLEntryPtr entry;
  104. SLEntryPtr next;
  105. if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
  106. for (entry = list->head; entry; entry = next) {
  107. if (entry->magic != SL_ENTRY_MAGIC) return -1; /* Bad magic */
  108. next = entry->forward[0];
  109. entry->magic = SL_FREED_MAGIC;
  110. drmFree(entry);
  111. }
  112. list->magic = SL_FREED_MAGIC;
  113. drmFree(list);
  114. return 0;
  115. }
  116. static SLEntryPtr SLLocate(void *l, unsigned long key, SLEntryPtr *update)
  117. {
  118. SkipListPtr list = (SkipListPtr)l;
  119. SLEntryPtr entry;
  120. int i;
  121. if (list->magic != SL_LIST_MAGIC) return NULL;
  122. for (i = list->level, entry = list->head; i >= 0; i--) {
  123. while (entry->forward[i] && entry->forward[i]->key < key)
  124. entry = entry->forward[i];
  125. update[i] = entry;
  126. }
  127. return entry->forward[0];
  128. }
  129. drm_public int drmSLInsert(void *l, unsigned long key, void *value)
  130. {
  131. SkipListPtr list = (SkipListPtr)l;
  132. SLEntryPtr entry;
  133. SLEntryPtr update[SL_MAX_LEVEL + 1];
  134. int level;
  135. int i;
  136. if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
  137. entry = SLLocate(list, key, update);
  138. if (entry && entry->key == key) return 1; /* Already in list */
  139. level = SLRandomLevel();
  140. if (level > list->level) {
  141. level = ++list->level;
  142. update[level] = list->head;
  143. }
  144. entry = SLCreateEntry(level, key, value);
  145. /* Fix up forward pointers */
  146. for (i = 0; i <= level; i++) {
  147. entry->forward[i] = update[i]->forward[i];
  148. update[i]->forward[i] = entry;
  149. }
  150. ++list->count;
  151. return 0; /* Added to table */
  152. }
  153. drm_public int drmSLDelete(void *l, unsigned long key)
  154. {
  155. SkipListPtr list = (SkipListPtr)l;
  156. SLEntryPtr update[SL_MAX_LEVEL + 1];
  157. SLEntryPtr entry;
  158. int i;
  159. if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
  160. entry = SLLocate(list, key, update);
  161. if (!entry || entry->key != key) return 1; /* Not found */
  162. /* Fix up forward pointers */
  163. for (i = 0; i <= list->level; i++) {
  164. if (update[i]->forward[i] == entry)
  165. update[i]->forward[i] = entry->forward[i];
  166. }
  167. entry->magic = SL_FREED_MAGIC;
  168. drmFree(entry);
  169. while (list->level && !list->head->forward[list->level]) --list->level;
  170. --list->count;
  171. return 0;
  172. }
  173. drm_public int drmSLLookup(void *l, unsigned long key, void **value)
  174. {
  175. SkipListPtr list = (SkipListPtr)l;
  176. SLEntryPtr update[SL_MAX_LEVEL + 1];
  177. SLEntryPtr entry;
  178. entry = SLLocate(list, key, update);
  179. if (entry && entry->key == key) {
  180. *value = entry;
  181. return 0;
  182. }
  183. *value = NULL;
  184. return -1;
  185. }
  186. drm_public int drmSLLookupNeighbors(void *l, unsigned long key,
  187. unsigned long *prev_key, void **prev_value,
  188. unsigned long *next_key, void **next_value)
  189. {
  190. SkipListPtr list = (SkipListPtr)l;
  191. SLEntryPtr update[SL_MAX_LEVEL + 1] = {0};
  192. int retcode = 0;
  193. SLLocate(list, key, update);
  194. *prev_key = *next_key = key;
  195. *prev_value = *next_value = NULL;
  196. if (update[0]) {
  197. *prev_key = update[0]->key;
  198. *prev_value = update[0]->value;
  199. ++retcode;
  200. if (update[0]->forward[0]) {
  201. *next_key = update[0]->forward[0]->key;
  202. *next_value = update[0]->forward[0]->value;
  203. ++retcode;
  204. }
  205. }
  206. return retcode;
  207. }
  208. drm_public int drmSLNext(void *l, unsigned long *key, void **value)
  209. {
  210. SkipListPtr list = (SkipListPtr)l;
  211. SLEntryPtr entry;
  212. if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
  213. entry = list->p0;
  214. if (entry) {
  215. list->p0 = entry->forward[0];
  216. *key = entry->key;
  217. *value = entry->value;
  218. return 1;
  219. }
  220. list->p0 = NULL;
  221. return 0;
  222. }
  223. drm_public int drmSLFirst(void *l, unsigned long *key, void **value)
  224. {
  225. SkipListPtr list = (SkipListPtr)l;
  226. if (list->magic != SL_LIST_MAGIC) return -1; /* Bad magic */
  227. list->p0 = list->head->forward[0];
  228. return drmSLNext(list, key, value);
  229. }
  230. /* Dump internal data structures for debugging. */
  231. drm_public void drmSLDump(void *l)
  232. {
  233. SkipListPtr list = (SkipListPtr)l;
  234. SLEntryPtr entry;
  235. int i;
  236. if (list->magic != SL_LIST_MAGIC) {
  237. printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
  238. list->magic, SL_LIST_MAGIC);
  239. return;
  240. }
  241. printf("Level = %d, count = %d\n", list->level, list->count);
  242. for (entry = list->head; entry; entry = entry->forward[0]) {
  243. if (entry->magic != SL_ENTRY_MAGIC) {
  244. printf("Bad magic: 0x%08lx (expected 0x%08lx)\n",
  245. list->magic, SL_ENTRY_MAGIC);
  246. }
  247. printf("\nEntry %p <0x%08lx, %p> has %2d levels\n",
  248. entry, entry->key, entry->value, entry->levels);
  249. for (i = 0; i < entry->levels; i++) {
  250. if (entry->forward[i]) {
  251. printf(" %2d: %p <0x%08lx, %p>\n",
  252. i,
  253. entry->forward[i],
  254. entry->forward[i]->key,
  255. entry->forward[i]->value);
  256. } else {
  257. printf(" %2d: %p\n", i, entry->forward[i]);
  258. }
  259. }
  260. }
  261. }