Apache Portable Runtime
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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 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.
161  */
163 
164 /**
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.
170  */
172 
173 /**
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
178  */
180  void *data, apr_skiplist_compare comp);
181 
182 /**
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.
188  */
190 
191 /**
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
199  * will be returned.
200  */
203 
204 /**
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
211  * will be returned.
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.
214  */
216 
217 /**
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
221  */
223 
224 /**
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
228  */
230 
231 /**
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
236  */
238 
239 /**
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
243  */
245 
246 /**
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
250  */
252 
253 /** @} */
254 
255 #ifdef __cplusplus
256 }
257 #endif
258 
259 #endif /* ! APR_SKIPLIST_H */