Nagios  4.3.4
Dev docs for Nagios core and neb-module hackers
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 
42 struct skiplist_struct;
43 typedef 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  */
50 unsigned 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  */
62 skiplist *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  */
70 int 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  */
77 int 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  */
85 int 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  */
92 void *skiplist_peek(skiplist *list);
93 
94 /**
95  * Pop the first item from the skiplist
96  * @param list The list to pop from
97  */
98 void *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  */
106 void *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  */
114 void *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  */
124 void *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  */
134 void *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  */
142 int 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  */
150 int 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  */
158 int skiplist_delete_node(skiplist *list, void *node_ptr);
159 
161 /* @} */
162 #endif
void * skiplist_find_next(skiplist *list, void *data, void **node_ptr)
Find next entry in skiplist matching data.
int skiplist_empty(skiplist *list)
Empty the skiplist of all data.
void * skiplist_peek(skiplist *list)
Get the first item in the skiplist.
int skiplist_delete(skiplist *list, void *data)
Delete all items matching &#39;data&#39; from skiplist.
#define NAGIOS_END_DECL
C++ compatibility macro that avoid confusing indentation programs.
Definition: lnag-utils.h:32
void * skiplist_get_first(skiplist *list, void **node_ptr)
Get first node of skiplist.
int skiplist_insert(skiplist *list, void *data)
Insert an item into a 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.
libnagios helper and compatibility macros that lack a "real" home.
int skiplist_delete_first(skiplist *list, void *data)
Delete first item matching &#39;data&#39; from skiplist.
void * skiplist_get_next(void **node_ptr)
Get next item from node_ptr.
unsigned long skiplist_num_items(skiplist *list)
Return number of items currently in the skiplist.
void * skiplist_find_first(skiplist *list, void *data, void **node_ptr)
Find first entry in skiplist matching data.
int skiplist_delete_node(skiplist *list, void *node_ptr)
Delete a particular node from the skiplist.
int skiplist_free(skiplist **list)
Free all nodes (but not all data) in a skiplist This is similar to skiplist_empty(), but also free()&#39;s the head node.
void * skiplist_pop(skiplist *list)
Pop the first item from the skiplist.
#define NAGIOS_BEGIN_DECL
C++ compatibility macro that avoids confusing indentation programs.
Definition: lnag-utils.h:30