1/* 2 * Copyright © 2004 Keith Packard and Bart Massey. 3 * All Rights Reserved. See the file COPYING in this directory 4 * for licensing information. 5 */ 6 7autoload PRNG; 8 9namespace Skiplist { 10 public typedef bool (poly a, poly b) Greater; 11 12 public typedef void (poly a) Visit; 13 14 public exception not_found (poly missing); 15 16 /* 17 * Private representation of an element 18 */ 19 typedef Element; 20 21 typedef union { 22 *Element element; 23 void nil; 24 } ElementPtr; 25 26 const MaxLevel = 16; 27 28 typedef struct { 29 poly value; 30 ElementPtr[*] forward; 31 } Element; 32 33 typedef struct { 34 int level; 35 Greater greater; 36 Element header; 37 } SkipRec; 38 39 public typedef *SkipRec Skip; 40 41 int random_level () 42 /* 43 * This uses a fixed probability of 1/4 for each level 44 */ 45 { 46 int bits = PRNG::randbits(MaxLevel * 2); 47 int level = 0; 48 49 while (++level < MaxLevel) 50 { 51 if ((bits & 3) != 0) 52 break; 53 bits >>= 2; 54 } 55 return level; 56 } 57 58 public Skip new (Greater greater) 59 /* 60 * Allocate a new list with 'greater' as the ordering function 61 */ 62 { 63 return &(SkipRec) { 64 .level = 0, 65 .greater = greater, 66 .header = { 67 .forward = (ElementPtr[MaxLevel]) { [i] = ElementPtr.nil }, 68 .value = <> 69 } 70 }; 71 } 72 73 public poly search (Skip list, poly value) 74 /* 75 * Search 'list' for 'value', returning a 76 * matching value in the list else Raise 'not_found'. 77 */ 78 { 79 ElementPtr x = (ElementPtr.element) &list->header; 80 81 for (int i = list->level; --i >= 0; ) 82 { 83 while (x.element->forward[i] != ElementPtr.nil && 84 list->greater (value, 85 x.element->forward[i].element->value)) 86 x = x.element->forward[i]; 87 } 88 x = x.element->forward[0]; 89 if (x == ElementPtr.nil || list->greater (x.element->value, value)) 90 raise not_found (value); 91 return x.element->value; 92 } 93 94 public void insert (Skip list, poly value) 95 /* 96 * Insert 'value' into 'list' 97 */ 98 { 99 ElementPtr[MaxLevel] update = {}; 100 ElementPtr x = (ElementPtr.element) &list->header; 101 102 for (int i = list->level; --i >= 0;) 103 { 104 while (x.element->forward[i] != ElementPtr.nil && 105 list->greater (value, 106 x.element->forward[i].element->value)) 107 x = x.element->forward[i]; 108 update[i] = x; 109 } 110 x = x.element->forward[0]; 111 int level = random_level (); 112 if (level > list->level) 113 { 114 level = list->level + 1; 115 list->level = level; 116 update[level-1] = (ElementPtr.element) &list->header; 117 } 118 119 /* 120 * Allocate new list entry 121 */ 122 ElementPtr new = (ElementPtr.element) &(Element) { 123 .value = value, 124 .forward = (ElementPtr[level]) {} 125 }; 126 127 for (int i = 0; i < level; i++) 128 { 129 new.element->forward[i] = update[i].element->forward[i]; 130 update[i].element->forward[i] = new; 131 } 132 } 133 134 public void delete (Skip list, poly value) 135 /* 136 * delete entry matching 'value' from 'list', else 137 * raise not_found. 138 */ 139 { 140 ElementPtr[MaxLevel] update = {}; 141 ElementPtr x = (ElementPtr.element) &list->header; 142 143 for (int i = list->level; --i >= 0;) 144 { 145 while (x.element->forward[i] != ElementPtr.nil && 146 list->greater (value, 147 x.element->forward[i].element->value)) 148 x = x.element->forward[i]; 149 update[i] = x; 150 } 151 x = x.element->forward[0]; 152 if (x == ElementPtr.nil || list->greater (x.element->value, value)) 153 raise not_found (value); 154 155 for (int i = 0; 156 i < list->level && update[i].element->forward[i] == x; 157 i++) 158 { 159 update[i].element->forward[i] = x.element->forward[i]; 160 } 161 162 while (list->level > 0 && 163 list->header.forward[list->level-1] == ElementPtr.nil) 164 list->level--; 165 } 166 167 public void walk (Skip list, Visit visit) 168 /* 169 * Invoke 'visit' for each element of 'list'. 170 * Operations on 171 */ 172 { 173 for (ElementPtr e = list->header.forward[0]; 174 e != ElementPtr.nil; 175 e = (ElementPtr next)) 176 { 177 next = e.element->forward[0]; 178 visit (e.element->value); 179 } 180 } 181 182 public bool (&poly) iterate (Skip list) 183 { 184 ElementPtr e = list->header.forward[0]; 185 186 bool next (&poly value) { 187 if (e == ElementPtr.nil) 188 return false; 189 value = e.element->value; 190 e = e.element->forward[0]; 191 return true; 192 } 193 194 return next; 195 } 196 197 public int length (Skip list) 198 { 199 int len = 0; 200 for (ElementPtr e = list->header.forward[0]; 201 e != ElementPtr.nil; 202 e = e.element->forward[0]) 203 { 204 len++; 205 } 206 return len; 207 } 208 209 public int storage (Skip list, poly value) 210 { 211 ElementPtr x = (ElementPtr.element) &list->header; 212 213 for (int i = list->level; --i >= 0;) 214 { 215 while (x.element->forward[i] != ElementPtr.nil && 216 list->greater (value, 217 x.element->forward[i].element->value)) 218 x = x.element->forward[i]; 219 } 220 x = x.element->forward[0]; 221 if (x == ElementPtr.nil || list->greater (x.element->value, value)) 222 raise not_found (value); 223 return dim (x.element->forward); 224 } 225} 226 227namespace Sortlist { 228 public import Skiplist; 229} 230