Nagios 4.5.4
Dev docs for Nagios core and neb-module hackers
Loading...
Searching...
No Matches
skiplist.h
Go to the documentation of this file.
1/************************************************************************
2 *
3 * SKIPLIST.H - Skiplist data structures and functions
4 *
5 *
6 * License:
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License version 2 as
10 * published by the Free Software Foundation.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 ************************************************************************/
21
22#ifndef LIBNAGIOS_SKIPLIST_H_INCLUDED
23#define LIBNAGIOS_SKIPLIST_H_INCLUDED
24#include "lnag-utils.h"
25
26/**
27 * @file skiplist.h
28 * @brief Skiplist library functions
29 *
30 * http://en.wikipedia.org/wiki/Skiplist
31 *
32 * @{
33 */
34
35#define SKIPLIST_OK 0 /**< A ok */
36#define SKIPLIST_ERROR_ARGS 1 /**< Bad arguments */
37#define SKIPLIST_ERROR_MEMORY 2 /**< Memory error */
38#define SKIPLIST_ERROR_DUPLICATE 3 /**< Trying to insert non-unique item */
39
41
42struct skiplist_struct;
43typedef struct skiplist_struct skiplist;
44
45/**
46 * Return number of items currently in the skiplist
47 * @param list The list to investigate
48 * @return number of items in list
49 */
50unsigned long skiplist_num_items(skiplist *list);
51
52/**
53 * Create a new skiplist
54 * @param max_levels Number of "ups" we have.
55 * This Should be kept close to lg2 of the number of items to store.
56 * @param level_probability Ignored
57 * @param allow_duplicates Allow duplicates in this list
58 * @param append_duplicates Append rather than prepend duplicates
59 * @param compare_function Comparison function for data entries
60 * @return pointer to a new skiplist on success, NULL on errors
61 */
62skiplist *skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int (*compare_function)(void *, void *));
63
64/**
65 * Insert an item into a skiplist
66 * @param list The list to insert to
67 * @param data The data to insert
68 * @return SKIPLIST_OK on success, or an error code
69 */
70int skiplist_insert(skiplist *list, void *data);
71
72/**
73 * Empty the skiplist of all data
74 * @param list The list to empty
75 * @return ERROR on failures. OK on success
76 */
77int skiplist_empty(skiplist *list);
78
79/**
80 * Free all nodes (but not all data) in a skiplist
81 * This is similar to skiplist_empty(), but also free()'s the head node
82 * @param list The list to free
83 * @return OK on success, ERROR on failures
84 */
85int skiplist_free(skiplist **list);
86
87/**
88 * Get the first item in the skiplist
89 * @param list The list to peek into
90 * @return The first item, or NULL if there is none
91 */
92void *skiplist_peek(skiplist *list);
93
94/**
95 * Pop the first item from the skiplist
96 * @param list The list to pop from
97 */
98void *skiplist_pop(skiplist *list);
99
100/**
101 * Get first node of skiplist
102 * @param list The list to search
103 * @param[out] node_ptr State variable for skiplist_get_next()
104 * @return The data-item of the first node on success, NULL on errors
105 */
106void *skiplist_get_first(skiplist *list, void **node_ptr);
107
108/**
109 * Get next item from node_ptr
110 * @param[out] node_ptr State variable primed from an earlier call to
111 * skiplist_get_first() or skiplist_get_next()
112 * @return The next data-item matching node_ptr on success, NULL on errors
113 */
114void *skiplist_get_next(void **node_ptr);
115
116/**
117 * Find first entry in skiplist matching data
118 * @param list The list to search
119 * @param data Comparison object used to search
120 * @param[out] node_ptr State variable for future lookups with
121 * skiplist_find_next()
122 * @return The first found data-item, of NULL if none could be found
123 */
124void *skiplist_find_first(skiplist *list, void *data, void **node_ptr);
125
126/**
127 * Find next entry in skiplist matching data
128 * @param list The list to search
129 * @param data The data to compare against
130 * @param[out] node_ptr State var primed from earlier call to
131 * skiplist_find_next() or skiplist_find_first()
132 * @return The next found data-item, or NULL if none could be found
133 */
134void *skiplist_find_next(skiplist *list, void *data, void **node_ptr);
135
136/**
137 * Delete all items matching 'data' from skiplist
138 * @param list The list to delete from
139 * @param data Comparison object used to find the real node
140 * @return OK on success, ERROR on errors
141 */
142int skiplist_delete(skiplist *list, void *data);
143
144/**
145 * Delete first item matching 'data' from skiplist
146 * @param list The list to delete from
147 * @param data Comparison object used to search the list
148 * @return OK on success, ERROR on errors.
149 */
150int skiplist_delete_first(skiplist *list, void *data);
151
152/**
153 * Delete a particular node from the skiplist
154 * @param list The list to search
155 * @param node_ptr The node to delete
156 * @return OK on success, ERROR on errors.
157 */
158int skiplist_delete_node(skiplist *list, void *node_ptr);
159
161/* @} */
162#endif
libnagios helper and compatibility macros that lack a "real" home.
#define NAGIOS_END_DECL
C++ compatibility macro that avoid confusing indentation programs.
Definition lnag-utils.h:32
#define NAGIOS_BEGIN_DECL
C++ compatibility macro that avoids confusing indentation programs.
Definition lnag-utils.h:30
void * skiplist_find_first(skiplist *list, void *data, void **node_ptr)
Find first entry in skiplist matching data.
void * skiplist_pop(skiplist *list)
Pop the first item from the skiplist.
int skiplist_empty(skiplist *list)
Empty the skiplist of all data.
unsigned long skiplist_num_items(skiplist *list)
Return number of items currently in the skiplist.
int skiplist_insert(skiplist *list, void *data)
Insert an item into a skiplist.
int skiplist_delete_node(skiplist *list, void *node_ptr)
Delete a particular node from the skiplist.
void * skiplist_find_next(skiplist *list, void *data, void **node_ptr)
Find next entry in skiplist matching data.
int skiplist_delete_first(skiplist *list, void *data)
Delete first item matching 'data' from skiplist.
void * skiplist_peek(skiplist *list)
Get the first item in the skiplist.
int skiplist_free(skiplist **list)
Free all nodes (but not all data) in a skiplist This is similar to skiplist_empty(),...
void * skiplist_get_next(void **node_ptr)
Get next item from node_ptr.
int skiplist_delete(skiplist *list, void *data)
Delete all items matching 'data' from skiplist.
skiplist * skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int(*compare_function)(void *, void *))
Create a new skiplist.
void * skiplist_get_first(skiplist *list, void **node_ptr)
Get first node of skiplist.