Apache Portable Runtime
apr_skiplist.h
Go to the documentation of this file.
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 */
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  */
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  */
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  */
123  apr_skiplist_compare XXX2);
124 
125 /**
126  * Return the list maintained by the skip list abstraction.
127  * @param sl The skip list
128  */
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  */
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 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 func The comparison function to use
163  */
164 APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sli, 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  */
176 APR_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  */
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  */
196 
197 /**
198  * Return the element of the skip list node
199  * @param iter The skip list node
200  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
333 
334 /**
335  * Return the size of the list (number of elements), in O(1).
336  * @param sl The skip list
337  */
338 APR_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  */
345 
346 /**
347  * Return the predefined maximum height of the skip list.
348  * @param sl The skip list
349  */
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  */
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  */
374 
375 /** @} */
376 
377 #ifdef __cplusplus
378 }
379 #endif
380 
381 #endif /* ! APR_SKIPLIST_H */
void * apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
apr_skiplistnode * apr_skiplist_replace(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
void apr_skiplist_free(apr_skiplist *sl, void *mem)
void * apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
void * apr_skiplist_peek(apr_skiplist *sl)
void apr_skiplist_set_preheight(apr_skiplist *sl, int to)
apr_skiplistnode * apr_skiplist_replace_compare(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
apr_skiplistnode * apr_skiplist_insert(apr_skiplist *sl, void *data)
void * apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree)
apr_skiplist * apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
struct apr_skiplist apr_skiplist
Definition: apr_skiplist.h:56
struct apr_skiplistnode apr_skiplistnode
Definition: apr_skiplist.h:65
apr_status_t apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p)
void * apr_skiplist_element(apr_skiplistnode *iter)
size_t apr_skiplist_size(const apr_skiplist *sl)
void(* apr_skiplist_freefunc)(void *)
Definition: apr_skiplist.h:51
apr_skiplistnode * apr_skiplist_insert_compare(apr_skiplist *sl, void *data, apr_skiplist_compare comp)
void * apr_skiplist_last_compare(apr_skiplist *sli, void *data, apr_skiplistnode **iter, apr_skiplist_compare comp)
int(* apr_skiplist_compare)(void *, void *)
Definition: apr_skiplist.h:45
void apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, apr_skiplist_compare XXX2)
void * apr_skiplist_last(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
#define APR_DECLARE(type)
Definition: apr.h:500
void * apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
APR Platform Definitions.
apr_skiplistnode * apr_skiplist_add(apr_skiplist *sl, void *data)
void apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
int apr_skiplist_remove_compare(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
void * apr_skiplist_alloc(apr_skiplist *sl, size_t size)
void apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, apr_skiplist_compare XXX2)
int apr_skiplist_height(const apr_skiplist *sl)
void * apr_skiplist_find_compare(apr_skiplist *sl, void *data, apr_skiplistnode **iter, apr_skiplist_compare func)
struct apr_pool_t apr_pool_t
Definition: apr_pools.h:60
int apr_status_t
Definition: apr_errno.h:44
int apr_skiplist_preheight(const apr_skiplist *sl)
int apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
apr_skiplistnode * apr_skiplist_add_compare(apr_skiplist *sl, void *data, apr_skiplist_compare comp)
apr_skiplistnode * apr_skiplist_getlist(apr_skiplist *sl)
int apr_skiplist_remove_node(apr_skiplist *sl, apr_skiplistnode *iter, apr_skiplist_freefunc myfree)
APR Portability Routines.
void apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)