1 
/* ====================================================================== 

2 
* Copyright (c) 2000,2006 Theo Schlossnagle 

3 
* All rights reserved. 

4 
* The following code was written by Theo Schlossnagle for use in the 

5 
* Backhand project at The Center for Networking and Distributed Systems 

6 
* at The Johns Hopkins University. 

7 
* 

8 
* This is a skiplist implementation to be used for abstract structures 

9 
* and is release under the LGPL license version 2.1 or later. A copy 

10 
* of this license can be found file LGPL. 

11 
* 

12 
* Alternatively, this file may be licensed under the new BSD license. 

13 
* A copy of this license can be found file BSD. 

14 
* 

15 
* ====================================================================== 

16 
*/ 

17 


18 
#include <stdio.h> 

19 
#include <stdlib.h> 

20 
#include <assert.h> 

21 


22 
#include "noit_skiplist.h" 

23 


24 
#ifndef MIN 

25 
#define MIN(a,b) ((a<b)?(a):(b)) 

26 
#endif 

27 


28 
int noit_compare_voidptr(void *a, void *b) { 

29 
if(a < b) return 1; 

30 
if(a == b) return 0; 

31 
return 1; 

32 
} 

33 


34 
static int get_b_rand(void) { 

35 
static int ph=32; /* More bits than we will ever use */ 

36 
static unsigned long randseq; 

37 
if(ph > 31) { /* Num bits in return of lrand48() */ 

38 
ph=0; 

39 
randseq = lrand48(); 

40 
} 

41 
ph++; 

42 
return ((randseq & (1 << (ph1))) >> (ph1)); 

43 
} 

44 


45 
void noit_skiplisti_init(noit_skiplist *sl) { 

46 
sl>compare = (noit_skiplist_comparator_t)NULL; 

47 
sl>comparek = (noit_skiplist_comparator_t)NULL; 

48 
sl>height=0; 

49 
sl>preheight=0; 

50 
sl>size=0; 

51 
sl>top = NULL; 

52 
sl>bottom = NULL; 

53 
sl>index = NULL; 

54 
} 

55 


56 
static int indexing_comp(void *a, void *b) { 

57 
assert(a); 

58 
assert(b); 

59 
return (void *)(((noit_skiplist *)a)>compare)>(void *)(((noit_skiplist *)b)>compare); 

60 
} 

61 
static int indexing_compk(void *a, void *b) { 

62 
assert(b); 

63 
return a>(void *)(((noit_skiplist *)b)>compare); 

64 
} 

65 


66 
void noit_skiplist_init(noit_skiplist *sl) { 

67 
noit_skiplisti_init(sl); 

68 
sl>index = (noit_skiplist *)malloc(sizeof(noit_skiplist)); 

69 
noit_skiplisti_init(sl>index); 

70 
noit_skiplist_set_compare(sl>index, indexing_comp, indexing_compk); 

71 
} 

72 


73 
void noit_skiplist_set_compare(noit_skiplist *sl, 

74 
noit_skiplist_comparator_t comp, 

75 
noit_skiplist_comparator_t compk) { 

76 
if(sl>compare && sl>comparek) { 

77 
noit_skiplist_add_index(sl, comp, compk); 

78 
} else { 

79 
sl>compare = comp; 

80 
sl>comparek = compk; 

81 
} 

82 
} 

83 


