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