diff options
Diffstat (limited to 'src/H5ST.c')
| -rw-r--r-- | src/H5ST.c | 186 |
1 files changed, 85 insertions, 101 deletions
@@ -16,10 +16,9 @@ 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 */ +#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); @@ -31,7 +30,6 @@ 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 @@ -52,12 +50,12 @@ H5FL_DEFINE_STATIC(H5ST_tree_t); H5ST_tree_t * H5ST_create(void) { - H5ST_tree_t *ret_value; /* Return value */ + H5ST_tree_t *ret_value; /* Return value */ FUNC_ENTER_NOAPI(NULL) /* Allocate wrapper for TST */ - if(NULL == (ret_value = H5FL_MALLOC(H5ST_tree_t))) + if (NULL == (ret_value = H5FL_MALLOC(H5ST_tree_t))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, NULL, "memory allocation failed") /* Set the internal fields */ @@ -67,7 +65,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST_create() */ - /*-------------------------------------------------------------------------- NAME H5ST__close_internal @@ -92,9 +89,9 @@ H5ST__close_internal(H5ST_ptr_t p) FUNC_ENTER_STATIC_NOERR /* Recursively free TST */ - if(p) { + if (p) { H5ST__close_internal(p->lokid); - if(p->splitchar) + if (p->splitchar) H5ST__close_internal(p->eqkid); H5ST__close_internal(p->hikid); p = H5FL_FREE(H5ST_node_t, p); @@ -103,7 +100,6 @@ H5ST__close_internal(H5ST_ptr_t p) FUNC_LEAVE_NOAPI(SUCCEED) } /* end H5ST__close_internal() */ - /*-------------------------------------------------------------------------- NAME H5ST_close @@ -125,16 +121,16 @@ H5ST__close_internal(H5ST_ptr_t p) herr_t H5ST_close(H5ST_tree_t *tree) { - herr_t ret_value = SUCCEED; /* Return value */ + herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI(FAIL) /* Check arguments */ - if(NULL == tree) + if (NULL == tree) HGOTO_ERROR(H5E_ARGS, H5E_BADVALUE, FAIL, "invalid TST") /* Free the TST itself */ - if(H5ST__close_internal(tree->root) < 0) + if (H5ST__close_internal(tree->root) < 0) HGOTO_ERROR(H5E_TST, H5E_CANTFREE, FAIL, "can't free TST") /* Free root node itself */ @@ -144,7 +140,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST_close() */ - /*-------------------------------------------------------------------------- NAME H5ST_insert @@ -168,61 +163,60 @@ done: 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 */ + 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)) { + 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) + 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); + up = pp; + p = &(pp->eqkid); } /* end if */ else { /* Walk through the current tree, searching for the matching character */ parent = pp; - if(d < 0) + if (d < 0) p = &(pp->lokid); else p = &(pp->hikid); } /* end else */ - } /* end while */ + } /* end while */ /* Finish walking through the key string, adding nodes until the end */ for (;;) { - if(NULL == (*p = H5FL_MALLOC(H5ST_node_t))) + if (NULL == (*p = H5FL_MALLOC(H5ST_node_t))) HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "memory allocation failed") - pp = *p; + pp = *p; pp->splitchar = *s; - pp->up = up; - pp->parent = parent; + 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) { + if (*s++ == 0) { pp->eqkid = (H5ST_ptr_t)obj; break; } /* end if */ /* Continue to next character */ parent = NULL; - up = pp; - p = &(pp->eqkid); + up = pp; + p = &(pp->eqkid); } /* end for */ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST_insert() */ - /*-------------------------------------------------------------------------- NAME H5ST_search @@ -246,8 +240,8 @@ done: 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 */ + H5ST_ptr_t p; /* Temporary pointer to TST node */ + htri_t ret_value = FALSE; /* Return value */ FUNC_ENTER_NOAPI_NOINIT_NOERR @@ -255,11 +249,12 @@ H5ST_search(H5ST_tree_t *tree, const char *s) while (p) { if (*s < p->splitchar) p = p->lokid; - else if (*s == p->splitchar) { + else if (*s == p->splitchar) { if (*s++ == 0) HGOTO_DONE(TRUE); p = p->eqkid; - } else + } + else p = p->hikid; } /* end while */ @@ -267,7 +262,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST_search() */ - /*-------------------------------------------------------------------------- NAME H5ST__find_internal @@ -291,18 +285,19 @@ done: static H5ST_ptr_t H5ST__find_internal(H5ST_ptr_t p, const char *s) { - H5ST_ptr_t ret_value = NULL; /* Return value */ + 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) { + else if (*s == p->splitchar) { if (*s++ == 0) HGOTO_DONE(p); p = p->eqkid; - } else + } + else p = p->hikid; } /* end while */ @@ -310,7 +305,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST__find_internal() */ - /*-------------------------------------------------------------------------- NAME H5ST_find @@ -334,18 +328,17 @@ done: H5ST_ptr_t H5ST_find(H5ST_tree_t *tree, const char *s) { - H5ST_ptr_t ret_value; /* Return value */ + H5ST_ptr_t ret_value; /* Return value */ FUNC_ENTER_NOAPI(NULL) - if(NULL == (ret_value = H5ST__find_internal(tree->root, s))) + 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 @@ -368,13 +361,13 @@ done: void * H5ST_locate(H5ST_tree_t *tree, const char *s) { - H5ST_ptr_t node; /* Pointer to node located */ - void *ret_value; /* Return value */ + 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))) + 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 */ @@ -384,7 +377,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* H5ST_locate() */ - /*-------------------------------------------------------------------------- NAME H5ST__findfirst_internal @@ -406,17 +398,17 @@ done: static H5ST_ptr_t H5ST__findfirst_internal(H5ST_ptr_t p) { - H5ST_ptr_t ret_value = NULL; /* Return value */ + H5ST_ptr_t ret_value = NULL; /* Return value */ FUNC_ENTER_STATIC_NOERR - while(p) { + while (p) { /* Find least node in current tree */ - while(p->lokid) + while (p->lokid) p = p->lokid; /* Is least node '\0'? */ - if(p->splitchar == '\0') { + if (p->splitchar == '\0') { /* Return it */ HGOTO_DONE(p); } /* end if */ @@ -424,13 +416,12 @@ H5ST__findfirst_internal(H5ST_ptr_t p) /* Go down to next level of tree */ p = p->eqkid; } /* end else */ - } /* end while */ + } /* end while */ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST__findfirst_internal() */ - /*-------------------------------------------------------------------------- NAME H5ST_findfirst @@ -452,18 +443,17 @@ done: H5ST_ptr_t H5ST_findfirst(H5ST_tree_t *tree) { - H5ST_ptr_t ret_value; /* Return value */ + 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"); + 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 @@ -485,33 +475,33 @@ done: static H5ST_ptr_t H5ST__getnext(H5ST_ptr_t p) { - H5ST_ptr_t ret_value = NULL; /* Return value */ + 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) { + if (p->hikid) { /* Go to first higher-valued node */ p = p->hikid; /* Find least node from here */ - while(p->lokid) + while (p->lokid) p = p->lokid; HGOTO_DONE(p); } /* end if */ else { - H5ST_ptr_t q; /* Temporary TST node pointer */ + H5ST_ptr_t q; /* Temporary TST node pointer */ /* Go up one level in current tree */ q = p->parent; - if(q == NULL) + if (q == NULL) HGOTO_DONE(NULL); /* While the previous node was the higher-valued node, keep backing up the tree */ - while(q->hikid == p) { + while (q->hikid == p) { p = q; q = p->parent; - if(NULL == q) + if (NULL == q) HGOTO_DONE(NULL); } /* end while */ HGOTO_DONE(q); @@ -521,7 +511,6 @@ done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST__getnext() */ - /*-------------------------------------------------------------------------- NAME H5ST_findnext @@ -543,26 +532,25 @@ done: 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 */ + 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) { + if (q) { HGOTO_DONE(H5ST__findfirst_internal(q->eqkid)); } /* end if */ else p = p->up; - } while(p); + } while (p); done: FUNC_LEAVE_NOAPI(ret_value) } /* end H5ST_findnext() */ - /*-------------------------------------------------------------------------- NAME H5ST__delete_internal @@ -586,24 +574,24 @@ done: 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 */ + 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 (p->lokid) { /* If the deleted node has lo & hi kids, attach them together */ - if(p->hikid) { + if (p->hikid) { q = p->lokid; - while(q->hikid) + while (q->hikid) q = q->hikid; - q->hikid = p->hikid; + q->hikid = p->hikid; p->hikid->parent = q; } /* end if */ newp = p->lokid; } /* end if */ - else if(p->hikid) { + else if (p->hikid) { newp = p->hikid; } /* end if */ else { @@ -611,25 +599,25 @@ H5ST__delete_internal(H5ST_ptr_t *root, H5ST_ptr_t p) } /* end else */ /* Deleted node is in middle of tree */ - if(p->parent) { + if (p->parent) { /* Attach new node to correct side of parent */ - if(p == p->parent->lokid) + if (p == p->parent->lokid) p->parent->lokid = newp; else p->parent->hikid = newp; - if(newp) + if (newp) newp->parent = p->parent; } /* end if */ else { - if(newp) + if (newp) newp->parent = p->parent; - if(p->up) { + if (p->up) { p->up->eqkid = newp; /* If we deleted the last node in the TST, delete the upper node also */ - if(NULL == newp) + if (NULL == newp) H5ST__delete_internal(root, p->up); - } /* end if */ + } /* end if */ else /* Deleted last node at top level of tree */ *root = newp; } /* end else */ @@ -639,7 +627,6 @@ H5ST__delete_internal(H5ST_ptr_t *root, H5ST_ptr_t p) FUNC_LEAVE_NOAPI(SUCCEED) } /* end H5ST__delete_internal() */ - /*-------------------------------------------------------------------------- NAME H5ST_delete @@ -663,18 +650,17 @@ H5ST__delete_internal(H5ST_ptr_t *root, H5ST_ptr_t p) herr_t H5ST_delete(H5ST_tree_t *tree, H5ST_ptr_t p) { - herr_t ret_value = SUCCEED; /* Return value */ + herr_t ret_value = SUCCEED; /* Return value */ FUNC_ENTER_NOAPI(FAIL) - if(H5ST__delete_internal(&tree->root, p) < 0) + 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 @@ -697,20 +683,20 @@ done: void * H5ST_remove(H5ST_tree_t *tree, const char *s) { - H5ST_ptr_t node; /* Pointer to node to remove */ - void *ret_value; /* Return value */ + 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))) + 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) + if (H5ST__delete_internal(&tree->root, node) < 0) HGOTO_ERROR(H5E_TST, H5E_CANTDELETE, NULL, "can't delete node from TST") done: @@ -718,7 +704,7 @@ done: } /* H5ST_remove() */ #ifdef H5ST_DEBUG - + /*-------------------------------------------------------------------------- NAME H5ST__dump_internal @@ -742,7 +728,7 @@ H5ST__dump_internal(H5ST_ptr_t p) { FUNC_ENTER_STATIC_NOERR - if(p) { + if (p) { HDprintf("p=%p\n", (void *)p); HDprintf("\tp->up=%p\n", (void *)p->up); HDprintf("\tp->parent=%p\n", (void *)p->parent); @@ -752,7 +738,7 @@ H5ST__dump_internal(H5ST_ptr_t p) HDprintf("\tp->splitchar=%c\n", p->splitchar); H5ST__dump_internal(p->lokid); - if(p->splitchar) + if (p->splitchar) H5ST__dump_internal(p->eqkid); else HDprintf("%s\n", (char *)p->eqkid); @@ -762,7 +748,6 @@ H5ST__dump_internal(H5ST_ptr_t p) FUNC_LEAVE_NOAPI(SUCCEED) } /* end H5ST__dump_internal() */ - /*-------------------------------------------------------------------------- NAME H5ST_dump @@ -792,4 +777,3 @@ H5ST_dump(H5ST_tree_t *tree) FUNC_LEAVE_NOAPI(SUCCEED) } /* end H5ST_dump() */ #endif /* H5ST_DEBUG */ - |