[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 <string.h>
#include "typesafe.h"

#ifdef __cplusplus
extern "C" {
#endif

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 *rbt,
		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_remove(struct typed_rb_root *rbt,
				       struct typed_rb_entry *rbe);
const struct typed_rb_entry *typed_rb_find(const struct typed_rb_root *rbt,
		const struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
const struct typed_rb_entry *typed_rb_find_gteq(const struct typed_rb_root *rbt,
		const struct typed_rb_entry *rbe,
		int (*cmpfn)(
			const struct typed_rb_entry *a,
			const struct typed_rb_entry *b));
const struct typed_rb_entry *typed_rb_find_lt(const struct typed_rb_root *rbt,
		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(const struct typed_rb_root *rbt);
struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe);
bool typed_rb_member(const struct typed_rb_root *rbt,
		     const struct typed_rb_entry *rbe);

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

#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 const type *prefix ## _const_find_gteq(                           \
		const struct prefix##_head *h, const type *item)               \
{                                                                              \
	const 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 const type *prefix ## _const_find_lt(                             \
		const struct prefix##_head *h, const type *item)               \
{                                                                              \
	const 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);                          \
}                                                                              \
TYPESAFE_FIND_CMP(prefix, type)                                                \
macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
{                                                                              \
	struct typed_rb_entry *re;                                             \
	re = typed_rb_remove(&h->rr, &item->field.re);                         \
	return container_of_null(re, type, 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);                               \
}                                                                              \
TYPESAFE_SWAP_ALL_SIMPLE(prefix)                                               \
macro_pure const type *prefix ## _const_first(const struct prefix##_head *h)   \
{                                                                              \
	const struct typed_rb_entry *re;                                       \
	re = typed_rb_min(&h->rr);                                             \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
macro_pure const type *prefix ## _const_next(const struct prefix##_head *h,    \
					     const type *item)                 \
{                                                                              \
	const struct typed_rb_entry *re;                                       \
	re = typed_rb_next(&item->field.re);                                   \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
TYPESAFE_FIRST_NEXT(prefix, type)                                              \
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(const struct prefix##_head *h)              \
{                                                                              \
	return h->rr.count;                                                    \
}                                                                              \
macro_pure bool prefix ## _member(const struct prefix##_head *h,               \
				  const type *item)                            \
{                                                                              \
	return typed_rb_member(&h->rr, &item->field.re);                       \
}                                                                              \
MACRO_REQUIRE_SEMICOLON() /* end */

#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 const type *prefix ## _const_find(const struct prefix##_head *h,  \
					       const type *item)               \
{                                                                              \
	const struct typed_rb_entry *re;                                       \
	re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp);         \
	return container_of_null(re, type, field.re);                          \
}                                                                              \
TYPESAFE_FIND(prefix, type)                                                    \
                                                                               \
_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp);        \
MACRO_REQUIRE_SEMICOLON() /* end */

#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);     \
MACRO_REQUIRE_SEMICOLON() /* end */

#ifdef __cplusplus
}
#endif

