[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

#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);

#endif /* _ZEBRA_SKIPLIST_H */
Commit	Line	Data
520d2512 LB	1	/*
	2	* Copyright 1990 William Pugh
	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
	34	#define SKIPLIST_0TIMER_DEBUG 1
	35
	36	/*
	37	* skiplistnodes must always contain data to be valid. Adding an
	38	* empty node to a list is invalid
	39	*/
	40	struct skiplistnode
	41	{
	42	void *key;
	43	void *value;
	44	#if SKIPLIST_0TIMER_DEBUG
	45	int flags;
	46	#define SKIPLIST_NODE_FLAG_INSERTED 0x00000001
	47	#endif
	48
	49	struct skiplistnode forward[1]; / variable sized */
	50	};
	51
	52	struct skiplist
	53	{
	54	int flags;
	55
	56	#define SKIPLIST_FLAG_ALLOW_DUPLICATES 0x00000001
	57
	58	int level; /* max lvl (1 + current # of levels in list) */
	59	unsigned int count;
	60	struct skiplistnode *header;
	61	struct skiplistnode *stats;
	62	struct skiplistnode last; / last real list item (NULL if empty list) */
	63
	64	/*
65	* Returns -1 if val1 < val2, 0 if equal?, 1 if val1 > val2.
66	* Used as definition of sorted for listnode_add_sort
67	*/
68	int (cmp) (void val1, void *val2);
69
70	/* callback to free user-owned data when listnode is deleted. supplying
71	* this callback is very much encouraged!
72	*/
73	void (del) (void val);
74	};
75
76
77	/* Prototypes. */
78	extern struct skiplist *
79	skiplist_new( /* encouraged: set list.del callback on new lists */
80	int flags,
81	int (cmp) (void key1, void key2), / NULL => default cmp */
82	void (del) (void val)); /* NULL => no auto val free */
83
84	extern void
85	skiplist_free (struct skiplist *);
86
87	extern int
88	skiplist_insert(
89	register struct skiplist *l,
90	register void *key,
91	register void *value);
92
93	extern int
94	skiplist_delete(
95	register struct skiplist *l,
96	register void *key,
97	register void *value);
98
99	extern int
100	skiplist_search(
101	register struct skiplist *l,
102	register void *key,
103	void **valuePointer);
104
105	extern int
106	skiplist_first_value(
107	register struct skiplist l, / in */
108	register void key, / in */
109	void *valuePointer, / in/out */
110	void *cursor); / out */
111
112	extern int
113	skiplist_next_value(
114	register struct skiplist l, / in */
115	register void key, / in */
116	void *valuePointer, / in/out */
117	void *cursor); / in/out */
118
119	extern int
120	skiplist_first(
121	register struct skiplist *l,
122	void **keyPointer,
123	void **valuePointer);
124
125	extern int
126	skiplist_last(
127	register struct skiplist *l,
128	void **keyPointer,
129	void **valuePointer);
130
131	extern int
132	skiplist_delete_first(
133	register struct skiplist *l);
134
135	extern int
136	skiplist_next(
137	register struct skiplist l, / in */
138	void *keyPointer, / out */
139	void *valuePointer, / out */
140	void *cursor); / in/out */
141
142	extern int
143	skiplist_empty(
144	register struct skiplist l); / in */
145
146	extern unsigned int
147	skiplist_count(
148	register struct skiplist l); / in */
149
150	extern void
151	skiplist_debug(
152	struct vty *vty,
153	struct skiplist *l);
154
155	extern void
156	skiplist_test(
157	struct vty *vty);
158
159	#endif /* _ZEBRA_SKIPLIST_H */