84 
void noit_skiplist_add_index(noit_skiplist *sl, 

85 
noit_skiplist_comparator_t comp, 

86 
noit_skiplist_comparator_t compk) { 

87 
noit_skiplist_node *m; 

88 
noit_skiplist *ni; 

89 
int icount=0; 

90 
noit_skiplist_find(sl>index, (void *)comp, &m); 

91 
if(m) return; /* Index already there! */ 

92 
ni = (noit_skiplist *)malloc(sizeof(noit_skiplist)); 

93 
noit_skiplisti_init(ni); 

94 
noit_skiplist_set_compare(ni, comp, compk); 

95 
/* Build the new index... This can be expensive! */ 

96 
m = noit_skiplist_insert(sl>index, ni); 

97 
while(m>prev) m=m>prev, icount++; 

98 
for(m=noit_skiplist_getlist(sl); m; noit_skiplist_next(sl, &m)) { 

99 
int j=icount1; 

100 
noit_skiplist_node *nsln; 

101 
nsln = noit_skiplist_insert(ni, m>data); 

102 
/* skip from main index down list */ 

103 
while(j>0) m=m>nextindex, j; 

104 
/* insert this node in the indexlist after m */ 

105 
nsln>nextindex = m>nextindex; 

106 
if(m>nextindex) m>nextindex>previndex = nsln; 

107 
nsln>previndex = m; 

108 
m>nextindex = nsln; 

109 
} 

110 
} 

111 


112 
noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl) { 

113 
if(!sl>bottom) return NULL; 

114 
return sl>bottom>next; 

115 
} 

116 


117 
void *noit_skiplist_find(noit_skiplist *sl, 

118 
void *data, 

119 
noit_skiplist_node **iter) { 

120 
void *ret; 

121 
noit_skiplist_node *aiter; 

122 
if(!sl>compare) return 0; 

123 
if(iter) 

124 
ret = noit_skiplist_find_compare(sl, data, iter, sl>compare); 

125 
else 

126 
ret = noit_skiplist_find_compare(sl, data, &aiter, sl>compare); 

127 
return ret; 

128 
} 

129 
void *noit_skiplist_find_compare(noit_skiplist *sli, 

130 
void *data, 

131 
noit_skiplist_node **iter, 

132 
noit_skiplist_comparator_t comp) { 

133 
noit_skiplist_node *m = NULL; 

134 
noit_skiplist *sl; 

135 
if(comp==sli>compare  !sli>index) { 

136 
sl = sli; 

137 
} else { 

138 
noit_skiplist_find(sli>index, (void *)comp, &m); 

139 
assert(m); 

140 
sl= (noit_skiplist *) m>data; 

141 
} 

142 
noit_skiplisti_find_compare(sl, data, iter, sl>comparek); 

143 
return (*iter)?((*iter)>data):(*iter); 

144 
} 

145 
int noit_skiplisti_find_compare(noit_skiplist *sl, 

146 
void *data, 

147 
noit_skiplist_node **ret, 

148 
noit_skiplist_comparator_t comp) { 

149 
noit_skiplist_node *m = NULL; 

150 
int count=0; 

151 
m = sl>top; 

152 
while(m) { 

153 
int compared = 1; 

154 
if(m>next) compared=comp(data, m>next>data); 

155 
if(compared == 0) { 

156 
#ifdef SL_DEBUG 

157 
printf("Looking  found in %d steps\n", count); 

158 
#endif 

159 
m=m>next; 

160 
while(m>down) m=m>down; 

161 
*ret = m; 

162 
return count; 

163 
} 

164 
if((m>next == NULL)  (compared<0)) 

165 
m = m>down, count++; 

166 
else 

167 
m = m>next, count++; 

168 
} 

169 
#ifdef SL_DEBUG 

170 
printf("Looking  not found in %d steps\n", count); 

171 
#endif 

172 
*ret = NULL; 

173 
return count; 

174 
} 

175 
void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **iter) { 

176 
if(!*iter) return NULL; 

177 
*iter = (*iter)>next; 

178 
return (*iter)?((*iter)>data):NULL; 

179 
} 

180 
void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **iter) { 

181 
if(!*iter) return NULL; 

182 
*iter = (*iter)>prev; 

183 
return (*iter)?((*iter)>data):NULL; 

184 
} 

185 
noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, 

186 
void *data) { 

187 
if(!sl>compare) return 0; 

188 
return noit_skiplist_insert_compare(sl, data, sl>compare); 

189 
} 

190 


191 
noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl, 

192 
void *data, 

