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 *
16 * Created: H5B.c
17 * Jul 10 1997
18 * Robb Matzke <matzke@llnl.gov>
19 *
20 * Purpose: Implements balanced, sibling-linked, N-ary trees
21 * capable of storing any type of data with unique key
22 * values.
23 *
24 * A B-link-tree is a balanced tree where each node has
25 * a pointer to its left and right siblings. A
26 * B-link-tree is a rooted tree having the following
27 * properties:
28 *
29 * 1. Every node, x, has the following fields:
30 *
31 * a. level[x], the level in the tree at which node
32 * x appears. Leaf nodes are at level zero.
33 *
34 * b. n[x], the number of children pointed to by the
35 * node. Internal nodes point to subtrees while
36 * leaf nodes point to arbitrary data.
37 *
38 * c. The child pointers themselves, child[x,i] such
39 * that 0 <= i < n[x].
40 *
41 * d. n[x]+1 key values stored in increasing
42 * order:
43 *
44 * key[x,0] < key[x,1] < ... < key[x,n[x]].
45 *
46 * e. left[x] is a pointer to the node's left sibling
47 * or the null pointer if this is the left-most
48 * node at this level in the tree.
49 *
50 * f. right[x] is a pointer to the node's right
51 * sibling or the null pointer if this is the
52 * right-most node at this level in the tree.
53 *
54 * 3. The keys key[x,i] partition the key spaces of the
55 * children of x:
56 *
57 * key[x,i] <= key[child[x,i],j] <= key[x,i+1]
58 *
59 * for any valid combination of i and j.
60 *
61 * 4. There are lower and upper bounds on the number of
62 * child pointers a node can contain. These bounds
63 * can be expressed in terms of a fixed integer k>=2
64 * called the `minimum degree' of the B-tree.
65 *
66 * a. Every node other than the root must have at least
67 * k child pointers and k+1 keys. If the tree is
68 * nonempty, the root must have at least one child
69 * pointer and two keys.
70 *
71 * b. Every node can contain at most 2k child pointers
72 * and 2k+1 keys. A node is `full' if it contains
73 * exactly 2k child pointers and 2k+1 keys.
74 *
75 * 5. When searching for a particular value, V, and
76 * key[V] = key[x,i] for some node x and entry i,
77 * then:
78 *
79 * a. If i=0 the child[0] is followed.
80 *
81 * b. If i=n[x] the child[n[x]-1] is followed.
82 *
83 * c. Otherwise, the child that is followed
84 * (either child[x,i-1] or child[x,i]) is
85 * determined by the type of object to which the
86 * leaf nodes of the tree point and is controlled
87 * by the key comparison function registered for
88 * that type of B-tree.
89 *
90 *
91 *-------------------------------------------------------------------------
92 */
93
94 /****************/
95 /* Module Setup */
96 /****************/
97
98 #include "H5Bmodule.h" /* This source code file is part of the H5B module */
99
100
101 /***********/
102 /* Headers */
103 /***********/
104 #include "H5private.h" /* Generic Functions */
105 #include "H5Bpkg.h" /* B-link trees */
106 #include "H5CXprivate.h" /* API Contexts */
107 #include "H5Eprivate.h" /* Error handling */
108 #include "H5Iprivate.h" /* IDs */
109 #include "H5MFprivate.h" /* File memory management */
110 #include "H5Pprivate.h" /* Property lists */
111
112
113 /****************/
114 /* Local Macros */
115 /****************/
116 #define H5B_SIZEOF_HDR(F) \
117 (H5_SIZEOF_MAGIC + /*magic number */ \
118 4 + /*type, level, num entries */ \
119 2*H5F_SIZEOF_ADDR(F)) /*left and right sibling addresses */
120
121 /* Default initializer for H5B_ins_ud_t */
122 #define H5B_INS_UD_T_NULL {NULL, HADDR_UNDEF, H5AC__NO_FLAGS_SET}
123
124 /******************/
125 /* Local Typedefs */
126 /******************/
127
128 /* "user data" for iterating over B-tree (collects B-tree metadata size) */
129 typedef struct H5B_iter_ud_t {
130 H5B_info_t *bt_info; /* Information about B-tree */
131 void *udata; /* Node type's 'udata' for loading & iterator callback */
132 } H5B_info_ud_t;
133
134 /* Convenience struct for the arguments needed to unprotect a b-tree after a
135 * call to H5B__iterate_helper() or H5B__split() */
136 typedef struct H5B_ins_ud_t {
137 H5B_t *bt; /* B-tree */
138 haddr_t addr; /* B-tree address */
139 unsigned cache_flags; /* Cache flags for H5AC_unprotect() */
140 } H5B_ins_ud_t;
141
142
143 /********************/
144 /* Local Prototypes */
145 /********************/
146 static H5B_ins_t H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud,
147 const H5B_class_t *type, uint8_t *lt_key, hbool_t *lt_key_changed,
148 uint8_t *md_key, void *udata, uint8_t *rt_key, hbool_t *rt_key_changed,
149 H5B_ins_ud_t *split_bt_ud/*out*/);
150 static herr_t H5B__insert_child(H5B_t *bt, unsigned *bt_flags,
151 unsigned idx, haddr_t child,
152 H5B_ins_t anchor, const void *md_key);
153 static herr_t H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
154 void *udata, H5B_ins_ud_t *split_bt_ud/*out*/);
155 static H5B_t * H5B__copy(const H5B_t *old_bt);
156
157
158 /*********************/
159 /* Package Variables */
160 /*********************/
161
162 /* Package initialization variable */
163 hbool_t H5_PKG_INIT_VAR = FALSE;
164
165 /* Declare a free list to manage the haddr_t sequence information */
166 H5FL_SEQ_DEFINE(haddr_t);
167
168 /* Declare a PQ free list to manage the native block information */
169 H5FL_BLK_DEFINE(native_block);
170
171 /* Declare a free list to manage the H5B_t struct */
172 H5FL_DEFINE(H5B_t);
173
174
175 /*****************************/
176 /* Library Private Variables */
177 /*****************************/
178
179
180 /*******************/
181 /* Local Variables */
182 /*******************/
183
184 /* Declare a free list to manage the H5B_shared_t struct */
185 H5FL_DEFINE_STATIC(H5B_shared_t);
186
187 /* Declare a free list to manage the raw page information */
188 H5FL_BLK_DEFINE_STATIC(page);
189
190 /* Declare a free list to manage the native key offset sequence information */
191 H5FL_SEQ_DEFINE_STATIC(size_t);
192
193
194
195 /*-------------------------------------------------------------------------
196 * Function: H5B_create
197 *
198 * Purpose: Creates a new empty B-tree leaf node. The UDATA pointer is
199 * passed as an argument to the sizeof_rkey() method for the
200 * B-tree.
201 *
202 * Return: Success: Non-negative, and the address of new node is
203 * returned through the ADDR_P argument.
204 *
205 * Failure: Negative
206 *
207 * Programmer: Robb Matzke
208 * matzke@llnl.gov
209 * Jun 23 1997
210 *
211 *-------------------------------------------------------------------------
212 */
213 herr_t
H5B_create(H5F_t * f,const H5B_class_t * type,void * udata,haddr_t * addr_p)214 H5B_create(H5F_t *f, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*/)
215 {
216 H5B_t *bt = NULL;
217 H5B_shared_t *shared=NULL; /* Pointer to shared B-tree info */
218 herr_t ret_value = SUCCEED;
219
220 FUNC_ENTER_NOAPI(FAIL)
221
222 /*
223 * Check arguments.
224 */
225 HDassert(f);
226 HDassert(type);
227 HDassert(addr_p);
228
229 /*
230 * Allocate file and memory data structures.
231 */
232 if(NULL == (bt = H5FL_MALLOC(H5B_t)))
233 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
234 HDmemset(&bt->cache_info, 0, sizeof(H5AC_info_t));
235 bt->level = 0;
236 bt->left = HADDR_UNDEF;
237 bt->right = HADDR_UNDEF;
238 bt->nchildren = 0;
239 if(NULL == (bt->rc_shared = (type->get_shared)(f, udata)))
240 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree node buffer")
241 H5UC_INC(bt->rc_shared);
242 shared=(H5B_shared_t *)H5UC_GET_OBJ(bt->rc_shared);
243 HDassert(shared);
244 if(NULL == (bt->native = H5FL_BLK_MALLOC(native_block, shared->sizeof_keys)) ||
245 NULL == (bt->child = H5FL_SEQ_MALLOC(haddr_t, (size_t)shared->two_k)))
246 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
247 if(HADDR_UNDEF == (*addr_p = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
248 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "file allocation failed for B-tree root node")
249
250 /*
251 * Cache the new B-tree node.
252 */
253 if(H5AC_insert_entry(f, H5AC_BT, *addr_p, bt, H5AC__NO_FLAGS_SET) < 0)
254 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree root node to cache")
255 #ifdef H5B_DEBUG
256 H5B__assert(f, *addr_p, shared->type, udata);
257 #endif
258
259 done:
260 if(ret_value < 0) {
261 if(shared && shared->sizeof_rnode>0) {
262 H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
263 (void)H5MF_xfree(f, H5FD_MEM_BTREE, *addr_p, (hsize_t)shared->sizeof_rnode);
264 } /* end if */
265 if(bt)
266 /* Destroy B-tree node */
267 if(H5B__node_dest(bt) < 0)
268 HDONE_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree node")
269 } /* end if */
270
271 FUNC_LEAVE_NOAPI(ret_value)
272 } /* end H5B_create() */ /*lint !e818 Can't make udata a pointer to const */
273
274
275 /*-------------------------------------------------------------------------
276 * Function: H5B_find
277 *
278 * Purpose: Locate the specified information in a B-tree and return
279 * that information by filling in fields of the caller-supplied
280 * UDATA pointer depending on the type of leaf node
281 * requested. The UDATA can point to additional data passed
282 * to the key comparison function.
283 *
284 * Note: This function does not follow the left/right sibling
285 * pointers since it assumes that all nodes can be reached
286 * from the parent node.
287 *
288 * Return: Non-negative (TRUE/FALSE) on success (if found, values returned
289 * through the UDATA argument). Negative on failure (if not found,
290 * UDATA is undefined).
291 *
292 * Programmer: Robb Matzke
293 * matzke@llnl.gov
294 * Jun 23 1997
295 *
296 *-------------------------------------------------------------------------
297 */
298 htri_t
H5B_find(H5F_t * f,const H5B_class_t * type,haddr_t addr,void * udata)299 H5B_find(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
300 {
301 H5B_t *bt = NULL;
302 H5UC_t *rc_shared; /* Ref-counted shared info */
303 H5B_shared_t *shared; /* Pointer to shared B-tree info */
304 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
305 unsigned idx = 0, lt = 0, rt; /* Final, left & right key indices */
306 int cmp = 1; /* Key comparison value */
307 htri_t ret_value = FAIL; /* Return value */
308
309 FUNC_ENTER_NOAPI(FAIL)
310
311 /*
312 * Check arguments.
313 */
314 HDassert(f);
315 HDassert(type);
316 HDassert(type->decode);
317 HDassert(type->cmp3);
318 HDassert(type->found);
319 HDassert(H5F_addr_defined(addr));
320
321 /* Get shared info for B-tree */
322 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
323 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
324 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
325 HDassert(shared);
326
327 /*
328 * Perform a binary search to locate the child which contains
329 * the thing for which we're searching.
330 */
331 cache_udata.f = f;
332 cache_udata.type = type;
333 cache_udata.rc_shared = rc_shared;
334 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
335 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")
336
337 rt = bt->nchildren;
338 while(lt < rt && cmp) {
339 idx = (lt + rt) / 2;
340 /* compare */
341 if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, (idx + 1)))) < 0)
342 rt = idx;
343 else
344 lt = idx + 1;
345 } /* end while */
346 /* Check if not found */
347 if(cmp)
348 HGOTO_DONE(FALSE)
349
350 /*
351 * Follow the link to the subtree or to the data node.
352 */
353 HDassert(idx < bt->nchildren);
354
355 if(bt->level > 0) {
356 if((ret_value = H5B_find(f, type, bt->child[idx], udata)) < 0)
357 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in subtree")
358 } /* end if */
359 else {
360 if((ret_value = (type->found)(f, bt->child[idx], H5B_NKEY(bt, shared, idx), udata)) < 0)
361 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in leaf node")
362 } /* end else */
363
364 done:
365 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
366 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release node")
367
368 FUNC_LEAVE_NOAPI(ret_value)
369 } /* end H5B_find() */
370
371
372 /*-------------------------------------------------------------------------
373 * Function: H5B__split
374 *
375 * Purpose: Split a single node into two nodes. The old node will
376 * contain the left children and the new node will contain the
377 * right children.
378 *
379 * The UDATA pointer is passed to the sizeof_rkey() method but is
380 * otherwise unused.
381 *
382 * The BT_UD argument is a pointer to a protected B-tree
383 * node.
384 *
385 * Return: Non-negative on success (The address of the new node is
386 * returned through the NEW_ADDR argument). Negative on failure.
387 *
388 * Programmer: Robb Matzke
389 * matzke@llnl.gov
390 * Jul 3 1997
391 *
392 *-------------------------------------------------------------------------
393 */
394 static herr_t
H5B__split(H5F_t * f,H5B_ins_ud_t * bt_ud,unsigned idx,void * udata,H5B_ins_ud_t * split_bt_ud)395 H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
396 void *udata, H5B_ins_ud_t *split_bt_ud/*out*/)
397 {
398 H5B_shared_t *shared; /* Pointer to shared B-tree info */
399 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
400 unsigned nleft, nright; /* Number of keys in left & right halves */
401 double split_ratios[3]; /* B-tree split ratios */
402 herr_t ret_value = SUCCEED; /* Return value */
403
404 FUNC_ENTER_STATIC
405
406 /*
407 * Check arguments.
408 */
409 HDassert(f);
410 HDassert(bt_ud);
411 HDassert(bt_ud->bt);
412 HDassert(H5F_addr_defined(bt_ud->addr));
413 HDassert(split_bt_ud);
414 HDassert(!split_bt_ud->bt);
415
416 /*
417 * Initialize variables.
418 */
419 shared = (H5B_shared_t *)H5UC_GET_OBJ(bt_ud->bt->rc_shared);
420 HDassert(shared);
421 HDassert(bt_ud->bt->nchildren == shared->two_k);
422
423 /* Get B-tree split ratios */
424 if(H5CX_get_btree_split_ratios(split_ratios) < 0)
425 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree split ratios")
426
427 #ifdef H5B_DEBUG
428 if(H5DEBUG(B)) {
429 const char *side;
430
431 if(!H5F_addr_defined(bt_ud->bt->left) && !H5F_addr_defined(bt_ud->bt->right))
432 side = "ONLY";
433 else if(!H5F_addr_defined(bt_ud->bt->right))
434 side = "RIGHT";
435 else if(!H5F_addr_defined(bt_ud->bt->left))
436 side = "LEFT";
437 else
438 side = "MIDDLE";
439 fprintf(H5DEBUG(B), "H5B__split: %3u {%5.3f,%5.3f,%5.3f} %6s",
440 shared->two_k, split_ratios[0], split_ratios[1], split_ratios[2], side);
441 }
442 #endif
443
444 /*
445 * Decide how to split the children of the old node among the old node
446 * and the new node.
447 */
448 if(!H5F_addr_defined(bt_ud->bt->right))
449 nleft = (unsigned)((double)shared->two_k * split_ratios[2]); /*right*/
450 else if(!H5F_addr_defined(bt_ud->bt->left))
451 nleft = (unsigned)((double)shared->two_k * split_ratios[0]); /*left*/
452 else
453 nleft = (unsigned)((double)shared->two_k * split_ratios[1]); /*middle*/
454
455 /*
456 * Keep the new child in the same node as the child that split. This can
457 * result in nodes that have an unused child when data is written
458 * sequentially, but it simplifies stuff below.
459 */
460 if(idx < nleft && nleft == shared->two_k)
461 --nleft;
462 else if(idx >= nleft && 0 == nleft)
463 nleft++;
464 nright = shared->two_k - nleft;
465 #ifdef H5B_DEBUG
466 if(H5DEBUG(B))
467 fprintf(H5DEBUG(B), " split %3d/%-3d\n", nleft, nright);
468 #endif
469
470 /*
471 * Create the new B-tree node.
472 */
473 if(H5B_create(f, shared->type, udata, &split_bt_ud->addr/*out*/) < 0)
474 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create B-tree")
475 cache_udata.f = f;
476 cache_udata.type = shared->type;
477 cache_udata.rc_shared = bt_ud->bt->rc_shared;
478 if(NULL == (split_bt_ud->bt = (H5B_t *)H5AC_protect(f, H5AC_BT, split_bt_ud->addr, &cache_udata, H5AC__NO_FLAGS_SET)))
479 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree")
480 split_bt_ud->bt->level = bt_ud->bt->level;
481
482 /*
483 * Copy data from the old node to the new node.
484 */
485
486 split_bt_ud->cache_flags = H5AC__DIRTIED_FLAG;
487 HDmemcpy(split_bt_ud->bt->native,
488 bt_ud->bt->native + nleft * shared->type->sizeof_nkey,
489 (nright + 1) * shared->type->sizeof_nkey);
490 HDmemcpy(split_bt_ud->bt->child,
491 &bt_ud->bt->child[nleft],
492 nright * sizeof(haddr_t));
493
494 split_bt_ud->bt->nchildren = nright;
495
496 /*
497 * Truncate the old node.
498 */
499 bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
500 bt_ud->bt->nchildren = nleft;
501
502 /*
503 * Update other sibling pointers.
504 */
505 split_bt_ud->bt->left = bt_ud->addr;
506 split_bt_ud->bt->right = bt_ud->bt->right;
507
508 if(H5F_addr_defined(bt_ud->bt->right)) {
509 H5B_t *tmp_bt;
510
511 if(NULL == (tmp_bt = (H5B_t *)H5AC_protect(f, H5AC_BT, bt_ud->bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
512 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load right sibling")
513
514 tmp_bt->left = split_bt_ud->addr;
515
516 if(H5AC_unprotect(f, H5AC_BT, bt_ud->bt->right, tmp_bt, H5AC__DIRTIED_FLAG) < 0)
517 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
518 } /* end if */
519
520 bt_ud->bt->right = split_bt_ud->addr;
521 HDassert(bt_ud->cache_flags & H5AC__DIRTIED_FLAG);
522
523 done:
524 if(ret_value < 0) {
525 if(split_bt_ud->bt && H5AC_unprotect(f, H5AC_BT, split_bt_ud->addr, split_bt_ud->bt, split_bt_ud->cache_flags) < 0)
526 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
527 split_bt_ud->bt = NULL;
528 split_bt_ud->addr = HADDR_UNDEF;
529 split_bt_ud->cache_flags = H5AC__NO_FLAGS_SET;
530 } /* end if */
531
532 FUNC_LEAVE_NOAPI(ret_value)
533 } /* end H5B__split() */
534
535
536 /*-------------------------------------------------------------------------
537 * Function: H5B_insert
538 *
539 * Purpose: Adds a new item to the B-tree.
540 *
541 * Return: Non-negative on success/Negative on failure
542 *
543 * Programmer: Robb Matzke
544 * matzke@llnl.gov
545 * Jun 23 1997
546 *
547 *-------------------------------------------------------------------------
548 */
549 herr_t
H5B_insert(H5F_t * f,const H5B_class_t * type,haddr_t addr,void * udata)550 H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
551 {
552 /*
553 * These are defined this way to satisfy alignment constraints.
554 */
555 uint64_t _lt_key[128], _md_key[128], _rt_key[128];
556 uint8_t *lt_key=(uint8_t*)_lt_key;
557 uint8_t *md_key=(uint8_t*)_md_key;
558 uint8_t *rt_key=(uint8_t*)_rt_key;
559
560 hbool_t lt_key_changed = FALSE, rt_key_changed = FALSE;
561 haddr_t old_root_addr = HADDR_UNDEF;
562 unsigned level;
563 H5B_ins_ud_t bt_ud = H5B_INS_UD_T_NULL; /* (Old) root node */
564 H5B_ins_ud_t split_bt_ud = H5B_INS_UD_T_NULL; /* Split B-tree node */
565 H5B_t *new_root_bt = NULL; /* New root node */
566 H5UC_t *rc_shared; /* Ref-counted shared info */
567 H5B_shared_t *shared; /* Pointer to shared B-tree info */
568 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
569 H5B_ins_t my_ins = H5B_INS_ERROR;
570 herr_t ret_value = SUCCEED;
571
572 FUNC_ENTER_NOAPI(FAIL)
573
574 /* Check arguments. */
575 HDassert(f);
576 HDassert(type);
577 HDassert(type->sizeof_nkey <= sizeof _lt_key);
578 HDassert(H5F_addr_defined(addr));
579
580 /* Get shared info for B-tree */
581 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
582 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
583 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
584 HDassert(shared);
585
586 /* Protect the root node */
587 cache_udata.f = f;
588 cache_udata.type = type;
589 cache_udata.rc_shared = rc_shared;
590 bt_ud.addr = addr;
591 if(NULL == (bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
592 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to locate root of B-tree")
593
594 /* Insert the object */
595 if((int)(my_ins = H5B__insert_helper(f, &bt_ud, type, lt_key,
596 <_key_changed, md_key, udata, rt_key, &rt_key_changed,
597 &split_bt_ud/*out*/)) < 0)
598 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to insert key")
599
600 /* Check if the root node split */
601 if(H5B_INS_NOOP == my_ins) {
602 /* The root node did not split - just return */
603 HDassert(!split_bt_ud.bt);
604 HGOTO_DONE(SUCCEED)
605 } /* end if */
606 HDassert(H5B_INS_RIGHT == my_ins);
607 HDassert(split_bt_ud.bt);
608 HDassert(H5F_addr_defined(split_bt_ud.addr));
609
610 /* Get level of old root */
611 level = bt_ud.bt->level;
612
613 /* update left and right keys */
614 if(!lt_key_changed)
615 HDmemcpy(lt_key, H5B_NKEY(bt_ud.bt,shared,0), type->sizeof_nkey);
616 if(!rt_key_changed)
617 HDmemcpy(rt_key, H5B_NKEY(split_bt_ud.bt,shared,split_bt_ud.bt->nchildren), type->sizeof_nkey);
618
619 /*
620 * Copy the old root node to some other file location and make the new root
621 * at the old root's previous address. This prevents the B-tree from
622 * "moving".
623 */
624 H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
625 if(HADDR_UNDEF == (old_root_addr = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
626 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "unable to allocate file space to move root")
627
628 /*
629 * Move the node to the new location
630 */
631
632 /* Make a copy of the old root information */
633 if(NULL == (new_root_bt = H5B__copy(bt_ud.bt)))
634 HGOTO_ERROR(H5E_BTREE, H5E_CANTCOPY, FAIL, "unable to copy old root")
635
636 /* Unprotect the old root so we can move it. Also force it to be marked
637 * dirty so it is written to the new location. */
638 if(H5AC_unprotect(f, H5AC_BT, bt_ud.addr, bt_ud.bt, H5AC__DIRTIED_FLAG) < 0)
639 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release old root")
640 bt_ud.bt = NULL; /* Make certain future references will be caught */
641
642 /* Move the location of the old root on the disk */
643 if(H5AC_move_entry(f, H5AC_BT, bt_ud.addr, old_root_addr) < 0)
644 HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to move B-tree root node")
645 bt_ud.addr = old_root_addr;
646
647 /* Update the split b-tree's left pointer to point to the new location */
648 split_bt_ud.bt->left = bt_ud.addr;
649 split_bt_ud.cache_flags |= H5AC__DIRTIED_FLAG;
650
651 /* clear the old root info at the old address (we already copied it) */
652 new_root_bt->left = HADDR_UNDEF;
653 new_root_bt->right = HADDR_UNDEF;
654
655 /* Set the new information for the copy */
656 new_root_bt->level = level + 1;
657 new_root_bt->nchildren = 2;
658
659 new_root_bt->child[0] = bt_ud.addr;
660 HDmemcpy(H5B_NKEY(new_root_bt, shared, 0), lt_key, shared->type->sizeof_nkey);
661
662 new_root_bt->child[1] = split_bt_ud.addr;
663 HDmemcpy(H5B_NKEY(new_root_bt, shared, 1), md_key, shared->type->sizeof_nkey);
664 HDmemcpy(H5B_NKEY(new_root_bt, shared, 2), rt_key, shared->type->sizeof_nkey);
665
666 /* Insert the modified copy of the old root into the file again */
667 if(H5AC_insert_entry(f, H5AC_BT, addr, new_root_bt, H5AC__NO_FLAGS_SET) < 0)
668 HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to add old B-tree root node to cache")
669
670 done:
671 if(ret_value < 0)
672 if(new_root_bt && H5B__node_dest(new_root_bt) < 0)
673 HDONE_ERROR(H5E_BTREE, H5E_CANTRELEASE, FAIL, "unable to free B-tree root node");
674
675 if(bt_ud.bt)
676 if(H5AC_unprotect(f, H5AC_BT, bt_ud.addr, bt_ud.bt, bt_ud.cache_flags) < 0)
677 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to unprotect old root")
678
679 if(split_bt_ud.bt)
680 if(H5AC_unprotect(f, H5AC_BT, split_bt_ud.addr, split_bt_ud.bt, split_bt_ud.cache_flags) < 0)
681 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to unprotect new child")
682
683 #ifdef H5B_DEBUG
684 if(ret_value >= 0)
685 H5B__assert(f, addr, type, udata);
686 #endif
687
688 FUNC_LEAVE_NOAPI(ret_value)
689 } /* end H5B_insert() */
690
691
692 /*-------------------------------------------------------------------------
693 * Function: H5B__insert_child
694 *
695 * Purpose: Insert a child to the left or right of child[IDX] depending
696 * on whether ANCHOR is H5B_INS_LEFT or H5B_INS_RIGHT. The BT
697 * argument is a pointer to a protected B-tree node.
698 *
699 * Return: Non-negative on success/Negative on failure
700 *
701 * Programmer: Robb Matzke
702 * matzke@llnl.gov
703 * Jul 8 1997
704 *
705 *-------------------------------------------------------------------------
706 */
707 static herr_t
H5B__insert_child(H5B_t * bt,unsigned * bt_flags,unsigned idx,haddr_t child,H5B_ins_t anchor,const void * md_key)708 H5B__insert_child(H5B_t *bt, unsigned *bt_flags, unsigned idx,
709 haddr_t child, H5B_ins_t anchor, const void *md_key)
710 {
711 H5B_shared_t *shared; /* Pointer to shared B-tree info */
712 uint8_t *base; /* Base offset for move */
713
714 FUNC_ENTER_STATIC_NOERR
715
716 HDassert(bt);
717 HDassert(bt_flags);
718 HDassert(H5F_addr_defined(child));
719 shared = (H5B_shared_t *)H5UC_GET_OBJ(bt->rc_shared);
720 HDassert(shared);
721 HDassert(bt->nchildren < shared->two_k);
722
723 /* Check for inserting right-most key into node (common when just appending
724 * records to an unlimited dimension chunked dataset)
725 */
726 base = H5B_NKEY(bt, shared, (idx + 1));
727 if((idx + 1) == bt->nchildren) {
728 /* Make room for the new key */
729 HDmemcpy(base + shared->type->sizeof_nkey, base,
730 shared->type->sizeof_nkey); /* No overlap possible - memcpy() OK */
731 HDmemcpy(base, md_key, shared->type->sizeof_nkey);
732
733 /* The MD_KEY is the left key of the new node */
734 if(H5B_INS_RIGHT == anchor)
735 idx++; /* Don't have to memmove() child addresses down, just add new child */
736 else
737 /* Make room for the new child address */
738 bt->child[idx + 1] = bt->child[idx];
739 } /* end if */
740 else {
741 /* Make room for the new key */
742 HDmemmove(base + shared->type->sizeof_nkey, base,
743 (bt->nchildren - idx) * shared->type->sizeof_nkey);
744 HDmemcpy(base, md_key, shared->type->sizeof_nkey);
745
746 /* The MD_KEY is the left key of the new node */
747 if(H5B_INS_RIGHT == anchor)
748 idx++;
749
750 /* Make room for the new child address */
751 HDmemmove(bt->child + idx + 1, bt->child + idx,
752 (bt->nchildren - idx) * sizeof(haddr_t));
753 } /* end if */
754
755 bt->child[idx] = child;
756 bt->nchildren += 1;
757
758 /* Mark node as dirty */
759 *bt_flags |= H5AC__DIRTIED_FLAG;
760
761 FUNC_LEAVE_NOAPI(SUCCEED)
762 } /* end H5B_insert_child() */
763
764
765 /*-------------------------------------------------------------------------
766 * Function: H5B__insert_helper
767 *
768 * Purpose: Inserts the item UDATA into the tree rooted at ADDR and having
769 * the specified type.
770 *
771 * On return, if LT_KEY_CHANGED is non-zero, then LT_KEY is
772 * the new native left key. Similarly for RT_KEY_CHANGED
773 * and RT_KEY.
774 *
775 * If the node splits, then MD_KEY contains the key that
776 * was split between the two nodes (that is, the key that
777 * appears as the max key in the left node and the min key
778 * in the right node).
779 *
780 * Return: Success: A B-tree operation. The address of the new
781 * node, if the node splits, is returned through
782 * the NEW_NODE_P argument. The new node is always
783 * to the right of the previous node. This
784 * function is called recursively and the return
785 * value influences the behavior of the caller.
786 * See also, declaration of H5B_ins_t.
787 *
788 * Failure: H5B_INS_ERROR
789 *
790 * Programmer: Robb Matzke
791 * matzke@llnl.gov
792 * Jul 9 1997
793 *
794 *-------------------------------------------------------------------------
795 */
796 static H5B_ins_t
H5B__insert_helper(H5F_t * f,H5B_ins_ud_t * bt_ud,const H5B_class_t * type,uint8_t * lt_key,hbool_t * lt_key_changed,uint8_t * md_key,void * udata,uint8_t * rt_key,hbool_t * rt_key_changed,H5B_ins_ud_t * split_bt_ud)797 H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
798 uint8_t *lt_key, hbool_t *lt_key_changed, uint8_t *md_key, void *udata,
799 uint8_t *rt_key, hbool_t *rt_key_changed, H5B_ins_ud_t *split_bt_ud/*out*/)
800 {
801 H5B_t *bt; /* Convenience pointer to B-tree */
802 H5UC_t *rc_shared; /* Ref-counted shared info */
803 H5B_shared_t *shared; /* Pointer to shared B-tree info */
804 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
805 unsigned lt = 0, idx = 0, rt; /* Left, final & right index values */
806 int cmp = -1; /* Key comparison value */
807 H5B_ins_ud_t child_bt_ud = H5B_INS_UD_T_NULL; /* Child B-tree */
808 H5B_ins_ud_t new_child_bt_ud = H5B_INS_UD_T_NULL; /* Newly split child B-tree */
809 H5B_ins_t my_ins = H5B_INS_ERROR;
810 H5B_ins_t ret_value = H5B_INS_ERROR; /* Return value */
811
812 FUNC_ENTER_STATIC
813
814 /*
815 * Check arguments
816 */
817 HDassert(f);
818 HDassert(bt_ud);
819 HDassert(bt_ud->bt);
820 HDassert(H5F_addr_defined(bt_ud->addr));
821 HDassert(type);
822 HDassert(type->decode);
823 HDassert(type->cmp3);
824 HDassert(type->new_node);
825 HDassert(lt_key);
826 HDassert(lt_key_changed);
827 HDassert(rt_key);
828 HDassert(rt_key_changed);
829 HDassert(split_bt_ud);
830 HDassert(!split_bt_ud->bt);
831 HDassert(!H5F_addr_defined(split_bt_ud->addr));
832 HDassert(split_bt_ud->cache_flags == H5AC__NO_FLAGS_SET);
833
834 bt = bt_ud->bt;
835
836 *lt_key_changed = FALSE;
837 *rt_key_changed = FALSE;
838
839 /* Get shared info for B-tree */
840 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
841 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
842 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
843 HDassert(shared);
844
845 /*
846 * Use a binary search to find the child that will receive the new
847 * data. When the search completes IDX points to the child that
848 * should get the new data.
849 */
850 rt = bt->nchildren;
851
852 while(lt < rt && cmp) {
853 idx = (lt + rt) / 2;
854 if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
855 rt = idx;
856 else
857 lt = idx + 1;
858 } /* end while */
859
860 /* Set up user data for cache callbacks */
861 cache_udata.f = f;
862 cache_udata.type = type;
863 cache_udata.rc_shared = rc_shared;
864
865 if(0 == bt->nchildren) {
866 /*
867 * The value being inserted will be the only value in this tree. We
868 * must necessarily be at level zero.
869 */
870 HDassert(0 == bt->level);
871 if((type->new_node)(f, H5B_INS_FIRST, H5B_NKEY(bt, shared, 0), udata,
872 H5B_NKEY(bt, shared, 1), bt->child + 0/*out*/) < 0)
873 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, H5B_INS_ERROR, "unable to create leaf node")
874 bt->nchildren = 1;
875 bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
876 idx = 0;
877
878 if(type->follow_min) {
879 if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
880 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
881 rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
882 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "unable to insert first leaf node")
883 } /* end if */
884 else
885 my_ins = H5B_INS_NOOP;
886 } else if(cmp < 0 && idx == 0) {
887 if(bt->level > 0) {
888 /*
889 * The value being inserted is less than any value in this tree.
890 * Follow the minimum branch out of this node to a subtree.
891 */
892 child_bt_ud.addr = bt->child[idx];
893 if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
894 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")
895
896 if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
897 H5B_NKEY(bt,shared,idx), lt_key_changed, md_key,
898 udata, H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
899 &new_child_bt_ud/*out*/)) < 0)
900 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum subtree")
901 } else if(type->follow_min) {
902 /*
903 * The value being inserted is less than any leaf node out of this
904 * current node. Follow the minimum branch to a leaf node and let
905 * the subclass handle the problem.
906 */
907 if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
908 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
909 rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
910 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
911 } else {
912 /*
913 * The value being inserted is less than any leaf node out of the
914 * current node. Create a new minimum leaf node out of this B-tree
915 * node. This node is not empty (handled above).
916 */
917 my_ins = H5B_INS_LEFT;
918 HDmemcpy(md_key, H5B_NKEY(bt,shared,idx), type->sizeof_nkey);
919 if((type->new_node)(f, H5B_INS_LEFT, H5B_NKEY(bt, shared, idx), udata,
920 md_key, &new_child_bt_ud.addr/*out*/) < 0)
921 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
922 *lt_key_changed = TRUE;
923 } /* end else */
924
925 #ifdef H5_STRICT_FORMAT_CHECKS
926 /* Since we are to the left of the leftmost key there must not be a left
927 * sibling */
928 if(H5F_addr_defined(bt->left))
929 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
930 #endif /* H5_STRICT_FORMAT_CHECKS */
931 } else if(cmp > 0 && idx + 1 >= bt->nchildren) {
932 if (bt->level > 0) {
933 /*
934 * The value being inserted is larger than any value in this tree.
935 * Follow the maximum branch out of this node to a subtree.
936 */
937 idx = bt->nchildren - 1;
938 child_bt_ud.addr = bt->child[idx];
939 if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
940 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")
941
942 if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
943 H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
944 H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
945 &new_child_bt_ud/*out*/)) < 0)
946 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum subtree")
947 } else if(type->follow_max) {
948 /*
949 * The value being inserted is larger than any leaf node out of the
950 * current node. Follow the maximum branch to a leaf node and let
951 * the subclass handle the problem.
952 */
953 idx = bt->nchildren - 1;
954 if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
955 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
956 rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
957 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
958 } else {
959 /*
960 * The value being inserted is larger than any leaf node out of the
961 * current node. Create a new maximum leaf node out of this B-tree
962 * node.
963 */
964 idx = bt->nchildren - 1;
965 my_ins = H5B_INS_RIGHT;
966 HDmemcpy(md_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
967 if((type->new_node)(f, H5B_INS_RIGHT, md_key, udata,
968 H5B_NKEY(bt, shared, idx + 1), &new_child_bt_ud.addr/*out*/) < 0)
969 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
970 *rt_key_changed = TRUE;
971 } /* end else */
972
973 #ifdef H5_STRICT_FORMAT_CHECKS
974 /* Since we are to the right of the rightmost key there must not be a
975 * right sibling */
976 if(H5F_addr_defined(bt->right))
977 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
978 #endif /* H5_STRICT_FORMAT_CHECKS */
979 } else if(cmp) {
980 /*
981 * We couldn't figure out which branch to follow out of this node. THIS
982 * IS A MAJOR PROBLEM THAT NEEDS TO BE FIXED --rpm.
983 */
984 HDassert("INTERNAL HDF5 ERROR (contact rpm)" && 0);
985 #ifdef NDEBUG
986 HDabort();
987 #endif /* NDEBUG */
988 } else if(bt->level > 0) {
989 /*
990 * Follow a branch out of this node to another subtree.
991 */
992 HDassert(idx < bt->nchildren);
993 child_bt_ud.addr = bt->child[idx];
994 if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
995 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")
996
997 if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
998 H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
999 H5B_NKEY(bt, shared, idx + 1), rt_key_changed, &new_child_bt_ud/*out*/)) < 0)
1000 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert subtree")
1001 } else {
1002 /*
1003 * Follow a branch out of this node to a leaf node of some other type.
1004 */
1005 HDassert(idx < bt->nchildren);
1006 if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
1007 lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
1008 rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
1009 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert leaf node")
1010 }
1011 HDassert((int)my_ins >= 0);
1012
1013 /*
1014 * Update the left and right keys of the current node.
1015 */
1016 if(*lt_key_changed) {
1017 bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
1018 if(idx > 0) {
1019 HDassert(type->critical_key == H5B_LEFT);
1020 HDassert(!(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins));
1021 *lt_key_changed = FALSE;
1022 } /* end if */
1023 else
1024 HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
1025 } /* end if */
1026 if(*rt_key_changed) {
1027 bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
1028 if(idx + 1 < bt->nchildren) {
1029 HDassert(type->critical_key == H5B_RIGHT);
1030 HDassert(!(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins));
1031 *rt_key_changed = FALSE;
1032 } /* end if */
1033 else
1034 HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
1035 } /* end if */
1036
1037 /*
1038 * Handle changes/additions to children
1039 */
1040 HDassert(!(bt->level == 0) != !(child_bt_ud.bt));
1041 if(H5B_INS_CHANGE == my_ins) {
1042 /*
1043 * The insertion simply changed the address for the child.
1044 */
1045 HDassert(!child_bt_ud.bt);
1046 HDassert(bt->level == 0);
1047 bt->child[idx] = new_child_bt_ud.addr;
1048 bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
1049 } else if(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins) {
1050 unsigned *tmp_bt_flags_ptr = NULL;
1051 H5B_t *tmp_bt;
1052
1053 /*
1054 * If this node is full then split it before inserting the new child.
1055 */
1056 if(bt->nchildren == shared->two_k) {
1057 if(H5B__split(f, bt_ud, idx, udata, split_bt_ud/*out*/) < 0)
1058 HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, H5B_INS_ERROR, "unable to split node")
1059 if(idx < bt->nchildren) {
1060 tmp_bt = bt;
1061 tmp_bt_flags_ptr = &bt_ud->cache_flags;
1062 } else {
1063 idx -= bt->nchildren;
1064 tmp_bt = split_bt_ud->bt;
1065 tmp_bt_flags_ptr = &split_bt_ud->cache_flags;
1066 }
1067 } /* end if */
1068 else {
1069 tmp_bt = bt;
1070 tmp_bt_flags_ptr = &bt_ud->cache_flags;
1071 } /* end else */
1072
1073 /* Insert the child */
1074 if(H5B__insert_child(tmp_bt, tmp_bt_flags_ptr, idx, new_child_bt_ud.addr, my_ins, md_key) < 0)
1075 HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert child")
1076 } /* end else-if */
1077
1078 /*
1079 * If this node split, return the mid key (the one that is shared
1080 * by the left and right node).
1081 */
1082 if(split_bt_ud->bt) {
1083 HDmemcpy(md_key, H5B_NKEY(split_bt_ud->bt, shared, 0), type->sizeof_nkey);
1084 ret_value = H5B_INS_RIGHT;
1085 #ifdef H5B_DEBUG
1086 /*
1087 * The max key in the original left node must be equal to the min key
1088 * in the new node.
1089 */
1090 cmp = (type->cmp2)(H5B_NKEY(bt, shared, bt->nchildren), udata,
1091 H5B_NKEY(split_bt_ud->bt, shared, 0));
1092 HDassert(0 == cmp);
1093 #endif
1094 } /* end if */
1095 else
1096 ret_value = H5B_INS_NOOP;
1097
1098 done:
1099 if(child_bt_ud.bt)
1100 if(H5AC_unprotect(f, H5AC_BT, child_bt_ud.addr, child_bt_ud.bt, child_bt_ud.cache_flags) < 0)
1101 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to unprotect child")
1102
1103 if(new_child_bt_ud.bt)
1104 if(H5AC_unprotect(f, H5AC_BT, new_child_bt_ud.addr, new_child_bt_ud.bt, new_child_bt_ud.cache_flags) < 0)
1105 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to unprotect new child")
1106
1107 FUNC_LEAVE_NOAPI(ret_value)
1108 } /* end H5B_insert_helper() */
1109
1110
1111 /*-------------------------------------------------------------------------
1112 * Function: H5B__iterate_helper
1113 *
1114 * Purpose: Calls the list callback for each leaf node of the
1115 * B-tree, passing it the caller's UDATA structure.
1116 *
1117 * Return: Non-negative on success/Negative on failure
1118 *
1119 * Programmer: Robb Matzke
1120 * matzke@llnl.gov
1121 * Jun 23 1997
1122 *
1123 *-------------------------------------------------------------------------
1124 */
1125 static herr_t
H5B__iterate_helper(H5F_t * f,const H5B_class_t * type,haddr_t addr,H5B_operator_t op,void * udata)1126 H5B__iterate_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
1127 H5B_operator_t op, void *udata)
1128 {
1129 H5B_t *bt = NULL; /* Pointer to current B-tree node */
1130 H5UC_t *rc_shared; /* Ref-counted shared info */
1131 H5B_shared_t *shared; /* Pointer to shared B-tree info */
1132 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
1133 unsigned u; /* Local index variable */
1134 herr_t ret_value = H5_ITER_CONT; /* Return value */
1135
1136 FUNC_ENTER_STATIC
1137
1138 /*
1139 * Check arguments.
1140 */
1141 HDassert(f);
1142 HDassert(type);
1143 HDassert(H5F_addr_defined(addr));
1144 HDassert(op);
1145 HDassert(udata);
1146
1147 /* Get shared info for B-tree */
1148 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
1149 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
1150 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
1151 HDassert(shared);
1152
1153 /* Protect the initial/current node */
1154 cache_udata.f = f;
1155 cache_udata.type = type;
1156 cache_udata.rc_shared = rc_shared;
1157 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
1158 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5_ITER_ERROR, "unable to load B-tree node")
1159
1160 /* Iterate over node's children */
1161 for(u = 0; u < bt->nchildren && ret_value == H5_ITER_CONT; u++) {
1162 if(bt->level > 0)
1163 ret_value = H5B__iterate_helper(f, type, bt->child[u], op, udata);
1164 else
1165 ret_value = (*op)(f, H5B_NKEY(bt, shared, u), bt->child[u], H5B_NKEY(bt, shared, u + 1), udata);
1166 if(ret_value < 0)
1167 HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");
1168 } /* end for */
1169
1170 done:
1171 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
1172 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5_ITER_ERROR, "unable to release B-tree node")
1173
1174 FUNC_LEAVE_NOAPI(ret_value)
1175 } /* end H5B__iterate_helper() */
1176
1177
1178 /*-------------------------------------------------------------------------
1179 * Function: H5B_iterate
1180 *
1181 * Purpose: Calls the list callback for each leaf node of the
1182 * B-tree, passing it the UDATA structure.
1183 *
1184 * Return: Non-negative on success/Negative on failure
1185 *
1186 * Programmer: Robb Matzke
1187 * matzke@llnl.gov
1188 * Jun 23 1997
1189 *
1190 *-------------------------------------------------------------------------
1191 */
1192 herr_t
H5B_iterate(H5F_t * f,const H5B_class_t * type,haddr_t addr,H5B_operator_t op,void * udata)1193 H5B_iterate(H5F_t *f, const H5B_class_t *type, haddr_t addr,
1194 H5B_operator_t op, void *udata)
1195 {
1196 herr_t ret_value = FAIL; /* Return value */
1197
1198 FUNC_ENTER_NOAPI_NOERR
1199
1200 /*
1201 * Check arguments.
1202 */
1203 HDassert(f);
1204 HDassert(type);
1205 HDassert(H5F_addr_defined(addr));
1206 HDassert(op);
1207 HDassert(udata);
1208
1209 /* Iterate over the B-tree records */
1210 if((ret_value = H5B__iterate_helper(f, type, addr, op, udata)) < 0)
1211 HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");
1212
1213 FUNC_LEAVE_NOAPI(ret_value)
1214 } /* end H5B_iterate() */
1215
1216
1217 /*-------------------------------------------------------------------------
1218 * Function: H5B__remove_helper
1219 *
1220 * Purpose: The recursive part of removing an item from a B-tree. The
1221 * sub B-tree that is being considered is located at ADDR and
1222 * the item to remove is described by UDATA. If the removed
1223 * item falls at the left or right end of the current level then
1224 * it might be necessary to adjust the left and/or right keys
1225 * (LT_KEY and/or RT_KEY) to to indicate that they changed by
1226 * setting LT_KEY_CHANGED and/or RT_KEY_CHANGED.
1227 *
1228 * Return: Success: A B-tree operation, see comments for
1229 * H5B_ins_t declaration. This function is
1230 * called recursively and the return value
1231 * influences the actions of the caller. It is
1232 * also called by H5B_remove().
1233 *
1234 * Failure: H5B_INS_ERROR, a negative value.
1235 *
1236 * Programmer: Robb Matzke
1237 * Wednesday, September 16, 1998
1238 *
1239 *-------------------------------------------------------------------------
1240 */
1241 static H5B_ins_t
H5B__remove_helper(H5F_t * f,haddr_t addr,const H5B_class_t * type,int level,uint8_t * lt_key,hbool_t * lt_key_changed,void * udata,uint8_t * rt_key,hbool_t * rt_key_changed)1242 H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
1243 uint8_t *lt_key/*out*/, hbool_t *lt_key_changed/*out*/, void *udata,
1244 uint8_t *rt_key/*out*/, hbool_t *rt_key_changed/*out*/)
1245 {
1246 H5B_t *bt = NULL, *sibling = NULL;
1247 unsigned bt_flags = H5AC__NO_FLAGS_SET;
1248 H5UC_t *rc_shared; /* Ref-counted shared info */
1249 H5B_shared_t *shared; /* Pointer to shared B-tree info */
1250 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
1251 unsigned idx = 0, lt = 0, rt; /* Final, left & right indices */
1252 int cmp = 1; /* Key comparison value */
1253 H5B_ins_t ret_value = H5B_INS_ERROR;
1254
1255 FUNC_ENTER_STATIC
1256
1257 HDassert(f);
1258 HDassert(H5F_addr_defined(addr));
1259 HDassert(type);
1260 HDassert(type->decode);
1261 HDassert(type->cmp3);
1262 HDassert(lt_key && lt_key_changed);
1263 HDassert(udata);
1264 HDassert(rt_key && rt_key_changed);
1265
1266 /* Get shared info for B-tree */
1267 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
1268 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
1269 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
1270 HDassert(shared);
1271
1272 /*
1273 * Perform a binary search to locate the child which contains the thing
1274 * for which we're searching.
1275 */
1276 cache_udata.f = f;
1277 cache_udata.type = type;
1278 cache_udata.rc_shared = rc_shared;
1279 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
1280 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load B-tree node")
1281
1282 rt = bt->nchildren;
1283 while(lt < rt && cmp) {
1284 idx = (lt + rt) / 2;
1285 if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
1286 rt = idx;
1287 else
1288 lt = idx + 1;
1289 } /* end while */
1290 if(cmp)
1291 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "B-tree key not found")
1292
1293 /*
1294 * Follow the link to the subtree or to the data node. The return value
1295 * will be one of H5B_INS_ERROR, H5B_INS_NOOP, or H5B_INS_REMOVE.
1296 */
1297 HDassert(idx < bt->nchildren);
1298 if(bt->level > 0) {
1299 /* We're at an internal node -- call recursively */
1300 if((int)(ret_value = H5B__remove_helper(f, bt->child[idx], type,
1301 level + 1, H5B_NKEY(bt, shared, idx)/*out*/,
1302 lt_key_changed/*out*/, udata, H5B_NKEY(bt, shared, idx + 1)/*out*/,
1303 rt_key_changed/*out*/)) < 0)
1304 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in subtree")
1305 } else if(type->remove) {
1306 /*
1307 * We're at a leaf node but the leaf node points to an object that
1308 * has a removal method. Pass the removal request to the pointed-to
1309 * object and let it decide how to progress.
1310 */
1311 if((int)(ret_value = (type->remove)(f, bt->child[idx],
1312 H5B_NKEY(bt, shared, idx), lt_key_changed, udata,
1313 H5B_NKEY(bt, shared, idx + 1), rt_key_changed)) < 0)
1314 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in leaf node")
1315 } else {
1316 /*
1317 * We're at a leaf node which points to an object that has no removal
1318 * method. The best we can do is to leave the object alone but
1319 * remove the B-tree reference to the object.
1320 */
1321 *lt_key_changed = FALSE;
1322 *rt_key_changed = FALSE;
1323 ret_value = H5B_INS_REMOVE;
1324 }
1325
1326 /*
1327 * Update left and right key dirty bits if the subtree indicates that they
1328 * have changed. If the subtree's left key changed and the subtree is the
1329 * left-most child of the current node then we must update the key in our
1330 * parent and indicate that it changed. Similarly, if the right subtree
1331 * key changed and it's the right most key of this node we must update
1332 * our right key and indicate that it changed.
1333 */
1334 if(*lt_key_changed) {
1335 HDassert(type->critical_key == H5B_LEFT);
1336 bt_flags |= H5AC__DIRTIED_FLAG;
1337
1338 if(idx > 0)
1339 /* Don't propagate change out of this B-tree node */
1340 *lt_key_changed = FALSE;
1341 else
1342 HDmemcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
1343 } /* end if */
1344 if(*rt_key_changed) {
1345 HDassert(type->critical_key == H5B_RIGHT);
1346 bt_flags |= H5AC__DIRTIED_FLAG;
1347 if(idx + 1 < bt->nchildren)
1348 /* Don't propagate change out of this B-tree node */
1349 *rt_key_changed = FALSE;
1350 else
1351 HDmemcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
1352 } /* end if */
1353
1354 /*
1355 * If the subtree returned H5B_INS_REMOVE then we should remove the
1356 * subtree entry from the current node. There are four cases:
1357 */
1358 if(H5B_INS_REMOVE == ret_value) {
1359 /* Clients should not change keys when a node is removed. This function
1360 * will handle it as appropriate, based on the value of bt->critical_key
1361 */
1362 HDassert(!(*lt_key_changed));
1363 HDassert(!(*rt_key_changed));
1364
1365 if(1 == bt->nchildren) {
1366 /*
1367 * The subtree is the only child of this node. Discard both
1368 * keys and the subtree pointer. Free this node (unless it's the
1369 * root node) and return H5B_INS_REMOVE.
1370 */
1371 /* Only delete the node if it is not the root node. Note that this
1372 * "level" is the opposite of bt->level */
1373 if(level > 0) {
1374 /* Fix siblings, making sure that the keys remain consistent
1375 * between siblings. Overwrite the key that that is not
1376 * "critical" for any child in its node to maintain this
1377 * consistency (and avoid breaking key/child consistency) */
1378 if(H5F_addr_defined(bt->left)) {
1379 if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->left, &cache_udata, H5AC__NO_FLAGS_SET)))
1380 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node from tree")
1381
1382 /* Copy right-most key from deleted node to right-most key
1383 * in its left neighbor, but only if it is not the critical
1384 * key for the right-most child of the left neighbor */
1385 if(type->critical_key == H5B_LEFT)
1386 HDmemcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
1387 H5B_NKEY(bt, shared, 1), type->sizeof_nkey);
1388
1389 sibling->right = bt->right;
1390
1391 if(H5AC_unprotect(f, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
1392 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
1393 sibling = NULL; /* Make certain future references will be caught */
1394 } /* end if */
1395 if(H5F_addr_defined(bt->right)) {
1396 if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
1397 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")
1398
1399 /* Copy left-most key from deleted node to left-most key in
1400 * its right neighbor, but only if it is not the critical
1401 * key for the left-most child of the right neighbor */
1402 if(type->critical_key == H5B_RIGHT)
1403 HDmemcpy(H5B_NKEY(sibling, shared, 0),
1404 H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
1405
1406 sibling->left = bt->left;
1407
1408 if(H5AC_unprotect(f, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
1409 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
1410 sibling = NULL; /* Make certain future references will be caught */
1411 } /* end if */
1412
1413 /* Update bt struct */
1414 bt->left = HADDR_UNDEF;
1415 bt->right = HADDR_UNDEF;
1416 bt->nchildren = 0;
1417
1418 /* Delete the node from disk (via the metadata cache) */
1419 bt_flags |= H5AC__DIRTIED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
1420 H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t);
1421 if(H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG) < 0) {
1422 bt = NULL;
1423 bt_flags = H5AC__NO_FLAGS_SET;
1424 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to free B-tree node")
1425 } /* end if */
1426 bt = NULL;
1427 bt_flags = H5AC__NO_FLAGS_SET;
1428 } else {
1429 /* We removed the last child in the root node, set the level
1430 * back to 0 (as well as nchildren) */
1431 bt->nchildren = 0;
1432 bt->level = 0;
1433 bt_flags |= H5AC__DIRTIED_FLAG;
1434 } /* end else */
1435 } else if(0 == idx) {
1436 /*
1437 * The subtree is the left-most child of this node. We update the
1438 * key and child arrays and lt_key as appropriate, depending on the
1439 * status of bt->critical_key. Return H5B_INS_NOOP.
1440 */
1441 if(type->critical_key == H5B_LEFT) {
1442 /* Slide all keys down 1, update lt_key */
1443 HDmemmove(H5B_NKEY(bt, shared, 0), H5B_NKEY(bt, shared, 1),
1444 bt->nchildren * type->sizeof_nkey);
1445 HDmemcpy(lt_key, H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
1446 *lt_key_changed = TRUE;
1447 } else
1448 /* Slide all but the leftmost 2 keys down, leaving the leftmost
1449 * key intact (the right key of the leftmost child is
1450 * overwritten) */
1451 HDmemmove(H5B_NKEY(bt, shared, 1), H5B_NKEY(bt, shared, 2),
1452 (bt->nchildren - 1) * type->sizeof_nkey);
1453
1454 HDmemmove(bt->child,
1455 bt->child + 1,
1456 (bt->nchildren - 1) * sizeof(haddr_t));
1457
1458 bt->nchildren -= 1;
1459 bt_flags |= H5AC__DIRTIED_FLAG;
1460 ret_value = H5B_INS_NOOP;
1461 } else if(idx + 1 == bt->nchildren) {
1462 /*
1463 * The subtree is the right-most child of this node. We update the
1464 * key and child arrays and rt_key as appropriate, depending on the
1465 * status of bt->critical_key. Return H5B_INS_NOOP.
1466 */
1467 if(type->critical_key == H5B_LEFT)
1468 /* Slide the rightmost key down one, overwriting the left key of
1469 * the deleted (righmost) child */
1470 HDmemmove(H5B_NKEY(bt, shared, bt->nchildren - 1),
1471 H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
1472 else {
1473 /* Just update rt_key */
1474 HDmemcpy(rt_key, H5B_NKEY(bt, shared, bt->nchildren - 1),
1475 type->sizeof_nkey);
1476 *rt_key_changed = TRUE;
1477 } /* end else */
1478
1479 bt->nchildren -= 1;
1480 bt_flags |= H5AC__DIRTIED_FLAG;
1481 ret_value = H5B_INS_NOOP;
1482 } else {
1483 /*
1484 * There are subtrees out of this node to both the left and right of
1485 * the subtree being removed. The subtree and its critical key are
1486 * removed from this node and all keys and nodes to the right are
1487 * shifted left by one place. The subtree has already been freed.
1488 * Return H5B_INS_NOOP.
1489 */
1490 if(type->critical_key == H5B_LEFT)
1491 HDmemmove(H5B_NKEY(bt, shared, idx),
1492 H5B_NKEY(bt, shared, idx + 1),
1493 (bt->nchildren - idx) * type->sizeof_nkey);
1494 else
1495 HDmemmove(H5B_NKEY(bt, shared, idx + 1),
1496 H5B_NKEY(bt, shared, idx + 2),
1497 (bt->nchildren - 1 - idx) * type->sizeof_nkey);
1498
1499 HDmemmove(bt->child + idx,
1500 bt->child + idx + 1,
1501 (bt->nchildren - 1 - idx) * sizeof(haddr_t));
1502
1503 bt->nchildren -= 1;
1504 bt_flags |= H5AC__DIRTIED_FLAG;
1505 ret_value = H5B_INS_NOOP;
1506 } /* end else */
1507 } else /* H5B_INS_REMOVE != ret_value */
1508 ret_value = H5B_INS_NOOP;
1509
1510 /* Patch keys in neighboring trees if necessary */
1511 if(*lt_key_changed && H5F_addr_defined(bt->left)) {
1512 HDassert(type->critical_key == H5B_LEFT);
1513 HDassert(level > 0);
1514
1515 /* Update the rightmost key in the left sibling */
1516 if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->left, &cache_udata, H5AC__NO_FLAGS_SET)))
1517 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to protect node")
1518
1519 HDmemcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
1520 H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
1521
1522 if(H5AC_unprotect(f, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
1523 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
1524 sibling = NULL; /* Make certain future references will be caught */
1525 } /* end if */
1526 else if(*rt_key_changed && H5F_addr_defined(bt->right)) {
1527 HDassert(type->critical_key == H5B_RIGHT);
1528 HDassert(level > 0);
1529
1530 /* Update the lefttmost key in the right sibling */
1531 if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
1532 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to protect node")
1533
1534 HDmemcpy(H5B_NKEY(sibling, shared, 0),
1535 H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
1536
1537 if(H5AC_unprotect(f, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
1538 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
1539 sibling = NULL; /* Make certain future references will be caught */
1540 } /* end else */
1541
1542 done:
1543 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags) < 0)
1544 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node")
1545
1546 FUNC_LEAVE_NOAPI(ret_value)
1547 } /* end H5B__remove_helper() */
1548
1549
1550 /*-------------------------------------------------------------------------
1551 * Function: H5B_remove
1552 *
1553 * Purpose: Removes an item from a B-tree.
1554 *
1555 * Note: The current version does not attempt to rebalance the tree.
1556 * (Read the paper Yao & Lehman paper for details on why)
1557 *
1558 * Return: Non-negative on success/Negative on failure (failure includes
1559 * not being able to find the object which is to be removed).
1560 *
1561 * Programmer: Robb Matzke
1562 * Wednesday, September 16, 1998
1563 *
1564 *-------------------------------------------------------------------------
1565 */
1566 herr_t
H5B_remove(H5F_t * f,const H5B_class_t * type,haddr_t addr,void * udata)1567 H5B_remove(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
1568 {
1569 /* These are defined this way to satisfy alignment constraints */
1570 uint64_t _lt_key[128], _rt_key[128];
1571 uint8_t *lt_key = (uint8_t*)_lt_key; /*left key*/
1572 uint8_t *rt_key = (uint8_t*)_rt_key; /*right key*/
1573 hbool_t lt_key_changed = FALSE; /*left key changed?*/
1574 hbool_t rt_key_changed = FALSE; /*right key changed?*/
1575 herr_t ret_value = SUCCEED; /* Return value */
1576
1577 FUNC_ENTER_NOAPI(FAIL)
1578
1579 /* Check args */
1580 HDassert(f);
1581 HDassert(type);
1582 HDassert(type->sizeof_nkey <= sizeof _lt_key);
1583 HDassert(H5F_addr_defined(addr));
1584
1585 /* The actual removal */
1586 if(H5B_INS_ERROR == H5B__remove_helper(f, addr, type, 0, lt_key, <_key_changed, udata, rt_key, &rt_key_changed))
1587 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to remove entry from B-tree")
1588
1589 #ifdef H5B_DEBUG
1590 H5B__assert(f, addr, type, udata);
1591 #endif
1592 done:
1593 FUNC_LEAVE_NOAPI(ret_value)
1594 } /* end H5B_remove() */
1595
1596
1597 /*-------------------------------------------------------------------------
1598 * Function: H5B_delete
1599 *
1600 * Purpose: Deletes an entire B-tree from the file, calling the 'remove'
1601 * callbacks for each node.
1602 *
1603 * Return: Non-negative on success/Negative on failure
1604 *
1605 * Programmer: Quincey Koziol
1606 * Thursday, March 20, 2003
1607 *
1608 *-------------------------------------------------------------------------
1609 */
1610 herr_t
H5B_delete(H5F_t * f,const H5B_class_t * type,haddr_t addr,void * udata)1611 H5B_delete(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
1612 {
1613 H5B_t *bt = NULL; /* B-tree node being operated on */
1614 H5UC_t *rc_shared; /* Ref-counted shared info */
1615 H5B_shared_t *shared; /* Pointer to shared B-tree info */
1616 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
1617 unsigned u; /* Local index variable */
1618 herr_t ret_value = SUCCEED; /* Return value */
1619
1620 FUNC_ENTER_NOAPI(FAIL)
1621
1622 /* Check args */
1623 HDassert(f);
1624 HDassert(type);
1625 HDassert(H5F_addr_defined(addr));
1626
1627 /* Get shared info for B-tree */
1628 if(NULL == (rc_shared = (type->get_shared)(f, udata)))
1629 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
1630 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
1631 HDassert(shared);
1632
1633 /* Lock this B-tree node into memory for now */
1634 cache_udata.f = f;
1635 cache_udata.type = type;
1636 cache_udata.rc_shared = rc_shared;
1637 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
1638 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")
1639
1640 /* Iterate over all children in tree, deleting them */
1641 if(bt->level > 0) {
1642 /* Iterate over all children in node, deleting them */
1643 for(u = 0; u < bt->nchildren; u++)
1644 if(H5B_delete(f, type, bt->child[u], udata) < 0)
1645 HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to delete B-tree node")
1646
1647 } /* end if */
1648 else {
1649 hbool_t lt_key_changed, rt_key_changed; /* Whether key changed (unused here, just for callback) */
1650
1651 /* Check for removal callback */
1652 if(type->remove) {
1653 /* Iterate over all entries in node, calling callback */
1654 for(u = 0; u < bt->nchildren; u++) {
1655 /* Call user's callback for each entry */
1656 if((type->remove)(f, bt->child[u], H5B_NKEY(bt, shared, u),
1657 <_key_changed, udata, H5B_NKEY(bt, shared, u + 1),
1658 &rt_key_changed) < H5B_INS_NOOP)
1659 HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't remove B-tree node")
1660 } /* end for */
1661 } /* end if */
1662 } /* end else */
1663
1664 done:
1665 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0)
1666 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node in cache")
1667
1668 FUNC_LEAVE_NOAPI(ret_value)
1669 } /* end H5B_delete() */
1670
1671
1672 /*-------------------------------------------------------------------------
1673 * Function: H5B_shared_new
1674 *
1675 * Purpose: Allocates & constructs a shared v1 B-tree struct for client.
1676 *
1677 * Return: Success: non-NULL pointer to struct allocated
1678 * Failure: NULL
1679 *
1680 * Programmer: Quincey Koziol
1681 * koziol@hdfgroup.org
1682 * May 27 2008
1683 *
1684 *-------------------------------------------------------------------------
1685 */
1686 H5B_shared_t *
H5B_shared_new(const H5F_t * f,const H5B_class_t * type,size_t sizeof_rkey)1687 H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey)
1688 {
1689 H5B_shared_t *shared = NULL; /* New shared B-tree struct */
1690 size_t u; /* Local index variable */
1691 H5B_shared_t *ret_value = NULL; /* Return value */
1692
1693 FUNC_ENTER_NOAPI(NULL)
1694
1695 /*
1696 * Check arguments.
1697 */
1698 HDassert(type);
1699
1700 /* Allocate space for the shared structure */
1701 if(NULL == (shared = H5FL_CALLOC(H5B_shared_t)))
1702 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for shared B-tree info")
1703
1704 /* Set up the "global" information for this file's groups */
1705 shared->type = type;
1706 shared->two_k = 2 * H5F_KVALUE(f, type);
1707 shared->sizeof_addr = H5F_SIZEOF_ADDR(f);
1708 shared->sizeof_len = H5F_SIZEOF_SIZE(f);
1709 shared->sizeof_rkey = sizeof_rkey;
1710 HDassert(shared->sizeof_rkey);
1711 shared->sizeof_keys = (shared->two_k + 1) * type->sizeof_nkey;
1712 shared->sizeof_rnode = ((size_t)H5B_SIZEOF_HDR(f) + /*node header */
1713 shared->two_k * H5F_SIZEOF_ADDR(f) + /*child pointers */
1714 (shared->two_k + 1) * shared->sizeof_rkey); /*keys */
1715 HDassert(shared->sizeof_rnode);
1716
1717 /* Allocate and clear shared buffers */
1718 if(NULL == (shared->page = H5FL_BLK_MALLOC(page, shared->sizeof_rnode)))
1719 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree page")
1720 HDmemset(shared->page, 0, shared->sizeof_rnode);
1721
1722 if(NULL == (shared->nkey = H5FL_SEQ_MALLOC(size_t, (size_t)(shared->two_k + 1))))
1723 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree native keys")
1724
1725 /* Initialize the offsets into the native key buffer */
1726 for(u = 0; u < (shared->two_k + 1); u++)
1727 shared->nkey[u] = u * type->sizeof_nkey;
1728
1729 /* Set return value */
1730 ret_value = shared;
1731
1732 done:
1733 if(NULL == ret_value)
1734 if(shared) {
1735 if(shared->page)
1736 shared->page = H5FL_BLK_FREE(page, shared->page);
1737 if(shared->nkey)
1738 shared->nkey = H5FL_SEQ_FREE(size_t, shared->nkey);
1739 shared = H5FL_FREE(H5B_shared_t, shared);
1740 } /* end if */
1741
1742 FUNC_LEAVE_NOAPI(ret_value)
1743 } /* end H5B_shared_new() */
1744
1745
1746 /*-------------------------------------------------------------------------
1747 * Function: H5B_shared_free
1748 *
1749 * Purpose: Free B-tree shared info
1750 *
1751 * Return: Non-negative on success/Negative on failure
1752 *
1753 * Programmer: Quincey Koziol
1754 * Tuesday, May 27, 2008
1755 *
1756 *-------------------------------------------------------------------------
1757 */
1758 herr_t
H5B_shared_free(void * _shared)1759 H5B_shared_free(void *_shared)
1760 {
1761 H5B_shared_t *shared = (H5B_shared_t *)_shared;
1762
1763 FUNC_ENTER_NOAPI_NOINIT_NOERR
1764
1765 /* Free the raw B-tree node buffer */
1766 shared->page = H5FL_BLK_FREE(page, shared->page);
1767
1768 /* Free the B-tree native key offsets buffer */
1769 shared->nkey = H5FL_SEQ_FREE(size_t, shared->nkey);
1770
1771 /* Free the shared B-tree info */
1772 shared = H5FL_FREE(H5B_shared_t, shared);
1773
1774 FUNC_LEAVE_NOAPI(SUCCEED)
1775 } /* end H5B_shared_free() */
1776
1777
1778 /*-------------------------------------------------------------------------
1779 * Function: H5B__copy
1780 *
1781 * Purpose: Deep copies an existing H5B_t node.
1782 *
1783 * Return: Success: Pointer to H5B_t object.
1784 *
1785 * Failure: NULL
1786 *
1787 * Programmer: Quincey Koziol
1788 * koziol@ncsa.uiuc.edu
1789 * Apr 18 2000
1790 *
1791 *-------------------------------------------------------------------------
1792 */
1793 static H5B_t *
H5B__copy(const H5B_t * old_bt)1794 H5B__copy(const H5B_t *old_bt)
1795 {
1796 H5B_t *new_node = NULL;
1797 H5B_shared_t *shared; /* Pointer to shared B-tree info */
1798 H5B_t *ret_value = NULL; /* Return value */
1799
1800 FUNC_ENTER_STATIC
1801
1802 /*
1803 * Check arguments.
1804 */
1805 HDassert(old_bt);
1806 shared = (H5B_shared_t *)H5UC_GET_OBJ(old_bt->rc_shared);
1807 HDassert(shared);
1808
1809 /* Allocate memory for the new H5B_t object */
1810 if(NULL == (new_node = H5FL_MALLOC(H5B_t)))
1811 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree root node")
1812
1813 /* Copy the main structure */
1814 HDmemcpy(new_node, old_bt, sizeof(H5B_t));
1815
1816 /* Reset cache info */
1817 HDmemset(&new_node->cache_info, 0, sizeof(H5AC_info_t));
1818
1819 if(NULL == (new_node->native = H5FL_BLK_MALLOC(native_block, shared->sizeof_keys)) ||
1820 NULL == (new_node->child = H5FL_SEQ_MALLOC(haddr_t, (size_t)shared->two_k)))
1821 HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree root node")
1822
1823 /* Copy the other structures */
1824 HDmemcpy(new_node->native, old_bt->native, shared->sizeof_keys);
1825 HDmemcpy(new_node->child, old_bt->child, (sizeof(haddr_t) * shared->two_k));
1826
1827 /* Increment the ref-count on the raw page */
1828 H5UC_INC(new_node->rc_shared);
1829
1830 /* Set return value */
1831 ret_value = new_node;
1832
1833 done:
1834 if(NULL == ret_value) {
1835 if(new_node) {
1836 new_node->native = H5FL_BLK_FREE(native_block, new_node->native);
1837 new_node->child = H5FL_SEQ_FREE(haddr_t, new_node->child);
1838 new_node = H5FL_FREE(H5B_t, new_node);
1839 } /* end if */
1840 } /* end if */
1841
1842 FUNC_LEAVE_NOAPI(ret_value)
1843 } /* end H5B__copy() */
1844
1845
1846 /*-------------------------------------------------------------------------
1847 * Function: H5B__get_info_helper
1848 *
1849 * Purpose: Walks the B-tree nodes, getting information for all of them.
1850 *
1851 * Return: Non-negative on success/Negative on failure
1852 *
1853 * Programmer: Quincey Koziol
1854 * koziol@hdfgroup.org
1855 * Jun 3 2008
1856 *
1857 *-------------------------------------------------------------------------
1858 */
1859 static herr_t
H5B__get_info_helper(H5F_t * f,const H5B_class_t * type,haddr_t addr,const H5B_info_ud_t * info_udata)1860 H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
1861 const H5B_info_ud_t *info_udata)
1862 {
1863 H5B_t *bt = NULL; /* Pointer to current B-tree node */
1864 H5UC_t *rc_shared; /* Ref-counted shared info */
1865 H5B_shared_t *shared; /* Pointer to shared B-tree info */
1866 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
1867 unsigned level; /* Node level */
1868 size_t sizeof_rnode; /* Size of raw (disk) node */
1869 haddr_t next_addr; /* Address of next node to the right */
1870 haddr_t left_child; /* Address of left-most child in node */
1871 herr_t ret_value = SUCCEED; /* Return value */
1872
1873 FUNC_ENTER_STATIC
1874
1875 /*
1876 * Check arguments.
1877 */
1878 HDassert(f);
1879 HDassert(type);
1880 HDassert(H5F_addr_defined(addr));
1881 HDassert(info_udata);
1882 HDassert(info_udata->bt_info);
1883 HDassert(info_udata->udata);
1884
1885 /* Get shared info for B-tree */
1886 if(NULL == (rc_shared = (type->get_shared)(f, info_udata->udata)))
1887 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
1888 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
1889 HDassert(shared);
1890
1891 /* Get the raw node size for iteration */
1892 sizeof_rnode = shared->sizeof_rnode;
1893
1894 /* Protect the initial/current node */
1895 cache_udata.f = f;
1896 cache_udata.type = type;
1897 cache_udata.rc_shared = rc_shared;
1898 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
1899 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")
1900
1901 /* Cache information from this node */
1902 left_child = bt->child[0];
1903 next_addr = bt->right;
1904 level = bt->level;
1905
1906 /* Update B-tree info */
1907 info_udata->bt_info->size += sizeof_rnode;
1908 info_udata->bt_info->num_nodes++;
1909
1910 /* Release current node */
1911 if(H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
1912 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
1913 bt = NULL;
1914
1915 /*
1916 * Follow the right-sibling pointer from node to node until we've
1917 * processed all nodes.
1918 */
1919 while(H5F_addr_defined(next_addr)) {
1920 /* Protect the next node to the right */
1921 addr = next_addr;
1922 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
1923 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "B-tree node")
1924
1925 /* Cache information from this node */
1926 next_addr = bt->right;
1927
1928 /* Update B-tree info */
1929 info_udata->bt_info->size += sizeof_rnode;
1930 info_udata->bt_info->num_nodes++;
1931
1932 /* Unprotect node */
1933 if(H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
1934 HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
1935 bt = NULL;
1936 } /* end while */
1937
1938 /* Check for another "row" of B-tree nodes to iterate over */
1939 if(level > 0) {
1940 /* Keep following the left-most child until we reach a leaf node. */
1941 if(H5B__get_info_helper(f, type, left_child, info_udata) < 0)
1942 HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to list B-tree node")
1943 } /* end if */
1944
1945 done:
1946 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
1947 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
1948
1949 FUNC_LEAVE_NOAPI(ret_value)
1950 } /* end H5B__get_info_helper() */
1951
1952
1953 /*-------------------------------------------------------------------------
1954 * Function: H5B_get_info
1955 *
1956 * Purpose: Return the amount of storage used for the btree.
1957 *
1958 * Return: Non-negative on success/Negative on failure
1959 *
1960 * Programmer: Vailin Choi
1961 * June 19, 2007
1962 *
1963 *-------------------------------------------------------------------------
1964 */
1965 herr_t
H5B_get_info(H5F_t * f,const H5B_class_t * type,haddr_t addr,H5B_info_t * bt_info,H5B_operator_t op,void * udata)1966 H5B_get_info(H5F_t *f, const H5B_class_t *type, haddr_t addr,
1967 H5B_info_t *bt_info, H5B_operator_t op, void *udata)
1968 {
1969 H5B_info_ud_t info_udata; /* User-data for B-tree size iteration */
1970 herr_t ret_value = SUCCEED; /* Return value */
1971
1972 FUNC_ENTER_NOAPI(FAIL)
1973
1974 /*
1975 * Check arguments.
1976 */
1977 HDassert(f);
1978 HDassert(type);
1979 HDassert(bt_info);
1980 HDassert(H5F_addr_defined(addr));
1981 HDassert(udata);
1982
1983 /* Portably initialize B-tree info struct */
1984 HDmemset(bt_info, 0, sizeof(*bt_info));
1985
1986 /* Set up internal user-data for the B-tree 'get info' helper routine */
1987 info_udata.bt_info = bt_info;
1988 info_udata.udata = udata;
1989
1990 /* Iterate over the B-tree nodes */
1991 if(H5B__get_info_helper(f, type, addr, &info_udata) < 0)
1992 HGOTO_ERROR(H5E_BTREE, H5E_BADITER, FAIL, "B-tree iteration failed")
1993
1994 /* Iterate over the B-tree records, making any "leaf" callbacks */
1995 /* (Only if operator defined) */
1996 if(op)
1997 if((ret_value = H5B__iterate_helper(f, type, addr, op, udata)) < 0)
1998 HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");
1999
2000 done:
2001 FUNC_LEAVE_NOAPI(ret_value)
2002 } /* end H5B_get_info() */
2003
2004
2005 /*-------------------------------------------------------------------------
2006 * Function: H5B_valid
2007 *
2008 * Purpose: Attempt to load a B-tree node.
2009 *
2010 * Return: Non-negative on success/Negative on failure
2011 *
2012 * Programmer: Neil Fortner
2013 * March 17, 2009
2014 *
2015 *-------------------------------------------------------------------------
2016 */
2017 htri_t
H5B_valid(H5F_t * f,const H5B_class_t * type,haddr_t addr)2018 H5B_valid(H5F_t *f, const H5B_class_t *type, haddr_t addr)
2019 {
2020 H5B_t *bt = NULL; /* The B-tree */
2021 H5UC_t *rc_shared; /* Ref-counted shared info */
2022 H5B_shared_t *shared; /* Pointer to shared B-tree info */
2023 H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
2024 htri_t ret_value = SUCCEED; /* Return value */
2025
2026 FUNC_ENTER_NOAPI(FAIL)
2027
2028 /*
2029 * Check arguments.
2030 */
2031 HDassert(f);
2032 HDassert(type);
2033
2034 if(!H5F_addr_defined(addr))
2035 HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, FAIL, "address is undefined")
2036
2037 /* Get shared info for B-tree */
2038 if(NULL == (rc_shared = (type->get_shared)(f, NULL)))
2039 HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
2040 shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
2041 HDassert(shared);
2042
2043 /*
2044 * Load the tree node.
2045 */
2046 cache_udata.f = f;
2047 cache_udata.type = type;
2048 cache_udata.rc_shared = rc_shared;
2049 if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
2050 HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree node")
2051
2052 done:
2053 /* Release the node */
2054 if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
2055 HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
2056
2057 FUNC_LEAVE_NOAPI(ret_value)
2058 } /* end H5B_valid() */
2059
2060
2061 /*-------------------------------------------------------------------------
2062 * Function: H5B__node_dest
2063 *
2064 * Purpose: Destroy/release a B-tree node
2065 *
2066 * Return: Success: SUCCEED
2067 * Failure: FAIL
2068 *
2069 * Programmer: Quincey Koziol
2070 * koziol@hdfgroup.org
2071 * Mar 26, 2008
2072 *
2073 *-------------------------------------------------------------------------
2074 */
2075 herr_t
H5B__node_dest(H5B_t * bt)2076 H5B__node_dest(H5B_t *bt)
2077 {
2078 FUNC_ENTER_PACKAGE_NOERR
2079
2080 /* check arguments */
2081 HDassert(bt);
2082 HDassert(bt->rc_shared);
2083
2084 bt->child = H5FL_SEQ_FREE(haddr_t, bt->child);
2085 bt->native = H5FL_BLK_FREE(native_block, bt->native);
2086 H5UC_DEC(bt->rc_shared);
2087 bt = H5FL_FREE(H5B_t, bt);
2088
2089 FUNC_LEAVE_NOAPI(SUCCEED)
2090 } /* end H5B__node_dest() */
2091
2092