[mirror_frr.git] / lib / skiplist.h

/*
 * Copyright 1990 William Pugh
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Permission to include in quagga provide on March 31, 2016
 */

/*
 * Skip List impementation based on code from William Pugh.
 * ftp://ftp.cs.umd.edu/pub/skipLists/
 */

/* skiplist.h */


#ifndef _ZEBRA_SKIPLIST_H
#define _ZEBRA_SKIPLIST_H

#ifdef __cplusplus
extern "C" {
#endif

#define SKIPLIST_0TIMER_DEBUG 1

/*
 * skiplistnodes must always contain data to be valid. Adding an
 * empty node to a list is invalid
 */
struct skiplistnode {
	void *key;
	void *value;
#if SKIPLIST_0TIMER_DEBUG
	int flags;
#define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
#endif

	struct skiplistnode *forward[1]; /* variable sized */
};

struct skiplist {
	int flags;

#define SKIPLIST_FLAG_ALLOW_DUPLICATES	0x00000001

	int level; /* max lvl (1 + current # of levels in list) */
	unsigned int count;
	struct skiplistnode *header;
	struct skiplistnode *stats;
	struct skiplistnode
		*last; /* last real list item (NULL if empty list) */

	/*
	 * Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
	 * Used as definition of sorted for listnode_add_sort
	 */
	int (*cmp)(void *val1, void *val2);

	/* callback to free user-owned data when listnode is deleted. supplying
	 * this callback is very much encouraged!
	 */
	void (*del)(void *val);
};


/* Prototypes. */
extern struct skiplist *
skiplist_new(/* encouraged: set list.del callback on new lists */
	     int flags,
	     int (*cmp)(void *key1, void *key2), /* NULL => default cmp */
	     void (*del)(void *val));		 /* NULL => no auto val free */

extern void skiplist_free(struct skiplist *);

extern int skiplist_insert(register struct skiplist *l, register void *key,
			   register void *value);

extern int skiplist_delete(register struct skiplist *l, register void *key,
			   register void *value);

extern int skiplist_search(register struct skiplist *l, register void *key,
			   void **valuePointer);

extern int skiplist_first_value(register struct skiplist *l, /* in */
				register void *key,	  /* in */
				void **valuePointer,	 /* in/out */
				void **cursor);		     /* out */

extern int skiplist_next_value(register struct skiplist *l, /* in */
			       register void *key,	  /* in */
			       void **valuePointer,	 /* in/out */
			       void **cursor);		    /* in/out */

extern int skiplist_first(register struct skiplist *l, void **keyPointer,
			  void **valuePointer);

extern int skiplist_last(register struct skiplist *l, void **keyPointer,
			 void **valuePointer);

extern int skiplist_delete_first(register struct skiplist *l);

extern int skiplist_next(register struct skiplist *l, /* in */
			 void **keyPointer,	   /* out */
			 void **valuePointer,	 /* out */
			 void **cursor);	      /* in/out */

extern int skiplist_empty(register struct skiplist *l); /* in */

extern unsigned int skiplist_count(register struct skiplist *l); /* in */

extern void skiplist_debug(struct vty *vty, struct skiplist *l);

extern void skiplist_test(struct vty *vty);

#ifdef __cplusplus
}
#endif

#endif /* _ZEBRA_SKIPLIST_H */
Commit	Line	Data
520d2512	1	/*
d62a17ae	2	* Copyright 1990 William Pugh
520d2512 LB	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted.
	6	*
	7	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
	8	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	9	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
	10	* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
	11	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	12	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	13	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
	14	* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
	15	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
	16	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
	17	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	18	* SUCH DAMAGE.
	19	*
	20	* Permission to include in quagga provide on March 31, 2016
	21	*/
	22
	23	/*
	24	* Skip List impementation based on code from William Pugh.
	25	* ftp://ftp.cs.umd.edu/pub/skipLists/
	26	*/
	27
	28	/* skiplist.h */
	29
	30
	31	#ifndef _ZEBRA_SKIPLIST_H
	32	#define _ZEBRA_SKIPLIST_H
	33
5e244469 RW	34	#ifdef __cplusplus
	35	extern "C" {
	36	#endif
	37
520d2512 LB	38	#define SKIPLIST_0TIMER_DEBUG 1
520d2512 LB	39
d62a17ae	40	/*
520d2512 LB	41	* skiplistnodes must always contain data to be valid. Adding an
	42	* empty node to a list is invalid
	43	*/
d62a17ae	44	struct skiplistnode {
	45	void *key;
	46	void *value;
520d2512	47	#if SKIPLIST_0TIMER_DEBUG
d62a17ae	48	int flags;
520d2512 LB	49	#define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
	50	#endif
	51
d62a17ae	52	struct skiplistnode forward[1]; / variable sized */
520d2512 LB	53	};
520d2512 LB	54
d62a17ae	55	struct skiplist {
d62a17ae	56	int flags;
520d2512 LB	57
	58	#define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
	59
d62a17ae	60	int level; /* max lvl (1 + current # of levels in list) */
	61	unsigned int count;
	62	struct skiplistnode *header;
	63	struct skiplistnode *stats;
	64	struct skiplistnode
	65	last; / last real list item (NULL if empty list) */
	66
	67	/*
	68	* Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
	69	* Used as definition of sorted for listnode_add_sort
	70	*/
	71	int (cmp)(void val1, void *val2);
	72
	73	/* callback to free user-owned data when listnode is deleted. supplying
	74	* this callback is very much encouraged!
	75	*/
	76	void (del)(void val);
520d2512 LB	77	};
	78
	79
	80	/* Prototypes. */
	81	extern struct skiplist *
d62a17ae	82	skiplist_new(/* encouraged: set list.del callback on new lists */
	83	int flags,
	84	int (cmp)(void key1, void key2), / NULL => default cmp */
	85	void (del)(void val)); /* NULL => no auto val free */
	86
	87	extern void skiplist_free(struct skiplist *);
	88
	89	extern int skiplist_insert(register struct skiplist l, register void key,
	90	register void *value);
	91
	92	extern int skiplist_delete(register struct skiplist l, register void key,
	93	register void *value);
	94
	95	extern int skiplist_search(register struct skiplist l, register void key,
	96	void **valuePointer);
	97
	98	extern int skiplist_first_value(register struct skiplist l, / in */
	99	register void key, / in */
	100	void *valuePointer, / in/out */
	101	void *cursor); / out */
	102
	103	extern int skiplist_next_value(register struct skiplist l, / in */
	104	register void key, / in */
	105	void *valuePointer, / in/out */
	106	void *cursor); / in/out */
	107
	108	extern int skiplist_first(register struct skiplist l, void *keyPointer,
	109	void **valuePointer);
	110
	111	extern int skiplist_last(register struct skiplist l, void *keyPointer,
	112	void **valuePointer);
	113
	114	extern int skiplist_delete_first(register struct skiplist *l);
	115
	116	extern int skiplist_next(register struct skiplist l, / in */
	117	void *keyPointer, / out */
	118	void *valuePointer, / out */
	119	void *cursor); / in/out */
	120
	121	extern int skiplist_empty(register struct skiplist l); / in */
	122
	123	extern unsigned int skiplist_count(register struct skiplist l); / in */
	124
	125	extern void skiplist_debug(struct vty vty, struct skiplist l);
	126
	127	extern void skiplist_test(struct vty *vty);
520d2512	128
5e244469 RW	129	#ifdef __cplusplus
	130	}
	131	#endif
	132
520d2512	133	#endif /* _ZEBRA_SKIPLIST_H */