diff options
author | Larry Knox <lrknox@hdfgroup.org> | 2021-05-05 03:41:38 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-05-05 03:41:38 (GMT) |
commit | b19b6e5e37ebf9233d81517688b79b32383f8be5 (patch) | |
tree | 3cb02e9ce63a3a92358c90faaafab31b17d9e4e8 /src/H5ST.c | |
parent | 021d7c7278fd9c182802f2d5419438716beb37bc (diff) | |
download | hdf5-b19b6e5e37ebf9233d81517688b79b32383f8be5.zip hdf5-b19b6e5e37ebf9233d81517688b79b32383f8be5.tar.gz hdf5-b19b6e5e37ebf9233d81517688b79b32383f8be5.tar.bz2 |
Cherry-pick 12 develop branch PRs to hdf5_1_12 (#622)
* Snapshot version 1.12 release 1-3. Update version to 1.12.1-4.
* First cut of the H5 public API documentation. (#80)
* First cut of the H5 public API documentation.
* Added H5Z "bonus track."
* Applied Quincey's patch.
* Added the missing patches from Quincey's original patch.
* H5PL (complete) and basic H5VL API documentation.
* Added H5I API docs.
* Added H5L API docs.
* First installment from Elena's H5T batch.
* Second installment of Elena's H5T batch.
* Final installment of Elena's H5T batch.
* Full set of current H5F documentation. (#105)
* First cut of the H5 public API documentation.
* Added H5Z "bonus track."
* Applied Quincey's patch.
* Added the missing patches from Quincey's original patch.
* H5PL (complete) and basic H5VL API documentation.
* Added H5I API docs.
* Added H5L API docs.
* First installment from Elena's H5T batch.
* Second installment of Elena's H5T batch.
* Final installment of Elena's H5T batch.
* Migrated documentation for SWMR functions.
* Catching up on MDC functions.
* Integrated the H5F MDC function documentation.
* Added MDC and parallel H5F functions.
* Slightly updated main page.
* Added doxygen/dox/H5AC_cache_config_t.dox to MANIFEST.
* Doxygen - added (mostly) beginner functions (#112)
* Doxygen - added (mostly) beginner functions
* Removed duplicate H5Pset_szip function
* Add src/H5module.h to MANIFEST.
* close #195. (#196)
* Update HDF5PluginMacros.cmake
* Update HDF5PluginMacros.cmake
* Avoid aligned access for references by decoding into temporary buffer and then copying the result into the actual buffer. Update test to be more thorough with using compound datatype fields everywhere. (#206)
* Modify temporary rpath for testing in java example scripts. (#230)
* Fix undefined left shifting of negative numbers (#338)
Undefined Bahavior Sanitizer errored here about left shifting negative numbers.
* Fixes various warnings noticed on Windows (#425)
* Fixes various warnings noticed on Windows
- Adds a prototype for our implementation of vasprintf
- Return type of H5_get_utf16_str() is now non-const
- Fixes possible uninitialized return type in Wremove_utf8
- Better isolation of fork() code in accum.c:test_swmr_write_big()
- Better isolation of non-zlib code in dsets.c:test_filter_delete()
- Removed unused variable in trefer.c:test_reference_cmpnd_obj()
* Fixes clang-format issues
* Applied clang-tidy readability-non-const-parameter warning fixes auto… (#429)
* Automatically applied clang-tidy readability-avoid-const-params-in-decls fixes
Removes useless const declarations.
* Fixed most readability-non-const-parameter warnings
These changes were made automatically by clang-tidy, but I manually reverted the changes related to the H5Z_func_t signature.
* Reformat source with clang v10.0.1.
Co-authored-by: Larry Knox <lrknox@hdfgroup.org>
* Added C++11 override keyword where appropriate (#433)
Added H5_OVERRIDE macro for compatibility with both C++11 and older.
* Various clang tidy warning fixes (#448)
* Fixed clang-tidy bugprone-reserved-identifier warnings
* Fixed clang-tidy bugprone-assert-side-effect warnings
* Fixed clang-tidy bugprone-copy-constructor-init warning
* Fixed clang-tidy readability-redundant-preprocessor warning
For error_test.c the removed code was already dead, because it was in the else of an `#if H5_USE_16_API` block.
Based on H5Location.h, I think p_get_ref_obj_type was meant to be in `#ifndef DOXYGEN_SHOULD_SKIP_THIS` and an `#endif` was missing. Similarly, in the header, getObjTypeByIdx is only in H5_NO_DEPRECATED_SYMBOLS, not DOXYGEN_SHOULD_SKIP_THIS.
* Fixed clang-tidy readability-redundant-string-init warnings
* Fixed some clang-tidy performance-type-promotion-in-math-fn warnings
* Fixed clang-tidy performance-unnecessary-value-param warnings
* Reformat source with clang v10.0.1.
Co-authored-by: Larry Knox <lrknox@hdfgroup.org>
* Removed checks/workarounds for pre-C++89 compatibility (#449)
After 30+ years, just assume that the following exist:
- extension-less includes
- namespaces
- std::
- static_cast
- bool
* Fixed all clang-tidy bugprone-suspicious-string-compare warnings (#451)
* Fixed all clang-tidy bugprone-suspicious-string-compare warnings
This change was generated entirely by clang-tidy itself.
* Reformat code with clang v10.0.1.
Co-authored-by: Larry Knox <lrknox@hdfgroup.org>
* Remove 2 functions incorrectly merged from develop in a cherry-pick merge of PR #451.
* Minor parallel improvements (#519)
* Improve MPI error reporting, handled failed operations in parallel tests more nicely, and clean up MPI_Allreduce for determining whether to break collective I/O
* Committing clang-format changes
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Clean up MPI-IO VFD tracing support (#520)
* Clean up tracing support
* Committing clang-format changes
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Brings the native implementation of H5Fdelete() from Bitbucket (#524)
* Committing clang-format changes
* Brings the native VFD H5Fdelete() implementation from Bitbucket
Only brings the 'del' callbacks, not the 'open/close' scheme.
* Formatter changes
* Committing clang-format changes
* Fixes direct VFD callback name
* Removes UNUSED macro from family API call
* Adds barrier and rank 0 check to MPI-I/O VFD delete
* Revert "Adds barrier and rank 0 check to MPI-I/O VFD delete"
This reverts commit 909765f759d9d96e84f4b8b1cc14f7d2b3ac8143.
* Revert "Revert "Adds barrier and rank 0 check to MPI-I/O VFD delete""
This reverts commit 9b04bef1157853fc79fcb8fcc3e8ba1371091702.
* Adds a second barrier after the delete in MPI-I/O VFD
* Only delete files in the core VFD when the backing store flag is set
* Fixes string issues in multi VFD
Also, h5test.c cleanup code now uses H5Fdelete().
* Formatted source
* Rework fapl checks for MPI-I/O VFD delete callback
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Minor warning fixes in develop (#526)
* Committing clang-format changes
* Minor warning fixes
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Removes implementation of my_strdup() from the multi VFD (#527)
* Committing clang-format changes
* Removes my_strdup() from the multi VFD
* Use strdup directly when memory sanity checks are off
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Removes dead H5ST package from the library (#528)
* Committing clang-format changes
* Removes the unused H5ST package from the library
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Fix HDFFV-11232 (#530)
* fixed missed closing of a dataset
* fixed missed closing of a dataset
* fixed typo in error return
* Committing clang-format changes
* minor edits
* code format
* Committing clang-format changes
* code format
* minor edit
* added H5fortkit dependency for H5VLff.F90, HDFFV-11232
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Fixes incorrect usage of H5I_BADID (#554)
* Committing clang-format changes
* Fixes incorrect use of H5I_BADID
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Fixes a segfault when H5Pset_mdc_log_options is called multiple times on a fapl (#601)
* Committing clang-format changes
* Fixes a segfault when H5Pset_mdc_log_options() is called multiple times
An internal string is incorrectly freed when the API call is invoked
multiple times on a property list, which will usually cause a segfault
to occur. On the first call the log location is NULL so the problem
doesn't occur.
Fixes HDFFV-11239
* Fixes typos
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Fix for a segfault when H5Pset_fapl_log is passed an invalid fapl ID (#607)
* Committing clang-format changes
* Fixes an issue where H5Pset_fapl_log sefaults when passed an invalid
fapl ID
This was due to a pointer-containing struct being memset after the first
internal API call. If the first call failed, the error condition would
check if the pointer was not NULL and then attempt to free it if not.
This would lead to the freeing of a wild pointer if an invalid fapl ID
were passed in.
This was fixed by reordering the memset and adding a test to ensure the
problem stays fixed.
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Fixes crashes when size_hint > UINT32_MAX is passed to H5Gcreate1 (#611)
* Committing clang-format changes
* Fixes incorrect size_hint handling in H5Gcreate1
* Updates the size hint type for group creation
* Updates the RELEASE.txt note
* Revert "Updates the RELEASE.txt note"
This reverts commit 3df386acca806d652bbe2209f7c4503b30f068ff.
* Reverts previous behavior to use a uint32_t struct field
* Updates RELEASE.txt
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
* Revert "Brings the native implementation of H5Fdelete() from Bitbucket (#524)"
This reverts commit 38d1b121ae428138b8863c2a319518c7363c2d94.
Co-authored-by: Gerd Heber <gheber@hdfgroup.org>
Co-authored-by: bljhdf <58825073+bljhdf@users.noreply.github.com>
Co-authored-by: H. Joe Lee <hyoklee@hdfgroup.org>
Co-authored-by: Quincey Koziol <quincey@koziol.cc>
Co-authored-by: Sean McBride <sean@rogue-research.com>
Co-authored-by: Dana Robinson <43805+derobins@users.noreply.github.com>
Co-authored-by: Quincey Koziol <koziol@lbl.gov>
Co-authored-by: github-actions <41898282+github-actions[bot]@users.noreply.github.com>
Co-authored-by: Scot Breitenfeld <brtnfld@hdfgroup.org>
Diffstat (limited to 'src/H5ST.c')
-rw-r--r-- | src/H5ST.c | 779 |
1 files changed, 0 insertions, 779 deletions
diff --git a/src/H5ST.c b/src/H5ST.c deleted file mode 100644 index 0b7b858..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_STATIC_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_STATIC_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_STATIC_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_STATIC_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_STATIC_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 */ |