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. A value <0 indicates placement after this node; a value of 0 00044 * indicates collision with this exact node; a value >0 indicates placement 00045 * before this node. 00046 * */ 00047 typedef int (*apr_skiplist_compare) (void *, void *); 00048 00049 /** 00050 * apr_skiplist_freefunc is the function type that must be implemented 00051 * to handle elements as they are removed from a skip list. 00052 */ 00053 typedef void (*apr_skiplist_freefunc) (void *); 00054 00055 /** Opaque structure used to represent the skip list */ 00056 struct apr_skiplist; 00057 /** Opaque structure used to represent the skip list */ 00058 typedef struct apr_skiplist apr_skiplist; 00059 00060 /** 00061 * Opaque structure used to represent abstract nodes in the skip list 00062 * (an abstraction above the raw elements which are collected in the 00063 * skip list). 00064 */ 00065 struct apr_skiplistnode; 00066 /** Opaque structure */ 00067 typedef struct apr_skiplistnode apr_skiplistnode; 00068 00069 /** 00070 * Allocate memory using the same mechanism as the skip list. 00071 * @param sl The skip list 00072 * @param size The amount to allocate 00073 * @remark If a pool was provided to apr_skiplist_init(), memory will 00074 * be allocated from the pool or from a free list maintained with 00075 * the skip list. Otherwise, memory will be allocated using the 00076 * C standard library heap functions. 00077 */ 00078 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 00079 00080 /** 00081 * Free memory using the same mechanism as the skip list. 00082 * @param sl The skip list 00083 * @param mem The object to free 00084 * @remark If a pool was provided to apr_skiplist_init(), memory will 00085 * be added to a free list maintained with the skip list and be available 00086 * to operations on the skip list or to other calls to apr_skiplist_alloc(). 00087 * Otherwise, memory will be freed using the C standard library heap 00088 * functions. 00089 */ 00090 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 00091 00092 /** 00093 * Allocate a new skip list 00094 * @param sl The pointer in which to return the newly created skip list 00095 * @param p The pool from which to allocate the skip list (optional). 00096 * @remark Unlike most APR functions, a pool is optional. If no pool 00097 * is provided, the C standard library heap functions will be used instead. 00098 */ 00099 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 00100 00101 /** 00102 * Set the comparison functions to be used for searching the skip list. 00103 * @param sl The skip list 00104 * @param XXX1 FIXME 00105 * @param XXX2 FIXME 00106 * 00107 * @remark If existing comparison functions are being replaced, the index 00108 * will be replaced during this call. That is a potentially expensive 00109 * operation. 00110 */ 00111 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 00112 apr_skiplist_compare XXX2); 00113 00114 /** 00115 * Set the indexing functions to the specified comparison functions and 00116 * rebuild the index. 00117 * @param sl The skip list 00118 * @param XXX1 FIXME 00119 * @param XXX2 FIXME 00120 * 00121 * @remark If an index already exists, it will not be replaced and the 00122 * comparison functions will not be changed. 00123 */ 00124 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 00125 apr_skiplist_compare XXX2); 00126 00127 /** 00128 * Return the list maintained by the skip list abstraction. 00129 * @param sl The skip list 00130 */ 00131 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 00132 00133 /** 00134 * Return the next matching element in the skip list using the specified 00135 * comparison function. 00136 * @param sl The skip list 00137 * @param data The value to search for 00138 * @param iter A pointer to the returned skip list node representing the element 00139 * found 00140 * @param func The comparison function to use 00141 */ 00142 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 00143 void *data, 00144 apr_skiplistnode **iter, 00145 apr_skiplist_compare func); 00146 00147 /** 00148 * Return the next matching element in the skip list using the current comparison 00149 * function. 00150 * @param sl The skip list 00151 * @param data The value to search for 00152 * @param iter A pointer to the returned skip list node representing the element 00153 * found 00154 */ 00155 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 00156 00157 /** 00158 * Return the next element in the skip list. 00159 * @param sl The skip list 00160 * @param iter On entry, a pointer to the skip list node to start with; on return, 00161 * a pointer to the skip list node representing the element returned 00162 * @remark If iter points to a NULL value on entry, NULL will be returned. 00163 */ 00164 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 00165 00166 /** 00167 * Return the previous element in the skip list. 00168 * @param sl The skip list 00169 * @param iter On entry, a pointer to the skip list node to start with; on return, 00170 * a pointer to the skip list node representing the element returned 00171 * @remark If iter points to a NULL value on entry, NULL will be returned. 00172 */ 00173 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 00174 00175 /** 00176 * Insert an element into the skip list using the specified comparison function 00177 * if it does not already exist. 00178 * @param sl The skip list 00179 * @param data The element to insert 00180 * @param comp The comparison function to use for placement into the skip list 00181 */ 00182 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 00183 void *data, apr_skiplist_compare comp); 00184 00185 /** 00186 * Insert an element into the skip list using the existing comparison function 00187 * if it does not already exist (as determined by the comparison function) 00188 * @param sl The skip list 00189 * @param data The element to insert 00190 * @remark If no comparison function has been set for the skip list, the element 00191 * will not be inserted and NULL will be returned. 00192 */ 00193 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 00194 00195 /** 00196 * Remove an element from the skip list using the specified comparison function for 00197 * locating the element. In the case of duplicates, the 1st entry will be removed. 00198 * @param sl The skip list 00199 * @param data The element to remove 00200 * @param myfree A function to be called for each removed element 00201 * @param comp The comparison function to use for placement into the skip list 00202 * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 00203 * will be returned. 00204 */ 00205 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 00206 apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 00207 00208 /** 00209 * Remove an element from the skip list using the existing comparison function for 00210 * locating the element. In the case of duplicates, the 1st entry will be removed. 00211 * @param sl The skip list 00212 * @param data The element to remove 00213 * @param myfree A function to be called for each removed element 00214 * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 00215 * will be returned. 00216 * @remark If no comparison function has been set for the skip list, the element 00217 * will not be removed and 0 will be returned. 00218 */ 00219 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 00220 00221 /** 00222 * Remove all elements from the skip list. 00223 * @param sl The skip list 00224 * @param myfree A function to be called for each removed element 00225 */ 00226 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 00227 00228 /** 00229 * Remove each element from the skip list. 00230 * @param sl The skip list 00231 * @param myfree A function to be called for each removed element 00232 */ 00233 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 00234 00235 /** 00236 * Return the first element in the skip list, removing the element from the skip list. 00237 * @param sl The skip list 00238 * @param myfree A function to be called for the removed element 00239 * @remark NULL will be returned if there are no elements 00240 */ 00241 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 00242 00243 /** 00244 * Return the first element in the skip list, leaving the element in the skip list. 00245 * @param sl The skip list 00246 * @remark NULL will be returned if there are no elements 00247 */ 00248 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 00249 00250 /** 00251 * Merge two skip lists. XXX SEMANTICS 00252 * @param sl1 One of two skip lists to be merged 00253 * @param sl2 The other of two skip lists to be merged 00254 */ 00255 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2); 00256 00257 /** @} */ 00258 00259 #ifdef __cplusplus 00260 } 00261 #endif 00262 00263 #endif /* ! APR_SKIPLIST_H */