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 "noit_defines.h" 

19 
#include "noit_skiplist.h" 

20 


21 
#include <stdio.h> 

22 
#include <stdlib.h> 

23 
#include <string.h> 

24 
#include <assert.h> 

25 
#ifdef HAVE_ALLOCA_H 

26 
#include <alloca.h> 

27 
#endif 

28 


29 
#ifndef MIN 

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

31 
#endif 

32 


33 
static int noit_skiplisti_find_compare(noit_skiplist *sl, const void *data, 

34 
noit_skiplist_node **ret, 

35 
noit_skiplist_node **prev, 

36 
noit_skiplist_node **next, 

37 
noit_skiplist_comparator_t comp); 

38 


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

40 
if(a < b) return 1; 

41 
if(a == b) return 0; 

42 
return 1; 

43 
} 

44 


45 
static int get_b_rand(void) { 

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

47 
static unsigned long randseq; 

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

49 
ph=0; 

50 
randseq = lrand48(); 

51 
} 

52 
ph++; 

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

54 
} 

55 


56 
void noit_skiplisti_init(noit_skiplist *sl) { 

57 
memset(sl, 0, sizeof(*sl)); 

58 
} 

59 


60 
static int indexing_comp(const void *av, const void *bv) { 

61 
const noit_skiplist *a = av; 

62 
const noit_skiplist *b = bv; 

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

64 
} 

65 
static int indexing_compk(const void *a, const void *bv) { 

66 
const noit_skiplist *b = bv; 

67 
return a>(void *)(b>compare); 

68 
} 

69 


70 
void noit_skiplist_init(noit_skiplist *sl) { 

71 
noit_skiplisti_init(sl); 

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

73 
noit_skiplisti_init(sl>index); 

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

75 
} 

76 


77 
void noit_skiplist_set_compare(noit_skiplist *sl, 

78 
noit_skiplist_comparator_t comp, 

79 
noit_skiplist_comparator_t compk) { 

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

81 
noit_skiplist_add_index(sl, comp, compk); 

82 
} else { 

83 
sl>compare = comp; 

84 
sl>comparek = compk; 

85 
} 

86 
} 

87 


88 
void noit_skiplist_add_index(noit_skiplist *sl, 

89 
noit_skiplist_comparator_t comp, 

90 
noit_skiplist_comparator_t compk) { 

91 
noit_skiplist_node *m; 

92 
noit_skiplist *ni; 

93 
int icount=0; 

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

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

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

97 
noit_skiplisti_init(ni); 

98 
noit_skiplist_set_compare(ni, comp, compk); 

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

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

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

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

103 
int j=icount1; 

104 
noit_skiplist_node *nsln; 

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

106 
/* skip from main index down list */ 

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

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

109 
nsln>nextindex = m>nextindex; 

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

111 
nsln>previndex = m; 

112 
m>nextindex = nsln; 

113 
} 

114 
} 

115 


116 
noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl) { 

117 
if(!sl>bottom) return NULL; 

118 
return sl>bottom>next; 

119 
} 

120 


121 
void *noit_skiplist_find(noit_skiplist *sl, 

122 
const void *data, 

123 
noit_skiplist_node **iter) { 

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

125 
} 

126 
void *noit_skiplist_find_neighbors(noit_skiplist *sl, 

127 
const void *data, 

128 
noit_skiplist_node **iter, 

129 
noit_skiplist_node **prev, 

130 
noit_skiplist_node **next) { 

131 
void *ret; 

132 
noit_skiplist_node *aiter; 

133 
if(!sl>compare) return 0; 

134 
if(iter) 

135 
ret = noit_skiplist_find_neighbors_compare(sl, data, iter, 

136 
prev, next, sl>compare); 

137 
else 

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

139 
prev, next, sl>compare); 

140 
return ret; 

141 
} 

142 


143 
void *noit_skiplist_find_compare(noit_skiplist *sli, 

144 
const void *data, 

145 
noit_skiplist_node **iter, 

146 
noit_skiplist_comparator_t comp) { 

147 
return noit_skiplist_find_neighbors_compare(sli, data, iter, 

148 
NULL, NULL, comp); 

149 
} 

150 
void *noit_skiplist_find_neighbors_compare(noit_skiplist *sli, 

151 
const void *data, 

152 
noit_skiplist_node **iter, 

153 
noit_skiplist_node **prev, 

154 
noit_skiplist_node **next, 

155 
noit_skiplist_comparator_t comp) { 

156 
noit_skiplist_node *m = NULL; 

157 
noit_skiplist *sl; 

158 
if(iter) *iter = NULL; 

159 
if(prev) *prev = NULL; 

160 
if(next) *next = NULL; 

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

162 
sl = sli; 

163 
} else { 

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

165 
assert(m); 

166 
sl= (noit_skiplist *) m>data; 

167 
} 

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

169 
return (iter && *iter)?((*iter)>data):NULL; 

170 
} 

171 
static int noit_skiplisti_find_compare(noit_skiplist *sl, 

172 
const void *data, 

173 
noit_skiplist_node **ret, 

174 
noit_skiplist_node **prev, 

175 
noit_skiplist_node **next, 

176 
noit_skiplist_comparator_t comp) { 

177 
noit_skiplist_node *m = NULL; 

178 
int count=0; 

179 
if(ret) *ret = NULL; 

180 
if(prev) *prev = NULL; 

181 
if(next) *next = NULL; 

182 
m = sl>top; 

183 
while(m) { 

184 
int compared; 

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

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

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

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

189 
if(ret) *ret = m; 

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

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

192 
return count; 

193 
} 

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

195 
if(m>down == NULL) { 

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

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

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

199 
} 

200 
m = m>down; 

201 
count++; 

202 
} 

