apr_skiplist.h revision 269847
165532Snectar/* Licensed to the Apache Software Foundation (ASF) under one or more 265532Snectar * contributor license agreements. See the NOTICE file distributed with 3141580Sru * this work for additional information regarding copyright ownership. 4141580Sru * The ASF licenses this file to You under the Apache License, Version 2.0 579727Sschweikh * (the "License"); you may not use this file except in compliance with 6141580Sru * the License. You may obtain a copy of the License at 7141580Sru * 879727Sschweikh * http://www.apache.org/licenses/LICENSE-2.0 9141580Sru * 10141580Sru * Unless required by applicable law or agreed to in writing, software 11141580Sru * distributed under the License is distributed on an "AS IS" BASIS, 12141580Sru * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13141580Sru * See the License for the specific language governing permissions and 14141580Sru * limitations under the License. 15141580Sru */ 16141580Sru 17141580Sru#ifndef APR_SKIPLIST_H 18141580Sru#define APR_SKIPLIST_H 19141580Sru/** 20141580Sru * @file apr_skiplist.h 21141580Sru * @brief APR skip list implementation 2279727Sschweikh */ 23141580Sru 24141580Sru#include "apr.h" 25141580Sru#include "apr_portable.h" 26141580Sru#include <stdlib.h> 27141580Sru 28141580Sru#ifdef __cplusplus 29141580Sruextern "C" { 30141580Sru#endif /* __cplusplus */ 31141580Sru 32141580Sru/** 3365532Snectar * @defgroup apr_skiplist Skip list implementation 34141580Sru * Refer to http://en.wikipedia.org/wiki/Skip_list for information 35141580Sru * about the purpose of and ideas behind skip lists. 36260084Spluknet * @ingroup APR 3765532Snectar * @{ 3865532Snectar */ 3965532Snectar 4065532Snectar/** 4165532Snectar * apr_skiplist_compare is the function type that must be implemented 4265532Snectar * per object type that is used in a skip list for comparisons to maintain 4365532Snectar * order 4465532Snectar * */ 4565532Snectartypedef int (*apr_skiplist_compare) (void *, void *); 4665532Snectar 4765532Snectar/** 4865532Snectar * apr_skiplist_freefunc is the function type that must be implemented 4965532Snectar * to handle elements as they are removed from a skip list. 5065532Snectar */ 51158757Sumetypedef void (*apr_skiplist_freefunc) (void *); 52158757Sume 53158757Sume/** Opaque structure used to represent the skip list */ 5468962Srustruct apr_skiplist; 5565532Snectar/** Opaque structure used to represent the skip list */ 5679727Sschweikhtypedef struct apr_skiplist apr_skiplist; 5765532Snectar 5865532Snectar/** 5965532Snectar * Opaque structure used to represent abstract nodes in the skip list 6065532Snectar * (an abstraction above the raw elements which are collected in the 6165532Snectar * skip list). 6265532Snectar */ 6365532Snectarstruct apr_skiplistnode; 6465532Snectar/** Opaque structure */ 6565532Snectartypedef struct apr_skiplistnode apr_skiplistnode; 6671895Sru 6771895Sru/** 6871895Sru * Allocate memory using the same mechanism as the skip list. 6971895Sru * @param sl The skip list 7071895Sru * @param size The amount to allocate 7171895Sru * @remark If a pool was provided to apr_skiplist_init(), memory will 7265532Snectar * be allocated from the pool or from a free list maintained with 7365532Snectar * the skip list. Otherwise, memory will be allocated using the 7465532Snectar * C standard library heap functions. 75206155Sume */ 76206155SumeAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 7771895Sru 7871895Sru/** 7965532Snectar * Free memory using the same mechanism as the skip list. 8065532Snectar * @param sl The skip list 8165532Snectar * @param mem The object to free 8265532Snectar * @remark If a pool was provided to apr_skiplist_init(), memory will 8365532Snectar * be added to a free list maintained with the skip list and be available 8465532Snectar * to operations on the skip list or to other calls to apr_skiplist_alloc(). 8565532Snectar * Otherwise, memory will be freed using the C standard library heap 8665532Snectar * functions. 8771895Sru */ 8871895SruAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 8971895Sru 9071895Sru/** 9165532Snectar * Allocate a new skip list 9265532Snectar * @param sl The pointer in which to return the newly created skip list 9365532Snectar * @param p The pool from which to allocate the skip list (optional). 9465532Snectar * @remark Unlike most APR functions, a pool is optional. If no pool 9565532Snectar * is provided, the C standard library heap functions will be used instead. 9665532Snectar */ 9765532SnectarAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 98158757Sume 99158757Sume/** 100172784Sbushman * Set the comparison functions to be used for searching the skip list. 101158757Sume * @param sl The skip list 10265532Snectar * @param XXX1 FIXME 10365532Snectar * @param XXX2 FIXME 10465532Snectar * 10571895Sru * @remark If existing comparison functions are being replaced, the index 10671895Sru * will be replaced during this call. That is a potentially expensive 10771895Sru * operation. 10871895Sru */ 10971895SruAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 110166168Sbms apr_skiplist_compare XXX2); 111166168Sbms 112166168Sbms/** 113166168Sbms * Set the indexing functions to the specified comparison functions and 114166168Sbms * rebuild the index. 115166168Sbms * @param sl The skip list 11671895Sru * @param XXX1 FIXME 117166168Sbms * @param XXX2 FIXME 118166168Sbms * 119166168Sbms * @remark If an index already exists, it will not be replaced and the 120166168Sbms * comparison functions will not be changed. 121166168Sbms */ 122166168SbmsAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 123166168Sbms apr_skiplist_compare XXX2); 124166168Sbms 12571895Sru/** 126166168Sbms * Return the list maintained by the skip list abstraction. 127166168Sbms * @param sl The skip list 128166168Sbms */ 129166168SbmsAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 13071895Sru 131166168Sbms/** 132166168Sbms * Return the next matching element in the skip list using the specified 133166168Sbms * comparison function. 134166168Sbms * @param sl The skip list 135166168Sbms * @param data The value to search for 136166168Sbms * @param iter A pointer to the returned skip list node representing the element 13771895Sru * found 13865532Snectar * @param func The comparison function to use 139158757Sume */ 140158757SumeAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 141158757Sume void *data, 142166168Sbms apr_skiplistnode **iter, 143166168Sbms apr_skiplist_compare func); 144158757Sume 145158757Sume/** 146186445Strhodes * Return the next matching element in the skip list using the current comparison 147166168Sbms * function. 148166168Sbms * @param sl The skip list 149186445Strhodes * @param data The value to search for 150186445Strhodes * @param iter A pointer to the returned skip list node representing the element 151186445Strhodes * found 152186445Strhodes */ 15365532SnectarAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 15465532Snectar 15565532Snectar/** 15671895Sru * Return the next element in the skip list. 15771895Sru * @param sl The skip list 15871895Sru * @param iter On entry, a pointer to the skip list node to start with; on return, 15971895Sru * a pointer to the skip list node representing the element returned 16071895Sru * @remark If iter points to a NULL value on entry, NULL will be returned. 16171895Sru */ 16271895SruAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 16371895Sru 16471895Sru/** 16571895Sru * Return the previous element in the skip list. 16671895Sru * @param sl The skip list 16771895Sru * @param iter On entry, a pointer to the skip list node to start with; on return, 16865532Snectar * a pointer to the skip list node representing the element returned 16965532Snectar * @remark If iter points to a NULL value on entry, NULL will be returned. 17065532Snectar */ 17171895SruAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 17271895Sru 17371895Sru/** 17471895Sru * Insert an element into the skip list using the specified comparison function. 17571895Sru * @param sl The skip list 17671895Sru * @param data The element to insert 17771895Sru * @param comp The comparison function to use for placement into the skip list 17871895Sru */ 17965532SnectarAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 18065532Snectar void *data, apr_skiplist_compare comp); 18165532Snectar 18265532Snectar/** 18365532Snectar * Insert an element into the skip list using the existing comparison function. 18465532Snectar * @param sl The skip list 18565532Snectar * @param data The element to insert 18671895Sru * @remark If no comparison function has been set for the skip list, the element 18771895Sru * will not be inserted and NULL will be returned. 18871895Sru */ 18971895SruAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 19065532Snectar 19171895Sru/** 19271895Sru * Remove an element from the skip list using the specified comparison function for 19365532Snectar * locating the element. 19471895Sru * @param sl The skip list 19571895Sru * @param data The element to remove 19665532Snectar * @param myfree A function to be called for each removed element 19771895Sru * @param comp The comparison function to use for placement into the skip list 19871895Sru * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 19965532Snectar * will be returned. 20071895Sru */ 20171895SruAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 20265532Snectar apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 20365532Snectar 20465532Snectar/** 20565532Snectar * Remove an element from the skip list using the existing comparison function for 20665532Snectar * locating the element. 20765532Snectar * @param sl The skip list 20865532Snectar * @param data The element to remove 20965532Snectar * @param myfree A function to be called for each removed element 21065532Snectar * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 21165532Snectar * will be returned. 21265532Snectar * @remark If no comparison function has been set for the skip list, the element 21365532Snectar * will not be removed and 0 will be returned. 21465532Snectar */ 21565532SnectarAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 21665532Snectar 21765532Snectar/** 21865532Snectar * Remove all elements from the skip list. 21981462Sru * @param sl The skip list 220158757Sume * @param myfree A function to be called for each removed element 221158757Sume */ 222158757SumeAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 223158757Sume 224158757Sume/** 225158757Sume * Remove each element from the skip list. 226158757Sume * @param sl The skip list 227172784Sbushman * @param myfree A function to be called for each removed element 228158757Sume */ 229158757SumeAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 230158757Sume 231158757Sume/** 232158757Sume * Return the first element in the skip list, leaving the element in the skip list. 233158757Sume * @param sl The skip list 234158757Sume * @param myfree A function to be called for the removed element 235158757Sume * @remark NULL will be returned if there are no elements 236158757Sume */ 237172784SbushmanAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 238158757Sume 23965532Snectar/** 24065532Snectar * Return the first element in the skip list, leaving the element in the skip list. 24165532Snectar * @param sl The skip list 24265532Snectar * @remark NULL will be returned if there are no elements 24365532Snectar */ 24465532SnectarAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 24565532Snectar 24665532Snectar/** 24765532Snectar * Merge two skip lists. XXX SEMANTICS 24865532Snectar * @param sl1 One of two skip lists to be merged 24965532Snectar * @param sl2 The other of two skip lists to be merged 25065532Snectar */ 25165532SnectarAPR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2); 25265532Snectar 25365532Snectar/** @} */ 25465532Snectar 25565532Snectar#ifdef __cplusplus 25665532Snectar} 25765532Snectar#endif 25865532Snectar 25965532Snectar#endif /* ! APR_SKIPLIST_H */ 26065532Snectar