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  * node->link is really internal to the table code and should not be
  76  * accessed by outside code.  We don't have any writers (yay), though some
  77  * readers are left to be fixed.
  78  *
  79  * rationale: we need to add a hash table in parallel, to speed up
  80  * exact-match lookups.
  81  *
  82  * same really applies for node->parent, though that's less of an issue.
  83  * table->link should be - and is - NEVER written by outside code
  84  */
  85 #ifdef FRR_COMPILING_TABLE_C
  86 #define table_rdonly(x)         x
  87 #define table_internal(x)       x
  88 #else
  89 #define table_rdonly(x)         const x
  90 #define table_internal(x)       const x \
  91         __attribute__((deprecated("this should only be accessed by lib/table.c")))
  92 /* table_internal is for node->link and node->lock, once we have done
  93  * something about remaining accesses */
  94 #endif
  95
  96 /* so... the problem with this is that "const" doesn't mean "readonly".
  97  * It in fact may allow the compiler to optimize based on the assumption
  98  * that the value doesn't change.  Hence, since the only purpose of this
  99  * is to aid in development, don't put the "const" in release builds.
 100  *
 101  * (I haven't seen this actually break, but GCC and LLVM are getting ever
 102  * more aggressive in optimizing...)
 103  */
 104 #ifndef DEV_BUILD
 105 #undef table_rdonly
 106 #define table_rdonly(x) x
 107 #endif
 108
 109 /*
 110  * Macro that defines all fields in a route node.
 111  */
 112 #define ROUTE_NODE_FIELDS                       \
 113   /* Actual prefix of this radix. */            \
 114   struct prefix p;                              \
 115                                                 \
 116   /* Tree link. */                              \
 117   struct route_table * table_rdonly(table);     \
 118   struct route_node * table_rdonly(parent);     \
 119   struct route_node * table_rdonly(link[2]);    \
 120                                                 \
 121   /* Lock of this radix */                      \
 122   unsigned int table_rdonly(lock);              \
 123                                                 \
 124   /* Each node of route. */                     \
 125   void *info;                                   \
 126                                                 \
 127   /* Aggregation. */                            \
 128   void *aggregate;
 129
 130
 131 /* Each routing entry. */
 132 struct route_node
 133 {
 134   ROUTE_NODE_FIELDS
 135
 136 #define l_left   link[0]
 137 #define l_right  link[1]
 138 };
 139
 140 typedef struct route_table_iter_t_ route_table_iter_t;
 141
 142 typedef enum
 143 {
 144   RT_ITER_STATE_INIT,
 145   RT_ITER_STATE_ITERATING,
 146   RT_ITER_STATE_PAUSED,
 147   RT_ITER_STATE_DONE
 148 } route_table_iter_state_t;
 149
 150 /*
 151  * route_table_iter_t
 152  *
 153  * Structure that holds state for iterating over a route table.
 154  */
 155 struct route_table_iter_t_
 156 {
 157
 158   route_table_iter_state_t state;
 159
 160   /*
 161    * Routing table that we are iterating over. The caller must ensure
 162    * that that table outlives the iterator.
 163    */
 164   struct route_table *table;
 165
 166   /*
 167    * The node that the iterator is currently on.
 168    */
 169   struct route_node *current;
 170
 171   /*
 172    * The last prefix that the iterator processed before it was paused.
 173    */
 174   struct prefix pause_prefix;
 175 };
 176
 177 /* Prototypes. */
 178 extern struct route_table *route_table_init (void);
 179
 180 extern struct route_table *
 181 route_table_init_with_delegate (route_table_delegate_t *);
 182
 183 extern route_table_delegate_t *
 184 route_table_get_default_delegate(void);
 185
 186 extern void route_table_finish (struct route_table *);
 187 extern void route_unlock_node (struct route_node *node);
 188 extern struct route_node *route_top (struct route_table *);
 189 extern struct route_node *route_next (struct route_node *);
 190 extern struct route_node *route_next_until (struct route_node *,
 191                                             const struct route_node *);
 192 extern struct route_node *route_node_get (struct route_table *const,
 193                                           union prefixconstptr);
 194 extern struct route_node *route_node_lookup (const struct route_table *,
 195                                              union prefixconstptr);
 196 extern struct route_node *route_node_lookup_maynull (const struct route_table *,
 197                                              union prefixconstptr);
 198 extern struct route_node *route_lock_node (struct route_node *node);
 199 extern struct route_node *route_node_match (const struct route_table *,
 200                                             union prefixconstptr);
 201 extern struct route_node *route_node_match_ipv4 (const struct route_table *,
 202                                                  const struct in_addr *);
 203 extern struct route_node *route_node_match_ipv6 (const struct route_table *,
 204                                                  const struct in6_addr *);
 205
 206 extern unsigned long route_table_count (const struct route_table *);
 207
 208 extern struct route_node *route_node_create (route_table_delegate_t *,
 209                                              struct route_table *);
 210 extern void route_node_destroy (route_table_delegate_t *,
 211                                 struct route_table *, struct route_node *);
 212
 213 extern struct route_node *
 214 route_table_get_next (const struct route_table *table, union prefixconstptr pu);
 215 extern int
 216 route_table_prefix_iter_cmp (const struct prefix *p1, const struct prefix *p2);
 217
 218 /*
 219  * Iterator functions.
 220  */
 221 extern void route_table_iter_init (route_table_iter_t *iter,
 222                                    struct route_table *table);
 223 extern void route_table_iter_pause (route_table_iter_t *iter);
 224 extern void route_table_iter_cleanup (route_table_iter_t *iter);
 225
 226 /*
 227  * Inline functions.
 228  */
 229
 230 /*
 231  * route_table_iter_next
 232  *
 233  * Get the next node in the tree.
 234  */
 235 static inline struct route_node *
 236 route_table_iter_next (route_table_iter_t * iter)
 237 {
 238   struct route_node *node;
 239
 240   switch (iter->state)
 241     {
 242
 243     case RT_ITER_STATE_INIT:
 244
 245       /*
 246        * We're just starting the iteration.
 247        */
 248       node = route_top (iter->table);
 249       break;
 250
 251     case RT_ITER_STATE_ITERATING:
 252       node = route_next (iter->current);
 253       break;
 254
 255     case RT_ITER_STATE_PAUSED:
 256
 257       /*
 258        * Start with the node following pause_prefix.
 259        */
 260       node = route_table_get_next (iter->table, &iter->pause_prefix);
 261       break;
 262
 263     case RT_ITER_STATE_DONE:
 264       return NULL;
 265
 266     default:
 267       assert (0);
 268     }
 269
 270   iter->current = node;
 271   if (node)
 272     iter->state = RT_ITER_STATE_ITERATING;
 273   else
 274     iter->state = RT_ITER_STATE_DONE;
 275
 276   return node;
 277 }
 278
 279 /*
 280  * route_table_iter_is_done
 281  *
 282  * Returns TRUE if the iteration is complete.
 283  */
 284 static inline int
 285 route_table_iter_is_done (route_table_iter_t *iter)
 286 {
 287   return iter->state == RT_ITER_STATE_DONE;
 288 }
 289
 290 /*
 291  * route_table_iter_started
 292  *
 293  * Returns TRUE if this iterator has started iterating over the tree.
 294  */
 295 static inline int
 296 route_table_iter_started (route_table_iter_t *iter)
 297 {
 298   return iter->state != RT_ITER_STATE_INIT;
 299 }
 300
 301 #endif /* _ZEBRA_TABLE_H */