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