Apache Portable Runtime
|
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 */