summaryrefslogtreecommitdiffstats
path: root/src/H5HFflist.c
diff options
context:
space:
mode:
authorQuincey Koziol <koziol@hdfgroup.org>2006-03-13 19:47:16 (GMT)
committerQuincey Koziol <koziol@hdfgroup.org>2006-03-13 19:47:16 (GMT)
commitee3fdc2dbcdf9daaf4e41c085fddd37c1eadbcf9 (patch)
tree7cbd8c5fc545197f4efed76b9c317c817ebf791f /src/H5HFflist.c
parentc619cf0f518bfea91a34136a1424951eb17b99a4 (diff)
downloadhdf5-ee3fdc2dbcdf9daaf4e41c085fddd37c1eadbcf9.zip
hdf5-ee3fdc2dbcdf9daaf4e41c085fddd37c1eadbcf9.tar.gz
hdf5-ee3fdc2dbcdf9daaf4e41c085fddd37c1eadbcf9.tar.bz2
[svn-r12084] Purpose:
Code checkpoint Description: The fractal heap code is reasonably stable and is passing all its current tests, so checkpoint everything with CVS. Also, add "statistics" module for v2 B-trees code, which is only a stub right now. Platforms tested: FreeBSD 4.11 (sleipnir) Mac OSX (amazon) Linux 2.4 (chicago)
Diffstat (limited to 'src/H5HFflist.c')
-rw-r--r--src/H5HFflist.c367
1 files changed, 367 insertions, 0 deletions
diff --git a/src/H5HFflist.c b/src/H5HFflist.c
new file mode 100644
index 0000000..361bb37
--- /dev/null
+++ b/src/H5HFflist.c
@@ -0,0 +1,367 @@
+/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
+ * 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. *
+ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
+
+/* Programmer: Quincey Koziol <koziol@ncsa.uiuc.edu>
+ * Tuesday, March 7, 2006
+ *
+ * Purpose: Fractal heap free space functions.
+ *
+ */
+
+/****************/
+/* Module Setup */
+/****************/
+
+#define H5HF_PACKAGE /*suppress error about including H5HFpkg */
+
+/***********/
+/* Headers */
+/***********/
+#include "H5private.h" /* Generic Functions */
+#include "H5Eprivate.h" /* Error handling */
+#include "H5HFpkg.h" /* Fractal heaps */
+#include "H5Vprivate.h" /* Vectors and arrays */
+
+/****************/
+/* Local Macros */
+/****************/
+
+/* Max. height of the skip list holding free list nodes */
+#define H5HF_FLIST_DEFAULT_SKIPLIST_HEIGHT 16
+
+/******************/
+/* Local Typedefs */
+/******************/
+
+/* Free list node for free list sections of the same size */
+typedef struct H5HF_flist_node_t {
+ size_t sec_size; /* Size of all sections on list */
+ H5SL_t *sec_list; /* Skip list to hold pointers to actual free list section node */
+} H5HF_flist_node_t;
+
+
+/********************/
+/* Package Typedefs */
+/********************/
+
+/* Main free list info */
+struct H5HF_freelist_t {
+ hsize_t tot_space; /* Total amount of space in free list */
+ unsigned nbins; /* Number of bins */
+ H5SL_operator_t node_free_op; /* Callback for freeing nodes when free list is destroyed */
+ H5SL_t **bins; /* Pointer to array of lists of free nodes */
+};
+
+
+/********************/
+/* Local Prototypes */
+/********************/
+static herr_t H5HF_flist_node_free_cb(void *item, void *key, void *op_data);
+
+
+/*********************/
+/* Package Variables */
+/*********************/
+
+/* Declare a free list to manage the H5HF_freelist_t struct */
+H5FL_DEFINE_STATIC(H5HF_freelist_t);
+
+/* Declare a free list to manage the H5HF_flist_node_t struct */
+H5FL_DEFINE_STATIC(H5HF_flist_node_t);
+
+/* Declare a free list to manage the 'H5SL_t *' sequence information */
+typedef H5SL_t *H5SL_ptr_t;
+H5FL_SEQ_DEFINE_STATIC(H5SL_ptr_t);
+
+
+/*****************************/
+/* Library Private Variables */
+/*****************************/
+
+
+/*******************/
+/* Local Variables */
+/*******************/
+
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5HF_flist_create
+ *
+ * Purpose: Allocate & initialize free list for heap
+ *
+ * Return: Success: Pointer to free list structure
+ *
+ * Failure: NULL
+ *
+ * Programmer: Quincey Koziol
+ * Tuesday, March 7, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+H5HF_freelist_t *
+H5HF_flist_create(size_t max_block_size, H5SL_operator_t node_free_op)
+{
+ H5HF_freelist_t *flist; /* New free list structure */
+ H5HF_freelist_t *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5HF_flist_create)
+
+ /* Check arguments. */
+
+ /*
+ * Allocate top free list structure
+ */
+ if(NULL == (flist = H5FL_MALLOC(H5HF_freelist_t)))
+ HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for fractal heap free list")
+
+ /* Set free list parameters */
+ flist->tot_space = 0;
+ flist->nbins = H5V_log2_of2(max_block_size);
+ flist->node_free_op = node_free_op;
+
+ /* Allocate the bins for free space sizes */
+ if(NULL == (flist->bins = H5FL_SEQ_CALLOC(H5SL_ptr_t, flist->nbins)))
+ HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed for free list bins")
+
+ /* Set return value */
+ ret_value = flist;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5HF_flist_create() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5HF_flist_add
+ *
+ * Purpose: Add a section of free space in a direct block to the free list
+ *
+ * Return: Success: non-negative
+ *
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Tuesday, March 7, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5HF_flist_add(H5HF_freelist_t *flist, void *node, size_t *size_key, haddr_t *addr_key)
+{
+ H5HF_flist_node_t *flist_node = NULL; /* Pointer to free list node of the correct size */
+ unsigned bin; /* Bin to put the free space section in */
+ herr_t ret_value = SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5HF_flist_add)
+#ifdef QAK
+HDfprintf(stderr, "%s: *size_key = %Zu, *addr_key = %a\n", FUNC, *size_key, *addr_key);
+#endif /* QAK */
+
+ /* Check arguments. */
+ HDassert(flist);
+ HDassert(node);
+ HDassert(size_key);
+ HDassert(addr_key);
+
+ /* Determine correct bin which holds items of the section's size */
+ bin = H5V_log2_gen((hsize_t)*size_key);
+ if(flist->bins[bin] == NULL) {
+ if(NULL == (flist->bins[bin] = H5SL_create(H5SL_TYPE_SIZE, 0.5, H5HF_FLIST_DEFAULT_SKIPLIST_HEIGHT)))
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTCREATE, FAIL, "can't create skip list for free list nodes")
+ } /* end if */
+ else {
+ /* Check for node list of the correct size already */
+ flist_node = H5SL_search(flist->bins[bin], size_key);
+ } /* end else */
+
+ /* Check if we need to create a new skip list for nodes of this size */
+ if(flist_node == NULL) {
+ /* Allocate new free list size node */
+ if(NULL == (flist_node = H5FL_MALLOC(H5HF_flist_node_t)))
+ HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed for fractal heap free list")
+
+ /* Initialize the free list size node */
+ flist_node->sec_size = *size_key;
+ if(NULL == (flist_node->sec_list = H5SL_create(H5SL_TYPE_HADDR, 0.5, H5HF_FLIST_DEFAULT_SKIPLIST_HEIGHT)))
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTCREATE, FAIL, "can't create skip list for free list nodes")
+
+ /* Insert new free list size node into bin's list */
+ if(H5SL_insert(flist->bins[bin], flist_node, &flist_node->sec_size) < 0)
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTINSERT, FAIL, "can't insert free list node into skip list")
+ } /* end if */
+
+ /* Insert free list node into correct skip list */
+ if(H5SL_insert(flist_node->sec_list, node, addr_key) < 0)
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTINSERT, FAIL, "can't insert free list node into skip list")
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5HF_flist_add() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5HF_flist_find
+ *
+ * Purpose: Locate a section of free space (in existing free list) that
+ * is large enough to fulfill request.
+ *
+ * Return: Success: non-negative
+ *
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Tuesday, March 7, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+htri_t
+H5HF_flist_find(H5HF_freelist_t *flist, size_t request, void **node)
+{
+ H5HF_flist_node_t *flist_node; /* Free list size node */
+ unsigned bin; /* Bin to put the free space section in */
+ herr_t ret_value = FALSE; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5HF_flist_find)
+
+ /* Check arguments. */
+ HDassert(flist);
+ HDassert(request > 0);
+ HDassert(node);
+
+ /* Determine correct bin which holds items of at least the section's size */
+ bin = H5V_log2_gen((hsize_t)request);
+ while(bin < flist->nbins && flist->bins[bin] == NULL)
+ bin++;
+
+ /* Find the first free space section that is large enough to fulfill request */
+ /* (Since the bins use skip lists to track the sizes of the address-ordered
+ * lists, this is actually a "best fit" algorithm)
+ */
+#ifdef QAK
+HDfprintf(stderr, "%s: flist->nbins = %u\n", FUNC, flist->nbins);
+HDfprintf(stderr, "%s: bin = %u\n", FUNC, bin);
+#endif /* QAK */
+ if(bin < flist->nbins)
+ do {
+ /* Look for large enough free list section in this bin */
+ if(flist->bins[bin])
+ /* Check for large enough list of sections on list */
+ if((flist_node = H5SL_greater(flist->bins[bin], &request))) {
+ /* Take first node off of the list (ie. node w/lowest address) */
+ if(NULL == (*node = H5SL_remove_first(flist_node->sec_list)))
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "can't remove free list node from skip list")
+
+ /* Check for no more nodes on list of that size */
+ if(H5SL_count(flist_node->sec_list) == 0) {
+ H5HF_flist_node_t *tmp_flist_node; /* Free list size node */
+
+ /* Remove size tracking list from bin */
+ tmp_flist_node = H5SL_remove(flist->bins[bin], &flist_node->sec_size);
+ if(tmp_flist_node == NULL || tmp_flist_node != flist_node)
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTDELETE, FAIL, "can't remove free list node from skip list")
+
+ /* Destroy skip list for size tracking node */
+ if(H5SL_close(flist_node->sec_list) < 0)
+ HGOTO_ERROR(H5E_HEAP, H5E_CANTCLOSEOBJ, FAIL, "can't destroy size tracking node's skip list")
+
+ /* Release free list node */
+ H5FL_FREE(H5HF_flist_node_t, flist_node);
+ } /* end if */
+
+ HGOTO_DONE(TRUE)
+ } /* end if */
+
+ /* Advance to next larger bin */
+ bin++;
+ } while(bin < flist->nbins);
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value)
+} /* H5HF_flist_find() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5HF_flist_node_free_cb
+ *
+ * Purpose: Free a size-tracking node for a bin
+ *
+ * Return: Success: non-negative
+ *
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Saturday, March 11, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+static herr_t
+H5HF_flist_node_free_cb(void *item, void UNUSED *key, void *op_data)
+{
+ H5HF_flist_node_t *flist_node = (H5HF_flist_node_t *)item; /* Temporary pointer to free list node */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5HF_flist_node_free_cb)
+
+ HDassert(flist_node);
+
+ /* Release the skip list for sections of this size */
+ H5SL_destroy(flist_node->sec_list, (H5SL_operator_t)op_data, NULL);
+
+ /* Release free list node */
+ H5FL_FREE(H5HF_flist_node_t, flist_node);
+
+ FUNC_LEAVE_NOAPI(0)
+} /* H5HF_flist_node_free_cb() */
+
+
+/*-------------------------------------------------------------------------
+ * Function: H5HF_flist_free
+ *
+ * Purpose: Destroy & deallocate free list structure
+ *
+ * Return: Success: non-negative
+ *
+ * Failure: negative
+ *
+ * Programmer: Quincey Koziol
+ * Tuesday, March 7, 2006
+ *
+ *-------------------------------------------------------------------------
+ */
+herr_t
+H5HF_flist_free(H5HF_freelist_t *flist)
+{
+ unsigned u; /* Local index variable */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5HF_flist_free)
+
+ /* Check arguments. */
+ HDassert(flist);
+
+ /* Clear out lists of nodes */
+ for(u = 0; u < flist->nbins; u++)
+ if(flist->bins[u]) {
+ H5SL_destroy(flist->bins[u], H5HF_flist_node_free_cb, (void *)flist->node_free_op);
+ flist->bins[u] = NULL;
+ } /* end if */
+
+ /* Release bins for skip lists */
+ H5FL_SEQ_FREE(H5SL_ptr_t, flist->bins);
+
+ /* Free fractal heap free list info */
+ H5FL_FREE(H5HF_freelist_t, flist);
+
+ FUNC_LEAVE_NOAPI(SUCCEED)
+} /* H5HF_flist_free() */
+