[mirror_frr.git] / lib / typerb.h

/*
 * The following Red-Black tree implementation is based off code with
 * original copyright:
 *
 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef _FRR_TYPERB_H
#define _FRR_TYPERB_H

#include "typesafe.h"

struct typed_rb_entry {
	struct typed_rb_entry *rbt_parent;
	struct typed_rb_entry *rbt_left;
	struct typed_rb_entry *rbt_right;
	unsigned int rbt_color;
};

struct typed_rb_root {
	struct typed_rb_entry *rbt_root;
	size_t count;
};

struct typed_rb_entry *typed_rb_insert(struct typed_rb_root *,
		struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
void typed_rb_remove(struct typed_rb_root *, struct typed_rb_entry *rbe);
struct typed_rb_entry *typed_rb_find(struct typed_rb_root *,
		const struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
struct typed_rb_entry *typed_rb_find_gteq(struct typed_rb_root *,
		const struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
struct typed_rb_entry *typed_rb_find_lt(struct typed_rb_root *,
		const struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
struct typed_rb_entry *typed_rb_min(struct typed_rb_root *);
struct typed_rb_entry *typed_rb_next(struct typed_rb_entry *);

#define _PREDECL_RBTREE(prefix)                                                \
struct prefix ## _head { struct typed_rb_root rr; };                           \
struct prefix ## _item { struct typed_rb_entry re; };

#define INIT_RBTREE_UNIQ(var)		{ }
#define INIT_RBTREE_NONUNIQ(var)	{ }

#define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq)              \
                                                                               \
macro_inline void prefix ## _init(struct prefix##_head *h)                     \
{                                                                              \
	memset(h, 0, sizeof(*h));                                              \
}                                                                              \
macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
{                                                                              \
	memset(h, 0, sizeof(*h));                                              \
}                                                                              \
macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq);               \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
		const type *item)                                              \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq);           \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
		const type *item)                                              \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq);             \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
{                                                                              \
	typed_rb_remove(&h->rr, &item->field.re);                              \
}                                                                              \
macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_min(&h->rr);                                             \
	if (!re)                                                               \
		return NULL;                                                   \
	typed_rb_remove(&h->rr, re);                                           \
	return container_of(re, type, field.re);                               \
}                                                                              \
macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_min(&h->rr);                                             \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_next(&item->field.re);                                   \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = item ? typed_rb_next(&item->field.re) : NULL;                     \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
{                                                                              \
	return h->rr.count;                                                    \
}                                                                              \
/* ... */

#define PREDECL_RBTREE_UNIQ(prefix)                                            \
	_PREDECL_RBTREE(prefix)
#define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn)                        \
                                                                               \
macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
		const struct typed_rb_entry *b)                                \
{                                                                              \
	return cmpfn(container_of(a, type, field.re),                          \
			container_of(b, type, field.re));                      \
}                                                                              \
macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
                                                                               \
_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp)         \
/* ... */

#define PREDECL_RBTREE_NONUNIQ(prefix)                                         \
	_PREDECL_RBTREE(prefix)
#define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn)                     \
                                                                               \
macro_inline int prefix ## __cmp(const struct typed_rb_entry *a,               \
		const struct typed_rb_entry *b)                                \
{                                                                              \
	return cmpfn(container_of(a, type, field.re),                          \
			container_of(b, type, field.re));                      \
}                                                                              \
macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a,            \
		const struct typed_rb_entry *b)                                \
{                                                                              \
	int cmpval = cmpfn(container_of(a, type, field.re),                    \
			container_of(b, type, field.re));                      \
	if (cmpval)                                                            \
		return cmpval;                                                 \
	if (a < b)                                                             \
		return -1;                                                     \
	if (a > b)                                                             \
		return 1;                                                      \
	return 0;                                                              \
}                                                                              \
                                                                               \
_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq)      \
/* ... */

#endif /* _FRR_TYPERB_H */
Commit	Line	Data
80911bc2 DL	1	/*
	2	* The following Red-Black tree implementation is based off code with
	3	* original copyright:
	4	*
	5	* Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
	6	*
	7	* Permission to use, copy, modify, and distribute this software for any
	8	* purpose with or without fee is hereby granted, provided that the above
	9	* copyright notice and this permission notice appear in all copies.
	10	*
	11	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	12	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	13	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
	14	* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	15	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
	16	* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
	17	* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
	18	*/
	19
	20	#ifndef _FRR_TYPERB_H
	21	#define _FRR_TYPERB_H
	22
	23	#include "typesafe.h"
	24
	25	struct typed_rb_entry {
	26	struct typed_rb_entry *rbt_parent;
	27	struct typed_rb_entry *rbt_left;
	28	struct typed_rb_entry *rbt_right;
	29	unsigned int rbt_color;
	30	};
	31
	32	struct typed_rb_root {
	33	struct typed_rb_entry *rbt_root;
	34	size_t count;
	35	};
	36
	37	struct typed_rb_entry typed_rb_insert(struct typed_rb_root ,
	38	struct typed_rb_entry *rbe,
	39	int (*cmpfn)(
	40	const struct typed_rb_entry *a,
	41	const struct typed_rb_entry *b));
	42	void typed_rb_remove(struct typed_rb_root , struct typed_rb_entry rbe);
	43	struct typed_rb_entry typed_rb_find(struct typed_rb_root ,
	44	const struct typed_rb_entry *rbe,
	45	int (*cmpfn)(
	46	const struct typed_rb_entry *a,
	47	const struct typed_rb_entry *b));
	48	struct typed_rb_entry typed_rb_find_gteq(struct typed_rb_root ,
	49	const struct typed_rb_entry *rbe,
	50	int (*cmpfn)(
	51	const struct typed_rb_entry *a,
	52	const struct typed_rb_entry *b));
	53	struct typed_rb_entry typed_rb_find_lt(struct typed_rb_root ,
	54	const struct typed_rb_entry *rbe,
	55	int (*cmpfn)(
	56	const struct typed_rb_entry *a,
	57	const struct typed_rb_entry *b));
	58	struct typed_rb_entry typed_rb_min(struct typed_rb_root );
	59	struct typed_rb_entry typed_rb_next(struct typed_rb_entry );
	60
	61	#define _PREDECL_RBTREE(prefix) \
	62	struct prefix ## _head { struct typed_rb_root rr; }; \
	63	struct prefix ## _item { struct typed_rb_entry re; };
	64
