summaryrefslogtreecommitdiffstats
path: root/src/H5B.c
blob: f909d908106fbf6c068c3f5e0c2aac442813ef34 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by The HDF Group.                                               *
 * Copyright by the Board of Trustees of the University of Illinois.         *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of HDF5.  The full HDF5 copyright notice, including     *
 * terms governing use, modification, and redistribution, is contained in    *
 * the files COPYING and Copyright.html.  COPYING can be found at the root   *
 * of the source code distribution tree; Copyright.html can be found at the  *
 * root level of an installed copy of the electronic HDF5 document set and   *
 * is linked from the top-level documents page.  It can also be found at     *
 * http://hdfgroup.org/HDF5/doc/Copyright.html.  If you do not have          *
 * access to either file, you may request a copy from help@hdfgroup.org.     *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*
 * Programmer:  Quincey Koziol
 *              Monday, Apr 20
 *
 * Purpose:     This file contains declarations which are visible only within
 *              the H5A package.  Source files outside the H5A package should
 *              include H5Aprivate.h instead.
 */
#if !(defined H5A_FRIEND || defined H5A_MODULE)
#error "Do not include this file outside the H5A package!"
#endif

#ifndef _H5Apkg_H
#define _H5Apkg_H

/*
 * Define this to enable debugging.
 */
#ifdef NDEBUG
#  undef H5A_DEBUG
#endif

/* Get package's private header */
#include "H5Aprivate.h"

/* Other private headers needed by this file */
#include "H5B2private.h"	/* v2 B-trees				*/
#include "H5FLprivate.h"	/* Free Lists				*/
#include "H5HFprivate.h"	/* Fractal heaps			*/
#include "H5Oprivate.h"		/* Object headers		  	*/
#include "H5Sprivate.h"		/* Dataspace				*/
#include "H5Tprivate.h"		/* Datatype functions			*/


/**************************/
/* Package Private Macros */
/**************************/

/* This is the initial version, which does not have support for shared datatypes */
#define H5O_ATTR_VERSION_1	1

/* This version allows support for shared datatypes & dataspaces by adding a
 *      'flag' byte indicating when those components are shared.  This version
 *      also dropped the alignment on all the components.
 */
#define H5O_ATTR_VERSION_2	2

/* Add support for different character encodings of attribute names */
#define H5O_ATTR_VERSION_3      3

/* The latest version of the format.  Look through the 'encode', 'decode'
 *      and 'size' message callbacks for places to change when updating this.
 */
#define H5O_ATTR_VERSION_LATEST H5O_ATTR_VERSION_3


/****************************/
/* Package Private Typedefs */
/****************************/
/* Define the shared attribute structure */
typedef struct H5A_shared_t {
    uint8_t     version;    /* Version to encode attribute with */

    char        *name;      /* Attribute's name */
    H5T_cset_t  encoding;   /* Character encoding of attribute name */

    H5T_t       *dt;        /* Attribute's datatype */
    size_t      dt_size;    /* Size of datatype on disk */

    H5S_t       *ds;        /* Attribute's dataspace */
    size_t      ds_size;    /* Size of dataspace on disk */

    void        *data;      /* Attribute data (on a temporary basis) */
    size_t      data_size;  /* Size of data on disk */
    H5O_msg_crt_idx_t crt_idx;  /* Attribute's creation index in the object header */
    unsigned	nrefs;		/* Ref count for times this object is refered	*/
} H5A_shared_t;

/* Define the main attribute structure */
struct H5A_t {
    H5O_shared_t sh_loc;     /* Shared message info (must be first) */
    H5O_loc_t    oloc;       /* Object location for object attribute is on */
    hbool_t      obj_opened; /* Object header entry opened? */
    H5G_name_t   path;       /* Group hierarchy path */
    H5A_shared_t *shared;    /* Shared attribute information */
};

/* Typedefs for "dense" attribute storage */
/* (fractal heap & v2 B-tree info) */

/* Typedef for native 'name' field index records in the v2 B-tree */
/* (Keep 'id' field first so generic record handling in callbacks works) */
typedef struct H5A_dense_bt2_name_rec_t {
    H5O_fheap_id_t id;                  /* Heap ID for attribute */
    uint8_t flags;                      /* Object header message flags for attribute */
    H5O_msg_crt_idx_t corder;           /* 'creation order' field value */
    uint32_t hash;                      /* Hash of 'name' field value */
} H5A_dense_bt2_name_rec_t;

/* Typedef for native 'creation order' field index records in the v2 B-tree */
/* (Keep 'id' field first so generic record handling in callbacks works) */
typedef struct H5A_dense_bt2_corder_rec_t {
    H5O_fheap_id_t id;                  /* Heap ID for attribute */
    uint8_t flags;                      /* Object header message flags for attribute */
    H5O_msg_crt_idx_t corder;           /* 'creation order' field value */
} H5A_dense_bt2_corder_rec_t;

/* Define the 'found' callback function pointer for matching an attribute record in a v2 B-tree */
typedef herr_t (*H5A_bt2_found_t)(const H5A_t *attr, hbool_t *took_ownership, void *op_data);

/*
 * Common data exchange structure for dense attribute storage.  This structure
 * is passed through the v2 B-tree layer to the methods for the objects
 * to which the v2 B-tree points.
 */
typedef struct H5A_bt2_ud_common_t {
    /* downward */
    H5F_t       *f;                     /* Pointer to file that fractal heap is in */
    hid_t       dxpl_id;                /* DXPL for operation                */
    H5HF_t      *fheap;                 /* Fractal heap handle               */
    H5HF_t      *shared_fheap;          /* Fractal heap handle for shared messages */
    const char  *name;                  /* Name of attribute to compare      */
    uint32_t    name_hash;              /* Hash of name of attribute to compare */
    uint8_t     flags;                  /* Flags for attribute storage location */
    H5O_msg_crt_idx_t corder;           /* Creation order value of attribute to compare */
    H5A_bt2_found_t found_op;           /* Callback when correct attribute is found */
    void        *found_op_data;         /* Callback data when correct attribute is found */
} H5A_bt2_ud_common_t;

/*
 * Data exchange structure for dense attribute storage.  This structure is
 * passed through the v2 B-tree layer when inserting attributes.
 */
typedef struct H5A_bt2_ud_ins_t {
    /* downward */
    H5A_bt2_ud_common_t common;         /* Common info for B-tree user data (must be first) */
    H5O_fheap_id_t id;                  /* Heap ID of attribute to insert    */
} H5A_bt2_ud_ins_t;

/* Data structure to hold table of attributes for an object */
typedef struct {
    size_t      nattrs;         /* # of attributes in table */
    H5A_t       **attrs;        /* Pointer to array of attribute pointers */
} H5A_attr_table_t;


/*****************************/
/* Package Private Variables */
/*****************************/

/* Declare extern the free list for H5A_t's */
H5FL_EXTERN(H5A_t);

/* Declare the external free lists for H5A_shared_t's */
H5FL_EXTERN(H5A_shared_t);

/* Declare extern a free list to manage blocks of type conversion data */
H5FL_BLK_EXTERN(attr_buf);

/* The v2 B-tree class for indexing 'name' field on attributes */
H5_DLLVAR const H5B2_class_t H5A_BT2_NAME[1];

/* The v2 B-tree class for indexing 'creation order' field on attributes */
H5_DLLVAR const H5B2_class_t H5A_BT2_CORDER[1];


/******************************/
/* Package Private Prototypes */
/******************************/

/* Function prototypes for H5A package scope */
H5_DLL H5A_t *H5A_create(const H5G_loc_t *loc, const char *name,
    const H5T_t *type, const H5S_t *space, hid_t acpl_id, hid_t dxpl_id);
H5_DLL H5A_t *H5A_open_by_name(const H5G_loc_t *loc, const char *obj_name,
    const char *attr_name, hid_t lapl_id, hid_t dxpl_id);
H5_DLL H5A_t *H5A_open_by_idx(const H5G_loc_t *loc, const char *obj_name,
    H5_index_t idx_type, H5_iter_order_t order, hsize_t n, hid_t lapl_id, hid_t dxpl_id);
H5_DLL herr_t H5A__open_common(const H5G_loc_t *loc, H5A_t *attr);
H5_DLL H5A_t *H5A_copy(H5A_t *new_attr, const H5A_t *old_attr);
H5_DLL herr_t H5A__get_info(const H5A_t *attr, H5A_info_t *ainfo);
H5_DLL hid_t H5A_get_create_plist(H5A_t* attr);
H5_DLL herr_t H5A_free(H5A_t *attr);
H5_DLL herr_t H5A_close(H5A_t *attr);
H5_DLL htri_t H5A_get_ainfo(H5F_t *f, hid_t dxpl_id, H5O_t *oh, H5O_ainfo_t *ainfo);
H5_DLL herr_t H5A_set_version(const H5F_t *f, H5A_t *attr);
H5_DLL herr_t H5A_rename_by_name(H5G_loc_t loc, const char *obj_name, const char *old_attr_name,
    const char *new_attr_name, hid_t lapl_id, hid_t dxpl_id);
H5_DLL htri_t H5A_exists_by_name(H5G_loc_t loc, const char *obj_name, const char *attr_name,
    hid_t lapl_id, hid_t dxpl_id);
H5_DLL herr_t H5A__write(H5A_t *attr, const H5T_t *mem_type, const void *buf, hid_t dxpl_id);
H5_DLL herr_t H5A__read(const H5A_t *attr, const H5T_t *mem_type, void *buf, hid_t dxpl_id);
H5_DLL ssize_t H5A__get_name(H5A_t *attr, size_t buf_size, char *buf);

/* Attribute "dense" storage routines */
H5_DLL herr_t H5A_dense_create(H5F_t *f, hid_t dxpl_id, H5O_ainfo_t *ainfo);
H5_DLL H5A_t *H5A_dense_open(H5F_t *f, hid_t dxpl_id, const H5O_ainfo_t *ainfo,
    const char *name);
H5_DLL herr_t H5A_dense_insert(H5F_t *f, hid_t dxpl_id, const H5O_ainfo_t *ainfo,
    H5A_t *attr);
H5_DLL herr_t H5A_dense_write(H5F_t *f, hid_t dxpl_id, const H5O_ainfo_t *ainfo,
    H5A_t *attr);
H5_DLL herr_t H5A_dense_rename(H5F_t *f, hid_t dxpl_id, const H5O_ainfo_t *ainfo,
    const char *old_name, const char *new_name);
H5_DLL herr_t H5A_dense_iterate(H5F_t *f, hid_t dxpl_id, hid_t loc_id,
    const H5O_ainfo_t *ainfo, H5_index_t idx_type, H5_iter_order_t order,
    hsize_t skip, hsize_t *last_attr, const H5A_attr_iter_op_t *attr_op,
    void *op_data);