#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
b0993fb2	23	#include <string.h>
80911bc2 DL	24	#include "typesafe.h"
80911bc2 DL	25
eea3c899 RW	26	#ifdef __cplusplus
	27	extern "C" {
	28	#endif
	29
80911bc2 DL	30	struct typed_rb_entry {
	31	struct typed_rb_entry *rbt_parent;
	32	struct typed_rb_entry *rbt_left;
	33	struct typed_rb_entry *rbt_right;
	34	unsigned int rbt_color;
	35	};
	36
	37	struct typed_rb_root {
	38	struct typed_rb_entry *rbt_root;
	39	size_t count;
	40	};
	41
571a045b	42	struct typed_rb_entry typed_rb_insert(struct typed_rb_root rbt,
80911bc2 DL	43	struct typed_rb_entry *rbe,
	44	int (*cmpfn)(
	45	const struct typed_rb_entry *a,
	46	const struct typed_rb_entry *b));
571a045b	47	struct typed_rb_entry typed_rb_remove(struct typed_rb_root rbt,
da098d78	48	struct typed_rb_entry *rbe);
daf3441d	49	const struct typed_rb_entry typed_rb_find(const struct typed_rb_root rbt,
80911bc2 DL	50	const struct typed_rb_entry *rbe,
	51	int (*cmpfn)(
	52	const struct typed_rb_entry *a,
	53	const struct typed_rb_entry *b));
daf3441d	54	const struct typed_rb_entry typed_rb_find_gteq(const struct typed_rb_root rbt,
80911bc2 DL	55	const struct typed_rb_entry *rbe,
	56	int (*cmpfn)(
	57	const struct typed_rb_entry *a,
	58	const struct typed_rb_entry *b));
daf3441d	59	const struct typed_rb_entry typed_rb_find_lt(const struct typed_rb_root rbt,
80911bc2 DL	60	const struct typed_rb_entry *rbe,
	61	int (*cmpfn)(
	62	const struct typed_rb_entry *a,
	63	const struct typed_rb_entry *b));
daf3441d DL	64	struct typed_rb_entry typed_rb_min(const struct typed_rb_root rbt);
daf3441d DL	65	struct typed_rb_entry typed_rb_next(const struct typed_rb_entry rbe);
f45897e4 DL	66	bool typed_rb_member(const struct typed_rb_root *rbt,
f45897e4 DL	67	const struct typed_rb_entry *rbe);
80911bc2 DL	68
	69	#define _PREDECL_RBTREE(prefix) \
	70	struct prefix ## _head { struct typed_rb_root rr; }; \
960b9a53 DL	71	struct prefix ## _item { struct typed_rb_entry re; }; \
960b9a53 DL	72	MACRO_REQUIRE_SEMICOLON() /* end */
80911bc2 DL	73
	74	#define INIT_RBTREE_UNIQ(var) { }
	75	#define INIT_RBTREE_NONUNIQ(var) { }
	76
	77	#define _DECLARE_RBTREE(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
	78	\
	79	macro_inline void prefix ## _init(struct prefix##_head *h) \
	80	{ \
	81	memset(h, 0, sizeof(*h)); \
	82	} \
	83	macro_inline void prefix ## _fini(struct prefix##_head *h) \
	84	{ \
	85	memset(h, 0, sizeof(*h)); \
	86	} \
	87	macro_inline type prefix ## _add(struct prefix##_head h, type *item) \
	88	{ \
	89	struct typed_rb_entry *re; \
	90	re = typed_rb_insert(&h->rr, &item->field.re, cmpfn_uq); \
	91	return container_of_null(re, type, field.re); \
	92	} \
daf3441d DL	93	macro_inline const type *prefix ## _const_find_gteq( \
daf3441d DL	94	const struct prefix##_head h, const type item) \
80911bc2	95	{ \
daf3441d	96	const struct typed_rb_entry *re; \
80911bc2 DL	97	re = typed_rb_find_gteq(&h->rr, &item->field.re, cmpfn_nuq); \
	98	return container_of_null(re, type, field.re); \
	99	} \
daf3441d DL	100	macro_inline const type *prefix ## _const_find_lt( \
daf3441d DL	101	const struct prefix##_head h, const type item) \
80911bc2	102	{ \
daf3441d	103	const struct typed_rb_entry *re; \
80911bc2 DL	104	re = typed_rb_find_lt(&h->rr, &item->field.re, cmpfn_nuq); \
	105	return container_of_null(re, type, field.re); \
	106	} \
daf3441d	107	TYPESAFE_FIND_CMP(prefix, type) \
da098d78	108	macro_inline type prefix ## _del(struct prefix##_head h, type *item) \
80911bc2	109	{ \
da098d78 SW	110	struct typed_rb_entry *re; \
	111	re = typed_rb_remove(&h->rr, &item->field.re); \
	112	return container_of_null(re, type, field.re); \
80911bc2 DL	113	} \
	114	macro_inline type prefix ## _pop(struct prefix##_head h) \
	115	{ \
	116	struct typed_rb_entry *re; \
	117	re = typed_rb_min(&h->rr); \
	118	if (!re) \
	119	return NULL; \
	120	typed_rb_remove(&h->rr, re); \
	121	return container_of(re, type, field.re); \
	122	} \
507e0e5d	123	TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
daf3441d	124	macro_pure const type prefix ## _const_first(const struct prefix##_head h) \
80911bc2	125	{ \
daf3441d	126	const struct typed_rb_entry *re; \
80911bc2 DL	127	re = typed_rb_min(&h->rr); \
	128	return container_of_null(re, type, field.re); \
	129	} \
daf3441d DL	130	macro_pure const type prefix ## _const_next(const struct prefix##_head h, \
daf3441d DL	131	const type *item) \
80911bc2	132	{ \
daf3441d	133	const struct typed_rb_entry *re; \
80911bc2 DL	134	re = typed_rb_next(&item->field.re); \
	135	return container_of_null(re, type, field.re); \
	136	} \
