Apache Portable Runtime
Main Page
Related Pages
Modules
Data Structures
Files
File List
Globals
All
Data Structures
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Macros
Groups
Pages
include
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 */
65
typedef
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
*/
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
*/
97
APR_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
*/
109
APR_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
*/
122
APR_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
*/
129
APR_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
*/
140
APR_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
*/
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
*/
162
APR_DECLARE
(
void
*)
apr_skiplist_next
(
apr_skiplist
*sl,
apr_skiplistnode
**iter);
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
*/
171
APR_DECLARE
(
void
*)
apr_skiplist_previous
(
apr_skiplist
*sl,
apr_skiplistnode
**iter);
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
*/
179
APR_DECLARE
(
apr_skiplistnode
*)
apr_skiplist_insert_compare
(
apr_skiplist
*sl,
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
*/
189
APR_DECLARE
(
apr_skiplistnode
*)
apr_skiplist_insert
(
apr_skiplist
* sl,
void
*data);
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
*/
201
APR_DECLARE
(
int
)
apr_skiplist_remove_compare
(
apr_skiplist
*sl,
void
*data,
202
apr_skiplist_freefunc
myfree,
apr_skiplist_compare
comp);
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
*/
215
APR_DECLARE
(
int
)
apr_skiplist_remove
(
apr_skiplist
*sl,
void
*data,
apr_skiplist_freefunc
myfree);
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
*/
222
APR_DECLARE
(
void
)
apr_skiplist_remove_all
(
apr_skiplist
*sl,
apr_skiplist_freefunc
myfree);
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
*/
229
APR_DECLARE
(
void
)
apr_skiplist_destroy
(
apr_skiplist
*sl,
apr_skiplist_freefunc
myfree);
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
*/
237
APR_DECLARE
(
void
*)
apr_skiplist_pop
(
apr_skiplist
*sl,
apr_skiplist_freefunc
myfree);
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
*/
244
APR_DECLARE
(
void
*)
apr_skiplist_peek
(
apr_skiplist
*sl);
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
*/
251
APR_DECLARE
(
apr_skiplist
*)
apr_skiplist_merge
(
apr_skiplist
*sl1,
apr_skiplist
*sl2);
252
253
/** @} */
254
255
#ifdef __cplusplus
256
}
257
#endif
258
259
#endif
/* ! APR_SKIPLIST_H */
Generated on Fri Feb 28 2014 18:40:25 for Apache Portable Runtime by
1.8.1.2