H5_DLL herr_t H5A_dense_remove(H5F_t *f, hid_t dxpl_id,
    const H5O_ainfo_t *ainfo, const char *name);
H5_DLL herr_t H5A_dense_remove_by_idx(H5F_t *f, hid_t dxpl_id,
    const H5O_ainfo_t *ainfo, H5_index_t idx_type, H5_iter_order_t order,
    hsize_t n);
H5_DLL htri_t H5A_dense_exists(H5F_t *f, hid_t dxpl_id, const H5O_ainfo_t *ainfo,
    const char *name);
H5_DLL herr_t H5A_dense_delete(H5F_t *f, hid_t dxpl_id, H5O_ainfo_t *ainfo);

/* Attribute table operations */
H5_DLL herr_t H5A_compact_build_table(H5F_t *f, hid_t dxpl_id, H5O_t *oh,
    H5_index_t idx_type, H5_iter_order_t order, H5A_attr_table_t *atable);
H5_DLL herr_t H5A_dense_build_table(H5F_t *f, hid_t dxpl_id,
    const H5O_ainfo_t *ainfo, H5_index_t idx_type, H5_iter_order_t order,
    H5A_attr_table_t *atable);
H5_DLL herr_t H5A_attr_iterate_table(const H5A_attr_table_t *atable,
    hsize_t skip, hsize_t *last_attr, hid_t loc_id,
    const H5A_attr_iter_op_t *attr_op, void *op_data);
H5_DLL herr_t H5A_attr_release_table(H5A_attr_table_t *atable);

/* Attribute operations */
H5_DLL herr_t H5O_attr_create(const H5O_loc_t *loc, hid_t dxpl_id, H5A_t *attr);
H5_DLL H5A_t *H5O_attr_open_by_name(const H5O_loc_t *loc, const char *name,
    hid_t dxpl_id);
H5_DLL H5A_t *H5O_attr_open_by_idx(const H5O_loc_t *loc, H5_index_t idx_type,
    H5_iter_order_t order, hsize_t n, hid_t dxpl_id);
H5_DLL herr_t H5O_attr_update_shared(H5F_t *f, hid_t dxpl_id, H5O_t *oh,
        H5A_t *attr, H5O_shared_t *sh_mesg);
H5_DLL herr_t H5O_attr_write(const H5O_loc_t *loc, hid_t dxpl_id,
    H5A_t *attr);
H5_DLL herr_t H5O_attr_rename(const H5O_loc_t *loc, hid_t dxpl_id,
    const char *old_name, const char *new_name);
H5_DLL herr_t H5O_attr_remove(const H5O_loc_t *loc, const char *name,
    hid_t dxpl_id);
H5_DLL herr_t H5O_attr_remove_by_idx(const H5O_loc_t *loc, H5_index_t idx_type,
    H5_iter_order_t order, hsize_t n, hid_t dxpl_id);
H5_DLL htri_t H5O_attr_exists(const H5O_loc_t *loc, const char *name, hid_t dxpl_id);
#ifndef H5_NO_DEPRECATED_SYMBOLS
H5_DLL int H5O_attr_count(const H5O_loc_t *loc, hid_t dxpl_id);
#endif /* H5_NO_DEPRECATED_SYMBOLS */
H5_DLL H5A_t *H5A_attr_copy_file(const H5A_t *attr_src, H5F_t *file_dst, hbool_t *recompute_size,
    H5O_copy_t *cpy_info, hid_t dxpl_id);
H5_DLL herr_t H5A_attr_post_copy_file(const H5O_loc_t *src_oloc, const H5A_t *mesg_src,
    H5O_loc_t *dst_oloc, const H5A_t *mesg_dst, hid_t dxpl_id, H5O_copy_t *cpy_info);
H5_DLL herr_t H5A_dense_post_copy_file_all(const H5O_loc_t *src_oloc, const H5O_ainfo_t * ainfo_src,
    H5O_loc_t *dst_oloc, H5O_ainfo_t *ainfo_dst, hid_t dxpl_id, H5O_copy_t *cpy_info);

/* Testing functions */
#ifdef H5A_TESTING
H5_DLL htri_t H5A_is_shared_test(hid_t aid);
H5_DLL herr_t H5A_get_shared_rc_test(hid_t attr_id, hsize_t *ref_count);
#endif /* H5A_TESTING */

#endif /* _H5Apkg_H */

1263'>1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by The HDF Group.                                               *
 * Copyright by the Board of Trustees of the University of Illinois.         *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of HDF5.  The full HDF5 copyright notice, including     *
 * terms governing use, modification, and redistribution, is contained in    *
 * the COPYING file, which can be found at the root of the source code       *
 * distribution tree, or in https://support.hdfgroup.org/ftp/HDF5/releases.  *
 * If you do not have access to either file, you may request a copy from     *
 * help@hdfgroup.org.                                                        *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*-------------------------------------------------------------------------
 *
 * Created:		H5B.c
 *			Jul 10 1997
 *			Robb Matzke <matzke@llnl.gov>
 *
 * Purpose:		Implements balanced, sibling-linked, N-ary trees
 *			capable of storing any type of data with unique key
 *			values.
 *
 *			A B-link-tree is a balanced tree where each node has
 *			a pointer to its left and right siblings.  A
 *			B-link-tree is a rooted tree having the following
 *			properties:
 *
 *			1. Every node, x, has the following fields:
 *
 *			   a. level[x], the level in the tree at which node
 *			      x appears.  Leaf nodes are at level zero.
 *
 *			   b. n[x], the number of children pointed to by the
 *			      node.  Internal nodes point to subtrees while
 *			      leaf nodes point to arbitrary data.
 *
 *			   c. The child pointers themselves, child[x,i] such
 *			      that 0 <= i < n[x].
 *
 *			   d. n[x]+1 key values stored in increasing
 *			      order:
 *
 *				key[x,0] < key[x,1] < ... < key[x,n[x]].
 *
 *			   e. left[x] is a pointer to the node's left sibling
 *			      or the null pointer if this is the left-most
 *			      node at this level in the tree.
 *
 *			   f. right[x] is a pointer to the node's right
 *			      sibling or the null pointer if this is the
 *			      right-most node at this level in the tree.
 *
 *			3. The keys key[x,i] partition the key spaces of the
 *			   children of x:
 *
 *			      key[x,i] <= key[child[x,i],j] <= key[x,i+1]
 *
 *			   for any valid combination of i and j.
 *
 *			4. There are lower and upper bounds on the number of
 *			   child pointers a node can contain.  These bounds
 *			   can be expressed in terms of a fixed integer k>=2
 *			   called the `minimum degree' of the B-tree.
 *
 *			   a. Every node other than the root must have at least
 *			      k child pointers and k+1 keys.  If the tree is
 *			      nonempty, the root must have at least one child
 *			      pointer and two keys.
 *
 *			   b. Every node can contain at most 2k child pointers
 *			      and 2k+1 keys.  A node is `full' if it contains
 *			      exactly 2k child pointers and 2k+1 keys.
 *
 *			5. When searching for a particular value, V, and
 *			   key[V] = key[x,i] for some node x and entry i,
 *			   then:
 *
 *			   a. If i=0 the child[0] is followed.
 *
 *			   b. If i=n[x] the child[n[x]-1] is followed.
 *
 *			   c. Otherwise, the child that is followed
 *			      (either child[x,i-1] or child[x,i]) is
 *			      determined by the type of object to which the
 *			      leaf nodes of the tree point and is controlled
 *			      by the key comparison function registered for
 *			      that type of B-tree.
 *
 *
 *-------------------------------------------------------------------------
 */

/****************/
/* Module Setup */
/****************/

#include "H5Bmodule.h"          /* This source code file is part of the H5B module */


/***********/
/* Headers */
/***********/
#include "H5private.h"		/* Generic Functions			*/
#include "H5Bpkg.h"		/* B-link trees				*/
#include "H5CXprivate.h"        /* API Contexts                         */
#include "H5Eprivate.h"		/* Error handling		  	*/
#include "H5Iprivate.h"		/* IDs			  		*/
#include "H5MFprivate.h"	/* File memory management		*/
#include "H5MMprivate.h"	/* Memory management			*/
#include "H5Pprivate.h"         /* Property lists                       */


/****************/
/* Local Macros */
/****************/
#define H5B_SIZEOF_HDR(F)						      \
   (H5_SIZEOF_MAGIC +		/*magic number				  */  \
    4 +				/*type, level, num entries		  */  \
    2*H5F_SIZEOF_ADDR(F))	/*left and right sibling addresses	  */

/* Default initializer for H5B_ins_ud_t */
#define H5B_INS_UD_T_NULL {NULL, HADDR_UNDEF, H5AC__NO_FLAGS_SET}

/******************/
/* Local Typedefs */
/******************/

/* "user data" for iterating over B-tree (collects B-tree metadata size) */
typedef struct H5B_iter_ud_t {
    H5B_info_t *bt_info;        /* Information about B-tree */
    void    *udata;             /* Node type's 'udata' for loading & iterator callback */
} H5B_info_ud_t;

/* Convenience struct for the arguments needed to unprotect a b-tree after a
 * call to H5B__iterate_helper() or H5B__split() */
typedef struct H5B_ins_ud_t {
    H5B_t       *bt;            /* B-tree */
    haddr_t     addr;           /* B-tree address */
    unsigned    cache_flags;    /* Cache flags for H5AC_unprotect() */
} H5B_ins_ud_t;


/********************/
/* Local Prototypes */
/********************/
static H5B_ins_t H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud,
    const H5B_class_t *type, uint8_t *lt_key, hbool_t *lt_key_changed,
    uint8_t *md_key, void *udata, uint8_t *rt_key, hbool_t *rt_key_changed,
    H5B_ins_ud_t *split_bt_ud/*out*/);
static herr_t H5B__insert_child(H5B_t *bt, unsigned *bt_flags,
                               unsigned idx, haddr_t child,
			       H5B_ins_t anchor, const void *md_key);
static herr_t H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
    void *udata, H5B_ins_ud_t *split_bt_ud/*out*/);
static H5B_t * H5B__copy(const H5B_t *old_bt);


/*********************/
/* Package Variables */
/*********************/

/* Package initialization variable */
hbool_t H5_PKG_INIT_VAR = FALSE;

/* Declare a free list to manage the haddr_t sequence information */
H5FL_SEQ_DEFINE(haddr_t);

/* Declare a PQ free list to manage the native block information */
H5FL_BLK_DEFINE(native_block);

/* Declare a free list to manage the H5B_t struct */
H5FL_DEFINE(H5B_t);


/*****************************/
/* Library Private Variables */
/*****************************/