193 
noit_skiplist_comparator_t comp) { 

194 
noit_skiplist_node *m, *p, *tmp, *ret = NULL, **stack; 

195 
int nh=1, ch, stacki; 

196 
if(!sl>top) { 

197 
sl>height = 1; 

198 
sl>topend = sl>bottomend = sl>top = sl>bottom = 

199 
(noit_skiplist_node *)malloc(sizeof(noit_skiplist_node)); 

200 
assert(sl>top); 

201 
sl>top>next = (noit_skiplist_node *) NULL; 

202 
sl>top>data = (noit_skiplist_node *) NULL; 

203 
sl>top>prev =(noit_skiplist_node *) NULL; 

204 
sl>top>up = (noit_skiplist_node *) NULL; 

205 
sl>top>down = (noit_skiplist_node *) NULL; 

206 
sl>top>nextindex= (noit_skiplist_node *) NULL; 

207 
sl>top>previndex = (noit_skiplist_node *) NULL; 

208 
sl>top>sl = sl; 

209 
} 

210 
if(sl>preheight) { 

211 
while(nh < sl>preheight && get_b_rand()) nh++; 

212 
} else { 

213 
while(nh <= sl>height && get_b_rand()) nh++; 

214 
} 

215 
/* Now we have the new height at which we wish to insert our new node */ 

216 
/* Let us make sure that our tree is a least that tall (grow if necessary)*/ 

217 
for(;sl>height<nh;sl>height++) { 

218 
sl>top>up = 

219 
(noit_skiplist_node *)malloc(sizeof(noit_skiplist_node)); 

220 
assert(sl>top>up); 

221 
sl>top>up>down = sl>top; 

222 
sl>top = sl>topend = sl>top>up; 

223 
sl>top>prev = sl>top>next = sl>top>nextindex = 

224 
sl>top>previndex = sl>top>up = NULL; 

225 
sl>top>data = NULL; 

226 
sl>top>sl = sl; 

227 
} 

228 
ch = sl>height; 

229 
/* Find the node (or node after which we would insert) */ 

230 
/* Keep a stack to pop back through for insertion */ 

231 
m = sl>top; 

232 
stack = (noit_skiplist_node **)malloc(sizeof(noit_skiplist_node *)*(nh)); 

233 
stacki=0; 

234 
while(m) { 

235 
int compared=1; 

236 
if(m>next) compared=comp(data, m>next>data); 

237 
if(compared == 0) { 

238 
free(stack); 

239 
return 0; 

240 
} 

241 
if((m>next == NULL)  (compared<0)) { 

242 
if(ch<=nh) { 

243 
/* push on stack */ 

244 
stack[stacki++] = m; 

245 
} 

246 
m = m>down; 

247 
ch; 

248 
} else { 

249 
m = m>next; 

250 
} 

251 
} 

252 
/* Pop the stack and insert nodes */ 

253 
p = NULL; 

254 
for(;stacki>0;stacki) { 

255 
m = stack[stacki1]; 

256 
tmp = (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node)); 

257 
tmp>next = m>next; 

258 
if(m>next) m>next>prev=tmp; 

259 
tmp>prev = m; 

260 
tmp>up = NULL; 

261 
tmp>nextindex = tmp>previndex = NULL; 

262 
tmp>down = p; 

263 
if(p) p>up=tmp; 

264 
tmp>data = data; 

265 
tmp>sl = sl; 

266 
m>next = tmp; 

267 
/* This sets ret to the bottommost node we are inserting */ 

268 
if(!p) ret=tmp; 

269 
p = tmp; 

270 
} 

271 
free(stack); 

272 
if(sl>index != NULL) { 

273 
/* this is a external insertion, we must insert into each index as well */ 

274 
noit_skiplist_node *p, *ni, *li; 

275 
li=ret; 

276 
for(p = noit_skiplist_getlist(sl>index); p; noit_skiplist_next(sl>index, &p)) { 

277 
ni = noit_skiplist_insert((noit_skiplist *)p>data, ret>data); 

278 
assert(ni); 

279 
li>nextindex = ni; 

280 
ni>previndex = li; 

281 
li = ni; 

282 
} 

283 
} 

