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 
static int noit_skiplisti_find_compare(noit_skiplist *sl, const void *data, 

29 
noit_skiplist_node **ret, 

30 
noit_skiplist_node **prev, 

31 
noit_skiplist_node **next, 

32 
noit_skiplist_comparator_t comp); 

33 


34 
int noit_compare_voidptr(const void *a, const void *b) { 

35 
if(a < b) return 1; 

36 
if(a == b) return 0; 

37 
return 1; 

38 
} 

39 


40 
static int get_b_rand(void) { 

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

42 
static unsigned long randseq; 

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

44 
ph=0; 

45 
randseq = lrand48(); 

46 
} 

47 
ph++; 

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

49 
} 

50 


51 
void noit_skiplisti_init(noit_skiplist *sl) { 

52 
sl>compare = (noit_skiplist_comparator_t)NULL; 

53 
sl>comparek = (noit_skiplist_comparator_t)NULL; 

54 
sl>height=0; 

55 
sl>preheight=0; 

56 
sl>size=0; 

57 
sl>top = NULL; 

58 
sl>bottom = NULL; 

59 
sl>index = NULL; 

60 
} 

61 


62 
static int indexing_comp(const void *a, const void *b) { 

63 
assert(a); 

64 
assert(b); 

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

66 
} 

67 
static int indexing_compk(const void *a, const void *b) { 

68 
assert(b); 

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

70 
} 

71 


72 
void noit_skiplist_init(noit_skiplist *sl) { 

73 
noit_skiplisti_init(sl); 

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

75 
noit_skiplisti_init(sl>index); 

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

77 
} 

78 


79 
void noit_skiplist_set_compare(noit_skiplist *sl, 

80 
noit_skiplist_comparator_t comp, 

81 
noit_skiplist_comparator_t compk) { 

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

83 
noit_skiplist_add_index(sl, comp, compk); 

84 
} else { 

85 
sl>compare = comp; 

86 
sl>comparek = compk; 

87 
} 

88 
} 

89 


90 
void noit_skiplist_add_index(noit_skiplist *sl, 

91 
noit_skiplist_comparator_t comp, 

92 
noit_skiplist_comparator_t compk) { 

93 
noit_skiplist_node *m; 

94 
noit_skiplist *ni; 

95 
int icount=0; 

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

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

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

99 
noit_skiplisti_init(ni); 

100 
noit_skiplist_set_compare(ni, comp, compk); 

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

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

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

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

105 
int j=icount1; 

106 
noit_skiplist_node *nsln; 

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

108 
/* skip from main index down list */ 

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

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

111 
nsln>nextindex = m>nextindex; 

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

113 
nsln>previndex = m; 

114 
m>nextindex = nsln; 

115 
} 

116 
} 

117 


118 
noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl) { 

119 
if(!sl>bottom) return NULL; 

120 
return sl>bottom>next; 

121 
} 

122 


123 
void *noit_skiplist_find(noit_skiplist *sl, 

124 
const void *data, 

125 
noit_skiplist_node **iter) { 

126 
return noit_skiplist_find_neighbors(sl, data, iter, NULL, NULL); 

127 
} 

128 
void *noit_skiplist_find_neighbors(noit_skiplist *sl, 

129 
const void *data, 

130 
noit_skiplist_node **iter, 

131 
noit_skiplist_node **prev, 

132 
noit_skiplist_node **next) { 

133 
void *ret; 

134 
noit_skiplist_node *aiter; 

135 
if(!sl>compare) return 0; 

136 
if(iter) 

137 
ret = noit_skiplist_find_neighbors_compare(sl, data, iter, 

138 
prev, next, sl>compare); 

139 
else 

140 
ret = noit_skiplist_find_neighbors_compare(sl, data, &aiter, 

141 
prev, next, sl>compare); 

142 
return ret; 

143 
} 

144 


