diff options
Diffstat (limited to 'src/H5BP.c')
| -rw-r--r-- | src/H5BP.c | 471 |
1 files changed, 0 insertions, 471 deletions
diff --git a/src/H5BP.c b/src/H5BP.c deleted file mode 100644 index e01ab28..0000000 --- a/src/H5BP.c +++ /dev/null @@ -1,471 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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://hdf.ncsa.uiuc.edu/HDF5/doc/Copyright.html. If you do not have * - * access to either file, you may request a copy from hdfhelp@ncsa.uiuc.edu. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/*------------------------------------------------------------------------- - * - * Created: H5BP.c - * Apr 14 2005 - * Quincey Koziol <koziol@ncsa.uiuc.edu> - * - * Purpose: Implements a B+ tree, with several modifications from - * the "standard" methods. - * - * Please see the documentation in: - * doc/html/TechNotes/Btrees.html for a full description - * of how they work, etc. - * - *------------------------------------------------------------------------- - */ - -#define H5BP_PACKAGE /*suppress error about including H5BPpkg */ - -/* Private headers */ -#include "H5private.h" /* Generic Functions */ -#include "H5BPpkg.h" /* B+ trees */ -#include "H5Eprivate.h" /* Error handling */ -#include "H5MFprivate.h" /* File memory management */ -#include "H5MMprivate.h" /* Memory management */ - -/* Local macros */ - -/* Uncomment this macro to enable extra sanity checking */ -/* #define H5BP_DEBUG */ - - -/* Local typedefs */ - -/* Local prototypes */ - -/* Helper functions */ - - -/* Package variables */ - -/* Declare a free list to manage the H5BP_t struct */ -H5FL_DEFINE(H5BP_t); - -/* Declare a free list to manage the H5BP_branch_t struct */ -H5FL_DEFINE(H5BP_branch_t); - -/* Declare a free list to manage the H5BP_twig_t struct */ -H5FL_DEFINE(H5BP_twig_t); - -/* Declare a free list to manage the H5BP_leaf_t struct */ -H5FL_DEFINE(H5BP_leaf_t); - - -/* Static variables */ - -/* Declare a free list to manage B-tree node pages to/from disk */ -H5FL_BLK_DEFINE_STATIC(node_page); - -/* Declare a free list to manage the H5BP_shared_t struct */ -H5FL_DEFINE_STATIC(H5BP_shared_t); - - - -/*------------------------------------------------------------------------- - * Function: H5BP_shared_init - * - * Purpose: Allocate & initialize shared B-tree info - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 14 2005 - * - *------------------------------------------------------------------------- - */ -herr_t -H5BP_shared_init (H5BP_t *bpt, const H5BP_class_t *type, - size_t node_size, unsigned split_percent, unsigned merge_percent) -{ - H5BP_shared_t *shared = NULL; /* Shared B+ tree information */ - herr_t ret_value=SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT(H5BP_shared_init) - - /* Allocate space for the shared information */ - if(NULL==(shared = H5FL_CALLOC(H5BP_shared_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B+ tree shared information") - - /* Assign user's information */ - shared->split_percent = split_percent; - shared->merge_percent = merge_percent; - shared->node_size = node_size; - - /* Assign common type information */ - shared->type = type; - - /* Allocate "page" for node I/O */ - if((shared->page=H5FL_BLK_MALLOC(node_page,shared->node_size))==NULL) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") -#ifdef H5_USING_PURIFY -HDmemset(shared->page,0,shared->node_size); -#endif /* H5_USING_PURIFY */ - - /* Make shared B-tree info reference counted */ - if(NULL==(bpt->shared=H5RC_create(shared,H5BP_shared_free))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create ref-count wrapper for shared B+ tree info") - -done: - if(ret_value<0) - if(shared) - H5BP_shared_free(shared); - - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5BP_shared_init() */ - - -/*------------------------------------------------------------------------- - * Function: H5BP_shared_free - * - * Purpose: Free shared B+ tree info - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 14 2005 - * - *------------------------------------------------------------------------- - */ -herr_t -H5BP_shared_free (void *_shared) -{ - H5BP_shared_t *shared = (H5BP_shared_t *)_shared; - herr_t ret_value=SUCCEED; - - FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5BP_shared_free) - - /* Sanity check */ - HDassert(shared); - - /* Free the B-tree node buffer */ - if(shared->page) - H5FL_BLK_FREE(node_page,shared->page); - - /* Free the shared B-tree info itself */ - H5FL_FREE(H5BP_shared_t,shared); - - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5BP_shared_free() */ - - -/*------------------------------------------------------------------------- - * Function: H5BP_create - * - * Purpose: Creates a new empty B+ tree in the file. - * - * Return: Non-negative on success (with address of new B-tree - * filled in), negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 19 2005 - * - *------------------------------------------------------------------------- - */ -herr_t -H5BP_create(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, - size_t node_size, unsigned split_percent, unsigned merge_percent, - haddr_t *addr_p) -{ - H5BP_t *bpt = NULL; /* The new B+ tree header information */ - herr_t ret_value=SUCCEED; - - FUNC_ENTER_NOAPI(H5BP_create, FAIL) - - /* - * Check arguments. - */ - HDassert(f); - HDassert(type); - HDassert(node_size>0); - HDassert(merge_percent>0 && merge_percent<=100); - HDassert(split_percent>0 && split_percent<=100); - HDassert(merge_percent<(split_percent/2)); - - /* - * Allocate file and memory data structures. - */ - if (NULL==(bpt = H5FL_MALLOC(H5BP_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B-tree header") - - /* Assign internal information */ - HDmemset(&bpt->cache_info,0,sizeof(H5AC_info_t)); - bpt->cache_info.is_dirty = TRUE; - bpt->depth = 0; - bpt->root.addr = HADDR_UNDEF; - bpt->root.all_nrec = 0; - bpt->root.util = 0; - - /* Initialize shared B-tree info */ - if(H5BP_shared_init(bpt, type, node_size, split_percent, merge_percent)<0) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create shared B+ tree info") - - /* Allocate space for the header on disk */ - if (HADDR_UNDEF==(*addr_p=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)H5BP_HEADER_SIZE(f)))) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B-tree header") - - /* Cache the new B-tree node */ - if (H5AC_set(f, dxpl_id, H5AC_BPT_HDR, *addr_p, bpt, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B+ tree header to cache") - -done: - if (ret_value<0) { - if (bpt) - (void)H5BP_cache_hdr_dest(f,bpt); - } /* end if */ - - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5BP_create() */ - - -/*------------------------------------------------------------------------- - * Function: H5BP_create_leaf - * - * Purpose: Creates empty leaf node of a B+ tree and updates node pointer - * to point to it. - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 19 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5BP_create_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared, H5BP_node_ptr_t *node_ptr) -{ - H5BP_leaf_t *leaf=NULL; /* Pointer to new leaf node created */ - H5BP_shared_t *shared; /* Shared B+ tree information */ - herr_t ret_value = SUCCEED; - - FUNC_ENTER_NOAPI(H5BP_create_leaf, FAIL) - - /* Check arguments. */ - HDassert(f); - HDassert(bpt_shared); - HDassert(node_ptr); - - /* Allocate memory for leaf information */ - if (NULL==(leaf = H5FL_MALLOC(H5BP_leaf_t))) - HGOTO_ERROR (H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for B+ tree leaf info") - - /* Set metadata cache info */ - HDmemset(&leaf->cache_info,0,sizeof(H5AC_info_t)); - leaf->cache_info.is_dirty = TRUE; - - /* Share common B+ tree information */ - leaf->shared = bpt_shared; - H5RC_INC(leaf->shared); - - /* Get the pointer to the shared B-tree info */ - shared=H5RC_GET_OBJ(leaf->shared); - HDassert(shared); - - /* Create record pool for leaf node */ - if((leaf->rec_pool = H5MP_create(H5BP_LEAF_POOL_PAGE, H5MP_FLG_DEFAULT)) == NULL) - HGOTO_ERROR(H5E_BTREE, H5E_NOSPACE, FAIL, "can't allocate memory pool") - - /* Set number of records */ - leaf->nrec=0; - leaf->flags=0; - - /* Allocate space on disk for the leaf */ - if (HADDR_UNDEF==(node_ptr->addr=H5MF_alloc(f, H5FD_MEM_BTREE, dxpl_id, (hsize_t)shared->node_size))) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "file allocation failed for B+ tree leaf node") - - /* Cache the new B+ tree node */ - if (H5AC_set(f, dxpl_id, H5AC_BPT_LEAF, node_ptr->addr, leaf, H5AC__NO_FLAGS_SET) < 0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "can't add B+ tree leaf to cache") - -done: - if (ret_value<0) { - if (leaf) - (void)H5BP_cache_leaf_dest(f,leaf); - } /* end if */ - - FUNC_LEAVE_NOAPI(ret_value) -} /* H5BP_create_leaf() */ - - -/*------------------------------------------------------------------------- - * Function: H5BP_insert_leaf - * - * Purpose: Adds a new record to a B+ tree leaf node. - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 22 2005 - * - *------------------------------------------------------------------------- - */ -static herr_t -H5BP_insert_leaf(H5F_t *f, hid_t dxpl_id, H5RC_t *bpt_shared, - H5BP_node_ptr_t *curr_node_ptr, void *udata) -{ - H5BP_leaf_t *leaf; /* Pointer to leaf node */ - H5BP_shared_t *shared; /* Pointer to B+ tree's shared information */ -#ifdef LATER - int cmp; /* Comparison value of records */ - unsigned idx; /* Location of record which matches key */ -#endif /* LATER */ - herr_t ret_value = SUCCEED; - - FUNC_ENTER_NOAPI_NOINIT(H5BP_insert_leaf) - - /* Check arguments. */ - HDassert(f); - HDassert(bpt_shared); - HDassert(curr_node_ptr); - HDassert(H5F_addr_defined(curr_node_ptr->addr)); - -if( H5BP_NODE_OVERSIZE(curr_node_ptr->util)) { - HDfprintf(stderr,"%s: attempting to insert record into extent node\n",FUNC); - HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle extent node!") -} - /* Lock B+ tree node */ - if (NULL == (leaf = H5AC_protect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, &(curr_node_ptr->util), bpt_shared, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree leaf node") - - /* Get the pointer to the shared B+ tree info */ - shared=H5RC_GET_OBJ(bpt_shared); - HDassert(shared); - -#ifndef LATER -HDfprintf(stderr,"%s: finish record insertion code\n",FUNC); -HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't handle record insertion!") -#else /* LATER */ - /* Check for inserting into empty leaf */ - if(leaf->nrec==0) - idx=0; - else { - /* Find correct location to insert this record */ - if((cmp = H5BP_locate_record(shared->type,leaf->nrec,shared->nat_off,leaf->leaf_native,udata,&idx)) == 0) - HGOTO_ERROR(H5E_BTREE, H5E_EXISTS, FAIL, "record is already in B+ tree") - if(cmp > 0) - idx++; - - /* Make room for new record */ - if(idx<leaf->nrec) - HDmemmove(H5BP_LEAF_NREC(leaf,shared,idx+1),H5BP_LEAF_NREC(leaf,shared,idx),shared->type->nrec_size*(leaf->nrec-idx)); - } /* end else */ - - /* Make callback to store record in native form */ - if((shared->type->store)(H5BP_LEAF_NREC(leaf,shared,idx),udata)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into leaf node") -#endif /* LATER */ - - /* Update record count for node pointer to current node */ - curr_node_ptr->all_nrec++; - - /* Update record count for current node */ - leaf->nrec++; - -done: - /* Release the B+ tree leaf node */ - if (leaf && H5AC_unprotect(f, dxpl_id, H5AC_BPT_LEAF, curr_node_ptr->addr, leaf, H5AC__DIRTIED_FLAG) < 0) - HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release leaf B+ tree node") - - FUNC_LEAVE_NOAPI(ret_value) -} /* H5BP_insert_leaf() */ - - -/*------------------------------------------------------------------------- - * Function: H5BP_insert - * - * Purpose: Adds a new record to the B+ tree. - * - * Return: Non-negative on success/Negative on failure - * - * Programmer: Quincey Koziol - * koziol@ncsa.uiuc.edu - * Apr 19 2005 - * - *------------------------------------------------------------------------- - */ -herr_t -H5BP_insert(H5F_t *f, hid_t dxpl_id, const H5BP_class_t *type, haddr_t addr, - void *udata) -{ - H5BP_t *bpt=NULL; /* Pointer to the B+ tree header */ - H5BP_shared_t *shared; /* Pointer to B+ tree's shared information */ - herr_t ret_value = SUCCEED; - - FUNC_ENTER_NOAPI(H5BP_insert, FAIL) - - /* Check arguments. */ - HDassert(f); - HDassert(type); - HDassert(H5F_addr_defined(addr)); - - /* Look up the B+ tree header */ - if (NULL == (bpt = H5AC_protect(f, dxpl_id, H5AC_BPT_HDR, addr, type, NULL, H5AC_WRITE))) - HGOTO_ERROR(H5E_BTREE, H5E_CANTPROTECT, FAIL, "unable to load B+ tree header") - - /* Get the pointer to the shared B+ tree info */ - shared=H5RC_GET_OBJ(bpt->shared); - HDassert(shared); - - /* Check if the root node is allocated yet */ - if(!H5F_addr_defined(bpt->root.addr)) { - /* Create root node as leaf node in B+ tree */ - if(H5BP_create_leaf(f, dxpl_id, bpt->shared, &(bpt->root))<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINIT, FAIL, "unable to create root node") - - /* Mark B+ tree header as dirty, since we updated the address of the root node */ - bpt->cache_info.is_dirty = TRUE; - } /* end if */ - /* Check if we need to split the root node (equiv. to a 1->2 leaf node split) */ - else if(H5BP_NODE_OVERSIZE(bpt->root.util) || - (!H5BP_NODE_OVERSIZE(bpt->root.util) && bpt->root.util>=shared->split_percent)) { - /* Split root node */ -#ifdef LATER - if(H5BP_split_root(f, dxpl_id, bpt, bpt->shared)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTSPLIT, FAIL, "unable to split root node") -#else /* LATER */ -HDfprintf(stderr,"%s: attempting to split root node\n",FUNC); -HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't split root yet!") -#endif /* LATER */ - } /* end if */ - - /* Attempt to insert record into B+ tree */ - if(bpt->depth>0) { -#ifdef LATER - if(H5BP_insert_internal(f,dxpl_id,bpt->shared,bpt->depth,&(bpt->cache_info),&bpt->root,udata)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree internal node") -#else /* LATER */ -HDfprintf(stderr,"%s: attempting to insert record with internal node\n",FUNC); -HGOTO_ERROR(H5E_BTREE, H5E_UNSUPPORTED, FAIL, "Can't insert records yet!") -#endif /* LATER */ - } /* end if */ - else { - if(H5BP_insert_leaf(f,dxpl_id,bpt->shared,&bpt->root,udata)<0) - HGOTO_ERROR(H5E_BTREE, H5E_CANTINSERT, FAIL, "unable to insert record into B+ tree leaf node") - } /* end else */ - -done: - /* Release the B+ tree header info */ - if (bpt && H5AC_unprotect(f, dxpl_id, H5AC_BPT_HDR, addr, bpt, H5AC__DIRTIED_FLAG) < 0) - HDONE_ERROR(H5E_BTREE, H5E_CANTUNPROTECT, FAIL, "unable to release B+ tree header info") - - FUNC_LEAVE_NOAPI(ret_value) -} /* H5BP_insert() */ - |