Apache Portable Runtime

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
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 next element in the skip list.
00157  * @param sl The skip list
00158  * @param iter On entry, a pointer to the skip list node to start with; on return,
00159  * a pointer to the skip list node representing the element returned
00160  * @remark If iter points to a NULL value on entry, NULL will be returned.
00161  */
00162 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
00163 
00164 /**
00165  * Return the previous element in the skip list.
00166  * @param sl The skip list
00167  * @param iter On entry, a pointer to the skip list node to start with; on return,
00168  * a pointer to the skip list node representing the element returned
00169  * @remark If iter points to a NULL value on entry, NULL will be returned.
00170  */
00171 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
00172 
00173 /**
00174  * Insert an element into the skip list using the specified comparison function.
00175  * @param sl The skip list
00176  * @param data The element to insert
00177  * @param comp The comparison function to use for placement into the skip list
00178  */
00179 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
00180                                           void *data, apr_skiplist_compare comp);
00181 
00182 /**
00183  * Insert an element into the skip list using the existing comparison function.
00184  * @param sl The skip list
00185  * @param data The element to insert
00186  * @remark If no comparison function has been set for the skip list, the element
00187  * will not be inserted and NULL will be returned.
00188  */
00189 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
00190 
00191 /**
00192  * Remove an element from the skip list using the specified comparison function for
00193  * locating the element.
00194  * @param sl The skip list
00195  * @param data The element to remove
00196  * @param myfree A function to be called for each removed element
00197  * @param comp The comparison function to use for placement into the skip list
00198  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00199  * will be returned.
00200  */
00201 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
00202                                apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
00203 
00204 /**
00205  * Remove an element from the skip list using the existing comparison function for
00206  * locating the element.
00207  * @param sl The skip list
00208  * @param data The element to remove
00209  * @param myfree A function to be called for each removed element
00210  * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
00211  * will be returned.
00212  * @remark If no comparison function has been set for the skip list, the element
00213  * will not be removed and 0 will be returned.
00214  */
00215 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
00216 
00217 /**
00218  * Remove all elements from the skip list.
00219  * @param sl The skip list
00220  * @param myfree A function to be called for each removed element
00221  */
00222 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00223 
00224 /**
00225  * Remove each element from the skip list.
00226  * @param sl The skip list
00227  * @param myfree A function to be called for each removed element
00228  */
00229 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00230 
00231 /**
00232  * Return the first element in the skip list, leaving the element in the skip list.
00233  * @param sl The skip list
00234  * @param myfree A function to be called for the removed element
00235  * @remark NULL will be returned if there are no elements
00236  */
00237 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
00238 
00239 /**
00240  * Return the first element in the skip list, leaving the element in the skip list.
00241  * @param sl The skip list
00242  * @remark NULL will be returned if there are no elements
00243  */
00244 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
00245 
00246 /**
00247  * Merge two skip lists.  XXX SEMANTICS
00248  * @param sl1 One of two skip lists to be merged
00249  * @param sl2 The other of two skip lists to be merged
00250  */
00251 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
00252 
00253 /** @} */
00254 
00255 #ifdef __cplusplus
00256 }
00257 #endif
00258 
00259 #endif /* ! APR_SKIPLIST_H */
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines