Line | Count | Source (jump to first uncovered line) |
1 | | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * |
2 | | * Copyright by The HDF Group. * |
3 | | * All rights reserved. * |
4 | | * * |
5 | | * This file is part of HDF5. The full HDF5 copyright notice, including * |
6 | | * terms governing use, modification, and redistribution, is contained in * |
7 | | * the COPYING file, which can be found at the root of the source code * |
8 | | * distribution tree, or in https://www.hdfgroup.org/licenses. * |
9 | | * If you do not have access to either file, you may request a copy from * |
10 | | * help@hdfgroup.org. * |
11 | | * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
12 | | |
13 | | /*------------------------------------------------------------------------- |
14 | | * |
15 | | * Created: H5B2.c |
16 | | * |
17 | | * Purpose: Implements a B-tree, with several modifications from |
18 | | * the "standard" methods. |
19 | | * |
20 | | * Please see the documentation in: |
21 | | * doc/html/TechNotes/Btrees.html for a full description |
22 | | * of how they work, etc. |
23 | | * |
24 | | *------------------------------------------------------------------------- |
25 | | */ |
26 | | |
27 | | /****************/ |
28 | | /* Module Setup */ |
29 | | /****************/ |
30 | | |
31 | | #include "H5B2module.h" /* This source code file is part of the H5B2 module */ |
32 | | |
33 | | /***********/ |
34 | | /* Headers */ |
35 | | /***********/ |
36 | | #include "H5private.h" /* Generic Functions */ |
37 | | #include "H5B2pkg.h" /* v2 B-trees */ |
38 | | #include "H5Eprivate.h" /* Error handling */ |
39 | | #include "H5FLprivate.h" /* Free Lists */ |
40 | | #include "H5MMprivate.h" /* Memory management */ |
41 | | |
42 | | /****************/ |
43 | | /* Local Macros */ |
44 | | /****************/ |
45 | | |
46 | | /******************/ |
47 | | /* Local Typedefs */ |
48 | | /******************/ |
49 | | |
50 | | /********************/ |
51 | | /* Package Typedefs */ |
52 | | /********************/ |
53 | | |
54 | | /********************/ |
55 | | /* Local Prototypes */ |
56 | | /********************/ |
57 | | |
58 | | /*********************/ |
59 | | /* Package Variables */ |
60 | | /*********************/ |
61 | | |
62 | | /* v2 B-tree client ID to class mapping */ |
63 | | |
64 | | /* Remember to add client ID to H5B2_subid_t in H5B2private.h when adding a new |
65 | | * client class.. |
66 | | */ |
67 | | extern const H5B2_class_t H5B2_TEST[1]; |
68 | | extern const H5B2_class_t H5HF_HUGE_BT2_INDIR[1]; |
69 | | extern const H5B2_class_t H5HF_HUGE_BT2_FILT_INDIR[1]; |
70 | | extern const H5B2_class_t H5HF_HUGE_BT2_DIR[1]; |
71 | | extern const H5B2_class_t H5HF_HUGE_BT2_FILT_DIR[1]; |
72 | | extern const H5B2_class_t H5G_BT2_NAME[1]; |
73 | | extern const H5B2_class_t H5G_BT2_CORDER[1]; |
74 | | extern const H5B2_class_t H5SM_INDEX[1]; |
75 | | extern const H5B2_class_t H5A_BT2_NAME[1]; |
76 | | extern const H5B2_class_t H5A_BT2_CORDER[1]; |
77 | | extern const H5B2_class_t H5D_BT2[1]; |
78 | | extern const H5B2_class_t H5D_BT2_FILT[1]; |
79 | | extern const H5B2_class_t H5B2_TEST2[1]; |
80 | | |
81 | | const H5B2_class_t *const H5B2_client_class_g[] = { |
82 | | H5B2_TEST, /* 0 - H5B2_TEST_ID */ |
83 | | H5HF_HUGE_BT2_INDIR, /* 1 - H5B2_FHEAP_HUGE_INDIR_ID */ |
84 | | H5HF_HUGE_BT2_FILT_INDIR, /* 2 - H5B2_FHEAP_HUGE_FILT_INDIR_ID */ |
85 | | H5HF_HUGE_BT2_DIR, /* 3 - H5B2_FHEAP_HUGE_DIR_ID */ |
86 | | H5HF_HUGE_BT2_FILT_DIR, /* 4 - H5B2_FHEAP_HUGE_FILT_DIR_ID */ |
87 | | H5G_BT2_NAME, /* 5 - H5B2_GRP_DENSE_NAME_ID */ |
88 | | H5G_BT2_CORDER, /* 6 - H5B2_GRP_DENSE_CORDER_ID */ |
89 | | H5SM_INDEX, /* 7 - H5B2_SOHM_INDEX_ID */ |
90 | | H5A_BT2_NAME, /* 8 - H5B2_ATTR_DENSE_NAME_ID */ |
91 | | H5A_BT2_CORDER, /* 9 - H5B2_ATTR_DENSE_CORDER_ID */ |
92 | | H5D_BT2, /* 10 - H5B2_CDSET_ID */ |
93 | | H5D_BT2_FILT, /* 11 - H5B2_CDSET_FILT_ID */ |
94 | | H5B2_TEST2 /* 12 - H5B2_TEST_ID */ |
95 | | }; |
96 | | |
97 | | /*****************************/ |
98 | | /* Library Private Variables */ |
99 | | /*****************************/ |
100 | | |
101 | | /*******************/ |
102 | | /* Local Variables */ |
103 | | /*******************/ |
104 | | |
105 | | /* Declare a free list to manage the H5B2_t struct */ |
106 | | H5FL_DEFINE_STATIC(H5B2_t); |
107 | | |
108 | | /*------------------------------------------------------------------------- |
109 | | * Function: H5B2_create |
110 | | * |
111 | | * Purpose: Creates a new empty B-tree in the file. |
112 | | * |
113 | | * Return: Non-negative on success (with address of new B-tree |
114 | | * filled in), negative on failure |
115 | | * |
116 | | *------------------------------------------------------------------------- |
117 | | */ |
118 | | H5B2_t * |
119 | | H5B2_create(H5F_t *f, const H5B2_create_t *cparam, void *ctx_udata) |
120 | 0 | { |
121 | 0 | H5B2_t *bt2 = NULL; /* Pointer to the B-tree */ |
122 | 0 | H5B2_hdr_t *hdr = NULL; /* Pointer to the B-tree header */ |
123 | 0 | haddr_t hdr_addr; /* B-tree header address */ |
124 | 0 | H5B2_t *ret_value = NULL; /* Return value */ |
125 | |
|
126 | 0 | FUNC_ENTER_NOAPI(NULL) |
127 | | |
128 | | /* |
129 | | * Check arguments. |
130 | | */ |
131 | 0 | assert(f); |
132 | 0 | assert(cparam); |
133 | | |
134 | | /* H5B2 interface sanity check */ |
135 | 0 | HDcompile_assert(H5B2_NUM_BTREE_ID == NELMTS(H5B2_client_class_g)); |
136 | | |
137 | | /* Create shared v2 B-tree header */ |
138 | 0 | if (HADDR_UNDEF == (hdr_addr = H5B2__hdr_create(f, cparam, ctx_udata))) |
139 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, NULL, "can't create v2 B-tree header"); |
140 | | |
141 | | /* Create v2 B-tree wrapper */ |
142 | 0 | if (NULL == (bt2 = H5FL_MALLOC(H5B2_t))) |
143 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for v2 B-tree info"); |
144 | | |
145 | | /* Look up the B-tree header */ |
146 | 0 | if (NULL == (hdr = H5B2__hdr_protect(f, hdr_addr, ctx_udata, H5AC__NO_FLAGS_SET))) |
147 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to protect v2 B-tree header"); |
148 | | |
149 | | /* Point v2 B-tree wrapper at header and bump it's ref count */ |
150 | 0 | bt2->hdr = hdr; |
151 | 0 | if (H5B2__hdr_incr(bt2->hdr) < 0) |
152 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, |
153 | 0 | "can't increment reference count on shared v2 B-tree header"); |
154 | | |
155 | | /* Increment # of files using this v2 B-tree header */ |
156 | 0 | if (H5B2__hdr_fuse_incr(bt2->hdr) < 0) |
157 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, |
158 | 0 | "can't increment file reference count on shared v2 B-tree header"); |
159 | | |
160 | | /* Set file pointer for this v2 B-tree open context */ |
161 | 0 | bt2->f = f; |
162 | | |
163 | | /* Set the return value */ |
164 | 0 | ret_value = bt2; |
165 | |
|
166 | 0 | done: |
167 | 0 | if (hdr && H5B2__hdr_unprotect(hdr, H5AC__NO_FLAGS_SET) < 0) |
168 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, NULL, "unable to release v2 B-tree header"); |
169 | 0 | if (!ret_value && bt2) |
170 | 0 | if (H5B2_close(bt2) < 0) |
171 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTCLOSEOBJ, NULL, "unable to close v2 B-tree"); |
172 | |
|
173 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
174 | 0 | } /* end H5B2_create() */ |
175 | | |
176 | | /*------------------------------------------------------------------------- |
177 | | * Function: H5B2_open |
178 | | * |
179 | | * Purpose: Opens an existing v2 B-tree in the file. |
180 | | * |
181 | | * Return: Pointer to v2 B-tree wrapper on success |
182 | | * NULL on failure |
183 | | * |
184 | | *------------------------------------------------------------------------- |
185 | | */ |
186 | | H5B2_t * |
187 | | H5B2_open(H5F_t *f, haddr_t addr, void *ctx_udata) |
188 | 0 | { |
189 | 0 | H5B2_t *bt2 = NULL; /* Pointer to the B-tree */ |
190 | 0 | H5B2_hdr_t *hdr = NULL; /* Pointer to the B-tree header */ |
191 | 0 | H5B2_t *ret_value = NULL; /* Return value */ |
192 | |
|
193 | 0 | FUNC_ENTER_NOAPI_NOINIT |
194 | | |
195 | | /* Check arguments. */ |
196 | 0 | assert(f); |
197 | 0 | assert(H5_addr_defined(addr)); |
198 | | |
199 | | /* Look up the B-tree header */ |
200 | 0 | if (NULL == (hdr = H5B2__hdr_protect(f, addr, ctx_udata, H5AC__READ_ONLY_FLAG))) |
201 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, NULL, "unable to protect v2 B-tree header"); |
202 | | |
203 | | /* Check for pending heap deletion */ |
204 | 0 | if (hdr->pending_delete) |
205 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTOPENOBJ, NULL, "can't open v2 B-tree pending deletion"); |
206 | | |
207 | | /* Create v2 B-tree info */ |
208 | 0 | if (NULL == (bt2 = H5FL_MALLOC(H5B2_t))) |
209 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for v2 B-tree info"); |
210 | | |
211 | | /* Point v2 B-tree wrapper at header */ |
212 | 0 | bt2->hdr = hdr; |
213 | 0 | if (H5B2__hdr_incr(bt2->hdr) < 0) |
214 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, |
215 | 0 | "can't increment reference count on shared v2 B-tree header"); |
216 | | |
217 | | /* Increment # of files using this v2 B-tree header */ |
218 | 0 | if (H5B2__hdr_fuse_incr(bt2->hdr) < 0) |
219 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINC, NULL, |
220 | 0 | "can't increment file reference count on shared v2 B-tree header"); |
221 | | |
222 | | /* Set file pointer for this v2 B-tree open context */ |
223 | 0 | bt2->f = f; |
224 | | |
225 | | /* Set the return value */ |
226 | 0 | ret_value = bt2; |
227 | |
|
228 | 0 | done: |
229 | 0 | if (hdr && H5B2__hdr_unprotect(hdr, H5AC__NO_FLAGS_SET) < 0) |
230 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, NULL, "unable to release v2 B-tree header"); |
231 | 0 | if (!ret_value && bt2) |
232 | 0 | if (H5B2_close(bt2) < 0) |
233 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTCLOSEOBJ, NULL, "unable to close v2 B-tree"); |
234 | |
|
235 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
236 | 0 | } /* H5B2_open() */ |
237 | | |
238 | | /*------------------------------------------------------------------------- |
239 | | * Function: H5B2_insert |
240 | | * |
241 | | * Purpose: Adds a new record to the B-tree. |
242 | | * |
243 | | * Return: Non-negative on success/Negative on failure |
244 | | * |
245 | | *------------------------------------------------------------------------- |
246 | | */ |
247 | | herr_t |
248 | | H5B2_insert(H5B2_t *bt2, void *udata) |
249 | 0 | { |
250 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
251 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
252 | |
|
253 | 0 | FUNC_ENTER_NOAPI(FAIL) |
254 | | |
255 | | /* Check arguments. */ |
256 | 0 | assert(bt2); |
257 | 0 | assert(udata); |
258 | | |
259 | | /* Set the shared v2 B-tree header's file context for this operation */ |
260 | 0 | bt2->hdr->f = bt2->f; |
261 | | |
262 | | /* Get the v2 B-tree header */ |
263 | 0 | hdr = bt2->hdr; |
264 | | |
265 | | /* Insert the record */ |
266 | 0 | if (H5B2__insert(hdr, udata) < 0) |
267 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree"); |
268 | | |
269 | 0 | done: |
270 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
271 | 0 | } /* H5B2_insert() */ |
272 | | |
273 | | /*------------------------------------------------------------------------- |
274 | | * Function: H5B2_update |
275 | | * |
276 | | * Purpose: Insert or modify a record to the B-tree. |
277 | | * If the record exists already, it is modified as if H5B2_modify |
278 | | * was called). If it doesn't exist, it is inserted as if |
279 | | * H5B2_insert was called. |
280 | | * |
281 | | * Return: Non-negative on success/Negative on failure |
282 | | * |
283 | | *------------------------------------------------------------------------- |
284 | | */ |
285 | | herr_t |
286 | | H5B2_update(H5B2_t *bt2, void *udata, H5B2_modify_t op, void *op_data) |
287 | 0 | { |
288 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
289 | 0 | H5B2_update_status_t status = H5B2_UPDATE_UNKNOWN; /* Whether the record was inserted/modified */ |
290 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
291 | |
|
292 | 0 | FUNC_ENTER_NOAPI(FAIL) |
293 | | |
294 | | /* Check arguments. */ |
295 | 0 | assert(bt2); |
296 | 0 | assert(udata); |
297 | | |
298 | | /* Set the shared v2 B-tree header's file context for this operation */ |
299 | 0 | bt2->hdr->f = bt2->f; |
300 | | |
301 | | /* Get the v2 B-tree header */ |
302 | 0 | hdr = bt2->hdr; |
303 | | |
304 | | /* Check if the root node is allocated yet */ |
305 | 0 | if (!H5_addr_defined(hdr->root.addr)) { |
306 | | /* Create root node as leaf node in B-tree */ |
307 | 0 | if (H5B2__create_leaf(hdr, hdr, &(hdr->root)) < 0) |
308 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node"); |
309 | 0 | } /* end if */ |
310 | | |
311 | | /* Attempt to insert record into B-tree */ |
312 | 0 | if (hdr->depth > 0) { |
313 | 0 | if (H5B2__update_internal(hdr, hdr->depth, NULL, &hdr->root, &status, H5B2_POS_ROOT, hdr, udata, op, |
314 | 0 | op_data) < 0) |
315 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update record in B-tree internal node"); |
316 | 0 | } /* end if */ |
317 | 0 | else { |
318 | 0 | if (H5B2__update_leaf(hdr, &hdr->root, &status, H5B2_POS_ROOT, hdr, udata, op, op_data) < 0) |
319 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUPDATE, FAIL, "unable to update record in B-tree leaf node"); |
320 | 0 | } /* end else */ |
321 | | |
322 | | /* Sanity check */ |
323 | 0 | assert(H5B2_UPDATE_UNKNOWN != status); |
324 | | |
325 | | /* Use insert algorithm if nodes to leaf full */ |
326 | 0 | if (H5B2_UPDATE_INSERT_CHILD_FULL == status) { |
327 | 0 | if (H5B2__insert(hdr, udata) < 0) |
328 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B-tree"); |
329 | 0 | } /* end if */ |
330 | 0 | else if (H5B2_UPDATE_SHADOW_DONE == status || H5B2_UPDATE_INSERT_DONE == status) { |
331 | | /* Mark B-tree header as dirty */ |
332 | 0 | if (H5B2__hdr_dirty(hdr) < 0) |
333 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTMARKDIRTY, FAIL, "unable to mark B-tree header dirty"); |
334 | 0 | } /* end else-if */ |
335 | 0 | else { |
336 | | /* Sanity check */ |
337 | 0 | assert(H5B2_UPDATE_MODIFY_DONE == status); |
338 | 0 | } /* end else */ |
339 | | |
340 | 0 | done: |
341 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
342 | 0 | } /* H5B2_update() */ |
343 | | |
344 | | /*------------------------------------------------------------------------- |
345 | | * Function: H5B2_get_addr |
346 | | * |
347 | | * Purpose: Get the address of a v2 B-tree |
348 | | * |
349 | | * Return: SUCCEED/FAIL |
350 | | * |
351 | | *------------------------------------------------------------------------- |
352 | | */ |
353 | | herr_t |
354 | | H5B2_get_addr(const H5B2_t *bt2, haddr_t *addr_p) |
355 | 0 | { |
356 | 0 | FUNC_ENTER_NOAPI_NOERR |
357 | | |
358 | | /* |
359 | | * Check arguments. |
360 | | */ |
361 | 0 | assert(bt2); |
362 | 0 | assert(addr_p); |
363 | | |
364 | | /* Retrieve the header address for this v2 B-tree */ |
365 | 0 | *addr_p = bt2->hdr->addr; |
366 | |
|
367 | 0 | FUNC_LEAVE_NOAPI(SUCCEED) |
368 | 0 | } /* end H5B2_get_addr() */ |
369 | | |
370 | | /*------------------------------------------------------------------------- |
371 | | * Function: H5B2_iterate |
372 | | * |
373 | | * Purpose: Iterate over all the records in the B-tree, in "in-order" |
374 | | * order, making a callback for each record. |
375 | | * |
376 | | * If the callback returns non-zero, the iteration breaks out |
377 | | * without finishing all the records. |
378 | | * |
379 | | * Return: Value from callback: non-negative on success, negative on error |
380 | | * |
381 | | *------------------------------------------------------------------------- |
382 | | */ |
383 | | herr_t |
384 | | H5B2_iterate(H5B2_t *bt2, H5B2_operator_t op, void *op_data) |
385 | 0 | { |
386 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
387 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
388 | |
|
389 | 0 | FUNC_ENTER_NOAPI_NOERR |
390 | | |
391 | | /* Check arguments. */ |
392 | 0 | assert(bt2); |
393 | 0 | assert(op); |
394 | | |
395 | | /* Set the shared v2 B-tree header's file context for this operation */ |
396 | 0 | bt2->hdr->f = bt2->f; |
397 | | |
398 | | /* Get the v2 B-tree header */ |
399 | 0 | hdr = bt2->hdr; |
400 | | |
401 | | /* Iterate through records */ |
402 | 0 | if (hdr->root.node_nrec > 0) |
403 | | /* Iterate through nodes */ |
404 | 0 | if ((ret_value = H5B2__iterate_node(hdr, hdr->depth, &hdr->root, hdr, op, op_data)) < 0) |
405 | 0 | HERROR(H5E_BTREE, H5E_CANTLIST, "node iteration failed"); |
406 | |
|
407 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
408 | 0 | } /* H5B2_iterate() */ |
409 | | |
410 | | /*------------------------------------------------------------------------- |
411 | | * Function: H5B2_find |
412 | | * |
413 | | * Purpose: Locate the specified information in a B-tree and return |
414 | | * that information by calling the provided 'OP' routine with an |
415 | | * OP_DATA pointer. The UDATA parameter points to data passed |
416 | | * to the key comparison function. |
417 | | * |
418 | | * The 'OP' routine is called with the record found and the |
419 | | * OP_DATA pointer, to allow caller to return information about |
420 | | * the record. |
421 | | * |
422 | | * If 'OP' is NULL, then this routine just returns true when |
423 | | * a record is present in the B-tree. |
424 | | * |
425 | | * Return: SUCCEED/FAIL |
426 | | * |
427 | | *------------------------------------------------------------------------- |
428 | | */ |
429 | | herr_t |
430 | | H5B2_find(H5B2_t *bt2, void *udata, bool *found, H5B2_found_t op, void *op_data) |
431 | 0 | { |
432 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
433 | 0 | H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */ |
434 | 0 | void *parent = NULL; /* Parent of current node */ |
435 | 0 | uint16_t depth; /* Current depth of the tree */ |
436 | 0 | int cmp; /* Comparison value of records */ |
437 | 0 | unsigned idx; /* Location of record which matches key */ |
438 | 0 | H5B2_nodepos_t curr_pos; /* Position of the current node */ |
439 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
440 | |
|
441 | 0 | FUNC_ENTER_NOAPI(FAIL) |
442 | | |
443 | | /* Check arguments. */ |
444 | 0 | assert(bt2); |
445 | 0 | assert(found); |
446 | | |
447 | | /* Set the shared v2 B-tree header's file context for this operation */ |
448 | 0 | bt2->hdr->f = bt2->f; |
449 | | |
450 | | /* Get the v2 B-tree header */ |
451 | 0 | hdr = bt2->hdr; |
452 | | |
453 | | /* Make copy of the root node pointer to start search with */ |
454 | 0 | curr_node_ptr = hdr->root; |
455 | | |
456 | | /* Check for empty tree */ |
457 | 0 | if (curr_node_ptr.node_nrec == 0) { |
458 | 0 | *found = false; |
459 | 0 | HGOTO_DONE(SUCCEED); |
460 | 0 | } |
461 | | |
462 | | /* Check record against min & max records in tree, to attempt to quickly |
463 | | * find candidates or avoid further searching. |
464 | | */ |
465 | 0 | if (hdr->min_native_rec != NULL) { |
466 | 0 | if ((hdr->cls->compare)(udata, hdr->min_native_rec, &cmp) < 0) |
467 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
468 | 0 | if (cmp < 0) { |
469 | 0 | *found = false; /* Less than the least record--not found */ |
470 | 0 | HGOTO_DONE(SUCCEED); |
471 | 0 | } |
472 | 0 | else if (cmp == 0) { /* Record is found */ |
473 | 0 | if (op && (op)(hdr->min_native_rec, op_data) < 0) |
474 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
475 | 0 | "'found' callback failed for B-tree find operation"); |
476 | 0 | *found = true; |
477 | 0 | HGOTO_DONE(SUCCEED); |
478 | 0 | } /* end if */ |
479 | 0 | } /* end if */ |
480 | 0 | if (hdr->max_native_rec != NULL) { |
481 | 0 | if ((hdr->cls->compare)(udata, hdr->max_native_rec, &cmp) < 0) |
482 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
483 | 0 | if (cmp > 0) { |
484 | 0 | *found = false; /* Greater than the largest record--not found */ |
485 | 0 | HGOTO_DONE(SUCCEED); |
486 | 0 | } |
487 | 0 | else if (cmp == 0) { /* Record is found */ |
488 | 0 | if (op && (op)(hdr->max_native_rec, op_data) < 0) |
489 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
490 | 0 | "'found' callback failed for B-tree find operation"); |
491 | 0 | *found = true; |
492 | 0 | HGOTO_DONE(SUCCEED); |
493 | 0 | } /* end if */ |
494 | 0 | } /* end if */ |
495 | | |
496 | | /* Current depth of the tree */ |
497 | 0 | depth = hdr->depth; |
498 | | |
499 | | /* Set initial parent, if doing swmr writes */ |
500 | 0 | if (hdr->swmr_write) |
501 | 0 | parent = hdr; |
502 | | |
503 | | /* Walk down B-tree to find record or leaf node where record is located */ |
504 | 0 | cmp = -1; |
505 | 0 | curr_pos = H5B2_POS_ROOT; |
506 | 0 | while (depth > 0) { |
507 | 0 | H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ |
508 | 0 | H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ |
509 | | |
510 | | /* Lock B-tree current node */ |
511 | 0 | if (NULL == (internal = H5B2__protect_internal(hdr, parent, &curr_node_ptr, depth, false, |
512 | 0 | H5AC__READ_ONLY_FLAG))) |
513 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node"); |
514 | | |
515 | | /* Unpin parent if necessary */ |
516 | 0 | if (parent) { |
517 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
518 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
519 | 0 | parent = NULL; |
520 | 0 | } /* end if */ |
521 | | |
522 | | /* Locate node pointer for child */ |
523 | 0 | if (H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx, |
524 | 0 | &cmp) < 0) { |
525 | | /* Unlock current node before failing */ |
526 | 0 | H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET); |
527 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
528 | 0 | } /* end if */ |
529 | | |
530 | 0 | if (cmp > 0) |
531 | 0 | idx++; |
532 | 0 | if (cmp != 0) { |
533 | | /* Get node pointer for next node to search */ |
534 | 0 | next_node_ptr = internal->node_ptrs[idx]; |
535 | | |
536 | | /* Set the position of the next node */ |
537 | 0 | if (H5B2_POS_MIDDLE != curr_pos) { |
538 | 0 | if (idx == 0) { |
539 | 0 | if (H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) |
540 | 0 | curr_pos = H5B2_POS_LEFT; |
541 | 0 | else |
542 | 0 | curr_pos = H5B2_POS_MIDDLE; |
543 | 0 | } /* end if */ |
544 | 0 | else if (idx == internal->nrec) { |
545 | 0 | if (H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) |
546 | 0 | curr_pos = H5B2_POS_RIGHT; |
547 | 0 | else |
548 | 0 | curr_pos = H5B2_POS_MIDDLE; |
549 | 0 | } /* end if */ |
550 | 0 | else |
551 | 0 | curr_pos = H5B2_POS_MIDDLE; |
552 | 0 | } /* end if */ |
553 | | |
554 | | /* Unlock current node */ |
555 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, |
556 | 0 | (unsigned)(hdr->swmr_write ? H5AC__PIN_ENTRY_FLAG : H5AC__NO_FLAGS_SET)) < 0) |
557 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
558 | | |
559 | | /* Keep track of parent if necessary */ |
560 | 0 | if (hdr->swmr_write) |
561 | 0 | parent = internal; |
562 | | |
563 | | /* Set pointer to next node to load */ |
564 | 0 | curr_node_ptr = next_node_ptr; |
565 | 0 | } /* end if */ |
566 | 0 | else { |
567 | | /* Make callback for current record */ |
568 | 0 | if (op && (op)(H5B2_INT_NREC(internal, hdr, idx), op_data) < 0) { |
569 | | /* Unlock current node */ |
570 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < |
571 | 0 | 0) |
572 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
573 | | |
574 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
575 | 0 | "'found' callback failed for B-tree find operation"); |
576 | 0 | } /* end if */ |
577 | | |
578 | | /* Unlock current node */ |
579 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < 0) |
580 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
581 | | |
582 | | /* Indicate record found */ |
583 | 0 | *found = true; |
584 | 0 | HGOTO_DONE(SUCCEED); |
585 | 0 | } /* end else */ |
586 | | |
587 | | /* Decrement depth we're at in B-tree */ |
588 | 0 | depth--; |
589 | 0 | } /* end while */ |
590 | | |
591 | 0 | { |
592 | 0 | H5B2_leaf_t *leaf; /* Pointer to leaf node in B-tree */ |
593 | | |
594 | | /* Lock B-tree leaf node */ |
595 | 0 | if (NULL == (leaf = H5B2__protect_leaf(hdr, parent, &curr_node_ptr, false, H5AC__READ_ONLY_FLAG))) |
596 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node"); |
597 | | |
598 | | /* Unpin parent if necessary */ |
599 | 0 | if (parent) { |
600 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
601 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
602 | 0 | parent = NULL; |
603 | 0 | } /* end if */ |
604 | | |
605 | | /* Locate record */ |
606 | 0 | if (H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < |
607 | 0 | 0) { |
608 | | /* Unlock current node before failing */ |
609 | 0 | H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET); |
610 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
611 | 0 | } /* end if */ |
612 | | |
613 | 0 | if (cmp != 0) { |
614 | | /* Unlock leaf node */ |
615 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
616 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
617 | | |
618 | | /* Record not found */ |
619 | 0 | *found = false; |
620 | 0 | HGOTO_DONE(SUCCEED); |
621 | 0 | } /* end if */ |
622 | 0 | else { |
623 | | /* Make callback for current record */ |
624 | 0 | if (op && (op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0) { |
625 | | /* Unlock current node */ |
626 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
627 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
628 | | |
629 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
630 | 0 | "'found' callback failed for B-tree find operation"); |
631 | 0 | } /* end if */ |
632 | | |
633 | | /* Check for record being the min or max for the tree */ |
634 | | /* (Don't use 'else' for the idx check, to allow for root leaf node) */ |
635 | 0 | if (H5B2_POS_MIDDLE != curr_pos) { |
636 | 0 | if (idx == 0) { |
637 | 0 | if (H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { |
638 | 0 | if (hdr->min_native_rec == NULL) |
639 | 0 | if (NULL == (hdr->min_native_rec = H5MM_malloc(hdr->cls->nrec_size))) |
640 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, |
641 | 0 | "memory allocation failed for v2 B-tree min record info"); |
642 | 0 | H5MM_memcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); |
643 | 0 | } /* end if */ |
644 | 0 | } /* end if */ |
645 | 0 | if (idx == (unsigned)(leaf->nrec - 1)) { |
646 | 0 | if (H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { |
647 | 0 | if (hdr->max_native_rec == NULL) |
648 | 0 | if (NULL == (hdr->max_native_rec = H5MM_malloc(hdr->cls->nrec_size))) |
649 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, |
650 | 0 | "memory allocation failed for v2 B-tree max record info"); |
651 | 0 | H5MM_memcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); |
652 | 0 | } /* end if */ |
653 | 0 | } /* end if */ |
654 | 0 | } /* end if */ |
655 | 0 | } /* end else */ |
656 | | |
657 | | /* Unlock current node */ |
658 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
659 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
660 | | |
661 | | /* Indicate record found */ |
662 | 0 | *found = true; |
663 | 0 | } /* end block */ |
664 | | |
665 | 0 | done: |
666 | 0 | if (parent) { |
667 | 0 | assert(ret_value < 0); |
668 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
669 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
670 | 0 | } /* end if */ |
671 | |
|
672 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
673 | 0 | } /* H5B2_find() */ |
674 | | |
675 | | /*------------------------------------------------------------------------- |
676 | | * Function: H5B2_index |
677 | | * |
678 | | * Purpose: Locate the IDX'th record in a B-tree according to the |
679 | | * ordering used by the B-tree. The IDX values are 0-based. |
680 | | * |
681 | | * The 'OP' routine is called with the record found and the |
682 | | * OP_DATA pointer, to allow caller to return information about |
683 | | * the record. |
684 | | * |
685 | | * Return: Non-negative on success, negative on failure. |
686 | | * |
687 | | *------------------------------------------------------------------------- |
688 | | */ |
689 | | herr_t |
690 | | H5B2_index(H5B2_t *bt2, H5_iter_order_t order, hsize_t idx, H5B2_found_t op, void *op_data) |
691 | 0 | { |
692 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
693 | 0 | H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */ |
694 | 0 | void *parent = NULL; /* Parent of current node */ |
695 | 0 | uint16_t depth; /* Current depth of the tree */ |
696 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
697 | |
|
698 | 0 | FUNC_ENTER_NOAPI(FAIL) |
699 | | |
700 | | /* Check arguments. */ |
701 | 0 | assert(bt2); |
702 | 0 | assert(op); |
703 | | |
704 | | /* Set the shared v2 B-tree header's file context for this operation */ |
705 | 0 | bt2->hdr->f = bt2->f; |
706 | | |
707 | | /* Get the v2 B-tree header */ |
708 | 0 | hdr = bt2->hdr; |
709 | | |
710 | | /* Make copy of the root node pointer to start search with */ |
711 | 0 | curr_node_ptr = hdr->root; |
712 | | |
713 | | /* Check for empty tree */ |
714 | 0 | if (curr_node_ptr.node_nrec == 0) |
715 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records"); |
716 | | |
717 | | /* Check for index greater than the number of records in the tree */ |
718 | 0 | if (idx >= curr_node_ptr.all_nrec) |
719 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records"); |
720 | | |
721 | | /* Current depth of the tree */ |
722 | 0 | depth = hdr->depth; |
723 | | |
724 | | /* Set initial parent, if doing swmr writes */ |
725 | 0 | if (hdr->swmr_write) |
726 | 0 | parent = hdr; |
727 | | |
728 | | /* Check for reverse indexing and map requested index to appropriate forward index */ |
729 | 0 | if (order == H5_ITER_DEC) |
730 | 0 | idx = curr_node_ptr.all_nrec - (idx + 1); |
731 | | |
732 | | /* Walk down B-tree to find record or leaf node where record is located */ |
733 | 0 | while (depth > 0) { |
734 | 0 | H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ |
735 | 0 | H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ |
736 | 0 | unsigned u; /* Local index variable */ |
737 | | |
738 | | /* Lock B-tree current node */ |
739 | 0 | if (NULL == (internal = H5B2__protect_internal(hdr, parent, &curr_node_ptr, depth, false, |
740 | 0 | H5AC__READ_ONLY_FLAG))) |
741 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node"); |
742 | | |
743 | | /* Unpin parent if necessary */ |
744 | 0 | if (parent) { |
745 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
746 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
747 | 0 | parent = NULL; |
748 | 0 | } /* end if */ |
749 | | |
750 | | /* Search for record with correct index */ |
751 | 0 | for (u = 0; u < internal->nrec; u++) { |
752 | | /* Check if record is in child node */ |
753 | 0 | if (internal->node_ptrs[u].all_nrec > idx) { |
754 | | /* Get node pointer for next node to search */ |
755 | 0 | next_node_ptr = internal->node_ptrs[u]; |
756 | | |
757 | | /* Unlock current node */ |
758 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, |
759 | 0 | (unsigned)(hdr->swmr_write ? H5AC__PIN_ENTRY_FLAG : H5AC__NO_FLAGS_SET)) < |
760 | 0 | 0) |
761 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
762 | | |
763 | | /* Keep track of parent if necessary */ |
764 | 0 | if (hdr->swmr_write) |
765 | 0 | parent = internal; |
766 | | |
767 | | /* Set pointer to next node to load */ |
768 | 0 | curr_node_ptr = next_node_ptr; |
769 | | |
770 | | /* Break out of for loop */ |
771 | 0 | break; |
772 | 0 | } /* end if */ |
773 | | |
774 | | /* Check if record is in this node */ |
775 | 0 | if (internal->node_ptrs[u].all_nrec == idx) { |
776 | | /* Make callback for current record */ |
777 | 0 | if ((op)(H5B2_INT_NREC(internal, hdr, u), op_data) < 0) { |
778 | | /* Unlock current node */ |
779 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, |
780 | 0 | H5AC__NO_FLAGS_SET) < 0) |
781 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
782 | | |
783 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
784 | 0 | "'found' callback failed for B-tree find operation"); |
785 | 0 | } /* end if */ |
786 | | |
787 | | /* Unlock current node */ |
788 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < |
789 | 0 | 0) |
790 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
791 | | |
792 | 0 | HGOTO_DONE(SUCCEED); |
793 | 0 | } /* end if */ |
794 | | |
795 | | /* Decrement index we are looking for to account for the node we |
796 | | * just advanced past. |
797 | | */ |
798 | 0 | idx -= (internal->node_ptrs[u].all_nrec + 1); |
799 | 0 | } /* end for */ |
800 | | |
801 | | /* Check last node pointer */ |
802 | 0 | if (u == internal->nrec) { |
803 | | /* Check if record is in child node */ |
804 | 0 | if (internal->node_ptrs[u].all_nrec > idx) { |
805 | | /* Get node pointer for next node to search */ |
806 | 0 | next_node_ptr = internal->node_ptrs[u]; |
807 | | |
808 | | /* Unlock current node */ |
809 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, |
810 | 0 | (unsigned)(hdr->swmr_write ? H5AC__PIN_ENTRY_FLAG : H5AC__NO_FLAGS_SET)) < |
811 | 0 | 0) |
812 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
813 | | |
814 | | /* Keep track of parent if necessary */ |
815 | 0 | if (hdr->swmr_write) |
816 | 0 | parent = internal; |
817 | | |
818 | | /* Set pointer to next node to load */ |
819 | 0 | curr_node_ptr = next_node_ptr; |
820 | 0 | } /* end if */ |
821 | 0 | else |
822 | | /* Index that is greater than the number of records in the tree? */ |
823 | 0 | assert(0 && "Index off end of tree??"); |
824 | 0 | } /* end if */ |
825 | | |
826 | | /* Decrement depth we're at in B-tree */ |
827 | 0 | depth--; |
828 | 0 | } /* end while */ |
829 | | |
830 | 0 | { |
831 | 0 | H5B2_leaf_t *leaf; /* Pointer to leaf node in B-tree */ |
832 | | |
833 | | /* Lock B-tree leaf node */ |
834 | 0 | if (NULL == (leaf = H5B2__protect_leaf(hdr, parent, &curr_node_ptr, false, H5AC__READ_ONLY_FLAG))) |
835 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node"); |
836 | | |
837 | | /* Unpin parent if necessary */ |
838 | 0 | if (parent) { |
839 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
840 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
841 | 0 | parent = NULL; |
842 | 0 | } /* end if */ |
843 | | |
844 | | /* Sanity check index */ |
845 | 0 | assert(idx < leaf->nrec); |
846 | | |
847 | | /* Make callback for correct record */ |
848 | 0 | if ((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data) < 0) { |
849 | | /* Unlock current node */ |
850 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
851 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
852 | | |
853 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "'found' callback failed for B-tree find operation"); |
854 | 0 | } /* end if */ |
855 | | |
856 | | /* Unlock current node */ |
857 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
858 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
859 | 0 | } /* end block */ |
860 | | |
861 | 0 | done: |
862 | 0 | if (parent) { |
863 | 0 | assert(ret_value < 0); |
864 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
865 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
866 | 0 | } /* end if */ |
867 | |
|
868 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
869 | 0 | } /* H5B2_index() */ |
870 | | |
871 | | /*------------------------------------------------------------------------- |
872 | | * Function: H5B2_remove |
873 | | * |
874 | | * Purpose: Removes a record from a B-tree. |
875 | | * |
876 | | * Return: Non-negative on success/Negative on failure |
877 | | * |
878 | | *------------------------------------------------------------------------- |
879 | | */ |
880 | | herr_t |
881 | | H5B2_remove(H5B2_t *bt2, void *udata, H5B2_remove_t op, void *op_data) |
882 | 0 | { |
883 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
884 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
885 | |
|
886 | 0 | FUNC_ENTER_NOAPI(FAIL) |
887 | | |
888 | | /* Check arguments. */ |
889 | 0 | assert(bt2); |
890 | | |
891 | | /* Set the shared v2 B-tree header's file context for this operation */ |
892 | 0 | bt2->hdr->f = bt2->f; |
893 | | |
894 | | /* Get the v2 B-tree header */ |
895 | 0 | hdr = bt2->hdr; |
896 | | |
897 | | /* Check for empty B-tree */ |
898 | 0 | if (0 == hdr->root.all_nrec) |
899 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree"); |
900 | | |
901 | | /* Attempt to remove record from B-tree */ |
902 | 0 | if (hdr->depth > 0) { |
903 | 0 | bool depth_decreased = false; /* Flag to indicate whether the depth of the B-tree decreased */ |
904 | |
|
905 | 0 | if (H5B2__remove_internal(hdr, &depth_decreased, NULL, NULL, hdr->depth, &(hdr->cache_info), NULL, |
906 | 0 | H5B2_POS_ROOT, &hdr->root, udata, op, op_data) < 0) |
907 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node"); |
908 | | |
909 | | /* Check for decreasing the depth of the B-tree */ |
910 | 0 | if (depth_decreased) { |
911 | | /* Destroy free list factories for previous depth */ |
912 | 0 | if (hdr->node_info[hdr->depth].nat_rec_fac) |
913 | 0 | if (H5FL_fac_term(hdr->node_info[hdr->depth].nat_rec_fac) < 0) |
914 | 0 | HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, |
915 | 0 | "can't destroy node's native record block factory"); |
916 | 0 | if (hdr->node_info[hdr->depth].node_ptr_fac) |
917 | 0 | if (H5FL_fac_term(hdr->node_info[hdr->depth].node_ptr_fac) < 0) |
918 | 0 | HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, |
919 | 0 | "can't destroy node's node pointer block factory"); |
920 | | |
921 | 0 | assert((uint16_t)(hdr->depth - depth_decreased) < hdr->depth); |
922 | 0 | hdr->depth = (uint16_t)(hdr->depth - depth_decreased); |
923 | 0 | } /* end for */ |
924 | 0 | } /* end if */ |
925 | 0 | else { |
926 | 0 | if (H5B2__remove_leaf(hdr, &hdr->root, H5B2_POS_ROOT, hdr, udata, op, op_data) < 0) |
927 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node"); |
928 | 0 | } /* end else */ |
929 | | |
930 | | /* Decrement # of records in B-tree */ |
931 | 0 | hdr->root.all_nrec--; |
932 | | |
933 | | /* Mark B-tree header as dirty */ |
934 | 0 | if (H5B2__hdr_dirty(hdr) < 0) |
935 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTMARKDIRTY, FAIL, "unable to mark B-tree header dirty"); |
936 | | |
937 | 0 | done: |
938 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
939 | 0 | } /* H5B2_remove() */ |
940 | | |
941 | | /*------------------------------------------------------------------------- |
942 | | * Function: H5B2_remove_by_idx |
943 | | * |
944 | | * Purpose: Removes the n'th record from a B-tree. |
945 | | * |
946 | | * Return: Non-negative on success/Negative on failure |
947 | | * |
948 | | *------------------------------------------------------------------------- |
949 | | */ |
950 | | herr_t |
951 | | H5B2_remove_by_idx(H5B2_t *bt2, H5_iter_order_t order, hsize_t idx, H5B2_remove_t op, void *op_data) |
952 | 0 | { |
953 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
954 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
955 | |
|
956 | 0 | FUNC_ENTER_NOAPI(FAIL) |
957 | | |
958 | | /* Check arguments. */ |
959 | 0 | assert(bt2); |
960 | | |
961 | | /* Set the shared v2 B-tree header's file context for this operation */ |
962 | 0 | bt2->hdr->f = bt2->f; |
963 | | |
964 | | /* Get the v2 B-tree header */ |
965 | 0 | hdr = bt2->hdr; |
966 | | |
967 | | /* Check for empty B-tree */ |
968 | 0 | if (0 == hdr->root.all_nrec) |
969 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "record is not in B-tree"); |
970 | | |
971 | | /* Check for index greater than the number of records in the tree */ |
972 | 0 | if (idx >= hdr->root.all_nrec) |
973 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree doesn't have that many records"); |
974 | | |
975 | | /* Check for reverse indexing and map requested index to appropriate forward index */ |
976 | 0 | if (H5_ITER_DEC == order) |
977 | 0 | idx = hdr->root.all_nrec - (idx + 1); |
978 | | |
979 | | /* Attempt to remove record from B-tree */ |
980 | 0 | if (hdr->depth > 0) { |
981 | 0 | bool depth_decreased = false; /* Flag to indicate whether the depth of the B-tree decreased */ |
982 | |
|
983 | 0 | if (H5B2__remove_internal_by_idx(hdr, &depth_decreased, NULL, NULL, hdr->depth, &(hdr->cache_info), |
984 | 0 | NULL, &hdr->root, H5B2_POS_ROOT, idx, op, op_data) < 0) |
985 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree internal node"); |
986 | | |
987 | | /* Check for decreasing the depth of the B-tree */ |
988 | 0 | if (depth_decreased) { |
989 | | /* Destroy free list factories for previous depth */ |
990 | 0 | if (hdr->node_info[hdr->depth].nat_rec_fac) |
991 | 0 | if (H5FL_fac_term(hdr->node_info[hdr->depth].nat_rec_fac) < 0) |
992 | 0 | HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, |
993 | 0 | "can't destroy node's native record block factory"); |
994 | 0 | if (hdr->node_info[hdr->depth].node_ptr_fac) |
995 | 0 | if (H5FL_fac_term(hdr->node_info[hdr->depth].node_ptr_fac) < 0) |
996 | 0 | HGOTO_ERROR(H5E_RESOURCE, H5E_CANTRELEASE, FAIL, |
997 | 0 | "can't destroy node's node pointer block factory"); |
998 | | |
999 | 0 | assert((uint16_t)(hdr->depth - depth_decreased) < hdr->depth); |
1000 | 0 | hdr->depth = (uint16_t)(hdr->depth - depth_decreased); |
1001 | 0 | } /* end for */ |
1002 | 0 | } /* end if */ |
1003 | 0 | else { |
1004 | 0 | if (H5B2__remove_leaf_by_idx(hdr, &hdr->root, H5B2_POS_ROOT, hdr, (unsigned)idx, op, op_data) < 0) |
1005 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to remove record from B-tree leaf node"); |
1006 | 0 | } /* end else */ |
1007 | | |
1008 | | /* Decrement # of records in B-tree */ |
1009 | 0 | hdr->root.all_nrec--; |
1010 | | |
1011 | | /* Mark B-tree header as dirty */ |
1012 | 0 | if (H5B2__hdr_dirty(hdr) < 0) |
1013 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTMARKDIRTY, FAIL, "unable to mark B-tree header dirty"); |
1014 | | |
1015 | 0 | done: |
1016 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1017 | 0 | } /* H5B2_remove_by_idx() */ |
1018 | | |
1019 | | /*------------------------------------------------------------------------- |
1020 | | * Function: H5B2_get_nrec |
1021 | | * |
1022 | | * Purpose: Retrieves the number of records in a B-tree |
1023 | | * |
1024 | | * Return: Non-negative on success/Negative on failure |
1025 | | * |
1026 | | *------------------------------------------------------------------------- |
1027 | | */ |
1028 | | herr_t |
1029 | | H5B2_get_nrec(const H5B2_t *bt2, hsize_t *nrec) |
1030 | 0 | { |
1031 | 0 | FUNC_ENTER_NOAPI_NOINIT_NOERR |
1032 | | |
1033 | | /* Check arguments. */ |
1034 | 0 | assert(bt2); |
1035 | 0 | assert(nrec); |
1036 | | |
1037 | | /* Get B-tree number of records */ |
1038 | 0 | *nrec = bt2->hdr->root.all_nrec; |
1039 | |
|
1040 | 0 | FUNC_LEAVE_NOAPI(SUCCEED) |
1041 | 0 | } /* H5B2_get_nrec() */ |
1042 | | |
1043 | | /*------------------------------------------------------------------------- |
1044 | | * Function: H5B2_neighbor |
1045 | | * |
1046 | | * Purpose: Locate a record relative to the specified information in a |
1047 | | * B-tree and return that information by filling in fields of the |
1048 | | * caller-supplied UDATA pointer depending on the type of leaf node |
1049 | | * requested. The UDATA can point to additional data passed |
1050 | | * to the key comparison function. |
1051 | | * |
1052 | | * The 'OP' routine is called with the record found and the |
1053 | | * OP_DATA pointer, to allow caller to return information about |
1054 | | * the record. |
1055 | | * |
1056 | | * The RANGE indicates whether to search for records less than or |
1057 | | * equal to, or greater than or equal to the information passed |
1058 | | * in with UDATA. |
1059 | | * |
1060 | | * Return: Non-negative on success, negative on failure. |
1061 | | * |
1062 | | *------------------------------------------------------------------------- |
1063 | | */ |
1064 | | herr_t |
1065 | | H5B2_neighbor(H5B2_t *bt2, H5B2_compare_t range, void *udata, H5B2_found_t op, void *op_data) |
1066 | 0 | { |
1067 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
1068 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
1069 | |
|
1070 | 0 | FUNC_ENTER_NOAPI(FAIL) |
1071 | | |
1072 | | /* Check arguments. */ |
1073 | 0 | assert(bt2); |
1074 | 0 | assert(op); |
1075 | | |
1076 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1077 | 0 | bt2->hdr->f = bt2->f; |
1078 | | |
1079 | | /* Get the v2 B-tree header */ |
1080 | 0 | hdr = bt2->hdr; |
1081 | | |
1082 | | /* Check for empty tree */ |
1083 | 0 | if (!H5_addr_defined(hdr->root.addr)) |
1084 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records"); |
1085 | | |
1086 | | /* Attempt to find neighbor record in B-tree */ |
1087 | 0 | if (hdr->depth > 0) { |
1088 | 0 | if (H5B2__neighbor_internal(hdr, hdr->depth, &hdr->root, NULL, range, hdr, udata, op, op_data) < 0) |
1089 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, |
1090 | 0 | "unable to find neighbor record in B-tree internal node"); |
1091 | 0 | } /* end if */ |
1092 | 0 | else { |
1093 | 0 | if (H5B2__neighbor_leaf(hdr, &hdr->root, NULL, range, hdr, udata, op, op_data) < 0) |
1094 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "unable to find neighbor record in B-tree leaf node"); |
1095 | 0 | } /* end else */ |
1096 | | |
1097 | 0 | done: |
1098 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1099 | 0 | } /* H5B2_neighbor() */ |
1100 | | |
1101 | | /*------------------------------------------------------------------------- |
1102 | | * Function: H5B2_modify |
1103 | | * |
1104 | | * Purpose: Locate the specified information in a B-tree and modify it. |
1105 | | * The UDATA points to additional data passed |
1106 | | * to the key comparison function for locating the record to |
1107 | | * modify. |
1108 | | * |
1109 | | * The 'OP' routine is called with the record found and the |
1110 | | * OP_DATA pointer, to allow caller to modify information about |
1111 | | * the record. |
1112 | | * |
1113 | | * Return: Non-negative on success, negative on failure. |
1114 | | * |
1115 | | *------------------------------------------------------------------------- |
1116 | | */ |
1117 | | herr_t |
1118 | | H5B2_modify(H5B2_t *bt2, void *udata, H5B2_modify_t op, void *op_data) |
1119 | 0 | { |
1120 | 0 | H5B2_hdr_t *hdr; /* Pointer to the B-tree header */ |
1121 | 0 | H5B2_node_ptr_t curr_node_ptr; /* Node pointer info for current node */ |
1122 | 0 | void *parent = NULL; /* Parent of current node */ |
1123 | 0 | H5B2_nodepos_t curr_pos; /* Position of current node */ |
1124 | 0 | uint16_t depth; /* Current depth of the tree */ |
1125 | 0 | int cmp; /* Comparison value of records */ |
1126 | 0 | unsigned idx; /* Location of record which matches key */ |
1127 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
1128 | |
|
1129 | 0 | FUNC_ENTER_NOAPI(FAIL) |
1130 | | |
1131 | | /* Check arguments. */ |
1132 | 0 | assert(bt2); |
1133 | 0 | assert(op); |
1134 | | |
1135 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1136 | 0 | bt2->hdr->f = bt2->f; |
1137 | | |
1138 | | /* Get the v2 B-tree header */ |
1139 | 0 | hdr = bt2->hdr; |
1140 | | |
1141 | | /* Make copy of the root node pointer to start search with */ |
1142 | 0 | curr_node_ptr = hdr->root; |
1143 | | |
1144 | | /* Check for empty tree */ |
1145 | 0 | if (0 == curr_node_ptr.node_nrec) |
1146 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "B-tree has no records"); |
1147 | | |
1148 | | /* Current depth of the tree */ |
1149 | 0 | depth = hdr->depth; |
1150 | | |
1151 | | /* Set initial parent, if doing swmr writes */ |
1152 | 0 | if (hdr->swmr_write) |
1153 | 0 | parent = hdr; |
1154 | | |
1155 | | /* Walk down B-tree to find record or leaf node where record is located */ |
1156 | 0 | cmp = -1; |
1157 | 0 | curr_pos = H5B2_POS_ROOT; |
1158 | 0 | while (depth > 0) { |
1159 | 0 | unsigned internal_flags = H5AC__NO_FLAGS_SET; |
1160 | 0 | H5B2_internal_t *internal; /* Pointer to internal node in B-tree */ |
1161 | 0 | H5B2_node_ptr_t next_node_ptr; /* Node pointer info for next node */ |
1162 | | |
1163 | | /* Lock B-tree current node */ |
1164 | 0 | if (NULL == (internal = H5B2__protect_internal(hdr, parent, &curr_node_ptr, depth, false, |
1165 | 0 | H5AC__NO_FLAGS_SET))) |
1166 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree internal node"); |
1167 | | |
1168 | | /* Unpin parent if necessary */ |
1169 | 0 | if (parent) { |
1170 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
1171 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
1172 | 0 | parent = NULL; |
1173 | 0 | } /* end if */ |
1174 | | |
1175 | | /* Locate node pointer for child */ |
1176 | 0 | if (H5B2__locate_record(hdr->cls, internal->nrec, hdr->nat_off, internal->int_native, udata, &idx, |
1177 | 0 | &cmp) < 0) { |
1178 | | /* Unlock current node before failing */ |
1179 | 0 | H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET); |
1180 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
1181 | 0 | } /* end if */ |
1182 | | |
1183 | 0 | if (cmp > 0) |
1184 | 0 | idx++; |
1185 | |
|
1186 | 0 | if (cmp != 0) { |
1187 | | /* Get node pointer for next node to search */ |
1188 | 0 | next_node_ptr = internal->node_ptrs[idx]; |
1189 | | |
1190 | | /* Set the position of the next node */ |
1191 | 0 | if (H5B2_POS_MIDDLE != curr_pos) { |
1192 | 0 | if (idx == 0) { |
1193 | 0 | if (H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) |
1194 | 0 | curr_pos = H5B2_POS_LEFT; |
1195 | 0 | else |
1196 | 0 | curr_pos = H5B2_POS_MIDDLE; |
1197 | 0 | } /* end if */ |
1198 | 0 | else if (idx == internal->nrec) { |
1199 | 0 | if (H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) |
1200 | 0 | curr_pos = H5B2_POS_RIGHT; |
1201 | 0 | else |
1202 | 0 | curr_pos = H5B2_POS_MIDDLE; |
1203 | 0 | } /* end if */ |
1204 | 0 | else |
1205 | 0 | curr_pos = H5B2_POS_MIDDLE; |
1206 | 0 | } /* end if */ |
1207 | | |
1208 | | /* Unlock current node */ |
1209 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, |
1210 | 0 | (unsigned)(hdr->swmr_write ? H5AC__PIN_ENTRY_FLAG : H5AC__NO_FLAGS_SET)) < 0) |
1211 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1212 | | |
1213 | | /* Keep track of parent if necessary */ |
1214 | 0 | if (hdr->swmr_write) |
1215 | 0 | parent = internal; |
1216 | | |
1217 | | /* Set pointer to next node to load */ |
1218 | 0 | curr_node_ptr = next_node_ptr; |
1219 | 0 | } /* end if */ |
1220 | 0 | else { |
1221 | 0 | bool changed; /* Whether the 'modify' callback changed the record */ |
1222 | | |
1223 | | /* Make callback for current record */ |
1224 | 0 | if ((op)(H5B2_INT_NREC(internal, hdr, idx), op_data, &changed) < 0) { |
1225 | | /* Make certain that the callback didn't modify the value if it failed */ |
1226 | 0 | assert(changed == false); |
1227 | | |
1228 | | /* Unlock current node */ |
1229 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, H5AC__NO_FLAGS_SET) < |
1230 | 0 | 0) |
1231 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1232 | | |
1233 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, |
1234 | 0 | "'modify' callback failed for B-tree find operation"); |
1235 | 0 | } /* end if */ |
1236 | | |
1237 | | /* Mark the node as dirty if it changed */ |
1238 | 0 | internal_flags |= changed ? H5AC__DIRTIED_FLAG : 0; |
1239 | | |
1240 | | /* Unlock current node */ |
1241 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_INT, curr_node_ptr.addr, internal, internal_flags) < 0) |
1242 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1243 | | |
1244 | 0 | HGOTO_DONE(SUCCEED); |
1245 | 0 | } /* end else */ |
1246 | | |
1247 | | /* Decrement depth we're at in B-tree */ |
1248 | 0 | depth--; |
1249 | 0 | } /* end while */ |
1250 | | |
1251 | 0 | { |
1252 | 0 | H5B2_leaf_t *leaf; /* Pointer to leaf node in B-tree */ |
1253 | 0 | unsigned leaf_flags = H5AC__NO_FLAGS_SET; /* Flags for unprotecting the leaf node */ |
1254 | 0 | bool changed = false; /* Whether the 'modify' callback changed the record */ |
1255 | | |
1256 | | /* Lock B-tree leaf node */ |
1257 | 0 | if (NULL == (leaf = H5B2__protect_leaf(hdr, parent, &curr_node_ptr, false, H5AC__NO_FLAGS_SET))) |
1258 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree leaf node"); |
1259 | | |
1260 | | /* Unpin parent if necessary */ |
1261 | 0 | if (parent) { |
1262 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
1263 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
1264 | 0 | parent = NULL; |
1265 | 0 | } /* end if */ |
1266 | | |
1267 | | /* Locate record */ |
1268 | 0 | if (H5B2__locate_record(hdr->cls, leaf->nrec, hdr->nat_off, leaf->leaf_native, udata, &idx, &cmp) < |
1269 | 0 | 0) { |
1270 | | /* Unlock current node before failing */ |
1271 | 0 | H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET); |
1272 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTCOMPARE, FAIL, "can't compare btree2 records"); |
1273 | 0 | } /* end if */ |
1274 | | |
1275 | 0 | if (cmp != 0) { |
1276 | | /* Unlock leaf node */ |
1277 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
1278 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1279 | | |
1280 | | /* Note: don't push error on stack, leave that to next higher level, |
1281 | | * since many times the B-tree is searched in order to determine |
1282 | | * if an object exists in the B-tree or not. |
1283 | | */ |
1284 | 0 | HGOTO_DONE(FAIL); |
1285 | 0 | } |
1286 | 0 | else { |
1287 | | /* Make callback for current record */ |
1288 | 0 | if ((op)(H5B2_LEAF_NREC(leaf, hdr, idx), op_data, &changed) < 0) { |
1289 | | /* Make certain that the callback didn't modify the value if it failed */ |
1290 | 0 | assert(changed == false); |
1291 | | |
1292 | | /* Unlock current node */ |
1293 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, H5AC__NO_FLAGS_SET) < 0) |
1294 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1295 | | |
1296 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTMODIFY, FAIL, |
1297 | 0 | "'modify' callback failed for B-tree find operation"); |
1298 | 0 | } /* end if */ |
1299 | | |
1300 | | /* Check for modified record being the min or max for the tree */ |
1301 | | /* (Don't use 'else' for the idx check, to allow for root leaf node) */ |
1302 | 0 | if (H5B2_POS_MIDDLE != curr_pos) { |
1303 | 0 | if (idx == 0) { |
1304 | 0 | if (H5B2_POS_LEFT == curr_pos || H5B2_POS_ROOT == curr_pos) { |
1305 | 0 | if (hdr->min_native_rec == NULL) |
1306 | 0 | if (NULL == (hdr->min_native_rec = H5MM_malloc(hdr->cls->nrec_size))) |
1307 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, |
1308 | 0 | "memory allocation failed for v2 B-tree min record info"); |
1309 | 0 | H5MM_memcpy(hdr->min_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); |
1310 | 0 | } /* end if */ |
1311 | 0 | } /* end if */ |
1312 | 0 | if (idx == (unsigned)(leaf->nrec - 1)) { |
1313 | 0 | if (H5B2_POS_RIGHT == curr_pos || H5B2_POS_ROOT == curr_pos) { |
1314 | 0 | if (hdr->max_native_rec == NULL) |
1315 | 0 | if (NULL == (hdr->max_native_rec = H5MM_malloc(hdr->cls->nrec_size))) |
1316 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, |
1317 | 0 | "memory allocation failed for v2 B-tree max record info"); |
1318 | 0 | H5MM_memcpy(hdr->max_native_rec, H5B2_LEAF_NREC(leaf, hdr, idx), hdr->cls->nrec_size); |
1319 | 0 | } /* end if */ |
1320 | 0 | } /* end if */ |
1321 | 0 | } /* end if */ |
1322 | 0 | } /* end else */ |
1323 | | |
1324 | | /* Mark the node as dirty if it changed */ |
1325 | 0 | leaf_flags |= (changed ? H5AC__DIRTIED_FLAG : 0); |
1326 | | |
1327 | | /* Unlock current node */ |
1328 | 0 | if (H5AC_unprotect(hdr->f, H5AC_BT2_LEAF, curr_node_ptr.addr, leaf, leaf_flags) < 0) |
1329 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node"); |
1330 | 0 | } /* end block */ |
1331 | | |
1332 | 0 | done: |
1333 | 0 | if (parent) { |
1334 | 0 | assert(ret_value < 0); |
1335 | 0 | if (parent != hdr && H5AC_unpin_entry(parent) < 0) |
1336 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPIN, FAIL, "unable to unpin parent entry"); |
1337 | 0 | } /* end if */ |
1338 | |
|
1339 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1340 | 0 | } /* H5B2_modify() */ |
1341 | | |
1342 | | /*------------------------------------------------------------------------- |
1343 | | * Function: H5B2_close |
1344 | | * |
1345 | | * Purpose: Close a v2 B-tree |
1346 | | * |
1347 | | * Return: Non-negative on success/Negative on failure |
1348 | | * |
1349 | | *------------------------------------------------------------------------- |
1350 | | */ |
1351 | | herr_t |
1352 | | H5B2_close(H5B2_t *bt2) |
1353 | 0 | { |
1354 | 0 | haddr_t bt2_addr = HADDR_UNDEF; /* Address of v2 B-tree (for deletion) */ |
1355 | 0 | bool pending_delete = false; /* Whether the v2 B-tree is pending deletion */ |
1356 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
1357 | |
|
1358 | 0 | FUNC_ENTER_NOAPI_NOINIT |
1359 | | |
1360 | | /* Check arguments. */ |
1361 | 0 | assert(bt2); |
1362 | 0 | assert(bt2->f); |
1363 | | |
1364 | | /* Decrement file reference & check if this is the last open v2 B-tree using the shared B-tree header */ |
1365 | 0 | if (0 == H5B2__hdr_fuse_decr(bt2->hdr)) { |
1366 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1367 | 0 | bt2->hdr->f = bt2->f; |
1368 | | |
1369 | | /* Check for pending B-tree deletion */ |
1370 | 0 | if (bt2->hdr->pending_delete) { |
1371 | | /* Set local info, so B-tree deletion can occur after decrementing the |
1372 | | * header's ref count |
1373 | | */ |
1374 | 0 | pending_delete = true; |
1375 | 0 | bt2_addr = bt2->hdr->addr; |
1376 | 0 | } /* end if */ |
1377 | 0 | } /* end if */ |
1378 | | |
1379 | | /* Check for pending v2 B-tree deletion */ |
1380 | 0 | if (pending_delete) { |
1381 | 0 | H5B2_hdr_t *hdr; /* Another pointer to v2 B-tree header */ |
1382 | | |
1383 | | /* Sanity check */ |
1384 | 0 | assert(H5_addr_defined(bt2_addr)); |
1385 | |
|
1386 | | #ifndef NDEBUG |
1387 | | { |
1388 | | unsigned hdr_status = 0; /* Header's status in the metadata cache */ |
1389 | | |
1390 | | /* Check the header's status in the metadata cache */ |
1391 | | if (H5AC_get_entry_status(bt2->f, bt2_addr, &hdr_status) < 0) |
1392 | | HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, |
1393 | | "unable to check metadata cache status for v2 B-tree header, address = %llu", |
1394 | | (unsigned long long)bt2_addr); |
1395 | | |
1396 | | /* Sanity checks on header */ |
1397 | | assert(hdr_status & H5AC_ES__IN_CACHE); |
1398 | | assert(hdr_status & H5AC_ES__IS_PINNED); |
1399 | | assert(!(hdr_status & H5AC_ES__IS_PROTECTED)); |
1400 | | } |
1401 | | #endif /* NDEBUG */ |
1402 | | |
1403 | | /* Lock the v2 B-tree header into memory */ |
1404 | | /* (OK to pass in NULL for callback context, since we know the header must be in the cache) */ |
1405 | 0 | if (NULL == (hdr = H5B2__hdr_protect(bt2->f, bt2_addr, NULL, H5AC__NO_FLAGS_SET))) |
1406 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect v2 B-tree header"); |
1407 | | |
1408 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1409 | 0 | hdr->f = bt2->f; |
1410 | | |
1411 | | /* Decrement the reference count on the B-tree header */ |
1412 | | /* (don't put in H5B2__hdr_fuse_decr() as the B-tree header may be evicted |
1413 | | * immediately -QAK) |
1414 | | */ |
1415 | 0 | if (H5B2__hdr_decr(bt2->hdr) < 0) |
1416 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDEC, FAIL, |
1417 | 0 | "can't decrement reference count on shared v2 B-tree header"); |
1418 | | |
1419 | | /* Delete v2 B-tree, starting with header (unprotects header) */ |
1420 | 0 | if (H5B2__hdr_delete(hdr) < 0) |
1421 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to delete v2 B-tree"); |
1422 | 0 | } /* end if */ |
1423 | 0 | else { |
1424 | | /* Decrement the reference count on the B-tree header */ |
1425 | | /* (don't put in H5B2__hdr_fuse_decr() as the B-tree header may be evicted |
1426 | | * immediately -QAK) |
1427 | | */ |
1428 | 0 | if (H5B2__hdr_decr(bt2->hdr) < 0) |
1429 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDEC, FAIL, |
1430 | 0 | "can't decrement reference count on shared v2 B-tree header"); |
1431 | |
|
1432 | 0 | } /* end else */ |
1433 | | |
1434 | | /* Release the v2 B-tree wrapper */ |
1435 | 0 | bt2 = H5FL_FREE(H5B2_t, bt2); |
1436 | |
|
1437 | 0 | done: |
1438 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1439 | 0 | } /* H5B2_close() */ |
1440 | | |
1441 | | /*------------------------------------------------------------------------- |
1442 | | * Function: H5B2_delete |
1443 | | * |
1444 | | * Purpose: Delete an entire B-tree from a file. |
1445 | | * |
1446 | | * The 'OP' routine is called for each record and the |
1447 | | * OP_DATA pointer, to allow caller to perform an operation as |
1448 | | * each record is removed from the B-tree. |
1449 | | * |
1450 | | * If 'OP' is NULL, the records are just removed in the process |
1451 | | * of deleting the B-tree. |
1452 | | * |
1453 | | * Note: The records are _not_ guaranteed to be visited in order. |
1454 | | * |
1455 | | * Return: Non-negative on success, negative on failure. |
1456 | | * |
1457 | | *------------------------------------------------------------------------- |
1458 | | */ |
1459 | | herr_t |
1460 | | H5B2_delete(H5F_t *f, haddr_t addr, void *ctx_udata, H5B2_remove_t op, void *op_data) |
1461 | 0 | { |
1462 | 0 | H5B2_hdr_t *hdr = NULL; /* Pointer to the B-tree header */ |
1463 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
1464 | |
|
1465 | 0 | FUNC_ENTER_NOAPI(FAIL) |
1466 | | |
1467 | | /* Check arguments. */ |
1468 | 0 | assert(f); |
1469 | 0 | assert(H5_addr_defined(addr)); |
1470 | | |
1471 | | /* Lock the v2 B-tree header into memory */ |
1472 | 0 | if (NULL == (hdr = H5B2__hdr_protect(f, addr, ctx_udata, H5AC__NO_FLAGS_SET))) |
1473 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect v2 B-tree header"); |
1474 | | |
1475 | | /* Remember the callback & context for later */ |
1476 | 0 | hdr->remove_op = op; |
1477 | 0 | hdr->remove_op_data = op_data; |
1478 | | |
1479 | | /* Check for files using shared v2 B-tree header */ |
1480 | 0 | if (hdr->file_rc) |
1481 | 0 | hdr->pending_delete = true; |
1482 | 0 | else { |
1483 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1484 | 0 | hdr->f = f; |
1485 | | |
1486 | | /* Delete v2 B-tree now, starting with header (unprotects header) */ |
1487 | 0 | if (H5B2__hdr_delete(hdr) < 0) |
1488 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTDELETE, FAIL, "unable to delete v2 B-tree"); |
1489 | 0 | hdr = NULL; |
1490 | 0 | } /* end if */ |
1491 | | |
1492 | 0 | done: |
1493 | | /* Unprotect the header, if an error occurred */ |
1494 | 0 | if (hdr && H5B2__hdr_unprotect(hdr, H5AC__NO_FLAGS_SET) < 0) |
1495 | 0 | HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release v2 B-tree header"); |
1496 | |
|
1497 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1498 | 0 | } /* H5B2_delete() */ |
1499 | | |
1500 | | /*------------------------------------------------------------------------- |
1501 | | * Function: H5B2_depend |
1502 | | * |
1503 | | * Purpose: Make a child flush dependency between the v2 B-tree's |
1504 | | * header and another piece of metadata in the file. |
1505 | | * |
1506 | | * Return: SUCCEED/FAIL |
1507 | | * |
1508 | | *------------------------------------------------------------------------- |
1509 | | */ |
1510 | | herr_t |
1511 | | H5B2_depend(H5B2_t *bt2, H5AC_proxy_entry_t *parent) |
1512 | 0 | { |
1513 | | /* Local variables */ |
1514 | 0 | H5B2_hdr_t *hdr = bt2->hdr; /* Header for B-tree */ |
1515 | 0 | herr_t ret_value = SUCCEED; /* Return value */ |
1516 | |
|
1517 | 0 | FUNC_ENTER_NOAPI(SUCCEED) |
1518 | | |
1519 | | /* |
1520 | | * Check arguments. |
1521 | | */ |
1522 | 0 | assert(bt2); |
1523 | 0 | assert(hdr); |
1524 | 0 | assert(parent); |
1525 | 0 | assert(hdr->parent == NULL || hdr->parent == parent); |
1526 | | |
1527 | | /* |
1528 | | * Check to see if the flush dependency between the parent |
1529 | | * and the v2 B-tree header has already been setup. If it hasn't, then |
1530 | | * set it up. |
1531 | | */ |
1532 | 0 | if (NULL == hdr->parent) { |
1533 | | /* Sanity check */ |
1534 | 0 | assert(hdr->top_proxy); |
1535 | | |
1536 | | /* Set the shared v2 B-tree header's file context for this operation */ |
1537 | 0 | hdr->f = bt2->f; |
1538 | | |
1539 | | /* Add the v2 B-tree as a child of the parent (proxy) */ |
1540 | 0 | if (H5AC_proxy_entry_add_child(parent, hdr->f, hdr->top_proxy) < 0) |
1541 | 0 | HGOTO_ERROR(H5E_BTREE, H5E_CANTSET, FAIL, "unable to add v2 B-tree as child of proxy"); |
1542 | 0 | hdr->parent = parent; |
1543 | 0 | } /* end if */ |
1544 | | |
1545 | 0 | done: |
1546 | 0 | FUNC_LEAVE_NOAPI(ret_value) |
1547 | 0 | } /* end H5B2_depend() */ |
1548 | | |
1549 | | /*------------------------------------------------------------------------- |
1550 | | * Function: H5B2_patch_file |
1551 | | * |
1552 | | * Purpose: Patch the top-level file pointer contained in bt2 |
1553 | | * to point to idx_info->f if they are different. |
1554 | | * This is possible because the file pointer in bt2 can be |
1555 | | * closed out if bt2 remains open. |
1556 | | * |
1557 | | * Return: SUCCEED |
1558 | | * |
1559 | | *------------------------------------------------------------------------- |
1560 | | */ |
1561 | | herr_t |
1562 | | H5B2_patch_file(H5B2_t *bt2, H5F_t *f) |
1563 | 0 | { |
1564 | 0 | FUNC_ENTER_NOAPI_NOINIT_NOERR |
1565 | | |
1566 | | /* |
1567 | | * Check arguments. |
1568 | | */ |
1569 | 0 | assert(bt2); |
1570 | 0 | assert(f); |
1571 | |
|
1572 | 0 | if (bt2->f != f || bt2->hdr->f != f) |
1573 | 0 | bt2->f = bt2->hdr->f = f; |
1574 | |
|
1575 | 0 | FUNC_LEAVE_NOAPI(SUCCEED) |
1576 | 0 | } /* H5B2_patch_file() */ |