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