1266733Speter/* Licensed to the Apache Software Foundation (ASF) under one or more 2266733Speter * contributor license agreements. See the NOTICE file distributed with 3266733Speter * this work for additional information regarding copyright ownership. 4266733Speter * The ASF licenses this file to You under the Apache License, Version 2.0 5266733Speter * (the "License"); you may not use this file except in compliance with 6266733Speter * the License. You may obtain a copy of the License at 7266733Speter * 8266733Speter * http://www.apache.org/licenses/LICENSE-2.0 9266733Speter * 10266733Speter * Unless required by applicable law or agreed to in writing, software 11266733Speter * distributed under the License is distributed on an "AS IS" BASIS, 12266733Speter * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13266733Speter * See the License for the specific language governing permissions and 14266733Speter * limitations under the License. 15266733Speter */ 16266733Speter 17266733Speter#ifndef APR_SKIPLIST_H 18266733Speter#define APR_SKIPLIST_H 19266733Speter/** 20266733Speter * @file apr_skiplist.h 21266733Speter * @brief APR skip list implementation 22266733Speter */ 23266733Speter 24266733Speter#include "apr.h" 25266733Speter#include "apr_portable.h" 26266733Speter#include <stdlib.h> 27266733Speter 28266733Speter#ifdef __cplusplus 29266733Speterextern "C" { 30266733Speter#endif /* __cplusplus */ 31266733Speter 32266733Speter/** 33266733Speter * @defgroup apr_skiplist Skip list implementation 34266733Speter * Refer to http://en.wikipedia.org/wiki/Skip_list for information 35266733Speter * about the purpose of and ideas behind skip lists. 36266733Speter * @ingroup APR 37266733Speter * @{ 38266733Speter */ 39266733Speter 40266733Speter/** 41266733Speter * apr_skiplist_compare is the function type that must be implemented 42266733Speter * per object type that is used in a skip list for comparisons to maintain 43362181Sdim * order 44266733Speter * */ 45266733Spetertypedef int (*apr_skiplist_compare) (void *, void *); 46266733Speter 47266733Speter/** 48266733Speter * apr_skiplist_freefunc is the function type that must be implemented 49266733Speter * to handle elements as they are removed from a skip list. 50266733Speter */ 51266733Spetertypedef void (*apr_skiplist_freefunc) (void *); 52266733Speter 53266733Speter/** Opaque structure used to represent the skip list */ 54266733Speterstruct apr_skiplist; 55266733Speter/** Opaque structure used to represent the skip list */ 56266733Spetertypedef struct apr_skiplist apr_skiplist; 57266733Speter 58266733Speter/** 59266733Speter * Opaque structure used to represent abstract nodes in the skip list 60266733Speter * (an abstraction above the raw elements which are collected in the 61266733Speter * skip list). 62266733Speter */ 63266733Speterstruct apr_skiplistnode; 64266733Speter/** Opaque structure */ 65266733Spetertypedef struct apr_skiplistnode apr_skiplistnode; 66266733Speter 67266733Speter/** 68266733Speter * Allocate memory using the same mechanism as the skip list. 69266733Speter * @param sl The skip list 70266733Speter * @param size The amount to allocate 71266733Speter * @remark If a pool was provided to apr_skiplist_init(), memory will 72266733Speter * be allocated from the pool or from a free list maintained with 73266733Speter * the skip list. Otherwise, memory will be allocated using the 74266733Speter * C standard library heap functions. 75266733Speter */ 76266733SpeterAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 77266733Speter 78266733Speter/** 79266733Speter * Free memory using the same mechanism as the skip list. 80266733Speter * @param sl The skip list 81266733Speter * @param mem The object to free 82266733Speter * @remark If a pool was provided to apr_skiplist_init(), memory will 83266733Speter * be added to a free list maintained with the skip list and be available 84266733Speter * to operations on the skip list or to other calls to apr_skiplist_alloc(). 85266733Speter * Otherwise, memory will be freed using the C standard library heap 86266733Speter * functions. 87266733Speter */ 88266733SpeterAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 89266733Speter 90266733Speter/** 91266733Speter * Allocate a new skip list 92266733Speter * @param sl The pointer in which to return the newly created skip list 93266733Speter * @param p The pool from which to allocate the skip list (optional). 94266733Speter * @remark Unlike most APR functions, a pool is optional. If no pool 95266733Speter * is provided, the C standard library heap functions will be used instead. 96266733Speter */ 97266733SpeterAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 98266733Speter 99266733Speter/** 100266733Speter * Set the comparison functions to be used for searching the skip list. 101266733Speter * @param sl The skip list 102266733Speter * @param XXX1 FIXME 103266733Speter * @param XXX2 FIXME 104266733Speter * 105266733Speter * @remark If existing comparison functions are being replaced, the index 106266733Speter * will be replaced during this call. That is a potentially expensive 107266733Speter * operation. 108266733Speter */ 109266733SpeterAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 110266733Speter apr_skiplist_compare XXX2); 111266733Speter 112266733Speter/** 113266733Speter * Set the indexing functions to the specified comparison functions and 114266733Speter * rebuild the index. 115266733Speter * @param sl The skip list 116266733Speter * @param XXX1 FIXME 117266733Speter * @param XXX2 FIXME 118266733Speter * 119266733Speter * @remark If an index already exists, it will not be replaced and the 120266733Speter * comparison functions will not be changed. 121266733Speter */ 122266733SpeterAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 123266733Speter apr_skiplist_compare XXX2); 124266733Speter 125266733Speter/** 126266733Speter * Return the list maintained by the skip list abstraction. 127266733Speter * @param sl The skip list 128266733Speter */ 129266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 130266733Speter 131266733Speter/** 132266733Speter * Return the next matching element in the skip list using the specified 133266733Speter * comparison function. 134266733Speter * @param sl The skip list 135266733Speter * @param data The value to search for 136266733Speter * @param iter A pointer to the returned skip list node representing the element 137266733Speter * found 138266733Speter * @param func The comparison function to use 139266733Speter */ 140266733SpeterAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 141266733Speter void *data, 142266733Speter apr_skiplistnode **iter, 143266733Speter apr_skiplist_compare func); 144266733Speter 145266733Speter/** 146266733Speter * Return the next matching element in the skip list using the current comparison 147266733Speter * function. 148266733Speter * @param sl The skip list 149266733Speter * @param data The value to search for 150266733Speter * @param iter A pointer to the returned skip list node representing the element 151266733Speter * found 152266733Speter */ 153266733SpeterAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 154266733Speter 155266733Speter/** 156362181Sdim * Return the last matching element in the skip list using the specified 157362181Sdim * comparison function. 158362181Sdim * @param sl The skip list 159362181Sdim * @param data The value to search for 160362181Sdim * @param iter A pointer to the returned skip list node representing the element 161362181Sdim * found 162362181Sdim * @param comp The comparison function to use 163362181Sdim */ 164362181SdimAPR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, 165362181Sdim apr_skiplistnode **iter, 166362181Sdim apr_skiplist_compare comp); 167362181Sdim 168362181Sdim/** 169362181Sdim * Return the last matching element in the skip list using the current comparison 170362181Sdim * function. 171362181Sdim * @param sl The skip list 172362181Sdim * @param data The value to search for 173362181Sdim * @param iter A pointer to the returned skip list node representing the element 174362181Sdim * found 175362181Sdim */ 176362181SdimAPR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, 177362181Sdim apr_skiplistnode **iter); 178362181Sdim 179362181Sdim/** 180266733Speter * Return the next element in the skip list. 181266733Speter * @param sl The skip list 182266733Speter * @param iter On entry, a pointer to the skip list node to start with; on return, 183266733Speter * a pointer to the skip list node representing the element returned 184266733Speter * @remark If iter points to a NULL value on entry, NULL will be returned. 185266733Speter */ 186266733SpeterAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 187266733Speter 188266733Speter/** 189266733Speter * Return the previous element in the skip list. 190266733Speter * @param sl The skip list 191266733Speter * @param iter On entry, a pointer to the skip list node to start with; on return, 192266733Speter * a pointer to the skip list node representing the element returned 193266733Speter * @remark If iter points to a NULL value on entry, NULL will be returned. 194266733Speter */ 195266733SpeterAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 196266733Speter 197266733Speter/** 198362181Sdim * Return the element of the skip list node 199362181Sdim * @param iter The skip list node 200362181Sdim */ 201362181SdimAPR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter); 202362181Sdim 203362181Sdim/** 204286503Speter * Insert an element into the skip list using the specified comparison function 205286503Speter * if it does not already exist. 206266733Speter * @param sl The skip list 207266733Speter * @param data The element to insert 208266733Speter * @param comp The comparison function to use for placement into the skip list 209266733Speter */ 210266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 211266733Speter void *data, apr_skiplist_compare comp); 212266733Speter 213266733Speter/** 214286503Speter * Insert an element into the skip list using the existing comparison function 215362181Sdim * if it does not already exist. 216266733Speter * @param sl The skip list 217266733Speter * @param data The element to insert 218266733Speter * @remark If no comparison function has been set for the skip list, the element 219266733Speter * will not be inserted and NULL will be returned. 220266733Speter */ 221266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 222266733Speter 223266733Speter/** 224362181Sdim * Add an element into the skip list using the specified comparison function 225362181Sdim * allowing for duplicates. 226362181Sdim * @param sl The skip list 227362181Sdim * @param data The element to add 228362181Sdim * @param comp The comparison function to use for placement into the skip list 229362181Sdim */ 230362181SdimAPR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, 231362181Sdim void *data, apr_skiplist_compare comp); 232362181Sdim 233362181Sdim/** 234362181Sdim * Add an element into the skip list using the existing comparison function 235362181Sdim * allowing for duplicates. 236362181Sdim * @param sl The skip list 237362181Sdim * @param data The element to insert 238362181Sdim * @remark If no comparison function has been set for the skip list, the element 239362181Sdim * will not be inserted and NULL will be returned. 240362181Sdim */ 241362181SdimAPR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data); 242362181Sdim 243362181Sdim/** 244362181Sdim * Add an element into the skip list using the specified comparison function 245362181Sdim * removing the existing duplicates. 246362181Sdim * @param sl The skip list 247362181Sdim * @param data The element to insert 248362181Sdim * @param comp The comparison function to use for placement into the skip list 249362181Sdim * @param myfree A function to be called for each removed duplicate 250362181Sdim * @remark If no comparison function has been set for the skip list, the element 251362181Sdim * will not be inserted, none will be replaced, and NULL will be returned. 252362181Sdim */ 253362181SdimAPR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, 254362181Sdim void *data, apr_skiplist_freefunc myfree, 255362181Sdim apr_skiplist_compare comp); 256362181Sdim 257362181Sdim/** 258362181Sdim * Add an element into the skip list using the existing comparison function 259362181Sdim * removing the existing duplicates. 260362181Sdim * @param sl The skip list 261362181Sdim * @param data The element to insert 262362181Sdim * @param myfree A function to be called for each removed duplicate 263362181Sdim * @remark If no comparison function has been set for the skip list, the element 264362181Sdim * will not be inserted, none will be replaced, and NULL will be returned. 265362181Sdim */ 266362181SdimAPR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, 267362181Sdim void *data, apr_skiplist_freefunc myfree); 268362181Sdim 269362181Sdim/** 270362181Sdim * Remove a node from the skip list. 271362181Sdim * @param sl The skip list 272362181Sdim * @param iter The skip list node to remove 273362181Sdim * @param myfree A function to be called for the removed element 274362181Sdim */ 275362181SdimAPR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl, 276362181Sdim apr_skiplistnode *iter, 277362181Sdim apr_skiplist_freefunc myfree); 278362181Sdim 279362181Sdim/** 280266733Speter * Remove an element from the skip list using the specified comparison function for 281286503Speter * locating the element. In the case of duplicates, the 1st entry will be removed. 282266733Speter * @param sl The skip list 283266733Speter * @param data The element to remove 284266733Speter * @param myfree A function to be called for each removed element 285266733Speter * @param comp The comparison function to use for placement into the skip list 286266733Speter * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 287266733Speter * will be returned. 288266733Speter */ 289266733SpeterAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 290266733Speter apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 291266733Speter 292266733Speter/** 293266733Speter * Remove an element from the skip list using the existing comparison function for 294286503Speter * locating the element. In the case of duplicates, the 1st entry will be removed. 295266733Speter * @param sl The skip list 296266733Speter * @param data The element to remove 297266733Speter * @param myfree A function to be called for each removed element 298266733Speter * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 299266733Speter * will be returned. 300266733Speter * @remark If no comparison function has been set for the skip list, the element 301266733Speter * will not be removed and 0 will be returned. 302266733Speter */ 303266733SpeterAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 304266733Speter 305266733Speter/** 306266733Speter * Remove all elements from the skip list. 307266733Speter * @param sl The skip list 308266733Speter * @param myfree A function to be called for each removed element 309266733Speter */ 310266733SpeterAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 311266733Speter 312266733Speter/** 313266733Speter * Remove each element from the skip list. 314266733Speter * @param sl The skip list 315266733Speter * @param myfree A function to be called for each removed element 316266733Speter */ 317266733SpeterAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 318266733Speter 319266733Speter/** 320286503Speter * Return the first element in the skip list, removing the element from the skip list. 321266733Speter * @param sl The skip list 322266733Speter * @param myfree A function to be called for the removed element 323266733Speter * @remark NULL will be returned if there are no elements 324266733Speter */ 325266733SpeterAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 326266733Speter 327266733Speter/** 328266733Speter * Return the first element in the skip list, leaving the element in the skip list. 329266733Speter * @param sl The skip list 330266733Speter * @remark NULL will be returned if there are no elements 331266733Speter */ 332266733SpeterAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 333266733Speter 334266733Speter/** 335362181Sdim * Return the size of the list (number of elements), in O(1). 336362181Sdim * @param sl The skip list 337362181Sdim */ 338362181SdimAPR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl); 339362181Sdim 340362181Sdim/** 341362181Sdim * Return the height of the list (number of skip paths), in O(1). 342362181Sdim * @param sl The skip list 343362181Sdim */ 344362181SdimAPR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl); 345362181Sdim 346362181Sdim/** 347362181Sdim * Return the predefined maximum height of the skip list. 348362181Sdim * @param sl The skip list 349362181Sdim */ 350362181SdimAPR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl); 351362181Sdim 352362181Sdim/** 353362181Sdim * Set a predefined maximum height for the skip list. 354362181Sdim * @param sl The skip list 355362181Sdim * @param to The preheight to set, or a nul/negative value to disable. 356362181Sdim * @remark When a preheight is used, the height of each inserted element is 357362181Sdim * computed randomly up to this preheight instead of the current skip list's 358362181Sdim * height plus one used by the default implementation. Using a preheight can 359362181Sdim * probably ensure more fairness with long living elements (since with an 360362181Sdim * adaptative height, former elements may have been created with a low height, 361362181Sdim * hence a longest path to reach them while the skip list grows). On the other 362362181Sdim * hand, the default behaviour (preheight <= 0) with a growing and decreasing 363362181Sdim * maximum height is more adaptative/suitable for short living values. 364362181Sdim * @note Should be called before any insertion/add. 365362181Sdim */ 366362181SdimAPR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to); 367362181Sdim 368362181Sdim/** 369266733Speter * Merge two skip lists. XXX SEMANTICS 370266733Speter * @param sl1 One of two skip lists to be merged 371266733Speter * @param sl2 The other of two skip lists to be merged 372266733Speter */ 373266733SpeterAPR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2); 374266733Speter 375266733Speter/** @} */ 376266733Speter 377266733Speter#ifdef __cplusplus 378266733Speter} 379266733Speter#endif 380266733Speter 381266733Speter#endif /* ! APR_SKIPLIST_H */ 382