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