145 
void *noit_skiplist_find_compare(noit_skiplist *sli, 

146 
const void *data, 

147 
noit_skiplist_node **iter, 

148 
noit_skiplist_comparator_t comp) { 

149 
return noit_skiplist_find_neighbors_compare(sli, data, iter, 

150 
NULL, NULL, comp); 

151 
} 

152 
void *noit_skiplist_find_neighbors_compare(noit_skiplist *sli, 

153 
const void *data, 

154 
noit_skiplist_node **iter, 

155 
noit_skiplist_node **prev, 

156 
noit_skiplist_node **next, 

157 
noit_skiplist_comparator_t comp) { 

158 
noit_skiplist_node *m = NULL; 

159 
noit_skiplist *sl; 

160 
if(iter) *iter = NULL; 

161 
if(prev) *prev = NULL; 

162 
if(next) *next = NULL; 

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

164 
sl = sli; 

165 
} else { 

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

167 
assert(m); 

168 
sl= (noit_skiplist *) m>data; 

169 
} 

170 
noit_skiplisti_find_compare(sl, data, iter, prev, next, sl>comparek); 

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

172 
} 

173 
static int noit_skiplisti_find_compare(noit_skiplist *sl, 

174 
const void *data, 

175 
noit_skiplist_node **ret, 

176 
noit_skiplist_node **prev, 

177 
noit_skiplist_node **next, 

178 
noit_skiplist_comparator_t comp) { 

179 
noit_skiplist_node *m = NULL; 

180 
int count=0; 

181 
if(ret) *ret = NULL; 

182 
if(prev) *prev = NULL; 

183 
if(next) *next = NULL; 

184 
m = sl>top; 

185 
while(m) { 

186 
int compared; 

187 
compared = (m>next) ? comp(data, m>next>data) : 1; 

188 
if(compared == 0) { /* Found */ 

189 
m=m>next; /* m>next is the match */ 

190 
while(m>down) m=m>down; /* proceed to the bottommost */ 

191 
*ret = m; 

192 
if(prev) *prev = m>prev; 

193 
if(next) *next = m>next; 

194 
return count; 

195 
} 

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

197 
if(m>down == NULL) { 

198 
/* This is... we're about to bail, figure out our neighbors */ 

199 
if(prev) *prev = (m == sl>bottom) ? NULL : m; 

200 
if(next) *next = m>next; 

201 
} 

202 
m = m>down; 

203 
count++; 

204 
} 

205 
else 

206 
m = m>next, count++; 

207 
} 

208 
*ret = NULL; 

209 
return count; 

210 
} 

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

212 
if(!*iter) return NULL; 

213 
*iter = (*iter)>next; 

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

215 
} 

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

217 
if(!*iter) return NULL; 

218 
*iter = (*iter)>prev; 

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

220 
} 

221 
noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, 

222 
const void *data) { 

223 
if(!sl>compare) return 0; 

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

225 
} 

226 


227 
noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl, 

228 
const void *data, 

229 
noit_skiplist_comparator_t comp) { 

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

231 
int nh=1, ch, stacki; 

232 
if(!sl>top) { 

233 
sl>height = 1; 

234 
sl>topend = sl>bottomend = sl>top = sl>bottom = 

235 
(noit_skiplist_node *)malloc(sizeof(noit_skiplist_node)); 

236 
assert(sl>top); 

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

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

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

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

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

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

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

244 
sl>top>sl = sl; 

245 
} 

246 
if(sl>preheight) { 

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

248 
} else { 

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

250 
} 

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

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

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

254 
sl>top>up = 

255 
(noit_skiplist_node *)malloc(sizeof(noit_skiplist_node)); 

256 
assert(sl>top>up); 

257 
sl>top>up>down = sl>top; 

258 
sl>top = sl>topend = sl>top>up; 

259 
sl>top>prev = sl>top>next = sl>top>nextindex = 

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

261 
sl>top>data = NULL; 

262 
sl>top>sl = sl; 

263 
} 

