diff options
Diffstat (limited to 'include/apr_skiplist.h')
| -rw-r--r-- | include/apr_skiplist.h | 126 |
1 files changed, 122 insertions, 4 deletions
diff --git a/include/apr_skiplist.h b/include/apr_skiplist.h index f56ff22c36d6..eeab10bf9f44 100644 --- a/include/apr_skiplist.h +++ b/include/apr_skiplist.h @@ -40,9 +40,7 @@ extern "C" { /** * apr_skiplist_compare is the function type that must be implemented * per object type that is used in a skip list for comparisons to maintain - * order. A value <0 indicates placement after this node; a value of 0 - * indicates collision with this exact node; a value >0 indicates placement - * before this node. + * order * */ typedef int (*apr_skiplist_compare) (void *, void *); @@ -155,6 +153,30 @@ APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); /** + * Return the last matching element in the skip list using the specified + * comparison function. + * @param sl The skip list + * @param data The value to search for + * @param iter A pointer to the returned skip list node representing the element + * found + * @param comp The comparison function to use + */ +APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp); + +/** + * Return the last matching element in the skip list using the current comparison + * function. + * @param sl The skip list + * @param data The value to search for + * @param iter A pointer to the returned skip list node representing the element + * found + */ +APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, + apr_skiplistnode **iter); + +/** * Return the next element in the skip list. * @param sl The skip list * @param iter On entry, a pointer to the skip list node to start with; on return, @@ -173,6 +195,12 @@ APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter) APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); /** + * Return the element of the skip list node + * @param iter The skip list node + */ +APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter); + +/** * Insert an element into the skip list using the specified comparison function * if it does not already exist. * @param sl The skip list @@ -184,7 +212,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, /** * Insert an element into the skip list using the existing comparison function - * if it does not already exist (as determined by the comparison function) + * if it does not already exist. * @param sl The skip list * @param data The element to insert * @remark If no comparison function has been set for the skip list, the element @@ -193,6 +221,62 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); /** + * Add an element into the skip list using the specified comparison function + * allowing for duplicates. + * @param sl The skip list + * @param data The element to add + * @param comp The comparison function to use for placement into the skip list + */ +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, + void *data, apr_skiplist_compare comp); + +/** + * Add an element into the skip list using the existing comparison function + * allowing for duplicates. + * @param sl The skip list + * @param data The element to insert + * @remark If no comparison function has been set for the skip list, the element + * will not be inserted and NULL will be returned. + */ +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data); + +/** + * Add an element into the skip list using the specified comparison function + * removing the existing duplicates. + * @param sl The skip list + * @param data The element to insert + * @param comp The comparison function to use for placement into the skip list + * @param myfree A function to be called for each removed duplicate + * @remark If no comparison function has been set for the skip list, the element + * will not be inserted, none will be replaced, and NULL will be returned. + */ +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree, + apr_skiplist_compare comp); + +/** + * Add an element into the skip list using the existing comparison function + * removing the existing duplicates. + * @param sl The skip list + * @param data The element to insert + * @param myfree A function to be called for each removed duplicate + * @remark If no comparison function has been set for the skip list, the element + * will not be inserted, none will be replaced, and NULL will be returned. + */ +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree); + +/** + * Remove a node from the skip list. + * @param sl The skip list + * @param iter The skip list node to remove + * @param myfree A function to be called for the removed element + */ +APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl, + apr_skiplistnode *iter, + apr_skiplist_freefunc myfree); + +/** * Remove an element from the skip list using the specified comparison function for * locating the element. In the case of duplicates, the 1st entry will be removed. * @param sl The skip list @@ -248,6 +332,40 @@ APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myf APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); /** + * Return the size of the list (number of elements), in O(1). + * @param sl The skip list + */ +APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl); + +/** + * Return the height of the list (number of skip paths), in O(1). + * @param sl The skip list + */ +APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl); + +/** + * Return the predefined maximum height of the skip list. + * @param sl The skip list + */ +APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl); + +/** + * Set a predefined maximum height for the skip list. + * @param sl The skip list + * @param to The preheight to set, or a nul/negative value to disable. + * @remark When a preheight is used, the height of each inserted element is + * computed randomly up to this preheight instead of the current skip list's + * height plus one used by the default implementation. Using a preheight can + * probably ensure more fairness with long living elements (since with an + * adaptative height, former elements may have been created with a low height, + * hence a longest path to reach them while the skip list grows). On the other + * hand, the default behaviour (preheight <= 0) with a growing and decreasing + * maximum height is more adaptative/suitable for short living values. + * @note Should be called before any insertion/add. + */ +APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to); + +/** * Merge two skip lists. XXX SEMANTICS * @param sl1 One of two skip lists to be merged * @param sl2 The other of two skip lists to be merged |