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 next element in the skip list.
 157  * @param sl The skip list
 158  * @param iter On entry, a pointer to the skip list node to start with; on return,
 159  * a pointer to the skip list node representing the element returned
 160  * @remark If iter points to a NULL value on entry, NULL will be returned.
 161  */
 162 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
 163
 164 /**
 165  * Return the previous element in the skip list.
 166  * @param sl The skip list
 167  * @param iter On entry, a pointer to the skip list node to start with; on return,
 168  * a pointer to the skip list node representing the element returned
 169  * @remark If iter points to a NULL value on entry, NULL will be returned.
 170  */
 171 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
 172
 173 /**
 174  * Insert an element into the skip list using the specified comparison function.
 175  * @param sl The skip list
 176  * @param data The element to insert
 177  * @param comp The comparison function to use for placement into the skip list
 178  */
 179 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
 180                                           void *data, apr_skiplist_compare comp);
 181
 182 /**
 183  * Insert an element into the skip list using the existing comparison function.
 184  * @param sl The skip list
 185  * @param data The element to insert
 186  * @remark If no comparison function has been set for the skip list, the element
 187  * will not be inserted and NULL will be returned.
 188  */
 189 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
 190
 191 /**
 192  * Remove an element from the skip list using the specified comparison function for
 193  * locating the element.
 194  * @param sl The skip list
 195  * @param data The element to remove
 196  * @param myfree A function to be called for each removed element
 197  * @param comp The comparison function to use for placement into the skip list
 198  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
 199  * will be returned.
 200  */
 201 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
 202                                apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
 203
 204 /**
 205  * Remove an element from the skip list using the existing comparison function for
 206  * locating the element.
 207  * @param sl The skip list
 208  * @param data The element to remove
 209  * @param myfree A function to be called for each removed element
 210  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
 211  * will be returned.
 212  * @remark If no comparison function has been set for the skip list, the element
 213  * will not be removed and 0 will be returned.
 214  */
 215 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
 216
 217 /**
 218  * Remove all elements from the skip list.
 219  * @param sl The skip list
 220  * @param myfree A function to be called for each removed element
 221  */
 222 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
 223
 224 /**
 225  * Remove each element from the skip list.
 226  * @param sl The skip list
 227  * @param myfree A function to be called for each removed element
 228  */
 229 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
 230
 231 /**
 232  * Return the first element in the skip list, leaving the element in the skip list.
 233  * @param sl The skip list
 234  * @param myfree A function to be called for the removed element
 235  * @remark NULL will be returned if there are no elements
 236  */
 237 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
 238
 239 /**
 240  * Return the first element in the skip list, leaving the element in the skip list.
 241  * @param sl The skip list
 242  * @remark NULL will be returned if there are no elements
 243  */
 244 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
 245
 246 /**
 247  * Merge two skip lists.  XXX SEMANTICS
 248  * @param sl1 One of two skip lists to be merged
 249  * @param sl2 The other of two skip lists to be merged
 250  */
 251 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
 252
 253 /** @} */
 254
 255 #ifdef __cplusplus
 256 }
 257 #endif
 258
 259 #endif /* ! APR_SKIPLIST_H */