[mirror_frr.git] / lib / table.h

/*
 * Routing Table
 * Copyright (C) 1998 Kunihiro Ishiguro
 *
 * This file is part of GNU Zebra.
 *
 * GNU Zebra is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _ZEBRA_TABLE_H
#define _ZEBRA_TABLE_H

#include "memory.h"
#include "hash.h"
DECLARE_MTYPE(ROUTE_TABLE)
DECLARE_MTYPE(ROUTE_NODE)

/*
 * Forward declarations.
 */
struct route_node;
struct route_table;

/*
 * route_table_delegate_t
 *
 * Function vector that can be used by a client to customize the
 * behavior of one or more route tables.
 */
typedef struct route_table_delegate_t_ route_table_delegate_t;

typedef struct route_node *(*route_table_create_node_func_t)(
	route_table_delegate_t *, struct route_table *);

typedef void (*route_table_destroy_node_func_t)(route_table_delegate_t *,
						struct route_table *,
						struct route_node *);

struct route_table_delegate_t_ {
	route_table_create_node_func_t create_node;
	route_table_destroy_node_func_t destroy_node;
};

/* Routing table top structure. */
struct route_table {
	struct route_node *top;
	struct hash *hash;

	/*
	 * Delegate that performs certain functions for this table.
	 */
	route_table_delegate_t *delegate;
	void (*cleanup)(struct route_table *, struct route_node *);

	unsigned long count;

	/*
	 * User data.
	 */
	void *info;
};

/*
 * node->link is really internal to the table code and should not be
 * accessed by outside code.  We don't have any writers (yay), though some
 * readers are left to be fixed.
 *
 * rationale: we need to add a hash table in parallel, to speed up
 * exact-match lookups.
 *
 * same really applies for node->parent, though that's less of an issue.
 * table->link should be - and is - NEVER written by outside code
 */
#ifdef FRR_COMPILING_TABLE_C
#define table_rdonly(x)		x
#define table_internal(x)	x
#else
#define table_rdonly(x)		const x
#define table_internal(x)                                                      \
	const x __attribute__(                                                 \
		(deprecated("this should only be accessed by lib/table.c")))
/* table_internal is for node->link and node->lock, once we have done
 * something about remaining accesses */
#endif

/* so... the problem with this is that "const" doesn't mean "readonly".
 * It in fact may allow the compiler to optimize based on the assumption
 * that the value doesn't change.  Hence, since the only purpose of this
 * is to aid in development, don't put the "const" in release builds.
 *
 * (I haven't seen this actually break, but GCC and LLVM are getting ever
 * more aggressive in optimizing...)
 */
#ifndef DEV_BUILD
#undef table_rdonly
#define table_rdonly(x) x
#endif

/*
 * Macro that defines all fields in a route node.
 */
#define ROUTE_NODE_FIELDS                                                      \
	/* Actual prefix of this radix. */                                     \
	struct prefix p;                                                       \
                                                                               \
	/* Tree link. */                                                       \
	struct route_table *table_rdonly(table);                               \
	struct route_node *table_rdonly(parent);                               \
	struct route_node *table_rdonly(link[2]);                              \
                                                                               \
	/* Lock of this radix */                                               \
	unsigned int table_rdonly(lock);                                       \
                                                                               \
	/* Each node of route. */                                              \
	void *info;                                                            \
                                                                               \
	/* Aggregation. */                                                     \
	void *aggregate;


/* Each routing entry. */
struct route_node {
	ROUTE_NODE_FIELDS

#define l_left   link[0]
#define l_right  link[1]
};

typedef struct route_table_iter_t_ route_table_iter_t;

typedef enum {
	RT_ITER_STATE_INIT,
	RT_ITER_STATE_ITERATING,
	RT_ITER_STATE_PAUSED,
	RT_ITER_STATE_DONE
} route_table_iter_state_t;

/*
 * route_table_iter_t
 *
 * Structure that holds state for iterating over a route table.
 */
