1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * Copyright by The HDF Group. *
3 * Copyright by the Board of Trustees of the University of Illinois. *
4 * All rights reserved. *
5 * *
6 * This file is part of HDF5. The full HDF5 copyright notice, including *
7 * terms governing use, modification, and redistribution, is contained in *
8 * the COPYING file, which can be found at the root of the source code *
9 * distribution tree, or in https://support.hdfgroup.org/ftp/HDF5/releases. *
10 * If you do not have access to either file, you may request a copy from *
11 * help@hdfgroup.org. *
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 /*
15 * Purpose: Provides a skip list abstract data type.
16 *
17 * (See "Deterministic Skip Lists" by Munro, Papadakis & Sedgewick)
18 *
19 * (Implementation changed to a deterministic skip list from a
20 * probabilistic one. This implementation uses a 1-2-3 skip list
21 * using arrays, as described by Munro, Papadakis & Sedgewick.
22 *
23 * Arrays are allocated using a free list factory for each size
24 * that is a power of two. Factories are created as soon as they
25 * are needed, and are never destroyed until the package is shut
26 * down. There is no longer a maximum level or "p" value.
27 * -NAF 2008/11/05)
28 *
29 * (See "Skip Lists: A Probabilistic Alternative to Balanced Trees"
30 * by William Pugh for additional information)
31 *
32 * (This implementation has the optimization for reducing key
33 * key comparisons mentioned in section 3.5 of "A Skip List
34 * Cookbook" by William Pugh
35 * -Removed as our implementation of this was useless for a 1-2-3
36 * skip list. The implementation in that document hurts
37 * performance, at least for integer keys. -NAF)
38 *
39 * (Also, this implementation has a couple of home-grown
40 * optimizations, including setting the "update" vector to the
41 * actual 'forward' pointer to update, instead of the node
42 * containing the forward pointer -QAK
43 * -No longer uses update vector, as insertions/deletions are now
44 * always at level 0. -NAF)
45 *
46 * (Note: This implementation does not have the information for
47 * implementing the "Linear List Operations" (like insert/delete/
48 * search by position) in section 3.4 of "A Skip List Cookbook",
49 * but they shouldn't be that hard to add, if necessary)
50 *
51 * (This implementation has an additional backward pointer, which
52 * allows the list to be iterated in reverse)
53 *
54 * (There's also an article on "Alternating Skip Lists", which
55 * are similar to deterministic skip lists, in the August 2000
56 * issue of Dr. Dobb's Journal)
57 *
58 */
59
60 #include "H5SLmodule.h" /* This source code file is part of the H5SL module */
61
62
63 /* Private headers needed */
64 #include "H5private.h" /* Generic Functions */
65 #include "H5Eprivate.h" /* Error handling */
66 #include "H5FLprivate.h" /* Free Lists */
67 #include "H5MMprivate.h" /* Memory management */
68 #include "H5SLprivate.h" /* Skip list routines */
69
70 /* Local Macros */
71
72 /* Define the code template for searches for the "OP" in the H5SL_LOCATE macro */
73 #define H5SL_LOCATE_SEARCH_FOUND(SLIST, X, I) \
74 { \
75 HDassert(!X->removed); \
76 HGOTO_DONE(X->item); \
77 } /* end block */
78
79 /* Define the code template for deferred removals for the "OP" in the
80 * H5SL_LOCATE macro */
81 #define H5SL_LOCATE_SEARCH_DEFER_REMOVE_FOUND(SLIST, X, I) \
82 { \
83 HDassert(!X->removed); \
84 X->removed = TRUE; \
85 HGOTO_DONE(X->item); \
86 } /* end block */
87
88 /* Define the code template for finds for the "OP" in the H5SL_LOCATE macro */
89 #define H5SL_LOCATE_FIND_FOUND(SLIST, X, I) \
90 { \
91 HDassert(!X->removed); \
92 HGOTO_DONE(X); \
93 } /* end block */
94
95
96 /* Define a code template for comparing scalar keys for the "CMP" in the H5SL_LOCATE macro */
97 #define H5SL_LOCATE_SCALAR_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
98 (*(TYPE *)((PNODE)->key) < *(TYPE *)PKEY)
99
100 /* Define a code template for comparing string keys for the "CMP" in the H5SL_LOCATE macro */
101 #define H5SL_LOCATE_STRING_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
102 (((PNODE)->hashval == HASHVAL) ? \
103 (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) < 0) : \
104 ((PNODE)->hashval < HASHVAL))
105
106 /* Define a code template for comparing H5_obj_t keys for the "CMP" in the H5SL_LOCATE macro */
107 #define H5SL_LOCATE_OBJ_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
108 ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) \
109 ? (((TYPE *)((PNODE)->key))->addr < ((TYPE *)PKEY)->addr) \
110 : (((TYPE *)((PNODE)->key))->fileno < ((TYPE *)PKEY)->fileno))
111
112 /* Define a code template for comparing generic keys for the "CMP" in the H5SL_LOCATE macro */
113 #define H5SL_LOCATE_GENERIC_CMP(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
114 ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) < 0)
115
116
117 /* Define a code template for comparing scalar keys for the "EQ" in the H5SL_LOCATE macro */
118 #define H5SL_LOCATE_SCALAR_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
119 (*(TYPE *)((PNODE)->key) == *(TYPE *)PKEY)
120
121 /* Define a code template for comparing string keys for the "EQ" in the H5SL_LOCATE macro */
122 #define H5SL_LOCATE_STRING_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
123 (((PNODE)->hashval == HASHVAL) && (HDstrcmp((const char *)(PNODE)->key, (const char *)PKEY) == 0))
124
125 /* Define a code template for comparing H5_obj_t keys for the "EQ" in the H5SL_LOCATE macro */
126 #define H5SL_LOCATE_OBJ_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
127 ((((TYPE *)((PNODE)->key))->fileno == ((TYPE *)PKEY)->fileno) && (((TYPE *)((PNODE)->key))->addr == ((TYPE *)PKEY)->addr))
128
129 /* Define a code template for comparing generic keys for the "EQ" in the H5SL_LOCATE macro */
130 #define H5SL_LOCATE_GENERIC_EQ(SLIST, TYPE, PNODE, PKEY, HASHVAL) \
131 ((SLIST)->cmp((TYPE *)((PNODE)->key), (TYPE *)PKEY) == 0)
132
133
134 /* Define a code template for initializing the hash value for scalar keys for the "HASHINIT" in the H5SL_LOCATE macro */
135 #define H5SL_LOCATE_SCALAR_HASHINIT(KEY, HASHVAL)
136
137 /* Define a code template for initializing the hash value for string keys for the "HASHINIT" in the H5SL_LOCATE macro */
138 #define H5SL_LOCATE_STRING_HASHINIT(KEY, HASHVAL) \
139 HASHVAL = H5_hash_string((const char *)KEY);
140
141 /* Define a code template for initializing the hash value for H5_obj_t keys for the "HASHINIT" in the H5SL_LOCATE macro */
142 #define H5SL_LOCATE_OBJ_HASHINIT(KEY, HASHVAL)
143
144 /* Define a code template for initializing the hash value for generic keys for the "HASHINIT" in the H5SL_LOCATE macro */
145 #define H5SL_LOCATE_GENERIC_HASHINIT(KEY, HASHVAL)
146
147
148 /* Macro used to find node for operation, if all keys are valid */
149 #define H5SL_LOCATE_OPT(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
150 { \
151 int _i; /* Local index variable */ \
152 unsigned _count; /* Num nodes searched at this height */ \
153 \
154 H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
155 for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \
156 _count = 0; \
157 while(_count < 3 && X->forward[_i] && \
158 H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL) ) { \
159 X = X->forward[_i]; \
160 _count++; \
161 } /* end while */ \
162 } /* end for */ \
163 X = X->forward[0]; \
164 if(X != NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, X, KEY, HASHVAL) ) { \
165 /* What to do when a node is found */ \
166 H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST, X, _i) \
167 } /* end if */ \
168 }
169
170 /* Macro used to find node for operation, if there may be "removed" nodes in the
171 * list (whose keys cannot be read) */
172 #define H5SL_LOCATE_SAFE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
173 { \
174 int _i; /* Local index variable */ \
175 H5SL_node_t *_low = X; \
176 H5SL_node_t *_high = NULL; \
177 \
178 H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
179 for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \
180 X = _low->forward[_i]; \
181 while(X != _high) { \
182 if(!X->removed) { \
183 if(H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X, KEY, HASHVAL)) \
184 _low = X; \
185 else \
186 break; \
187 } /* end if */ \
188 X = X->forward[_i]; \
189 } /* end while */ \
190 _high = X; \
191 if(X != NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, X, KEY, HASHVAL) ) { \
192 /* What to do when a node is found */ \
193 H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST, X, _i) \
194 break; \
195 } /* end if */ \
196 } /* end for */ \
197 }
198
199 /* Macro used to find node for operation */
200 #define H5SL_LOCATE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
201 { \
202 if((SLIST)->safe_iterating) \
203 H5SL_LOCATE_SAFE(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
204 else \
205 H5SL_LOCATE_OPT(OP, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
206 }
207
208
209 /* Macro used to grow a node by 1. Does not update pointers. LVL is the current
210 * level of X. Does not update LVL but does update X->lvl. */
211 #define H5SL_GROW(X, LVL, ERR) \
212 { \
213 /* Check if we need to increase allocation of forward pointers */ \
214 if(LVL + 1 >= 1u << X->log_nalloc) { \
215 H5SL_node_t **_tmp; \
216 HDassert(LVL + 1 == 1u << X->log_nalloc); \
217 /* Double the amount of allocated space */ \
218 X->log_nalloc++; \
219 \
220 /* Check if we need to create a new factory */ \
221 if(X->log_nalloc >= H5SL_fac_nused_g) { \
222 HDassert(X->log_nalloc == H5SL_fac_nused_g); \
223 \
224 /* Check if we need to allocate space for the factory pointer*/ \
225 if(H5SL_fac_nused_g >= H5SL_fac_nalloc_g) { \
226 HDassert(H5SL_fac_nused_g == H5SL_fac_nalloc_g); \
227 /* Double the size of the array of factory pointers */ \
228 H5SL_fac_nalloc_g *= 2; \
229 if(NULL == (H5SL_fac_g = (H5FL_fac_head_t **)H5MM_realloc( \
230 (void *)H5SL_fac_g, H5SL_fac_nalloc_g \
231 * sizeof(H5FL_fac_head_t *)))) \
232 HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, ERR, "memory allocation failed") \
233 } /* end if */ \
234 \
235 /* Create the new factory */ \
236 H5SL_fac_g[H5SL_fac_nused_g] = H5FL_fac_init((1u << H5SL_fac_nused_g) * sizeof(H5SL_node_t *)); \
237 H5SL_fac_nused_g++; \
238 } /* end if */ \
239 \
240 /* Allocate space for new forward pointers */ \
241 if(NULL == (_tmp = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[X->log_nalloc]))) \
242 HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, ERR, "memory allocation failed") \
243 HDmemcpy((void *)_tmp, (const void *)X->forward, (LVL + 1) * sizeof(H5SL_node_t *)); \
244 X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[X->log_nalloc-1], (void *)X->forward); \
245 X->forward = _tmp; \
246 } /* end if */ \
247 \
248 X->level++; \
249 }
250
251
252 /* Macro used to shrink a node by 1. Does not update pointers. LVL is the
253 * current level of X. Does not update LVL but does update X->level. */
254 #define H5SL_SHRINK(X, LVL) \
255 { \
256 /* Check if we can reduce the allocation of forward pointers */ \
257 if(LVL <= 1u << (X->log_nalloc - 1)) { \
258 H5SL_node_t **_tmp; \
259 HDassert(LVL == 1u << (X->log_nalloc - 1)); \
260 X->log_nalloc--; \
261 \
262 /* Allocate space for new forward pointers */ \
263 if(NULL == (_tmp = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[X->log_nalloc]))) \
264 HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed") \
265 HDmemcpy((void *)_tmp, (const void *)X->forward, (LVL) * sizeof(H5SL_node_t *)); \
266 X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[X->log_nalloc+1], (void *)X->forward); \
267 X->forward = _tmp; \
268 } /* end if */ \
269 \
270 X->level--; \
271 }
272
273
274 /* Macro used to grow the level of a node by 1, with appropriate changes to the
275 * head node if necessary. PREV is the previous node of the height that X is to
276 * grow to. */
277 #define H5SL_PROMOTE(SLIST, X, PREV, ERR) \
278 { \
279 size_t _lvl = X->level; \
280 \
281 H5SL_GROW(X, _lvl, ERR); \
282 \
283 if(_lvl == (size_t) SLIST->curr_level) { \
284 HDassert(PREV == SLIST->header); \
285 /* Grow the head */ \
286 H5SL_GROW(PREV, _lvl, ERR) \
287 SLIST->curr_level++; \
288 X->forward[_lvl+1] = NULL; \
289 } else { \
290 HDassert(_lvl < (size_t) SLIST->curr_level); \
291 X->forward[_lvl+1] = PREV->forward[_lvl+1]; \
292 } /* end else */ \
293 PREV->forward[_lvl+1] = X; \
294 }
295
296
297 /* Macro used to reduce the level of a node by 1. Does not update the head node
298 * "current level". PREV is the previous node of the currrent height of X. */
299 #define H5SL_DEMOTE(X, PREV) \
300 { \
301 size_t _lvl = X->level; \
302 \
303 HDassert(PREV->forward[_lvl] == X); \
304 PREV->forward[_lvl] = X->forward[_lvl]; \
305 H5SL_SHRINK(X, _lvl); \
306 }
307
308
309 /* Macro used to insert node. Does not actually insert the node. After running
310 * this macro, X will contain the node before where the new node should be
311 * inserted (at level 0). */
312 #define H5SL_INSERT(CMP, SLIST, X, TYPE, KEY, HASHVAL) \
313 { \
314 H5SL_node_t *_last = X; /* Lowest node in the current gap */ \
315 H5SL_node_t *_next = NULL; /* Highest node in the currect gap */ \
316 H5SL_node_t *_drop; /* Low node of the gap to drop into */ \
317 int _count; /* Number of nodes in the current gap */ \
318 int _i; \
319 \
320 H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
321 for(_i = (int)SLIST->curr_level; _i >= 0; _i--) { \
322 /* Search for the node to drop into, also count the number of nodes */ \
323 /* of height _i in this gap */ \
324 _drop = NULL; \
325 for(_count = 0; ; _count++) { \
326 /* Terminate if this is the last node in the gap */ \
327 if(X->forward[_i] == _next) { \
328 if(!_drop) \
329 _drop = X; \
330 break; \
331 } /* end if */ \
332 \
333 /* Check if this node is the start of the next gap */ \
334 if(!_drop && !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) \
335 _drop = X; \
336 \
337 /* No need to check the last node in the gap if there are 3, as */ \
338 /* there cannot be a fourth */ \
339 if(_count == 2) { \
340 if(!_drop) \
341 _drop = X->forward[_i]; \
342 _count = 3; \
343 break; \
344 } \
345 X = X->forward[_i]; \
346 } /* end for */ \
347 HDassert(!_drop->forward[_i] || \
348 !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \
349 \
350 /* Promote the middle node if necessary */ \
351 if(_count == 3) { \
352 HDassert(X == _last->forward[_i]->forward[_i]); \
353 H5SL_PROMOTE(SLIST, X, _last, NULL) \
354 } \
355 \
356 /* Prepare to drop down */ \
357 X = _last = _drop; \
358 _next = _drop->forward[_i]; \
359 } /* end for */ \
360 \
361 if(_next && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) \
362 HGOTO_ERROR(H5E_SLIST, H5E_CANTINSERT, NULL, "can't insert duplicate key") \
363 }
364
365
366 /* Macro used to remove node */
367 #define H5SL_REMOVE(CMP, SLIST, X, TYPE, KEY, HASHVAL) \
368 { \
369 /* Check for deferred removal */ \
370 if(SLIST->safe_iterating) \
371 H5SL_LOCATE(SEARCH_DEFER_REMOVE, CMP, SLIST, X, TYPE, KEY, HASHVAL) \
372 else { \
373 H5SL_node_t *_last = X; /* Lowest node in the current gap */ \
374 H5SL_node_t *_llast = X; /* Lowest node in the previous gap */ \
375 H5SL_node_t *_next = NULL; /* Highest node in the currect gap */ \
376 H5SL_node_t *_drop = NULL; /* Low node of the gap to drop into */ \
377 H5SL_node_t *_ldrop = NULL; /* Low node of gap before the one to drop into */ \
378 H5SL_node_t *_head = SLIST->header; /* Head of the skip list */ \
379 int _count; /* Number of nodes in the current gap */ \
380 int _i = (int)SLIST->curr_level; \
381 \
382 if(_i < 0) \
383 HGOTO_DONE(NULL); \
384 \
385 H5_GLUE3(H5SL_LOCATE_,CMP,_HASHINIT)(KEY, HASHVAL) \
386 \
387 /* Find the gap to drop in to at the highest level */ \
388 while(X && (!X->key || H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X, KEY, HASHVAL))) { \
389 _llast = _last; \
390 _last = X; \
391 X = X->forward[_i]; \
392 } \
393 _next = X; \
394 \
395 /* Main loop */ \
396 for(_i--; _i >= 0; _i--) { \
397 /* Search for the node to drop into, also count the number of */ \
398 /* nodes of height _i in this gap and keep track of of the node */ \
399 /* before the one to drop into (_ldrop will become _llast, */ \
400 /* _drop will become _last). */ \
401 X = _ldrop = _last; \
402 _drop = NULL; \
403 for(_count = 0; ; _count++) { \
404 /* Terminate if this is the last node in the gap */ \
405 if(X->forward[_i] == _next) { \
406 if(!_drop) \
407 _drop = X; \
408 break; \
409 } /* end if */ \
410 \
411 /* If we have already found the node to drop into and there */ \
412 /* is more than one node in this gap, we can stop searching */ \
413 if(_drop) { \
414 HDassert(_count >= 1); \
415 _count = 2; \
416 break; \
417 } else { /* !_drop */ \
418 /* Check if this node is the start of the next gap */ \
419 if (!H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, X->forward[_i], KEY, HASHVAL)) { \
420 _drop = X; \
421 /* Again check if we can stop searching */ \
422 if(_count) { \
423 _count = 2; \
424 break; \
425 } /* end if */ \
426 } /* end if */ \
427 else \
428 _ldrop = X; \
429 } /* end else */ \
430 \
431 /* No need to check the last node in the gap if there are */ \
432 /* 3, as there cannot be a fourth */ \
433 if(_count == 2) { \
434 if(!_drop) \
435 _drop = X->forward[_i]; \
436 break; \
437 } /* end if */ \
438 X = X->forward[_i]; \
439 } /* end for */ \
440 HDassert(_count >= 1 && _count <= 3); \
441 HDassert(!_drop->forward[_i] || \
442 !H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(SLIST, TYPE, _drop->forward[_i], KEY, HASHVAL)); \
443 \
444 /* Check if we need to adjust node heights */ \
445 if(_count == 1) { \
446 /* Check if we are in the first gap */ \
447 if(_llast == _last) { \
448 /* We are in the first gap, count the number of nodes */ \
449 /* of height _i in the next gap. We need only check */ \
450 /* onenode to see if we should promote the first node */ \
451 /* in the next gap */ \
452 _llast = _next->forward[_i+1]; \
453 \
454 /* Demote the separator node */ \
455 H5SL_DEMOTE(_next, _last) \
456 \
457 /* If there are 2 or more nodes, promote the first */ \
458 if(_next->forward[_i]->forward[_i] != _llast) { \
459 X = _next->forward[_i]; \
460 H5SL_PROMOTE(SLIST, X, _last, NULL) \
461 } else if(!_head->forward[_i+1]) { \
462 /* shrink the header */ \
463 HDassert(_i == SLIST->curr_level - 1); \
464 HDassert((size_t) SLIST->curr_level == _head->level); \
465 \
466 H5SL_SHRINK(_head, (size_t) (_i+1)) \
467 SLIST->curr_level--; \
468 } /* end else */ \
469 } else { \
470 /* We are not in the first gap, count the number of */ \
471 /* nodes of height _i in the previous gap. Note we */ \
472 /* "look ahead" in this loop so X has the value of the */ \
473 /* last node in the previous gap. */ \
474 X = _llast->forward[_i]; \
475 for(_count = 1; _count < 3 && X->forward[_i] != _last; _count++) \
476 X = X->forward[_i]; \
477 HDassert(X->forward[_i] == _last); \
478 \
479 /* Demote the separator node */ \
480 H5SL_DEMOTE(_last, _llast) \
481 \
482 /* If there are 2 or more nodes, promote the last */ \
483 if(_count >= 2) \
484 H5SL_PROMOTE(SLIST, X, _llast, NULL) \
485 else if(!_head->forward[_i+1]) { \
486 /* shrink the header */ \
487 HDassert(_i == SLIST->curr_level - 1); \
488 HDassert((size_t) SLIST->curr_level == _head->level); \
489 \
490 H5SL_SHRINK(_head, (size_t) (_i+1)) \
491 SLIST->curr_level--; \
492 } /* end else */ \
493 } /* end else */ \
494 } /* end if */ \
495 \
496 /* Prepare to drop down */ \
497 _llast = _ldrop; \
498 _last = _drop; \
499 _next = _drop->forward[_i]; \
500 } /* end for */ \
501 \
502 /* Check if we've found the node */ \
503 if(_next && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(SLIST, TYPE, _next, KEY, HASHVAL)) { \
504 void *tmp = _next->item; \
505 X = _next; \
506 \
507 /* If the node has a height > 0, swap it with its (lower) */ \
508 /* neighbor */ \
509 if(X->level) { \
510 X = X->backward; \
511 _next->key = X->key; \
512 _next->item = X->item; \
513 _next->hashval = X->hashval; \
514 } /* end if */ \
515 HDassert(!X->level); \
516 \
517 /* Remove the node */ \
518 X->backward->forward[0] = X->forward[0]; \
519 if(SLIST->last == X) \
520 SLIST->last = X->backward; \
521 else \
522 X->forward[0]->backward = X->backward; \
523 SLIST->nobjs--; \
524 X->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[0], X->forward); \
525 X = H5FL_FREE(H5SL_node_t, X); \
526 \
527 HGOTO_DONE(tmp); \
528 } /* end if */ \
529 } /* end else */ \
530 }
531
532
533 /* Macro used to search for node */
534 #define H5SL_SEARCH(CMP, SLIST, X, TYPE, KEY, HASHVAL) \
535 H5SL_LOCATE(SEARCH, CMP, SLIST, X, TYPE, KEY, HASHVAL)
536
537 /* Macro used to find a node */
538 #define H5SL_FIND(CMP, SLIST, X, TYPE, KEY, HASHVAL) \
539 H5SL_LOCATE(FIND, CMP, SLIST, X, TYPE, KEY, HASHVAL)
540
541
542 /* Private typedefs & structs */
543
544 /* Skip list node data structure */
545 struct H5SL_node_t {
546 const void *key; /* Pointer to node's key */
547 void *item; /* Pointer to node's item */
548 size_t level; /* The level of this node */
549 size_t log_nalloc; /* log2(Number of slots allocated in forward) */
550 uint32_t hashval; /* Hash value for key (only for strings, currently) */
551 hbool_t removed; /* Whether the node is "removed" (actual removal deferred) */
552 struct H5SL_node_t **forward; /* Array of forward pointers from this node */
553 struct H5SL_node_t *backward; /* Backward pointer from this node */
554 };
555
556 /* Main skip list data structure */
557 struct H5SL_t {
558 /* Static values for each list */
559 H5SL_type_t type; /* Type of skip list */
560 H5SL_cmp_t cmp; /* Comparison callback, if type is H5SL_TYPE_GENERIC */
561
562 /* Dynamic values for each list */
563 int curr_level; /* Current top level used in list */
564 size_t nobjs; /* Number of active objects in skip list */
565 H5SL_node_t *header; /* Header for nodes in skip list */
566 H5SL_node_t *last; /* Pointer to last node in skip list */
567 hbool_t safe_iterating; /* Whether a routine is "safely" iterating over the list and removals should be deferred */
568 };
569
570 /* Static functions */
571 static H5SL_node_t * H5SL_new_node(void *item, const void *key, uint32_t hashval);
572 static H5SL_node_t *H5SL_insert_common(H5SL_t *slist, void *item, const void *key);
573 static herr_t H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data);
574 static herr_t H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data);
575
576 /* Package initialization variable */
577 hbool_t H5_PKG_INIT_VAR = FALSE;
578
579 /* Declare a free list to manage the H5SL_t struct */
580 H5FL_DEFINE_STATIC(H5SL_t);
581
582 /* Declare a free list to manage the H5SL_node_t struct */
583 H5FL_DEFINE_STATIC(H5SL_node_t);
584
585 /* Global variables */
586 static H5FL_fac_head_t **H5SL_fac_g;
587 static size_t H5SL_fac_nused_g;
588 static size_t H5SL_fac_nalloc_g;
589
590
591 /*--------------------------------------------------------------------------
592 NAME
593 H5SL__init_package
594 PURPOSE
595 Initialize interface-specific information
596 USAGE
597 herr_t H5SL__init_package()
598 RETURNS
599 Non-negative on success/Negative on failure
600 DESCRIPTION
601 Initializes any interface-specific data or routines.
602 GLOBAL VARIABLES
603 COMMENTS, BUGS, ASSUMPTIONS
604 EXAMPLES
605 REVISION LOG
606 --------------------------------------------------------------------------*/
607 herr_t
H5SL__init_package(void)608 H5SL__init_package(void)
609 {
610 FUNC_ENTER_PACKAGE_NOERR
611
612 /* Allocate space for array of factories */
613 H5SL_fac_g = (H5FL_fac_head_t **)H5MM_malloc(sizeof(H5FL_fac_head_t *));
614 HDassert(H5SL_fac_g);
615 H5SL_fac_nalloc_g = 1;
616
617 /* Initialize first factory */
618 H5SL_fac_g[0] = H5FL_fac_init(sizeof(H5SL_node_t *));
619 HDassert(H5SL_fac_g[0]);
620 H5SL_fac_nused_g = 1;
621
622 FUNC_LEAVE_NOAPI(SUCCEED)
623 } /* end H5SL__init_package() */
624
625
626 /*--------------------------------------------------------------------------
627 NAME
628 H5SL_term_package
629 PURPOSE
630 Terminate all the H5FL factories used in this package, and clear memory
631 USAGE
632 int H5SL_term_package()
633 RETURNS
634 Success: Positive if any action might have caused a change in some
635 other interface; zero otherwise.
636 Failure: Negative
637 DESCRIPTION
638 Release any resources allocated.
639 GLOBAL VARIABLES
640 COMMENTS, BUGS, ASSUMPTIONS
641 Can't report errors...
642 EXAMPLES
643 REVISION LOG
644 --------------------------------------------------------------------------*/
H5SL_term_package(void)645 int H5SL_term_package(void)
646 {
647 int n = 0;
648
649 FUNC_ENTER_NOAPI_NOINIT_NOERR
650
651 if(H5_PKG_INIT_VAR) {
652 /* Terminate all the factories */
653 if(H5SL_fac_nused_g > 0) {
654 size_t i;
655 herr_t ret;
656
657 for(i = 0; i < H5SL_fac_nused_g; i++) {
658 ret = H5FL_fac_term(H5SL_fac_g[i]);
659 HDassert(ret >= 0);
660 } /* end if */
661 H5SL_fac_nused_g = 0;
662
663 n++;
664 } /* end if */
665
666 /* Free the list of factories */
667 if(H5SL_fac_g) {
668 H5SL_fac_g = (H5FL_fac_head_t **)H5MM_xfree((void *)H5SL_fac_g);
669 H5SL_fac_nalloc_g = 0;
670
671 n++;
672 } /* end if */
673
674 /* Mark the interface as uninitialized */
675 if(0 == n)
676 H5_PKG_INIT_VAR = FALSE;
677 } /* end if */
678
679 FUNC_LEAVE_NOAPI(n)
680 } /* H5SL_term_package() */
681
682
683 /*--------------------------------------------------------------------------
684 NAME
685 H5SL_new_node
686 PURPOSE
687 Create a new skip list node of level 0
688 USAGE
689 H5SL_node_t *H5SL_new_node(item,key,hasval)
690 void *item; IN: Pointer to item info for node
691 void *key; IN: Pointer to key info for node
692 uint32_t hashval; IN: Hash value for node
693
694 RETURNS
695 Returns a pointer to a skip list node on success, NULL on failure.
696 DESCRIPTION
697 Create a new skip list node of the height 0, setting the item
698 and key values internally.
699 GLOBAL VARIABLES
700 COMMENTS, BUGS, ASSUMPTIONS
701 This routine does _not_ initialize the 'forward' pointers
702 EXAMPLES
703 REVISION LOG
704 --------------------------------------------------------------------------*/
705 static H5SL_node_t *
H5SL_new_node(void * item,const void * key,uint32_t hashval)706 H5SL_new_node(void *item, const void *key, uint32_t hashval)
707 {
708 H5SL_node_t *ret_value = NULL; /* New skip list node */
709
710 FUNC_ENTER_NOAPI_NOINIT
711
712 /* Allocate the node */
713 if(NULL == (ret_value = (H5SL_node_t *)H5FL_MALLOC(H5SL_node_t)))
714 HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed")
715
716 /* Initialize node */
717 ret_value->key = key;
718 ret_value->item = item;
719 ret_value->level = 0;
720 ret_value->hashval = hashval;
721 ret_value->removed = FALSE;
722 if(NULL == (ret_value->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0]))) {
723 ret_value = H5FL_FREE(H5SL_node_t, ret_value);
724 HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed")
725 } /* end if */
726 ret_value->log_nalloc = 0;
727
728 done:
729 FUNC_LEAVE_NOAPI(ret_value)
730 } /* end H5SL_new_node() */
731
732
733 /*--------------------------------------------------------------------------
734 NAME
735 H5SL_insert_common
736 PURPOSE
737 Common code for inserting an object into a skip list
738 USAGE
739 H5SL_node_t *H5SL_insert_common(slist,item,key)
740 H5SL_t *slist; IN/OUT: Pointer to skip list
741 void *item; IN: Item to insert
742 void *key; IN: Key for item to insert
743
744 RETURNS
745 Returns pointer to new node on success, NULL on failure.
746 DESCRIPTION
747 Common code for inserting an element into a skip list.
748 GLOBAL VARIABLES
749 COMMENTS, BUGS, ASSUMPTIONS
750 Inserting an item with the same key as an existing object fails.
751 EXAMPLES
752 REVISION LOG
753 --------------------------------------------------------------------------*/
754 static H5SL_node_t *
H5SL_insert_common(H5SL_t * slist,void * item,const void * key)755 H5SL_insert_common(H5SL_t *slist, void *item, const void *key)
756 {
757 H5SL_node_t *x; /* Current node to examine */
758 H5SL_node_t *prev; /* Node before the new node */
759 uint32_t hashval = 0; /* Hash value for key */
760 H5SL_node_t *ret_value; /* Return value */
761
762 FUNC_ENTER_NOAPI_NOINIT
763
764 /* Check args */
765 HDassert(slist);
766 HDassert(key);
767
768 /* Check internal consistency */
769 /* (Pre-condition) */
770
771 /* Insert item into skip list */
772
773 /* Work through the forward pointers for a node, finding the node at each
774 * level that is before the location to insert
775 */
776 prev=slist->header;
777 switch(slist->type) {
778 case H5SL_TYPE_INT:
779 H5SL_INSERT(SCALAR, slist, prev, const int, key, -)
780 break;
781
782 case H5SL_TYPE_HADDR:
783 H5SL_INSERT(SCALAR, slist, prev, const haddr_t, key, -)
784 break;
785
786 case H5SL_TYPE_STR:
787 H5SL_INSERT(STRING, slist, prev, char *, key, hashval)
788 break;
789
790 case H5SL_TYPE_HSIZE:
791 H5SL_INSERT(SCALAR, slist, prev, const hsize_t, key, -)
792 break;
793
794 case H5SL_TYPE_UNSIGNED:
795 H5SL_INSERT(SCALAR, slist, prev, const unsigned, key, -)
796 break;
797
798 case H5SL_TYPE_SIZE:
799 H5SL_INSERT(SCALAR, slist, prev, const size_t, key, -)
800 break;
801
802 case H5SL_TYPE_OBJ:
803 H5SL_INSERT(OBJ, slist, prev, const H5_obj_t, key, -)
804 break;
805
806 case H5SL_TYPE_HID:
807 H5SL_INSERT(SCALAR, slist, prev, const hid_t, key, -)
808 break;
809
810 case H5SL_TYPE_GENERIC:
811 H5SL_INSERT(GENERIC, slist, prev, const void, key, -)
812 break;
813
814 default:
815 HDassert(0 && "Unknown skiplist type!");
816 } /* end switch */
817
818
819 /* 'key' must not have been found in existing list, if we get here */
820
821 if(slist->curr_level < 0)
822 slist->curr_level = 0;
823
824 /* Create new node of level 0 */
825 if(NULL == (x = H5SL_new_node(item, key, hashval)))
826 HGOTO_ERROR(H5E_SLIST ,H5E_NOSPACE, NULL, "can't create new skip list node")
827
828 /* Update the links */
829 x->backward = prev;
830 x->forward[0] = prev->forward[0];
831 prev->forward[0] = x;
832 if(x->forward[0])
833 x->forward[0]->backward = x;
834 else {
835 HDassert(slist->last == prev);
836 slist->last = x;
837 }
838
839 /* Increment the number of nodes in the skip list */
840 slist->nobjs++;
841
842 /* Set return value */
843 ret_value=x;
844
845 done:
846 FUNC_LEAVE_NOAPI(ret_value)
847 } /* end H5SL_insert_common() */
848
849
850 /*--------------------------------------------------------------------------
851 NAME
852 H5SL_release_common
853 PURPOSE
854 Release all nodes from a skip list, optionally calling a 'free' operator
855 USAGE
856 herr_t H5SL_release_common(slist,op,opdata)
857 H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
858 H5SL_operator_t op; IN: Callback function to free item & key
859 void *op_data; IN/OUT: Pointer to application data for callback
860
861 RETURNS
862 Returns non-negative on success, negative on failure.
863 DESCRIPTION
864 Release all the nodes in a skip list. The 'op' routine is called for
865 each node in the list.
866 GLOBAL VARIABLES
867 COMMENTS, BUGS, ASSUMPTIONS
868 The return value from the 'op' routine is ignored.
869
870 The skip list itself is still valid, it just has all its nodes removed.
871 EXAMPLES
872 REVISION LOG
873 --------------------------------------------------------------------------*/
874 static herr_t
H5SL_release_common(H5SL_t * slist,H5SL_operator_t op,void * op_data)875 H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
876 {
877 H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */
878 herr_t ret_value = SUCCEED;
879
880 FUNC_ENTER_NOAPI_NOINIT
881
882 /* Check args */
883 HDassert(slist);
884
885 /* Check internal consistency */
886 /* (Pre-condition) */
887
888 /* Free skip list nodes */
889 node = slist->header->forward[0];
890 while(node) {
891 next_node = node->forward[0];
892
893 /* Call callback, if one is given */
894 if(op)
895 /* Casting away const OK -QAK */
896 (void)(op)(node->item, (void *)node->key, op_data);
897
898 node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], node->forward);
899 node = H5FL_FREE(H5SL_node_t, node);
900 node = next_node;
901 } /* end while */
902
903 /* Reset the header pointers */
904 slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], slist->header->forward);
905 if(NULL == (slist->header->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
906 HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, FAIL, "memory allocation failed")
907 slist->header->forward[0] = NULL;
908 slist->header->log_nalloc = 0;
909 slist->header->level = 0;
910
911 /* Reset the last pointer */
912 slist->last = slist->header;
913
914 /* Reset the dynamic internal fields */
915 slist->curr_level = -1;
916 slist->nobjs = 0;
917
918 done:
919 FUNC_LEAVE_NOAPI(ret_value)
920 } /* end H5SL_release_common() */
921
922
923 /*--------------------------------------------------------------------------
924 NAME
925 H5SL_close_common
926 PURPOSE
927 Close a skip list, deallocating it and potentially freeing all its nodes.
928 USAGE
929 herr_t H5SL_close_common(slist,op,opdata)
930 H5SL_t *slist; IN/OUT: Pointer to skip list to close
931 H5SL_operator_t op; IN: Callback function to free item & key
932 void *op_data; IN/OUT: Pointer to application data for callback
933
934 RETURNS
935 Returns non-negative on success, negative on failure.
936 DESCRIPTION
937 Close a skip list, freeing all internal information. Any objects left in
938 the skip list have the 'op' routine called for each.
939 GLOBAL VARIABLES
940 COMMENTS, BUGS, ASSUMPTIONS
941 If the 'op' routine returns non-zero, only the nodes up to that
942 point in the list are released and the list is still valid.
943 EXAMPLES
944 REVISION LOG
945 --------------------------------------------------------------------------*/
946 static herr_t
H5SL_close_common(H5SL_t * slist,H5SL_operator_t op,void * op_data)947 H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
948 {
949 herr_t ret_value = SUCCEED;
950
951 FUNC_ENTER_NOAPI_NOINIT
952
953 /* Check args */
954 HDassert(slist);
955
956 /* Check internal consistency */
957 /* (Pre-condition) */
958
959 /* Free skip list nodes */
960 if(H5SL_release_common(slist, op, op_data) < 0)
961 HGOTO_ERROR(H5E_SLIST, H5E_CANTFREE, FAIL, "can't release skip list nodes")
962
963 /* Release header node */
964 slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], slist->header->forward);
965 slist->header = H5FL_FREE(H5SL_node_t, slist->header);
966
967 /* Free skip list object */
968 slist = H5FL_FREE(H5SL_t, slist);
969
970 done:
971 FUNC_LEAVE_NOAPI(ret_value)
972 } /* end H5SL_close_common() */
973
974
975 /*--------------------------------------------------------------------------
976 NAME
977 H5SL_create
978 PURPOSE
979 Create a skip list
980 USAGE
981 H5SL_t *H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp)
982
983 RETURNS
984 Returns a pointer to a skip list on success, NULL on failure.
985 DESCRIPTION
986 Create a skip list.
987 GLOBAL VARIABLES
988 COMMENTS, BUGS, ASSUMPTIONS
989 EXAMPLES
990 REVISION LOG
991 --------------------------------------------------------------------------*/
992 H5SL_t *
H5SL_create(H5SL_type_t type,H5SL_cmp_t cmp)993 H5SL_create(H5SL_type_t type, H5SL_cmp_t cmp)
994 {
995 H5SL_t *new_slist = NULL; /* Pointer to new skip list object created */
996 H5SL_node_t *header; /* Pointer to skip list header node */
997 H5SL_t *ret_value = NULL; /* Return value */
998
999 FUNC_ENTER_NOAPI(NULL)
1000
1001 /* Check args */
1002 HDassert(type >= H5SL_TYPE_INT && type <= H5SL_TYPE_GENERIC);
1003
1004 /* Allocate skip list structure */
1005 if(NULL == (new_slist = H5FL_MALLOC(H5SL_t)))
1006 HGOTO_ERROR(H5E_SLIST, H5E_NOSPACE, NULL, "memory allocation failed")
1007
1008 /* Set the static internal fields */
1009 new_slist->type = type;
1010 HDassert((type == H5SL_TYPE_GENERIC) == !!cmp);
1011 new_slist->cmp = cmp;
1012
1013 /* Set the dynamic internal fields */
1014 new_slist->curr_level = -1;
1015 new_slist->nobjs = 0;
1016 new_slist->safe_iterating = FALSE;
1017
1018 /* Allocate the header node */
1019 if(NULL == (header = H5SL_new_node(NULL, NULL, (uint32_t)ULONG_MAX)))
1020 HGOTO_ERROR(H5E_SLIST ,H5E_NOSPACE, NULL, "can't create new skip list node")
1021
1022 /* Initialize header node's forward pointer */
1023 header->forward[0] = NULL;
1024
1025 /* Initialize header node's backward pointer */
1026 header->backward = NULL;
1027
1028 /* Attach the header */
1029 new_slist->header = header;
1030 new_slist->last = header;
1031
1032 /* Set the return value */
1033 ret_value = new_slist;
1034
1035 done:
1036 /* Error cleanup */
1037 if(ret_value == NULL) {
1038 if(new_slist != NULL)
1039 new_slist = H5FL_FREE(H5SL_t, new_slist);
1040 } /* end if */
1041
1042 FUNC_LEAVE_NOAPI(ret_value)
1043 } /* end H5SL_create() */
1044
1045
1046 /*--------------------------------------------------------------------------
1047 NAME
1048 H5SL_count
1049 PURPOSE
1050 Count the number of objects in a skip list
1051 USAGE
1052 size_t H5SL_count(slist)
1053 H5SL_t *slist; IN: Pointer to skip list to count
1054
1055 RETURNS
1056 Returns number of objects on success, can't fail
1057 DESCRIPTION
1058 Count elements in a skip list.
1059 GLOBAL VARIABLES
1060 COMMENTS, BUGS, ASSUMPTIONS
1061 EXAMPLES
1062 REVISION LOG
1063 --------------------------------------------------------------------------*/
1064 size_t
H5SL_count(H5SL_t * slist)1065 H5SL_count(H5SL_t *slist)
1066 {
1067 FUNC_ENTER_NOAPI_NOINIT_NOERR
1068
1069 /* Check args */
1070 HDassert(slist);
1071
1072 /* Not currently supported */
1073 HDassert(!slist->safe_iterating);
1074
1075 /* Check internal consistency */
1076 /* (Pre-condition) */
1077
1078 FUNC_LEAVE_NOAPI(slist->nobjs)
1079 } /* end H5SL_count() */
1080
1081
1082 /*--------------------------------------------------------------------------
1083 NAME
1084 H5SL_insert
1085 PURPOSE
1086 Insert an object into a skip list
1087 USAGE
1088 herr_t H5SL_insert(slist,item,key)
1089 H5SL_t *slist; IN/OUT: Pointer to skip list
1090 void *item; IN: Item to insert
1091 void *key; IN: Key for item to insert
1092
1093 RETURNS
1094 Returns non-negative on success, negative on failure.
1095 DESCRIPTION
1096 Insert element into a skip list.
1097 GLOBAL VARIABLES
1098 COMMENTS, BUGS, ASSUMPTIONS
1099 Inserting an item with the same key as an existing object fails.
1100 EXAMPLES
1101 REVISION LOG
1102 --------------------------------------------------------------------------*/
1103 herr_t
H5SL_insert(H5SL_t * slist,void * item,const void * key)1104 H5SL_insert(H5SL_t *slist, void *item, const void *key)
1105 {
1106 herr_t ret_value=SUCCEED; /* Return value */
1107
1108 FUNC_ENTER_NOAPI_NOINIT
1109
1110 /* Check args */
1111 HDassert(slist);
1112 HDassert(key);
1113
1114 /* Not currently supported */
1115 HDassert(!slist->safe_iterating);
1116
1117 /* Check internal consistency */
1118 /* (Pre-condition) */
1119
1120 /* Insert item into skip list */
1121 if(H5SL_insert_common(slist,item,key)==NULL)
1122 HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,FAIL,"can't create new skip list node")
1123
1124 done:
1125 FUNC_LEAVE_NOAPI(ret_value)
1126 } /* end H5SL_insert() */
1127
1128
1129 /*--------------------------------------------------------------------------
1130 NAME
1131 H5SL_add
1132 PURPOSE
1133 Insert an object into a skip list
1134 USAGE
1135 H5SL_node_t *H5SL_add(slist,item,key)
1136 H5SL_t *slist; IN/OUT: Pointer to skip list
1137 void *item; IN: Item to insert
1138 void *key; IN: Key for item to insert
1139
1140 RETURNS
1141 Returns pointer to new skip list node on success, NULL on failure.
1142 DESCRIPTION
1143 Insert element into a skip list and return the skip list node for the
1144 new element in the list.
1145 GLOBAL VARIABLES
1146 COMMENTS, BUGS, ASSUMPTIONS
1147 Inserting an item with the same key as an existing object fails.
1148
1149 This routine is a useful starting point for next/prev calls
1150 EXAMPLES
1151 REVISION LOG
1152 --------------------------------------------------------------------------*/
1153 H5SL_node_t *
H5SL_add(H5SL_t * slist,void * item,const void * key)1154 H5SL_add(H5SL_t *slist, void *item, const void *key)
1155 {
1156 H5SL_node_t *ret_value = NULL; /* Return value */
1157
1158 FUNC_ENTER_NOAPI_NOINIT
1159
1160 /* Check args */
1161 HDassert(slist);
1162 HDassert(key);
1163
1164 /* Not currently supported */
1165 HDassert(!slist->safe_iterating);
1166
1167 /* Check internal consistency */
1168 /* (Pre-condition) */
1169
1170 /* Insert item into skip list */
1171 if((ret_value=H5SL_insert_common(slist,item,key))==NULL)
1172 HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,NULL,"can't create new skip list node")
1173
1174 done:
1175 FUNC_LEAVE_NOAPI(ret_value)
1176 } /* end H5SL_add() */
1177
1178
1179 /*--------------------------------------------------------------------------
1180 NAME
1181 H5SL_remove
1182 PURPOSE
1183 Removes an object from a skip list
1184 USAGE
1185 void *H5SL_remove(slist,key)
1186 H5SL_t *slist; IN/OUT: Pointer to skip list
1187 void *key; IN: Key for item to remove
1188
1189 RETURNS
1190 Returns pointer to item removed on success, NULL on failure.
1191 DESCRIPTION
1192 Remove element from a skip list.
1193 GLOBAL VARIABLES
1194 COMMENTS, BUGS, ASSUMPTIONS
1195 EXAMPLES
1196 REVISION LOG
1197 --------------------------------------------------------------------------*/
1198 void *
H5SL_remove(H5SL_t * slist,const void * key)1199 H5SL_remove(H5SL_t *slist, const void *key)
1200 {
1201 H5SL_node_t *x; /* Current node to examine */
1202 uint32_t hashval = 0; /* Hash value for key */
1203 void *ret_value = NULL; /* Return value */
1204
1205 FUNC_ENTER_NOAPI_NOINIT
1206
1207 /* Check args */
1208 HDassert(slist);
1209 HDassert(key);
1210
1211 /* Check internal consistency */
1212 /* (Pre-condition) */
1213
1214 /* Remove item from skip list */
1215
1216 /* Work through the forward pointers for a node, finding the node at each
1217 * level that is before the location to remove
1218 */
1219 x = slist->header;
1220 switch(slist->type) {
1221 case H5SL_TYPE_INT:
1222 H5SL_REMOVE(SCALAR, slist, x, const int, key, -)
1223 break;
1224
1225 case H5SL_TYPE_HADDR:
1226 H5SL_REMOVE(SCALAR, slist, x, const haddr_t, key, -)
1227 break;
1228
1229 case H5SL_TYPE_STR:
1230 H5SL_REMOVE(STRING, slist, x, char *, key, hashval)
1231 break;
1232
1233 case H5SL_TYPE_HSIZE:
1234 H5SL_REMOVE(SCALAR, slist, x, const hsize_t, key, -)
1235 break;
1236
1237 case H5SL_TYPE_UNSIGNED:
1238 H5SL_REMOVE(SCALAR, slist, x, const unsigned, key, -)
1239 break;
1240
1241 case H5SL_TYPE_SIZE:
1242 H5SL_REMOVE(SCALAR, slist, x, const size_t, key, -)
1243 break;
1244
1245 case H5SL_TYPE_OBJ:
1246 H5SL_REMOVE(OBJ, slist, x, const H5_obj_t, key, -)
1247 break;
1248
1249 case H5SL_TYPE_HID:
1250 H5SL_REMOVE(SCALAR, slist, x, const hid_t, key, -)
1251 break;
1252
1253 case H5SL_TYPE_GENERIC:
1254 H5SL_REMOVE(GENERIC, slist, x, const void, key, -)
1255 break;
1256
1257 default:
1258 HDassert(0 && "Unknown skiplist type!");
1259 } /* end switch */
1260
1261 done:
1262 FUNC_LEAVE_NOAPI(ret_value)
1263 } /* end H5SL_remove() */
1264
1265
1266 /*--------------------------------------------------------------------------
1267 NAME
1268 H5SL_remove_first
1269 PURPOSE
1270 Removes the first object from a skip list
1271 USAGE
1272 void *H5SL_remove_first(slist)
1273 H5SL_t *slist; IN/OUT: Pointer to skip list
1274
1275 RETURNS
1276 Returns pointer to item removed on success, NULL on failure.
1277 DESCRIPTION
1278 Remove first element from a skip list.
1279 GLOBAL VARIABLES
1280 COMMENTS, BUGS, ASSUMPTIONS
1281 EXAMPLES
1282 REVISION LOG
1283 --------------------------------------------------------------------------*/
1284 void *
H5SL_remove_first(H5SL_t * slist)1285 H5SL_remove_first(H5SL_t *slist)
1286 {
1287 void *ret_value = NULL; /* Return value */
1288 H5SL_node_t *head = slist->header; /* Skip list header */
1289 H5SL_node_t *tmp = slist->header->forward[0]; /* Temporary node pointer */
1290 H5SL_node_t *next; /* Next node to search for */
1291 size_t level; /* Skip list level */
1292 size_t i; /* Index */
1293
1294 FUNC_ENTER_NOAPI_NOINIT
1295
1296 /* Check args */
1297 HDassert(slist);
1298
1299 /* Not currently supported */
1300 HDassert(!slist->safe_iterating);
1301
1302 /* Assign level */
1303 H5_CHECK_OVERFLOW(slist->curr_level, int, size_t);
1304 level = (size_t)slist->curr_level;
1305
1306 /* Check internal consistency */
1307 /* (Pre-condition) */
1308
1309 /* Remove item from skip list */
1310
1311 /* Check for empty list */
1312 if(slist->last != slist->header) {
1313
1314 /* Assign return value */
1315 ret_value = tmp->item;
1316 HDassert(level == head->level);
1317 HDassert(0 == tmp->level);
1318
1319 /* Remove the first node */
1320 head->forward[0] = tmp->forward[0];
1321 if(slist->last == tmp)
1322 slist->last = head;
1323 else
1324 tmp->forward[0]->backward = head;
1325 slist->nobjs--;
1326 /* Free memory */
1327 tmp->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[0], tmp->forward);
1328 tmp = H5FL_FREE(H5SL_node_t, tmp);
1329
1330 /* Reshape the skip list as necessary to maintain 1-2-3 condition */
1331 for(i=0; i < level; i++) {
1332 next = head->forward[i+1];
1333 HDassert(next);
1334
1335 /* Check if head->forward[i] == head->forward[i+1] (illegal) */
1336 if(head->forward[i] == next) {
1337 tmp = next;
1338 next = next->forward[i+1];
1339
1340 HDassert(tmp->level == i+1);
1341
1342 /* Demote head->forward[i] */
1343 H5SL_DEMOTE(tmp, head)
1344
1345 /* Check if we need to promote the following node to maintain
1346 * 1-2-3 condition */
1347 if(tmp->forward[i]->forward[i] != next) {
1348 HDassert(tmp->forward[i]->forward[i]->forward[i] == next ||
1349 tmp->forward[i]->forward[i]->forward[i]->forward[i] == next);
1350 tmp = tmp->forward[i];
1351 H5SL_PROMOTE(slist, tmp, head, NULL);
1352 /* In this case, since there is a node of height = i+1 here
1353 * now (tmp), we know the skip list must be valid and can
1354 * break */
1355 break;
1356 } else if(!head->forward[i+1]) {
1357 /* We just shrunk the largest node, shrink the header */
1358 HDassert(i == level - 1);
1359
1360 H5SL_SHRINK(head, level)
1361 slist->curr_level--;
1362 } /* end else */
1363 } else
1364 break;
1365 } /* end for */
1366 } /* end if */
1367
1368 done:
1369 FUNC_LEAVE_NOAPI(ret_value)
1370 } /* end H5SL_remove_first() */
1371
1372
1373 /*--------------------------------------------------------------------------
1374 NAME
1375 H5SL_search
1376 PURPOSE
1377 Search for object in a skip list
1378 USAGE
1379 void *H5SL_search(slist,key)
1380 H5SL_t *slist; IN/OUT: Pointer to skip list
1381 void *key; IN: Key for item to search for
1382
1383 RETURNS
1384 Returns pointer to item on success, NULL on failure
1385 DESCRIPTION
1386 Search for an object in a skip list, according to it's key
1387 GLOBAL VARIABLES
1388 COMMENTS, BUGS, ASSUMPTIONS
1389 EXAMPLES
1390 REVISION LOG
1391 --------------------------------------------------------------------------*/
1392 void *
H5SL_search(H5SL_t * slist,const void * key)1393 H5SL_search(H5SL_t *slist, const void *key)
1394 {
1395 H5SL_node_t *x; /* Current node to examine */
1396 uint32_t hashval = 0; /* Hash value for key */
1397 void *ret_value; /* Return value */
1398
1399 FUNC_ENTER_NOAPI_NOINIT_NOERR
1400
1401 /* Check args */
1402 HDassert(slist);
1403 HDassert(key);
1404
1405 /* Check internal consistency */
1406 /* (Pre-condition) */
1407
1408 /* Insert item into skip list */
1409
1410 /* Work through the forward pointers for a node, finding the node at each
1411 * level that is before the location to insert
1412 */
1413 x=slist->header;
1414 switch(slist->type) {
1415 case H5SL_TYPE_INT:
1416 H5SL_SEARCH(SCALAR, slist, x, const int, key, -)
1417 break;
1418
1419 case H5SL_TYPE_HADDR:
1420 H5SL_SEARCH(SCALAR, slist, x, const haddr_t, key, -)
1421 break;
1422
1423 case H5SL_TYPE_STR:
1424 H5SL_SEARCH(STRING, slist, x, char *, key, hashval)
1425 break;
1426
1427 case H5SL_TYPE_HSIZE:
1428 H5SL_SEARCH(SCALAR, slist, x, const hsize_t, key, -)
1429 break;
1430
1431 case H5SL_TYPE_UNSIGNED:
1432 H5SL_SEARCH(SCALAR, slist, x, const unsigned, key, -)
1433 break;
1434
1435 case H5SL_TYPE_SIZE:
1436 H5SL_SEARCH(SCALAR, slist, x, const size_t, key, -)
1437 break;
1438
1439 case H5SL_TYPE_OBJ:
1440 H5SL_SEARCH(OBJ, slist, x, const H5_obj_t, key, -)
1441 break;
1442
1443 case H5SL_TYPE_HID:
1444 H5SL_SEARCH(SCALAR, slist, x, const hid_t, key, -)
1445 break;
1446
1447 case H5SL_TYPE_GENERIC:
1448 H5SL_SEARCH(GENERIC, slist, x, const void, key, -)
1449 break;
1450
1451 default:
1452 HDassert(0 && "Unknown skiplist type!");
1453 } /* end switch */
1454
1455 /* 'key' must not have been found in list, if we get here */
1456 ret_value=NULL;
1457
1458 done:
1459 FUNC_LEAVE_NOAPI(ret_value)
1460 } /* end H5SL_search() */
1461
1462
1463 /*--------------------------------------------------------------------------
1464 NAME
1465 H5SL_less
1466 PURPOSE
1467 Search for object in a skip list that is less than or equal to 'key'
1468 USAGE
1469 void *H5SL_less(slist,key)
1470 H5SL_t *slist; IN/OUT: Pointer to skip list
1471 void *key; IN: Key for item to search for
1472
1473 RETURNS
1474 Returns pointer to item who key is less than or equal to 'key' on success,
1475 NULL on failure
1476 DESCRIPTION
1477 Search for an object in a skip list, according to it's key, returning the
1478 object itself (for an exact match), or the object with the next highest
1479 key that is less than 'key'
1480 GLOBAL VARIABLES
1481 COMMENTS, BUGS, ASSUMPTIONS
1482 EXAMPLES
1483 REVISION LOG
1484 --------------------------------------------------------------------------*/
1485 void *
H5SL_less(H5SL_t * slist,const void * key)1486 H5SL_less(H5SL_t *slist, const void *key)
1487 {
1488 H5SL_node_t *x; /* Current node to examine */
1489 uint32_t hashval = 0; /* Hash value for key */
1490 void *ret_value = NULL; /* Return value */
1491
1492 FUNC_ENTER_NOAPI_NOINIT_NOERR
1493
1494 /* Check args */
1495 HDassert(slist);
1496 HDassert(key);
1497
1498 /* Not currently supported */
1499 HDassert(!slist->safe_iterating);
1500
1501 /* Check internal consistency */
1502 /* (Pre-condition) */
1503
1504 /* Insert item into skip list */
1505
1506 /* Work through the forward pointers for a node, finding the node at each
1507 * level that is before the location to insert
1508 */
1509 x=slist->header;
1510 switch(slist->type) {
1511 case H5SL_TYPE_INT:
1512 H5SL_SEARCH(SCALAR, slist, x, const int, key, -)
1513 break;
1514
1515 case H5SL_TYPE_HADDR:
1516 H5SL_SEARCH(SCALAR, slist, x, const haddr_t, key, -)
1517 break;
1518
1519 case H5SL_TYPE_STR:
1520 H5SL_SEARCH(STRING, slist, x, char *, key, hashval)
1521 break;
1522
1523 case H5SL_TYPE_HSIZE:
1524 H5SL_SEARCH(SCALAR, slist, x, const hsize_t, key, -)
1525 break;
1526
1527 case H5SL_TYPE_UNSIGNED:
1528 H5SL_SEARCH(SCALAR, slist, x, const unsigned, key, -)
1529 break;
1530
1531 case H5SL_TYPE_SIZE:
1532 H5SL_SEARCH(SCALAR, slist, x, const size_t, key, -)
1533 break;
1534
1535 case H5SL_TYPE_OBJ:
1536 H5SL_SEARCH(OBJ, slist, x, const H5_obj_t, key, -)
1537 break;
1538
1539 case H5SL_TYPE_HID:
1540 H5SL_SEARCH(SCALAR, slist, x, const hid_t, key, -)
1541 break;
1542
1543 case H5SL_TYPE_GENERIC:
1544 H5SL_SEARCH(GENERIC, slist, x, const void, key, -)
1545 break;
1546
1547 default:
1548 HDassert(0 && "Unknown skiplist type!");
1549 } /* end switch */
1550
1551 /* An exact match for 'key' must not have been found in list, if we get here */
1552 /* Check for a node with a key that is less than the given 'key' */
1553 if(x==NULL) {
1554 /* Check for walking off the list */
1555 if(slist->last!=slist->header)
1556 ret_value=slist->last->item;
1557 else
1558 ret_value=NULL;
1559 } /* end if */
1560 else {
1561 if(x->backward!=slist->header)
1562 ret_value=x->backward->item;
1563 else
1564 ret_value=NULL;
1565 } /* end else */
1566
1567 done:
1568 FUNC_LEAVE_NOAPI(ret_value)
1569 } /* end H5SL_less() */
1570
1571
1572 /*--------------------------------------------------------------------------
1573 NAME
1574 H5SL_greater
1575 PURPOSE
1576 Search for object in a skip list that is greater than or equal to 'key'
1577 USAGE
1578 void *H5SL_greater(slist, key)
1579 H5SL_t *slist; IN/OUT: Pointer to skip list
1580 void *key; IN: Key for item to search for
1581
1582 RETURNS
1583 Returns pointer to item who key is greater than or equal to 'key' on success,
1584 NULL on failure
1585 DESCRIPTION
1586 Search for an object in a skip list, according to it's key, returning the
1587 object itself (for an exact match), or the object with the next lowest
1588 key that is greater than 'key'
1589 GLOBAL VARIABLES
1590 COMMENTS, BUGS, ASSUMPTIONS
1591 EXAMPLES
1592 REVISION LOG
1593 --------------------------------------------------------------------------*/
1594 void *
H5SL_greater(H5SL_t * slist,const void * key)1595 H5SL_greater(H5SL_t *slist, const void *key)
1596 {
1597 H5SL_node_t *x; /* Current node to examine */
1598 uint32_t hashval = 0; /* Hash value for key */
1599 void *ret_value = NULL; /* Return value */
1600
1601 FUNC_ENTER_NOAPI_NOINIT_NOERR
1602
1603 /* Check args */
1604 HDassert(slist);
1605 HDassert(key);
1606
1607 /* Not currently supported */
1608 HDassert(!slist->safe_iterating);
1609
1610 /* Check internal consistency */
1611 /* (Pre-condition) */
1612
1613 /* Insert item into skip list */
1614
1615 /* Work through the forward pointers for a node, finding the node at each
1616 * level that is before the location to insert
1617 */
1618 x = slist->header;
1619 switch(slist->type) {
1620 case H5SL_TYPE_INT:
1621 H5SL_SEARCH(SCALAR, slist, x, const int, key, -)
1622 break;
1623
1624 case H5SL_TYPE_HADDR:
1625 H5SL_SEARCH(SCALAR, slist, x, const haddr_t, key, -)
1626 break;
1627
1628 case H5SL_TYPE_STR:
1629 H5SL_SEARCH(STRING, slist, x, char *, key, hashval)
1630 break;
1631
1632 case H5SL_TYPE_HSIZE:
1633 H5SL_SEARCH(SCALAR, slist, x, const hsize_t, key, -)
1634 break;
1635
1636 case H5SL_TYPE_UNSIGNED:
1637 H5SL_SEARCH(SCALAR, slist, x, const unsigned, key, -)
1638 break;
1639
1640 case H5SL_TYPE_SIZE:
1641 H5SL_SEARCH(SCALAR, slist, x, const size_t, key, -)
1642 break;
1643
1644 case H5SL_TYPE_OBJ:
1645 H5SL_SEARCH(OBJ, slist, x, const H5_obj_t, key, -)
1646 break;
1647
1648 case H5SL_TYPE_HID:
1649 H5SL_SEARCH(SCALAR, slist, x, const hid_t, key, -)
1650 break;
1651
1652 case H5SL_TYPE_GENERIC:
1653 H5SL_SEARCH(GENERIC, slist, x, const void, key, -)
1654 break;
1655
1656 default:
1657 HDassert(0 && "Unknown skiplist type!");
1658 } /* end switch */
1659
1660 /* An exact match for 'key' must not have been found in list, if we get here */
1661 /* ('x' must be the next node with a key greater than the 'key', or NULL) */
1662 if(x)
1663 ret_value = x->item;
1664 else
1665 ret_value = NULL;
1666
1667 done:
1668 FUNC_LEAVE_NOAPI(ret_value)
1669 } /* end H5SL_greater() */
1670
1671
1672 /*--------------------------------------------------------------------------
1673 NAME
1674 H5SL_find
1675 PURPOSE
1676 Search for _node_ in a skip list
1677 USAGE
1678 H5SL_node_t *H5SL_node(slist,key)
1679 H5SL_t *slist; IN/OUT: Pointer to skip list
1680 void *key; IN: Key for item to search for
1681
1682 RETURNS
1683 Returns pointer to _node_ matching key on success, NULL on failure
1684 DESCRIPTION
1685 Search for an object in a skip list, according to it's key and returns
1686 the node that the object is attached to
1687 GLOBAL VARIABLES
1688 COMMENTS, BUGS, ASSUMPTIONS
1689 This routine is a useful starting point for next/prev calls
1690 EXAMPLES
1691 REVISION LOG
1692 --------------------------------------------------------------------------*/
1693 H5SL_node_t *
H5SL_find(H5SL_t * slist,const void * key)1694 H5SL_find(H5SL_t *slist, const void *key)
1695 {
1696 H5SL_node_t *x; /* Current node to examine */
1697 uint32_t hashval = 0; /* Hash value for key */
1698 H5SL_node_t *ret_value; /* Return value */
1699
1700 FUNC_ENTER_NOAPI_NOINIT_NOERR
1701
1702 /* Check args */
1703 HDassert(slist);
1704 HDassert(key);
1705
1706 /* Check internal consistency */
1707 /* (Pre-condition) */
1708
1709 /* Insert item into skip list */
1710
1711 /* Work through the forward pointers for a node, finding the node at each
1712 * level that is before the location to insert
1713 */
1714 x=slist->header;
1715 switch(slist->type) {
1716 case H5SL_TYPE_INT:
1717 H5SL_FIND(SCALAR, slist, x, const int, key, -)
1718 break;
1719
1720 case H5SL_TYPE_HADDR:
1721 H5SL_FIND(SCALAR, slist, x, const haddr_t, key, -)
1722 break;
1723
1724 case H5SL_TYPE_STR:
1725 H5SL_FIND(STRING, slist, x, char *, key, hashval)
1726 break;
1727
1728 case H5SL_TYPE_HSIZE:
1729 H5SL_FIND(SCALAR, slist, x, const hsize_t, key, -)
1730 break;
1731
1732 case H5SL_TYPE_UNSIGNED:
1733 H5SL_FIND(SCALAR, slist, x, const unsigned, key, -)
1734 break;
1735
1736 case H5SL_TYPE_SIZE:
1737 H5SL_FIND(SCALAR, slist, x, const size_t, key, -)
1738 break;
1739
1740 case H5SL_TYPE_OBJ:
1741 H5SL_FIND(OBJ, slist, x, const H5_obj_t, key, -)
1742 break;
1743
1744 case H5SL_TYPE_HID:
1745 H5SL_FIND(SCALAR, slist, x, const hid_t, key, -)
1746 break;
1747
1748 case H5SL_TYPE_GENERIC:
1749 H5SL_FIND(GENERIC, slist, x, const void, key, -)
1750 break;
1751
1752 default:
1753 HDassert(0 && "Unknown skiplist type!");
1754 } /* end switch */
1755
1756 /* 'key' must not have been found in list, if we get here */
1757 ret_value=NULL;
1758
1759 done:
1760 FUNC_LEAVE_NOAPI(ret_value)
1761 } /* end H5SL_find() */
1762
1763
1764 /*--------------------------------------------------------------------------
1765 NAME
1766 H5SL_below
1767 PURPOSE
1768 Search for _node_ in a skip list whose object is less than or equal to 'key'
1769 USAGE
1770 H5SL_node_t *H5SL_below(slist, key)
1771 H5SL_t *slist; IN/OUT: Pointer to skip list
1772 void *key; IN: Key for item to search for
1773
1774 RETURNS
1775 Returns pointer to _node_ who key is less than or equal to 'key' on success,
1776 NULL on failure
1777 DESCRIPTION
1778 Search for a node with an object in a skip list, according to it's key,
1779 returning the node itself (for an exact match), or the node with the next
1780 highest key that is less than 'key'
1781 GLOBAL VARIABLES
1782 COMMENTS, BUGS, ASSUMPTIONS
1783 EXAMPLES
1784 REVISION LOG
1785 --------------------------------------------------------------------------*/
1786 H5SL_node_t *
H5SL_below(H5SL_t * slist,const void * key)1787 H5SL_below(H5SL_t *slist, const void *key)
1788 {
1789 H5SL_node_t *x; /* Current node to examine */
1790 uint32_t hashval = 0; /* Hash value for key */
1791 H5SL_node_t *ret_value = NULL; /* Return value */
1792
1793 FUNC_ENTER_NOAPI_NOINIT_NOERR
1794
1795 /* Check args */
1796 HDassert(slist);
1797 HDassert(key);
1798
1799 /* Check internal consistency */
1800 /* (Pre-condition) */
1801
1802 /* Insert item into skip list */
1803
1804 /* Work through the forward pointers for a node, finding the node at each
1805 * level that is before the location to insert
1806 */
1807 x = slist->header;
1808 switch(slist->type) {
1809 case H5SL_TYPE_INT:
1810 H5SL_FIND(SCALAR, slist, x, const int, key, -)
1811 break;
1812
1813 case H5SL_TYPE_HADDR:
1814 H5SL_FIND(SCALAR, slist, x, const haddr_t, key, -)
1815 break;
1816
1817 case H5SL_TYPE_STR:
1818 H5SL_FIND(STRING, slist, x, char *, key, hashval)
1819 break;
1820
1821 case H5SL_TYPE_HSIZE:
1822 H5SL_FIND(SCALAR, slist, x, const hsize_t, key, -)
1823 break;
1824
1825 case H5SL_TYPE_UNSIGNED:
1826 H5SL_FIND(SCALAR, slist, x, const unsigned, key, -)
1827 break;
1828
1829 case H5SL_TYPE_SIZE:
1830 H5SL_FIND(SCALAR, slist, x, const size_t, key, -)
1831 break;
1832
1833 case H5SL_TYPE_OBJ:
1834 H5SL_FIND(OBJ, slist, x, const H5_obj_t, key, -)
1835 break;
1836
1837 case H5SL_TYPE_HID:
1838 H5SL_FIND(SCALAR, slist, x, const hid_t, key, -)
1839 break;
1840
1841 case H5SL_TYPE_GENERIC:
1842 H5SL_FIND(GENERIC, slist, x, const void, key, -)
1843 break;
1844
1845 default:
1846 HDassert(0 && "Unknown skiplist type!");
1847 } /* end switch */
1848
1849 /* An exact match for 'key' must not have been found in list, if we get here */
1850 /* Check for a node with a key that is less than the given 'key' */
1851 if(NULL == x) {
1852 /* Check for walking off the list */
1853 if(slist->last != slist->header)
1854 ret_value = slist->last;
1855 else
1856 ret_value = NULL;
1857 } /* end if */
1858 else {
1859 if(x->backward != slist->header)
1860 ret_value = x->backward;
1861 else
1862 ret_value = NULL;
1863 } /* end else */
1864
1865 done:
1866 FUNC_LEAVE_NOAPI(ret_value)
1867 } /* end H5SL_below() */
1868
1869
1870 /*--------------------------------------------------------------------------
1871 NAME
1872 H5SL_above
1873 PURPOSE
1874 Search for _node_ in a skip list whose object is greater than or equal to 'key'
1875 USAGE
1876 H5SL_node_t *H5SL_above(slist, key)
1877 H5SL_t *slist; IN/OUT: Pointer to skip list
1878 void *key; IN: Key for item to search for
1879
1880 RETURNS
1881 Returns pointer to _node_ with object that has a key is greater than or
1882 equal to 'key' on success, NULL on failure
1883 DESCRIPTION
1884 Search for a node with an object in a skip list, according to it's key,
1885 returning the node itself (for an exact match), or the node with the next
1886 lowest key that is greater than 'key'
1887 GLOBAL VARIABLES
1888 COMMENTS, BUGS, ASSUMPTIONS
1889 EXAMPLES
1890 REVISION LOG
1891 --------------------------------------------------------------------------*/
1892 H5SL_node_t *
H5SL_above(H5SL_t * slist,const void * key)1893 H5SL_above(H5SL_t *slist, const void *key)
1894 {
1895 H5SL_node_t *x; /* Current node to examine */
1896 uint32_t hashval = 0; /* Hash value for key */
1897 H5SL_node_t *ret_value = NULL; /* Return value */
1898
1899 FUNC_ENTER_NOAPI_NOINIT_NOERR
1900
1901 /* Check args */
1902 HDassert(slist);
1903 HDassert(key);
1904
1905 /* Check internal consistency */
1906 /* (Pre-condition) */
1907
1908 /* Insert item into skip list */
1909
1910 /* Work through the forward pointers for a node, finding the node at each
1911 * level that is before the location to insert
1912 */
1913 x = slist->header;
1914 switch(slist->type) {
1915 case H5SL_TYPE_INT:
1916 H5SL_FIND(SCALAR, slist, x, const int, key, -)
1917 break;
1918
1919 case H5SL_TYPE_HADDR:
1920 H5SL_FIND(SCALAR, slist, x, const haddr_t, key, -)
1921 break;
1922
1923 case H5SL_TYPE_STR:
1924 H5SL_FIND(STRING, slist, x, char *, key, hashval)
1925 break;
1926
1927 case H5SL_TYPE_HSIZE:
1928 H5SL_FIND(SCALAR, slist, x, const hsize_t, key, -)
1929 break;
1930
1931 case H5SL_TYPE_UNSIGNED:
1932 H5SL_FIND(SCALAR, slist, x, const unsigned, key, -)
1933 break;
1934
1935 case H5SL_TYPE_SIZE:
1936 H5SL_FIND(SCALAR, slist, x, const size_t, key, -)
1937 break;
1938
1939 case H5SL_TYPE_OBJ:
1940 H5SL_FIND(OBJ, slist, x, const H5_obj_t, key, -)
1941 break;
1942
1943 case H5SL_TYPE_HID:
1944 H5SL_FIND(SCALAR, slist, x, const hid_t, key, -)
1945 break;
1946
1947 case H5SL_TYPE_GENERIC:
1948 H5SL_FIND(GENERIC, slist, x, const void, key, -)
1949 break;
1950
1951 default:
1952 HDassert(0 && "Unknown skiplist type!");
1953 } /* end switch */
1954
1955 /* An exact match for 'key' must not have been found in list, if we get here */
1956 /* ('x' must be the next node with a key greater than the 'key', or NULL) */
1957 if(x)
1958 ret_value = x;
1959 else
1960 ret_value = NULL;
1961
1962 done:
1963 FUNC_LEAVE_NOAPI(ret_value)
1964 } /* end H5SL_above() */
1965
1966
1967 /*--------------------------------------------------------------------------
1968 NAME
1969 H5SL_first
1970 PURPOSE
1971 Gets a pointer to the first node in a skip list
1972 USAGE
1973 H5SL_node_t *H5SL_first(slist)
1974 H5SL_t *slist; IN: Pointer to skip list
1975
1976 RETURNS
1977 Returns pointer to first node in skip list on success, NULL on failure.
1978 DESCRIPTION
1979 Retrieves a pointer to the first node in a skip list, for iterating over
1980 the list.
1981 GLOBAL VARIABLES
1982 COMMENTS, BUGS, ASSUMPTIONS
1983 EXAMPLES
1984 REVISION LOG
1985 --------------------------------------------------------------------------*/
1986 H5SL_node_t *
H5SL_first(H5SL_t * slist)1987 H5SL_first(H5SL_t *slist)
1988 {
1989 FUNC_ENTER_NOAPI_NOINIT_NOERR
1990
1991 /* Check args */
1992 HDassert(slist);
1993
1994 /* Not currently supported */
1995 HDassert(!slist->safe_iterating);
1996
1997 /* Check internal consistency */
1998 /* (Pre-condition) */
1999
2000 FUNC_LEAVE_NOAPI(slist->header->forward[0])
2001 } /* end H5SL_first() */
2002
2003
2004 /*--------------------------------------------------------------------------
2005 NAME
2006 H5SL_next
2007 PURPOSE
2008 Gets a pointer to the next node in a skip list
2009 USAGE
2010 H5SL_node_t *H5SL_next(slist_node)
2011 H5SL_node_t *slist_node; IN: Pointer to skip list node
2012
2013 RETURNS
2014 Returns pointer to node after slist_node in skip list on success, NULL on failure.
2015 DESCRIPTION
2016 Retrieves a pointer to the next node in a skip list, for iterating over
2017 the list.
2018 GLOBAL VARIABLES
2019 COMMENTS, BUGS, ASSUMPTIONS
2020 EXAMPLES
2021 REVISION LOG
2022 --------------------------------------------------------------------------*/
2023 H5SL_node_t *
H5SL_next(H5SL_node_t * slist_node)2024 H5SL_next(H5SL_node_t *slist_node)
2025 {
2026 FUNC_ENTER_NOAPI_NOINIT_NOERR
2027
2028 /* Check args */
2029 HDassert(slist_node);
2030
2031 /* Not currently supported */
2032 HDassert(!slist_node->removed);
2033
2034 /* Check internal consistency */
2035 /* (Pre-condition) */
2036
2037 FUNC_LEAVE_NOAPI(slist_node->forward[0])
2038 } /* end H5SL_next() */
2039
2040
2041 /*--------------------------------------------------------------------------
2042 NAME
2043 H5SL_prev
2044 PURPOSE
2045 Gets a pointer to the previos node in a skip list
2046 USAGE
2047 H5SL_node_t *H5SL_prev(slist_node)
2048 H5SL_node_t *slist_node; IN: Pointer to skip list node
2049
2050 RETURNS
2051 Returns pointer to node before slist_node in skip list on success, NULL on failure.
2052 DESCRIPTION
2053 Retrieves a pointer to the previous node in a skip list, for iterating over
2054 the list.
2055 GLOBAL VARIABLES
2056 COMMENTS, BUGS, ASSUMPTIONS
2057 EXAMPLES
2058 REVISION LOG
2059 --------------------------------------------------------------------------*/
2060 H5SL_node_t *
H5SL_prev(H5SL_node_t * slist_node)2061 H5SL_prev(H5SL_node_t *slist_node)
2062 {
2063 FUNC_ENTER_NOAPI_NOINIT_NOERR
2064
2065 /* Check args */
2066 HDassert(slist_node);
2067
2068 /* Not currently supported */
2069 HDassert(!slist_node->removed);
2070
2071 /* Check internal consistency */
2072 /* (Pre-condition) */
2073
2074 /* Walk backward, detecting the header node (which has it's key set to NULL) */
2075 FUNC_LEAVE_NOAPI(slist_node->backward->key==NULL ? NULL : slist_node->backward)
2076 } /* end H5SL_prev() */
2077
2078
2079 /*--------------------------------------------------------------------------
2080 NAME
2081 H5SL_last
2082 PURPOSE
2083 Gets a pointer to the last node in a skip list
2084 USAGE
2085 H5SL_node_t *H5SL_last(slist)
2086 H5SL_t *slist; IN: Pointer to skip list
2087
2088 RETURNS
2089 Returns pointer to last node in skip list on success, NULL on failure.
2090 DESCRIPTION
2091 Retrieves a pointer to the last node in a skip list, for iterating over
2092 the list.
2093 GLOBAL VARIABLES
2094 COMMENTS, BUGS, ASSUMPTIONS
2095 EXAMPLES
2096 REVISION LOG
2097 --------------------------------------------------------------------------*/
2098 H5SL_node_t *
H5SL_last(H5SL_t * slist)2099 H5SL_last(H5SL_t *slist)
2100 {
2101 FUNC_ENTER_NOAPI_NOINIT_NOERR
2102
2103 /* Check args */
2104 HDassert(slist);
2105
2106 /* Not currently supported */
2107 HDassert(!slist->safe_iterating);
2108
2109 /* Check internal consistency */
2110 /* (Pre-condition) */
2111
2112 /* Find last node, avoiding the header node */
2113 FUNC_LEAVE_NOAPI(slist->last==slist->header ? NULL : slist->last)
2114 } /* end H5SL_last() */
2115
2116
2117 /*--------------------------------------------------------------------------
2118 NAME
2119 H5SL_item
2120 PURPOSE
2121 Gets pointer to the 'item' for a skip list node
2122 USAGE
2123 void *H5SL_item(slist_node)
2124 H5SL_node_t *slist_node; IN: Pointer to skip list node
2125
2126 RETURNS
2127 Returns pointer to node 'item' on success, NULL on failure.
2128 DESCRIPTION
2129 Retrieves a node's 'item'
2130 GLOBAL VARIABLES
2131 COMMENTS, BUGS, ASSUMPTIONS
2132 EXAMPLES
2133 REVISION LOG
2134 --------------------------------------------------------------------------*/
2135 void *
H5SL_item(H5SL_node_t * slist_node)2136 H5SL_item(H5SL_node_t *slist_node)
2137 {
2138 FUNC_ENTER_NOAPI_NOINIT_NOERR
2139
2140 /* Check args */
2141 HDassert(slist_node);
2142
2143 /* Not currently supported */
2144 HDassert(!slist_node->removed);
2145
2146 /* Check internal consistency */
2147 /* (Pre-condition) */
2148
2149 FUNC_LEAVE_NOAPI(slist_node->item)
2150 } /* end H5SL_item() */
2151
2152
2153 /*--------------------------------------------------------------------------
2154 NAME
2155 H5SL_iterate
2156 PURPOSE
2157 Iterate over all nodes in a skip list
2158 USAGE
2159 herr_t H5SL_iterate(slist, op, op_data)
2160 H5SL_t *slist; IN/OUT: Pointer to skip list to iterate over
2161 H5SL_operator_t op; IN: Callback function for iteration
2162 void *op_data; IN/OUT: Pointer to application data for callback
2163
2164 RETURNS
2165 Returns a negative value if something is wrong, the return
2166 value of the last operator if it was non-zero, or zero if all
2167 nodes were processed.
2168 DESCRIPTION
2169 Iterate over all the nodes in a skip list, calling an application callback
2170 with the item, key and any operator data.
2171
2172 The operator callback receives a pointer to the item and key for the list
2173 being iterated over ('mesg'), and the pointer to the operator data passed
2174 in to H5SL_iterate ('op_data'). The return values from an operator are:
2175 A. Zero causes the iterator to continue, returning zero when all
2176 nodes of that type have been processed.
2177 B. Positive causes the iterator to immediately return that positive
2178 value, indicating short-circuit success.
2179 C. Negative causes the iterator to immediately return that value,
2180 indicating failure.
2181 GLOBAL VARIABLES
2182 COMMENTS, BUGS, ASSUMPTIONS
2183 EXAMPLES
2184 REVISION LOG
2185 --------------------------------------------------------------------------*/
2186 herr_t
H5SL_iterate(H5SL_t * slist,H5SL_operator_t op,void * op_data)2187 H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data)
2188 {
2189 H5SL_node_t *node; /* Pointer to current skip list node */
2190 H5SL_node_t *next; /* Pointer to next skip list node */
2191 herr_t ret_value = 0; /* Return value */
2192
2193 FUNC_ENTER_NOAPI_NOINIT_NOERR
2194
2195 /* Check args */
2196 HDassert(slist);
2197
2198 /* Check internal consistency */
2199 /* (Pre-condition) */
2200
2201 /* Free skip list nodes */
2202 node = slist->header->forward[0];
2203 while(node != NULL) {
2204 /* Protect against the node being deleted by the callback */
2205 next = node->forward[0];
2206
2207 /* Call the iterator callback */
2208 /* Casting away const OK -QAK */
2209 if(!node->removed)
2210 if((ret_value = (op)(node->item, (void *)node->key, op_data)) != 0)
2211 break;
2212
2213 /* Advance to next node */
2214 node = next;
2215 } /* end while */
2216
2217 FUNC_LEAVE_NOAPI(ret_value)
2218 } /* end H5SL_iterate() */
2219
2220
2221 /*--------------------------------------------------------------------------
2222 NAME
2223 H5SL_release
2224 PURPOSE
2225 Release all nodes from a skip list
2226 USAGE
2227 herr_t H5SL_release(slist)
2228 H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
2229
2230 RETURNS
2231 Returns non-negative on success, negative on failure.
2232 DESCRIPTION
2233 Release all the nodes in a skip list. Any objects left in the skip list
2234 nodes are not deallocated.
2235 GLOBAL VARIABLES
2236 COMMENTS, BUGS, ASSUMPTIONS
2237 The skip list itself is still valid, it just has all its nodes removed.
2238 EXAMPLES
2239 REVISION LOG
2240 --------------------------------------------------------------------------*/
2241 herr_t
H5SL_release(H5SL_t * slist)2242 H5SL_release(H5SL_t *slist)
2243 {
2244 FUNC_ENTER_NOAPI_NOINIT_NOERR
2245
2246 /* Check args */
2247 HDassert(slist);
2248
2249 /* Not currently supported */
2250 HDassert(!slist->safe_iterating);
2251
2252 /* Check internal consistency */
2253 /* (Pre-condition) */
2254
2255 /* Free skip list nodes */
2256 H5SL_release_common(slist,NULL,NULL); /* always succeeds */
2257
2258 FUNC_LEAVE_NOAPI(SUCCEED)
2259 } /* end H5SL_release() */
2260
2261
2262 /*--------------------------------------------------------------------------
2263 NAME
2264 H5SL_free
2265 PURPOSE
2266 Release all nodes from a skip list, freeing all nodes
2267 USAGE
2268 herr_t H5SL_free(slist,op,op_data)
2269 H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
2270 H5SL_operator_t op; IN: Callback function to free item & key
2271 void *op_data; IN/OUT: Pointer to application data for callback
2272
2273 RETURNS
2274 Returns non-negative on success, negative on failure.
2275 DESCRIPTION
2276 Release all the nodes in a skip list. Any objects left in
2277 the skip list have the 'op' routine called for each.
2278 GLOBAL VARIABLES
2279 COMMENTS, BUGS, ASSUMPTIONS
2280 The skip list itself is still valid, it just has all its nodes removed.
2281
2282 The return value from the 'op' routine is ignored.
2283
2284 This routine is essentially a combination of iterating over all the nodes
2285 (where the iterator callback is supposed to free the items and/or keys)
2286 followed by a call to H5SL_release().
2287 EXAMPLES
2288 REVISION LOG
2289 --------------------------------------------------------------------------*/
2290 herr_t
H5SL_free(H5SL_t * slist,H5SL_operator_t op,void * op_data)2291 H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data)
2292 {
2293 FUNC_ENTER_NOAPI_NOINIT_NOERR
2294
2295 /* Check args */
2296 HDassert(slist);
2297
2298 /* Not currently supported */
2299 HDassert(!slist->safe_iterating);
2300
2301 /* Check internal consistency */
2302 /* (Pre-condition) */
2303
2304 /* Free skip list nodes */
2305 H5SL_release_common(slist,op,op_data); /* always succeeds */
2306
2307 FUNC_LEAVE_NOAPI(SUCCEED)
2308 } /* end H5SL_free() */
2309
2310
2311 /*--------------------------------------------------------------------------
2312 NAME
2313 H5SL_try_free_safe
2314 PURPOSE
2315 Makes the supplied callback on all nodes in the skip list, freeing each
2316 node that the callback returns TRUE for.
2317 USAGE
2318 herr_t PURPOSE(slist,op,opdata)
2319 H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
2320 H5SL_try_free_op_t op; IN: Callback function to try to free item & key
2321 void *op_data; IN/OUT: Pointer to application data for callback
2322
2323 RETURNS
2324 Returns non-negative on success, negative on failure.
2325 DESCRIPTION
2326 Makes the supplied callback on all nodes in the skip list, freeing each
2327 node that the callback returns TRUE for. The iteration is performed in
2328 a safe manner, such that the callback can call H5SL_remove(),
2329 H5SL_search(), H5SL_find(), and H5SL_iterate() on nodes in this
2330 skiplist, except H5SL_remove() may not be call on *this* node.
2331 GLOBAL VARIABLES
2332 COMMENTS, BUGS, ASSUMPTIONS
2333 This function is written to be most efficient when most nodes are
2334 removed from the skiplist, as it rebuilds the nodes afterwards.
2335 EXAMPLES
2336 REVISION LOG
2337 --------------------------------------------------------------------------*/
2338 herr_t
H5SL_try_free_safe(H5SL_t * slist,H5SL_try_free_op_t op,void * op_data)2339 H5SL_try_free_safe(H5SL_t *slist, H5SL_try_free_op_t op, void *op_data)
2340 {
2341 H5SL_node_t *node, *next_node, *last_node; /* Pointers to skip list nodes */
2342 htri_t op_ret;
2343 herr_t ret_value = SUCCEED;
2344
2345 FUNC_ENTER_NOAPI_NOINIT
2346
2347 /* Check args */
2348 HDassert(slist);
2349 HDassert(op);
2350
2351 /* Not currently supported */
2352 HDassert(!slist->safe_iterating);
2353
2354 /* Check internal consistency */
2355 /* (Pre-condition) */
2356
2357 /* Mark skip list as safe iterating, so nodes aren't freed out from under
2358 * us */
2359 slist->safe_iterating = TRUE;
2360
2361 /* Iterate over skip list nodes, making the callback for each and marking
2362 * them as removed if requested by the callback */
2363 node = slist->header->forward[0];
2364 while(node) {
2365 /* Check if the node was already removed */
2366 if(!node->removed) {
2367 /* Call callback */
2368 /* Casting away const OK -NAF */
2369 if((op_ret = (op)(node->item , (void *)node->key, op_data)) < 0)
2370 HGOTO_ERROR(H5E_SLIST, H5E_CALLBACK, FAIL, "callback operation failed")
2371
2372 /* Check if op indicated that the node should be removed */
2373 if(op_ret)
2374 /* Mark the node as removed */
2375 node->removed = TRUE;
2376 } /* end if */
2377
2378 /* Advance node */
2379 node = node->forward[0];
2380 } /* end while */
2381
2382 /* Reset safe_iterating */
2383 slist->safe_iterating = FALSE;
2384
2385 /* Iterate over nodes, freeing ones marked as removed */
2386 node = slist->header->forward[0];
2387 last_node = slist->header;
2388 while(node) {
2389 /* Save next node */
2390 next_node = node->forward[0];
2391
2392 /* Check if the node was marked as removed */
2393 if(node->removed) {
2394 /* Remove the node */
2395 node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], node->forward);
2396 node = H5FL_FREE(H5SL_node_t, node);
2397 slist->nobjs--;
2398 } /* end if */
2399 else {
2400 /* Update backwards and forwards[0] pointers, and set the level to
2401 * 0. Since the list is flattened we must rebuild the skiplist
2402 * afterwards. */
2403 /* Set level to 0. Note there is no need to preserve
2404 * node->forward[0] since it was cached above and will always be
2405 * updated later. */
2406 if(node->level > 0) {
2407 node->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[node->log_nalloc], (void *)node->forward);
2408 if(NULL == (node->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
2409 HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, FAIL, "memory allocation failed")
2410 node->log_nalloc = 0;
2411 node->level = 0;
2412 } /* end if */
2413
2414 /* Update pointers */
2415 last_node->forward[0] = node;
2416 node->backward = last_node;
2417 last_node = node;
2418 } /* end else */
2419
2420 /* Advance node */
2421 node = next_node;
2422 } /* end while */
2423
2424 /* Final pointer update */
2425 last_node->forward[0] = NULL;
2426 slist->last = last_node;
2427
2428 /* Demote skip list to level 0 */
2429 if(slist->curr_level > 0) {
2430 HDassert(slist->header->level == (size_t)slist->curr_level);
2431
2432 node = slist->header->forward[0];
2433 slist->header->forward = (H5SL_node_t **)H5FL_FAC_FREE(H5SL_fac_g[slist->header->log_nalloc], (void *)slist->header->forward);
2434 if(NULL == (slist->header->forward = (H5SL_node_t **)H5FL_FAC_MALLOC(H5SL_fac_g[0])))
2435 HGOTO_ERROR(H5E_SLIST, H5E_CANTALLOC, FAIL, "memory allocation failed")
2436 slist->header->forward[0] = node;
2437 slist->header->log_nalloc = 0;
2438 slist->header->level = 0;
2439 } /* end if */
2440
2441 /* Check if there are any nodes left */
2442 if(slist->nobjs > 0) {
2443 int i;
2444
2445 HDassert(slist->header->forward[0]);
2446
2447 /* Set skiplist level to 0 */
2448 slist->curr_level = 0;
2449
2450 /* Rebuild the forward arrays */
2451 for(i = 0; slist->curr_level >= i; i++) {
2452 HDassert(slist->curr_level == i);
2453
2454 /* Promote every third node this level until we run out of nodes */
2455 node = last_node = slist->header;
2456 while(1) {
2457 /* Check second node in gap, if not present, no need to promote
2458 * further this level. */
2459 HDassert(node->forward[i]);
2460 node = node->forward[i]->forward[i];
2461 if(!node)
2462 break;
2463
2464 /* Check third and fourth node in gap, if either is not present,
2465 * no need to promote further this level. */
2466 node = node->forward[i];
2467 if(!node || !node->forward[i])
2468 break;
2469
2470 /* Promote the third node in the gap */
2471 H5SL_PROMOTE(slist, node, last_node, FAIL)
2472 last_node = node;
2473 } /* end while */
2474 } /* end for */
2475 } /* end if */
2476 else {
2477 HDassert(!slist->header->forward[0]);
2478 HDassert(slist->last == slist->header);
2479 HDassert(slist->nobjs == 0);
2480
2481 /* Reset the skiplist level */
2482 slist->curr_level = -1;
2483 } /* end else */
2484
2485 done:
2486 FUNC_LEAVE_NOAPI(ret_value)
2487 } /* end H5SL_try_free_safe() */
2488
2489
2490 /*--------------------------------------------------------------------------
2491 NAME
2492 H5SL_destroy
2493 PURPOSE
2494 Close a skip list, deallocating it and freeing all its nodes.
2495 USAGE
2496 herr_t H5SL_destroy(slist,op,opdata)
2497 H5SL_t *slist; IN/OUT: Pointer to skip list to close
2498 H5SL_operator_t op; IN: Callback function to free item & key
2499 void *op_data; IN/OUT: Pointer to application data for callback
2500
2501 RETURNS
2502 Returns non-negative on success, negative on failure.
2503 DESCRIPTION
2504 Close a skip list, freeing all internal information. Any objects left in
2505 the skip list have the 'op' routine called for each.
2506 GLOBAL VARIABLES
2507 COMMENTS, BUGS, ASSUMPTIONS
2508 The return value from the 'op' routine is ignored.
2509
2510 This routine is essentially a combination of iterating over all the nodes
2511 (where the iterator callback is supposed to free the items and/or keys)
2512 followed by a call to H5SL_close().
2513 EXAMPLES
2514 REVISION LOG
2515 --------------------------------------------------------------------------*/
2516 herr_t
H5SL_destroy(H5SL_t * slist,H5SL_operator_t op,void * op_data)2517 H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data)
2518 {
2519 herr_t ret_value=SUCCEED; /* Return value */
2520
2521 FUNC_ENTER_NOAPI_NOINIT_NOERR
2522
2523 /* Check args */
2524 HDassert(slist);
2525
2526 /* Check internal consistency */
2527 /* (Pre-condition) */
2528
2529 /* Close skip list */
2530 (void)H5SL_close_common(slist,op,op_data); /* always succeeds */
2531
2532 FUNC_LEAVE_NOAPI(ret_value)
2533 } /* end H5SL_destroy() */
2534
2535
2536 /*--------------------------------------------------------------------------
2537 NAME
2538 H5SL_close
2539 PURPOSE
2540 Close a skip list, deallocating it.
2541 USAGE
2542 herr_t H5SL_close(slist)
2543 H5SL_t *slist; IN/OUT: Pointer to skip list to close
2544
2545 RETURNS
2546 Returns non-negative on success, negative on failure.
2547 DESCRIPTION
2548 Close a skip list, freeing all internal information. Any objects left in
2549 the skip list are not deallocated.
2550 GLOBAL VARIABLES
2551 COMMENTS, BUGS, ASSUMPTIONS
2552 EXAMPLES
2553 REVISION LOG
2554 --------------------------------------------------------------------------*/
2555 herr_t
H5SL_close(H5SL_t * slist)2556 H5SL_close(H5SL_t *slist)
2557 {
2558 FUNC_ENTER_NOAPI_NOINIT_NOERR
2559
2560 /* Check args */
2561 HDassert(slist);
2562
2563 /* Check internal consistency */
2564 /* (Pre-condition) */
2565
2566 /* Close skip list */
2567 (void)H5SL_close_common(slist,NULL,NULL); /* always succeeds */
2568
2569 FUNC_LEAVE_NOAPI(SUCCEED)
2570 } /* end H5SL_close() */
2571
2572