/*******************/
/* Local Variables */
/*******************/

/* Declare a free list to manage the H5B_shared_t struct */
H5FL_DEFINE_STATIC(H5B_shared_t);

/* Declare a free list to manage the raw page information */
H5FL_BLK_DEFINE_STATIC(page);

/* Declare a free list to manage the native key offset sequence information */
H5FL_SEQ_DEFINE_STATIC(size_t);



/*-------------------------------------------------------------------------
 * Function:	H5B_create
 *
 * Purpose:	Creates a new empty B-tree leaf node.  The UDATA pointer is
 *		passed as an argument to the sizeof_rkey() method for the
 *		B-tree.
 *
 * Return:	Success:	Non-negative, and the address of new node is
 *				returned through the ADDR_P argument.
 *
 * 		Failure:	Negative
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jun 23 1997
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_create(H5F_t *f, const H5B_class_t *type, void *udata, haddr_t *addr_p/*out*/)
{
    H5B_t		*bt = NULL;
    H5B_shared_t        *shared=NULL;        /* Pointer to shared B-tree info */
    herr_t		ret_value = SUCCEED;

    FUNC_ENTER_NOAPI(FAIL)

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(addr_p);

    /*
     * Allocate file and memory data structures.
     */
    if(NULL == (bt = H5FL_MALLOC(H5B_t)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
    HDmemset(&bt->cache_info, 0, sizeof(H5AC_info_t));
    bt->level = 0;
    bt->left = HADDR_UNDEF;
    bt->right = HADDR_UNDEF;
    bt->nchildren = 0;
    if(NULL == (bt->rc_shared = (type->get_shared)(f, udata)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree node buffer")
    H5UC_INC(bt->rc_shared);
    shared=(H5B_shared_t *)H5UC_GET_OBJ(bt->rc_shared);
    HDassert(shared);
    if(NULL == (bt->native = H5FL_BLK_MALLOC(native_block, shared->sizeof_keys)) ||
            NULL == (bt->child = H5FL_SEQ_MALLOC(haddr_t, (size_t)shared->two_k)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "memory allocation failed for B-tree root node")
    if(HADDR_UNDEF == (*addr_p = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "file allocation failed for B-tree root node")

    /*
     * Cache the new B-tree node.
     */
    if(H5AC_insert_entry(f, H5AC_BT, *addr_p, bt, H5AC__NO_FLAGS_SET) < 0)
	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B-tree root node to cache")
#ifdef H5B_DEBUG
    H5B__assert(f, *addr_p, shared->type, udata);
#endif

done:
    if(ret_value < 0) {
        if(shared && shared->sizeof_rnode>0) {
            H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
            (void)H5MF_xfree(f, H5FD_MEM_BTREE, *addr_p, (hsize_t)shared->sizeof_rnode);
        } /* end if */
	if(bt)
            /* Destroy B-tree node */
            if(H5B__node_dest(bt) < 0)
                HDONE_ERROR(H5E_BTREE, H5E_CANTFREE, FAIL, "unable to destroy B-tree node")
    } /* end if */

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_create() */        /*lint !e818 Can't make udata a pointer to const */


/*-------------------------------------------------------------------------
 * Function:	H5B_find
 *
 * Purpose:	Locate the specified information in a B-tree and return
 *		that information by filling in fields of the caller-supplied
 *		UDATA pointer depending on the type of leaf node
 *		requested.  The UDATA can point to additional data passed
 *		to the key comparison function.
 *
 * Note:	This function does not follow the left/right sibling
 *		pointers since it assumes that all nodes can be reached
 *		from the parent node.
 *
 * Return:	Non-negative (TRUE/FALSE) on success (if found, values returned
 *              through the UDATA argument). Negative on failure (if not found,
 *              UDATA is undefined).
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jun 23 1997
 *
 *-------------------------------------------------------------------------
 */
htri_t
H5B_find(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
    H5B_t	*bt = NULL;
    H5UC_t	*rc_shared;             /* Ref-counted shared info */
    H5B_shared_t *shared;               /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    unsigned    idx = 0, lt = 0, rt;    /* Final, left & right key indices */
    int	        cmp = 1;                /* Key comparison value */
    htri_t	ret_value = FAIL;       /* Return value */

    FUNC_ENTER_NOAPI(FAIL)

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(type->decode);
    HDassert(type->cmp3);
    HDassert(type->found);
    HDassert(H5F_addr_defined(addr));

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /*
     * Perform a binary search to locate the child which contains
     * the thing for which we're searching.
     */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")

    rt = bt->nchildren;
    while(lt < rt && cmp) {
	idx = (lt + rt) / 2;
	/* compare */
	if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, (idx + 1)))) < 0)
	    rt = idx;
	else
	    lt = idx + 1;
    } /* end while */
    /* Check if not found */
    if(cmp)
	HGOTO_DONE(FALSE)

    /*
     * Follow the link to the subtree or to the data node.
     */
    HDassert(idx < bt->nchildren);

    if(bt->level > 0) {
	if((ret_value = H5B_find(f, type, bt->child[idx], udata)) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in subtree")
    } /* end if */
    else {
	if((ret_value = (type->found)(f, bt->child[idx], H5B_NKEY(bt, shared, idx), udata)) < 0)
            HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't lookup key in leaf node")
    } /* end else */

done:
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
	HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release node")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_find() */


/*-------------------------------------------------------------------------
 * Function:	H5B__split
 *
 * Purpose:	Split a single node into two nodes.  The old node will
 *		contain the left children and the new node will contain the
 *		right children.
 *
 *		The UDATA pointer is passed to the sizeof_rkey() method but is
 *		otherwise unused.
 *
 *		The BT_UD argument is a pointer to a protected B-tree
 *		node.
 *
 * Return:	Non-negative on success (The address of the new node is
 *              returned through the NEW_ADDR argument). Negative on failure.
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jul  3 1997
 *
 *-------------------------------------------------------------------------
 */
static herr_t
H5B__split(H5F_t *f, H5B_ins_ud_t *bt_ud, unsigned idx,
    void *udata, H5B_ins_ud_t *split_bt_ud/*out*/)
{
    H5B_shared_t  *shared;              /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    unsigned	nleft, nright;          /* Number of keys in left & right halves */
    double      split_ratios[3];        /* B-tree split ratios */
    herr_t	ret_value = SUCCEED;    /* Return value */

    FUNC_ENTER_STATIC

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(bt_ud);
    HDassert(bt_ud->bt);
    HDassert(H5F_addr_defined(bt_ud->addr));
    HDassert(split_bt_ud);
    HDassert(!split_bt_ud->bt);

    /*
     * Initialize variables.
     */
    shared = (H5B_shared_t *)H5UC_GET_OBJ(bt_ud->bt->rc_shared);
    HDassert(shared);
    HDassert(bt_ud->bt->nchildren == shared->two_k);

    /* Get B-tree split ratios */
    if(H5CX_get_btree_split_ratios(split_ratios) < 0)
        HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree split ratios")

#ifdef H5B_DEBUG
    if(H5DEBUG(B)) {
	const char *side;

	if(!H5F_addr_defined(bt_ud->bt->left) && !H5F_addr_defined(bt_ud->bt->right))
	    side = "ONLY";
	else if(!H5F_addr_defined(bt_ud->bt->right))
	    side = "RIGHT";
	else if(!H5F_addr_defined(bt_ud->bt->left))
	    side = "LEFT";
	else
	    side = "MIDDLE";
        HDfprintf(H5DEBUG(B), "H5B__split: %3u {%5.3f,%5.3f,%5.3f} %6s",
            shared->two_k, split_ratios[0], split_ratios[1], split_ratios[2], side);
    }
#endif

    /*
     * Decide how to split the children of the old node among the old node
     * and the new node.
     */
    if(!H5F_addr_defined(bt_ud->bt->right))
	nleft = (unsigned)((double)shared->two_k * split_ratios[2]);	/*right*/
    else if(!H5F_addr_defined(bt_ud->bt->left))
	nleft = (unsigned)((double)shared->two_k * split_ratios[0]);	/*left*/
    else
	nleft = (unsigned)((double)shared->two_k * split_ratios[1]);	/*middle*/

    /*
     * Keep the new child in the same node as the child that split.  This can
     * result in nodes that have an unused child when data is written
     * sequentially, but it simplifies stuff below.
     */
    if(idx < nleft && nleft == shared->two_k)
	--nleft;
    else if(idx >= nleft && 0 == nleft)
	nleft++;
    nright = shared->two_k - nleft;
#ifdef H5B_DEBUG
    if(H5DEBUG(B))
        HDfprintf(H5DEBUG(B), " split %3d/%-3d\n", nleft, nright);
#endif

    /*
     * Create the new B-tree node.
     */
    if(H5B_create(f, shared->type, udata, &split_bt_ud->addr/*out*/) < 0)
        HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create B-tree")
    cache_udata.f = f;
    cache_udata.type = shared->type;
    cache_udata.rc_shared = bt_ud->bt->rc_shared;
    if(NULL == (split_bt_ud->bt = (H5B_t *)H5AC_protect(f, H5AC_BT, split_bt_ud->addr, &cache_udata, H5AC__NO_FLAGS_SET)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree")
    split_bt_ud->bt->level = bt_ud->bt->level;

    /*
     * Copy data from the old node to the new node.
     */

    split_bt_ud->cache_flags = H5AC__DIRTIED_FLAG;
    H5MM_memcpy(split_bt_ud->bt->native,
	     bt_ud->bt->native + nleft * shared->type->sizeof_nkey,
	     (nright + 1) * shared->type->sizeof_nkey);
    H5MM_memcpy(split_bt_ud->bt->child,
            &bt_ud->bt->child[nleft],
            nright * sizeof(haddr_t));

    split_bt_ud->bt->nchildren = nright;

    /*
     * Truncate the old node.
     */
    bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
    bt_ud->bt->nchildren = nleft;

    /*
     * Update other sibling pointers.
     */
    split_bt_ud->bt->left = bt_ud->addr;
    split_bt_ud->bt->right = bt_ud->bt->right;

    if(H5F_addr_defined(bt_ud->bt->right)) {
        H5B_t   *tmp_bt;

        if(NULL == (tmp_bt = (H5B_t *)H5AC_protect(f, H5AC_BT, bt_ud->bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load right sibling")

        tmp_bt->left = split_bt_ud->addr;

        if(H5AC_unprotect(f, H5AC_BT, bt_ud->bt->right, tmp_bt, H5AC__DIRTIED_FLAG) < 0)
            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
    } /* end if */

    bt_ud->bt->right = split_bt_ud->addr;
    HDassert(bt_ud->cache_flags & H5AC__DIRTIED_FLAG);

done:
    if(ret_value < 0) {
        if(split_bt_ud->bt && H5AC_unprotect(f, H5AC_BT, split_bt_ud->addr, split_bt_ud->bt, split_bt_ud->cache_flags) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
        split_bt_ud->bt = NULL;
        split_bt_ud->addr = HADDR_UNDEF;
        split_bt_ud->cache_flags = H5AC__NO_FLAGS_SET;
    } /* end if */

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__split() */


/*-------------------------------------------------------------------------
 * Function:	H5B_insert
 *
 * Purpose:	Adds a new item to the B-tree.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jun 23 1997
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_insert(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
    /*
     * These are defined this way to satisfy alignment constraints.
     */
    uint64_t	_lt_key[128], _md_key[128], _rt_key[128];
    uint8_t	*lt_key=(uint8_t*)_lt_key;
    uint8_t	*md_key=(uint8_t*)_md_key;
    uint8_t	*rt_key=(uint8_t*)_rt_key;

    hbool_t	lt_key_changed = FALSE, rt_key_changed = FALSE;
    haddr_t     old_root_addr = HADDR_UNDEF;
    unsigned	level;
    H5B_ins_ud_t bt_ud = H5B_INS_UD_T_NULL; /* (Old) root node */
    H5B_ins_ud_t split_bt_ud = H5B_INS_UD_T_NULL; /* Split B-tree node */
    H5B_t       *new_root_bt = NULL;    /* New root node */
    H5UC_t	*rc_shared;             /* Ref-counted shared info */
    H5B_shared_t        *shared;        /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    H5B_ins_t	my_ins = H5B_INS_ERROR;
    herr_t	ret_value = SUCCEED;

    FUNC_ENTER_NOAPI(FAIL)

    /* Check arguments. */
    HDassert(f);
    HDassert(type);
    HDassert(type->sizeof_nkey <= sizeof _lt_key);
    HDassert(H5F_addr_defined(addr));

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /* Protect the root node */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    bt_ud.addr = addr;
    if(NULL == (bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to locate root of B-tree")

    /* Insert the object */
    if((int)(my_ins = H5B__insert_helper(f, &bt_ud, type, lt_key,
            &lt_key_changed, md_key, udata, rt_key, &rt_key_changed,
            &split_bt_ud/*out*/)) < 0)
	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to insert key")

    /* Check if the root node split */
    if(H5B_INS_NOOP == my_ins) {
        /* The root node did not split - just return */
        HDassert(!split_bt_ud.bt);
        HGOTO_DONE(SUCCEED)
    } /* end if */
    HDassert(H5B_INS_RIGHT == my_ins);
    HDassert(split_bt_ud.bt);
    HDassert(H5F_addr_defined(split_bt_ud.addr));

    /* Get level of old root */
    level = bt_ud.bt->level;

    /* update left and right keys */
    if(!lt_key_changed)
	H5MM_memcpy(lt_key, H5B_NKEY(bt_ud.bt,shared,0), type->sizeof_nkey);
    if(!rt_key_changed)
	H5MM_memcpy(rt_key, H5B_NKEY(split_bt_ud.bt,shared,split_bt_ud.bt->nchildren), type->sizeof_nkey);

    /*
     * Copy the old root node to some other file location and make the new root
     * at the old root's previous address.  This prevents the B-tree from
     * "moving".
     */
    H5_CHECK_OVERFLOW(shared->sizeof_rnode,size_t,hsize_t);
    if(HADDR_UNDEF == (old_root_addr = H5MF_alloc(f, H5FD_MEM_BTREE, (hsize_t)shared->sizeof_rnode)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, FAIL, "unable to allocate file space to move root")

    /*
     * Move the node to the new location
     */

    /* Make a copy of the old root information */
    if(NULL == (new_root_bt = H5B__copy(bt_ud.bt)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTCOPY, FAIL, "unable to copy old root")

    /* Unprotect the old root so we can move it.  Also force it to be marked
     * dirty so it is written to the new location. */
    if(H5AC_unprotect(f, H5AC_BT, bt_ud.addr, bt_ud.bt, H5AC__DIRTIED_FLAG) < 0)
	HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release old root")
    bt_ud.bt = NULL;  /* Make certain future references will be caught */

    /* Move the location of the old root on the disk */
    if(H5AC_move_entry(f, H5AC_BT, bt_ud.addr, old_root_addr) < 0)
	HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to move B-tree root node")
    bt_ud.addr = old_root_addr;

    /* Update the split b-tree's left pointer to point to the new location */
    split_bt_ud.bt->left = bt_ud.addr;
    split_bt_ud.cache_flags |= H5AC__DIRTIED_FLAG;

    /* clear the old root info at the old address (we already copied it) */
    new_root_bt->left = HADDR_UNDEF;
    new_root_bt->right = HADDR_UNDEF;

    /* Set the new information for the copy */
    new_root_bt->level = level + 1;
    new_root_bt->nchildren = 2;

    new_root_bt->child[0] = bt_ud.addr;
    H5MM_memcpy(H5B_NKEY(new_root_bt, shared, 0), lt_key, shared->type->sizeof_nkey);

    new_root_bt->child[1] = split_bt_ud.addr;
    H5MM_memcpy(H5B_NKEY(new_root_bt, shared, 1), md_key, shared->type->sizeof_nkey);
    H5MM_memcpy(H5B_NKEY(new_root_bt, shared, 2), rt_key, shared->type->sizeof_nkey);

    /* Insert the modified copy of the old root into the file again */
    if(H5AC_insert_entry(f, H5AC_BT, addr, new_root_bt, H5AC__NO_FLAGS_SET) < 0)
        HGOTO_ERROR(H5E_BTREE, H5E_CANTFLUSH, FAIL, "unable to add old B-tree root node to cache")

done:
    if(ret_value < 0)
        if(new_root_bt && H5B__node_dest(new_root_bt) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTRELEASE, FAIL, "unable to free B-tree root node");

    if(bt_ud.bt)
        if(H5AC_unprotect(f, H5AC_BT, bt_ud.addr, bt_ud.bt, bt_ud.cache_flags) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to unprotect old root")

    if(split_bt_ud.bt)
        if(H5AC_unprotect(f, H5AC_BT, split_bt_ud.addr, split_bt_ud.bt, split_bt_ud.cache_flags) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to unprotect new child")

#ifdef H5B_DEBUG
    if(ret_value >= 0)
        H5B__assert(f, addr, type, udata);
#endif

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_insert() */


/*-------------------------------------------------------------------------
 * Function:	H5B__insert_child
 *
 * Purpose:	Insert a child to the left or right of child[IDX] depending
 *		on whether ANCHOR is H5B_INS_LEFT or H5B_INS_RIGHT. The BT
 *		argument is a pointer to a protected B-tree node.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jul  8 1997
 *
 *-------------------------------------------------------------------------
 */
static herr_t
H5B__insert_child(H5B_t *bt, unsigned *bt_flags, unsigned idx,
    haddr_t child, H5B_ins_t anchor, const void *md_key)
{
    H5B_shared_t        *shared;        /* Pointer to shared B-tree info */
    uint8_t             *base;          /* Base offset for move */

    FUNC_ENTER_STATIC_NOERR

    HDassert(bt);
    HDassert(bt_flags);
    HDassert(H5F_addr_defined(child));
    shared = (H5B_shared_t *)H5UC_GET_OBJ(bt->rc_shared);
    HDassert(shared);
    HDassert(bt->nchildren < shared->two_k);

    /* Check for inserting right-most key into node (common when just appending
     * records to an unlimited dimension chunked dataset)
     */
    base = H5B_NKEY(bt, shared, (idx + 1));
    if((idx + 1) == bt->nchildren) {
        /* Make room for the new key */
        H5MM_memcpy(base + shared->type->sizeof_nkey, base,
                  shared->type->sizeof_nkey);   /* No overlap possible - memcpy() OK */
        H5MM_memcpy(base, md_key, shared->type->sizeof_nkey);

        /* The MD_KEY is the left key of the new node */
        if(H5B_INS_RIGHT == anchor)
            idx++;  /* Don't have to memmove() child addresses down, just add new child */
        else
            /* Make room for the new child address */
            bt->child[idx + 1] = bt->child[idx];
    } /* end if */
    else {
        /* Make room for the new key */
        HDmemmove(base + shared->type->sizeof_nkey, base,
                  (bt->nchildren - idx) * shared->type->sizeof_nkey);
        H5MM_memcpy(base, md_key, shared->type->sizeof_nkey);

        /* The MD_KEY is the left key of the new node */
        if(H5B_INS_RIGHT == anchor)
            idx++;

        /* Make room for the new child address */
        HDmemmove(bt->child + idx + 1, bt->child + idx,
                  (bt->nchildren - idx) * sizeof(haddr_t));
    } /* end if */

    bt->child[idx] = child;
    bt->nchildren += 1;

    /* Mark node as dirty */
    *bt_flags |= H5AC__DIRTIED_FLAG;

    FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5B_insert_child() */


/*-------------------------------------------------------------------------
 * Function:	H5B__insert_helper
 *
 * Purpose:	Inserts the item UDATA into the tree rooted at ADDR and having
 *		the specified type.
 *
 *		On return, if LT_KEY_CHANGED is non-zero, then LT_KEY is
 *		the new native left key.  Similarly for RT_KEY_CHANGED
 *		and RT_KEY.
 *
 *		If the node splits, then MD_KEY contains the key that
 *		was split between the two nodes (that is, the key that
 *		appears as the max key in the left node and the min key
 *		in the right node).
 *
 * Return:	Success:	A B-tree operation.  The address of the new
 *				node, if the node splits, is returned through
 *				the NEW_NODE_P argument. The new node is always
 *				to the right of the previous node.  This
 *				function is called recursively and the return
 *				value influences the behavior of the caller.
 *				See also, declaration of H5B_ins_t.
 *
 *		Failure:	H5B_INS_ERROR
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jul  9 1997
 *
 *-------------------------------------------------------------------------
 */
static H5B_ins_t
H5B__insert_helper(H5F_t *f, H5B_ins_ud_t *bt_ud, const H5B_class_t *type,
    uint8_t *lt_key, hbool_t *lt_key_changed, uint8_t *md_key, void *udata,
    uint8_t *rt_key, hbool_t *rt_key_changed, H5B_ins_ud_t *split_bt_ud/*out*/)
{
    H5B_t       *bt;                    /* Convenience pointer to B-tree */
    H5UC_t	*rc_shared;             /* Ref-counted shared info */
    H5B_shared_t *shared;               /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    unsigned	lt = 0, idx = 0, rt;    /* Left, final & right index values */
    int         cmp = -1;               /* Key comparison value */
    H5B_ins_ud_t child_bt_ud = H5B_INS_UD_T_NULL; /* Child B-tree */
    H5B_ins_ud_t new_child_bt_ud = H5B_INS_UD_T_NULL; /* Newly split child B-tree */
    H5B_ins_t	my_ins = H5B_INS_ERROR;
    H5B_ins_t	ret_value = H5B_INS_ERROR;      /* Return value */

    FUNC_ENTER_STATIC

    /*
     * Check arguments
     */
    HDassert(f);
    HDassert(bt_ud);
    HDassert(bt_ud->bt);
    HDassert(H5F_addr_defined(bt_ud->addr));
    HDassert(type);
    HDassert(type->decode);
    HDassert(type->cmp3);
    HDassert(type->new_node);
    HDassert(lt_key);
    HDassert(lt_key_changed);
    HDassert(rt_key);
    HDassert(rt_key_changed);
    HDassert(split_bt_ud);
    HDassert(!split_bt_ud->bt);
    HDassert(!H5F_addr_defined(split_bt_ud->addr));
    HDassert(split_bt_ud->cache_flags == H5AC__NO_FLAGS_SET);

    bt = bt_ud->bt;

    *lt_key_changed = FALSE;
    *rt_key_changed = FALSE;

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /*
     * Use a binary search to find the child that will receive the new
     * data.  When the search completes IDX points to the child that
     * should get the new data.
     */
    rt = bt->nchildren;

    while(lt < rt && cmp) {
	idx = (lt + rt) / 2;
	if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
	    rt = idx;
	else
	    lt = idx + 1;
    } /* end while */

    /* Set up user data for cache callbacks */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;

    if(0 == bt->nchildren) {
	/*
	 * The value being inserted will be the only value in this tree. We
	 * must necessarily be at level zero.
	 */
	HDassert(0 == bt->level);
	if((type->new_node)(f, H5B_INS_FIRST, H5B_NKEY(bt, shared, 0), udata,
			     H5B_NKEY(bt, shared, 1), bt->child + 0/*out*/) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, H5B_INS_ERROR, "unable to create leaf node")
	bt->nchildren = 1;
        bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
	idx = 0;

	if(type->follow_min) {
	    if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
                     lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
                     rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
		HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "unable to insert first leaf node")
	} /* end if */
        else
	    my_ins = H5B_INS_NOOP;
    } else if(cmp < 0 && idx == 0) {
        if(bt->level > 0) {
            /*
             * The value being inserted is less than any value in this tree.
             * Follow the minimum branch out of this node to a subtree.
             */
            child_bt_ud.addr = bt->child[idx];
            if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
                HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")

            if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
                    H5B_NKEY(bt,shared,idx), lt_key_changed, md_key,
                    udata, H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
                    &new_child_bt_ud/*out*/)) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum subtree")
        } else if(type->follow_min) {
            /*
             * The value being inserted is less than any leaf node out of this
             * current node.  Follow the minimum branch to a leaf node and let
             * the subclass handle the problem.
             */
            if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
                    lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
                    rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
        } else {
            /*
             * The value being inserted is less than any leaf node out of the
             * current node. Create a new minimum leaf node out of this B-tree
             * node. This node is not empty (handled above).
             */
            my_ins = H5B_INS_LEFT;
            H5MM_memcpy(md_key, H5B_NKEY(bt,shared,idx), type->sizeof_nkey);
            if((type->new_node)(f, H5B_INS_LEFT, H5B_NKEY(bt, shared, idx), udata,
                    md_key, &new_child_bt_ud.addr/*out*/) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert minimum leaf node")
            *lt_key_changed = TRUE;
        } /* end else */

#ifdef H5_STRICT_FORMAT_CHECKS
        /* Since we are to the left of the leftmost key there must not be a left
         * sibling */
        if(H5F_addr_defined(bt->left))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
#endif /* H5_STRICT_FORMAT_CHECKS */
    } else if(cmp > 0 && idx + 1 >= bt->nchildren) {
        if (bt->level > 0) {
            /*
            * The value being inserted is larger than any value in this tree.
            * Follow the maximum branch out of this node to a subtree.
            */
            idx = bt->nchildren - 1;
            child_bt_ud.addr = bt->child[idx];
            if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
                HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")

            if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
                    H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
                    H5B_NKEY(bt, shared, idx + 1), rt_key_changed,
                    &new_child_bt_ud/*out*/)) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum subtree")
        } else if(type->follow_max) {
            /*
             * The value being inserted is larger than any leaf node out of the
             * current node.  Follow the maximum branch to a leaf node and let
             * the subclass handle the problem.
             */
            idx = bt->nchildren - 1;
            if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
                    lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
                    rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
        } else {
            /*
             * The value being inserted is larger than any leaf node out of the
             * current node.  Create a new maximum leaf node out of this B-tree
             * node.
             */
            idx = bt->nchildren - 1;
            my_ins = H5B_INS_RIGHT;
            H5MM_memcpy(md_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
            if((type->new_node)(f, H5B_INS_RIGHT, md_key, udata,
                    H5B_NKEY(bt, shared, idx + 1), &new_child_bt_ud.addr/*out*/) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert maximum leaf node")
            *rt_key_changed = TRUE;
        } /* end else */

#ifdef H5_STRICT_FORMAT_CHECKS
        /* Since we are to the right of the rightmost key there must not be a
         * right sibling */
        if(H5F_addr_defined(bt->right))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "internal error: likely corrupt key values")
#endif /* H5_STRICT_FORMAT_CHECKS */
    } else if(cmp) {
	/*
	 * We couldn't figure out which branch to follow out of this node. THIS
	 * IS A MAJOR PROBLEM THAT NEEDS TO BE FIXED --rpm.
	 */
	HDassert("INTERNAL HDF5 ERROR (contact rpm)" && 0);
#ifdef NDEBUG
	HDabort();
#endif /* NDEBUG */
    } else if(bt->level > 0) {
	/*
	 * Follow a branch out of this node to another subtree.
	 */
	HDassert(idx < bt->nchildren);
	child_bt_ud.addr = bt->child[idx];
        if(NULL == (child_bt_ud.bt = (H5B_t *)H5AC_protect(f, H5AC_BT, child_bt_ud.addr, &cache_udata, H5AC__NO_FLAGS_SET)))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node")

	if((int)(my_ins = H5B__insert_helper(f, &child_bt_ud, type,
                H5B_NKEY(bt, shared, idx), lt_key_changed, md_key, udata,
                H5B_NKEY(bt, shared, idx + 1), rt_key_changed, &new_child_bt_ud/*out*/)) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert subtree")
    } else {
	/*
	 * Follow a branch out of this node to a leaf node of some other type.
	 */
	HDassert(idx < bt->nchildren);
	if((int)(my_ins = (type->insert)(f, bt->child[idx], H5B_NKEY(bt, shared, idx),
                  lt_key_changed, md_key, udata, H5B_NKEY(bt, shared, idx + 1),
                  rt_key_changed, &new_child_bt_ud.addr/*out*/)) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert leaf node")
    }
    HDassert((int)my_ins >= 0);

    /*
     * Update the left and right keys of the current node.
     */
    if(*lt_key_changed) {
        bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
        if(idx > 0) {
            HDassert(type->critical_key == H5B_LEFT);
            HDassert(!(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins));
            *lt_key_changed = FALSE;
        } /* end if */
        else
            H5MM_memcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
    } /* end if */
    if(*rt_key_changed) {
        bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
        if(idx + 1 < bt->nchildren) {
            HDassert(type->critical_key == H5B_RIGHT);
            HDassert(!(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins));
            *rt_key_changed = FALSE;
        } /* end if */
        else
            H5MM_memcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
    } /* end if */

    /*
     * Handle changes/additions to children
     */
    HDassert(!(bt->level == 0) != !(child_bt_ud.bt));
    if(H5B_INS_CHANGE == my_ins) {
	/*
	 * The insertion simply changed the address for the child.
	 */
	HDassert(!child_bt_ud.bt);
	HDassert(bt->level == 0);
	bt->child[idx] = new_child_bt_ud.addr;
        bt_ud->cache_flags |= H5AC__DIRTIED_FLAG;
    } else if(H5B_INS_LEFT == my_ins || H5B_INS_RIGHT == my_ins) {
        unsigned *tmp_bt_flags_ptr = NULL;
        H5B_t	*tmp_bt;

	/*
	 * If this node is full then split it before inserting the new child.
	 */
	if(bt->nchildren == shared->two_k) {
	    if(H5B__split(f, bt_ud, idx, udata, split_bt_ud/*out*/) < 0)
		HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, H5B_INS_ERROR, "unable to split node")
	    if(idx < bt->nchildren) {
		tmp_bt = bt;
                tmp_bt_flags_ptr = &bt_ud->cache_flags;
	    } else {
		idx -= bt->nchildren;
		tmp_bt = split_bt_ud->bt;
                tmp_bt_flags_ptr = &split_bt_ud->cache_flags;
	    }
	} /* end if */
        else {
	    tmp_bt = bt;
            tmp_bt_flags_ptr = &bt_ud->cache_flags;
	} /* end else */

	/* Insert the child */
	if(H5B__insert_child(tmp_bt, tmp_bt_flags_ptr, idx, new_child_bt_ud.addr, my_ins, md_key) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, H5B_INS_ERROR, "can't insert child")
    } /* end else-if */

    /*
     * If this node split, return the mid key (the one that is shared
     * by the left and right node).
     */
    if(split_bt_ud->bt) {
	H5MM_memcpy(md_key, H5B_NKEY(split_bt_ud->bt, shared, 0), type->sizeof_nkey);
	ret_value = H5B_INS_RIGHT;
#ifdef H5B_DEBUG
	/*
	 * The max key in the original left node must be equal to the min key
	 * in the new node.
	 */
	cmp = (type->cmp2)(H5B_NKEY(bt, shared, bt->nchildren), udata,
			    H5B_NKEY(split_bt_ud->bt, shared, 0));
	HDassert(0 == cmp);
#endif
    } /* end if */
    else
	ret_value = H5B_INS_NOOP;

done:
    if(child_bt_ud.bt)
        if(H5AC_unprotect(f, H5AC_BT, child_bt_ud.addr, child_bt_ud.bt, child_bt_ud.cache_flags) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to unprotect child")

    if(new_child_bt_ud.bt)
        if(H5AC_unprotect(f, H5AC_BT, new_child_bt_ud.addr, new_child_bt_ud.bt, new_child_bt_ud.cache_flags) < 0)
            HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to unprotect new child")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_insert_helper() */


/*-------------------------------------------------------------------------
 * Function:	H5B__iterate_helper
 *
 * Purpose:	Calls the list callback for each leaf node of the
 *		B-tree, passing it the caller's UDATA structure.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jun 23 1997
 *
 *-------------------------------------------------------------------------
 */
static herr_t
H5B__iterate_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
    H5B_operator_t op, void *udata)
{
    H5B_t               *bt = NULL;     /* Pointer to current B-tree node */
    H5UC_t	        *rc_shared;     /* Ref-counted shared info */
    H5B_shared_t        *shared;        /* Pointer to shared B-tree info */
    H5B_cache_ud_t      cache_udata;    /* User-data for metadata cache callback */
    unsigned            u;              /* Local index variable */
    herr_t              ret_value = H5_ITER_CONT; /* Return value */

    FUNC_ENTER_STATIC

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(H5F_addr_defined(addr));
    HDassert(op);
    HDassert(udata);

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /* Protect the initial/current node */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5_ITER_ERROR, "unable to load B-tree node")

    /* Iterate over node's children */
    for(u = 0; u < bt->nchildren && ret_value == H5_ITER_CONT; u++) {
        if(bt->level > 0)
            ret_value = H5B__iterate_helper(f, type, bt->child[u], op, udata);
        else
            ret_value = (*op)(f, H5B_NKEY(bt, shared, u), bt->child[u], H5B_NKEY(bt, shared, u + 1), udata);
        if(ret_value < 0)
            HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");
    } /* end for */

done:
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5_ITER_ERROR, "unable to release B-tree node")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__iterate_helper() */


/*-------------------------------------------------------------------------
 * Function:	H5B_iterate
 *
 * Purpose:	Calls the list callback for each leaf node of the
 *		B-tree, passing it the UDATA structure.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Robb Matzke
 *		matzke@llnl.gov
 *		Jun 23 1997
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_iterate(H5F_t *f, const H5B_class_t *type, haddr_t addr,
    H5B_operator_t op, void *udata)
{
    herr_t ret_value = FAIL;            /* Return value */

    FUNC_ENTER_NOAPI_NOERR

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(H5F_addr_defined(addr));
    HDassert(op);
    HDassert(udata);

    /* Iterate over the B-tree records */
    if((ret_value = H5B__iterate_helper(f, type, addr, op, udata)) < 0)
        HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_iterate() */


/*-------------------------------------------------------------------------
 * Function:	H5B__remove_helper
 *
 * Purpose:	The recursive part of removing an item from a B-tree.  The
 *		sub B-tree that is being considered is located at ADDR and
 *		the item to remove is described by UDATA.  If the removed
 *		item falls at the left or right end of the current level then
 *		it might be necessary to adjust the left and/or right keys
 *		(LT_KEY and/or RT_KEY) to to indicate that they changed by
 * 		setting LT_KEY_CHANGED and/or RT_KEY_CHANGED.
 *
 * Return:	Success:	A B-tree operation, see comments for
 *				H5B_ins_t declaration.  This function is
 *				called recursively and the return value
 *				influences the actions of the caller. It is
 *				also called by H5B_remove().
 *
 *		Failure:	H5B_INS_ERROR, a negative value.
 *
 * Programmer:	Robb Matzke
 *              Wednesday, September 16, 1998
 *
 *-------------------------------------------------------------------------
 */
static H5B_ins_t
H5B__remove_helper(H5F_t *f, haddr_t addr, const H5B_class_t *type, int level,
    uint8_t *lt_key/*out*/, hbool_t *lt_key_changed/*out*/, void *udata,
    uint8_t *rt_key/*out*/, hbool_t *rt_key_changed/*out*/)
{
    H5B_t	*bt = NULL, *sibling = NULL;
    unsigned	bt_flags = H5AC__NO_FLAGS_SET;
    H5UC_t	*rc_shared;             /* Ref-counted shared info */
    H5B_shared_t *shared;               /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    unsigned    idx = 0, lt = 0, rt;    /* Final, left & right indices */
    int         cmp = 1;                /* Key comparison value */
    H5B_ins_t	ret_value = H5B_INS_ERROR;

    FUNC_ENTER_STATIC

    HDassert(f);
    HDassert(H5F_addr_defined(addr));
    HDassert(type);
    HDassert(type->decode);
    HDassert(type->cmp3);
    HDassert(lt_key && lt_key_changed);
    HDassert(udata);
    HDassert(rt_key && rt_key_changed);

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, H5B_INS_ERROR, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /*
     * Perform a binary search to locate the child which contains the thing
     * for which we're searching.
     */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load B-tree node")

    rt = bt->nchildren;
    while(lt < rt && cmp) {
	idx = (lt + rt) / 2;
	if((cmp = (type->cmp3)(H5B_NKEY(bt, shared, idx), udata, H5B_NKEY(bt, shared, idx + 1))) < 0)
	    rt = idx;
	else
	    lt = idx + 1;
    } /* end while */
    if(cmp)
	HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "B-tree key not found")

    /*
     * Follow the link to the subtree or to the data node.  The return value
     * will be one of H5B_INS_ERROR, H5B_INS_NOOP, or H5B_INS_REMOVE.
     */
    HDassert(idx < bt->nchildren);
    if(bt->level > 0) {
	/* We're at an internal node -- call recursively */
	if((int)(ret_value = H5B__remove_helper(f, bt->child[idx], type,
                level + 1, H5B_NKEY(bt, shared, idx)/*out*/,
                lt_key_changed/*out*/, udata, H5B_NKEY(bt, shared, idx + 1)/*out*/,
                rt_key_changed/*out*/)) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in subtree")
    } else if(type->remove) {
	/*
	 * We're at a leaf node but the leaf node points to an object that
	 * has a removal method.  Pass the removal request to the pointed-to
	 * object and let it decide how to progress.
	 */
	if((int)(ret_value = (type->remove)(f, bt->child[idx],
                H5B_NKEY(bt, shared, idx), lt_key_changed, udata,
                H5B_NKEY(bt, shared, idx + 1), rt_key_changed)) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, H5B_INS_ERROR, "key not found in leaf node")
    } else {
	/*
	 * We're at a leaf node which points to an object that has no removal
	 * method.  The best we can do is to leave the object alone but
	 * remove the B-tree reference to the object.
	 */
	*lt_key_changed = FALSE;
	*rt_key_changed = FALSE;
	ret_value = H5B_INS_REMOVE;
    }

    /*
     * Update left and right key dirty bits if the subtree indicates that they
     * have changed.  If the subtree's left key changed and the subtree is the
     * left-most child of the current node then we must update the key in our
     * parent and indicate that it changed.  Similarly, if the right subtree
     * key changed and it's the right most key of this node we must update
     * our right key and indicate that it changed.
     */
    if(*lt_key_changed) {
        HDassert(type->critical_key == H5B_LEFT);
        bt_flags |= H5AC__DIRTIED_FLAG;

        if(idx > 0)
            /* Don't propagate change out of this B-tree node */
            *lt_key_changed = FALSE;
        else
            H5MM_memcpy(lt_key, H5B_NKEY(bt, shared, idx), type->sizeof_nkey);
    } /* end if */
    if(*rt_key_changed) {
        HDassert(type->critical_key == H5B_RIGHT);
        bt_flags |= H5AC__DIRTIED_FLAG;
        if(idx + 1 < bt->nchildren)
            /* Don't propagate change out of this B-tree node */
            *rt_key_changed = FALSE;
        else
            H5MM_memcpy(rt_key, H5B_NKEY(bt, shared, idx + 1), type->sizeof_nkey);
    } /* end if */

    /*
     * If the subtree returned H5B_INS_REMOVE then we should remove the
     * subtree entry from the current node.  There are four cases:
     */
    if(H5B_INS_REMOVE == ret_value) {
        /* Clients should not change keys when a node is removed.  This function
         * will handle it as appropriate, based on the value of bt->critical_key
         */
        HDassert(!(*lt_key_changed));
        HDassert(!(*rt_key_changed));

        if(1 == bt->nchildren) {
            /*
             * The subtree is the only child of this node.  Discard both
             * keys and the subtree pointer. Free this node (unless it's the
             * root node) and return H5B_INS_REMOVE.
             */
            /* Only delete the node if it is not the root node.  Note that this
             * "level" is the opposite of bt->level */
            if(level > 0) {
                /* Fix siblings, making sure that the keys remain consistent
                 * between siblings.  Overwrite the key that that is not
                 * "critical" for any child in its node to maintain this
                 * consistency (and avoid breaking key/child consistency) */
                if(H5F_addr_defined(bt->left)) {
                    if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->left, &cache_udata, H5AC__NO_FLAGS_SET)))
                        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to load node from tree")

                    /* Copy right-most key from deleted node to right-most key
                     * in its left neighbor, but only if it is not the critical
                     * key for the right-most child of the left neighbor */
                    if(type->critical_key == H5B_LEFT)
                        H5MM_memcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
                                H5B_NKEY(bt, shared, 1), type->sizeof_nkey);

                    sibling->right = bt->right;

                    if(H5AC_unprotect(f, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
                        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
                    sibling = NULL;   /* Make certain future references will be caught */
                } /* end if */
                if(H5F_addr_defined(bt->right)) {
                    if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
                        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to unlink node from tree")

                    /* Copy left-most key from deleted node to left-most key in
                     * its right neighbor, but only if it is not the critical
                     * key for the left-most child of the right neighbor */
                    if(type->critical_key == H5B_RIGHT)
                        H5MM_memcpy(H5B_NKEY(sibling, shared, 0),
                                H5B_NKEY(bt, shared, 0), type->sizeof_nkey);

                    sibling->left = bt->left;

                    if(H5AC_unprotect(f, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
                        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
                    sibling = NULL;   /* Make certain future references will be caught */
                } /* end if */

                /* Update bt struct */
                bt->left = HADDR_UNDEF;
                bt->right = HADDR_UNDEF;
                bt->nchildren = 0;

                /* Delete the node from disk (via the metadata cache) */
		bt_flags |= H5AC__DIRTIED_FLAG | H5AC__FREE_FILE_SPACE_FLAG;
                H5_CHECK_OVERFLOW(shared->sizeof_rnode, size_t, hsize_t);
                if(H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags | H5AC__DELETED_FLAG) < 0) {
                    bt = NULL;
                    bt_flags = H5AC__NO_FLAGS_SET;
                    HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to free B-tree node")
                } /* end if */
                bt = NULL;
                bt_flags = H5AC__NO_FLAGS_SET;
            } else {
                /* We removed the last child in the root node, set the level
                 * back to 0 (as well as nchildren) */
                bt->nchildren = 0;
                bt->level = 0;
                bt_flags |= H5AC__DIRTIED_FLAG;
            } /* end else */
        } else if(0 == idx) {
            /*
             * The subtree is the left-most child of this node. We update the
             * key and child arrays and lt_key as appropriate, depending on the
             * status of bt->critical_key.  Return H5B_INS_NOOP.
             */
            if(type->critical_key == H5B_LEFT) {
                /* Slide all keys down 1, update lt_key */
                HDmemmove(H5B_NKEY(bt, shared, 0), H5B_NKEY(bt, shared, 1),
                        bt->nchildren * type->sizeof_nkey);
                H5MM_memcpy(lt_key, H5B_NKEY(bt, shared, 0), type->sizeof_nkey);
                *lt_key_changed = TRUE;
            } else
                /* Slide all but the leftmost 2 keys down, leaving the leftmost
                 * key intact (the right key of the leftmost child is
                 * overwritten) */
                HDmemmove(H5B_NKEY(bt, shared, 1), H5B_NKEY(bt, shared, 2),
                        (bt->nchildren - 1) * type->sizeof_nkey);

            HDmemmove(bt->child,
                    bt->child + 1,
                    (bt->nchildren - 1) * sizeof(haddr_t));

            bt->nchildren -= 1;
            bt_flags |= H5AC__DIRTIED_FLAG;
            ret_value = H5B_INS_NOOP;
        } else if(idx + 1 == bt->nchildren) {
            /*
             * The subtree is the right-most child of this node. We update the
             * key and child arrays and rt_key as appropriate, depending on the
             * status of bt->critical_key.  Return H5B_INS_NOOP.
             */
            if(type->critical_key == H5B_LEFT)
                /* Slide the rightmost key down one, overwriting the left key of
                 * the deleted (righmost) child */
                HDmemmove(H5B_NKEY(bt, shared, bt->nchildren - 1),
                        H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);
            else {
                /* Just update rt_key */
                H5MM_memcpy(rt_key, H5B_NKEY(bt, shared, bt->nchildren - 1),
                        type->sizeof_nkey);
                *rt_key_changed = TRUE;
            } /* end else */

            bt->nchildren -= 1;
            bt_flags |= H5AC__DIRTIED_FLAG;
            ret_value = H5B_INS_NOOP;
        } else {
            /*
             * There are subtrees out of this node to both the left and right of
             * the subtree being removed.  The subtree and its critical key are
             * removed from this node and all keys and nodes to the right are
             * shifted left by one place.  The subtree has already been freed.
             * Return H5B_INS_NOOP.
             */
            if(type->critical_key == H5B_LEFT)
                HDmemmove(H5B_NKEY(bt, shared, idx),
                        H5B_NKEY(bt, shared, idx + 1),
                        (bt->nchildren - idx) * type->sizeof_nkey);
            else
                HDmemmove(H5B_NKEY(bt, shared, idx + 1),
                        H5B_NKEY(bt, shared, idx + 2),
                        (bt->nchildren - 1 - idx) * type->sizeof_nkey);

            HDmemmove(bt->child + idx,
                    bt->child + idx + 1,
                    (bt->nchildren - 1 - idx) * sizeof(haddr_t));

            bt->nchildren -= 1;
            bt_flags |= H5AC__DIRTIED_FLAG;
            ret_value = H5B_INS_NOOP;
        } /* end else */
    } else /* H5B_INS_REMOVE != ret_value */
        ret_value = H5B_INS_NOOP;

    /* Patch keys in neighboring trees if necessary */
    if(*lt_key_changed && H5F_addr_defined(bt->left)) {
        HDassert(type->critical_key == H5B_LEFT);
        HDassert(level > 0);

        /* Update the rightmost key in the left sibling */
        if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->left, &cache_udata, H5AC__NO_FLAGS_SET)))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to protect node")

        H5MM_memcpy(H5B_NKEY(sibling, shared, sibling->nchildren),
                H5B_NKEY(bt, shared, 0), type->sizeof_nkey);

        if(H5AC_unprotect(f, H5AC_BT, bt->left, sibling, H5AC__DIRTIED_FLAG) < 0)
            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
        sibling = NULL;   /* Make certain future references will be caught */
    } /* end if */
    else if(*rt_key_changed && H5F_addr_defined(bt->right)) {
        HDassert(type->critical_key == H5B_RIGHT);
        HDassert(level > 0);

        /* Update the lefttmost key in the right sibling */
        if(NULL == (sibling = (H5B_t *)H5AC_protect(f, H5AC_BT, bt->right, &cache_udata, H5AC__NO_FLAGS_SET)))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, H5B_INS_ERROR, "unable to protect node")

        H5MM_memcpy(H5B_NKEY(sibling, shared, 0),
                H5B_NKEY(bt, shared, bt->nchildren), type->sizeof_nkey);

        if(H5AC_unprotect(f, H5AC_BT, bt->right, sibling, H5AC__DIRTIED_FLAG) < 0)
            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node from tree")
        sibling = NULL;   /* Make certain future references will be caught */
    } /* end else */

done:
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, bt_flags) < 0)
	HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, H5B_INS_ERROR, "unable to release node")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__remove_helper() */


/*-------------------------------------------------------------------------
 * Function:	H5B_remove
 *
 * Purpose:	Removes an item from a B-tree.
 *
 * Note:	The current version does not attempt to rebalance the tree.
 *              (Read the paper Yao & Lehman paper for details on why)
 *
 * Return:	Non-negative on success/Negative on failure (failure includes
 *		not being able to find the object which is to be removed).
 *
 * Programmer:	Robb Matzke
 *              Wednesday, September 16, 1998
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_remove(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
    /* These are defined this way to satisfy alignment constraints */
    uint64_t	_lt_key[128], _rt_key[128];
    uint8_t	*lt_key = (uint8_t*)_lt_key;	/*left key*/
    uint8_t	*rt_key = (uint8_t*)_rt_key;	/*right key*/
    hbool_t	lt_key_changed = FALSE;		/*left key changed?*/
    hbool_t	rt_key_changed = FALSE;		/*right key changed?*/
    herr_t      ret_value = SUCCEED;            /* Return value */

    FUNC_ENTER_NOAPI(FAIL)

    /* Check args */
    HDassert(f);
    HDassert(type);
    HDassert(type->sizeof_nkey <= sizeof _lt_key);
    HDassert(H5F_addr_defined(addr));

    /* The actual removal */
    if(H5B_INS_ERROR == H5B__remove_helper(f, addr, type, 0, lt_key, &lt_key_changed, udata, rt_key, &rt_key_changed))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to remove entry from B-tree")

#ifdef H5B_DEBUG
    H5B__assert(f, addr, type, udata);
#endif
done:
    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_remove() */


/*-------------------------------------------------------------------------
 * Function:	H5B_delete
 *
 * Purpose:	Deletes an entire B-tree from the file, calling the 'remove'
 *              callbacks for each node.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Quincey Koziol
 *              Thursday, March 20, 2003
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_delete(H5F_t *f, const H5B_class_t *type, haddr_t addr, void *udata)
{
    H5B_t	*bt = NULL;             /* B-tree node being operated on */
    H5UC_t	*rc_shared;             /* Ref-counted shared info */
    H5B_shared_t *shared;               /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata;         /* User-data for metadata cache callback */
    unsigned    u;                      /* Local index variable */
    herr_t      ret_value = SUCCEED;    /* Return value */

    FUNC_ENTER_NOAPI(FAIL)

    /* Check args */
    HDassert(f);
    HDassert(type);
    HDassert(H5F_addr_defined(addr));

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, udata)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /* Lock this B-tree node into memory for now */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__NO_FLAGS_SET)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")

    /* Iterate over all children in tree, deleting them */
    if(bt->level > 0) {
        /* Iterate over all children in node, deleting them */
        for(u = 0; u < bt->nchildren; u++)
            if(H5B_delete(f, type, bt->child[u], udata) < 0)
                HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to delete B-tree node")

    } /* end if */
    else {
        hbool_t lt_key_changed, rt_key_changed; /* Whether key changed (unused here, just for callback) */

        /* Check for removal callback */
        if(type->remove) {
            /* Iterate over all entries in node, calling callback */
            for(u = 0; u < bt->nchildren; u++) {
                /* Call user's callback for each entry */
                if((type->remove)(f, bt->child[u], H5B_NKEY(bt, shared, u),
                        &lt_key_changed, udata, H5B_NKEY(bt, shared, u + 1),
                        &rt_key_changed) < H5B_INS_NOOP)
                    HGOTO_ERROR(H5E_BTREE, H5E_NOTFOUND, FAIL, "can't remove B-tree node")
            } /* end for */
        } /* end if */
    } /* end else */

done:
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__DELETED_FLAG | H5AC__FREE_FILE_SPACE_FLAG) < 0)
        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node in cache")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_delete() */


/*-------------------------------------------------------------------------
 * Function:	H5B_shared_new
 *
 * Purpose:	Allocates & constructs a shared v1 B-tree struct for client.
 *
 * Return:	Success:	non-NULL pointer to struct allocated
 *		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *		koziol@hdfgroup.org
 *		May 27 2008
 *
 *-------------------------------------------------------------------------
 */
H5B_shared_t *
H5B_shared_new(const H5F_t *f, const H5B_class_t *type, size_t sizeof_rkey)
{
    H5B_shared_t *shared = NULL;        /* New shared B-tree struct */
    size_t	u;                      /* Local index variable */
    H5B_shared_t *ret_value = NULL;     /* Return value */

    FUNC_ENTER_NOAPI(NULL)

    /*
     * Check arguments.
     */
    HDassert(type);

    /* Allocate space for the shared structure */
    if(NULL == (shared = H5FL_CALLOC(H5B_shared_t)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for shared B-tree info")

    /* Set up the "global" information for this file's groups */
    shared->type = type;
    shared->two_k = 2 * H5F_KVALUE(f, type);
    shared->sizeof_addr = H5F_SIZEOF_ADDR(f);
    shared->sizeof_len = H5F_SIZEOF_SIZE(f);
    shared->sizeof_rkey = sizeof_rkey;
    HDassert(shared->sizeof_rkey);
    shared->sizeof_keys = (shared->two_k + 1) * type->sizeof_nkey;
    shared->sizeof_rnode = ((size_t)H5B_SIZEOF_HDR(f) + /*node header	*/
	    shared->two_k * H5F_SIZEOF_ADDR(f) +	/*child pointers */
	    (shared->two_k + 1) * shared->sizeof_rkey);	/*keys		*/
    HDassert(shared->sizeof_rnode);

    /* Allocate and clear shared buffers */
    if(NULL == (shared->page = H5FL_BLK_MALLOC(page, shared->sizeof_rnode)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree page")
    HDmemset(shared->page, 0, shared->sizeof_rnode);

    if(NULL == (shared->nkey = H5FL_SEQ_MALLOC(size_t, (size_t)(shared->two_k + 1))))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree native keys")

    /* Initialize the offsets into the native key buffer */
    for(u = 0; u < (shared->two_k + 1); u++)
        shared->nkey[u] = u * type->sizeof_nkey;

    /* Set return value */
    ret_value = shared;

done:
    if(NULL == ret_value)
        if(shared) {
            if(shared->page)
                shared->page = H5FL_BLK_FREE(page, shared->page);
            if(shared->nkey)
                shared->nkey = H5FL_SEQ_FREE(size_t, shared->nkey);
            shared = H5FL_FREE(H5B_shared_t, shared);
        } /* end if */

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_shared_new() */


/*-------------------------------------------------------------------------
 * Function:	H5B_shared_free
 *
 * Purpose:	Free B-tree shared info
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Quincey Koziol
 *              Tuesday, May 27, 2008
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_shared_free(void *_shared)
{
    H5B_shared_t *shared = (H5B_shared_t *)_shared;

    FUNC_ENTER_NOAPI_NOINIT_NOERR

    /* Free the raw B-tree node buffer */
    shared->page = H5FL_BLK_FREE(page, shared->page);

    /* Free the B-tree native key offsets buffer */
    shared->nkey = H5FL_SEQ_FREE(size_t, shared->nkey);

    /* Free the shared B-tree info */
    shared = H5FL_FREE(H5B_shared_t, shared);

    FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5B_shared_free() */


/*-------------------------------------------------------------------------
 * Function:	H5B__copy
 *
 * Purpose:	Deep copies an existing H5B_t node.
 *
 * Return:	Success:	Pointer to H5B_t object.
 *
 * 		Failure:	NULL
 *
 * Programmer:	Quincey Koziol
 *		koziol@ncsa.uiuc.edu
 *		Apr 18 2000
 *
 *-------------------------------------------------------------------------
 */
static H5B_t *
H5B__copy(const H5B_t *old_bt)
{
    H5B_t		*new_node = NULL;
    H5B_shared_t        *shared;        /* Pointer to shared B-tree info */
    H5B_t		*ret_value = NULL;      /* Return value */

    FUNC_ENTER_STATIC

    /*
     * Check arguments.
     */
    HDassert(old_bt);
    shared = (H5B_shared_t *)H5UC_GET_OBJ(old_bt->rc_shared);
    HDassert(shared);

    /* Allocate memory for the new H5B_t object */
    if(NULL == (new_node = H5FL_MALLOC(H5B_t)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree root node")

    /* Copy the main structure */
    H5MM_memcpy(new_node, old_bt, sizeof(H5B_t));

    /* Reset cache info */
    HDmemset(&new_node->cache_info, 0, sizeof(H5AC_info_t));

    if(NULL == (new_node->native = H5FL_BLK_MALLOC(native_block, shared->sizeof_keys)) ||
            NULL == (new_node->child = H5FL_SEQ_MALLOC(haddr_t, (size_t)shared->two_k)))
        HGOTO_ERROR(H5E_BTREE, H5E_CANTALLOC, NULL, "memory allocation failed for B-tree root node")

    /* Copy the other structures */
    H5MM_memcpy(new_node->native, old_bt->native, shared->sizeof_keys);
    H5MM_memcpy(new_node->child, old_bt->child, (sizeof(haddr_t) * shared->two_k));

    /* Increment the ref-count on the raw page */
    H5UC_INC(new_node->rc_shared);

    /* Set return value */
    ret_value = new_node;

done:
    if(NULL == ret_value) {
        if(new_node) {
	    new_node->native = H5FL_BLK_FREE(native_block, new_node->native);
	    new_node->child = H5FL_SEQ_FREE(haddr_t, new_node->child);
	    new_node = H5FL_FREE(H5B_t, new_node);
        } /* end if */
    } /* end if */

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__copy() */


/*-------------------------------------------------------------------------
 * Function:	H5B__get_info_helper
 *
 * Purpose:	Walks the B-tree nodes, getting information for all of them.
 *
 * Return:	Non-negative on success/Negative on failure
 *
 * Programmer:	Quincey Koziol
 *		koziol@hdfgroup.org
 *		Jun  3 2008
 *
 *-------------------------------------------------------------------------
 */
static herr_t
H5B__get_info_helper(H5F_t *f, const H5B_class_t *type, haddr_t addr,
    const H5B_info_ud_t *info_udata)
{
    H5B_t *bt = NULL;           /* Pointer to current B-tree node */
    H5UC_t *rc_shared;          /* Ref-counted shared info */
    H5B_shared_t *shared;       /* Pointer to shared B-tree info */
    H5B_cache_ud_t cache_udata; /* User-data for metadata cache callback */
    unsigned level;		/* Node level			     */
    size_t sizeof_rnode;	/* Size of raw (disk) node	     */
    haddr_t next_addr;          /* Address of next node to the right */
    haddr_t left_child;         /* Address of left-most child in node */
    herr_t ret_value = SUCCEED; /* Return value */

    FUNC_ENTER_STATIC

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(H5F_addr_defined(addr));
    HDassert(info_udata);
    HDassert(info_udata->bt_info);
    HDassert(info_udata->udata);

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, info_udata->udata)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    shared = (H5B_shared_t *)H5UC_GET_OBJ(rc_shared);
    HDassert(shared);

    /* Get the raw node size for iteration */
    sizeof_rnode = shared->sizeof_rnode;

    /* Protect the initial/current node */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B-tree node")

    /* Cache information from this node */
    left_child = bt->child[0];
    next_addr = bt->right;
    level = bt->level;

    /* Update B-tree info */
    info_udata->bt_info->size += sizeof_rnode;
    info_udata->bt_info->num_nodes++;

    /* Release current node */
    if(H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
        HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
    bt = NULL;

    /*
     * Follow the right-sibling pointer from node to node until we've
     *      processed all nodes.
     */
    while(H5F_addr_defined(next_addr)) {
        /* Protect the next node to the right */
        addr = next_addr;
        if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
            HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "B-tree node")

        /* Cache information from this node */
        next_addr = bt->right;

        /* Update B-tree info */
        info_udata->bt_info->size += sizeof_rnode;
        info_udata->bt_info->num_nodes++;

        /* Unprotect node */
        if(H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
            HGOTO_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")
        bt = NULL;
    } /* end while */

    /* Check for another "row" of B-tree nodes to iterate over */
    if(level > 0) {
	/* Keep following the left-most child until we reach a leaf node. */
	if(H5B__get_info_helper(f, type, left_child, info_udata) < 0)
	    HGOTO_ERROR(H5E_BTREE, H5E_CANTLIST, FAIL, "unable to list B-tree node")
    } /* end if */

done:
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B__get_info_helper() */


/*-------------------------------------------------------------------------
 * Function:    H5B_get_info
 *
 * Purpose:     Return the amount of storage used for the btree.
 *
 * Return:      Non-negative on success/Negative on failure
 *
 * Programmer:  Vailin Choi
 *              June 19, 2007
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B_get_info(H5F_t *f, const H5B_class_t *type, haddr_t addr,
    H5B_info_t *bt_info, H5B_operator_t op, void *udata)
{
    H5B_info_ud_t       info_udata;     /* User-data for B-tree size iteration */
    herr_t		ret_value = SUCCEED;      /* Return value */

    FUNC_ENTER_NOAPI(FAIL)

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);
    HDassert(bt_info);
    HDassert(H5F_addr_defined(addr));
    HDassert(udata);

    /* Portably initialize B-tree info struct */
    HDmemset(bt_info, 0, sizeof(*bt_info));

    /* Set up internal user-data for the B-tree 'get info' helper routine */
    info_udata.bt_info = bt_info;
    info_udata.udata = udata;

    /* Iterate over the B-tree nodes */
    if(H5B__get_info_helper(f, type, addr, &info_udata) < 0)
        HGOTO_ERROR(H5E_BTREE, H5E_BADITER, FAIL, "B-tree iteration failed")

    /* Iterate over the B-tree records, making any "leaf" callbacks */
    /* (Only if operator defined) */
    if(op)
        if((ret_value = H5B__iterate_helper(f, type, addr, op, udata)) < 0)
            HERROR(H5E_BTREE, H5E_BADITER, "B-tree iteration failed");

done:
    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_get_info() */


/*-------------------------------------------------------------------------
 * Function:    H5B_valid
 *
 * Purpose:     Attempt to load a B-tree node.
 *
 * Return:      Non-negative on success/Negative on failure
 *
 * Programmer:  Neil Fortner
 *              March 17, 2009
 *
 *-------------------------------------------------------------------------
 */
htri_t
H5B_valid(H5F_t *f, const H5B_class_t *type, haddr_t addr)
{
    H5B_t               *bt = NULL;             /* The B-tree */
    H5UC_t              *rc_shared;             /* Ref-counted shared info */
    H5B_cache_ud_t      cache_udata;            /* User-data for metadata cache callback */
    htri_t		ret_value = SUCCEED;    /* Return value */

    FUNC_ENTER_NOAPI(FAIL)

    /*
     * Check arguments.
     */
    HDassert(f);
    HDassert(type);

    if(!H5F_addr_defined(addr))
        HGOTO_ERROR(H5E_BTREE, H5E_BADVALUE, FAIL, "address is undefined")

    /* Get shared info for B-tree */
    if(NULL == (rc_shared = (type->get_shared)(f, NULL)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTGET, FAIL, "can't retrieve B-tree's shared ref. count object")
    HDassert(H5UC_GET_OBJ(rc_shared) != NULL);

    /*
     * Load the tree node.
     */
    cache_udata.f = f;
    cache_udata.type = type;
    cache_udata.rc_shared = rc_shared;
    if(NULL == (bt = (H5B_t *)H5AC_protect(f, H5AC_BT, addr, &cache_udata, H5AC__READ_ONLY_FLAG)))
	HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to protect B-tree node")

done:
    /* Release the node */
    if(bt && H5AC_unprotect(f, H5AC_BT, addr, bt, H5AC__NO_FLAGS_SET) < 0)
        HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B-tree node")

    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5B_valid() */


/*-------------------------------------------------------------------------
 * Function:    H5B__node_dest
 *
 * Purpose:     Destroy/release a B-tree node
 *
 * Return:      Success:        SUCCEED
 *              Failure:        FAIL
 *
 * Programmer:  Quincey Koziol
 *              koziol@hdfgroup.org
 *              Mar 26, 2008
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5B__node_dest(H5B_t *bt)
{
    FUNC_ENTER_PACKAGE_NOERR

    /* check arguments */
    HDassert(bt);
    HDassert(bt->rc_shared);

    bt->child = H5FL_SEQ_FREE(haddr_t, bt->child);
    bt->native = H5FL_BLK_FREE(native_block, bt->native);
    H5UC_DEC(bt->rc_shared);
    bt = H5FL_FREE(H5B_t, bt);

    FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5B__node_dest() */