1/* Licensed to the Apache Software Foundation (ASF) under one or more 2 * contributor license agreements. See the NOTICE file distributed with 3 * this work for additional information regarding copyright ownership. 4 * The ASF licenses this file to You under the Apache License, Version 2.0 5 * (the "License"); you may not use this file except in compliance with 6 * the License. You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17#ifndef APR_SKIPLIST_H 18#define APR_SKIPLIST_H 19/** 20 * @file apr_skiplist.h 21 * @brief APR skip list implementation 22 */ 23 24#include "apr.h" 25#include "apr_portable.h" 26#include <stdlib.h> 27 28#ifdef __cplusplus 29extern "C" { 30#endif /* __cplusplus */ 31 32/** 33 * @defgroup apr_skiplist Skip list implementation 34 * Refer to http://en.wikipedia.org/wiki/Skip_list for information 35 * about the purpose of and ideas behind skip lists. 36 * @ingroup APR 37 * @{ 38 */ 39 40/** 41 * apr_skiplist_compare is the function type that must be implemented 42 * per object type that is used in a skip list for comparisons to maintain 43 * order 44 * */ 45typedef int (*apr_skiplist_compare) (void *, void *); 46 47/** 48 * apr_skiplist_freefunc is the function type that must be implemented 49 * to handle elements as they are removed from a skip list. 50 */ 51typedef void (*apr_skiplist_freefunc) (void *); 52 53/** Opaque structure used to represent the skip list */ 54struct apr_skiplist; 55/** Opaque structure used to represent the skip list */ 56typedef struct apr_skiplist apr_skiplist; 57 58/** 59 * Opaque structure used to represent abstract nodes in the skip list 60 * (an abstraction above the raw elements which are collected in the 61 * skip list). 62 */ 63struct apr_skiplistnode; 64/** Opaque structure */ 65typedef struct apr_skiplistnode apr_skiplistnode; 66 67/** 68 * Allocate memory using the same mechanism as the skip list. 69 * @param sl The skip list 70 * @param size The amount to allocate 71 * @remark If a pool was provided to apr_skiplist_init(), memory will 72 * be allocated from the pool or from a free list maintained with 73 * the skip list. Otherwise, memory will be allocated using the 74 * C standard library heap functions. 75 */ 76APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 77 78/** 79 * Free memory using the same mechanism as the skip list. 80 * @param sl The skip list 81 * @param mem The object to free 82 * @remark If a pool was provided to apr_skiplist_init(), memory will 83 * be added to a free list maintained with the skip list and be available 84 * to operations on the skip list or to other calls to apr_skiplist_alloc(). 85 * Otherwise, memory will be freed using the C standard library heap 86 * functions. 87 */ 88APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 89 90/** 91 * Allocate a new skip list 92 * @param sl The pointer in which to return the newly created skip list 93 * @param p The pool from which to allocate the skip list (optional). 94 * @remark Unlike most APR functions, a pool is optional. If no pool 95 * is provided, the C standard library heap functions will be used instead. 96 */ 97APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 98 99/** 100 * Set the comparison functions to be used for searching the skip list. 101 * @param sl The skip list 102 * @param XXX1 FIXME 103 * @param XXX2 FIXME 104 * 105 * @remark If existing comparison functions are being replaced, the index 106 * will be replaced during this call. That is a potentially expensive 107 * operation. 108 */ 109APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 110 apr_skiplist_compare XXX2); 111 112/** 113 * Set the indexing functions to the specified comparison functions and 114 * rebuild the index. 115 * @param sl The skip list 116 * @param XXX1 FIXME 117 * @param XXX2 FIXME 118 * 119 * @remark If an index already exists, it will not be replaced and the 120 * comparison functions will not be changed. 121 */ 122APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 123 apr_skiplist_compare XXX2); 124 125/** 126 * Return the list maintained by the skip list abstraction. 127 * @param sl The skip list 128 */ 129APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 130 131/** 132 * Return the next matching element in the skip list using the specified 133 * comparison function. 134 * @param sl The skip list 135 * @param data The value to search for 136 * @param iter A pointer to the returned skip list node representing the element 137 * found 138 * @param func The comparison function to use 139 */ 140APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 141 void *data, 142 apr_skiplistnode **iter, 143 apr_skiplist_compare func); 144 145/** 146 * Return the next matching element in the skip list using the current comparison 147 * function. 148 * @param sl The skip list 149 * @param data The value to search for 150 * @param iter A pointer to the returned skip list node representing the element 151 * found 152 */ 153APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 154 155/** 156 * Return the last matching element in the skip list using the specified 157 * comparison function. 158 * @param sl The skip list 159 * @param data The value to search for 160 * @param iter A pointer to the returned skip list node representing the element 161 * found 162 * @param comp The comparison function to use 163 */ 164APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, 165 apr_skiplistnode **iter, 166 apr_skiplist_compare comp); 167 168/** 169 * Return the last matching element in the skip list using the current comparison 170 * function. 171 * @param sl The skip list 172 * @param data The value to search for 173 * @param iter A pointer to the returned skip list node representing the element 174 * found 175 */ 176APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, 177 apr_skiplistnode **iter); 178 179/** 180 * Return the next element in the skip list. 181 * @param sl The skip list 182 * @param iter On entry, a pointer to the skip list node to start with; on return, 183 * a pointer to the skip list node representing the element returned 184 * @remark If iter points to a NULL value on entry, NULL will be returned. 185 */ 186APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 187 188/** 189 * Return the previous element in the skip list. 190 * @param sl The skip list 191 * @param iter On entry, a pointer to the skip list node to start with; on return, 192 * a pointer to the skip list node representing the element returned 193 * @remark If iter points to a NULL value on entry, NULL will be returned. 194 */ 195APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 196 197/** 198 * Return the element of the skip list node 199 * @param iter The skip list node 200 */ 201APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter); 202 203/** 204 * Insert an element into the skip list using the specified comparison function 205 * if it does not already exist. 206 * @param sl The skip list 207 * @param data The element to insert 208 * @param comp The comparison function to use for placement into the skip list 209 */ 210APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 211 void *data, apr_skiplist_compare comp); 212 213/** 214 * Insert an element into the skip list using the existing comparison function 215 * if it does not already exist. 216 * @param sl The skip list 217 * @param data The element to insert 218 * @remark If no comparison function has been set for the skip list, the element 219 * will not be inserted and NULL will be returned. 220 */ 221APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 222 223/** 224 * Add an element into the skip list using the specified comparison function 225 * allowing for duplicates. 226 * @param sl The skip list 227 * @param data The element to add 228 * @param comp The comparison function to use for placement into the skip list 229 */ 230APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, 231 void *data, apr_skiplist_compare comp); 232 233/** 234 * Add an element into the skip list using the existing comparison function 235 * allowing for duplicates. 236 * @param sl The skip list 237 * @param data The element to insert 238 * @remark If no comparison function has been set for the skip list, the element 239 * will not be inserted and NULL will be returned. 240 */ 241APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data); 242 243/** 244 * Add an element into the skip list using the specified comparison function 245 * removing the existing duplicates. 246 * @param sl The skip list 247 * @param data The element to insert 248 * @param comp The comparison function to use for placement into the skip list 249 * @param myfree A function to be called for each removed duplicate 250 * @remark If no comparison function has been set for the skip list, the element 251 * will not be inserted, none will be replaced, and NULL will be returned. 252 */ 253APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, 254 void *data, apr_skiplist_freefunc myfree, 255 apr_skiplist_compare comp); 256 257/** 258 * Add an element into the skip list using the existing comparison function 259 * removing the existing duplicates. 260 * @param sl The skip list 261 * @param data The element to insert 262 * @param myfree A function to be called for each removed duplicate 263 * @remark If no comparison function has been set for the skip list, the element 264 * will not be inserted, none will be replaced, and NULL will be returned. 265 */ 266APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, 267 void *data, apr_skiplist_freefunc myfree); 268 269/** 270 * Remove a node from the skip list. 271 * @param sl The skip list 272 * @param iter The skip list node to remove 273 * @param myfree A function to be called for the removed element 274 */ 275APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl, 276 apr_skiplistnode *iter, 277 apr_skiplist_freefunc myfree); 278 279/** 280 * Remove an element from the skip list using the specified comparison function for 281 * locating the element. In the case of duplicates, the 1st entry will be removed. 282 * @param sl The skip list 283 * @param data The element to remove 284 * @param myfree A function to be called for each removed element 285 * @param comp The comparison function to use for placement into the skip list 286 * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 287 * will be returned. 288 */ 289APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 290 apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 291 292/** 293 * Remove an element from the skip list using the existing comparison function for 294 * locating the element. In the case of duplicates, the 1st entry will be removed. 295 * @param sl The skip list 296 * @param data The element to remove 297 * @param myfree A function to be called for each removed element 298 * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 299 * will be returned. 300 * @remark If no comparison function has been set for the skip list, the element 301 * will not be removed and 0 will be returned. 302 */ 303APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 304 305/** 306 * Remove all elements from the skip list. 307 * @param sl The skip list 308 * @param myfree A function to be called for each removed element 309 */ 310APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 311 312/** 313 * Remove each element from the skip list. 314 * @param sl The skip list 315 * @param myfree A function to be called for each removed element 316 */ 317APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 318 319/** 320 * Return the first element in the skip list, removing the element from the skip list. 321 * @param sl The skip list 322 * @param myfree A function to be called for the removed element 323 * @remark NULL will be returned if there are no elements 324 */ 325APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 326 327/** 328 * Return the first element in the skip list, leaving the element in the skip list. 329 * @param sl The skip list 330 * @remark NULL will be returned if there are no elements 331 */ 332APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 333 334/** 335 * Return the size of the list (number of elements), in O(1). 336 * @param sl The skip list 337 */ 338APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl); 339 340/** 341 * Return the height of the list (number of skip paths), in O(1). 342 * @param sl The skip list 343 */ 344APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl); 345 346/** 347 * Return the predefined maximum height of the skip list. 348 * @param sl The skip list 349 */ 350APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl); 351 352/** 353 * Set a predefined maximum height for the skip list. 354 * @param sl The skip list 355 * @param to The preheight to set, or a nul/negative value to disable. 356 * @remark When a preheight is used, the height of each inserted element is 357 * computed randomly up to this preheight instead of the current skip list's 358 * height plus one used by the default implementation. Using a preheight can 359 * probably ensure more fairness with long living elements (since with an 360 * adaptative height, former elements may have been created with a low height, 361 * hence a longest path to reach them while the skip list grows). On the other 362 * hand, the default behaviour (preheight <= 0) with a growing and decreasing 363 * maximum height is more adaptative/suitable for short living values. 364 * @note Should be called before any insertion/add. 365 */ 366APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to); 367 368/** 369 * Merge two skip lists. XXX SEMANTICS 370 * @param sl1 One of two skip lists to be merged 371 * @param sl2 The other of two skip lists to be merged 372 */ 373APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2); 374 375/** @} */ 376 377#ifdef __cplusplus 378} 379#endif 380 381#endif /* ! APR_SKIPLIST_H */ 382