284 
sl>size++; 

285 
return ret; 

286 
} 

287 
int noit_skiplist_remove(noit_skiplist *sl, 

288 
void *data, noit_freefunc_t myfree) { 

289 
if(!sl>compare) return 0; 

290 
return noit_skiplist_remove_compare(sl, data, myfree, sl>comparek); 

291 
} 

292 
int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m, noit_freefunc_t myfree) { 

293 
noit_skiplist_node *p; 

294 
if(!m) return 0; 

295 
if(m>nextindex) noit_skiplisti_remove(m>nextindex>sl, m>nextindex, NULL); 

296 
while(m>up) m=m>up; 

297 
while(m) { 

298 
p=m; 

299 
p>prev>next = p>next; /* take me out of the list */ 

300 
if(p>next) p>next>prev = p>prev; /* take me out of the list */ 

301 
m=m>down; 

302 
/* This only frees the actual data in the bottom one */ 

303 
if(!m && myfree && p>data) myfree(p>data); 

304 
free(p); 

305 
} 

306 
sl>size; 

307 
while(sl>top && sl>top>next == NULL) { 

308 
/* While the row is empty and we are not on the bottom row */ 

309 
p = sl>top; 

310 
sl>top = sl>top>down; /* Move top down one */ 

311 
if(sl>top) sl>top>up = NULL; /* Make it think its the top */ 

312 
free(p); 

313 
sl>height; 

314 
} 

315 
if(!sl>top) sl>bottom = NULL; 

316 
assert(sl>height>=0); 

317 
return sl>height; 

318 
} 

319 
int noit_skiplist_remove_compare(noit_skiplist *sli, 

320 
void *data, 

321 
noit_freefunc_t myfree, noit_skiplist_comparator_t comp) { 

322 
noit_skiplist_node *m; 

323 
noit_skiplist *sl; 

324 
if(comp==sli>comparek  !sli>index) { 

325 
sl = sli; 

326 
} else { 

327 
noit_skiplist_find(sli>index, (void *)comp, &m); 

328 
assert(m); 

329 
sl= (noit_skiplist *) m>data; 

330 
} 

331 
noit_skiplisti_find_compare(sl, data, &m, comp); 

332 
if(!m) return 0; 

333 
while(m>previndex) m=m>previndex; 

334 
return noit_skiplisti_remove(sl, m, myfree); 

335 
} 

336 
void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree) { 

337 
/* This must remove even the place holder nodes (bottom though top) 

338 
because we specify in the API that one can free the noit_skiplist after 

339 
making this call without memory leaks */ 

340 
noit_skiplist_node *m, *p, *u; 

341 
m=sl>bottom; 

342 
while(m) { 

343 
p = m>next; 

344 
if(myfree && p>data) myfree(p>data); 

345 
while(m) { 

346 
u = m>up; 

347 
free(m); 

348 
m=u; 

349 
} 

350 
m = p; 

351 
} 

352 
sl>top = sl>bottom = NULL; 

353 
sl>height = 0; 

354 
sl>size = 0; 

355 
} 

356 


357 
void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree) 

358 
{ 

359 
noit_skiplist_node *sln; 

360 
void *data = NULL; 

361 
sln = noit_skiplist_getlist(a); 

362 
if (sln) { 

363 
data = sln>data; 

364 
noit_skiplisti_remove(a, sln, myfree); 

365 
} 

366 
return data; 

367 
} 

368 
void *noit_skiplist_peek(noit_skiplist * a) 

369 
{ 

370 
noit_skiplist_node *sln; 

371 
sln = noit_skiplist_getlist(a); 

372 
if (sln) { 

373 
return sln>data; 

374 
} 

375 
return NULL; 

376 
} 
