11541Srgrimes/* Licensed to the Apache Software Foundation (ASF) under one or more 21541Srgrimes * contributor license agreements. See the NOTICE file distributed with 31541Srgrimes * this work for additional information regarding copyright ownership. 41541Srgrimes * The ASF licenses this file to You under the Apache License, Version 2.0 51541Srgrimes * (the "License"); you may not use this file except in compliance with 61541Srgrimes * the License. You may obtain a copy of the License at 71541Srgrimes * 81541Srgrimes * http://www.apache.org/licenses/LICENSE-2.0 91541Srgrimes * 101541Srgrimes * Unless required by applicable law or agreed to in writing, software 111541Srgrimes * distributed under the License is distributed on an "AS IS" BASIS, 121541Srgrimes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131541Srgrimes * See the License for the specific language governing permissions and 141541Srgrimes * limitations under the License. 151541Srgrimes */ 161541Srgrimes 171541Srgrimes#ifndef APR_SKIPLIST_H 181541Srgrimes#define APR_SKIPLIST_H 191541Srgrimes/** 201541Srgrimes * @file apr_skiplist.h 211541Srgrimes * @brief APR skip list implementation 221541Srgrimes */ 231541Srgrimes 241541Srgrimes#include "apr.h" 251541Srgrimes#include "apr_portable.h" 261541Srgrimes#include <stdlib.h> 271541Srgrimes 281541Srgrimes#ifdef __cplusplus 291541Srgrimesextern "C" { 301541Srgrimes#endif /* __cplusplus */ 311541Srgrimes 321541Srgrimes/** 331541Srgrimes * @defgroup apr_skiplist Skip list implementation 341541Srgrimes * Refer to http://en.wikipedia.org/wiki/Skip_list for information 351541Srgrimes * about the purpose of and ideas behind skip lists. 361541Srgrimes * @ingroup APR 371541Srgrimes * @{ 381541Srgrimes */ 3913765Smpp 401541Srgrimes/** 411541Srgrimes * apr_skiplist_compare is the function type that must be implemented 421541Srgrimes * per object type that is used in a skip list for comparisons to maintain 431541Srgrimes * order. A value <0 indicates placement after this node; a value of 0 441541Srgrimes * indicates collision with this exact node; a value >0 indicates placement 451541Srgrimes * before this node. 461541Srgrimes * */ 471541Srgrimestypedef int (*apr_skiplist_compare) (void *, void *); 486549Sbde 496549Sbde/** 506549Sbde * apr_skiplist_freefunc is the function type that must be implemented 516549Sbde * to handle elements as they are removed from a skip list. 526549Sbde */ 536549Sbdetypedef void (*apr_skiplist_freefunc) (void *); 546549Sbde 556549Sbde/** Opaque structure used to represent the skip list */ 566549Sbdestruct apr_skiplist; 576549Sbde/** Opaque structure used to represent the skip list */ 586549Sbdetypedef struct apr_skiplist apr_skiplist; 596549Sbde 6012408Sdyson/** 6112408Sdyson * Opaque structure used to represent abstract nodes in the skip list 621541Srgrimes * (an abstraction above the raw elements which are collected in the 631541Srgrimes * skip list). 641541Srgrimes */ 651541Srgrimesstruct apr_skiplistnode; 661541Srgrimes/** Opaque structure */ 671541Srgrimestypedef struct apr_skiplistnode apr_skiplistnode; 681541Srgrimes 6913765Smpp/** 7012408Sdyson * Allocate memory using the same mechanism as the skip list. 711541Srgrimes * @param sl The skip list 7212767Sdyson * @param size The amount to allocate 7312767Sdyson * @remark If a pool was provided to apr_skiplist_init(), memory will 7412767Sdyson * be allocated from the pool or from a free list maintained with 751541Srgrimes * the skip list. Otherwise, memory will be allocated using the 761541Srgrimes * C standard library heap functions. 771541Srgrimes */ 781541SrgrimesAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 791541Srgrimes 801541Srgrimes/** 811541Srgrimes * Free memory using the same mechanism as the skip list. 821541Srgrimes * @param sl The skip list 831541Srgrimes * @param mem The object to free 841541Srgrimes * @remark If a pool was provided to apr_skiplist_init(), memory will 851541Srgrimes * be added to a free list maintained with the skip list and be available 861541Srgrimes * to operations on the skip list or to other calls to apr_skiplist_alloc(). 871541Srgrimes * Otherwise, memory will be freed using the C standard library heap 886549Sbde * functions. 896549Sbde */ 901541SrgrimesAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 911541Srgrimes 921541Srgrimes/** 931541Srgrimes * Allocate a new skip list 941541Srgrimes * @param sl The pointer in which to return the newly created skip list 951541Srgrimes * @param p The pool from which to allocate the skip list (optional). 961541Srgrimes * @remark Unlike most APR functions, a pool is optional. If no pool 971549Srgrimes * is provided, the C standard library heap functions will be used instead. 981549Srgrimes */ 991549SrgrimesAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 1001549Srgrimes 1011549Srgrimes/** 10212404Sdyson * Set the comparison functions to be used for searching the skip list. 10312404Sdyson * @param sl The skip list 10412404Sdyson * @param XXX1 FIXME 10512404Sdyson * @param XXX2 FIXME 1065455Sdg * 1073374Sdg * @remark If existing comparison functions are being replaced, the index 1081541Srgrimes * will be replaced during this call. That is a potentially expensive 1091541Srgrimes * operation. 1101541Srgrimes */ 1111541SrgrimesAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 1121541Srgrimes apr_skiplist_compare XXX2); 1131541Srgrimes 1141541Srgrimes/** 1151541Srgrimes * Set the indexing functions to the specified comparison functions and 1161541Srgrimes * rebuild the index. 1171541Srgrimes * @param sl The skip list 1181541Srgrimes * @param XXX1 FIXME 1191541Srgrimes * @param XXX2 FIXME 1201541Srgrimes * 1211541Srgrimes * @remark If an index already exists, it will not be replaced and the 1221541Srgrimes * comparison functions will not be changed. 1231541Srgrimes */ 1241541SrgrimesAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 1251541Srgrimes apr_skiplist_compare XXX2); 1261541Srgrimes 1271541Srgrimes/** 1281541Srgrimes * Return the list maintained by the skip list abstraction. 1291541Srgrimes * @param sl The skip list 1301541Srgrimes */ 1311541SrgrimesAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 1321541Srgrimes 1331541Srgrimes/** 1341541Srgrimes * Return the next matching element in the skip list using the specified 1351541Srgrimes * comparison function. 1365455Sdg * @param sl The skip list 1375455Sdg * @param data The value to search for 1381541Srgrimes * @param iter A pointer to the returned skip list node representing the element 1391541Srgrimes * found 1401541Srgrimes * @param func The comparison function to use 1411541Srgrimes */ 1427695SdgAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 1431541Srgrimes void *data, 1441541Srgrimes apr_skiplistnode **iter, 1451541Srgrimes apr_skiplist_compare func); 1461541Srgrimes 1477935Sdg/** 1483374Sdg * Return the next matching element in the skip list using the current comparison 1491549Srgrimes * function. 1501549Srgrimes * @param sl The skip list 1511541Srgrimes * @param data The value to search for 1521541Srgrimes * @param iter A pointer to the returned skip list node representing the element 1531564Sdg * found 1541564Sdg */ 1551564SdgAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 1561564Sdg 1571541Srgrimes/** 1581564Sdg * Return the next element in the skip list. 1591564Sdg * @param sl The skip list 1601564Sdg * @param iter On entry, a pointer to the skip list node to start with; on return, 16110226Sdg * a pointer to the skip list node representing the element returned 1621564Sdg * @remark If iter points to a NULL value on entry, NULL will be returned. 1631564Sdg */ 1641564SdgAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 1651564Sdg 1665455Sdg/** 1671564Sdg * Return the previous element in the skip list. 1689759Sbde * @param sl The skip list 1699759Sbde * @param iter On entry, a pointer to the skip list node to start with; on return, 1701564Sdg * a pointer to the skip list node representing the element returned 1711564Sdg * @remark If iter points to a NULL value on entry, NULL will be returned. 1721564Sdg */ 1731564SdgAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 1745455Sdg 1755455Sdg/** 1765455Sdg * Insert an element into the skip list using the specified comparison function 1771564Sdg * if it does not already exist. 1781564Sdg * @param sl The skip list 1791541Srgrimes * @param data The element to insert 1801541Srgrimes * @param comp The comparison function to use for placement into the skip list 1811541Srgrimes */ 18213086SdgAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 1831541Srgrimes void *data, apr_skiplist_compare comp); 1841541Srgrimes 1851541Srgrimes/** 1861541Srgrimes * Insert an element into the skip list using the existing comparison function 1871541Srgrimes * if it does not already exist (as determined by the comparison function) 1881541Srgrimes * @param sl The skip list 1891541Srgrimes * @param data The element to insert 1901541Srgrimes * @remark If no comparison function has been set for the skip list, the element 1912112Swollman * will not be inserted and NULL will be returned. 1922112Swollman */ 1932112SwollmanAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 1942112Swollman 1952112Swollman/** 1962112Swollman * Remove an element from the skip list using the specified comparison function for 1972112Swollman * locating the element. In the case of duplicates, the 1st entry will be removed. 1981541Srgrimes * @param sl The skip list 1991541Srgrimes * @param data The element to remove 2003098Sphk * @param myfree A function to be called for each removed element 2013098Sphk * @param comp The comparison function to use for placement into the skip list 2021541Srgrimes * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 2031541Srgrimes * will be returned. 2041541Srgrimes */ 2051541SrgrimesAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 2063098Sphk apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 2073098Sphk 2083098Sphk/** 2091549Srgrimes * Remove an element from the skip list using the existing comparison function for 21013490Sdyson * locating the element. In the case of duplicates, the 1st entry will be removed. 21112767Sdyson * @param sl The skip list 2123484Sphk * @param data The element to remove 2133098Sphk * @param myfree A function to be called for each removed element 21412767Sdyson * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 2157090Sbde * will be returned. 2163098Sphk * @remark If no comparison function has been set for the skip list, the element 2173098Sphk * will not be removed and 0 will be returned. 2187399Sdg */ 2193098SphkAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 2203098Sphk 2213098Sphk/** 2221541Srgrimes * Remove all elements from the skip list. 2231541Srgrimes * @param sl The skip list 2241541Srgrimes * @param myfree A function to be called for each removed element 22512767Sdyson */ 2261541SrgrimesAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 22712428Sphk 22812428Sphk/** 2293484Sphk * Remove each element from the skip list. 2307695Sdg * @param sl The skip list 2317090Sbde * @param myfree A function to be called for each removed element 2327090Sbde */ 2333484SphkAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 2343484Sphk 2353484Sphk/** 2363484Sphk * Return the first element in the skip list, removing the element from the skip list. 2373484Sphk * @param sl The skip list 2383484Sphk * @param myfree A function to be called for the removed element 2397090Sbde * @remark NULL will be returned if there are no elements 2407090Sbde */ 2413484SphkAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 2427090Sbde 2437430Sbde/** 2447430Sbde * Return the first element in the skip list, leaving the element in the skip list. 2457430Sbde * @param sl The skip list 2467430Sbde * @remark NULL will be returned if there are no elements 2471541Srgrimes */ 2481541SrgrimesAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 2491541Srgrimes 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 */ 255APR_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 */ 264