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