contrib/apr/include/apr_skiplist.h

   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
  29 extern "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  * */
  45 typedef 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  */
  51 typedef void (*apr_skiplist_freefunc) (void *);
  52
  53 /** Opaque structure used to represent the skip list */
  54 struct apr_skiplist;
  55 /** Opaque structure used to represent the skip list */
  56 typedef 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  */
  63 struct apr_skiplistnode;
  64 /** Opaque structure */
  65 typedef 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  */
  76 APR_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  */
  88 APR_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  */
  97 APR_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  */
 109 APR_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  */
 122 APR_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  */
 129 APR_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  */
 140 APR_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  */
 153 APR_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  */
 164 APR_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  */
 176 APR_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  */
 186 APR_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  */
 195 APR_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  */
 201 APR_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  */
 210 APR_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  */
 221 APR_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  */
 230 APR_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  */
 241 APR_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  */
 253 APR_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  */
 266 APR_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  */
 275 APR_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  */
 289 APR_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  */
 303 APR_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  */
 310 APR_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  */
 317 APR_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  */
 325 APR_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  */
 332 APR_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  */
 338 APR_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  */
 344 APR_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  */
 350 APR_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  */
 366 APR_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  */
 373 APR_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 */