1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * Copyright by The HDF Group. *
3 * Copyright by the Board of Trustees of the University of Illinois. *
4 * All rights reserved. *
5 * *
6 * This file is part of HDF5. The full HDF5 copyright notice, including *
7 * terms governing use, modification, and redistribution, is contained in *
8 * the COPYING file, which can be found at the root of the source code *
9 * distribution tree, or in https://www.hdfgroup.org/licenses. *
10 * If you do not have access to either file, you may request a copy from *
11 * help@hdfgroup.org. *
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 /* Programmer: Robb Matzke
15 * Wednesday, October 8, 1997
16 *
17 * Purpose: v1 B-tree indexed (chunked) I/O functions. The chunks are
18 * given a multi-dimensional index which is used as a lookup key
19 * in a B-tree that maps chunk index to disk address.
20 *
21 */
22
23 /****************/
24 /* Module Setup */
25 /****************/
26
27 #include "H5Dmodule.h" /* This source code file is part of the H5D module */
28
29 /***********/
30 /* Headers */
31 /***********/
32 #include "H5private.h" /* Generic Functions */
33 #include "H5Bprivate.h" /* B-link trees */
34 #include "H5Dpkg.h" /* Datasets */
35 #include "H5Eprivate.h" /* Error handling */
36 #include "H5Fprivate.h" /* Files */
37 #include "H5FDprivate.h" /* File drivers */
38 #include "H5FLprivate.h" /* Free Lists */
39 #include "H5Iprivate.h" /* IDs */
40 #include "H5MFprivate.h" /* File space management */
41 #include "H5MMprivate.h" /* Memory management */
42 #include "H5Oprivate.h" /* Object headers */
43 #include "H5Sprivate.h" /* Dataspaces */
44 #include "H5VMprivate.h" /* Vector and array functions */
45
46 /****************/
47 /* Local Macros */
48 /****************/
49
50 /******************/
51 /* Local Typedefs */
52 /******************/
53
54 /*
55 * B-tree key. A key contains the minimum logical N-dimensional coordinates and
56 * the logical size of the chunk to which this key refers. The
57 * fastest-varying dimension is assumed to reference individual bytes of the
58 * array, so a 100-element 1-d array of 4-byte integers would really be a 2-d
59 * array with the slow varying dimension of size 100 and the fast varying
60 * dimension of size 4 (the storage dimensionality has very little to do with
61 * the real dimensionality).
62 *
63 * Only the first few values of the OFFSET and SIZE fields are actually
64 * stored on disk, depending on the dimensionality.
65 *
66 * The chunk's file address is part of the B-tree and not part of the key.
67 */
68 typedef struct H5D_btree_key_t {
69 hsize_t scaled[H5O_LAYOUT_NDIMS]; /*logical offset to start*/
70 uint32_t nbytes; /*size of stored data */
71 unsigned filter_mask; /*excluded filters */
72 } H5D_btree_key_t;
73
74 /* B-tree callback info for iteration over chunks */
75 typedef struct H5D_btree_it_ud_t {
76 H5D_chunk_common_ud_t common; /* Common info for B-tree user data (must be first) */
77 H5D_chunk_cb_func_t cb; /* Chunk callback routine */
78 void * udata; /* User data for chunk callback routine */
79 } H5D_btree_it_ud_t;
80
81 /* B-tree callback info for debugging */
82 typedef struct H5D_btree_dbg_t {
83 H5D_chunk_common_ud_t common; /* Common info for B-tree user data (must be first) */
84 unsigned ndims; /* Number of dimensions */
85 } H5D_btree_dbg_t;
86
87 /********************/
88 /* Local Prototypes */
89 /********************/
90
91 static herr_t H5D__btree_shared_free(void *_shared);
92 static herr_t H5D__btree_shared_create(const H5F_t *f, H5O_storage_chunk_t *store,
93 const H5O_layout_chunk_t *layout);
94
95 /* B-tree iterator callbacks */
96 static int H5D__btree_idx_iterate_cb(H5F_t *f, const void *left_key, haddr_t addr, const void *right_key,
97 void *_udata);
98
99 /* B-tree callbacks */
100 static H5UC_t * H5D__btree_get_shared(const H5F_t *f, const void *_udata);
101 static herr_t H5D__btree_new_node(H5F_t *f, H5B_ins_t, void *_lt_key, void *_udata, void *_rt_key,
102 haddr_t *addr_p /*out*/);
103 static int H5D__btree_cmp2(void *_lt_key, void *_udata, void *_rt_key);
104 static int H5D__btree_cmp3(void *_lt_key, void *_udata, void *_rt_key);
105 static htri_t H5D__btree_found(H5F_t *f, haddr_t addr, const void *_lt_key, void *_udata);
106 static H5B_ins_t H5D__btree_insert(H5F_t *f, haddr_t addr, void *_lt_key, hbool_t *lt_key_changed,
107 void *_md_key, void *_udata, void *_rt_key, hbool_t *rt_key_changed,
108 haddr_t *new_node /*out*/);
109 static H5B_ins_t H5D__btree_remove(H5F_t *f, haddr_t addr, void *_lt_key, hbool_t *lt_key_changed,
110 void *_udata, void *_rt_key, hbool_t *rt_key_changed);
111 static herr_t H5D__btree_decode_key(const H5B_shared_t *shared, const uint8_t *raw, void *_key);
112 static herr_t H5D__btree_encode_key(const H5B_shared_t *shared, uint8_t *raw, const void *_key);
113 static herr_t H5D__btree_debug_key(FILE *stream, int indent, int fwidth, const void *key, const void *udata);
114
115 /* Chunked layout indexing callbacks */
116 static herr_t H5D__btree_idx_init(const H5D_chk_idx_info_t *idx_info, const H5S_t *space,
117 haddr_t dset_ohdr_addr);
118 static herr_t H5D__btree_idx_create(const H5D_chk_idx_info_t *idx_info);
119 static hbool_t H5D__btree_idx_is_space_alloc(const H5O_storage_chunk_t *storage);
120 static herr_t H5D__btree_idx_insert(const H5D_chk_idx_info_t *idx_info, H5D_chunk_ud_t *udata,
121 const H5D_t *dset);
122 static herr_t H5D__btree_idx_get_addr(const H5D_chk_idx_info_t *idx_info, H5D_chunk_ud_t *udata);
123 static int H5D__btree_idx_iterate(const H5D_chk_idx_info_t *idx_info, H5D_chunk_cb_func_t chunk_cb,
124 void *chunk_udata);
125 static herr_t H5D__btree_idx_remove(const H5D_chk_idx_info_t *idx_info, H5D_chunk_common_ud_t *udata);
126 static herr_t H5D__btree_idx_delete(const H5D_chk_idx_info_t *idx_info);
127 static herr_t H5D__btree_idx_copy_setup(const H5D_chk_idx_info_t *idx_info_src,
128 const H5D_chk_idx_info_t *idx_info_dst);
129 static herr_t H5D__btree_idx_copy_shutdown(H5O_storage_chunk_t *storage_src,
130 H5O_storage_chunk_t *storage_dst);
131 static herr_t H5D__btree_idx_size(const H5D_chk_idx_info_t *idx_info, hsize_t *size);
132 static herr_t H5D__btree_idx_reset(H5O_storage_chunk_t *storage, hbool_t reset_addr);
133 static herr_t H5D__btree_idx_dump(const H5O_storage_chunk_t *storage, FILE *stream);
134 static herr_t H5D__btree_idx_dest(const H5D_chk_idx_info_t *idx_info);
135
136 /*********************/
137 /* Package Variables */
138 /*********************/
139
140 /* v1 B-tree indexed chunk I/O ops */
141 const H5D_chunk_ops_t H5D_COPS_BTREE[1] = {{
142 FALSE, /* v1 B-tree indices does not support SWMR access */
143 H5D__btree_idx_init, /* insert */
144 H5D__btree_idx_create, /* create */
145 H5D__btree_idx_is_space_alloc, /* is_space_alloc */
146 H5D__btree_idx_insert, /* insert */
147 H5D__btree_idx_get_addr, /* get_addr */
148 NULL, /* resize */
149 H5D__btree_idx_iterate, /* iterate */
150 H5D__btree_idx_remove, /* remove */
151 H5D__btree_idx_delete, /* delete */
152 H5D__btree_idx_copy_setup, /* copy_setup */
153 H5D__btree_idx_copy_shutdown, /* copy_shutdown */
154 H5D__btree_idx_size, /* size */
155 H5D__btree_idx_reset, /* reset */
156 H5D__btree_idx_dump, /* dump */
157 H5D__btree_idx_dest /* destroy */
158 }};
159
160 /*****************************/
161 /* Library Private Variables */
162 /*****************************/
163
164 /* inherits B-tree like properties from H5B */
165 H5B_class_t H5B_BTREE[1] = {{
166 H5B_CHUNK_ID, /*id */
167 sizeof(H5D_btree_key_t), /*sizeof_nkey */
168 H5D__btree_get_shared, /*get_shared */
169 H5D__btree_new_node, /*new */
170 H5D__btree_cmp2, /*cmp2 */
171 H5D__btree_cmp3, /*cmp3 */
172 H5D__btree_found, /*found */
173 H5D__btree_insert, /*insert */
174 FALSE, /*follow min branch? */
175 FALSE, /*follow max branch? */
176 H5B_LEFT, /*critical key */
177 H5D__btree_remove, /*remove */
178 H5D__btree_decode_key, /*decode */
179 H5D__btree_encode_key, /*encode */
180 H5D__btree_debug_key /*debug */
181 }};
182
183 /*******************/
184 /* Local Variables */
185 /*******************/
186
187 /* Declare a free list to manage H5O_layout_chunk_t objects */
188 H5FL_DEFINE_STATIC(H5O_layout_chunk_t);
189
190 /*-------------------------------------------------------------------------
191 * Function: H5D__btree_get_shared
192 *
193 * Purpose: Returns the shared B-tree info for the specified UDATA.
194 *
195 * Return: Success: Pointer to the raw B-tree page for this dataset
196 *
197 * Failure: Can't fail
198 *
199 * Programmer: Quincey Koziol
200 * Monday, July 5, 2004
201 *
202 *-------------------------------------------------------------------------
203 */
204 static H5UC_t *
H5D__btree_get_shared(const H5F_t H5_ATTR_UNUSED * f,const void * _udata)205 H5D__btree_get_shared(const H5F_t H5_ATTR_UNUSED *f, const void *_udata)
206 {
207 const H5D_chunk_common_ud_t *udata = (const H5D_chunk_common_ud_t *)_udata;
208
209 FUNC_ENTER_STATIC_NOERR
210
211 HDassert(udata);
212 HDassert(udata->storage);
213 HDassert(udata->storage->idx_type == H5D_CHUNK_IDX_BTREE);
214 HDassert(udata->storage->u.btree.shared);
215
216 /* Return the pointer to the ref-count object */
217 FUNC_LEAVE_NOAPI(udata->storage->u.btree.shared)
218 } /* end H5D__btree_get_shared() */
219
220 /*-------------------------------------------------------------------------
221 * Function: H5D__btree_new_node
222 *
223 * Purpose: Adds a new entry to an i-storage B-tree. We can assume that
224 * the domain represented by UDATA doesn't intersect the domain
225 * already represented by the B-tree.
226 *
227 * Return: Success: Non-negative. The address of leaf is returned
228 * through the ADDR argument. It is also added
229 * to the UDATA.
230 *
231 * Failure: Negative
232 *
233 * Programmer: Robb Matzke
234 * Tuesday, October 14, 1997
235 *
236 *-------------------------------------------------------------------------
237 */
238 static herr_t
H5D__btree_new_node(H5F_t H5_ATTR_NDEBUG_UNUSED * f,H5B_ins_t op,void * _lt_key,void * _udata,void * _rt_key,haddr_t * addr_p)239 H5D__btree_new_node(H5F_t H5_ATTR_NDEBUG_UNUSED *f, H5B_ins_t op, void *_lt_key, void *_udata, void *_rt_key,
240 haddr_t *addr_p /*out*/)
241 {
242 H5D_btree_key_t *lt_key = (H5D_btree_key_t *)_lt_key;
243 H5D_btree_key_t *rt_key = (H5D_btree_key_t *)_rt_key;
244 H5D_chunk_ud_t * udata = (H5D_chunk_ud_t *)_udata;
245 unsigned u;
246 herr_t ret_value = SUCCEED; /* Return value */
247
248 FUNC_ENTER_STATIC_NOERR
249
250 /* check args */
251 HDassert(f);
252 HDassert(lt_key);
253 HDassert(rt_key);
254 HDassert(udata);
255 HDassert(udata->common.layout->ndims > 0 && udata->common.layout->ndims < H5O_LAYOUT_NDIMS);
256 HDassert(addr_p);
257
258 /* Set address */
259 HDassert(H5F_addr_defined(udata->chunk_block.offset));
260 HDassert(udata->chunk_block.length > 0);
261 *addr_p = udata->chunk_block.offset;
262
263 /*
264 * The left key describes the storage of the UDATA chunk being
265 * inserted into the tree.
266 */
267 H5_CHECKED_ASSIGN(lt_key->nbytes, uint32_t, udata->chunk_block.length, hsize_t);
268 lt_key->filter_mask = udata->filter_mask;
269 for (u = 0; u < udata->common.layout->ndims; u++)
270 lt_key->scaled[u] = udata->common.scaled[u];
271
272 /*
273 * The right key might already be present. If not, then add a zero-width
274 * chunk.
275 */
276 if (H5B_INS_LEFT != op) {
277 rt_key->nbytes = 0;
278 rt_key->filter_mask = 0;
279 for (u = 0; u < udata->common.layout->ndims; u++) {
280 HDassert(udata->common.scaled[u] + 1 > udata->common.scaled[u]);
281 rt_key->scaled[u] = udata->common.scaled[u] + 1;
282 } /* end if */
283 } /* end if */
284
285 FUNC_LEAVE_NOAPI(ret_value)
286 } /* end H5D__btree_new_node() */
287
288 /*-------------------------------------------------------------------------
289 * Function: H5D__btree_cmp2
290 *
291 * Purpose: Compares two keys sort of like strcmp(). The UDATA pointer
292 * is only to supply extra information not carried in the keys
293 * (in this case, the dimensionality) and is not compared
294 * against the keys.
295 *
296 * Return: Success: -1 if LT_KEY is less than RT_KEY;
297 * 1 if LT_KEY is greater than RT_KEY;
298 * 0 if LT_KEY and RT_KEY are equal.
299 *
300 * Failure: FAIL (same as LT_KEY<RT_KEY)
301 *
302 * Programmer: Robb Matzke
303 * Thursday, November 6, 1997
304 *
305 *-------------------------------------------------------------------------
306 */
307 static int
H5D__btree_cmp2(void * _lt_key,void * _udata,void * _rt_key)308 H5D__btree_cmp2(void *_lt_key, void *_udata, void *_rt_key)
309 {
310 H5D_btree_key_t * lt_key = (H5D_btree_key_t *)_lt_key;
311 H5D_btree_key_t * rt_key = (H5D_btree_key_t *)_rt_key;
312 H5D_chunk_common_ud_t *udata = (H5D_chunk_common_ud_t *)_udata;
313 int ret_value = -1; /* Return value */
314
315 FUNC_ENTER_STATIC_NOERR
316
317 HDassert(lt_key);
318 HDassert(rt_key);
319 HDassert(udata);
320 HDassert(udata->layout->ndims > 0 && udata->layout->ndims <= H5O_LAYOUT_NDIMS);
321
322 /* Compare the offsets but ignore the other fields */
323 ret_value = H5VM_vector_cmp_u(udata->layout->ndims, lt_key->scaled, rt_key->scaled);
324
325 FUNC_LEAVE_NOAPI(ret_value)
326 } /* end H5D__btree_cmp2() */
327
328 /*-------------------------------------------------------------------------
329 * Function: H5D__btree_cmp3
330 *
331 * Purpose: Compare the requested datum UDATA with the left and right
332 * keys of the B-tree.
333 *
334 * Return: Success: negative if the min_corner of UDATA is less
335 * than the min_corner of LT_KEY.
336 *
337 * positive if the min_corner of UDATA is
338 * greater than or equal the min_corner of
339 * RT_KEY.
340 *
341 * zero otherwise. The min_corner of UDATA is
342 * not necessarily contained within the address
343 * space represented by LT_KEY, but a key that
344 * would describe the UDATA min_corner address
345 * would fall lexicographically between LT_KEY
346 * and RT_KEY.
347 *
348 * Failure: FAIL (same as UDATA < LT_KEY)
349 *
350 * Programmer: Robb Matzke
351 * Wednesday, October 8, 1997
352 *
353 *-------------------------------------------------------------------------
354 */
355 static int
H5D__btree_cmp3(void * _lt_key,void * _udata,void * _rt_key)356 H5D__btree_cmp3(void *_lt_key, void *_udata, void *_rt_key)
357 {
358 H5D_btree_key_t * lt_key = (H5D_btree_key_t *)_lt_key;
359 H5D_btree_key_t * rt_key = (H5D_btree_key_t *)_rt_key;
360 H5D_chunk_common_ud_t *udata = (H5D_chunk_common_ud_t *)_udata;
361 int ret_value = 0;
362
363 FUNC_ENTER_STATIC_NOERR
364
365 HDassert(lt_key);
366 HDassert(rt_key);
367 HDassert(udata);
368 HDassert(udata->layout->ndims > 0 && udata->layout->ndims <= H5O_LAYOUT_NDIMS);
369
370 /* Special case for faster checks on 1-D chunks */
371 /* (Checking for ndims==2 because last dimension is the datatype size) */
372 /* The additional checking for the right key is necessary due to the */
373 /* slightly odd way the library initializes the right-most node in the */
374 /* indexed storage B-tree... */
375 /* (Dump the B-tree with h5debug to look at it) -QAK */
376 if (udata->layout->ndims == 2) {
377 if (udata->scaled[0] > rt_key->scaled[0])
378 ret_value = 1;
379 else if (udata->scaled[0] == rt_key->scaled[0] && udata->scaled[1] >= rt_key->scaled[1])
380 ret_value = 1;
381 else if (udata->scaled[0] < lt_key->scaled[0])
382 ret_value = (-1);
383 } /* end if */
384 else {
385 if (H5VM_vector_ge_u(udata->layout->ndims, udata->scaled, rt_key->scaled))
386 ret_value = 1;
387 else if (H5VM_vector_lt_u(udata->layout->ndims, udata->scaled, lt_key->scaled))
388 ret_value = (-1);
389 } /* end else */
390
391 FUNC_LEAVE_NOAPI(ret_value)
392 } /* end H5D__btree_cmp3() */
393
394 /*-------------------------------------------------------------------------
395 * Function: H5D__btree_found
396 *
397 * Purpose: This function is called when the B-tree search engine has
398 * found the leaf entry that points to a chunk of storage that
399 * contains the beginning of the logical address space
400 * represented by UDATA. The LT_KEY is the left key (the one
401 * that describes the chunk) and RT_KEY is the right key (the
402 * one that describes the next or last chunk).
403 *
404 * Note: It's possible that the chunk isn't really found. For
405 * instance, in a sparse dataset the requested chunk might fall
406 * between two stored chunks in which case this function is
407 * called with the maximum stored chunk indices less than the
408 * requested chunk indices.
409 *
410 * Return: Non-negative (TRUE/FALSE) on success with information about the
411 * chunk returned through the UDATA argument. Negative on failure.
412 *
413 * Programmer: Robb Matzke
414 * Thursday, October 9, 1997
415 *
416 *-------------------------------------------------------------------------
417 */
418 static htri_t
H5D__btree_found(H5F_t H5_ATTR_UNUSED * f,haddr_t addr,const void * _lt_key,void * _udata)419 H5D__btree_found(H5F_t H5_ATTR_UNUSED *f, haddr_t addr, const void *_lt_key, void *_udata)
420 {
421 H5D_chunk_ud_t * udata = (H5D_chunk_ud_t *)_udata;
422 const H5D_btree_key_t *lt_key = (const H5D_btree_key_t *)_lt_key;
423 unsigned u;
424 htri_t ret_value = TRUE; /* Return value */
425
426 FUNC_ENTER_STATIC_NOERR
427
428 /* Check arguments */
429 HDassert(f);
430 HDassert(H5F_addr_defined(addr));
431 HDassert(udata);
432 HDassert(lt_key);
433
434 /* Is this *really* the requested chunk? */
435 for (u = 0; u < udata->common.layout->ndims; u++)
436 if (udata->common.scaled[u] >= (lt_key->scaled[u] + 1))
437 HGOTO_DONE(FALSE)
438
439 /* Initialize return values */
440 HDassert(lt_key->nbytes > 0);
441 udata->chunk_block.offset = addr;
442 udata->chunk_block.length = lt_key->nbytes;
443 udata->filter_mask = lt_key->filter_mask;
444
445 done:
446 FUNC_LEAVE_NOAPI(ret_value)
447 } /* end H5D__btree_found() */
448
449 /*-------------------------------------------------------------------------
450 * Function: H5D__chunk_disjoint
451 *
452 * Purpose: Determines if two chunks are disjoint.
453 *
454 * Return: Success: FALSE if they are not disjoint.
455 * TRUE if they are disjoint.
456 *
457 * Programmer: Quincey Koziol
458 * Wednesday, May 6, 2015
459 *
460 * Note: Assumes that the chunk offsets are scaled coordinates
461 *
462 *-------------------------------------------------------------------------
463 */
464 static hbool_t
H5D__chunk_disjoint(unsigned n,const hsize_t * scaled1,const hsize_t * scaled2)465 H5D__chunk_disjoint(unsigned n, const hsize_t *scaled1, const hsize_t *scaled2)
466 {
467 unsigned u; /* Local index variable */
468 hbool_t ret_value = FALSE; /* Return value */
469
470 FUNC_ENTER_STATIC_NOERR
471
472 /* Sanity checks */
473 HDassert(n);
474 HDassert(scaled1);
475 HDassert(scaled2);
476
477 /* Loop over two chunks, detecting disjointness and getting out quickly */
478 for (u = 0; u < n; u++)
479 if ((scaled1[u] + 1) <= scaled2[u] || (scaled2[u] + 1) <= scaled1[u])
480 HGOTO_DONE(TRUE)
481
482 done:
483 FUNC_LEAVE_NOAPI(ret_value)
484 } /* end H5D__chunk_disjoint() */
485
486 /*-------------------------------------------------------------------------
487 * Function: H5D__btree_insert
488 *
489 * Purpose: This function is called when the B-tree insert engine finds
490 * the node to use to insert new data. The UDATA argument
491 * points to a struct that describes the logical addresses being
492 * added to the file. This function allocates space for the
493 * data and returns information through UDATA describing a
494 * file chunk to receive (part of) the data.
495 *
496 * The LT_KEY is always the key describing the chunk of file
497 * memory at address ADDR. On entry, UDATA describes the logical
498 * addresses for which storage is being requested (through the
499 * `offset' and `size' fields). On return, UDATA describes the
500 * logical addresses contained in a chunk on disk.
501 *
502 * Return: Success: An insertion command for the caller, one of
503 * the H5B_INS_* constants. The address of the
504 * new chunk is returned through the NEW_NODE
505 * argument.
506 *
507 * Failure: H5B_INS_ERROR
508 *
509 * Programmer: Robb Matzke
510 * Thursday, October 9, 1997
511 *
512 *-------------------------------------------------------------------------
513 */
514 static H5B_ins_t
H5D__btree_insert(H5F_t H5_ATTR_NDEBUG_UNUSED * f,haddr_t H5_ATTR_NDEBUG_UNUSED addr,void * _lt_key,hbool_t * lt_key_changed,void * _md_key,void * _udata,void * _rt_key,hbool_t H5_ATTR_UNUSED * rt_key_changed,haddr_t * new_node_p)515 H5D__btree_insert(H5F_t H5_ATTR_NDEBUG_UNUSED *f, haddr_t H5_ATTR_NDEBUG_UNUSED addr, void *_lt_key,
516 hbool_t *lt_key_changed, void *_md_key, void *_udata, void *_rt_key,
517 hbool_t H5_ATTR_UNUSED *rt_key_changed, haddr_t *new_node_p /*out*/)
518 {
519 H5D_btree_key_t *lt_key = (H5D_btree_key_t *)_lt_key;
520 H5D_btree_key_t *md_key = (H5D_btree_key_t *)_md_key;
521 H5D_btree_key_t *rt_key = (H5D_btree_key_t *)_rt_key;
522 H5D_chunk_ud_t * udata = (H5D_chunk_ud_t *)_udata;
523 int cmp;
524 unsigned u;
525 H5B_ins_t ret_value = H5B_INS_ERROR; /* Return value */
526
527 FUNC_ENTER_STATIC
528
529 /* check args */
530 HDassert(f);
531 HDassert(H5F_addr_defined(addr));
532 HDassert(lt_key);
533 HDassert(lt_key_changed);
534 HDassert(md_key);
535 HDassert(udata);
536 HDassert(rt_key);
537 HDassert(new_node_p);
538
539 cmp = H5D__btree_cmp3(lt_key, udata, rt_key);
540 HDassert(cmp <= 0);
541
542 if (cmp < 0) {
543 /* Negative indices not supported yet */
544 HGOTO_ERROR(H5E_STORAGE, H5E_UNSUPPORTED, H5B_INS_ERROR, "internal error")
545 }
546 else if (H5VM_vector_eq_u(udata->common.layout->ndims, udata->common.scaled, lt_key->scaled) &&
547 lt_key->nbytes > 0) {
548 /*
549 * Already exists. If the new size is not the same as the old size
550 * then we should reallocate storage.
551 */
552 if (lt_key->nbytes != udata->chunk_block.length) {
553 /* Set node's address (already re-allocated by main chunk routines) */
554 HDassert(H5F_addr_defined(udata->chunk_block.offset));
555 *new_node_p = udata->chunk_block.offset;
556 H5_CHECKED_ASSIGN(lt_key->nbytes, uint32_t, udata->chunk_block.length, hsize_t);
557 lt_key->filter_mask = udata->filter_mask;
558 *lt_key_changed = TRUE;
559 ret_value = H5B_INS_CHANGE;
560 }
561 else {
562 /* Already have address in udata, from main chunk routines */
563 HDassert(H5F_addr_defined(udata->chunk_block.offset));
564 ret_value = H5B_INS_NOOP;
565 }
566 }
567 else if (H5D__chunk_disjoint(udata->common.layout->ndims, lt_key->scaled, udata->common.scaled)) {
568 HDassert(H5D__chunk_disjoint(udata->common.layout->ndims, rt_key->scaled, udata->common.scaled));
569 /*
570 * Split this node, inserting the new new node to the right of the
571 * current node. The MD_KEY is where the split occurs.
572 */
573 H5_CHECKED_ASSIGN(md_key->nbytes, uint32_t, udata->chunk_block.length, hsize_t);
574 md_key->filter_mask = udata->filter_mask;
575 for (u = 0; u < udata->common.layout->ndims; u++)
576 md_key->scaled[u] = udata->common.scaled[u];
577
578 HDassert(H5F_addr_defined(udata->chunk_block.offset));
579 *new_node_p = udata->chunk_block.offset;
580 ret_value = H5B_INS_RIGHT;
581 }
582 else {
583 HGOTO_ERROR(H5E_IO, H5E_UNSUPPORTED, H5B_INS_ERROR, "internal error")
584 }
585
586 done:
587 FUNC_LEAVE_NOAPI(ret_value)
588 } /* end H5D__btree_insert() */
589
590 /*-------------------------------------------------------------------------
591 * Function: H5D__btree_remove
592 *
593 * Purpose: Removes chunks that are no longer necessary in the B-tree.
594 *
595 * Return: Non-negative on success/Negative on failure
596 *
597 * Programmer: Pedro Vicente
598 * March 28, 2002
599 *
600 *-------------------------------------------------------------------------
601 */
602 static H5B_ins_t
H5D__btree_remove(H5F_t * f,haddr_t addr,void * _lt_key,hbool_t * lt_key_changed,void H5_ATTR_UNUSED * _udata,void H5_ATTR_UNUSED * _rt_key,hbool_t * rt_key_changed)603 H5D__btree_remove(H5F_t *f, haddr_t addr, void *_lt_key /*in,out */, hbool_t *lt_key_changed /*out */,
604 void H5_ATTR_UNUSED *_udata /*in,out */, void H5_ATTR_UNUSED *_rt_key /*in,out */,
605 hbool_t *rt_key_changed /*out */)
606 {
607 H5D_btree_key_t *lt_key = (H5D_btree_key_t *)_lt_key;
608 H5B_ins_t ret_value = H5B_INS_REMOVE; /* Return value */
609
610 FUNC_ENTER_STATIC
611
612 /* Remove raw data chunk from file */
613 H5_CHECK_OVERFLOW(lt_key->nbytes, uint32_t, hsize_t);
614 if (H5MF_xfree(f, H5FD_MEM_DRAW, addr, (hsize_t)lt_key->nbytes) < 0)
615 HGOTO_ERROR(H5E_STORAGE, H5E_CANTFREE, H5B_INS_ERROR, "unable to free chunk")
616
617 /* Mark keys as unchanged */
618 *lt_key_changed = FALSE;
619 *rt_key_changed = FALSE;
620
621 done:
622 FUNC_LEAVE_NOAPI(ret_value)
623 } /* end H5D__btree_remove() */
624
625 /*-------------------------------------------------------------------------
626 * Function: H5D__btree_decode_key
627 *
628 * Purpose: Decodes a raw key into a native key for the B-tree
629 *
630 * Return: Non-negative on success/Negative on failure
631 *
632 * Programmer: Robb Matzke
633 * Friday, October 10, 1997
634 *
635 *-------------------------------------------------------------------------
636 */
637 static herr_t
H5D__btree_decode_key(const H5B_shared_t * shared,const uint8_t * raw,void * _key)638 H5D__btree_decode_key(const H5B_shared_t *shared, const uint8_t *raw, void *_key)
639 {
640 const H5O_layout_chunk_t *layout; /* Chunk layout description */
641 H5D_btree_key_t * key = (H5D_btree_key_t *)_key; /* Pointer to decoded key */
642 hsize_t tmp_offset; /* Temporary coordinate offset, from file */
643 unsigned u; /* Local index variable */
644 herr_t ret_value = SUCCEED; /* Return value */
645
646 FUNC_ENTER_STATIC
647
648 /* check args */
649 HDassert(shared);
650 HDassert(raw);
651 HDassert(key);
652 layout = (const H5O_layout_chunk_t *)shared->udata;
653 HDassert(layout);
654 HDassert(layout->ndims > 0 && layout->ndims <= H5O_LAYOUT_NDIMS);
655
656 /* decode */
657 UINT32DECODE(raw, key->nbytes);
658 UINT32DECODE(raw, key->filter_mask);
659 for (u = 0; u < layout->ndims; u++) {
660 if (layout->dim[u] == 0)
661 HGOTO_ERROR(H5E_DATASET, H5E_BADVALUE, FAIL, "chunk size must be > 0, dim = %u ", u)
662
663 /* Retrieve coordinate offset */
664 UINT64DECODE(raw, tmp_offset);
665 HDassert(0 == (tmp_offset % layout->dim[u]));
666
667 /* Convert to a scaled offset */
668 key->scaled[u] = tmp_offset / layout->dim[u];
669 } /* end for */
670
671 done:
672 FUNC_LEAVE_NOAPI(ret_value)
673 } /* end H5D__btree_decode_key() */
674
675 /*-------------------------------------------------------------------------
676 * Function: H5D__btree_encode_key
677 *
678 * Purpose: Encode a key from native format to raw format.
679 *
680 * Return: Non-negative on success/Negative on failure
681 *
682 * Programmer: Robb Matzke
683 * Friday, October 10, 1997
684 *
685 *-------------------------------------------------------------------------
686 */
687 static herr_t
H5D__btree_encode_key(const H5B_shared_t * shared,uint8_t * raw,const void * _key)688 H5D__btree_encode_key(const H5B_shared_t *shared, uint8_t *raw, const void *_key)
689 {
690 const H5O_layout_chunk_t *layout; /* Chunk layout description */
691 const H5D_btree_key_t * key = (const H5D_btree_key_t *)_key;
692 hsize_t tmp_offset; /* Temporary coordinate offset, from file */
693 unsigned u; /* Local index variable */
694
695 FUNC_ENTER_STATIC_NOERR
696
697 /* check args */
698 HDassert(shared);
699 HDassert(raw);
700 HDassert(key);
701 layout = (const H5O_layout_chunk_t *)shared->udata;
702 HDassert(layout);
703 HDassert(layout->ndims > 0 && layout->ndims <= H5O_LAYOUT_NDIMS);
704
705 /* encode */
706 UINT32ENCODE(raw, key->nbytes);
707 UINT32ENCODE(raw, key->filter_mask);
708 for (u = 0; u < layout->ndims; u++) {
709 /* Compute coordinate offset from scaled offset */
710 tmp_offset = key->scaled[u] * layout->dim[u];
711 UINT64ENCODE(raw, tmp_offset);
712 } /* end for */
713
714 FUNC_LEAVE_NOAPI(SUCCEED)
715 } /* end H5D__btree_encode_key() */
716
717 /*-------------------------------------------------------------------------
718 * Function: H5D__btree_debug_key
719 *
720 * Purpose: Prints a key.
721 *
722 * Return: Non-negative on success/Negative on failure
723 *
724 * Programmer: Robb Matzke
725 * Thursday, April 16, 1998
726 *
727 *-------------------------------------------------------------------------
728 */
729 static herr_t
H5D__btree_debug_key(FILE * stream,int indent,int fwidth,const void * _key,const void * _udata)730 H5D__btree_debug_key(FILE *stream, int indent, int fwidth, const void *_key, const void *_udata)
731 {
732 const H5D_btree_key_t *key = (const H5D_btree_key_t *)_key;
733 const H5D_btree_dbg_t *udata = (const H5D_btree_dbg_t *)_udata;
734 unsigned u;
735
736 FUNC_ENTER_STATIC_NOERR
737
738 HDassert(key);
739
740 HDfprintf(stream, "%*s%-*s %u bytes\n", indent, "", fwidth, "Chunk size:", (unsigned)key->nbytes);
741 HDfprintf(stream, "%*s%-*s 0x%08x\n", indent, "", fwidth, "Filter mask:", key->filter_mask);
742 HDfprintf(stream, "%*s%-*s {", indent, "", fwidth, "Logical offset:");
743 for (u = 0; u < udata->ndims; u++)
744 HDfprintf(stream, "%s%" PRIuHSIZE, u ? ", " : "", (key->scaled[u] * udata->common.layout->dim[u]));
745 HDfputs("}\n", stream);
746
747 FUNC_LEAVE_NOAPI(SUCCEED)
748 } /* end H5D__btree_debug_key() */
749
750 /*-------------------------------------------------------------------------
751 * Function: H5D__btree_shared_free
752 *
753 * Purpose: Free "local" B-tree shared info
754 *
755 * Return: Non-negative on success/Negative on failure
756 *
757 * Programmer: Quincey Koziol
758 * Thursday, May 7, 2015
759 *
760 *-------------------------------------------------------------------------
761 */
762 static herr_t
H5D__btree_shared_free(void * _shared)763 H5D__btree_shared_free(void *_shared)
764 {
765 H5B_shared_t *shared = (H5B_shared_t *)_shared;
766 herr_t ret_value = SUCCEED; /* Return value */
767
768 FUNC_ENTER_STATIC
769
770 /* Free the chunk layout information */
771 shared->udata = H5FL_FREE(H5O_layout_chunk_t, shared->udata);
772
773 /* Chain up to the generic B-tree shared info free routine */
774 if (H5B_shared_free(shared) < 0)
775 HGOTO_ERROR(H5E_DATASET, H5E_CANTFREE, FAIL, "can't free shared B-tree info")
776
777 done:
778 FUNC_LEAVE_NOAPI(ret_value)
779 } /* end H5D__btree_shared_free() */
780
781 /*-------------------------------------------------------------------------
782 * Function: H5D__btree_shared_create
783 *
784 * Purpose: Create & initialize B-tree shared info
785 *
786 * Return: Non-negative on success/Negative on failure
787 *
788 * Programmer: Quincey Koziol
789 * Monday, September 27, 2004
790 *
791 *-------------------------------------------------------------------------
792 */
793 static herr_t
H5D__btree_shared_create(const H5F_t * f,H5O_storage_chunk_t * store,const H5O_layout_chunk_t * layout)794 H5D__btree_shared_create(const H5F_t *f, H5O_storage_chunk_t *store, const H5O_layout_chunk_t *layout)
795 {
796 H5B_shared_t * shared; /* Shared B-tree node info */
797 H5O_layout_chunk_t *my_layout = NULL; /* Pointer to copy of layout info */
798 size_t sizeof_rkey; /* Size of raw (disk) key */
799 herr_t ret_value = SUCCEED; /* Return value */
800
801 FUNC_ENTER_STATIC
802
803 /* Set the raw key size */
804 sizeof_rkey = 4 + /*storage size */
805 4 + /*filter mask */
806 layout->ndims * 8; /*dimension indices */
807
808 /* Allocate & initialize global info for the shared structure */
809 if (NULL == (shared = H5B_shared_new(f, H5B_BTREE, sizeof_rkey)))
810 HGOTO_ERROR(H5E_DATASET, H5E_NOSPACE, FAIL, "memory allocation failed for shared B-tree info")
811
812 /* Set up the "local" information for this dataset's chunks */
813 if (NULL == (my_layout = H5FL_MALLOC(H5O_layout_chunk_t)))
814 HGOTO_ERROR(H5E_DATASET, H5E_CANTALLOC, FAIL, "can't allocate chunk layout")
815 H5MM_memcpy(my_layout, layout, sizeof(H5O_layout_chunk_t));
816 shared->udata = my_layout;
817
818 /* Make shared B-tree info reference counted */
819 if (NULL == (store->u.btree.shared = H5UC_create(shared, H5D__btree_shared_free)))
820 HGOTO_ERROR(H5E_DATASET, H5E_NOSPACE, FAIL, "can't create ref-count wrapper for shared B-tree info")
821
822 done:
823 if (ret_value < 0)
824 if (my_layout)
825 my_layout = H5FL_FREE(H5O_layout_chunk_t, my_layout);
826
827 FUNC_LEAVE_NOAPI(ret_value)
828 } /* end H5D__btree_shared_create() */
829
830 /*-------------------------------------------------------------------------
831 * Function: H5D__btree_idx_init
832 *
833 * Purpose: Initialize the indexing information for a dataset.
834 *
835 * Return: Non-negative on success/Negative on failure
836 *
837 * Programmer: Robb Matzke
838 * Monday, May 18, 1998
839 *
840 *-------------------------------------------------------------------------
841 */
842 static herr_t
H5D__btree_idx_init(const H5D_chk_idx_info_t * idx_info,const H5S_t H5_ATTR_UNUSED * space,haddr_t dset_ohdr_addr)843 H5D__btree_idx_init(const H5D_chk_idx_info_t *idx_info, const H5S_t H5_ATTR_UNUSED *space,
844 haddr_t dset_ohdr_addr)
845 {
846 herr_t ret_value = SUCCEED; /* Return value */
847
848 FUNC_ENTER_STATIC
849
850 /* Check args */
851 HDassert(idx_info);
852 HDassert(idx_info->f);
853 HDassert(idx_info->pline);
854 HDassert(idx_info->layout);
855 HDassert(idx_info->storage);
856 HDassert(H5F_addr_defined(dset_ohdr_addr));
857
858 idx_info->storage->u.btree.dset_ohdr_addr = dset_ohdr_addr;
859
860 /* Allocate the shared structure */
861 if (H5D__btree_shared_create(idx_info->f, idx_info->storage, idx_info->layout) < 0)
862 HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create wrapper for shared B-tree info")
863
864 done:
865 FUNC_LEAVE_NOAPI(ret_value)
866 } /* end H5D__btree_idx_init() */
867
868 /*-------------------------------------------------------------------------
869 * Function: H5D__btree_idx_create
870 *
871 * Purpose: Creates a new indexed-storage B-tree and initializes the
872 * layout struct with information about the storage. The
873 * struct should be immediately written to the object header.
874 *
875 * This function must be called before passing LAYOUT to any of
876 * the other indexed storage functions!
877 *
878 * Return: Non-negative on success (with the LAYOUT argument initialized
879 * and ready to write to an object header). Negative on failure.
880 *
881 * Programmer: Robb Matzke
882 * Tuesday, October 21, 1997
883 *
884 *-------------------------------------------------------------------------
885 */
886 static herr_t
H5D__btree_idx_create(const H5D_chk_idx_info_t * idx_info)887 H5D__btree_idx_create(const H5D_chk_idx_info_t *idx_info)
888 {
889 H5D_chunk_common_ud_t udata; /* User data for B-tree callback */
890 herr_t ret_value = SUCCEED; /* Return value */
891
892 FUNC_ENTER_STATIC
893
894 /* Check args */
895 HDassert(idx_info);
896 HDassert(idx_info->f);
897 HDassert(idx_info->pline);
898 HDassert(idx_info->layout);
899 HDassert(idx_info->storage);
900 HDassert(!H5F_addr_defined(idx_info->storage->idx_addr));
901
902 /* Initialize "user" data for B-tree callbacks, etc. */
903 udata.layout = idx_info->layout;
904 udata.storage = idx_info->storage;
905
906 /* Create the v1 B-tree for the chunk index */
907 if (H5B_create(idx_info->f, H5B_BTREE, &udata, &(idx_info->storage->idx_addr) /*out*/) < 0)
908 HGOTO_ERROR(H5E_DATASET, H5E_CANTINIT, FAIL, "can't create B-tree")
909
910 done:
911 FUNC_LEAVE_NOAPI(ret_value)
912 } /* end H5D__btree_idx_create() */
913
914 /*-------------------------------------------------------------------------
915 * Function: H5D__btree_idx_is_space_alloc
916 *
917 * Purpose: Query if space is allocated for index method
918 *
919 * Return: Non-negative on success/Negative on failure
920 *
921 * Programmer: Quincey Koziol
922 * Thursday, January 15, 2009
923 *
924 *-------------------------------------------------------------------------
925 */
926 static hbool_t
H5D__btree_idx_is_space_alloc(const H5O_storage_chunk_t * storage)927 H5D__btree_idx_is_space_alloc(const H5O_storage_chunk_t *storage)
928 {
929 FUNC_ENTER_STATIC_NOERR
930
931 /* Check args */
932 HDassert(storage);
933
934 FUNC_LEAVE_NOAPI((hbool_t)H5F_addr_defined(storage->idx_addr))
935 } /* end H5D__btree_idx_is_space_alloc() */
936
937 /*-------------------------------------------------------------------------
938 * Function: H5D__btree_idx_insert
939 *
940 * Purpose: Insert chunk entry into the indexing structure.
941 *
942 * Return: Non-negative on success/Negative on failure
943 *
944 * Programmer: Robb Matzke
945 * Thursday, May 21, 1998
946 *
947 *-------------------------------------------------------------------------
948 */
949 static herr_t
H5D__btree_idx_insert(const H5D_chk_idx_info_t * idx_info,H5D_chunk_ud_t * udata,const H5D_t H5_ATTR_UNUSED * dset)950 H5D__btree_idx_insert(const H5D_chk_idx_info_t *idx_info, H5D_chunk_ud_t *udata,
951 const H5D_t H5_ATTR_UNUSED *dset)
952 {
953 herr_t ret_value = SUCCEED; /* Return value */
954
955 FUNC_ENTER_STATIC
956
957 HDassert(idx_info);
958 HDassert(idx_info->f);
959 HDassert(idx_info->pline);
960 HDassert(idx_info->layout);
961 HDassert(idx_info->storage);
962 HDassert(H5F_addr_defined(idx_info->storage->idx_addr));
963 HDassert(udata);
964
965 /*
966 * Create the chunk it if it doesn't exist, or reallocate the chunk if
967 * its size changed.
968 */
969 if (H5B_insert(idx_info->f, H5B_BTREE, idx_info->storage->idx_addr, udata) < 0)
970 HGOTO_ERROR(H5E_IO, H5E_WRITEERROR, FAIL, "unable to allocate chunk")
971
972 done:
973 FUNC_LEAVE_NOAPI(ret_value)
974 } /* H5D__btree_idx_insert() */
975
976 /*-------------------------------------------------------------------------
977 * Function: H5D__btree_idx_get_addr
978 *
979 * Purpose: Get the file address of a chunk if file space has been
980 * assigned. Save the retrieved information in the udata
981 * supplied.
982 *
983 * Return: Non-negative on success/Negative on failure
984 *
985 * Programmer: Albert Cheng
986 * June 27, 1998
987 *
988 *-------------------------------------------------------------------------
989 */
990 static herr_t
H5D__btree_idx_get_addr(const H5D_chk_idx_info_t * idx_info,H5D_chunk_ud_t * udata)991 H5D__btree_idx_get_addr(const H5D_chk_idx_info_t *idx_info, H5D_chunk_ud_t *udata)
992 {
993 herr_t ret_value = SUCCEED; /* Return value */
994
995 FUNC_ENTER_STATIC
996
997 HDassert(idx_info);
998 HDassert(idx_info->f);
999 HDassert(idx_info->pline);
1000 HDassert(idx_info->layout);
1001 HDassert(idx_info->layout->ndims > 0);
1002 HDassert(idx_info->storage);
1003 HDassert(H5F_addr_defined(idx_info->storage->idx_addr));
1004 HDassert(udata);
1005
1006 /* Go get the chunk information from the B-tree */
1007 if (H5B_find(idx_info->f, H5B_BTREE, idx_info->storage->idx_addr, udata) < 0)
1008 HGOTO_ERROR(H5E_DATASET, H5E_CANTGET, FAIL, "can't get chunk info")
1009
1010 done:
1011 FUNC_LEAVE_NOAPI(ret_value)
1012 } /* H5D__btree_idx_get_addr() */
1013
1014 /*-------------------------------------------------------------------------
1015 * Function: H5D__btree_idx_iterate_cb
1016 *
1017 * Purpose: Translate the B-tree specific chunk record into a generic
1018 * form and make the callback to the generic chunk callback
1019 * routine.
1020 *
1021 * Return: Success: Non-negative
1022 * Failure: Negative
1023 *
1024 * Programmer: Quincey Koziol
1025 * Tuesday, May 20, 2008
1026 *
1027 *-------------------------------------------------------------------------
1028 */
1029 static int
H5D__btree_idx_iterate_cb(H5F_t H5_ATTR_UNUSED * f,const void * _lt_key,haddr_t addr,const void H5_ATTR_UNUSED * _rt_key,void * _udata)1030 H5D__btree_idx_iterate_cb(H5F_t H5_ATTR_UNUSED *f, const void *_lt_key, haddr_t addr,
1031 const void H5_ATTR_UNUSED *_rt_key, void *_udata)
1032 {
1033 H5D_btree_it_ud_t * udata = (H5D_btree_it_ud_t *)_udata; /* User data */
1034 const H5D_btree_key_t *lt_key = (const H5D_btree_key_t *)_lt_key; /* B-tree key for chunk */
1035 H5D_chunk_rec_t chunk_rec; /* Generic chunk record for callback */
1036 int ret_value = -1; /* Return value */
1037
1038 FUNC_ENTER_STATIC_NOERR
1039
1040 /* Sanity check for memcpy() */
1041 HDcompile_assert(offsetof(H5D_chunk_rec_t, nbytes) == offsetof(H5D_btree_key_t, nbytes));
1042 HDcompile_assert(sizeof(chunk_rec.nbytes) == sizeof(lt_key->nbytes));
1043 HDcompile_assert(offsetof(H5D_chunk_rec_t, scaled) == offsetof(H5D_btree_key_t, scaled));
1044 HDcompile_assert(sizeof(chunk_rec.scaled) == sizeof(lt_key->scaled));
1045 HDcompile_assert(offsetof(H5D_chunk_rec_t, filter_mask) == offsetof(H5D_btree_key_t, filter_mask));
1046 HDcompile_assert(sizeof(chunk_rec.filter_mask) == sizeof(lt_key->filter_mask));
1047
1048 /* Compose generic chunk record for callback */
1049 H5MM_memcpy(&chunk_rec, lt_key, sizeof(*lt_key));
1050 chunk_rec.chunk_addr = addr;
1051
1052 /* Make "generic chunk" callback */
1053 if ((ret_value = (udata->cb)(&chunk_rec, udata->udata)) < 0)
1054 HERROR(H5E_DATASET, H5E_CALLBACK, "failure in generic chunk iterator callback");
1055
1056 FUNC_LEAVE_NOAPI(ret_value)
1057 } /* H5D__btree_idx_iterate_cb() */
1058
1059 /*-------------------------------------------------------------------------
1060 * Function: H5D__btree_idx_iterate
1061 *
1062 * Purpose: Iterate over the chunks in an index, making a callback
1063 * for each one.
1064 *
1065 * Return: Non-negative on success/Negative on failure
1066 *
1067 * Programmer: Quincey Koziol
1068 * Tuesday, May 20, 2008
1069 *
1070 *-------------------------------------------------------------------------
1071 */
1072 static int
H5D__btree_idx_iterate(const H5D_chk_idx_info_t * idx_info,H5D_chunk_cb_func_t chunk_cb,void * chunk_udata)1073 H5D__btree_idx_iterate(const H5D_chk_idx_info_t *idx_info, H5D_chunk_cb_func_t chunk_cb, void *chunk_udata)
1074 {
1075 H5D_btree_it_ud_t udata; /* User data for B-tree iterator callback */
1076 int ret_value = -1; /* Return value */
1077
1078 FUNC_ENTER_STATIC_NOERR
1079
1080 HDassert(idx_info);
1081 HDassert(idx_info->f);
1082 HDassert(idx_info->pline);
1083 HDassert(idx_info->layout);
1084 HDassert(idx_info->storage);
1085 HDassert(H5F_addr_defined(idx_info->storage->idx_addr));
1086 HDassert(chunk_cb);
1087 HDassert(chunk_udata);
1088
1089 /* Initialize userdata */
1090 HDmemset(&udata, 0, sizeof udata);
1091 udata.common.layout = idx_info->layout;
1092 udata.common.storage = idx_info->storage;
1093 udata.cb = chunk_cb;
1094 udata.udata = chunk_udata;
1095
1096 /* Iterate over existing chunks */
1097 if ((ret_value = H5B_iterate(idx_info->f, H5B_BTREE, idx_info->storage->idx_addr,
1098 H5D__btree_idx_iterate_cb, &udata)) < 0)
1099 HERROR(H5E_DATASET, H5E_BADITER, "unable to iterate over chunk B-tree");
1100
1101 FUNC_LEAVE_NOAPI(ret_value)
1102 } /* end H5D__btree_idx_iterate() */
1103
1104 /*-------------------------------------------------------------------------
1105 * Function: H5D__btree_idx_remove
1106 *
1107 * Purpose: Remove chunk from index.
1108 *
1109 * Return: Non-negative on success/Negative on failure
1110 *
1111 * Programmer: Quincey Koziol
1112 * Thursday, May 22, 2008
1113 *
1114 *-------------------------------------------------------------------------
1115 */
1116 static herr_t
H5D__btree_idx_remove(const H5D_chk_idx_info_t * idx_info,H5D_chunk_common_ud_t * udata)1117 H5D__btree_idx_remove(const H5D_chk_idx_info_t *idx_info, H5D_chunk_common_ud_t *udata)
1118 {
1119 herr_t ret_value = SUCCEED; /* Return value */
1120
1121 FUNC_ENTER_STATIC
1122
1123 HDassert(idx_info);
1124 HDassert(idx_info->f);
1125 HDassert(idx_info->pline);
1126 HDassert(idx_info->layout);
1127 HDassert(idx_info->storage);
1128 HDassert(H5F_addr_defined(idx_info->storage->idx_addr));
1129 HDassert(udata);
1130
1131 /* Remove the chunk from the v1 B-tree index and release the space for the
1132 * chunk (in the B-tree callback).
1133 */
1134 if (H5B_remove(idx_info->f, H5B_BTREE, idx_info->storage->idx_addr, udata) < 0)
1135 HGOTO_ERROR(H5E_DATASET, H5E_CANTDELETE, FAIL, "unable to remove chunk entry")
1136
1137 done:
1138 FUNC_LEAVE_NOAPI(ret_value)
1139 } /* H5D__btree_idx_remove() */
1140
1141 /*-------------------------------------------------------------------------
1142 * Function: H5D__btree_idx_delete
1143 *
1144 * Purpose: Delete index and raw data storage for entire dataset
1145 * (i.e. all chunks)
1146 *
1147 * Return: Success: Non-negative
1148 * Failure: negative
1149 *
1150 * Programmer: Quincey Koziol
1151 * Thursday, March 20, 2003
1152 *
1153 *-------------------------------------------------------------------------
1154 */
1155 static herr_t
H5D__btree_idx_delete(const H5D_chk_idx_info_t * idx_info)1156 H5D__btree_idx_delete(const H5D_chk_idx_info_t *idx_info)
1157 {
1158 herr_t ret_value = SUCCEED; /* Return value */
1159
1160 FUNC_ENTER_STATIC
1161
1162 /* Sanity checks */
1163 HDassert(idx_info);
1164 HDassert(idx_info->f);
1165 HDassert(idx_info->pline);
1166 HDassert(idx_info->layout);
1167 HDassert(idx_info->storage);
1168
1169 /* Check if the index data structure has been allocated */
1170 if (H5F_addr_defined(idx_info->storage->idx_addr)) {
1171 H5O_storage_chunk_t tmp_storage; /* Local copy of storage info */
1172 H5D_chunk_common_ud_t udata; /* User data for B-tree operations */
1173
1174 /* Set up temporary chunked storage info */
1175 tmp_storage = *idx_info->storage;
1176
1177 /* Set up the shared structure */
1178 if (H5D__btree_shared_create(idx_info->f, &tmp_storage, idx_info->layout) < 0)
1179 HGOTO_ERROR(H5E_DATASET, H5E_CANTINIT, FAIL, "can't create wrapper for shared B-tree info")
1180
1181 /* Set up B-tree user data */
1182 HDmemset(&udata, 0, sizeof udata);
1183 udata.layout = idx_info->layout;
1184 udata.storage = &tmp_storage;
1185
1186 /* Delete entire B-tree */
1187 if (H5B_delete(idx_info->f, H5B_BTREE, tmp_storage.idx_addr, &udata) < 0)
1188 HGOTO_ERROR(H5E_DATASET, H5E_CANTDELETE, FAIL, "unable to delete chunk B-tree")
1189
1190 /* Release the shared B-tree page */
1191 if (NULL == tmp_storage.u.btree.shared)
1192 HGOTO_ERROR(H5E_DATASET, H5E_CANTFREE, FAIL, "ref-counted page nil")
1193 if (H5UC_DEC(tmp_storage.u.btree.shared) < 0)
1194 HGOTO_ERROR(H5E_DATASET, H5E_CANTFREE, FAIL, "unable to decrement ref-counted page")
1195 } /* end if */
1196
1197 done:
1198 FUNC_LEAVE_NOAPI(ret_value)
1199 } /* end H5D__btree_idx_delete() */
1200
1201 /*-------------------------------------------------------------------------
1202 * Function: H5D__btree_idx_copy_setup
1203 *
1204 * Purpose: Set up any necessary information for copying chunks
1205 *
1206 * Return: Non-negative on success/Negative on failure
1207 *
1208 * Programmer: Quincey Koziol
1209 * Thursday, May 29, 2008
1210 *
1211 *-------------------------------------------------------------------------
1212 */
1213 static herr_t
H5D__btree_idx_copy_setup(const H5D_chk_idx_info_t * idx_info_src,const H5D_chk_idx_info_t * idx_info_dst)1214 H5D__btree_idx_copy_setup(const H5D_chk_idx_info_t *idx_info_src, const H5D_chk_idx_info_t *idx_info_dst)
1215 {
1216 herr_t ret_value = SUCCEED; /* Return value */
1217
1218 FUNC_ENTER_STATIC_TAG(H5AC__COPIED_TAG)
1219
1220 HDassert(idx_info_src);
1221 HDassert(idx_info_src->f);
1222 HDassert(idx_info_src->pline);
1223 HDassert(idx_info_src->layout);
1224 HDassert(idx_info_src->storage);
1225 HDassert(idx_info_dst);
1226 HDassert(idx_info_dst->f);
1227 HDassert(idx_info_dst->pline);
1228 HDassert(idx_info_dst->layout);
1229 HDassert(idx_info_dst->storage);
1230 HDassert(!H5F_addr_defined(idx_info_dst->storage->idx_addr));
1231
1232 /* Create shared B-tree info for each file */
1233 if (H5D__btree_shared_create(idx_info_src->f, idx_info_src->storage, idx_info_src->layout) < 0)
1234 HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create wrapper for source shared B-tree info")
1235 if (H5D__btree_shared_create(idx_info_dst->f, idx_info_dst->storage, idx_info_dst->layout) < 0)
1236 HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL,
1237 "can't create wrapper for destination shared B-tree info")
1238
1239 /* Create the root of the B-tree that describes chunked storage in the dest. file */
1240 if (H5D__btree_idx_create(idx_info_dst) < 0)
1241 HGOTO_ERROR(H5E_IO, H5E_CANTINIT, FAIL, "unable to initialize chunked storage")
1242 HDassert(H5F_addr_defined(idx_info_dst->storage->idx_addr));
1243
1244 done:
1245 FUNC_LEAVE_NOAPI_TAG(ret_value)
1246 } /* end H5D__btree_idx_copy_setup() */
1247
1248 /*-------------------------------------------------------------------------
1249 * Function: H5D__btree_idx_copy_shutdown
1250 *
1251 * Purpose: Shutdown any information from copying chunks
1252 *
1253 * Return: Non-negative on success/Negative on failure
1254 *
1255 * Programmer: Quincey Koziol
1256 * Thursday, May 29, 2008
1257 *
1258 *-------------------------------------------------------------------------
1259 */
1260 static herr_t
H5D__btree_idx_copy_shutdown(H5O_storage_chunk_t * storage_src,H5O_storage_chunk_t * storage_dst)1261 H5D__btree_idx_copy_shutdown(H5O_storage_chunk_t *storage_src, H5O_storage_chunk_t *storage_dst)
1262 {
1263 herr_t ret_value = SUCCEED; /* Return value */
1264
1265 FUNC_ENTER_STATIC
1266
1267 HDassert(storage_src);
1268 HDassert(storage_dst);
1269
1270 /* Decrement refcount on shared B-tree info */
1271 if (H5UC_DEC(storage_src->u.btree.shared) < 0)
1272 HGOTO_ERROR(H5E_DATASET, H5E_CANTDEC, FAIL, "unable to decrement ref-counted page")
1273 if (H5UC_DEC(storage_dst->u.btree.shared) < 0)
1274 HGOTO_ERROR(H5E_DATASET, H5E_CANTDEC, FAIL, "unable to decrement ref-counted page")
1275
1276 done:
1277 FUNC_LEAVE_NOAPI(ret_value)
1278 } /* end H5D__btree_idx_copy_shutdown() */
1279
1280 /*-------------------------------------------------------------------------
1281 * Function: H5D__btree_idx_size
1282 *
1283 * Purpose: Retrieve the amount of index storage for chunked dataset
1284 *
1285 * Return: Success: Non-negative
1286 * Failure: negative
1287 *
1288 * Programmer: Vailin Choi
1289 * June 8, 2007
1290 *
1291 *-------------------------------------------------------------------------
1292 */
1293 static herr_t
H5D__btree_idx_size(const H5D_chk_idx_info_t * idx_info,hsize_t * index_size)1294 H5D__btree_idx_size(const H5D_chk_idx_info_t *idx_info, hsize_t *index_size)
1295 {
1296 H5D_chunk_common_ud_t udata; /* User-data for loading B-tree nodes */
1297 H5B_info_t bt_info; /* B-tree info */
1298 herr_t ret_value = SUCCEED; /* Return value */
1299
1300 FUNC_ENTER_STATIC
1301
1302 /* Check args */
1303 HDassert(idx_info);
1304 HDassert(idx_info->f);
1305 HDassert(idx_info->pline);
1306 HDassert(idx_info->layout);
1307 HDassert(idx_info->storage);
1308 HDassert(index_size);
1309
1310 /* Initialize B-tree node user-data */
1311 HDmemset(&udata, 0, sizeof udata);
1312 udata.layout = idx_info->layout;
1313 udata.storage = idx_info->storage;
1314
1315 /* Get metadata information for B-tree */
1316 if (H5B_get_info(idx_info->f, H5B_BTREE, idx_info->storage->idx_addr, &bt_info, NULL, &udata) < 0)
1317 HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to iterate over chunk B-tree")
1318
1319 /* Set the size of the B-tree */
1320 *index_size = bt_info.size;
1321
1322 done:
1323 FUNC_LEAVE_NOAPI(ret_value)
1324 } /* end H5D__btree_idx_size() */
1325
1326 /*-------------------------------------------------------------------------
1327 * Function: H5D__btree_idx_reset
1328 *
1329 * Purpose: Reset indexing information.
1330 *
1331 * Return: Non-negative on success/Negative on failure
1332 *
1333 * Programmer: Quincey Koziol
1334 * Thursday, January 15, 2009
1335 *
1336 *-------------------------------------------------------------------------
1337 */
1338 static herr_t
H5D__btree_idx_reset(H5O_storage_chunk_t * storage,hbool_t reset_addr)1339 H5D__btree_idx_reset(H5O_storage_chunk_t *storage, hbool_t reset_addr)
1340 {
1341 FUNC_ENTER_STATIC_NOERR
1342
1343 HDassert(storage);
1344
1345 /* Reset index info */
1346 if (reset_addr)
1347 storage->idx_addr = HADDR_UNDEF;
1348 storage->u.btree.shared = NULL;
1349
1350 FUNC_LEAVE_NOAPI(SUCCEED)
1351 } /* end H5D__btree_idx_reset() */
1352
1353 /*-------------------------------------------------------------------------
1354 * Function: H5D__btree_idx_dump
1355 *
1356 * Purpose: Dump indexing information to a stream.
1357 *
1358 * Return: Non-negative on success/Negative on failure
1359 *
1360 * Programmer: Quincey Koziol
1361 * Thursday, January 15, 2009
1362 *
1363 *-------------------------------------------------------------------------
1364 */
1365 static herr_t
H5D__btree_idx_dump(const H5O_storage_chunk_t * storage,FILE * stream)1366 H5D__btree_idx_dump(const H5O_storage_chunk_t *storage, FILE *stream)
1367 {
1368 FUNC_ENTER_STATIC_NOERR
1369
1370 HDassert(storage);
1371 HDassert(stream);
1372
1373 HDfprintf(stream, " Address: %" PRIuHADDR "\n", storage->idx_addr);
1374
1375 FUNC_LEAVE_NOAPI(SUCCEED)
1376 } /* end H5D__btree_idx_dump() */
1377
1378 /*-------------------------------------------------------------------------
1379 * Function: H5D__btree_idx_dest
1380 *
1381 * Purpose: Release indexing information in memory.
1382 *
1383 * Return: Non-negative on success/Negative on failure
1384 *
1385 * Programmer: Robb Matzke
1386 * Thursday, May 21, 1998
1387 *
1388 *-------------------------------------------------------------------------
1389 */
1390 static herr_t
H5D__btree_idx_dest(const H5D_chk_idx_info_t * idx_info)1391 H5D__btree_idx_dest(const H5D_chk_idx_info_t *idx_info)
1392 {
1393 herr_t ret_value = SUCCEED; /* Return value */
1394
1395 FUNC_ENTER_STATIC
1396
1397 HDassert(idx_info);
1398 HDassert(idx_info->f);
1399 HDassert(idx_info->pline);
1400 HDassert(idx_info->layout);
1401 HDassert(idx_info->storage);
1402
1403 /* Free the raw B-tree node buffer */
1404 if (NULL == idx_info->storage->u.btree.shared)
1405 HGOTO_ERROR(H5E_IO, H5E_CANTFREE, FAIL, "ref-counted page nil")
1406 if (H5UC_DEC(idx_info->storage->u.btree.shared) < 0)
1407 HGOTO_ERROR(H5E_IO, H5E_CANTFREE, FAIL, "unable to decrement ref-counted page")
1408
1409 done:
1410 FUNC_LEAVE_NOAPI(ret_value)
1411 } /* end H5D__btree_idx_dest() */
1412
1413 /*-------------------------------------------------------------------------
1414 * Function: H5D_btree_debug
1415 *
1416 * Purpose: Debugs a B-tree node for indexed raw data storage.
1417 *
1418 * Return: Non-negative on success/Negative on failure
1419 *
1420 * Programmer: Robb Matzke
1421 * Thursday, April 16, 1998
1422 *
1423 *-------------------------------------------------------------------------
1424 */
1425 herr_t
H5D_btree_debug(H5F_t * f,haddr_t addr,FILE * stream,int indent,int fwidth,unsigned ndims,const uint32_t * dim)1426 H5D_btree_debug(H5F_t *f, haddr_t addr, FILE *stream, int indent, int fwidth, unsigned ndims,
1427 const uint32_t *dim)
1428 {
1429 H5D_btree_dbg_t udata; /* User data for B-tree callback */
1430 H5O_storage_chunk_t storage; /* Storage information for B-tree callback */
1431 H5O_layout_chunk_t layout; /* Layout information for B-tree callback */
1432 hbool_t shared_init = FALSE; /* Whether B-tree shared info is initialized */
1433 unsigned u; /* Local index variable */
1434 herr_t ret_value = SUCCEED; /* Return value */
1435
1436 FUNC_ENTER_NOAPI(FAIL)
1437
1438 /* Reset "fake" storage info */
1439 HDmemset(&storage, 0, sizeof(storage));
1440 storage.idx_type = H5D_CHUNK_IDX_BTREE;
1441
1442 /* Reset "fake" layout info */
1443 HDmemset(&layout, 0, sizeof(layout));
1444 layout.ndims = ndims;
1445 for (u = 0; u < ndims; u++)
1446 layout.dim[u] = dim[u];
1447
1448 /* Allocate the shared structure */
1449 if (H5D__btree_shared_create(f, &storage, &layout) < 0)
1450 HGOTO_ERROR(H5E_RESOURCE, H5E_CANTINIT, FAIL, "can't create wrapper for shared B-tree info")
1451 shared_init = TRUE;
1452
1453 /* Set up user data for callback */
1454 udata.common.layout = &layout;
1455 udata.common.storage = &storage;
1456 udata.common.scaled = NULL;
1457 udata.ndims = ndims;
1458
1459 /* Dump the records for the B-tree */
1460 (void)H5B_debug(f, addr, stream, indent, fwidth, H5B_BTREE, &udata);
1461
1462 done:
1463 if (shared_init) {
1464 /* Free the raw B-tree node buffer */
1465 if (NULL == storage.u.btree.shared)
1466 HDONE_ERROR(H5E_IO, H5E_CANTFREE, FAIL, "ref-counted shared info nil")
1467 else if (H5UC_DEC(storage.u.btree.shared) < 0)
1468 HDONE_ERROR(H5E_IO, H5E_CANTFREE, FAIL, "unable to decrement ref-counted shared info")
1469 } /* end if */
1470
1471 FUNC_LEAVE_NOAPI(ret_value)
1472 } /* end H5D_btree_debug() */
1473