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

#ifdef __cplusplus
extern "C" {
#endif

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;
};

PREDECL_HASH(rn_hash_node)

/* Routing table top structure. */
struct route_table {
	struct route_node *top;
	struct rn_hash_node_head 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);                                       \
                                                                               \
	struct rn_hash_node_item nodehash;                                     \
	/* Each node of route. */                                              \
	void *info;                                                            \


/* 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 *delegate);

extern route_table_delegate_t *route_table_get_default_delegate(void);

static inline void *route_table_get_info(struct route_table *table)
{
	return table->info;
}

static inline void route_table_set_info(struct route_table *table, void *d)
{
	table->info = d;
}

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

extern unsigned long route_table_count(const struct route_table *table);

extern struct route_node *route_node_create(route_table_delegate_t *delegate,
					    struct route_table *table);
extern void route_node_delete(struct route_node *node);
extern void route_node_destroy(route_table_delegate_t *delegate,
			       struct route_table *table,
			       struct route_node *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)
{
	(*(unsigned *)&node->lock)++;
	return node;
}

/* Unlock node. */
static inline void route_unlock_node(struct route_node *node)
{
	assert(node->lock > 0);
	(*(unsigned *)&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;
}

#ifdef __cplusplus
}
#endif

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