apr_skiplist.h revision 286503 
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. A value <0 indicates placement after this node; a value of 0
44 * indicates collision with this exact node; a value >0 indicates placement
45 * before this node.
46 * */
47typedef int (*apr_skiplist_compare) (void *, void *);
48
49/**
50 * apr_skiplist_freefunc is the function type that must be implemented
51 * to handle elements as they are removed from a skip list.
52 */
53typedef void (*apr_skiplist_freefunc) (void *);
54
55/** Opaque structure used to represent the skip list */
56struct apr_skiplist;
57/** Opaque structure used to represent the skip list */
58typedef struct apr_skiplist apr_skiplist;
59
60/**
61 * Opaque structure used to represent abstract nodes in the skip list
62 * (an abstraction above the raw elements which are collected in the
63 * skip list).
64 */
65struct apr_skiplistnode;
66/** Opaque structure */
67typedef struct apr_skiplistnode apr_skiplistnode;
68
69/**
70 * Allocate memory using the same mechanism as the skip list.
71 * @param sl The skip list
72 * @param size The amount to allocate
73 * @remark If a pool was provided to apr_skiplist_init(), memory will
74 * be allocated from the pool or from a free list maintained with
75 * the skip list.  Otherwise, memory will be allocated using the
76 * C standard library heap functions.
77 */
78APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size);
79
80/**
81 * Free memory using the same mechanism as the skip list.
82 * @param sl The skip list
83 * @param mem The object to free
84 * @remark If a pool was provided to apr_skiplist_init(), memory will
85 * be added to a free list maintained with the skip list and be available
86 * to operations on the skip list or to other calls to apr_skiplist_alloc().
87 * Otherwise, memory will be freed using the  C standard library heap
88 * functions.
89 */
90APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem);
91
92/**
93 * Allocate a new skip list
94 * @param sl The pointer in which to return the newly created skip list
95 * @param p The pool from which to allocate the skip list (optional).
96 * @remark Unlike most APR functions, a pool is optional.  If no pool
97 * is provided, the C standard library heap functions will be used instead.
98 */
99APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p);
100
101/**
102 * Set the comparison functions to be used for searching the skip list.
103 * @param sl The skip list
104 * @param XXX1 FIXME
105 * @param XXX2 FIXME
106 *
107 * @remark If existing comparison functions are being replaced, the index
108 * will be replaced during this call.  That is a potentially expensive
109 * operation.
110 */
111APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1,
112                             apr_skiplist_compare XXX2);
113
114/**
115 * Set the indexing functions to the specified comparison functions and
116 * rebuild the index.
117 * @param sl The skip list
118 * @param XXX1 FIXME
119 * @param XXX2 FIXME
120 *
121 * @remark If an index already exists, it will not be replaced and the
122 * comparison functions will not be changed.
123 */
124APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1,
125                        apr_skiplist_compare XXX2);
126
127/**
128 * Return the list maintained by the skip list abstraction.
129 * @param sl The skip list
130 */
131APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl);
132
133/**
134 * Return the next matching element in the skip list using the specified
135 * comparison function.
136 * @param sl The skip list
137 * @param data The value to search for
138 * @param iter A pointer to the returned skip list node representing the element
139 * found
140 * @param func The comparison function to use
141 */
142APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl,
143                               void *data,
144                               apr_skiplistnode **iter,
145                               apr_skiplist_compare func);
146
147/**
148 * Return the next matching element in the skip list using the current comparison
149 * function.
150 * @param sl The skip list
151 * @param data The value to search for
152 * @param iter A pointer to the returned skip list node representing the element
153 * found
154 */
155APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
156
157/**
158 * Return the next element in the skip list.
159 * @param sl The skip list
160 * @param iter On entry, a pointer to the skip list node to start with; on return,
161 * a pointer to the skip list node representing the element returned
162 * @remark If iter points to a NULL value on entry, NULL will be returned.
163 */
164APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter);
165
166/**
167 * Return the previous element in the skip list.
168 * @param sl The skip list
169 * @param iter On entry, a pointer to the skip list node to start with; on return,
170 * a pointer to the skip list node representing the element returned
171 * @remark If iter points to a NULL value on entry, NULL will be returned.
172 */
173APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
174
175/**
176 * Insert an element into the skip list using the specified comparison function
177 * if it does not already exist.
178 * @param sl The skip list
179 * @param data The element to insert
180 * @param comp The comparison function to use for placement into the skip list
181 */
182APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl,
183                                          void *data, apr_skiplist_compare comp);
184
185/**
186 * Insert an element into the skip list using the existing comparison function
187 * if it does not already exist (as determined by the comparison function)
188 * @param sl The skip list
189 * @param data The element to insert
190 * @remark If no comparison function has been set for the skip list, the element
191 * will not be inserted and NULL will be returned.
192 */
193APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
194
195/**
196 * Remove an element from the skip list using the specified comparison function for
197 * locating the element. In the case of duplicates, the 1st entry will be removed.
198 * @param sl The skip list
199 * @param data The element to remove
200 * @param myfree A function to be called for each removed element
201 * @param comp The comparison function to use for placement into the skip list
202 * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
203 * will be returned.
204 */
205APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data,
206                               apr_skiplist_freefunc myfree, apr_skiplist_compare comp);
207
208/**
209 * Remove an element from the skip list using the existing comparison function for
210 * locating the element. In the case of duplicates, the 1st entry will be removed.
211 * @param sl The skip list
212 * @param data The element to remove
213 * @param myfree A function to be called for each removed element
214 * @remark If the element is not found, 0 will be returned.  Otherwise, the heightXXX
215 * will be returned.
216 * @remark If no comparison function has been set for the skip list, the element
217 * will not be removed and 0 will be returned.
218 */
219APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree);
220
221/**
222 * Remove all elements from the skip list.
223 * @param sl The skip list
224 * @param myfree A function to be called for each removed element
225 */
226APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree);
227
228/**
229 * Remove each element from the skip list.
230 * @param sl The skip list
231 * @param myfree A function to be called for each removed element
232 */
233APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree);
234
235/**
236 * Return the first element in the skip list, removing the element from the skip list.
237 * @param sl The skip list
238 * @param myfree A function to be called for the removed element
239 * @remark NULL will be returned if there are no elements
240 */
241APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree);
242
243/**
244 * Return the first element in the skip list, leaving the element in the skip list.
245 * @param sl The skip list
246 * @remark NULL will be returned if there are no elements
247 */
248APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
249
250/**
251 * Merge two skip lists.  XXX SEMANTICS
252 * @param sl1 One of two skip lists to be merged
253 * @param sl2 The other of two skip lists to be merged
254 */
255APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2);
256
257/** @} */
258
259#ifdef __cplusplus
260}
261#endif
262
263#endif /* ! APR_SKIPLIST_H */
264