264 
ch = sl>height; 

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

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

267 
m = sl>top; 

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

269 
stacki=0; 

270 
while(m) { 

271 
int compared=1; 

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

273 
if(compared == 0) { 

274 
free(stack); 

275 
return 0; 

276 
} 

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

278 
if(ch<=nh) { 

279 
/* push on stack */ 

280 
stack[stacki++] = m; 

281 
} 

282 
m = m>down; 

283 
ch; 

284 
} else { 

285 
m = m>next; 

286 
} 

287 
} 

288 
/* Pop the stack and insert nodes */ 

289 
p = NULL; 

290 
for(;stacki>0;stacki) { 

291 
m = stack[stacki1]; 

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

293 
tmp>next = m>next; 

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

295 
tmp>prev = m; 

296 
tmp>up = NULL; 

297 
tmp>nextindex = tmp>previndex = NULL; 

298 
tmp>down = p; 

299 
if(p) p>up=tmp; 

300 
tmp>data = (void *)data; 

301 
tmp>sl = sl; 

302 
m>next = tmp; 

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

304 
if(!p) ret=tmp; 

305 
p = tmp; 

306 
} 

307 
free(stack); 

308 
if(sl>index != NULL) { 

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

310 
noit_skiplist_node *p, *ni, *li; 

311 
li=ret; 

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

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

314 
assert(ni); 

315 
li>nextindex = ni; 

316 
ni>previndex = li; 

317 
li = ni; 

318 
} 

319 
} 

320 
sl>size++; 

321 
return ret; 

322 
} 

323 
int noit_skiplist_remove(noit_skiplist *sl, 

324 
const void *data, noit_freefunc_t myfree) { 

325 
if(!sl>compare) return 0; 

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

327 
} 

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

329 
noit_skiplist_node *p; 

330 
if(!m) return 0; 

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

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

333 
while(m) { 

334 
p=m; 

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

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

337 
m=m>down; 

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

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

340 
free(p); 

341 
} 

342 
sl>size; 

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

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

345 
p = sl>top; 

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

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

348 
free(p); 

349 
sl>height; 

350 
} 

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

352 
return 1; 

353 
} 

354 
int noit_skiplist_remove_compare(noit_skiplist *sli, 

355 
const void *data, 

356 
noit_freefunc_t myfree, 

357 
noit_skiplist_comparator_t comp) { 

358 
noit_skiplist_node *m; 

359 
noit_skiplist *sl; 

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

361 
sl = sli; 

362 
} else { 

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

364 
assert(m); 

365 
sl= (noit_skiplist *) m>data; 

366 
} 

367 
noit_skiplisti_find_compare(sl, data, &m, NULL, NULL, comp); 

368 
if(!m) return 0; 

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

370 
return noit_skiplisti_remove(sl, m, myfree); 

371 
} 

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

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

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

375 
making this call without memory leaks */ 

376 
noit_skiplist_node *m, *p, *u; 

377 
m=sl>bottom; 

378 
while(m) { 

379 
p = m>next; 

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

381 
while(m) { 

382 
u = m>up; 

383 
free(m); 

384 
m=u; 

385 
} 

386 
m = p; 

387 
} 

388 
sl>top = sl>bottom = NULL; 

389 
sl>height = 0; 

390 
sl>size = 0; 

391 
} 

392 


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

394 
{ 

395 
noit_skiplist_node *sln; 

396 
void *data = NULL; 

397 
sln = noit_skiplist_getlist(a); 

398 
if (sln) { 

399 
data = sln>data; 

400 
noit_skiplisti_remove(a, sln, myfree); 

401 
} 

402 
return data; 

403 
} 

404 
void *noit_skiplist_peek(noit_skiplist * a) 

405 
{ 

406 
noit_skiplist_node *sln; 

407 
sln = noit_skiplist_getlist(a); 

408 
if (sln) { 

409 
return sln>data; 

410 
} 

411 
return NULL; 

412 
} 
