From 16eda679e306fde7fec41f5ff1910be86645e745 Mon Sep 17 00:00:00 2001 From: Dana Robinson Date: Mon, 3 May 2021 16:23:33 -0700 Subject: Removes dead H5ST code --- MANIFEST | 3 - src/CMakeLists.txt | 12 +- src/H5ST.c | 779 ---------------------------------------------------- src/H5STprivate.h | 63 ----- src/Makefile.am | 1 - test/CMakeLists.txt | 1 - test/Makefile.am | 2 +- test/testhdf5.c | 1 - test/testhdf5.h | 1 - test/ttst.c | 391 -------------------------- 10 files changed, 2 insertions(+), 1252 deletions(-) delete mode 100644 src/H5ST.c delete mode 100644 src/H5STprivate.h delete mode 100644 test/ttst.c diff --git a/MANIFEST b/MANIFEST index 6071746..bb3a15a 100644 --- a/MANIFEST +++ b/MANIFEST @@ -1049,8 +1049,6 @@ ./src/H5SMpkg.h ./src/H5SMprivate.h ./src/H5SMtest.c -./src/H5ST.c -./src/H5STprivate.h ./src/H5T.c ./src/H5Tarray.c ./src/H5Tbit.c @@ -1362,7 +1360,6 @@ ./test/tskiplist.c ./test/tsohm.c ./test/ttime.c -./test/ttst.c ./test/ttsafe.c ./test/ttsafe.h ./test/ttsafe_acreate.c diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index adfb755..5dee0f3 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -606,14 +606,6 @@ set (H5SM_HDRS IDE_GENERATED_PROPERTIES ("H5SM" "${H5SM_HDRS}" "${H5SM_SOURCES}" ) -set (H5ST_SOURCES - ${HDF5_SRC_DIR}/H5ST.c -) -set (H5ST_HDRS -) -IDE_GENERATED_PROPERTIES ("H5ST" "${H5ST_HDRS}" "${H5ST_SOURCES}" ) - - set (H5T_SOURCES ${HDF5_SRC_DIR}/H5T.c ${HDF5_SRC_DIR}/H5Tarray.c @@ -807,7 +799,6 @@ set (common_SRCS ${H5S_SOURCES} ${H5SL_SOURCES} ${H5SM_SOURCES} - ${H5ST_SOURCES} ${H5T_SOURCES} ${H5TS_SOURCES} ${H5VL_SOURCES} @@ -932,6 +923,7 @@ set (H5_PRIVATE_HEADERS ${HDF5_SRC_DIR}/H5Mpkg.h ${HDF5_SRC_DIR}/H5Mprivate.h + ${HDF5_SRC_DIR}/H5MFpkg.h ${HDF5_SRC_DIR}/H5MFprivate.h ${HDF5_SRC_DIR}/H5MMprivate.h @@ -968,8 +960,6 @@ set (H5_PRIVATE_HEADERS ${HDF5_SRC_DIR}/H5SMpkg.h ${HDF5_SRC_DIR}/H5SMprivate.h - ${HDF5_SRC_DIR}/H5STprivate.h - ${HDF5_SRC_DIR}/H5Tpkg.h ${HDF5_SRC_DIR}/H5Tprivate.h diff --git a/src/H5ST.c b/src/H5ST.c deleted file mode 100644 index 53829b2..0000000 --- a/src/H5ST.c +++ /dev/null @@ -1,779 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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://www.hdfgroup.org/licenses. * - * If you do not have access to either file, you may request a copy from * - * help@hdfgroup.org. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/* TERNARY SEARCH TREE ALGS - This code is described in "Ternary Search Trees" by Jon -Bentley and Robert Sedgewick in the April, 1998, Dr. Dobb's Journal. -*/ - -#include "H5Eprivate.h" /* Error handling */ -#include "H5FLprivate.h" /* Free lists */ -#include "H5STprivate.h" /* Ternary search trees */ - -#ifdef H5ST_DEBUG -static herr_t H5ST__dump_internal(H5ST_ptr_t p); -#endif /* H5ST_DEBUG */ - -/* Declare a free list to manage the H5ST_node_t struct */ -H5FL_DEFINE_STATIC(H5ST_node_t); - -/* Declare a free list to manage the H5ST_tree_t struct */ -H5FL_DEFINE_STATIC(H5ST_tree_t); - -/*-------------------------------------------------------------------------- - NAME - H5ST_create - PURPOSE - Create a TST - USAGE - H5ST_ptr_t H5ST_create() - - RETURNS - Returns a pointer to the new TST tree on success, NULL on failure. - DESCRIPTION - Create a TST. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -H5ST_tree_t * -H5ST_create(void) -{ - H5ST_tree_t *ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - /* Allocate wrapper for TST */ - if (NULL == (ret_value = H5FL_MALLOC(H5ST_tree_t))) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") - - /* Set the internal fields */ - ret_value->root = NULL; - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_create() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_close_internal - PURPOSE - Close a TST, deallocating it. - USAGE - herr_t H5ST_close(p) - H5ST_ptr_t p; IN/OUT: Root of TST to free - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Close a TST, freeing all nodes. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5ST_close_internal(H5ST_ptr_t p) -{ - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Recursively free TST */ - if (p) { - H5ST_close_internal(p->lokid); - if (p->splitchar) - H5ST_close_internal(p->eqkid); - H5ST_close_internal(p->hikid); - p = H5FL_FREE(H5ST_node_t, p); - } /* end if */ - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5ST_close_internal() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_close - PURPOSE - Close a TST, deallocating it. - USAGE - herr_t H5ST_close(tree) - H5ST_tree_t *tree; IN/OUT: TST tree to free - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Close a TST, freeing all nodes. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5ST_close(H5ST_tree_t *tree) -{ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Check arguments */ - if (NULL == tree) - HGOTO_ERROR(H5E_ARGS, H5E_BADVALUE, FAIL, "invalid TST") - - /* Free the TST itself */ - if (H5ST_close_internal(tree->root) < 0) - HGOTO_ERROR(H5E_TST, H5E_CANTFREE, FAIL, "can't free TST") - - /* Free root node itself */ - tree = H5FL_FREE(H5ST_tree_t, tree); - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_close() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_insert - PURPOSE - Insert a string/object pair into a TST - USAGE - herr_t H5ST_insert(tree,s,obj) - H5ST_tree_t *tree; IN/OUT: TST to insert string into - const char *s; IN: String to use as key for object - void *obj; IN: Pointer to object to insert - - RETURNS - Returns non-negative on success, negative on failure. - DESCRIPTION - Insert a key (string)/object pair into a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5ST_insert(H5ST_tree_t *tree, const char *s, void *obj) -{ - int d; /* Comparison value */ - H5ST_ptr_t pp, *p; /* Pointer to current node and pointer to that */ - H5ST_ptr_t parent = NULL; /* Pointer to parent node */ - H5ST_ptr_t up = NULL; /* Pointer to up node */ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - /* Find the correct location to insert object */ - p = &tree->root; - while ((pp = *p)) { - /* If this node matches the character in the key, then drop down to the lower tree */ - if (0 == (d = *s - pp->splitchar)) { - if (*s++ == 0) - HGOTO_ERROR(H5E_TST, H5E_EXISTS, FAIL, "key already in tree") - up = pp; - p = &(pp->eqkid); - } /* end if */ - else { - /* Walk through the current tree, searching for the matching character */ - parent = pp; - if (d < 0) - p = &(pp->lokid); - else - p = &(pp->hikid); - } /* end else */ - } /* end while */ - - /* Finish walking through the key string, adding nodes until the end */ - for (;;) { - if (NULL == (*p = H5FL_MALLOC(H5ST_node_t))) - HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") - pp = *p; - pp->splitchar = *s; - pp->up = up; - pp->parent = parent; - pp->lokid = pp->eqkid = pp->hikid = NULL; - - /* If this is the end of the key string, break out */ - if (*s++ == 0) { - pp->eqkid = (H5ST_ptr_t)obj; - break; - } /* end if */ - - /* Continue to next character */ - parent = NULL; - up = pp; - p = &(pp->eqkid); - } /* end for */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_insert() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_search - PURPOSE - Determine if a key is in the TST - USAGE - hbool_t H5ST_search(tree,s) - H5ST_tree_t *tree; IN: TST to find string in - const char *s; IN: String to use as key to locate - - RETURNS - Success: TRUE if key string in TST, FALSE if not - Failure: negative - DESCRIPTION - Locate a key (string) in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -htri_t -H5ST_search(H5ST_tree_t *tree, const char *s) -{ - H5ST_ptr_t p; /* Temporary pointer to TST node */ - htri_t ret_value = FALSE; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - p = tree->root; - while (p) { - if (*s < p->splitchar) - p = p->lokid; - else if (*s == p->splitchar) { - if (*s++ == 0) - HGOTO_DONE(TRUE); - p = p->eqkid; - } - else - p = p->hikid; - } /* end while */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_search() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_find_internal - PURPOSE - Find the node matching a particular key string - USAGE - H5ST_ptr_t H5ST_find(p,s) - H5ST_ptr_t p; IN: TST to find string in - const char *s; IN: String to use as key to locate - - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Locate a key (string) in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static H5ST_ptr_t -H5ST_find_internal(H5ST_ptr_t p, const char *s) -{ - H5ST_ptr_t ret_value = NULL; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - while (p) { - if (*s < p->splitchar) - p = p->lokid; - else if (*s == p->splitchar) { - if (*s++ == 0) - HGOTO_DONE(p); - p = p->eqkid; - } - else - p = p->hikid; - } /* end while */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_find_internal() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_find - PURPOSE - Find the node matching a particular key string - USAGE - H5ST_ptr_t H5ST_find(tree,s) - H5ST_tree_t *tree; IN: TST to find string in - const char *s; IN: String to use as key to locate - - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Locate a key (string) in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -H5ST_ptr_t -H5ST_find(H5ST_tree_t *tree, const char *s) -{ - H5ST_ptr_t ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - if (NULL == (ret_value = H5ST_find_internal(tree->root, s))) - HGOTO_ERROR(H5E_TST, H5E_NOTFOUND, NULL, "key not found in TST") - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_find() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_locate - PURPOSE - Find an object in a TST - USAGE - void *H5ST_locate(tree,s) - H5ST_tree_t *tree; IN: TST to locate object within - const char *s; IN: String of key for object to locate - RETURNS - Success: Non-NULL, pointer to object stored for key - Failure: Negative - DESCRIPTION - Locate a node in a TST, returning the object from the node. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -void * -H5ST_locate(H5ST_tree_t *tree, const char *s) -{ - H5ST_ptr_t node; /* Pointer to node located */ - void * ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - /* Locate the node to remove */ - if (NULL == (node = H5ST_find_internal(tree->root, s))) - HGOTO_ERROR(H5E_TST, H5E_NOTFOUND, NULL, "key not found in TST") - - /* Get the pointer to the object to return */ - ret_value = node->eqkid; - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* H5ST_locate() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_findfirst_internal - PURPOSE - Find the first node in a TST - USAGE - H5ST_ptr_t H5ST_findfirst_internal(p) - H5ST_ptr_t p; IN: TST to locate first node within - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Get the first (lexicographically) node in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static H5ST_ptr_t -H5ST_findfirst_internal(H5ST_ptr_t p) -{ - H5ST_ptr_t ret_value = NULL; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - while (p) { - /* Find least node in current tree */ - while (p->lokid) - p = p->lokid; - - /* Is least node '\0'? */ - if (p->splitchar == '\0') { - /* Return it */ - HGOTO_DONE(p); - } /* end if */ - else { - /* Go down to next level of tree */ - p = p->eqkid; - } /* end else */ - } /* end while */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_findfirst_internal() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_findfirst - PURPOSE - Find the first node in a TST - USAGE - H5ST_ptr_t H5ST_findfirst(tree) - H5ST_tree_t *tree; IN: TST to locate first node within - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Get the first (lexicographically) node in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -H5ST_ptr_t -H5ST_findfirst(H5ST_tree_t *tree) -{ - H5ST_ptr_t ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - if (NULL == (ret_value = H5ST_findfirst_internal(tree->root))) - HGOTO_ERROR(H5E_TST, H5E_NOTFOUND, NULL, "no nodes in TST"); - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_findfirst() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_getnext - PURPOSE - Internal routine to find the next node in a given level of a TST - USAGE - H5ST_ptr_t H5ST_getnext(p) - H5ST_ptr_t *p; IN: Pointer to node to find next node from - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Get the next (lexicographically) node in the current level of a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static H5ST_ptr_t -H5ST_getnext(H5ST_ptr_t p) -{ - H5ST_ptr_t ret_value = NULL; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* If the node to continue from has higher-valued nodes attached */ - if (p->hikid) { - /* Go to first higher-valued node */ - p = p->hikid; - - /* Find least node from here */ - while (p->lokid) - p = p->lokid; - HGOTO_DONE(p); - } /* end if */ - else { - H5ST_ptr_t q; /* Temporary TST node pointer */ - - /* Go up one level in current tree */ - q = p->parent; - if (q == NULL) - HGOTO_DONE(NULL); - - /* While the previous node was the higher-valued node, keep backing up the tree */ - while (q->hikid == p) { - p = q; - q = p->parent; - if (NULL == q) - HGOTO_DONE(NULL); - } /* end while */ - HGOTO_DONE(q); - } /* end else */ - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_getnext() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_findnext - PURPOSE - Find the next node from a node in a TST - USAGE - H5ST_ptr_t H5ST_findnext(p) - H5ST_ptr_t p; IN: Current node to continue from - RETURNS - Success: Non-NULL - Failure: NULL - DESCRIPTION - Get the next (lexicographically) node in a TST - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -H5ST_ptr_t -H5ST_findnext(H5ST_ptr_t p) -{ - H5ST_ptr_t q; /* Temporary pointer to TST node */ - H5ST_ptr_t ret_value = NULL; /* Return value */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Find the next node at the current level, or go back up the tree */ - do { - q = H5ST_getnext(p); - if (q) { - HGOTO_DONE(H5ST_findfirst_internal(q->eqkid)); - } /* end if */ - else - p = p->up; - } while (p); - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_findnext() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_delete_internal - PURPOSE - Delete a node from a TST - USAGE - herr_t H5ST_delete_internal(root,p) - H5ST_ptr_t *root; IN/OUT: Root of TST to delete node from - H5ST_ptr_t p; IN: Node to delete - RETURNS - Success: Non-negative - Failure: Negative - DESCRIPTION - Delete a node from a TST. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This should be the final node for a string. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5ST_delete_internal(H5ST_ptr_t *root, H5ST_ptr_t p) -{ - H5ST_ptr_t q, /* Temporary pointer to TST node */ - newp; /* Pointer to node which will replace deleted node in tree */ - - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Find node to replace one being deleted */ - if (p->lokid) { - /* If the deleted node has lo & hi kids, attach them together */ - if (p->hikid) { - q = p->lokid; - while (q->hikid) - q = q->hikid; - q->hikid = p->hikid; - p->hikid->parent = q; - } /* end if */ - newp = p->lokid; - } /* end if */ - else if (p->hikid) { - newp = p->hikid; - } /* end if */ - else { - newp = NULL; - } /* end else */ - - /* Deleted node is in middle of tree */ - if (p->parent) { - /* Attach new node to correct side of parent */ - if (p == p->parent->lokid) - p->parent->lokid = newp; - else - p->parent->hikid = newp; - if (newp) - newp->parent = p->parent; - } /* end if */ - else { - if (newp) - newp->parent = p->parent; - if (p->up) { - p->up->eqkid = newp; - - /* If we deleted the last node in the TST, delete the upper node also */ - if (NULL == newp) - H5ST_delete_internal(root, p->up); - } /* end if */ - else /* Deleted last node at top level of tree */ - *root = newp; - } /* end else */ - - p = H5FL_FREE(H5ST_node_t, p); - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5ST_delete_internal() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_delete - PURPOSE - Delete a node from a TST - USAGE - herr_t H5ST_delete(tree,p) - H5ST_tree_t *tree; IN/OUT: TST to delete node from - H5ST_ptr_t p; IN: Node to delete - RETURNS - Success: Non-negative - Failure: Negative - DESCRIPTION - Delete a node from a TST. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - This should be the final node for a string. - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5ST_delete(H5ST_tree_t *tree, H5ST_ptr_t p) -{ - herr_t ret_value = SUCCEED; /* Return value */ - - FUNC_ENTER_NOAPI(FAIL) - - if (H5ST_delete_internal(&tree->root, p) < 0) - HGOTO_ERROR(H5E_TST, H5E_CANTDELETE, FAIL, "can't delete node from TST") - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* end H5ST_delete() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_remove - PURPOSE - Remove a node from a TST - USAGE - void *H5ST_remove(tree,s) - H5ST_tree_t *tree; IN/OUT: TST to remove node from - const char *s; IN: String of key for node to remove - RETURNS - Success: Non-NULL, pointer to object stored for key - Failure: Negative - DESCRIPTION - Remove a node from a TST, returning the object from the node. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -void * -H5ST_remove(H5ST_tree_t *tree, const char *s) -{ - H5ST_ptr_t node; /* Pointer to node to remove */ - void * ret_value; /* Return value */ - - FUNC_ENTER_NOAPI(NULL) - - /* Locate the node to remove */ - if (NULL == (node = H5ST_find_internal(tree->root, s))) - HGOTO_ERROR(H5E_TST, H5E_NOTFOUND, NULL, "key not found in TST") - - /* Get the pointer to the object to return */ - ret_value = node->eqkid; - - /* Remove the node from the TST */ - if (H5ST_delete_internal(&tree->root, node) < 0) - HGOTO_ERROR(H5E_TST, H5E_CANTDELETE, NULL, "can't delete node from TST") - -done: - FUNC_LEAVE_NOAPI(ret_value) -} /* H5ST_remove() */ - -#ifdef H5ST_DEBUG - -/*-------------------------------------------------------------------------- - NAME - H5ST__dump_internal - PURPOSE - Dump all the nodes of a TST - USAGE - herr_t H5ST_dump(p) - H5ST_ptr_t p; IN: Root of TST to dump - RETURNS - Success: Non-negative - Failure: Negative - DESCRIPTION - Dump information for a TST. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -static herr_t -H5ST__dump_internal(H5ST_ptr_t p) -{ - FUNC_ENTER_STATIC_NOERR - - if (p) { - HDprintf("p=%p\n", (void *)p); - HDprintf("\tp->up=%p\n", (void *)p->up); - HDprintf("\tp->parent=%p\n", (void *)p->parent); - HDprintf("\tp->lokid=%p\n", (void *)p->lokid); - HDprintf("\tp->hikid=%p\n", (void *)p->hikid); - HDprintf("\tp->eqkid=%p\n", (void *)p->eqkid); - HDprintf("\tp->splitchar=%c\n", p->splitchar); - - H5ST__dump_internal(p->lokid); - if (p->splitchar) - H5ST__dump_internal(p->eqkid); - else - HDprintf("%s\n", (char *)p->eqkid); - H5ST__dump_internal(p->hikid); - } /* end if */ - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5ST__dump_internal() */ - -/*-------------------------------------------------------------------------- - NAME - H5ST_dump - PURPOSE - Dump all the nodes of a TST - USAGE - herr_t H5ST_dump(tree) - H5ST_tree_t *tree; IN: TST to dump - RETURNS - Success: Non-negative - Failure: Negative - DESCRIPTION - Dump information for a TST. - GLOBAL VARIABLES - COMMENTS, BUGS, ASSUMPTIONS - EXAMPLES - REVISION LOG ---------------------------------------------------------------------------*/ -herr_t -H5ST_dump(H5ST_tree_t *tree) -{ - FUNC_ENTER_NOAPI_NOINIT_NOERR - - /* Dump the tree */ - H5ST__dump_internal(tree->root); - - FUNC_LEAVE_NOAPI(SUCCEED) -} /* end H5ST_dump() */ -#endif /* H5ST_DEBUG */ diff --git a/src/H5STprivate.h b/src/H5STprivate.h deleted file mode 100644 index c9d643e..0000000 --- a/src/H5STprivate.h +++ /dev/null @@ -1,63 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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://www.hdfgroup.org/licenses. * - * If you do not have access to either file, you may request a copy from * - * help@hdfgroup.org. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/* - * This file contains private information about the H5ST module - */ -#ifndef _H5STprivate_H -#define _H5STprivate_H - -#ifdef LATER -#include "H5STpublic.h" -#endif /* LATER */ - -/* Private headers needed by this file */ -#include "H5private.h" - -/* Typedefs */ - -/* Internal nodes for TST */ -typedef struct H5ST_node *H5ST_ptr_t; -typedef struct H5ST_node { - char splitchar; /* Character represented at node */ - H5ST_ptr_t up; /* Pointer to the node in the tree above (before) this node */ - H5ST_ptr_t parent; /* Pointer to the next higher tree node in this tree */ - H5ST_ptr_t lokid; /* Pointer to the lower node from this one, in this tree */ - H5ST_ptr_t eqkid; /* Pointer to the parent node in the next tree down (after) this node */ - H5ST_ptr_t hikid; /* Pointer to the higher node from this one, in this tree */ -} H5ST_node_t; - -/* Wrapper about TST */ -typedef struct { - H5ST_ptr_t root; /* Pointer to actual TST */ -} H5ST_tree_t; - -/* Macro to access "data" pointer in H5ST_node_t's returned from functions */ -#define H5ST_NODE_DATA(p) ((void *)(p->eqkid)) - -/* Private routines */ -H5_DLL H5ST_tree_t *H5ST_create(void); -H5_DLL herr_t H5ST_close(H5ST_tree_t *p); -H5_DLL herr_t H5ST_insert(H5ST_tree_t *root, const char *s, void *obj); -H5_DLL htri_t H5ST_search(H5ST_tree_t *root, const char *s); -H5_DLL H5ST_ptr_t H5ST_find(H5ST_tree_t *root, const char *s); -H5_DLL void * H5ST_locate(H5ST_tree_t *root, const char *s); -H5_DLL H5ST_ptr_t H5ST_findfirst(H5ST_tree_t *p); -H5_DLL H5ST_ptr_t H5ST_findnext(H5ST_ptr_t p); -H5_DLL void * H5ST_remove(H5ST_tree_t *root, const char *s); -H5_DLL herr_t H5ST_delete(H5ST_tree_t *root, H5ST_ptr_t p); -#ifdef H5ST_DEBUG -H5_DLL herr_t H5ST_dump(H5ST_tree_t *tree); -#endif /* H5ST_DEBUG */ - -#endif /* _H5STprivate_H */ diff --git a/src/Makefile.am b/src/Makefile.am index 08c420f..fc9cbe2 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -104,7 +104,6 @@ libhdf5_la_SOURCES= H5.c H5checksum.c H5dbg.c H5lib_settings.c H5system.c \ H5Sselect.c H5Stest.c \ H5SL.c \ H5SM.c H5SMbtree2.c H5SMcache.c H5SMmessage.c H5SMtest.c \ - H5ST.c \ H5T.c H5Tarray.c H5Tbit.c H5Tcommit.c H5Tcompound.c H5Tconv.c \ H5Tcset.c H5Tdbg.c H5Tdeprec.c H5Tenum.c H5Tfields.c H5Tfixed.c \ H5Tfloat.c H5Tinit.c H5Tnative.c H5Toffset.c H5Toh.c H5Topaque.c \ diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt index 5b4302e..6770666 100644 --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -245,7 +245,6 @@ set (testhdf5_SOURCES ${HDF5_TEST_SOURCE_DIR}/tskiplist.c ${HDF5_TEST_SOURCE_DIR}/tsohm.c ${HDF5_TEST_SOURCE_DIR}/ttime.c - ${HDF5_TEST_SOURCE_DIR}/ttst.c ${HDF5_TEST_SOURCE_DIR}/tunicode.c ${HDF5_TEST_SOURCE_DIR}/tvltypes.c ${HDF5_TEST_SOURCE_DIR}/tvlstr.c diff --git a/test/Makefile.am b/test/Makefile.am index d6e030b..018d447 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -242,7 +242,7 @@ CHECK_CLEANFILES+=accum.h5 cmpd_dset.h5 compact_dataset.h5 dataset.h5 dset_offse # Sources for testhdf5 executable testhdf5_SOURCES=testhdf5.c tarray.c tattr.c tchecksum.c tconfig.c tfile.c \ tgenprop.c th5o.c th5s.c tcoords.c theap.c tid.c titerate.c tmeta.c tmisc.c \ - trefer.c trefer_deprec.c trefstr.c tselect.c tskiplist.c tsohm.c ttime.c ttst.c tunicode.c \ + trefer.c trefer_deprec.c trefstr.c tselect.c tskiplist.c tsohm.c ttime.c tunicode.c \ tvlstr.c tvltypes.c # Sources for Use Cases diff --git a/test/testhdf5.c b/test/testhdf5.c index 5e413f3..45c0f9f 100644 --- a/test/testhdf5.c +++ b/test/testhdf5.c @@ -45,7 +45,6 @@ main(int argc, char *argv[]) AddTest("config", test_configure, cleanup_configure, "Configure definitions", NULL); AddTest("metadata", test_metadata, cleanup_metadata, "Encoding/decoding metadata", NULL); AddTest("checksum", test_checksum, cleanup_checksum, "Checksum algorithm", NULL); - AddTest("tst", test_tst, NULL, "Ternary Search Trees", NULL); AddTest("heap", test_heap, NULL, "Memory Heaps", NULL); AddTest("skiplist", test_skiplist, NULL, "Skip Lists", NULL); AddTest("refstr", test_refstr, NULL, "Reference Counted Strings", NULL); diff --git a/test/testhdf5.h b/test/testhdf5.h index f3cb995..5fb01a8 100644 --- a/test/testhdf5.h +++ b/test/testhdf5.h @@ -203,7 +203,6 @@ extern "C" { /* Prototypes for the test routines */ void test_metadata(void); void test_checksum(void); -void test_tst(void); void test_heap(void); void test_refstr(void); void test_file(void); diff --git a/test/ttst.c b/test/ttst.c deleted file mode 100644 index 53aab5e..0000000 --- a/test/ttst.c +++ /dev/null @@ -1,391 +0,0 @@ -/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * - * 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://www.hdfgroup.org/licenses. * - * If you do not have access to either file, you may request a copy from * - * help@hdfgroup.org. * - * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ - -/* - FILE - tst.c - Test HDF Ternary Search Tree (tst) routines. - - REMARKS - - DESIGN - - BUGS/LIMITATIONS - - EXPORTED ROUTINES - - AUTHOR - Quincey Koziol - - MODIFICATION HISTORY - 12/9/02 - Started coding - */ - -#include "testhdf5.h" -#include "H5STprivate.h" - -/* Test words to insert into s TST */ -static const char *words[] = { - "We", "hold", "these", "truths", "to", "be", "self-evident,", - "that", "all", "men", "are", "created", "equal,", "that", - "they", "are", "endowed", "by", "their", "Creator", "with", - "certain", "unalienable", "Rights,", "that", "among", "these", "are", - "Life,", "Liberty", "and", "the", "pursuit", "of", "Happiness."}; -/* Number of words in test words set */ -size_t num_words; - -/* Number of unique words in test word set */ -size_t num_uniq_words; -/* Unique words in test word set */ -char **uniq_words; -/* Randomized order version of words in test word set */ -char **rand_uniq_words; -/* Sorted order version of words in test word set */ -char **sort_uniq_words; - -static int -tst_strcmp(const void *_s1, const void *_s2) -{ - return (HDstrcmp(*(const char *const *)_s1, *(const char *const *)_s2)); -} - -/**************************************************************** -** -** test_tst_init(): Test basic H5ST (ternary search tree) selection code. -** Initialize data for TST testing -** -****************************************************************/ -static void -test_tst_init(void) -{ - time_t curr_time; /* Current time, for seeding random number generator */ - char * tmp_word; /* Temporary pointer to word in word set */ - size_t u, v, w; /* Local index variables */ - - /* Compute the number of words in the test set */ - num_words = sizeof(words) / sizeof(words[0]); - - /* Determine the number of unique words in test set */ - /* (Not particularly efficient, be careful if many words are added to set) */ - num_uniq_words = 0; - for (u = 0; u < num_words; u++) { - /* Assume word is unique */ - num_uniq_words++; - for (v = 0; v < u; v++) - /* If word is already found in words looked at, decrement unique count */ - if (!HDstrcmp(words[u], words[v])) { - num_uniq_words--; - break; - } /* end if */ - } /* end for */ - - /* Allocate space for the array of unique words */ - uniq_words = (char **)HDmalloc(sizeof(char *) * num_uniq_words); - - /* Allocate space for the array of randomized order unique words also */ - rand_uniq_words = (char **)HDmalloc(sizeof(char *) * num_uniq_words); - - /* Allocate space for the array of sorted order unique words also */ - sort_uniq_words = (char **)HDmalloc(sizeof(char *) * num_uniq_words); - - /* Insert unique words from test set into unique word set */ - w = 0; - for (u = 0; u < num_words; u++) { - /* Assume word is unique */ - tmp_word = (char *)words[u]; - for (v = 0; v < u; v++) - /* If word is already found in words looked at, decrement unique count */ - if (!HDstrcmp(words[u], words[v])) { - tmp_word = NULL; - break; - } /* end if */ - - /* Check if word was actually unique */ - if (tmp_word != NULL) - uniq_words[w++] = tmp_word; - } /* end for */ - - /* Create randomized set of unique words */ - for (u = 0; u < num_uniq_words; u++) - rand_uniq_words[u] = uniq_words[u]; - curr_time = HDtime(NULL); - HDsrandom((unsigned)curr_time); - for (u = 0; u < num_uniq_words; u++) { - v = u + ((size_t)HDrandom() % (num_uniq_words - u)); - if (u != v) { - tmp_word = rand_uniq_words[u]; - rand_uniq_words[u] = rand_uniq_words[v]; - rand_uniq_words[v] = tmp_word; - } /* end if */ - } /* end for */ - - /* Create sorted set of unique words */ - for (u = 0; u < num_uniq_words; u++) - sort_uniq_words[u] = uniq_words[u]; - HDqsort(sort_uniq_words, num_uniq_words, sizeof(char *), tst_strcmp); -} /* end test_tst_init() */ - -/**************************************************************** -** -** test_tst_create(): Test basic H5ST (ternary search tree) selection code. -** Tests creating and closing TSTs. -** -****************************************************************/ -static void -test_tst_create(void) -{ - H5ST_tree_t *tree; /* TST created */ - herr_t ret; /* Generic return value */ - - /* Output message about test being performed */ - MESSAGE(5, ("Testing Creating & Closing TSTs\n")); - - /* Try closing a NULL tree */ - tree = NULL; - ret = H5ST_close(tree); - VERIFY(ret, FAIL, "H5ST_close"); - - /* Try creating a TST */ - tree = H5ST_create(); - CHECK_PTR(tree, "H5ST_create"); - - /* Try closing a real tree */ - ret = H5ST_close(tree); - CHECK(ret, FAIL, "H5ST_close"); - -} /* end test_tst_create() */ - -/**************************************************************** -** -** test_tst_insert(): Test basic H5ST (ternary search tree) selection code. -** Tests inserting key/value pairs into TST -** -****************************************************************/ -static void -test_tst_insert(void) -{ - H5ST_tree_t *tree; /* TST created */ - H5ST_ptr_t found; /* Pointer to TST node found */ - void * obj; /* Pointer to object located in TST */ - size_t u; /* Local index counter */ - htri_t check; /* Is string in TST? */ - herr_t ret; /* Generic return value */ - - /* Output message about test being performed */ - MESSAGE(5, ("Testing Inserting Values into TSTs\n")); - - /* Create the TST */ - tree = H5ST_create(); - CHECK_PTR(tree, "H5ST_create"); - - /* Insert unique words into TST, in random order */ - for (u = 0; u < num_uniq_words; u++) { - ret = H5ST_insert(tree, rand_uniq_words[u], rand_uniq_words[u]); - CHECK(ret, FAIL, "H5ST_insert"); - } /* end for */ - - /* Verify that all words were inserted into TST properly */ - for (u = 0; u < num_uniq_words; u++) { - /* Check that the word is present */ - check = H5ST_search(tree, uniq_words[u]); - VERIFY(check, TRUE, "H5ST_search"); - - /* Check that the value "payloads" are correct */ - found = H5ST_find(tree, uniq_words[u]); - CHECK_PTR(found, "H5ST_find"); - - if (HDstrcmp((const char *)found->eqkid, uniq_words[u])) - TestErrPrintf("%d: TST node values don't match!, found->eqkid=%s, uniq_words[%u]=%s\n", __LINE__, - (char *)found->eqkid, (unsigned)u, uniq_words[u]); - - obj = H5ST_locate(tree, uniq_words[u]); - CHECK_PTR(obj, "H5ST_locate"); - - if (HDstrcmp((const char *)obj, uniq_words[u])) - TestErrPrintf("%d: TST objects don't match!, obj=%s, uniq_words[%u]=%s\n", __LINE__, (char *)obj, - (unsigned)u, uniq_words[u]); - } /* end for */ - - /* Verify that words not in the TST aren't found */ - check = H5ST_search(tree, "foo"); - VERIFY(check, FALSE, "H5ST_search"); - check = H5ST_search(tree, "bar"); - VERIFY(check, FALSE, "H5ST_search"); - check = H5ST_search(tree, "baz"); - VERIFY(check, FALSE, "H5ST_search"); - - /* Close the TST */ - ret = H5ST_close(tree); - CHECK(ret, FAIL, "H5ST_close"); -} /* end test_tst_insert() */ - -/**************************************************************** -** -** test_tst_iterate(): Test basic H5ST (ternary search tree) code. -** Tests iterating through key/value pairs in TST -** -****************************************************************/ -static void -test_tst_iterate(void) -{ - H5ST_tree_t *tree; /* TST created */ - H5ST_ptr_t found; /* Pointer to TST node found */ - size_t u; /* Local index counter */ - herr_t ret; /* Generic return value */ - - /* Output message about test being performed */ - MESSAGE(5, ("Testing Iterating Over TSTs\n")); - - /* Create the TST */ - tree = H5ST_create(); - CHECK_PTR(tree, "H5ST_create"); - - /* Insert unique words into TST, in random order */ - for (u = 0; u < num_uniq_words; u++) { - ret = H5ST_insert(tree, rand_uniq_words[u], rand_uniq_words[u]); - CHECK(ret, FAIL, "H5ST_insert"); - } /* end for */ - - /* Use findfirst/findnext calls to iterate through TST */ - found = H5ST_findfirst(tree); - CHECK_PTR(found, "H5ST_findfirst"); - u = 0; - do { - /* Check that the strings in the TST are in the correct order */ - if (HDstrcmp((const char *)found->eqkid, sort_uniq_words[u])) - TestErrPrintf("%d: TST node values don't match!, found->eqkid=%s, sort_uniq_words[%u]=%s\n", - __LINE__, (char *)found->eqkid, (unsigned)u, sort_uniq_words[u]); - - /* Advance to next string in TST */ - found = H5ST_findnext(found); - u++; - } while (found != NULL); - - /* Close the TST */ - ret = H5ST_close(tree); - CHECK(ret, FAIL, "H5ST_close"); -} /* end test_tst_iterate() */ - -/**************************************************************** -** -** test_tst_remove(): Test basic H5ST (ternary search tree) code. -** Tests removing key/value pairs by string value in TST -** -****************************************************************/ -static void -test_tst_remove(void) -{ - H5ST_tree_t *tree; /* TST created */ - H5ST_ptr_t found; /* Pointer to TST node found */ - void * obj; /* Pointer to object removed from TST */ - htri_t check; /* Is string in TST? */ - size_t u; /* Local index counter */ - herr_t ret; /* Generic return value */ - - /* Output message about test being performed */ - MESSAGE(5, ("Testing Removing String Values from TSTs\n")); - - /* Create the TST */ - tree = H5ST_create(); - CHECK_PTR(tree, "H5ST_create"); - - /* Insert unique words into TST, in random order */ - for (u = 0; u < num_uniq_words; u++) { - ret = H5ST_insert(tree, rand_uniq_words[u], rand_uniq_words[u]); - CHECK(ret, FAIL, "H5ST_insert"); - } /* end for */ - - /* Remove strings from TST in random order */ - for (u = 0; u < num_uniq_words; u++) { - obj = H5ST_remove(tree, rand_uniq_words[u]); - CHECK_PTR(obj, "H5ST_remove"); - - /* Check that the correct string was removed from TST */ - if (HDstrcmp((const char *)obj, rand_uniq_words[u])) - TestErrPrintf("%d: TST node values don't match!, obj=%s, rand_uniq_words[%u]=%s\n", __LINE__, - (char *)obj, (unsigned)u, rand_uniq_words[u]); - - /* Check that the string can't be found in the TST any longer */ - check = H5ST_search(tree, rand_uniq_words[u]); - VERIFY(check, FALSE, "H5ST_search"); - } /* end for */ - - /* Re-insert unique words into TST, in random order */ - for (u = 0; u < num_uniq_words; u++) { - ret = H5ST_insert(tree, rand_uniq_words[u], rand_uniq_words[u]); - CHECK(ret, FAIL, "H5ST_insert"); - } /* end for */ - - /* Remove TST nodes from TST in random order */ - for (u = 0; u < num_uniq_words; u++) { - /* Get the pointer to the node to delete */ - found = H5ST_find(tree, rand_uniq_words[u]); - CHECK_PTR(found, "H5ST_find"); - - /* Check that the correct object will be removed from TST */ - if (HDstrcmp((const char *)found->eqkid, rand_uniq_words[u])) - TestErrPrintf("%d: TST node values don't match!, found->eqkid=%s, rand_uniq_words[%u]=%s\n", - __LINE__, (char *)found->eqkid, (unsigned)u, rand_uniq_words[u]); - - /* Remove the node */ - ret = H5ST_delete(tree, found); - CHECK(ret, FAIL, "H5ST_delete"); - - /* Check that the string can't be found in the TST any longer */ - check = H5ST_search(tree, rand_uniq_words[u]); - VERIFY(check, FALSE, "H5ST_search"); - } /* end for */ - - /* Close the TST */ - ret = H5ST_close(tree); - CHECK(ret, FAIL, "H5ST_close"); -} /* end test_tst_remove() */ - -/**************************************************************** -** -** test_tst_finalize(): Test basic H5ST (ternary search tree) selection code. -** Wrap up data for TST testing -** -****************************************************************/ -static void -test_tst_finalize(void) -{ - /* Release memory for unordered, randomized and sorted order unique words */ - HDfree(uniq_words); - HDfree(rand_uniq_words); - HDfree(sort_uniq_words); -} /* end test_tst_finalize() */ - -/**************************************************************** -** -** test_tst(): Main H5ST selection testing routine. -** -****************************************************************/ -void -test_tst(void) -{ - /* Output message about test being performed */ - MESSAGE(5, ("Testing Ternary Search Trees\n")); - - /* Initialize TST testing data */ - test_tst_init(); - - /* Actual TST tests */ - test_tst_create(); /* Test TST creation */ - test_tst_insert(); /* Test TST insertion */ - test_tst_iterate(); /* Test TST iteration */ - test_tst_remove(); /* Test TST deletion */ - - /* Finalize TST testing data */ - test_tst_finalize(); -} /* end test_tst() */ -- cgit v0.12