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