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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef APR_SKIPLIST_H
18 #define APR_SKIPLIST_H
20 * @file apr_skiplist.h
21 * @brief APR skip list implementation
25 #include "apr_portable.h"
30 #endif /* __cplusplus */
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.
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
45 typedef int (*apr_skiplist_compare) (void *, void *);
48 * apr_skiplist_freefunc is the function type that must be implemented
49 * to handle elements as they are removed from a skip list.
51 typedef void (*apr_skiplist_freefunc) (void *);
53 /** Opaque structure used to represent the skip list */
55 /** Opaque structure used to represent the skip list */
56 typedef struct apr_skiplist apr_skiplist;
59 * Opaque structure used to represent abstract nodes in the skip list
60 * (an abstraction above the raw elements which are collected in the
63 struct apr_skiplistnode;
64 /** Opaque structure */
65 typedef struct apr_skiplistnode apr_skiplistnode;
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.
76 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size);
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
88 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem);
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.
97 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p);
100 * Set the comparison functions to be used for searching the skip list.
101 * @param sl The skip list
105 * @remark If existing comparison functions are being replaced, the index
106 * will be replaced during this call. That is a potentially expensive
109 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1,
110 apr_skiplist_compare XXX2);
113 * Set the indexing functions to the specified comparison functions and
115 * @param sl The skip list
119 * @remark If an index already exists, it will not be replaced and the
120 * comparison functions will not be changed.
122 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1,
123 apr_skiplist_compare XXX2);
126 * Return the list maintained by the skip list abstraction.
127 * @param sl The skip list
129 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl);
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
138 * @param func The comparison function to use
140 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl,
142 apr_skiplistnode **iter,
143 apr_skiplist_compare func);
146 * Return the next matching element in the skip list using the current comparison
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
153 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
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.
162 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
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.
171 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
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
179 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
180 void *data, apr_skiplist_compare comp);
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.
189 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
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
201 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
202 apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
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
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.
215 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
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
222 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
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
229 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
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
237 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
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
244 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
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
251 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
259 #endif /* ! APR_SKIPLIST_H */