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