summaryrefslogtreecommitdiffstats
path: root/src/H5SL.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/H5SL.c')
-rw-r--r--src/H5SL.c777
1 files changed, 667 insertions, 110 deletions
diff --git a/src/H5SL.c b/src/H5SL.c
index 7a54b14..005cb86 100644
--- a/src/H5SL.c
+++ b/src/H5SL.c
@@ -32,6 +32,9 @@
* search by position) in section 3.4 of "A Skip List Cookbook",
* but they shouldn't be that hard to add, if necessary)
*
+ * (This implementation has an additional backward pointer, which
+ * allows the list to be iterated in reverse)
+ *
*/
/* Interface initialization */
@@ -50,12 +53,12 @@
/* Local Macros */
-/* Define the code template for insertions for the "OP" in the H5SL_FIND macro */
-#define H5SL_FIND_INSERT_FOUND(SLIST,X,UPDATE,I,ITEM) \
- HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,FAIL,"can't insert duplicate key");
+/* Define the code template for insertions for the "OP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_INSERT_FOUND(SLIST,X,UPDATE,I,ITEM) \
+ HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,NULL,"can't insert duplicate key");
-/* Define the code template for removals for the "OP" in the H5SL_FIND macro */
-#define H5SL_FIND_REMOVE_FOUND(SLIST,X,UPDATE,I,ITEM) \
+/* Define the code template for removals for the "OP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_REMOVE_FOUND(SLIST,X,UPDATE,I,ITEM) \
void *tmp; \
\
for(I=0; I<=(int)SLIST->curr_level; I++) { \
@@ -63,6 +66,10 @@
break; \
*UPDATE[I]=X->forward[I]; \
} /* end for */ \
+ if(SLIST->last==X) \
+ SLIST->last=X->backward; \
+ else \
+ X->forward[0]->backward=X->backward; \
tmp=X->item; \
H5MM_xfree(X); \
while(SLIST->curr_level>0 && SLIST->header->forward[SLIST->curr_level]==NULL) \
@@ -70,61 +77,69 @@
SLIST->nobjs--; \
HGOTO_DONE(tmp);
-/* Define the code template for searches for the "OP" in the H5SL_FIND macro */
-#define H5SL_FIND_SEARCH_FOUND(SLIST,X,UPDATE,I,ITEM) \
+/* Define the code template for searches for the "OP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_SEARCH_FOUND(SLIST,X,UPDATE,I,ITEM) \
HGOTO_DONE(X->item);
-/* Define a code template for updating the "update" vector for the "DOUPDATE" in the H5SL_FIND macro */
-#define H5SL_FIND_YES_UPDATE(X,UPDATE,I) \
+/* Define the code template for finds for the "OP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_FIND_FOUND(SLIST,X,UPDATE,I,ITEM) \
+ HGOTO_DONE(X);
+
+/* Define a code template for updating the "update" vector for the "DOUPDATE" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_YES_UPDATE(X,UPDATE,I) \
UPDATE[I]=&X->forward[I];
-/* Define a code template for _NOT_ updating the "update" vector for the "DOUPDATE" in the H5SL_FIND macro */
-#define H5SL_FIND_NO_UPDATE(X,UPDATE,I)
+/* Define a code template for _NOT_ updating the "update" vector for the "DOUPDATE" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_NO_UPDATE(X,UPDATE,I)
-/* Define a code template for comparing scalar keys for the "CMP" in the H5SL_FIND macro */
-#define H5SL_FIND_SCALAR_CMP(TYPE,PKEY1,PKEY2) \
+/* Define a code template for comparing scalar keys for the "CMP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_SCALAR_CMP(TYPE,PKEY1,PKEY2) \
(*(TYPE *)PKEY1<*(TYPE *)PKEY2)
-/* Define a code template for comparing string keys for the "CMP" in the H5SL_FIND macro */
-#define H5SL_FIND_STRING_CMP(TYPE,PKEY1,PKEY2) \
+/* Define a code template for comparing string keys for the "CMP" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_STRING_CMP(TYPE,PKEY1,PKEY2) \
(HDstrcmp(PKEY1,PKEY2)<0)
-/* Define a code template for comparing scalar keys for the "EQ" in the H5SL_FIND macro */
-#define H5SL_FIND_SCALAR_EQ(TYPE,PKEY1,PKEY2) \
+/* Define a code template for comparing scalar keys for the "EQ" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_SCALAR_EQ(TYPE,PKEY1,PKEY2) \
(*(TYPE *)PKEY1==*(TYPE *)PKEY2)
-/* Define a code template for comparing string keys for the "EQ" in the H5SL_FIND macro */
-#define H5SL_FIND_STRING_EQ(TYPE,PKEY1,PKEY2) \
+/* Define a code template for comparing string keys for the "EQ" in the H5SL_LOCATE macro */
+#define H5SL_LOCATE_STRING_EQ(TYPE,PKEY1,PKEY2) \
(HDstrcmp(PKEY1,PKEY2)==0)
/* Macro used to find node for operation */
-#define H5SL_FIND(OP,DOUPDATE,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+#define H5SL_LOCATE(OP,DOUPDATE,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
CHECKED=NULL; \
for(I=(int)SLIST->curr_level; I>=0; I--) { \
if(X->forward[I]!=CHECKED) { \
- while(X->forward[I] && H5_GLUE3(H5SL_FIND_,CMP,_CMP)(TYPE,X->forward[I]->key,KEY) ) \
+ while(X->forward[I] && H5_GLUE3(H5SL_LOCATE_,CMP,_CMP)(TYPE,X->forward[I]->key,KEY) ) \
X=X->forward[I]; \
CHECKED=X->forward[I]; \
} /* end if */ \
- H5_GLUE3(H5SL_FIND_,DOUPDATE,_UPDATE)(X,UPDATE,I) \
+ H5_GLUE3(H5SL_LOCATE_,DOUPDATE,_UPDATE)(X,UPDATE,I) \
} /* end for */ \
X=X->forward[0]; \
- if(X!=NULL && H5_GLUE3(H5SL_FIND_,CMP,_EQ)(TYPE,X->key,KEY) ) { \
+ if(X!=NULL && H5_GLUE3(H5SL_LOCATE_,CMP,_EQ)(TYPE,X->key,KEY) ) { \
/* What to do when a node is found */ \
- H5_GLUE3(H5SL_FIND_,OP,_FOUND)(SLIST,X,UPDATE,I,ITEM) \
+ H5_GLUE3(H5SL_LOCATE_,OP,_FOUND)(SLIST,X,UPDATE,I,ITEM) \
} /* end if */
/* Macro used to insert node */
#define H5SL_INSERT(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
- H5SL_FIND(INSERT,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+ H5SL_LOCATE(INSERT,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
/* Macro used to remove node */
#define H5SL_REMOVE(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
- H5SL_FIND(REMOVE,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+ H5SL_LOCATE(REMOVE,YES,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
/* Macro used to search for node */
#define H5SL_SEARCH(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
- H5SL_FIND(SEARCH,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+ H5SL_LOCATE(SEARCH,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
+
+/* Macro used to find a node */
+#define H5SL_FIND(CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED) \
+ H5SL_LOCATE(FIND,NO,CMP,SLIST,X,UPDATE,I,TYPE,ITEM,KEY,CHECKED)
/* Private typedefs & structs */
@@ -135,6 +150,7 @@ struct H5SL_node_t {
void *item; /* Pointer to node's item */
size_t level; /* The level of this node */
struct H5SL_node_t **forward; /* Array of forward pointers from this node */
+ struct H5SL_node_t *backward; /* Backward pointer from this node */
};
/* Main skip list data structure */
@@ -149,11 +165,15 @@ struct H5SL_t {
int curr_level; /* Current top level used in list */
size_t nobjs; /* Number of active objects in skip list */
H5SL_node_t *header; /* Header for nodes in skip list */
+ H5SL_node_t *last; /* Pointer to last node in skip list */
};
/* Static functions */
static size_t H5SL_random_level(int p1, size_t max_level);
static H5SL_node_t * H5SL_new_node(size_t lvl, void *item, const void *key);
+static H5SL_node_t *H5SL_insert_common(H5SL_t *slist, void *item, const void *key);
+static herr_t H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data);
+static herr_t H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data);
/* Declare a free list to manage the H5SL_t struct */
H5FL_DEFINE_STATIC(H5SL_t);
@@ -281,6 +301,234 @@ done:
/*--------------------------------------------------------------------------
NAME
+ H5SL_insert_common
+ PURPOSE
+ Common code for inserting an object into a skip list
+ USAGE
+ H5SL_node_t *H5SL_insert_common(slist,item,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *item; IN: Item to insert
+ void *key; IN: Key for item to insert
+
+ RETURNS
+ Returns pointer to new node on success, NULL on failure.
+ DESCRIPTION
+ Common code for inserting an element into a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ Inserting an item with the same key as an existing object fails.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+static H5SL_node_t *
+H5SL_insert_common(H5SL_t *slist, void *item, const void *key)
+{
+ H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
+ H5SL_node_t *checked; /* Pointer to last node checked */
+ H5SL_node_t *x; /* Current node to examine */
+ size_t lvl; /* Level of new node */
+ int i; /* Local index value */
+ H5SL_node_t *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5SL_insert_common);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+
+ /* Work through the forward pointers for a node, finding the node at each
+ * level that is before the location to insert
+ */
+ x=slist->header;
+ switch(slist->type) {
+ case H5SL_TYPE_INT:
+ H5SL_INSERT(SCALAR,slist,x,update,i,const int,item,key,checked)
+ break;
+
+ case H5SL_TYPE_HADDR:
+ H5SL_INSERT(SCALAR,slist,x,update,i,const haddr_t,item,key,checked)
+ break;
+
+ case H5SL_TYPE_STR:
+ H5SL_INSERT(STRING,slist,x,update,i,char *,item,key,checked)
+ break;
+
+ case H5SL_TYPE_HSIZE:
+ H5SL_INSERT(SCALAR,slist,x,update,i,const hsize_t,item,key,checked)
+ break;
+
+ case H5SL_TYPE_UNSIGNED:
+ H5SL_INSERT(SCALAR,slist,x,update,i,const unsigned,item,key,checked)
+ break;
+ } /* end switch */
+
+ /* 'key' must not have been found in existing list, if we get here */
+
+ /* Generate level for new node */
+ lvl=H5SL_random_level(slist->p1,slist->max_level);
+ if((int)lvl>slist->curr_level) {
+ /* Cap the increase in the current level to just one greater */
+ lvl=slist->curr_level+1;
+
+ /* Set the update pointer correctly */
+ update[lvl]=&slist->header->forward[lvl];
+
+ /* Increase the maximum level of the list */
+ slist->curr_level=(int)lvl;
+ } /* end if */
+
+ /* Create new node of proper level */
+ if((x=H5SL_new_node(lvl,item,key))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,NULL,"can't create new skip list node");
+
+ /* Update the backward links */
+ if(*update[0]!=NULL) {
+ x->backward=(*update[0])->backward;
+ (*update[0])->backward=x;
+ } /* end if */
+ else {
+ HDassert(slist->last);
+ x->backward=slist->last;
+ slist->last=x;
+ } /* end else */
+
+ /* Link the new node into the existing forward pointers */
+ for(i=0; i<=(int)lvl; i++) {
+ x->forward[i]=*update[i];
+ *update[i]=x;
+ } /* end for */
+
+ /* Increment the number of nodes in the skip list */
+ slist->nobjs++;
+
+ /* Set return value */
+ ret_value=x;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_insert_common() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_release_common
+ PURPOSE
+ Release all nodes from a skip list, optionally calling a 'free' operator
+ USAGE
+ herr_t H5SL_release_common(slist)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
+ H5SL_operator_t op; IN: Callback function to free item & key
+ void *op_data; IN/OUT: Pointer to application data for callback
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Release all the nodes in a skip list. The 'op' routine is called for
+ each node in the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ The return value from the 'op' routine is ignored.
+
+ The skip list itself is still valid, it just has all its nodes removed.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_release_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
+{
+ H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */
+ size_t u; /* Local index variable */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_release_common);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Free skip list nodes */
+ node=slist->header->forward[0];
+ while(node!=NULL) {
+ next_node=node->forward[0];
+
+ /* Call callback, if one is given */
+ if(op!=NULL)
+ (void)(op)(node->item,(void *)node->key,op_data);
+
+ H5MM_xfree(node);
+ node=next_node;
+ } /* end while */
+
+ /* Reset the header pointers */
+ for(u=0; u<slist->max_level; u++)
+ slist->header->forward[u]=NULL;
+
+ /* Reset the last pointer */
+ slist->last=slist->header;
+
+ /* Reset the dynamic internal fields */
+ slist->curr_level=-1;
+ slist->nobjs=0;
+
+ FUNC_LEAVE_NOAPI(SUCCEED);
+} /* end H5SL_release_common() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_close_common
+ PURPOSE
+ Close a skip list, deallocating it and potentially freeing all its nodes.
+ USAGE
+ herr_t H5SL_close_common(slist,op,opdata)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to close
+ H5SL_operator_t op; IN: Callback function to free item & key
+ void *op_data; IN/OUT: Pointer to application data for callback
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Close a skip list, freeing all internal information. Any objects left in
+ the skip list have the 'op' routine called for each.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ If the 'op' routine returns non-zero, only the nodes up to that
+ point in the list are released and the list is still valid.
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_close_common(H5SL_t *slist, H5SL_operator_t op, void *op_data)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_close_common);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Free skip list nodes */
+ (void)H5SL_release_common(slist,op,op_data); /* always succeeds */
+
+ /* Release header node */
+ H5MM_xfree(slist->header);
+
+ /* Free skip list object */
+ H5FL_FREE(H5SL_t,slist);
+
+ FUNC_LEAVE_NOAPI(SUCCEED);
+} /* end H5SL_close_common() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
H5SL_create
PURPOSE
Create a skip list
@@ -309,7 +557,7 @@ H5SL_create(H5SL_type_t type, double p, size_t max_level)
/* Check args */
HDassert(p>0.0 && p<1.0);
HDassert(max_level>0 && max_level<=H5SL_LEVEL_MAX);
- HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_HSIZE);
+ HDassert(type>=H5SL_TYPE_INT && type<=H5SL_TYPE_UNSIGNED);
/* Allocate skip list structure */
if((new_slist=H5FL_MALLOC(H5SL_t))==NULL)
@@ -333,8 +581,12 @@ H5SL_create(H5SL_type_t type, double p, size_t max_level)
for(u=0; u<max_level; u++)
header->forward[u]=NULL;
+ /* Initialize header node's backward pointer */
+ header->backward=NULL;
+
/* Attach the header */
new_slist->header=header;
+ new_slist->last=header;
/* Set the return value */
ret_value=new_slist;
@@ -388,7 +640,7 @@ H5SL_count(H5SL_t *slist)
NAME
H5SL_insert
PURPOSE
- Insert an objects into a skip list
+ Insert an object into a skip list
USAGE
herr_t H5SL_insert(slist,item,key)
H5SL_t *slist; IN/OUT: Pointer to skip list
@@ -408,14 +660,102 @@ H5SL_count(H5SL_t *slist)
herr_t
H5SL_insert(H5SL_t *slist, void *item, const void *key)
{
+ herr_t ret_value=SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5SL_insert);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+ if(H5SL_insert_common(slist,item,key)==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,FAIL,"can't create new skip list node")
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_insert() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_add
+ PURPOSE
+ Insert an object into a skip list
+ USAGE
+ H5SL_node_t *H5SL_add(slist,item,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *item; IN: Item to insert
+ void *key; IN: Key for item to insert
+
+ RETURNS
+ Returns pointer to new skip list node on success, NULL on failure.
+ DESCRIPTION
+ Insert element into a skip list and return the skip list node for the
+ new element in the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ Inserting an item with the same key as an existing object fails.
+
+ This routine is a useful starting point for next/prev calls
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_add(H5SL_t *slist, void *item, const void *key)
+{
+ H5SL_node_t *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT(H5SL_add);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+ if((ret_value=H5SL_insert_common(slist,item,key))==NULL)
+ HGOTO_ERROR(H5E_SLIST,H5E_CANTINSERT,NULL,"can't create new skip list node")
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_add() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_remove
+ PURPOSE
+ Removes an object from a skip list
+ USAGE
+ void *H5SL_remove(slist,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *key; IN: Key for item to remove
+
+ RETURNS
+ Returns pointer to item removed on success, NULL on failure.
+ DESCRIPTION
+ Remove element from a skip list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+void *
+H5SL_remove(H5SL_t *slist, const void *key)
+{
H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
H5SL_node_t *checked; /* Pointer to last node checked */
H5SL_node_t *x; /* Current node to examine */
- size_t lvl; /* Level of new node */
int i; /* Local index value */
- herr_t ret_value=SUCCEED; /* Return value */
+ void *ret_value=NULL; /* Return value */
- FUNC_ENTER_NOAPI_NOINIT(H5SL_insert);
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_remove);
/* Check args */
assert(slist);
@@ -424,68 +764,44 @@ H5SL_insert(H5SL_t *slist, void *item, const void *key)
/* Check internal consistency */
/* (Pre-condition) */
- /* Insert item into skip list */
+ /* Remove item from skip list */
/* Work through the forward pointers for a node, finding the node at each
- * level that is before the location to insert
+ * level that is before the location to remove
*/
x=slist->header;
switch(slist->type) {
case H5SL_TYPE_INT:
- H5SL_INSERT(SCALAR,slist,x,update,i,const int,item,key,checked)
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const int,-,key,checked)
break;
case H5SL_TYPE_HADDR:
- H5SL_INSERT(SCALAR,slist,x,update,i,const haddr_t,item,key,checked)
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const haddr_t,-,key,checked)
break;
case H5SL_TYPE_STR:
- H5SL_INSERT(STRING,slist,x,update,i,char *,item,key,checked)
+ H5SL_REMOVE(STRING,slist,x,update,i,char *,-,key,checked)
break;
case H5SL_TYPE_HSIZE:
- H5SL_INSERT(SCALAR,slist,x,update,i,const hsize_t,item,key,checked)
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const hsize_t,-,key,checked)
break;
- } /* end switch */
-
- /* 'key' must not have been found in existing list, if we get here */
- /* Generate level for new node */
- lvl=H5SL_random_level(slist->p1,slist->max_level);
- if((int)lvl>slist->curr_level) {
- /* Cap the increase in the current level to just one greater */
- lvl=slist->curr_level+1;
-
- /* Set the update pointer correctly */
- update[lvl]=&slist->header->forward[lvl];
-
- /* Increase the maximum level of the list */
- slist->curr_level=(int)lvl;
- } /* end if */
-
- /* Create new node of proper level */
- if((x=H5SL_new_node(lvl,item,key))==NULL)
- HGOTO_ERROR(H5E_SLIST,H5E_NOSPACE,FAIL,"can't create new skip list node");
-
- /* Link the new node into the existing list */
- for(i=0; i<=(int)lvl; i++) {
- x->forward[i]=*update[i];
- *update[i]=x;
- } /* end for */
-
- /* Increment the number of nodes in the skip list */
- slist->nobjs++;
+ case H5SL_TYPE_UNSIGNED:
+ H5SL_REMOVE(SCALAR,slist,x,update,i,const unsigned,-,key,checked)
+ break;
+ } /* end switch */
done:
FUNC_LEAVE_NOAPI(ret_value);
-} /* end H5SL_insert() */
+} /* end H5SL_remove() */
/*--------------------------------------------------------------------------
NAME
H5SL_search
PURPOSE
- Search for objects into a skip list
+ Search for object in a skip list
USAGE
void *H5SL_search(slist,key)
H5SL_t *slist; IN/OUT: Pointer to skip list
@@ -539,9 +855,13 @@ H5SL_search(H5SL_t *slist, const void *key)
case H5SL_TYPE_HSIZE:
H5SL_SEARCH(SCALAR,slist,x,-,i,const hsize_t,-,key,checked)
break;
+
+ case H5SL_TYPE_UNSIGNED:
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const unsigned,-,key,checked)
+ break;
} /* end switch */
- /* 'key' must not have been found in existing list, if we get here */
+ /* 'key' must not have been found in list, if we get here */
ret_value=NULL;
done:
@@ -551,33 +871,35 @@ done:
/*--------------------------------------------------------------------------
NAME
- H5SL_remove
+ H5SL_less
PURPOSE
- Removes an object from a skip list
+ Search for object in a skip list that is less than or equal to 'key'
USAGE
- void *H5SL_remove(slist,key)
+ void *H5SL_less(slist,key)
H5SL_t *slist; IN/OUT: Pointer to skip list
- void *key; IN: Key for item to remove
+ void *key; IN: Key for item to search for
RETURNS
- Returns pointer to item removed on success, NULL on failure.
+ Returns pointer to item who key is less than or equal to 'key' on success,
+ NULL on failure
DESCRIPTION
- Remove element from a skip list.
+ Search for an object in a skip list, according to it's key, returning the
+ object itself (for an exact match), or the object with the next highest
+ key that is less than 'key'
GLOBAL VARIABLES
COMMENTS, BUGS, ASSUMPTIONS
EXAMPLES
REVISION LOG
--------------------------------------------------------------------------*/
void *
-H5SL_remove(H5SL_t *slist, const void *key)
+H5SL_less(H5SL_t *slist, const void *key)
{
- H5SL_node_t **update[H5SL_LEVEL_MAX]; /* 'update' vector */
H5SL_node_t *checked; /* Pointer to last node checked */
H5SL_node_t *x; /* Current node to examine */
int i; /* Local index value */
- void *ret_value=NULL; /* Return value */
+ void *ret_value; /* Return value */
- FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_remove);
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_less);
/* Check args */
assert(slist);
@@ -586,33 +908,127 @@ H5SL_remove(H5SL_t *slist, const void *key)
/* Check internal consistency */
/* (Pre-condition) */
- /* Remove item from skip list */
+ /* Insert item into skip list */
/* Work through the forward pointers for a node, finding the node at each
- * level that is before the location to remove
+ * level that is before the location to insert
*/
x=slist->header;
switch(slist->type) {
case H5SL_TYPE_INT:
- H5SL_REMOVE(SCALAR,slist,x,update,i,const int,-,key,checked)
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const int,-,key,checked)
break;
case H5SL_TYPE_HADDR:
- H5SL_REMOVE(SCALAR,slist,x,update,i,const haddr_t,-,key,checked)
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const haddr_t,-,key,checked)
break;
case H5SL_TYPE_STR:
- H5SL_REMOVE(STRING,slist,x,update,i,char *,-,key,checked)
+ H5SL_SEARCH(STRING,slist,x,-,i,char *,-,key,checked)
break;
case H5SL_TYPE_HSIZE:
- H5SL_REMOVE(SCALAR,slist,x,update,i,const hsize_t,-,key,checked)
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const hsize_t,-,key,checked)
+ break;
+
+ case H5SL_TYPE_UNSIGNED:
+ H5SL_SEARCH(SCALAR,slist,x,-,i,const unsigned,-,key,checked)
break;
} /* end switch */
+ /* An exact match for 'key' must not have been found in list, if we get here */
+ /* Check for a node with a key that is less than the given 'key' */
+ if(x==NULL) {
+ /* Check for walking off the list */
+ if(slist->last!=slist->header)
+ ret_value=slist->last->item;
+ else
+ ret_value=NULL;
+ } /* end if */
+ else {
+ if(x->backward!=slist->header)
+ ret_value=x->backward->item;
+ else
+ ret_value=NULL;
+ } /* end else */
+
done:
FUNC_LEAVE_NOAPI(ret_value);
-} /* end H5SL_remove() */
+} /* end H5SL_less() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_find
+ PURPOSE
+ Search for _node_ in a skip list
+ USAGE
+ H5SL_node_t *H5SL_node(slist,key)
+ H5SL_t *slist; IN/OUT: Pointer to skip list
+ void *key; IN: Key for item to search for
+
+ RETURNS
+ Returns pointer to _node_ matching key on success, NULL on failure
+ DESCRIPTION
+ Search for an object in a skip list, according to it's key and returns
+ the node that the object is attached to
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ This routine is a useful starting point for next/prev calls
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_find(H5SL_t *slist, const void *key)
+{
+ H5SL_node_t *checked; /* Pointer to last node checked */
+ H5SL_node_t *x; /* Current node to examine */
+ int i; /* Local index value */
+ H5SL_node_t *ret_value; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_find);
+
+ /* Check args */
+ assert(slist);
+ assert(key);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Insert item into skip list */
+
+ /* Work through the forward pointers for a node, finding the node at each
+ * level that is before the location to insert
+ */
+ x=slist->header;
+ switch(slist->type) {
+ case H5SL_TYPE_INT:
+ H5SL_FIND(SCALAR,slist,x,-,i,const int,-,key,checked)
+ break;
+
+ case H5SL_TYPE_HADDR:
+ H5SL_FIND(SCALAR,slist,x,-,i,const haddr_t,-,key,checked)
+ break;
+
+ case H5SL_TYPE_STR:
+ H5SL_FIND(STRING,slist,x,-,i,char *,-,key,checked)
+ break;
+
+ case H5SL_TYPE_HSIZE:
+ H5SL_FIND(SCALAR,slist,x,-,i,const hsize_t,-,key,checked)
+ break;
+
+ case H5SL_TYPE_UNSIGNED:
+ H5SL_FIND(SCALAR,slist,x,-,i,const unsigned,-,key,checked)
+ break;
+ } /* end switch */
+
+ /* 'key' must not have been found in list, if we get here */
+ ret_value=NULL;
+
+done:
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_find() */
/*--------------------------------------------------------------------------
@@ -685,6 +1101,76 @@ H5SL_next(H5SL_node_t *slist_node)
/*--------------------------------------------------------------------------
NAME
+ H5SL_prev
+ PURPOSE
+ Gets a pointer to the previos node in a skip list
+ USAGE
+ H5SL_node_t *H5SL_prev(slist_node)
+ H5SL_node_t *slist_node; IN: Pointer to skip list node
+
+ RETURNS
+ Returns pointer to node before slist_node in skip list on success, NULL on failure.
+ DESCRIPTION
+ Retrieves a pointer to the previous node in a skip list, for iterating over
+ the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_prev(H5SL_node_t *slist_node)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_prev);
+
+ /* Check args */
+ assert(slist_node);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Walk backward, detecting the header node (which has it's key set to NULL) */
+ FUNC_LEAVE_NOAPI(slist_node->backward->key==NULL ? NULL : slist_node->backward);
+} /* end H5SL_prev() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_last
+ PURPOSE
+ Gets a pointer to the lsat node in a skip list
+ USAGE
+ H5SL_node_t *H5SL_last(slist)
+ H5SL_t *slist; IN: Pointer to skip list
+
+ RETURNS
+ Returns pointer to last node in skip list on success, NULL on failure.
+ DESCRIPTION
+ Retrieves a pointer to the last node in a skip list, for iterating over
+ the list.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+H5SL_node_t *
+H5SL_last(H5SL_t *slist)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_last);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Find last node, avoiding the header node */
+ FUNC_LEAVE_NOAPI(slist->last==slist->header ? NULL : slist->last);
+} /* end H5SL_last() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
H5SL_item
PURPOSE
Gets pointer to the 'item' for a skip list node
@@ -794,15 +1280,13 @@ H5SL_iterate(H5SL_t *slist, H5SL_operator_t op, void *op_data)
nodes are not deallocated.
GLOBAL VARIABLES
COMMENTS, BUGS, ASSUMPTIONS
+ The skip list itself is still valid, it just has all its nodes removed.
EXAMPLES
REVISION LOG
--------------------------------------------------------------------------*/
herr_t
H5SL_release(H5SL_t *slist)
{
- H5SL_node_t *node, *next_node; /* Pointers to skip list nodes */
- size_t u; /* Local index variable */
-
FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_release);
/* Check args */
@@ -812,23 +1296,102 @@ H5SL_release(H5SL_t *slist)
/* (Pre-condition) */
/* Free skip list nodes */
- node=slist->header->forward[0];
- while(node!=NULL) {
- next_node=node->forward[0];
- H5MM_xfree(node);
- node=next_node;
- } /* end while */
+ H5SL_release_common(slist,NULL,NULL); /* always succeeds */
- /* Reset the header pointers */
- for(u=0; u<slist->max_level; u++)
- slist->header->forward[u]=NULL;
+ FUNC_LEAVE_NOAPI(SUCCEED);
+} /* end H5SL_release() */
- /* Reset the dynamic internal fields */
- slist->curr_level=-1;
- slist->nobjs=0;
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_free
+ PURPOSE
+ Release all nodes from a skip list, freeing all nodes
+ USAGE
+ herr_t H5SL_free(slist,op,op_data)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to release nodes
+ H5SL_operator_t op; IN: Callback function to free item & key
+ void *op_data; IN/OUT: Pointer to application data for callback
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Release all the nodes in a skip list. Any objects left in
+ the skip list have the 'op' routine called for each.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ The skip list itself is still valid, it just has all its nodes removed.
+
+ The return value from the 'op' routine is ignored.
+
+ This routine is essentially a combination of iterating over all the nodes
+ (where the iterator callback is supposed to free the items and/or keys)
+ followed by a call to H5SL_release().
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_free(H5SL_t *slist, H5SL_operator_t op, void *op_data)
+{
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_free);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Free skip list nodes */
+ H5SL_release_common(slist,op,op_data); /* always succeeds */
FUNC_LEAVE_NOAPI(SUCCEED);
-} /* end H5SL_release() */
+} /* end H5SL_free() */
+
+
+/*--------------------------------------------------------------------------
+ NAME
+ H5SL_destroy
+ PURPOSE
+ Close a skip list, deallocating it and freeing all its nodes.
+ USAGE
+ herr_t H5SL_destroy(slist,op,opdata)
+ H5SL_t *slist; IN/OUT: Pointer to skip list to close
+ H5SL_operator_t op; IN: Callback function to free item & key
+ void *op_data; IN/OUT: Pointer to application data for callback
+
+ RETURNS
+ Returns non-negative on success, negative on failure.
+ DESCRIPTION
+ Close a skip list, freeing all internal information. Any objects left in
+ the skip list have the 'op' routine called for each.
+ GLOBAL VARIABLES
+ COMMENTS, BUGS, ASSUMPTIONS
+ The return value from the 'op' routine is ignored.
+
+ This routine is essentially a combination of iterating over all the nodes
+ (where the iterator callback is supposed to free the items and/or keys)
+ followed by a call to H5SL_close().
+ EXAMPLES
+ REVISION LOG
+--------------------------------------------------------------------------*/
+herr_t
+H5SL_destroy(H5SL_t *slist, H5SL_operator_t op, void *op_data)
+{
+ herr_t ret_value=SUCCEED; /* Return value */
+
+ FUNC_ENTER_NOAPI_NOINIT_NOFUNC(H5SL_destroy);
+
+ /* Check args */
+ assert(slist);
+
+ /* Check internal consistency */
+ /* (Pre-condition) */
+
+ /* Close skip list */
+ (void)H5SL_close_common(slist,op,op_data); /* always succeeds */
+
+ FUNC_LEAVE_NOAPI(ret_value);
+} /* end H5SL_destroy() */
/*--------------------------------------------------------------------------
@@ -861,14 +1424,8 @@ H5SL_close(H5SL_t *slist)
/* Check internal consistency */
/* (Pre-condition) */
- /* Free skip list nodes */
- H5SL_release(slist); /* always succeeds */
-
- /* Release header node */
- H5MM_xfree(slist->header);
-
- /* Free skip list object */
- H5FL_FREE(H5SL_t,slist);
+ /* Close skip list */
+ (void)H5SL_close_common(slist,NULL,NULL); /* always succeeds */
FUNC_LEAVE_NOAPI(SUCCEED);
} /* end H5SL_close() */