struct route_table_iter_t_ {

	route_table_iter_state_t state;

	/*
	 * Routing table that we are iterating over. The caller must ensure
	 * that that table outlives the iterator.
	 */
	struct route_table *table;

	/*
	 * The node that the iterator is currently on.
	 */
	struct route_node *current;

	/*
	 * The last prefix that the iterator processed before it was paused.
	 */
	struct prefix pause_prefix;
};

/* Prototypes. */
extern struct route_table *route_table_init(void);

extern struct route_table *
route_table_init_with_delegate(route_table_delegate_t *);

extern route_table_delegate_t *route_table_get_default_delegate(void);

extern void route_table_finish(struct route_table *);
extern struct route_node *route_top(struct route_table *);
extern struct route_node *route_next(struct route_node *);
extern struct route_node *route_next_until(struct route_node *,
					   const struct route_node *);
extern struct route_node *route_node_get(struct route_table *const,
					 union prefixconstptr);
extern struct route_node *route_node_lookup(const struct route_table *,
					    union prefixconstptr);
extern struct route_node *route_node_lookup_maynull(const struct route_table *,
						    union prefixconstptr);
extern struct route_node *route_node_match(const struct route_table *,
					   union prefixconstptr);
extern struct route_node *route_node_match_ipv4(const struct route_table *,
						const struct in_addr *);
extern struct route_node *route_node_match_ipv6(const struct route_table *,
						const struct in6_addr *);

extern unsigned long route_table_count(const struct route_table *);

extern struct route_node *route_node_create(route_table_delegate_t *,
					    struct route_table *);
extern void route_node_delete(struct route_node *);
extern void route_node_destroy(route_table_delegate_t *, struct route_table *,
			       struct route_node *);

extern struct route_node *route_table_get_next(const struct route_table *table,
					       union prefixconstptr pu);
extern int route_table_prefix_iter_cmp(const struct prefix *p1,
				       const struct prefix *p2);

/*
 * Iterator functions.
 */
extern void route_table_iter_init(route_table_iter_t *iter,
				  struct route_table *table);
extern void route_table_iter_pause(route_table_iter_t *iter);
extern void route_table_iter_cleanup(route_table_iter_t *iter);

/*
 * Inline functions.
 */

/* Lock node. */
static inline struct route_node *route_lock_node(struct route_node *node)
{
	node->lock++;
	return node;
}

/* Unlock node. */
static inline void route_unlock_node(struct route_node *node)
{
	assert(node->lock > 0);
	node->lock--;

	if (node->lock == 0)
		route_node_delete(node);
}

/*
 * route_table_iter_next
 *
 * Get the next node in the tree.
 */
static inline struct route_node *route_table_iter_next(route_table_iter_t *iter)
{
	struct route_node *node;

	switch (iter->state) {

	case RT_ITER_STATE_INIT:

		/*
		 * We're just starting the iteration.
		 */
		node = route_top(iter->table);
		break;

	case RT_ITER_STATE_ITERATING:
		node = route_next(iter->current);
		break;

	case RT_ITER_STATE_PAUSED:

		/*
		 * Start with the node following pause_prefix.
		 */
		node = route_table_get_next(iter->table, &iter->pause_prefix);
		break;

	case RT_ITER_STATE_DONE:
		return NULL;

	default:
		assert(0);
	}

	iter->current = node;
	if (node)
		iter->state = RT_ITER_STATE_ITERATING;
	else
		iter->state = RT_ITER_STATE_DONE;

	return node;
}

/*
 * route_table_iter_is_done
 *
 * Returns TRUE if the iteration is complete.
 */
static inline int route_table_iter_is_done(route_table_iter_t *iter)
{
	return iter->state == RT_ITER_STATE_DONE;
}

/*
 * route_table_iter_started
 *
 * Returns TRUE if this iterator has started iterating over the tree.
 */
static inline int route_table_iter_started(route_table_iter_t *iter)
{
	return iter->state != RT_ITER_STATE_INIT;
}

