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. A value <0 indicates placement after this node; a value of 0
00044  * indicates collision with this exact node; a value >0 indicates placement
00045  * before this node.
00046  * */
00047 typedef int (*apr_skiplist_compare) (void *, void *);
00048 
00049 /**
00050  * apr_skiplist_freefunc is the function type that must be implemented
00051  * to handle elements as they are removed from a skip list.
00052  */
00053 typedef void (*apr_skiplist_freefunc) (void *);
00054 
00055 /** Opaque structure used to represent the skip list */
00056 struct apr_skiplist;
00057 /** Opaque structure used to represent the skip list */
00058 typedef struct apr_skiplist apr_skiplist;
00059 
00060 /** 
00061  * Opaque structure used to represent abstract nodes in the skip list
00062  * (an abstraction above the raw elements which are collected in the
00063  * skip list).
00064  */
00065 struct apr_skiplistnode;
00066 /** Opaque structure */
00067 typedef struct apr_skiplistnode apr_skiplistnode;
00068 
00069 /**
00070  * Allocate memory using the same mechanism as the skip list.
00071  * @param sl The skip list
00072  * @param size The amount to allocate
00073  * @remark If a pool was provided to apr_skiplist_init(), memory will
00074  * be allocated from the pool or from a free list maintained with
00075  * the skip list.  Otherwise, memory will be allocated using the
00076  * C standard library heap functions.
00077  */
00078 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size);
00079 
00080 /**
00081  * Free memory using the same mechanism as the skip list.
00082  * @param sl The skip list
00083  * @param mem The object to free
00084  * @remark If a pool was provided to apr_skiplist_init(), memory will
00085  * be added to a free list maintained with the skip list and be available
00086  * to operations on the skip list or to other calls to apr_skiplist_alloc().
00087  * Otherwise, memory will be freed using the  C standard library heap
00088  * functions.
00089  */
00090 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem);
00091 
00092 /**
00093  * Allocate a new skip list
00094  * @param sl The pointer in which to return the newly created skip list
00095  * @param p The pool from which to allocate the skip list (optional).
00096  * @remark Unlike most APR functions, a pool is optional.  If no pool
00097  * is provided, the C standard library heap functions will be used instead.
00098  */
00099 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p);
00100 
00101 /**
00102  * Set the comparison functions to be used for searching the skip list.
00103  * @param sl The skip list
00104  * @param XXX1 FIXME
00105  * @param XXX2 FIXME
00106  *
00107  * @remark If existing comparison functions are being replaced, the index
00108  * will be replaced during this call.  That is a potentially expensive
00109  * operation.
00110  */
00111 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1,
00112                              apr_skiplist_compare XXX2);
00113 
00114 /**
00115  * Set the indexing functions to the specified comparison functions and
00116  * rebuild the index.
00117  * @param sl The skip list
00118  * @param XXX1 FIXME
00119  * @param XXX2 FIXME
00120  *
00121  * @remark If an index already exists, it will not be replaced and the
00122  * comparison functions will not be changed.
00123  */
00124 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1,
00125                         apr_skiplist_compare XXX2);
00126 
00127 /**
00128  * Return the list maintained by the skip list abstraction.
00129  * @param sl The skip list
00130  */
00131 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl);
00132 
00133 /**
00134  * Return the next matching element in the skip list using the specified
00135  * comparison function.
00136  * @param sl The skip list
00137  * @param data The value to search for
00138  * @param iter A pointer to the returned skip list node representing the element
00139  * found
00140  * @param func The comparison function to use
00141  */
00142 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl,
00143                                void *data,
00144                                apr_skiplistnode **iter,
00145                                apr_skiplist_compare func);
00146 
00147 /**
00148  * Return the next matching element in the skip list using the current comparison
00149  * function.
00150  * @param sl The skip list
00151  * @param data The value to search for
00152  * @param iter A pointer to the returned skip list node representing the element
00153  * found
00154  */
00155 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
00156 
00157 /**
00158  * Return the next element in the skip list.
00159  * @param sl The skip list
00160  * @param iter On entry, a pointer to the skip list node to start with; on return,
00161  * a pointer to the skip list node representing the element returned
00162  * @remark If iter points to a NULL value on entry, NULL will be returned.
00163  */
00164 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
00165 
00166 /**
00167  * Return the previous element in the skip list.
00168  * @param sl The skip list
00169  * @param iter On entry, a pointer to the skip list node to start with; on return,
00170  * a pointer to the skip list node representing the element returned
00171  * @remark If iter points to a NULL value on entry, NULL will be returned.
00172  */
00173 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
00174 
00175 /**
00176  * Insert an element into the skip list using the specified comparison function
00177  * if it does not already exist.
00178  * @param sl The skip list
00179  * @param data The element to insert
00180  * @param comp The comparison function to use for placement into the skip list
00181  */
00182 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
00183                                           void *data, apr_skiplist_compare comp);
00184 
00185 /**
00186  * Insert an element into the skip list using the existing comparison function
00187  * if it does not already exist (as determined by the comparison function)
00188  * @param sl The skip list
00189  * @param data The element to insert
00190  * @remark If no comparison function has been set for the skip list, the element
00191  * will not be inserted and NULL will be returned.
00192  */
00193 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
00194 
00195 /**
00196  * Remove an element from the skip list using the specified comparison function for
00197  * locating the element. In the case of duplicates, the 1st entry will be removed.
00198  * @param sl The skip list
00199  * @param data The element to remove
00200  * @param myfree A function to be called for each removed element
00201  * @param comp The comparison function to use for placement into the skip list
00202  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00203  * will be returned.
00204  */
00205 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
00206                                apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
00207 
00208 /**
00209  * Remove an element from the skip list using the existing comparison function for
00210  * locating the element. In the case of duplicates, the 1st entry will be removed.
00211  * @param sl The skip list
00212  * @param data The element to remove
00213  * @param myfree A function to be called for each removed element
00214  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00215  * will be returned.
00216  * @remark If no comparison function has been set for the skip list, the element
00217  * will not be removed and 0 will be returned.
00218  */
00219 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
00220 
00221 /**
00222  * Remove all elements from the skip list.
00223  * @param sl The skip list
00224  * @param myfree A function to be called for each removed element
00225  */
00226 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00227 
00228 /**
00229  * Remove each element from the skip list.
00230  * @param sl The skip list
00231  * @param myfree A function to be called for each removed element
00232  */
00233 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00234 
00235 /**
00236  * Return the first element in the skip list, removing the element from the skip list.
00237  * @param sl The skip list
00238  * @param myfree A function to be called for the removed element
00239  * @remark NULL will be returned if there are no elements
00240  */
00241 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00242 
00243 /**
00244  * Return the first element in the skip list, leaving the element in the skip list.
00245  * @param sl The skip list
00246  * @remark NULL will be returned if there are no elements
00247  */
00248 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
00249 
00250 /**
00251  * Merge two skip lists.  XXX SEMANTICS
00252  * @param sl1 One of two skip lists to be merged
00253  * @param sl2 The other of two skip lists to be merged
00254  */
00255 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
00256 
00257 /** @} */
00258 
00259 #ifdef __cplusplus
00260 }
00261 #endif
00262 
00263 #endif /* ! APR_SKIPLIST_H */

Generated on 14 Jul 2016 for Apache Portable Runtime by  doxygen 1.4.7