65	#define INIT_RBTREE_UNIQ(var) { }
66	#define INIT_RBTREE_NONUNIQ(var) { }
67
68	#define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
69	\
70	macro_inline void prefix ## _init(struct prefix##_head *h) \
71	{ \
72	memset(h, 0, sizeof(*h)); \
73	} \
74	macro_inline void prefix ## _fini(struct prefix##_head *h) \
75	{ \
76	memset(h, 0, sizeof(*h)); \
77	} \
78	macro_inline type prefix ## _add(struct prefix##_head h, type *item) \
79	{ \
80	struct typed_rb_entry *re; \
81	re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq); \
82	return container_of_null(re, type, field.re); \
83	} \
84	macro_inline type prefix ## _find_gteq(struct prefix##_head h, \
85	const type *item) \
86	{ \
87	struct typed_rb_entry *re; \
88	re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq); \
89	return container_of_null(re, type, field.re); \
90	} \
91	macro_inline type prefix ## _find_lt(struct prefix##_head h, \
92	const type *item) \
93	{ \
94	struct typed_rb_entry *re; \
95	re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq); \
96	return container_of_null(re, type, field.re); \
97	} \
98	macro_inline void prefix ## _del(struct prefix##_head h, type item) \
99	{ \
100	typed_rb_remove(&h->rr, &item->field.re); \
101	} \
102	macro_inline type prefix ## _pop(struct prefix##_head h) \
103	{ \
104	struct typed_rb_entry *re; \
105	re = typed_rb_min(&h->rr); \
106	if (!re) \
107	return NULL; \
108	typed_rb_remove(&h->rr, re); \
109	return container_of(re, type, field.re); \
110	} \
111	macro_pure type prefix ## _first(struct prefix##_head h) \
112	{ \
113	struct typed_rb_entry *re; \
114	re = typed_rb_min(&h->rr); \
115	return container_of_null(re, type, field.re); \
116	} \
117	macro_pure type prefix ## _next(struct prefix##_head h, type *item) \
118	{ \
119	struct typed_rb_entry *re; \
120	re = typed_rb_next(&item->field.re); \
121	return container_of_null(re, type, field.re); \
122	} \
123	macro_pure type prefix ## _next_safe(struct prefix##_head h, type *item) \
124	{ \
125	struct typed_rb_entry *re; \
126	re = item ? typed_rb_next(&item->field.re) : NULL; \
127	return container_of_null(re, type, field.re); \
128	} \
129	macro_pure size_t prefix ## _count(struct prefix##_head *h) \
130	{ \
131	return h->rr.count; \
132	} \
133	/* ... */
134
135	#define PREDECL_RBTREE_UNIQ(prefix) \
136	_PREDECL_RBTREE(prefix)
137	#define DECLARE_RBTREE_UNIQ(prefix, type, field, cmpfn) \
138	\
139	macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
140	const struct typed_rb_entry *b) \
141	{ \
142	return cmpfn(container_of(a, type, field.re), \
143	container_of(b, type, field.re)); \
144	} \
145	macro_inline type prefix ## _find(struct prefix##_head h, const type *item) \
146	{ \
147	struct typed_rb_entry *re; \
148	re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp); \
149	return container_of_null(re, type, field.re); \
150	} \
151	\
152	_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp) \
153	/* ... */
154
155	#define PREDECL_RBTREE_NONUNIQ(prefix) \
156	_PREDECL_RBTREE(prefix)
157	#define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn) \
158	\
159	macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
160	const struct typed_rb_entry *b) \
161	{ \
162	return cmpfn(container_of(a, type, field.re), \
163	container_of(b, type, field.re)); \
164	} \
165	macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \
166	const struct typed_rb_entry *b) \
167	{ \
168	int cmpval = cmpfn(container_of(a, type, field.re), \
169	container_of(b, type, field.re)); \
170	if (cmpval) \
171	return cmpval; \
172	if (a < b) \
173	return -1; \
174	if (a > b) \
175	return 1; \
176	return 0; \
177	} \
178	\
179	_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq) \
180	/* ... */
181
182	#endif /* _FRR_TYPERB_H */