203 
else 

204 
m = m>next, count++; 

205 
} 

206 
if(ret) *ret = NULL; 

207 
return count; 

208 
} 

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

210 
if(!*iter) return NULL; 

211 
*iter = (*iter)>next; 

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

213 
} 

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

215 
if(!*iter) return NULL; 

216 
*iter = (*iter)>prev; 

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

218 
} 

219 
noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl, 

220 
const void *data) { 

221 
if(!sl>compare) return 0; 

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

223 
} 

224 


225 
noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl, 

226 
const void *data, 

227 
noit_skiplist_comparator_t comp) { 

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

229 
int nh=1, ch, stacki; 

230 
if(!sl>top) { 

231 
sl>height = 1; 

232 
sl>top = sl>bottom = 

233 
calloc(1, sizeof(noit_skiplist_node)); 

234 
sl>top>sl = sl; 

235 
} 

236 
if(sl>preheight) { 

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

238 
} else { 

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

240 
} 

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

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

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

244 
sl>top>up = (noit_skiplist_node *)calloc(1, sizeof(noit_skiplist_node)); 

245 
sl>top>up>down = sl>top; 

246 
sl>top = sl>top>up; 

247 
sl>top>sl = sl; 

248 
} 

249 
ch = sl>height; 

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

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

252 
m = sl>top; 

253 
stack = (noit_skiplist_node **)alloca(sizeof(noit_skiplist_node *)*(nh)); 

254 
stacki=0; 

255 
while(m) { 

256 
int compared=1; 

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

258 
if(compared == 0) { 

259 
return 0; 

260 
} 

261 
if(compared<0) { 

262 
if(ch<=nh) { 

263 
/* push on stack */ 

264 
stack[stacki++] = m; 

265 
} 

266 
m = m>down; 

267 
ch; 

268 
} else { 

269 
m = m>next; 

270 
} 

271 
} 

272 
/* Pop the stack and insert nodes */ 

273 
p = NULL; 

274 
for(;stacki>0;stacki) { 

275 
m = stack[stacki1]; 

276 
tmp = calloc(1, sizeof(*tmp)); 

277 
tmp>next = m>next; 

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

279 
tmp>prev = m; 

280 
tmp>down = p; 

281 
if(p) p>up=tmp; 

282 
tmp>data = (void *)data; 

283 
tmp>sl = sl; 

284 
m>next = tmp; 

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

286 
if(!p) ret=tmp; 

287 
p = tmp; 

288 
} 

289 
if(sl>index != NULL) { 

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

291 
noit_skiplist_node *p, *ni, *li; 

292 
assert(ret); 

293 
li=ret; 

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

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

296 
assert(ni); 

297 
li>nextindex = ni; 

298 
ni>previndex = li; 

299 
li = ni; 

300 
} 

301 
} 

302 
sl>size++; 

303 
return ret; 

304 
} 

305 
int noit_skiplist_remove(noit_skiplist *sl, 

306 
const void *data, noit_freefunc_t myfree) { 

307 
if(!sl>compare) return 0; 

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

309 
} 

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

311 
noit_skiplist_node *p; 

312 
if(!m) return 0; 

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

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

315 
while(m) { 

316 
p=m; 

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

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

319 
m=m>down; 

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

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

322 
free(p); 

323 
} 

324 
sl>size; 

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

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

327 
p = sl>top; 

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

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

330 
free(p); 

331 
sl>height; 

332 
} 

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

334 
return 1; 

335 
} 

336 
int noit_skiplist_remove_compare(noit_skiplist *sli, 

337 
const void *data, 

338 
noit_freefunc_t myfree, 

339 
noit_skiplist_comparator_t comp) { 

340 
noit_skiplist_node *m; 

341 
noit_skiplist *sl; 

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

343 
sl = sli; 

344 
} else { 

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

346 
assert(m); 

347 
sl= (noit_skiplist *) m>data; 

348 
} 

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

350 
if(!m) return 0; 

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

352 
return noit_skiplisti_remove(m>sl, m, myfree); 

353 
} 

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

355 
noit_skiplist_node *m, *p, *u; 

356 
m=sl>bottom; 

357 
while(m) { 

358 
p = m>next; 

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

360 
while(m) { 

361 
u = m>up; 

362 
free(m); 

363 
m=u; 

364 
} 

365 
m = p; 

366 
} 

367 
sl>top = sl>bottom = NULL; 

368 
sl>height = 0; 

369 
sl>size = 0; 

370 
} 

371 
static void noit_skiplisti_destroy(void *vsl) { 

372 
noit_skiplist_destroy((noit_skiplist *)vsl, NULL); 

373 
free(vsl); 

374 
} 

375 
void noit_skiplist_destroy(noit_skiplist *sl, noit_freefunc_t myfree) { 

376 
while(noit_skiplist_pop(sl>index, noit_skiplisti_destroy) != NULL); 

377 
noit_skiplist_remove_all(sl, myfree); 

378 
} 

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

380 
{ 

381 
noit_skiplist_node *sln; 

382 
void *data = NULL; 

383 
sln = noit_skiplist_getlist(a); 

384 
if (sln) { 

385 
data = sln>data; 

386 
noit_skiplisti_remove(a, sln, myfree); 

387 
} 

388 
return data; 

389 
} 

390 
void *noit_skiplist_peek(noit_skiplist * a) 

391 
{ 

392 
noit_skiplist_node *sln; 

393 
sln = noit_skiplist_getlist(a); 

394 
if (sln) { 

395 
return sln>data; 

396 
} 

397 
return NULL; 

398 
} 
