table.h 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255
  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. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with GNU Zebra; see the file COPYING. If not, write to the Free
  19. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  20. * 02111-1307, USA.
  21. */
  22. #ifndef _ZEBRA_TABLE_H
  23. #define _ZEBRA_TABLE_H
  24. /*
  25. * Forward declarations.
  26. */
  27. struct route_node;
  28. struct route_table;
  29. /*
  30. * route_table_delegate_t
  31. *
  32. * Function vector that can be used by a client to customize the
  33. * behavior of one or more route tables.
  34. */
  35. typedef struct route_table_delegate_t_ route_table_delegate_t;
  36. typedef struct route_node * (*route_table_create_node_func_t)
  37. (route_table_delegate_t *, struct route_table *);
  38. typedef void (*route_table_destroy_node_func_t)
  39. (route_table_delegate_t *, struct route_table *, struct route_node *);
  40. struct route_table_delegate_t_
  41. {
  42. route_table_create_node_func_t create_node;
  43. route_table_destroy_node_func_t destroy_node;
  44. };
  45. /* Routing table top structure. */
  46. struct route_table
  47. {
  48. struct route_node *top;
  49. /*
  50. * Delegate that performs certain functions for this table.
  51. */
  52. route_table_delegate_t *delegate;
  53. unsigned long count;
  54. /*
  55. * User data.
  56. */
  57. void *info;
  58. };
  59. /*
  60. * Macro that defines all fields in a route node.
  61. */
  62. #define ROUTE_NODE_FIELDS \
  63. /* Actual prefix of this radix. */ \
  64. struct prefix p; \
  65. \
  66. /* Tree link. */ \
  67. struct route_table *table; \
  68. struct route_node *parent; \
  69. struct route_node *link[2]; \
  70. \
  71. /* Lock of this radix */ \
  72. unsigned int lock; \
  73. \
  74. /* Each node of route. */ \
  75. void *info; \
  76. \
  77. /* Aggregation. */ \
  78. void *aggregate;
  79. /* Each routing entry. */
  80. struct route_node
  81. {
  82. ROUTE_NODE_FIELDS
  83. #define l_left link[0]
  84. #define l_right link[1]
  85. };
  86. typedef struct route_table_iter_t_ route_table_iter_t;
  87. typedef enum
  88. {
  89. RT_ITER_STATE_INIT,
  90. RT_ITER_STATE_ITERATING,
  91. RT_ITER_STATE_PAUSED,
  92. RT_ITER_STATE_DONE
  93. } route_table_iter_state_t;
  94. /*
  95. * route_table_iter_t
  96. *
  97. * Structure that holds state for iterating over a route table.
  98. */
  99. struct route_table_iter_t_
  100. {
  101. route_table_iter_state_t state;
  102. /*
  103. * Routing table that we are iterating over. The caller must ensure
  104. * that that table outlives the iterator.
  105. */
  106. struct route_table *table;
  107. /*
  108. * The node that the iterator is currently on.
  109. */
  110. struct route_node *current;
  111. /*
  112. * The last prefix that the iterator processed before it was paused.
  113. */
  114. struct prefix pause_prefix;
  115. };
  116. /* Prototypes. */
  117. extern struct route_table *route_table_init (void);
  118. extern struct route_table *
  119. route_table_init_with_delegate (route_table_delegate_t *);
  120. extern void route_table_finish (struct route_table *);
  121. extern void route_unlock_node (struct route_node *node);
  122. extern struct route_node *route_top (struct route_table *);
  123. extern struct route_node *route_next (struct route_node *);
  124. extern struct route_node *route_next_until (struct route_node *,
  125. struct route_node *);
  126. extern struct route_node *route_node_get (struct route_table *const,
  127. const struct prefix *);
  128. extern struct route_node *route_node_lookup (const struct route_table *,
  129. const struct prefix *);
  130. extern struct route_node *route_lock_node (struct route_node *node);
  131. extern struct route_node *route_node_match (const struct route_table *,
  132. const struct prefix *);
  133. extern struct route_node *route_node_match_ipv4 (const struct route_table *,
  134. const struct in_addr *);
  135. #ifdef HAVE_IPV6
  136. extern struct route_node *route_node_match_ipv6 (const struct route_table *,
  137. const struct in6_addr *);
  138. #endif /* HAVE_IPV6 */
  139. extern unsigned long route_table_count (const struct route_table *);
  140. extern struct route_node *
  141. route_table_get_next (const struct route_table *table, struct prefix *p);
  142. extern int
  143. route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2);
  144. /*
  145. * Iterator functions.
  146. */
  147. extern void route_table_iter_init (route_table_iter_t *iter,
  148. struct route_table *table);
  149. extern void route_table_iter_pause (route_table_iter_t *iter);
  150. extern void route_table_iter_cleanup (route_table_iter_t *iter);
  151. /*
  152. * Inline functions.
  153. */
  154. /*
  155. * route_table_iter_next
  156. *
  157. * Get the next node in the tree.
  158. */
  159. static inline struct route_node *
  160. route_table_iter_next (route_table_iter_t * iter)
  161. {
  162. struct route_node *node;
  163. switch (iter->state)
  164. {
  165. case RT_ITER_STATE_INIT:
  166. /*
  167. * We're just starting the iteration.
  168. */
  169. node = route_top (iter->table);
  170. break;
  171. case RT_ITER_STATE_ITERATING:
  172. node = route_next (iter->current);
  173. break;
  174. case RT_ITER_STATE_PAUSED:
  175. /*
  176. * Start with the node following pause_prefix.
  177. */
  178. node = route_table_get_next (iter->table, &iter->pause_prefix);
  179. break;
  180. case RT_ITER_STATE_DONE:
  181. return NULL;
  182. default:
  183. assert (0);
  184. }
  185. iter->current = node;
  186. if (node)
  187. iter->state = RT_ITER_STATE_ITERATING;
  188. else
  189. iter->state = RT_ITER_STATE_DONE;
  190. return node;
  191. }
  192. /*
  193. * route_table_iter_is_done
  194. *
  195. * Returns TRUE if the iteration is complete.
  196. */
  197. static inline int
  198. route_table_iter_is_done (route_table_iter_t *iter)
  199. {
  200. return iter->state == RT_ITER_STATE_DONE;
  201. }
  202. /*
  203. * route_table_iter_started
  204. *
  205. * Returns TRUE if this iterator has started iterating over the tree.
  206. */
  207. static inline int
  208. route_table_iter_started (route_table_iter_t *iter)
  209. {
  210. return iter->state != RT_ITER_STATE_INIT;
  211. }
  212. #endif /* _ZEBRA_TABLE_H */