#endif /* _ZEBRA_TABLE_H */
Commit	Line	Data
718e3744	1	/*
	2	* Routing Table
	3	* Copyright (C) 1998 Kunihiro Ishiguro
	4	*
	5	* This file is part of GNU Zebra.
	6	*
	7	* GNU Zebra is free software; you can redistribute it and/or modify it
	8	* under the terms of the GNU General Public License as published by the
	9	* Free Software Foundation; either version 2, or (at your option) any
	10	* later version.
	11	*
	12	* GNU Zebra is distributed in the hope that it will be useful, but
	13	* WITHOUT ANY WARRANTY; without even the implied warranty of
	14	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	15	* General Public License for more details.
	16	*
896014f4 DL	17	* You should have received a copy of the GNU General Public License along
	18	* with this program; see the file COPYING; if not, write to the Free Software
	19	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
718e3744	20	*/
	21
	22	#ifndef _ZEBRA_TABLE_H
	23	#define _ZEBRA_TABLE_H
	24
4a1ab8e4	25	#include "memory.h"
bc7a2c03	26	#include "hash.h"
4a1ab8e4	27	DECLARE_MTYPE(ROUTE_TABLE)
0964ad9c	28	DECLARE_MTYPE(ROUTE_NODE)
4a1ab8e4	29
f9c1b7bb AS	30	/*
	31	* Forward declarations.
	32	*/
	33	struct route_node;
	34	struct route_table;
	35
	36	/*
	37	* route_table_delegate_t
	38	*
	39	* Function vector that can be used by a client to customize the
	40	* behavior of one or more route tables.
	41	*/
	42	typedef struct route_table_delegate_t_ route_table_delegate_t;
	43
d62a17ae	44	typedef struct route_node (route_table_create_node_func_t)(
d62a17ae	45	route_table_delegate_t , struct route_table );
f9c1b7bb	46
d62a17ae	47	typedef void (route_table_destroy_node_func_t)(route_table_delegate_t ,
	48	struct route_table *,
	49	struct route_node *);
f9c1b7bb	50
d62a17ae	51	struct route_table_delegate_t_ {
	52	route_table_create_node_func_t create_node;
	53	route_table_destroy_node_func_t destroy_node;
f9c1b7bb AS	54	};
f9c1b7bb AS	55
718e3744	56	/* Routing table top structure. */
d62a17ae	57	struct route_table {
	58	struct route_node *top;
	59	struct hash *hash;
	60
	61	/*
	62	* Delegate that performs certain functions for this table.
	63	*/
	64	route_table_delegate_t *delegate;
	65	void (cleanup)(struct route_table , struct route_node *);
	66
	67	unsigned long count;
	68
	69	/*
	70	* User data.
	71	*/
	72	void *info;
718e3744	73	};
718e3744	74
4cb260c3 DL	75	/*
	76	* node->link is really internal to the table code and should not be
	77	* accessed by outside code. We don't have any writers (yay), though some
	78	* readers are left to be fixed.
	79	*
	80	* rationale: we need to add a hash table in parallel, to speed up
	81	* exact-match lookups.
	82	*
	83	* same really applies for node->parent, though that's less of an issue.
	84	* table->link should be - and is - NEVER written by outside code
	85	*/
	86	#ifdef FRR_COMPILING_TABLE_C
	87	#define table_rdonly(x) x
	88	#define table_internal(x) x
	89	#else
	90	#define table_rdonly(x) const x
d62a17ae	91	#define table_internal(x) \
	92	const x __attribute__( \
	93	(deprecated("this should only be accessed by lib/table.c")))
