[svn-r2] Oops...

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		*/
+}
+