nagios/skiplist.h

   1 /************************************************************************
   2  *
   3  * SKIPLIST.H - Skiplist data structures and functions
   4  *
   5  * Copyright (c) 2008 Ethan Galstad
   6  * Last Modified: 02-24-2008
   7  *
   8  * License:
   9  *
  10  * This program is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU General Public License version 2 as
  12  * published by the Free Software Foundation.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  ************************************************************************/
  23
  24 #ifndef _SKIPLIST_H
  25 #define _SKIPLIST_H
  26
  27 #define SKIPLIST_OK              0
  28 #define SKIPLIST_ERROR_ARGS      1
  29 #define SKIPLIST_ERROR_MEMORY    2
  30 #define SKIPLIST_ERROR_DUPLICATE 3
  31
  32
  33 typedef struct skiplistnode_struct{
  34         void *data;
  35         struct skiplistnode_struct *forward[1]; /* this must be the last element of the struct, as we allocate # of elements during runtime*/
  36 }skiplistnode;
  37
  38 typedef struct skiplist_struct{
  39         int current_level;
  40         int max_levels;
  41         float level_probability;
  42         unsigned long items;
  43         int allow_duplicates;
  44         int append_duplicates;
  45         int (*compare_function)(void *,void *);
  46         skiplistnode *head;
  47 }skiplist;
  48
  49
  50 skiplist *skiplist_new(int max_levels, float level_probability, int allow_duplicates, int append_duplicates, int (*compare_function)(void *,void *));
  51 skiplistnode *skiplist_new_node(skiplist *list,int node_levels);
  52 int skiplist_insert(skiplist *list, void *data);
  53 int skiplist_random_level(skiplist *list);
  54 int skiplist_empty(skiplist *list);
  55 int skiplist_free(skiplist **list);
  56 void *skiplist_peek(skiplist *);
  57 void *skiplist_pop(skiplist *);
  58 void *skiplist_get_first(skiplist *list, void **node_ptr);
  59 void *skiplist_get_next(void **node_ptr);
  60 void *skiplist_find_first(skiplist *list, void *data, void **node_ptr);
  61 void *skiplist_find_next(skiplist *list, void *data, void **node_ptr);
  62 int skiplist_delete(skiplist *list, void *data);
  63 int skiplist_delete_first(skiplist *list, void *data);
  64 int skiplist_delete_all(skiplist *list, void *data);
  65 int skiplist_delete_node(skiplist *list, void *node_ptr);
  66
  67 #endif