4cb260c3 DL	94	/* table_internal is for node->link and node->lock, once we have done
	95	* something about remaining accesses */
	96	#endif
	97
	98	/* so... the problem with this is that "const" doesn't mean "readonly".
	99	* It in fact may allow the compiler to optimize based on the assumption
	100	* that the value doesn't change. Hence, since the only purpose of this
	101	* is to aid in development, don't put the "const" in release builds.
	102	*
	103	* (I haven't seen this actually break, but GCC and LLVM are getting ever
	104	* more aggressive in optimizing...)
	105	*/
	106	#ifndef DEV_BUILD
	107	#undef table_rdonly
	108	#define table_rdonly(x) x
	109	#endif
	110
f9c1b7bb AS	111	/*
	112	* Macro that defines all fields in a route node.
	113	*/
d62a17ae	114	#define ROUTE_NODE_FIELDS \
	115	/* Actual prefix of this radix. */ \
	116	struct prefix p; \
	117	\
	118	/* Tree link. */ \
	119	struct route_table *table_rdonly(table); \
	120	struct route_node *table_rdonly(parent); \
	121	struct route_node *table_rdonly(link[2]); \
	122	\
	123	/* Lock of this radix */ \
	124	unsigned int table_rdonly(lock); \
	125	\
	126	/* Each node of route. */ \
	127	void *info; \
	128	\
	129	/* Aggregation. */ \
	130	void *aggregate;
f9c1b7bb AS	131
f9c1b7bb AS	132
718e3744	133	/* Each routing entry. */
d62a17ae	134	struct route_node {
d62a17ae	135	ROUTE_NODE_FIELDS
718e3744	136
718e3744	137	#define l_left link[0]
718e3744	138	#define l_right link[1]
718e3744	139	};
718e3744	140
28971c8c AS	141	typedef struct route_table_iter_t_ route_table_iter_t;
28971c8c AS	142
d62a17ae	143	typedef enum {
	144	RT_ITER_STATE_INIT,
	145	RT_ITER_STATE_ITERATING,
	146	RT_ITER_STATE_PAUSED,
	147	RT_ITER_STATE_DONE
28971c8c AS	148	} route_table_iter_state_t;
	149
	150	/*
	151	* route_table_iter_t
d62a17ae	152	*
28971c8c AS	153	* Structure that holds state for iterating over a route table.
28971c8c AS	154	*/
d62a17ae	155	struct route_table_iter_t_ {
28971c8c	156
d62a17ae	157	route_table_iter_state_t state;
28971c8c	158
d62a17ae	159	/*
	160	* Routing table that we are iterating over. The caller must ensure
	161	* that that table outlives the iterator.
	162	*/
	163	struct route_table *table;
28971c8c	164
d62a17ae	165	/*
	166	* The node that the iterator is currently on.
	167	*/
	168	struct route_node *current;
28971c8c	169
d62a17ae	170	/*
	171	* The last prefix that the iterator processed before it was paused.
	172	*/
	173	struct prefix pause_prefix;
28971c8c AS	174	};
28971c8c AS	175
718e3744	176	/* Prototypes. */
d62a17ae	177	extern struct route_table *route_table_init(void);
f9c1b7bb AS	178
f9c1b7bb AS	179	extern struct route_table *
d62a17ae	180	route_table_init_with_delegate(route_table_delegate_t *);
	181
	182	extern route_table_delegate_t *route_table_get_default_delegate(void);
	183
	184	extern void route_table_finish(struct route_table *);
d62a17ae	185	extern struct route_node route_top(struct route_table );
	186	extern struct route_node route_next(struct route_node );
	187	extern struct route_node route_next_until(struct route_node ,
	188	const struct route_node *);
	189	extern struct route_node route_node_get(struct route_table const,
	190	union prefixconstptr);
	191	extern struct route_node route_node_lookup(const struct route_table ,
	192	union prefixconstptr);
	193	extern struct route_node route_node_lookup_maynull(const struct route_table ,
	194	union prefixconstptr);
d62a17ae	195	extern struct route_node route_node_match(const struct route_table ,
	196	union prefixconstptr);
	197	extern struct route_node route_node_match_ipv4(const struct route_table ,
	198	const struct in_addr *);
	199	extern struct route_node route_node_match_ipv6(const struct route_table ,
	200	const struct in6_addr *);
	201
	202	extern unsigned long route_table_count(const struct route_table *);
	203
	204	extern struct route_node route_node_create(route_table_delegate_t ,
	205	struct route_table *);
