[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;                                                            \


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

#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; \
f9c1b7bb AS	129
f9c1b7bb AS	130
718e3744	131	/* Each routing entry. */
d62a17ae	132	struct route_node {
d62a17ae	133	ROUTE_NODE_FIELDS
718e3744	134
718e3744	135	#define l_left link[0]
718e3744	136	#define l_right link[1]
718e3744	137	};
718e3744	138
28971c8c AS	139	typedef struct route_table_iter_t_ route_table_iter_t;
28971c8c AS	140
d62a17ae	141	typedef enum {
	142	RT_ITER_STATE_INIT,
	143	RT_ITER_STATE_ITERATING,
	144	RT_ITER_STATE_PAUSED,
	145	RT_ITER_STATE_DONE
28971c8c AS	146	} route_table_iter_state_t;
	147
	148	/*
	149	* route_table_iter_t
d62a17ae	150	*
28971c8c AS	151	* Structure that holds state for iterating over a route table.
28971c8c AS	152	*/
d62a17ae	153	struct route_table_iter_t_ {
28971c8c	154
d62a17ae	155	route_table_iter_state_t state;
28971c8c	156
d62a17ae	157	/*
	158	* Routing table that we are iterating over. The caller must ensure
	159	* that that table outlives the iterator.
	160	*/
	161	struct route_table *table;
28971c8c	162
d62a17ae	163	/*
	164	* The node that the iterator is currently on.
	165	*/
	166	struct route_node *current;
28971c8c	167
d62a17ae	168	/*
	169	* The last prefix that the iterator processed before it was paused.
	170	*/
	171	struct prefix pause_prefix;
28971c8c AS	172	};
28971c8c AS	173
718e3744	174	/* Prototypes. */
d62a17ae	175	extern struct route_table *route_table_init(void);
f9c1b7bb AS	176
f9c1b7bb AS	177	extern struct route_table *
e0700290	178	route_table_init_with_delegate(route_table_delegate_t *delegate);
d62a17ae	179
	180	extern route_table_delegate_t *route_table_get_default_delegate(void);
	181
e0700290 DS	182	extern void route_table_finish(struct route_table *table);
	183	extern struct route_node route_top(struct route_table table);
	184	extern struct route_node route_next(struct route_node node);
	185	extern struct route_node route_next_until(struct route_node node,
	186	const struct route_node *limit);
	187	extern struct route_node route_node_get(struct route_table const table,
	188	union prefixconstptr pu);
	189	extern struct route_node route_node_lookup(const struct route_table table,
	190	union prefixconstptr pu);
	191	extern struct route_node *
	192	route_node_lookup_maynull(const struct route_table *table,
	193	union prefixconstptr pu);
	194	extern struct route_node route_node_match(const struct route_table table,
	195	union prefixconstptr pu);
	196	extern struct route_node route_node_match_ipv4(const struct route_table table,
	197	const struct in_addr *addr);
	198	extern struct route_node route_node_match_ipv6(const struct route_table table,
	199	const struct in6_addr *addr);
	200
	201	extern unsigned long route_table_count(const struct route_table *table);
	202
	203	extern struct route_node route_node_create(route_table_delegate_t delegate,
	204	struct route_table *table);
	205	extern void route_node_delete(struct route_node *node);
	206	extern void route_node_destroy(route_table_delegate_t *delegate,
	207	struct route_table *table,
	208	struct route_node *node);
d62a17ae	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	{
acf3a851	230	((unsigned )&node->lock)++;
01dccc0b JB	231	return node;
	232	}
	233
	234	/* Unlock node. */
0e70e6c8	235	static inline void route_unlock_node(struct route_node *node)
01dccc0b JB	236	{
01dccc0b JB	237	assert(node->lock > 0);
acf3a851	238	((unsigned )&node->lock)--;
01dccc0b	239
0e70e6c8	240	if (node->lock == 0)
01dccc0b JB	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 */