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