[mirror_frr.git] / lib / skiplist.h

// SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
/*
 * Copyright 1990 William Pugh
 *
 * Permission to include in quagga provide on March 31, 2016
 */

/*
 * Skip List implementation 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;
	int *level_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)(const void *val1, const 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)(const void *key1,
			const 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 const void *key,    /* in */
				void **valuePointer,	     /* in/out */
				void **cursor);		     /* out */

extern int skiplist_next_value(register struct skiplist *l, /* in */
			       register const 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 */

struct vty;
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
2bc1fe6d	1	// SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
520d2512	2	/*
d62a17ae	3	* Copyright 1990 William Pugh
520d2512	4	*
520d2512 LB	5	* Permission to include in quagga provide on March 31, 2016
	6	*/
	7
	8	/*
214d8a60	9	* Skip List implementation based on code from William Pugh.
520d2512 LB	10	* ftp://ftp.cs.umd.edu/pub/skipLists/
	11	*/
	12
	13	/* skiplist.h */
	14
	15
	16	#ifndef _ZEBRA_SKIPLIST_H
	17	#define _ZEBRA_SKIPLIST_H
	18
5e244469 RW	19	#ifdef __cplusplus
	20	extern "C" {
	21	#endif
	22
520d2512 LB	23	#define SKIPLIST_0TIMER_DEBUG 1
520d2512 LB	24
d62a17ae	25	/*
520d2512 LB	26	* skiplistnodes must always contain data to be valid. Adding an
	27	* empty node to a list is invalid
	28	*/
d62a17ae	29	struct skiplistnode {
	30	void *key;
	31	void *value;
520d2512	32	#if SKIPLIST_0TIMER_DEBUG
d62a17ae	33	int flags;
520d2512 LB	34	#define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
	35	#endif
	36
d62a17ae	37	struct skiplistnode forward[1]; / variable sized */
520d2512 LB	38	};
520d2512 LB	39
d62a17ae	40	struct skiplist {
d62a17ae	41	int flags;
520d2512 LB	42
	43	#define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
	44
d62a17ae	45	int level; /* max lvl (1 + current # of levels in list) */
	46	unsigned int count;
	47	struct skiplistnode *header;
c324b10f	48	int *level_stats;
d62a17ae	49	struct skiplistnode
	50	last; / last real list item (NULL if empty list) */
	51
	52	/*
	53	* Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
	54	* Used as definition of sorted for listnode_add_sort
	55	*/
1a4189d4	56	int (cmp)(const void val1, const void *val2);
d62a17ae	57
	58	/* callback to free user-owned data when listnode is deleted. supplying
	59	* this callback is very much encouraged!
	60	*/
	61	void (del)(void val);
520d2512 LB	62	};
	63
	64
	65	/* Prototypes. */
	66	extern struct skiplist *
d62a17ae	67	skiplist_new(/* encouraged: set list.del callback on new lists */
d62a17ae	68	int flags,
1a4189d4 DS	69	int (cmp)(const void key1,
	70	const void key2), / NULL => default cmp */
	71	void (del)(void val)); /* NULL => no auto val free */
d62a17ae	72
	73	extern void skiplist_free(struct skiplist *);
	74
	75	extern int skiplist_insert(register struct skiplist l, register void key,
	76	register void *value);
	77
	78	extern int skiplist_delete(register struct skiplist l, register void key,
	79	register void *value);
	80
	81	extern int skiplist_search(register struct skiplist l, register void key,
	82	void **valuePointer);
	83
	84	extern int skiplist_first_value(register struct skiplist l, / in */
1a4189d4 DS	85	register const void key, / in */
1a4189d4 DS	86	void *valuePointer, / in/out */
d62a17ae	87	void *cursor); / out */
	88
	89	extern int skiplist_next_value(register struct skiplist l, / in */
1a4189d4	90	register const void key, / in */
d62a17ae	91	void *valuePointer, / in/out */
	92	void *cursor); / in/out */
	93
	94	extern int skiplist_first(register struct skiplist l, void *keyPointer,
	95	void **valuePointer);
	96
	97	extern int skiplist_last(register struct skiplist l, void *keyPointer,
	98	void **valuePointer);
	99
	100	extern int skiplist_delete_first(register struct skiplist *l);
	101
	102	extern int skiplist_next(register struct skiplist l, / in */
	103	void *keyPointer, / out */
	104	void *valuePointer, / out */
	105	void *cursor); / in/out */
	106
	107	extern int skiplist_empty(register struct skiplist l); / in */
	108
	109	extern unsigned int skiplist_count(register struct skiplist l); / in */
	110
c324b10f	111	struct vty;
d62a17ae	112	extern void skiplist_debug(struct vty vty, struct skiplist l);
	113
	114	extern void skiplist_test(struct vty *vty);
520d2512	115
5e244469 RW	116	#ifdef __cplusplus
	117	}
	118	#endif
	119
520d2512	120	#endif /* _ZEBRA_SKIPLIST_H */