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. 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
* */
47
typedef
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
*/
53
typedef
void (*
apr_skiplist_freefunc
) (
void
*);
54
55
/** Opaque structure used to represent the skip list */
56
struct
apr_skiplist
;
57
/** Opaque structure used to represent the skip list */
58
typedef
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
*/
65
struct
apr_skiplistnode
;
66
/** Opaque structure */
67
typedef
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
*/
78
APR_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
*/
90
APR_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
*/
99
APR_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
*/
111
APR_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
*/
124
APR_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
*/
131
APR_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
*/
142
APR_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
*/
155
APR_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
*/
164
APR_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
*/
173
APR_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
*/
182
APR_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
*/
193
APR_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
*/
205
APR_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
*/
219
APR_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
*/
226
APR_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
*/
233
APR_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
*/
241
APR_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
*/
248
APR_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
*/
255
APR_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 */
Generated on Thu Sep 30 2021 21:18:41 for Apache Portable Runtime by
1.8.1.2