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 43286503Speter * order. A value <0 indicates placement after this node; a value of 0 44286503Speter * indicates collision with this exact node; a value >0 indicates placement 45286503Speter * before this node. 46266733Speter * */ 47266733Spetertypedef int (*apr_skiplist_compare) (void *, void *); 48266733Speter 49266733Speter/** 50266733Speter * apr_skiplist_freefunc is the function type that must be implemented 51266733Speter * to handle elements as they are removed from a skip list. 52266733Speter */ 53266733Spetertypedef void (*apr_skiplist_freefunc) (void *); 54266733Speter 55266733Speter/** Opaque structure used to represent the skip list */ 56266733Speterstruct apr_skiplist; 57266733Speter/** Opaque structure used to represent the skip list */ 58266733Spetertypedef struct apr_skiplist apr_skiplist; 59266733Speter 60266733Speter/** 61266733Speter * Opaque structure used to represent abstract nodes in the skip list 62266733Speter * (an abstraction above the raw elements which are collected in the 63266733Speter * skip list). 64266733Speter */ 65266733Speterstruct apr_skiplistnode; 66266733Speter/** Opaque structure */ 67266733Spetertypedef struct apr_skiplistnode apr_skiplistnode; 68266733Speter 69266733Speter/** 70266733Speter * Allocate memory using the same mechanism as the skip list. 71266733Speter * @param sl The skip list 72266733Speter * @param size The amount to allocate 73266733Speter * @remark If a pool was provided to apr_skiplist_init(), memory will 74266733Speter * be allocated from the pool or from a free list maintained with 75266733Speter * the skip list. Otherwise, memory will be allocated using the 76266733Speter * C standard library heap functions. 77266733Speter */ 78266733SpeterAPR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size); 79266733Speter 80266733Speter/** 81266733Speter * Free memory using the same mechanism as the skip list. 82266733Speter * @param sl The skip list 83266733Speter * @param mem The object to free 84266733Speter * @remark If a pool was provided to apr_skiplist_init(), memory will 85266733Speter * be added to a free list maintained with the skip list and be available 86266733Speter * to operations on the skip list or to other calls to apr_skiplist_alloc(). 87266733Speter * Otherwise, memory will be freed using the C standard library heap 88266733Speter * functions. 89266733Speter */ 90266733SpeterAPR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem); 91266733Speter 92266733Speter/** 93266733Speter * Allocate a new skip list 94266733Speter * @param sl The pointer in which to return the newly created skip list 95266733Speter * @param p The pool from which to allocate the skip list (optional). 96266733Speter * @remark Unlike most APR functions, a pool is optional. If no pool 97266733Speter * is provided, the C standard library heap functions will be used instead. 98266733Speter */ 99266733SpeterAPR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **sl, apr_pool_t *p); 100266733Speter 101266733Speter/** 102266733Speter * Set the comparison functions to be used for searching the skip list. 103266733Speter * @param sl The skip list 104266733Speter * @param XXX1 FIXME 105266733Speter * @param XXX2 FIXME 106266733Speter * 107266733Speter * @remark If existing comparison functions are being replaced, the index 108266733Speter * will be replaced during this call. That is a potentially expensive 109266733Speter * operation. 110266733Speter */ 111266733SpeterAPR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl, apr_skiplist_compare XXX1, 112266733Speter apr_skiplist_compare XXX2); 113266733Speter 114266733Speter/** 115266733Speter * Set the indexing functions to the specified comparison functions and 116266733Speter * rebuild the index. 117266733Speter * @param sl The skip list 118266733Speter * @param XXX1 FIXME 119266733Speter * @param XXX2 FIXME 120266733Speter * 121266733Speter * @remark If an index already exists, it will not be replaced and the 122266733Speter * comparison functions will not be changed. 123266733Speter */ 124266733SpeterAPR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, apr_skiplist_compare XXX1, 125266733Speter apr_skiplist_compare XXX2); 126266733Speter 127266733Speter/** 128266733Speter * Return the list maintained by the skip list abstraction. 129266733Speter * @param sl The skip list 130266733Speter */ 131266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl); 132266733Speter 133266733Speter/** 134266733Speter * Return the next matching element in the skip list using the specified 135266733Speter * comparison function. 136266733Speter * @param sl The skip list 137266733Speter * @param data The value to search for 138266733Speter * @param iter A pointer to the returned skip list node representing the element 139266733Speter * found 140266733Speter * @param func The comparison function to use 141266733Speter */ 142266733SpeterAPR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, 143266733Speter void *data, 144266733Speter apr_skiplistnode **iter, 145266733Speter apr_skiplist_compare func); 146266733Speter 147266733Speter/** 148266733Speter * Return the next matching element in the skip list using the current comparison 149266733Speter * function. 150266733Speter * @param sl The skip list 151266733Speter * @param data The value to search for 152266733Speter * @param iter A pointer to the returned skip list node representing the element 153266733Speter * found 154266733Speter */ 155266733SpeterAPR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter); 156266733Speter 157266733Speter/** 158266733Speter * Return the next element in the skip list. 159266733Speter * @param sl The skip list 160266733Speter * @param iter On entry, a pointer to the skip list node to start with; on return, 161266733Speter * a pointer to the skip list node representing the element returned 162266733Speter * @remark If iter points to a NULL value on entry, NULL will be returned. 163266733Speter */ 164266733SpeterAPR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter); 165266733Speter 166266733Speter/** 167266733Speter * Return the previous element in the skip list. 168266733Speter * @param sl The skip list 169266733Speter * @param iter On entry, a pointer to the skip list node to start with; on return, 170266733Speter * a pointer to the skip list node representing the element returned 171266733Speter * @remark If iter points to a NULL value on entry, NULL will be returned. 172266733Speter */ 173266733SpeterAPR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter); 174266733Speter 175266733Speter/** 176286503Speter * Insert an element into the skip list using the specified comparison function 177286503Speter * if it does not already exist. 178266733Speter * @param sl The skip list 179266733Speter * @param data The element to insert 180266733Speter * @param comp The comparison function to use for placement into the skip list 181266733Speter */ 182266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, 183266733Speter void *data, apr_skiplist_compare comp); 184266733Speter 185266733Speter/** 186286503Speter * Insert an element into the skip list using the existing comparison function 187286503Speter * if it does not already exist (as determined by the comparison function) 188266733Speter * @param sl The skip list 189266733Speter * @param data The element to insert 190266733Speter * @remark If no comparison function has been set for the skip list, the element 191266733Speter * will not be inserted and NULL will be returned. 192266733Speter */ 193266733SpeterAPR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data); 194266733Speter 195266733Speter/** 196266733Speter * Remove an element from the skip list using the specified comparison function for 197286503Speter * locating the element. In the case of duplicates, the 1st entry will be removed. 198266733Speter * @param sl The skip list 199266733Speter * @param data The element to remove 200266733Speter * @param myfree A function to be called for each removed element 201266733Speter * @param comp The comparison function to use for placement into the skip list 202266733Speter * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 203266733Speter * will be returned. 204266733Speter */ 205266733SpeterAPR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sl, void *data, 206266733Speter apr_skiplist_freefunc myfree, apr_skiplist_compare comp); 207266733Speter 208266733Speter/** 209266733Speter * Remove an element from the skip list using the existing comparison function for 210286503Speter * locating the element. In the case of duplicates, the 1st entry will be removed. 211266733Speter * @param sl The skip list 212266733Speter * @param data The element to remove 213266733Speter * @param myfree A function to be called for each removed element 214266733Speter * @remark If the element is not found, 0 will be returned. Otherwise, the heightXXX 215266733Speter * will be returned. 216266733Speter * @remark If no comparison function has been set for the skip list, the element 217266733Speter * will not be removed and 0 will be returned. 218266733Speter */ 219266733SpeterAPR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree); 220266733Speter 221266733Speter/** 222266733Speter * Remove all elements from the skip list. 223266733Speter * @param sl The skip list 224266733Speter * @param myfree A function to be called for each removed element 225266733Speter */ 226266733SpeterAPR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree); 227266733Speter 228266733Speter/** 229266733Speter * Remove each element from the skip list. 230266733Speter * @param sl The skip list 231266733Speter * @param myfree A function to be called for each removed element 232266733Speter */ 233266733SpeterAPR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree); 234266733Speter 235266733Speter/** 236286503Speter * Return the first element in the skip list, removing the element from the skip list. 237266733Speter * @param sl The skip list 238266733Speter * @param myfree A function to be called for the removed element 239266733Speter * @remark NULL will be returned if there are no elements 240266733Speter */ 241266733SpeterAPR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *sl, apr_skiplist_freefunc myfree); 242266733Speter 243266733Speter/** 244266733Speter * Return the first element in the skip list, leaving the element in the skip list. 245266733Speter * @param sl The skip list 246266733Speter * @remark NULL will be returned if there are no elements 247266733Speter */ 248266733SpeterAPR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl); 249266733Speter 250266733Speter/** 251266733Speter * Merge two skip lists. XXX SEMANTICS 252266733Speter * @param sl1 One of two skip lists to be merged 253266733Speter * @param sl2 The other of two skip lists to be merged 254266733Speter */ 255266733SpeterAPR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2); 256266733Speter 257266733Speter/** @} */ 258266733Speter 259266733Speter#ifdef __cplusplus 260266733Speter} 261266733Speter#endif 262266733Speter 263266733Speter#endif /* ! APR_SKIPLIST_H */ 264