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 route_table_delegate_t *
 148 route_table_get_default_delegate(void);
 149
 150 extern void route_table_finish (struct route_table *);
 151 extern void route_unlock_node (struct route_node *node);
 152 extern struct route_node *route_top (struct route_table *);
 153 extern struct route_node *route_next (struct route_node *);
 154 extern struct route_node *route_next_until (struct route_node *,
 155                                             struct route_node *);
 156 extern struct route_node *route_node_get (struct route_table *const,
 157                                           const struct prefix *);
 158 extern struct route_node *route_node_lookup (const struct route_table *,
 159                                              const struct prefix *);
 160 extern struct route_node *route_lock_node (struct route_node *node);
 161 extern struct route_node *route_node_match (const struct route_table *,
 162                                             const struct prefix *);
 163 extern struct route_node *route_node_match_ipv4 (const struct route_table *,
 164                                                  const struct in_addr *);
 165 #ifdef HAVE_IPV6
 166 extern struct route_node *route_node_match_ipv6 (const struct route_table *,
 167                                                  const struct in6_addr *);
 168 #endif /* HAVE_IPV6 */
 169
 170 extern unsigned long route_table_count (const struct route_table *);
 171
 172 extern struct route_node *route_node_create (route_table_delegate_t *,
 173                                              struct route_table *);
 174 extern void route_node_destroy (route_table_delegate_t *,
 175                                 struct route_table *, struct route_node *);
 176
 177 extern struct route_node *
 178 route_table_get_next (const struct route_table *table, struct prefix *p);
 179 extern int
 180 route_table_prefix_iter_cmp (struct prefix *p1, struct prefix *p2);
 181
 182 /*
 183  * Iterator functions.
 184  */
 185 extern void route_table_iter_init (route_table_iter_t *iter,
 186                                    struct route_table *table);
 187 extern void route_table_iter_pause (route_table_iter_t *iter);
 188 extern void route_table_iter_cleanup (route_table_iter_t *iter);
 189
 190 /*
 191  * Inline functions.
 192  */
 193
 194 /*
 195  * route_table_iter_next
 196  *
 197  * Get the next node in the tree.
 198  */
 199 static inline struct route_node *
 200 route_table_iter_next (route_table_iter_t * iter)
 201 {
 202   struct route_node *node;
 203
 204   switch (iter->state)
 205     {
 206
 207     case RT_ITER_STATE_INIT:
 208
 209       /*
 210        * We're just starting the iteration.
 211        */
 212       node = route_top (iter->table);
 213       break;
 214
 215     case RT_ITER_STATE_ITERATING:
 216       node = route_next (iter->current);
 217       break;
 218
 219     case RT_ITER_STATE_PAUSED:
 220
 221       /*
 222        * Start with the node following pause_prefix.
 223        */
 224       node = route_table_get_next (iter->table, &iter->pause_prefix);
 225       break;
 226
 227     case RT_ITER_STATE_DONE:
 228       return NULL;
 229
 230     default:
 231       assert (0);
 232     }
 233
 234   iter->current = node;
 235   if (node)
 236     iter->state = RT_ITER_STATE_ITERATING;
 237   else
 238     iter->state = RT_ITER_STATE_DONE;
 239
 240   return node;
 241 }
 242
 243 /*
 244  * route_table_iter_is_done
 245  *
 246  * Returns TRUE if the iteration is complete.
 247  */
 248 static inline int
 249 route_table_iter_is_done (route_table_iter_t *iter)
 250 {
 251   return iter->state == RT_ITER_STATE_DONE;
 252 }
 253
 254 /*
 255  * route_table_iter_started
 256  *
 257  * Returns TRUE if this iterator has started iterating over the tree.
 258  */
 259 static inline int
 260 route_table_iter_started (route_table_iter_t *iter)
 261 {
 262   return iter->state != RT_ITER_STATE_INIT;
 263 }
 264
 265 #endif /* _ZEBRA_TABLE_H */