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