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

extern route_table_delegate_t *route_table_get_default_delegate(void);

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 struct route_node *route_unlock_node(struct route_node *node)
{
	assert(node->lock > 0);
	(*(unsigned *)&node->lock)--;

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

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