01dccc0b	206	extern void route_node_delete(struct route_node *);
d62a17ae	207	extern void route_node_destroy(route_table_delegate_t , struct route_table ,
	208	struct route_node *);
	209
	210	extern struct route_node route_table_get_next(const struct route_table table,
	211	union prefixconstptr pu);
	212	extern int route_table_prefix_iter_cmp(const struct prefix *p1,
	213	const struct prefix *p2);
28971c8c AS	214
	215	/*
	216	* Iterator functions.
	217	*/
d62a17ae	218	extern void route_table_iter_init(route_table_iter_t *iter,
	219	struct route_table *table);
	220	extern void route_table_iter_pause(route_table_iter_t *iter);
	221	extern void route_table_iter_cleanup(route_table_iter_t *iter);
28971c8c AS	222
	223	/*
	224	* Inline functions.
	225	*/
	226
01dccc0b JB	227	/* Lock node. */
	228	static inline struct route_node route_lock_node(struct route_node node)
	229	{
	230	node->lock++;
	231	return node;
	232	}
	233
	234	/* Unlock node. */
	235	static inline void route_unlock_node(struct route_node *node)
	236	{
	237	assert(node->lock > 0);
	238	node->lock--;
	239
	240	if (node->lock == 0)
	241	route_node_delete(node);
	242	}
	243
28971c8c AS	244	/*
	245	* route_table_iter_next
	246	*
	247	* Get the next node in the tree.
	248	*/
d62a17ae	249	static inline struct route_node route_table_iter_next(route_table_iter_t iter)
28971c8c	250	{
d62a17ae	251	struct route_node *node;
28971c8c	252
d62a17ae	253	switch (iter->state) {
28971c8c	254
d62a17ae	255	case RT_ITER_STATE_INIT:
28971c8c	256
d62a17ae	257	/*
	258	* We're just starting the iteration.
	259	*/
	260	node = route_top(iter->table);
	261	break;
28971c8c	262
d62a17ae	263	case RT_ITER_STATE_ITERATING:
	264	node = route_next(iter->current);
	265	break;
28971c8c	266
d62a17ae	267	case RT_ITER_STATE_PAUSED:
28971c8c	268
d62a17ae	269	/*
	270	* Start with the node following pause_prefix.
	271	*/
	272	node = route_table_get_next(iter->table, &iter->pause_prefix);
	273	break;
28971c8c	274
d62a17ae	275	case RT_ITER_STATE_DONE:
d62a17ae	276	return NULL;
28971c8c	277
d62a17ae	278	default:
	279	assert(0);
	280	}
28971c8c	281
d62a17ae	282	iter->current = node;
	283	if (node)
	284	iter->state = RT_ITER_STATE_ITERATING;
	285	else
	286	iter->state = RT_ITER_STATE_DONE;
28971c8c	287
d62a17ae	288	return node;
28971c8c AS	289	}
	290
	291	/*
	292	* route_table_iter_is_done
	293	*
	294	* Returns TRUE if the iteration is complete.
	295	*/
d62a17ae	296	static inline int route_table_iter_is_done(route_table_iter_t *iter)
28971c8c	297	{
d62a17ae	298	return iter->state == RT_ITER_STATE_DONE;
28971c8c AS	299	}
	300
	301	/*
	302	* route_table_iter_started
	303	*
	304	* Returns TRUE if this iterator has started iterating over the tree.
	305	*/
d62a17ae	306	static inline int route_table_iter_started(route_table_iter_t *iter)
28971c8c	307	{
d62a17ae	308	return iter->state != RT_ITER_STATE_INIT;
28971c8c AS	309	}
28971c8c AS	310
718e3744	311	#endif /* _ZEBRA_TABLE_H */