lib/table.h

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