Apache Portable Runtime

apr_skiplist.h

Go to the documentation of this file.
00001 /* Licensed to the Apache Software Foundation (ASF) under one or more
00002  * contributor license agreements.  See the NOTICE file distributed with
00003  * this work for additional information regarding copyright ownership.
00004  * The ASF licenses this file to You under the Apache License, Version 2.0
00005  * (the "License"); you may not use this file except in compliance with
00006  * the License.  You may obtain a copy of the License at
00007  *
00008  *     http://www.apache.org/licenses/LICENSE-2.0
00009  *
00010  * Unless required by applicable law or agreed to in writing, software
00011  * distributed under the License is distributed on an "AS IS" BASIS,
00012  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  * See the License for the specific language governing permissions and
00014  * limitations under the License.
00015  */
00016 
00017 #ifndef APR_SKIPLIST_H
00018 #define APR_SKIPLIST_H
00019 /**
00020  * @file apr_skiplist.h
00021  * @brief APR skip list implementation
00022  */
00023 
00024 #include "apr.h"
00025 #include "apr_portable.h"
00026 #include <stdlib.h>
00027 
00028 #ifdef __cplusplus
00029 extern "C" {
00030 #endif /* __cplusplus */
00031 
00032 /**
00033  * @defgroup apr_skiplist Skip list implementation
00034  * Refer to http://en.wikipedia.org/wiki/Skip_list for information
00035  * about the purpose of and ideas behind skip lists.
00036  * @ingroup APR
00037  * @{
00038  */
00039 
00040 /**
00041  * apr_skiplist_compare is the function type that must be implemented 
00042  * per object type that is used in a skip list for comparisons to maintain
00043  * order
00044  * */
00045 typedef int (*apr_skiplist_compare) (void *, void *);
00046 
00047 /**
00048  * apr_skiplist_freefunc is the function type that must be implemented
00049  * to handle elements as they are removed from a skip list.
00050  */
00051 typedef void (*apr_skiplist_freefunc) (void *);
00052 
00053 /** Opaque structure used to represent the skip list */
00054 struct apr_skiplist;
00055 /** Opaque structure used to represent the skip list */
00056 typedef struct apr_skiplist apr_skiplist;
00057 
00058 /** 
00059  * Opaque structure used to represent abstract nodes in the skip list
00060  * (an abstraction above the raw elements which are collected in the
00061  * skip list).
00062  */
00063 struct apr_skiplistnode;
00064 /** Opaque structure */
00065 typedef struct apr_skiplistnode apr_skiplistnode;
00066 
00067 /**
00068  * Allocate memory using the same mechanism as the skip list.
00069  * @param sl The skip list
00070  * @param size The amount to allocate
00071  * @remark If a pool was provided to apr_skiplist_init(), memory will
00072  * be allocated from the pool or from a free list maintained with
00073  * the skip list.  Otherwise, memory will be allocated using the
00074  * C standard library heap functions.
00075  */
00076 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size);
00077 
00078 /**
00079  * Free memory using the same mechanism as the skip list.
00080  * @param sl The skip list
00081  * @param mem The object to free
00082  * @remark If a pool was provided to apr_skiplist_init(), memory will
00083  * be added to a free list maintained with the skip list and be available
00084  * to operations on the skip list or to other calls to apr_skiplist_alloc().
00085  * Otherwise, memory will be freed using the  C standard library heap
00086  * functions.
00087  */
00088 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem);
00089 
00090 /**
00091  * Allocate a new skip list
00092  * @param sl The pointer in which to return the newly created skip list
00093  * @param p The pool from which to allocate the skip list (optional).
00094  * @remark Unlike most APR functions, a pool is optional.  If no pool
00095  * is provided, the C standard library heap functions will be used instead.
00096  */
00097 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p);
00098 
00099 /**
00100  * Set the comparison functions to be used for searching the skip list.
00101  * @param sl The skip list
00102  * @param XXX1 FIXME
00103  * @param XXX2 FIXME
00104  *
00105  * @remark If existing comparison functions are being replaced, the index
00106  * will be replaced during this call.  That is a potentially expensive
00107  * operation.
00108  */
00109 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1,
00110                              apr_skiplist_compare XXX2);
00111 
00112 /**
00113  * Set the indexing functions to the specified comparison functions and
00114  * rebuild the index.
00115  * @param sl The skip list
00116  * @param XXX1 FIXME
00117  * @param XXX2 FIXME
00118  *
00119  * @remark If an index already exists, it will not be replaced and the
00120  * comparison functions will not be changed.
00121  */
00122 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1,
00123                         apr_skiplist_compare XXX2);
00124 
00125 /**
00126  * Return the list maintained by the skip list abstraction.
00127  * @param sl The skip list
00128  */
00129 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl);
00130 
00131 /**
00132  * Return the next matching element in the skip list using the specified
00133  * comparison function.
00134  * @param sl The skip list
00135  * @param data The value to search for
00136  * @param iter A pointer to the returned skip list node representing the element
00137  * found
00138  * @param func The comparison function to use
00139  */
00140 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl,
00141                                void *data,
00142                                apr_skiplistnode **iter,
00143                                apr_skiplist_compare func);
00144 
00145 /**
00146  * Return the next matching element in the skip list using the current comparison
00147  * function.
00148  * @param sl The skip list
00149  * @param data The value to search for
00150  * @param iter A pointer to the returned skip list node representing the element
00151  * found
00152  */
00153 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
00154 
00155 /**
00156  * Return the last matching element in the skip list using the specified
00157  * comparison function.
00158  * @param sl The skip list
00159  * @param data The value to search for
00160  * @param iter A pointer to the returned skip list node representing the element
00161  * found
00162  * @param func The comparison function to use
00163  */
00164 APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sli, void *data,
00165                                               apr_skiplistnode **iter,
00166                                               apr_skiplist_compare comp);
00167 
00168 /**
00169  * Return the last matching element in the skip list using the current comparison
00170  * function.
00171  * @param sl The skip list
00172  * @param data The value to search for
00173  * @param iter A pointer to the returned skip list node representing the element
00174  * found
00175  */
00176 APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
00177                                       apr_skiplistnode **iter);
00178 
00179 /**
00180  * Return the next element in the skip list.
00181  * @param sl The skip list
00182  * @param iter On entry, a pointer to the skip list node to start with; on return,
00183  * a pointer to the skip list node representing the element returned
00184  * @remark If iter points to a NULL value on entry, NULL will be returned.
00185  */
00186 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
00187 
00188 /**
00189  * Return the previous element in the skip list.
00190  * @param sl The skip list
00191  * @param iter On entry, a pointer to the skip list node to start with; on return,
00192  * a pointer to the skip list node representing the element returned
00193  * @remark If iter points to a NULL value on entry, NULL will be returned.
00194  */
00195 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
00196 
00197 /**
00198  * Return the element of the skip list node
00199  * @param iter The skip list node
00200  */
00201 APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter);
00202 
00203 /**
00204  * Insert an element into the skip list using the specified comparison function
00205  * if it does not already exist.
00206  * @param sl The skip list
00207  * @param data The element to insert
00208  * @param comp The comparison function to use for placement into the skip list
00209  */
00210 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
00211                                           void *data, apr_skiplist_compare comp);
00212 
00213 /**
00214  * Insert an element into the skip list using the existing comparison function
00215  * if it does not already exist.
00216  * @param sl The skip list
00217  * @param data The element to insert
00218  * @remark If no comparison function has been set for the skip list, the element
00219  * will not be inserted and NULL will be returned.
00220  */
00221 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
00222 
00223 /**
00224  * Add an element into the skip list using the specified comparison function
00225  * allowing for duplicates.
00226  * @param sl The skip list
00227  * @param data The element to add
00228  * @param comp The comparison function to use for placement into the skip list
00229  */
00230 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl,
00231                                           void *data, apr_skiplist_compare comp);
00232 
00233 /**
00234  * Add an element into the skip list using the existing comparison function
00235  * allowing for duplicates.
00236  * @param sl The skip list
00237  * @param data The element to insert
00238  * @remark If no comparison function has been set for the skip list, the element
00239  * will not be inserted and NULL will be returned.
00240  */
00241 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data);
00242 
00243 /**
00244  * Add an element into the skip list using the specified comparison function
00245  * removing the existing duplicates.
00246  * @param sl The skip list
00247  * @param data The element to insert
00248  * @param comp The comparison function to use for placement into the skip list
00249  * @param myfree A function to be called for each removed duplicate
00250  * @remark If no comparison function has been set for the skip list, the element
00251  * will not be inserted, none will be replaced, and NULL will be returned.
00252  */
00253 APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
00254                                     void *data, apr_skiplist_freefunc myfree,
00255                                     apr_skiplist_compare comp);
00256 
00257 /**
00258  * Add an element into the skip list using the existing comparison function
00259  * removing the existing duplicates.
00260  * @param sl The skip list
00261  * @param data The element to insert
00262  * @param myfree A function to be called for each removed duplicate
00263  * @remark If no comparison function has been set for the skip list, the element
00264  * will not be inserted, none will be replaced, and NULL will be returned.
00265  */
00266 APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
00267                                     void *data, apr_skiplist_freefunc myfree);
00268 
00269 /**
00270  * Remove a node from the skip list.
00271  * @param sl The skip list
00272  * @param iter The skip list node to remove
00273  * @param myfree A function to be called for the removed element
00274  */
00275 APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
00276                                           apr_skiplistnode *iter,
00277                                           apr_skiplist_freefunc myfree);
00278 
00279 /**
00280  * Remove an element from the skip list using the specified comparison function for
00281  * locating the element. In the case of duplicates, the 1st entry will be removed.
00282  * @param sl The skip list
00283  * @param data The element to remove
00284  * @param myfree A function to be called for each removed element
00285  * @param comp The comparison function to use for placement into the skip list
00286  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00287  * will be returned.
00288  */
00289 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
00290                                apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
00291 
00292 /**
00293  * Remove an element from the skip list using the existing comparison function for
00294  * locating the element. In the case of duplicates, the 1st entry will be removed.
00295  * @param sl The skip list
00296  * @param data The element to remove
00297  * @param myfree A function to be called for each removed element
00298  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00299  * will be returned.
00300  * @remark If no comparison function has been set for the skip list, the element
00301  * will not be removed and 0 will be returned.
00302  */
00303 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
00304 
00305 /**
00306  * Remove all elements from the skip list.
00307  * @param sl The skip list
00308  * @param myfree A function to be called for each removed element
00309  */
00310 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00311 
00312 /**
00313  * Remove each element from the skip list.
00314  * @param sl The skip list
00315  * @param myfree A function to be called for each removed element
00316  */
00317 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00318 
00319 /**
00320  * Return the first element in the skip list, removing the element from the skip list.
00321  * @param sl The skip list
00322  * @param myfree A function to be called for the removed element
00323  * @remark NULL will be returned if there are no elements
00324  */
00325 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00326 
00327 /**
00328  * Return the first element in the skip list, leaving the element in the skip list.
00329  * @param sl The skip list
00330  * @remark NULL will be returned if there are no elements
00331  */
00332 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
00333 
00334 /**
00335  * Return the size of the list (number of elements), in O(1).
00336  * @param sl The skip list
00337  */
00338 APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl);
00339 
00340 /**
00341  * Return the height of the list (number of skip paths), in O(1).
00342  * @param sl The skip list
00343  */
00344 APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl);
00345 
00346 /**
00347  * Return the predefined maximum height of the skip list.
00348  * @param sl The skip list
00349  */
00350 APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl);
00351 
00352 /**
00353  * Set a predefined maximum height for the skip list.
00354  * @param sl The skip list
00355  * @param to The preheight to set, or a nul/negative value to disable.
00356  * @remark When a preheight is used, the height of each inserted element is
00357  * computed randomly up to this preheight instead of the current skip list's
00358  * height plus one used by the default implementation. Using a preheight can
00359  * probably ensure more fairness with long living elements (since with an
00360  * adaptative height, former elements may have been created with a low height,
00361  * hence a longest path to reach them while the skip list grows). On the other
00362  * hand, the default behaviour (preheight <= 0) with a growing and decreasing
00363  * maximum height is more adaptative/suitable for short living values.
00364  * @note Should be called before any insertion/add.
00365  */
00366 APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to);
00367 
00368 /**
00369  * Merge two skip lists.  XXX SEMANTICS
00370  * @param sl1 One of two skip lists to be merged
00371  * @param sl2 The other of two skip lists to be merged
00372  */
00373 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
00374 
00375 /** @} */
00376 
00377 #ifdef __cplusplus
00378 }
00379 #endif
00380 
00381 #endif /* ! APR_SKIPLIST_H */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines