summaryrefslogtreecommitdiffstats
path: root/src/H5B.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5B.c')
-rw-r--r--src/H5B.c1177
1 files changed, 1177 insertions, 0 deletions
diff --git a/src/H5B.c b/src/H5B.c
new file mode 100644
index 0000000..f3a7052
--- /dev/null
+++ b/src/H5B.c
@@ -0,0 +1,1177 @@
+/*-------------------------------------------------------------------------
+ * Copyright (C) 1997 National Center for Supercomputing Applications.
+ * All rights reserved.
+ *
+ *-------------------------------------------------------------------------
+ *
+ * Created: hdf5btree.c
+ * Jul 10 1997
+ * Robb Matzke <robb@maya.nuance.com>
+ *
+ * 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.
+ *
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+
+/*
+ * Define this if the root address of a B-link tree should never change.
+ *
+ * If this isn't defined and the root node of a tree splits, then the
+ * new root (which points to the old root plus the new node from the
+ * split) will be at a new file address.
+ *
+ * But if this is defined, then the old root will be copied to a new
+ * location and the new root will occupy the file memory vacated by the
+ * old root.
+ */
+#define H5B_ANCHOR_ROOT
+
+/* system headers */
+#include <assert.h>
+#include "hdf5.h"
+
+/* private headers */
+#include "H5ACprivate.h" /*cache */
+#include "H5Bprivate.h" /*B-link trees */
+#include "H5MFprivate.h" /*File memory management */
+#include "H5MMprivate.h" /*Core memory management */
+
+#define BOUND(MIN,X,MAX) ((MIN)<(X)?(MIN):((MAX)>(X)?(MAX):(X)))
+#define false 0
+#define true 1
+
+/* PRIVATE PROTOTYPES */
+static off_t H5B_insert_helper (hdf5_file_t *f, off_t addr,
+ const H5B_class_t *type,
+ uint8 *lt_key, intn *lt_key_changed,
+ uint8 *md_key, void *udata,
+ uint8 *rt_key, intn *rt_key_changed);
+static herr_t H5B_flush (hdf5_file_t *f, hbool_t destroy, off_t addr,
+ H5B_t *b);
+static H5B_t *H5B_load (hdf5_file_t *f, off_t addr, const void *_data);
+static herr_t H5B_decode_key (hdf5_file_t *f, H5B_t *bt, intn idx);
+static size_t H5B_nodesize (hdf5_file_t *f, const H5B_class_t *type,
+ size_t *total_nkey_size, size_t sizeof_rkey);
+
+/* H5B inherits cache-like properties from H5AC */
+static const H5AC_class_t H5AC_BT[1] = {{
+ (void*(*)(hdf5_file_t*,off_t,const void*))H5B_load,
+ (herr_t(*)(hdf5_file_t*,hbool_t,off_t,void*))H5B_flush,
+}};
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_new
+ *
+ * Purpose: Creates a new empty B-tree leaf node.
+ *
+ * Return: Success: address of new node.
+ *
+ * Failure: 0
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+off_t
+H5B_new (hdf5_file_t *f, const H5B_class_t *type, size_t sizeof_rkey)
+{
+ H5B_t *bt=NULL;
+ off_t addr;
+ size_t size;
+ size_t total_native_keysize;
+ intn offset, i;
+
+ /*
+ * Allocate file and memory data structures.
+ */
+ size = H5B_nodesize (f, type, &total_native_keysize, sizeof_rkey);
+ if ((addr = H5MF_alloc (f, size))<=0) return 0;
+ bt = H5MM_xmalloc (sizeof(H5B_t));
+ bt->type = type;
+ bt->sizeof_rkey = sizeof_rkey;
+ bt->dirty = 1;
+ bt->ndirty = 0;
+ bt->type = type;
+ bt->level = 0;
+ bt->left = bt->right = 0;
+ bt->nchildren = 0;
+ bt->page = H5MM_xmalloc (size);
+ bt->native = H5MM_xmalloc (total_native_keysize);
+ bt->child = H5MM_xmalloc (2*type->k * sizeof(off_t));
+ bt->key = H5MM_xmalloc ((2*type->k+1) * sizeof(H5B_key_t));
+
+ /*
+ * Initialize each entry's raw child and key pointers to point into the
+ * `page' buffer. Each native key pointer should be null until the key is
+ * translated to native format.
+ */
+ for (i=0,offset=H5B_HDR_SIZE(f);
+ i<2*type->k;
+ i++,offset+=bt->sizeof_rkey+SIZEOF_OFFSET(f)) {
+
+ bt->key[i].dirty = 0;
+ bt->key[i].rkey = bt->page + offset;
+ bt->key[i].nkey = NULL;
+ bt->child[i] = 0;
+ }
+
+ /*
+ * The last possible key...
+ */
+ bt->key[2*type->k].dirty = 0;
+ bt->key[2*type->k].rkey = bt->page + offset;
+ bt->key[2*type->k].nkey = NULL;
+
+ /*
+ * Cache the new B-tree node.
+ */
+ H5AC_set (f, H5AC_BT, addr, bt);
+ return addr;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_load
+ *
+ * Purpose: Loads a B-tree node from the disk.
+ *
+ * Return: Success: Pointer to a new B-tree node.
+ *
+ * Failure: 0
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static H5B_t *
+H5B_load (hdf5_file_t *f, off_t addr, const void *_data)
+{
+ const H5B_class_t *type = (const H5B_class_t *)_data;
+ size_t size, total_nkey_size;
+ H5B_t *bt = H5MM_xmalloc (sizeof(H5B_t));
+ intn i;
+ uint8 *p;
+
+ assert (type);
+ assert (type->get_sizeof_rkey);
+
+
+ bt->sizeof_rkey = (type->get_sizeof_rkey)(f);
+ size = H5B_nodesize (f, type, &total_nkey_size, bt->sizeof_rkey);
+ bt->type = type;
+ bt->dirty = 0;
+ bt->ndirty = 0;
+ bt->page = H5MM_xmalloc (size);
+ bt->native = H5MM_xmalloc (total_nkey_size);
+ bt->key = H5MM_xmalloc ((2*type->k+1) * sizeof(H5B_key_t));
+ bt->child = H5MM_xmalloc (2 * type->k * sizeof(off_t));
+ H5F_block_read (f, addr, size, bt->page);
+ p = bt->page;
+
+ /* magic number */
+ if (memcmp (p, H5B_MAGIC, 4)) goto error;
+ p += 4;
+
+ /* node type and level */
+ if (*p++ != type->id) goto error;
+ bt->level = *p++;
+
+ /* entries used */
+ UINT16DECODE (p, bt->nchildren);
+
+ /* sibling pointers */
+ H5F_decode_offset (f, p, bt->left);
+ H5F_decode_offset (f, p, bt->right);
+
+ /* the child/key pairs */
+ for (i=0; i<2*type->k; i++) {
+
+ bt->key[i].dirty = 0;
+ bt->key[i].rkey = p;
+ p += bt->sizeof_rkey;
+ bt->key[i].nkey = NULL;
+
+ if (i<bt->nchildren) {
+ H5F_decode_offset (f, p, bt->child[i]);
+ } else {
+ bt->child[i] = 0;
+ p += SIZEOF_OFFSET(f);
+ }
+ }
+
+ bt->key[2*type->k].dirty = 0;
+ bt->key[2*type->k].rkey = p;
+ bt->key[2*type->k].nkey = NULL;
+ return bt;
+
+error:
+ if (bt) {
+ H5MM_xfree (bt->child);
+ H5MM_xfree (bt->key);
+ H5MM_xfree (bt->page);
+ H5MM_xfree (bt->native);
+ H5MM_xfree (bt);
+ }
+ return NULL;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_flush
+ *
+ * Purpose: Flushes a dirty B-tree node to disk.
+ *
+ * Return: Success: 0
+ *
+ * Failure: -1
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B_flush (hdf5_file_t *f, hbool_t destroy, off_t addr, H5B_t *bt)
+{
+ intn i;
+ size_t size = H5B_nodesize (f, bt->type, NULL, bt->sizeof_rkey);
+ uint8 *p = bt->page;
+
+ assert (bt->type);
+ assert (bt->type->encode);
+
+ if (bt->dirty) {
+
+ /* magic number */
+ memcpy (p, H5B_MAGIC, 4);
+ p += 4;
+
+ /* node type and level */
+ *p++ = bt->type->id;
+ *p++ = bt->level;
+
+ /* entries used */
+ UINT16ENCODE (p, bt->nchildren);
+
+ /* sibling pointers */
+ H5F_encode_offset (f, p, bt->left);
+ H5F_encode_offset (f, p, bt->right);
+
+ /* child keys and pointers */
+ for (i=0; i<=bt->nchildren; i++) {
+
+ /* encode the key */
+ assert (bt->key[i].rkey == p);
+ if (bt->key[i].dirty) {
+ if (bt->key[i].nkey) {
+ (bt->type->encode)(f, bt->key[i].rkey, bt->key[i].nkey);
+ }
+ bt->key[i].dirty = 0;
+ }
+ p += bt->sizeof_rkey;
+
+ /* encode the child address */
+ if (i<bt->ndirty) {
+ H5F_encode_offset (f, p, bt->child[i]);
+ } else {
+ p += SIZEOF_OFFSET(f);
+ }
+ }
+
+ /*
+ * Write the disk page. We always write the header, but we don't
+ * bother writing data for the child entries that don't exist or
+ * for the final unchanged children.
+ */
+ H5F_block_write (f, addr, size, bt->page);
+ bt->dirty = 0;
+ bt->ndirty = 0;
+ }
+
+ if (destroy) {
+ H5MM_xfree (bt->child);
+ H5MM_xfree (bt->key);
+ H5MM_xfree (bt->page);
+ H5MM_xfree (bt->native);
+ H5MM_xfree (bt);
+ }
+ return 0;
+}
+
+
+/*-------------------------------------------------------------------------
+ * 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: Success: 0 if found, values returned through the
+ * RETVAL argument.
+ *
+ * Failure: -1 if not found.
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B_find (hdf5_file_t *f, const H5B_class_t *type, off_t addr, void *udata)
+{
+ H5B_t *bt=NULL;
+ uint8 lt_key[256], rt_key[256];
+ intn idx=-1, lt=0, rt, cmp=1;
+
+ assert (type);
+ assert (type->sizeof_nkey < sizeof lt_key);
+ assert (type->decode);
+ assert (type->cmp);
+ assert (type->found);
+
+ /*
+ * Perform a binary search to locate the child which contains
+ * the thing for which we're searching. The comparison function
+ * may preempt the B-tree node from the cache.
+ */
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ rt = bt->nchildren;
+
+ while (lt<rt && cmp) {
+ idx = (lt + rt) / 2;
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ if (!bt) return -1;
+
+ /* the left key */
+ if (!bt->key[idx].nkey) H5B_decode_key (f, bt, idx);
+ HDmemcpy (lt_key, bt->key[idx].nkey, type->sizeof_nkey);
+
+ /* the right key */
+ if (!bt->key[idx+1].nkey) H5B_decode_key (f, bt, idx+1);
+ HDmemcpy (rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
+
+ /* compare */
+ if ((cmp=(type->cmp)(f, lt_key, udata, rt_key))<0) {
+ rt = idx;
+ } else {
+ lt = idx+1;
+ }
+ }
+ if (cmp) return -1;
+
+ /*
+ * Follow the link to the subtree or to the data node.
+ */
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ assert (idx>=0 && idx<bt->nchildren);
+ if (bt->level > 0) {
+ return H5B_find (f, type, bt->child[idx], udata);
+ }
+
+ return (type->found)(f, bt->child[idx], lt_key, udata, rt_key);
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_split
+ *
+ * Purpose: Split a single node into two nodes. If anchor is
+ * H5B_ANCHOR_LT then the new node gets the right half of
+ * the old node. If anchor is H5B_ANCHOR_RT then the
+ * new node gets the left half of the old node.
+ *
+ * Return: Success: Address of the new node.
+ *
+ * Failure: 0
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jul 3 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static off_t
+H5B_split (hdf5_file_t *f, const H5B_class_t *type, off_t addr, intn anchor)
+{
+ H5B_t *old = H5AC_find (f, H5AC_BT, addr, type);
+ H5B_t *bt = H5MM_xmalloc (sizeof(H5B_t));
+ size_t total_nkey_size, size;
+ intn i, offset;
+ intn delta = H5B_ANCHOR_LT==anchor ? type->k : 0;
+ size_t recsize = old->sizeof_rkey + SIZEOF_OFFSET(f);
+ off_t tmp_addr, new_addr;
+ H5B_t *tmp=NULL;
+
+ /*
+ * Create the new B-tree node.
+ */
+ size = H5B_nodesize (f, type, &total_nkey_size, old->sizeof_rkey);
+ bt->dirty = 1;
+ bt->ndirty = BOUND (0, old->ndirty-delta, type->k);
+ bt->type = type;
+ bt->level = old->level;
+ bt->nchildren = type->k;
+ bt->page = H5MM_xmalloc (size);
+ bt->native = H5MM_xmalloc (total_nkey_size);
+ bt->child = H5MM_xmalloc (2*type->k * sizeof(off_t));
+ bt->key = H5MM_xmalloc ((2*type->k+1) * sizeof(H5B_key_t));
+
+ /*
+ * Copy data into the new node from the old node.
+ */
+ memcpy (bt->page + H5B_HDR_SIZE(f),
+ old->page + H5B_HDR_SIZE(f) + delta*recsize,
+ type->k * recsize);
+ memcpy (bt->native,
+ old->native + delta * type->sizeof_nkey,
+ (type->k+1) * type->sizeof_nkey);
+
+ for (i=0,offset=H5B_HDR_SIZE(f); i<=2*type->k; i++,offset+=recsize) {
+
+ /* key */
+ if (i<=type->k) {
+ bt->key[i].dirty = old->key[delta+i].dirty;
+ bt->key[i].rkey = bt->native + offset;
+ if (old->key[delta+i].nkey) {
+ bt->key[i].nkey = bt->native + i*type->sizeof_nkey;
+ } else {
+ bt->key[i].nkey = NULL;
+ }
+ } else {
+ bt->key[i].dirty = 0;
+ bt->key[i].rkey = bt->native + offset;
+ bt->key[i].nkey = NULL;
+ }
+
+ /* child */
+ if (i<type->k) {
+ bt->child[i] = old->child[delta+i];
+ } else if (i<2*type->k) {
+ bt->child[i] = 0;
+ }
+ }
+
+
+ /*
+ * Truncate the old node.
+ */
+ delta = H5B_ANCHOR_LT ? 0 : type->k;
+ old->dirty += 1;
+ old->ndirty = BOUND (0, old->ndirty-delta, type->k);
+ old->nchildren = type->k;
+
+ if (H5B_ANCHOR_RT==anchor) {
+ memcpy (old->page + H5B_HDR_SIZE(f),
+ old->page + H5B_HDR_SIZE(f) + delta*recsize,
+ type->k * recsize);
+ memmove (old->native,
+ old->native + delta * type->sizeof_nkey,
+ (type->k+1) * type->sizeof_nkey);
+
+ for (i=0; i<=2*type->k; i++) {
+
+ if (i<=type->k) {
+ old->key[i].dirty = old->key[delta+i].dirty;
+ if (old->key[delta+i].nkey) {
+ old->key[i].nkey = old->native + i * type->sizeof_nkey;
+ } else {
+ old->key[i].nkey = NULL;
+ }
+ } else {
+ old->key[i].nkey = NULL;
+ }
+ if (i<type->k) {
+ old->child[i] = old->child[delta+i];
+ } else if (i<2*type->k) {
+ old->child[i] = 0;
+ }
+ }
+ }
+
+ /*
+ * Update sibling pointers of new node.
+ */
+ if (H5B_ANCHOR_LT==anchor) {
+ bt->left = addr;
+ bt->right = old->right;
+ } else {
+ bt->left = old->left;
+ bt->right = addr;
+ }
+
+ /*
+ * Add the new node to the cache.
+ */
+ new_addr = H5MF_alloc (f, size);
+ H5AC_set (f, H5AC_BT, new_addr, bt);
+
+ /*
+ * Update sibling pointers of old nodes.
+ */
+ old = H5AC_find (f, H5AC_BT, addr, type);
+ if (H5B_ANCHOR_LT==anchor) {
+ old->dirty += 1;
+ tmp_addr = old->right;
+ old->right = new_addr;
+ if (tmp_addr) {
+ tmp = H5AC_find (f, H5AC_BT, tmp_addr, type);
+ tmp->dirty += 1;
+ tmp->left = new_addr;
+ }
+ } else {
+ old->dirty += 1;
+ tmp_addr = old->left;
+ old->left = new_addr;
+ if (tmp_addr) {
+ tmp = H5AC_find (f, H5AC_BT, tmp_addr, type);
+ tmp->dirty += 1;
+ tmp->right = new_addr;
+ }
+ }
+
+ return new_addr;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_decode_key
+ *
+ * Purpose: Decode the specified key into native format.
+ *
+ * Return: Success: 0
+ *
+ * Failure: -1
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jul 8 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5B_decode_key (hdf5_file_t *f, H5B_t *bt, intn idx)
+{
+ bt->key[idx].nkey = bt->native + idx * bt->type->sizeof_nkey;
+ (bt->type->decode)(f, bt->key[idx].rkey, bt->key[idx].nkey);
+ return 0;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_insert
+ *
+ * Purpose: Adds a new item to the B-tree. If the root node of
+ * the B-tree splits then the B-tree gets a new address.
+ *
+ * Return: Success: Address of the root of the B-tree. The
+ * B-tree root address may change if the old
+ * root is split.
+ *
+ * Failure: 0
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+off_t
+H5B_insert (hdf5_file_t *f, const H5B_class_t *type, off_t addr, void *udata)
+{
+ uint8 lt_key[256], md_key[256], rt_key[256];
+ intn lt_key_changed=false, rt_key_changed=false;
+ off_t child, new_root;
+ intn level;
+ H5B_t *bt;
+
+ assert (type);
+ assert (type->sizeof_nkey < sizeof lt_key);
+
+ child = H5B_insert_helper (f, addr, type, lt_key, &lt_key_changed,
+ md_key, udata, rt_key, &rt_key_changed);
+ if (child<0) return 0;
+ if (0==child) return addr;
+
+ /* the current root */
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ level = bt->level;
+ if (!lt_key_changed) {
+ if (!bt->key[0].nkey) H5B_decode_key (f, bt, 0);
+ memcpy (lt_key, bt->key[0].nkey, type->sizeof_nkey);
+ }
+
+ /* the new node */
+ bt = H5AC_find (f, H5AC_BT, child, type);
+ if (!rt_key_changed) {
+ if (!bt->key[bt->nchildren].nkey) H5B_decode_key (f, bt, bt->nchildren);
+ memcpy (rt_key, bt->key[bt->nchildren].nkey, type->sizeof_nkey);
+ }
+
+#ifdef H5B_ANCHOR_ROOT
+ {
+ /*
+ * 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".
+ */
+ size_t size = H5B_nodesize (f, type, NULL, bt->sizeof_rkey);
+ uint8 *buf = H5MM_xmalloc (size);
+ off_t tmp_addr = H5MF_alloc (f, size);
+
+ H5AC_flush (f, H5AC_BT, addr, FALSE);
+ H5F_block_read (f, addr, size, buf);
+ H5F_block_write (f, tmp_addr, size, buf);
+ H5AC_rename (f, H5AC_BT, addr, tmp_addr);
+
+ buf = H5MM_xfree (buf);
+ new_root = addr;
+ addr = tmp_addr;
+
+ /* update the new child's left pointer */
+ bt = H5AC_find (f, H5AC_BT, child, type);
+ bt->dirty += 1;
+ bt->left = addr;
+
+ /* clear the old root at the old address */
+ bt = H5AC_find (f, H5AC_BT, new_root, type);
+ bt->dirty += 1;
+ bt->ndirty = 0;
+ bt->left = 0;
+ bt->right = 0;
+ bt->nchildren = 0;
+ }
+#else
+ /*
+ * The new root is created at a new file location.
+ */
+ new_root = H5B_new (f, type, bt->sizeof_rkey);
+#endif
+
+ /* the new root */
+ bt = H5AC_find (f, H5AC_BT, new_root, type);
+ bt->dirty += 1;
+ bt->ndirty = 2;
+ bt->level = level+1;
+ bt->nchildren = 2;
+
+ bt->child[0] = addr;
+ bt->key[0].dirty = 1;
+ bt->key[0].nkey = bt->native;
+ memcpy (bt->key[0].nkey, lt_key, type->sizeof_nkey);
+
+ bt->child[1] = child;
+ bt->key[1].dirty = 1;
+ bt->key[1].nkey = bt->native + type->sizeof_nkey;
+ memcpy (bt->key[1].nkey, md_key, type->sizeof_nkey);
+
+ bt->key[2].dirty = 1;
+ bt->key[2].nkey = bt->native + 2 * type->sizeof_nkey;
+ memcpy (bt->key[2].nkey, rt_key, type->sizeof_nkey);
+
+ return new_root;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_insert_child
+ *
+ * Purpose: Insert a child at the specified address with the
+ * specified left or right key.
+ *
+ * Return: void
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jul 8 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static void
+H5B_insert_child (hdf5_file_t *f, const H5B_class_t *type, off_t addr,
+ intn idx, off_t child, intn anchor, void *md_key)
+{
+ H5B_t *bt;
+ size_t recsize;
+ intn i;
+
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ assert (bt);
+ bt->dirty += 1;
+ recsize = bt->sizeof_rkey + SIZEOF_OFFSET(f);
+
+ if (H5B_ANCHOR_LT==anchor) {
+ /*
+ * The MD_KEY is the left key of the new node.
+ */
+ memmove (bt->page + H5B_HDR_SIZE(f) + (idx+1)*recsize,
+ bt->page + H5B_HDR_SIZE(f) + idx*recsize,
+ (bt->nchildren-idx)*recsize + bt->sizeof_rkey);
+
+ memmove (bt->native + (idx+1) * type->sizeof_nkey,
+ bt->native + idx * type->sizeof_nkey,
+ ((bt->nchildren-idx)+1) * type->sizeof_nkey);
+
+ for (i=bt->nchildren; i>=idx; --i) {
+ bt->key[i+1].dirty = bt->key[i].dirty;
+ }
+ bt->key[idx].dirty = 1;
+ bt->key[idx].nkey = bt->native + idx * type->sizeof_nkey;
+ memcpy (bt->key[idx].nkey, md_key, type->sizeof_nkey);
+
+ } else {
+ /*
+ * The MD_KEY is the right key of the new node.
+ */
+ memmove (bt->page + (H5B_HDR_SIZE(f) +
+ (idx+1)*recsize + bt->sizeof_rkey),
+ bt->page + (H5B_HDR_SIZE(f) +
+ idx*recsize + bt->sizeof_rkey),
+ (bt->nchildren-idx) * recsize);
+
+ memmove (bt->native + idx + 2,
+ bt->native + idx + 1,
+ (bt->nchildren-idx) * type->sizeof_nkey);
+
+ for (i=bt->nchildren; i>idx; --i) {
+ bt->key[i+1].dirty = bt->key[i].dirty;
+ }
+ bt->key[idx+1].dirty = 1;
+ bt->key[idx+1].nkey = bt->native +
+ (idx+1) * type->sizeof_nkey;
+ memcpy (bt->key[idx+1].nkey, md_key, type->sizeof_nkey);
+ }
+
+ memmove (bt->child + idx + 1,
+ bt->child + idx,
+ (bt->nchildren - idx) * sizeof(off_t));
+
+ bt->child[idx] = child;
+ bt->nchildren += 1;
+ bt->ndirty = bt->nchildren;
+}
+
+
+/*-------------------------------------------------------------------------
+ * 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. Similarily 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: Address of the new node if the node
+ * splits. The new node is always to the
+ * right of the previous node.
+ *
+ * 0 if the node didn't split. The MD_KEY
+ * buffer is undefined.
+ *
+ * Failure: -1
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jul 9 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static off_t
+H5B_insert_helper (hdf5_file_t *f, off_t addr, const H5B_class_t *type,
+ uint8 *lt_key, intn *lt_key_changed,
+ uint8 *md_key, void *udata,
+ uint8 *rt_key, intn *rt_key_changed)
+{
+ H5B_t *bt;
+ intn lt=0, idx=-1, rt, cmp=-1;
+ intn anchor;
+ off_t child, twin=0;
+
+ assert (type);
+ assert (type->decode);
+ assert (type->cmp);
+ assert (type->new);
+
+ /*
+ * Use a binary search to find the child that will receive the new
+ * data. The comparison function may preempt the B-tree node from
+ * the cache each time through the loop. When the search completes
+ * IDX points to the child that should get the new data.
+ */
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ if (!bt) goto error;
+ rt = bt->nchildren;
+
+ while (lt<rt && cmp) {
+ idx = (lt + rt) / 2;
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ if (!bt) goto error;
+
+ /* left key */
+ if (!bt->key[idx].nkey) H5B_decode_key (f, bt, idx);
+ memcpy (lt_key, bt->key[idx].nkey, type->sizeof_nkey);
+
+ /* right key */
+ if (!bt->key[idx+1].nkey) H5B_decode_key (f, bt, idx+1);
+ memcpy (rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
+
+ /* compare */
+ if ((cmp=(type->cmp)(f, lt_key, udata, rt_key))<0) {
+ rt = idx;
+ } else {
+ lt = idx+1;
+ }
+ }
+
+ /*
+ * Adjust for boundary conditions. If adjusting at the leaf level
+ * update the left and right key buffers since the data node insert
+ * function needs them as input. Don't worry about it at higher node
+ * levels because this function uses them for output only.
+ */
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ if (cmp<0 && idx<=0) {
+ idx = 0;
+ cmp = 0;
+ if (0==bt->level && bt->nchildren) {
+ if (!bt->key[idx].nkey) H5B_decode_key (f, bt, idx);
+ memcpy (lt_key, bt->key[idx].nkey, type->sizeof_nkey);
+ if (!bt->key[idx+1].nkey) H5B_decode_key (f, bt, idx+1);
+ memcpy (rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
+ }
+ } else if (cmp>0 && idx+1>=bt->nchildren) {
+ idx = bt->nchildren-1;
+ cmp = 0;
+ if (0==bt->level && bt->nchildren) {
+ if (!bt->key[idx].nkey) H5B_decode_key (f, bt, idx);
+ memcpy (lt_key, bt->key[idx].nkey, type->sizeof_nkey);
+ if (!bt->key[idx+1].nkey) H5B_decode_key (f, bt, idx+1);
+ memcpy (rt_key, bt->key[idx+1].nkey, type->sizeof_nkey);
+ }
+ }
+ assert (0==cmp);
+
+ /*
+ * If there are no children, then create a new child. This can only
+ * happen at the root of the B-tree. Creating a new child may
+ * preempt the B-tree node from the cache. The left and right key
+ * buffers are output values.
+ */
+ if (0==bt->nchildren) {
+ child = (type->new)(f, lt_key, udata, rt_key);
+ if (child<=0) goto error;
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ bt->nchildren = 1;
+ bt->dirty += 1;
+ bt->ndirty = 1;
+ bt->child[0] = child;
+
+ bt->key[0].dirty = 1;
+ bt->key[0].nkey = bt->native;
+ memcpy (bt->key[0].nkey, lt_key, type->sizeof_nkey);
+
+ bt->key[1].dirty = 1;
+ bt->key[1].nkey = bt->native + type->sizeof_nkey;
+ memcpy (bt->key[1].nkey, rt_key, type->sizeof_nkey);
+ idx = 0;
+ }
+
+ /*
+ * Insert the new data in the child B-tree node or in the data node.
+ */
+ if (bt->level > 0) {
+ child = H5B_insert_helper (f, bt->child[idx], type,
+ lt_key, lt_key_changed,
+ md_key, udata,
+ rt_key, rt_key_changed);
+ anchor = H5B_ANCHOR_LT;
+ } else {
+ child = (type->insert)(f, bt->child[idx], &anchor,
+ lt_key, lt_key_changed,
+ md_key, udata,
+ rt_key, rt_key_changed);
+ }
+ if (child<0) goto error;
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+
+ /*
+ * Update the left and right keys.
+ */
+ if (*lt_key_changed) {
+ bt->key[idx].nkey = bt->native + idx * type->sizeof_nkey;
+ memcpy (bt->key[idx].nkey, lt_key, type->sizeof_nkey);
+ bt->dirty += 1;
+ bt->key[idx].dirty = 1;
+ if (idx>0) *lt_key_changed = false;
+ }
+ if (*rt_key_changed) {
+ bt->key[idx+1].nkey = bt->native +
+ (idx+1) * type->sizeof_nkey;
+ memcpy (bt->key[idx+1].nkey, rt_key, type->sizeof_nkey);
+ bt->dirty += 1;
+ bt->key[idx+1].dirty = 1;
+ if (idx+1<bt->nchildren) *rt_key_changed = false;
+ }
+
+ /*
+ * If the child split and the left node is anchored, then the new
+ * child node gets inserted to the right of our current position.
+ */
+ if (child && H5B_ANCHOR_LT==anchor) idx++;
+
+ /*
+ * Split this node if the child node split and this node is full.
+ * Make sure `addr' points to the node that gets the new child
+ * and that `idx' is adjusted appropriately.
+ */
+ if (child && bt->nchildren==2*type->k) {
+ twin = H5B_split (f, type, addr, anchor);
+ if (idx<=type->k) {
+ addr = H5B_ANCHOR_LT==anchor ? addr : twin;
+ } else {
+ idx -= type->k;
+ addr = H5B_ANCHOR_LT==anchor ? twin : addr;
+ }
+ }
+
+ /*
+ * If the child split, then insert the new child.
+ */
+ if (child) {
+ H5B_insert_child (f, type, addr, idx, child, anchor, md_key);
+ }
+
+ /*
+ * If this node split, return the mid key (the one that is shared
+ * by the left and right node).
+ */
+ if (twin) {
+ bt = H5AC_find (f, H5AC_BT, twin, type);
+ if (H5B_ANCHOR_LT==anchor) {
+ if (!bt->key[0].nkey) {
+ H5B_decode_key (f, bt, 0);
+ }
+ memcpy (md_key, bt->key[0].nkey, type->sizeof_nkey);
+ } else {
+ if (!bt->key[bt->nchildren].nkey) {
+ H5B_decode_key (f, bt, bt->nchildren);
+ }
+ memcpy (md_key, bt->key[bt->nchildren].nkey, type->sizeof_nkey);
+ }
+ }
+
+ return twin;
+
+error:
+ return -1;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_list
+ *
+ * Purpose: Calls the list callback for each leaf node of the
+ * B-tree, passing it the UDATA structure.
+ *
+ * Return: Success: 0
+ *
+ * Failure: -1
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jun 23 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5B_list (hdf5_file_t *f, const H5B_class_t *type, off_t addr, void *udata)
+{
+ H5B_t *bt;
+ off_t *child=NULL;
+ off_t twin;
+ intn i, nchildren, status;
+ herr_t (*list)(hdf5_file_t*,off_t,void*);
+
+ assert (type);
+ assert (type->list);
+
+ bt = H5AC_find (f, H5AC_BT, addr, type);
+ if (!bt) return -1;
+
+ if (bt->level>0) {
+ return H5B_list (f, type, bt->child[0], udata);
+ } else {
+ child = H5MM_xmalloc (2 * type->k * sizeof(off_t));
+ list = type->list;
+ twin = addr;
+
+ while (twin) { /*for each leaf node*/
+ bt = H5AC_find (f, H5AC_BT, twin, type);
+ if (!bt) {
+ H5MM_xfree (child);
+ return -1;
+ }
+ nchildren = bt->nchildren;
+ twin = bt->right;
+ HDmemcpy (child, bt->child, nchildren * sizeof(off_t));
+ bt = NULL; /*list callback may invalidate the cache*/
+
+ for (i=0; i<nchildren; i++) {
+ status = (list)(f, child[i], udata);
+ if (status<0) {
+ H5MM_xfree (child);
+ return -1;
+ }
+ }
+ }
+ H5MM_xfree (child);
+ }
+ return 0;
+}
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5B_nodesize
+ *
+ * Purpose: Returns the number of bytes needed for this type of
+ * B-tree node. The size is the size of the header plus
+ * enough space for 2t child pointers and 2t+1 keys.
+ *
+ * If TOTAL_NKEY_SIZE is non-null, what it points to will
+ * be initialized with the total number of bytes required to
+ * hold all the key values in native order.
+ *
+ * Return: Success: Size of node in file.
+ *
+ * Failure: never fails.
+ *
+ * Programmer: Robb Matzke
+ * robb@maya.nuance.com
+ * Jul 3 1997
+ *
+ * Modifications:
+ *
+ *-------------------------------------------------------------------------
+ */
+static size_t
+H5B_nodesize (hdf5_file_t *f, const H5B_class_t *type,
+ size_t *total_nkey_size, size_t sizeof_rkey)
+{
+ if (total_nkey_size) {
+ *total_nkey_size = (2 * type->k + 1) * type->sizeof_nkey;
+ }
+
+ return (H5B_HDR_SIZE(f) + /*node header */
+ 2 * type->k * SIZEOF_OFFSET(f) + /*child pointers*/
+ (2*type->k+1) * sizeof_rkey); /*keys */
+}
+