daf3441d	137	TYPESAFE_FIRST_NEXT(prefix, type) \
80911bc2 DL	138	macro_pure type prefix ## _next_safe(struct prefix##_head h, type *item) \
	139	{ \
	140	struct typed_rb_entry *re; \
	141	re = item ? typed_rb_next(&item->field.re) : NULL; \
	142	return container_of_null(re, type, field.re); \
	143	} \
0ca16c58	144	macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
80911bc2 DL	145	{ \
	146	return h->rr.count; \
	147	} \
f45897e4 DL	148	macro_pure bool prefix ## _member(const struct prefix##_head *h, \
	149	const type *item) \
	150	{ \
	151	return typed_rb_member(&h->rr, &item->field.re); \
	152	} \
960b9a53	153	MACRO_REQUIRE_SEMICOLON() /* end */
80911bc2 DL	154
	155	#define PREDECL_RBTREE_UNIQ(prefix) \
	156	_PREDECL_RBTREE(prefix)
	157	#define DECLARE_RBTREE_UNIQ(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	} \
daf3441d DL	165	macro_inline const type prefix ## _const_find(const struct prefix##_head h, \
daf3441d DL	166	const type *item) \
80911bc2	167	{ \
daf3441d	168	const struct typed_rb_entry *re; \
80911bc2 DL	169	re = typed_rb_find(&h->rr, &item->field.re, &prefix ## __cmp); \
	170	return container_of_null(re, type, field.re); \
	171	} \
daf3441d	172	TYPESAFE_FIND(prefix, type) \
80911bc2	173	\
960b9a53 DL	174	_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp); \
960b9a53 DL	175	MACRO_REQUIRE_SEMICOLON() /* end */
80911bc2 DL	176
	177	#define PREDECL_RBTREE_NONUNIQ(prefix) \
	178	_PREDECL_RBTREE(prefix)
	179	#define DECLARE_RBTREE_NONUNIQ(prefix, type, field, cmpfn) \
	180	\
	181	macro_inline int prefix ## __cmp(const struct typed_rb_entry *a, \
	182	const struct typed_rb_entry *b) \
	183	{ \
	184	return cmpfn(container_of(a, type, field.re), \
	185	container_of(b, type, field.re)); \
	186	} \
	187	macro_inline int prefix ## __cmp_uq(const struct typed_rb_entry *a, \
	188	const struct typed_rb_entry *b) \
	189	{ \
	190	int cmpval = cmpfn(container_of(a, type, field.re), \
	191	container_of(b, type, field.re)); \
	192	if (cmpval) \
	193	return cmpval; \
	194	if (a < b) \
	195	return -1; \
	196	if (a > b) \
	197	return 1; \
	198	return 0; \
	199	} \
	200	\
960b9a53 DL	201	_DECLARE_RBTREE(prefix, type, field, prefix ## __cmp, prefix ## __cmp_uq); \
960b9a53 DL	202	MACRO_REQUIRE_SEMICOLON() /* end */
80911bc2	203
eea3c899 RW	204	#ifdef __cplusplus
	205	}
	206	#endif
	207
80911bc2	208	#endif /* _FRR_TYPERB_H */