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 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)(route_table_delegate_t *,
  48                                                 struct route_table *,
  49                                                 struct route_node *);
  50
  51 struct route_table_delegate_t_ {
  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         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         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         RT_ITER_STATE_INIT,
 108         RT_ITER_STATE_ITERATING,
 109         RT_ITER_STATE_PAUSED,
 110         RT_ITER_STATE_DONE
 111 } route_table_iter_state_t;
 112
 113 /*
 114  * route_table_iter_t
 115  *
 116  * Structure that holds state for iterating over a route table.
 117  */
 118 struct route_table_iter_t_ {
 119
 120         route_table_iter_state_t state;
 121
 122         /*
 123          * Routing table that we are iterating over. The caller must ensure
 124          * that that table outlives the iterator.
 125          */
 126         struct route_table *table;
 127
 128         /*
 129          * The node that the iterator is currently on.
 130          */
 131         struct route_node *current;
 132
 133         /*
 134          * The last prefix that the iterator processed before it was paused.
 135          */
 136         struct prefix pause_prefix;
 137 };
 138
 139 /* Prototypes. */
 140 extern struct route_table *route_table_init(void);
 141
 142 extern struct route_table *
 143 route_table_init_with_delegate(route_table_delegate_t *);
 144
 145 extern route_table_delegate_t *route_table_get_default_delegate(void);
 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_node_lookup_maynull(const struct route_table *,
 158                                                     const struct prefix *);
 159 extern struct route_node *route_lock_node(struct route_node *node);
 160 extern struct route_node *route_node_match(const struct route_table *,
 161                                            const struct prefix *);
 162 extern struct route_node *route_node_match_ipv4(const struct route_table *,
 163                                                 const struct in_addr *);
 164 extern struct route_node *route_node_match_ipv6(const struct route_table *,
 165                                                 const struct in6_addr *);
 166
 167 extern unsigned long route_table_count(const struct route_table *);
 168
 169 extern struct route_node *route_node_create(route_table_delegate_t *,
 170                                             struct route_table *);
 171 extern void route_node_destroy(route_table_delegate_t *, struct route_table *,
 172                                struct route_node *);
 173
 174 extern struct route_node *route_table_get_next(const struct route_table *table,
 175                                                struct prefix *p);
 176 extern int route_table_prefix_iter_cmp(struct prefix *p1, struct prefix *p2);
 177
 178 /*
 179  * Iterator functions.
 180  */
 181 extern void route_table_iter_init(route_table_iter_t *iter,
 182                                   struct route_table *table);
 183 extern void route_table_iter_pause(route_table_iter_t *iter);
 184 extern void route_table_iter_cleanup(route_table_iter_t *iter);
 185
 186 /*
 187  * Inline functions.
 188  */
 189
 190 /*
 191  * route_table_iter_next
 192  *
 193  * Get the next node in the tree.
 194  */
 195 static inline struct route_node *route_table_iter_next(route_table_iter_t *iter)
 196 {
 197         struct route_node *node;
 198
 199         switch (iter->state) {
 200
 201         case RT_ITER_STATE_INIT:
 202
 203                 /*
 204                  * We're just starting the iteration.
 205                  */
 206                 node = route_top(iter->table);
 207                 break;
 208
 209         case RT_ITER_STATE_ITERATING:
 210                 node = route_next(iter->current);
 211                 break;
 212
 213         case RT_ITER_STATE_PAUSED:
 214
 215                 /*
 216                  * Start with the node following pause_prefix.
 217                  */
 218                 node = route_table_get_next(iter->table, &iter->pause_prefix);
 219                 break;
 220
 221         case RT_ITER_STATE_DONE:
 222                 return NULL;
 223
 224         default:
 225                 assert(0);
 226         }
 227
 228         iter->current = node;
 229         if (node)
 230                 iter->state = RT_ITER_STATE_ITERATING;
 231         else
 232                 iter->state = RT_ITER_STATE_DONE;
 233
 234         return node;
 235 }
 236
 237 /*
 238  * route_table_iter_is_done
 239  *
 240  * Returns TRUE if the iteration is complete.
 241  */
 242 static inline int route_table_iter_is_done(route_table_iter_t *iter)
 243 {
 244         return iter->state == RT_ITER_STATE_DONE;
 245 }
 246
 247 /*
 248  * route_table_iter_started
 249  *
 250  * Returns TRUE if this iterator has started iterating over the tree.
 251  */
 252 static inline int 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 */