00001 /************************************************************************ 00002 * 00003 * SKIPLIST.H - Skiplist data structures and functions 00004 * 00005 * 00006 * License: 00007 * 00008 * This program is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU General Public License version 2 as 00010 * published by the Free Software Foundation. 00011 * 00012 * This program is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 * GNU General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU General Public License 00018 * along with this program; if not, write to the Free Software 00019 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 00020 ************************************************************************/ 00021 00022 #ifndef LIBNAGIOS_SKIPLIST_H_INCLUDED 00023 #define LIBNAGIOS_SKIPLIST_H_INCLUDED 00024 #include "lnag-utils.h" 00025 00026 /** 00027 * @file skiplist.h 00028 * @brief Skiplist library functions 00029 * 00030 * http://en.wikipedia.org/wiki/Skiplist 00031 * 00032 * @{ 00033 */ 00034 00035 #define SKIPLIST_OK 0 /**< A ok */ 00036 #define SKIPLIST_ERROR_ARGS 1 /**< Bad arguments */ 00037 #define SKIPLIST_ERROR_MEMORY 2 /**< Memory error */ 00038 #define SKIPLIST_ERROR_DUPLICATE 3 /**< Trying to insert non-unique item */ 00039 00040 NAGIOS_BEGIN_DECL 00041 00042 struct skiplist_struct; 00043 typedef struct skiplist_struct skiplist; 00044 00045 /** 00046 * Return number of items currently in the skiplist 00047 * @param list The list to investigate 00048 * @return number of items in list 00049 */ 00050 unsigned long skiplist_num_items(skiplist *list); 00051 00052 /** 00053 * Create a new skiplist 00054 * @param max_levels Number of "ups" we have. 00055 * This Should be kept close to lg2 of the number of items to store. 00056 * @param level_probability Ignored 00057 * @param allow_duplicates Allow duplicates in this list 00058 * @param append_duplicates Append rather than prepend duplicates 00059 * @param compare_function Comparison function for data entries 00060 * @return pointer to a new skiplist on success, NULL on errors 00061 */ 00062 skiplist *skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int (*compare_function)(void *, void *)); 00063 00064 /** 00065 * Insert an item into a skiplist 00066 * @param list The list to insert to 00067 * @param data The data to insert 00068 * @return SKIPLIST_OK on success, or an error code 00069 */ 00070 int skiplist_insert(skiplist *list, void *data); 00071 00072 /** 00073 * Empty the skiplist of all data 00074 * @param list The list to empty 00075 * @return ERROR on failures. OK on success 00076 */ 00077 int skiplist_empty(skiplist *list); 00078 00079 /** 00080 * Free all nodes (but not all data) in a skiplist 00081 * This is similar to skiplist_empty(), but also free()'s the head node 00082 * @param list The list to free 00083 * @return OK on success, ERROR on failures 00084 */ 00085 int skiplist_free(skiplist **list); 00086 00087 /** 00088 * Get the first item in the skiplist 00089 * @param list The list to peek into 00090 * @return The first item, or NULL if there is none 00091 */ 00092 void *skiplist_peek(skiplist *list); 00093 00094 /** 00095 * Pop the first item from the skiplist 00096 * @param list The list to pop from 00097 */ 00098 void *skiplist_pop(skiplist *list); 00099 00100 /** 00101 * Get first node of skiplist 00102 * @param list The list to search 00103 * @param[out] node_ptr State variable for skiplist_get_next() 00104 * @return The data-item of the first node on success, NULL on errors 00105 */ 00106 void *skiplist_get_first(skiplist *list, void **node_ptr); 00107 00108 /** 00109 * Get next item from node_ptr 00110 * @param[out] node_ptr State variable primed from an earlier call to 00111 * skiplist_get_first() or skiplist_get_next() 00112 * @return The next data-item matching node_ptr on success, NULL on errors 00113 */ 00114 void *skiplist_get_next(void **node_ptr); 00115 00116 /** 00117 * Find first entry in skiplist matching data 00118 * @param list The list to search 00119 * @param data Comparison object used to search 00120 * @param[out] node_ptr State variable for future lookups with 00121 * skiplist_find_next() 00122 * @return The first found data-item, of NULL if none could be found 00123 */ 00124 void *skiplist_find_first(skiplist *list, void *data, void **node_ptr); 00125 00126 /** 00127 * Find next entry in skiplist matching data 00128 * @param list The list to search 00129 * @param data The data to compare against 00130 * @param[out] node_ptr State var primed from earlier call to 00131 * skiplist_find_next() or skiplist_find_first() 00132 * @return The next found data-item, or NULL if none could be found 00133 */ 00134 void *skiplist_find_next(skiplist *list, void *data, void **node_ptr); 00135 00136 /** 00137 * Delete all items matching 'data' from skiplist 00138 * @param list The list to delete from 00139 * @param data Comparison object used to find the real node 00140 * @return OK on success, ERROR on errors 00141 */ 00142 int skiplist_delete(skiplist *list, void *data); 00143 00144 /** 00145 * Delete first item matching 'data' from skiplist 00146 * @param list The list to delete from 00147 * @param data Comparison object used to search the list 00148 * @return OK on success, ERROR on errors. 00149 */ 00150 int skiplist_delete_first(skiplist *list, void *data); 00151 00152 /** 00153 * Delete a particular node from the skiplist 00154 * @param list The list to search 00155 * @param node_ptr The node to delete 00156 * @return OK on success, ERROR on errors. 00157 */ 00158 int skiplist_delete_node(skiplist *list, void *node_ptr); 00159 00160 NAGIOS_END_DECL 00161 /* @} */ 00162 #endif