ospfd/ospf_spf.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /*
   3  * OSPF calculation.
   4  * Copyright (C) 1999 Kunihiro Ishiguro
   5  */
   6
   7 #ifndef _QUAGGA_OSPF_SPF_H
   8 #define _QUAGGA_OSPF_SPF_H
   9
  10 #include "typesafe.h"
  11
  12 /* values for vertex->type */
  13 #define OSPF_VERTEX_ROUTER  1  /* for a Router-LSA */
  14 #define OSPF_VERTEX_NETWORK 2  /* for a Network-LSA */
  15
  16 /* values for vertex->flags */
  17 #define OSPF_VERTEX_PROCESSED      0x01
  18
  19 /* The "root" is the node running the SPF calculation */
  20
  21 PREDECL_SKIPLIST_NONUNIQ(vertex_pqueue);
  22 /* A router or network in an area */
  23 struct vertex {
  24         struct vertex_pqueue_item pqi;
  25         uint8_t flags;
  26         uint8_t type;           /* copied from LSA header */
  27         struct in_addr id;      /* copied from LSA header */
  28         struct ospf_lsa *lsa_p;
  29         struct lsa_header *lsa; /* Router or Network LSA */
  30         uint32_t distance;      /* from root to this vertex */
  31         struct list *parents;   /* list of parents in SPF tree */
  32         struct list *children;  /* list of children in SPF tree*/
  33 };
  34
  35 struct vertex_nexthop {
  36         struct in_addr router;     /* router address to send to */
  37         int lsa_pos; /* LSA position for resolving the interface */
  38 };
  39
  40 struct vertex_parent {
  41         struct vertex_nexthop *nexthop; /* nexthop taken on the root node */
  42         struct vertex_nexthop *local_nexthop; /* local nexthop of the parent */
  43         struct vertex *parent;                /* parent vertex */
  44         int backlink; /* index back to parent for router-lsa's */
  45 };
  46
  47 /* What triggered the SPF ? */
  48 typedef enum {
  49         SPF_FLAG_ROUTER_LSA_INSTALL = 1,
  50         SPF_FLAG_NETWORK_LSA_INSTALL,
  51         SPF_FLAG_SUMMARY_LSA_INSTALL,
  52         SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL,
  53         SPF_FLAG_MAXAGE,
  54         SPF_FLAG_ABR_STATUS_CHANGE,
  55         SPF_FLAG_ASBR_STATUS_CHANGE,
  56         SPF_FLAG_CONFIG_CHANGE,
  57         SPF_FLAG_GR_FINISH,
  58 } ospf_spf_reason_t;
  59
  60 extern void ospf_spf_calculate_schedule(struct ospf *, ospf_spf_reason_t);
  61 extern void ospf_spf_calculate(struct ospf_area *area,
  62                                struct ospf_lsa *root_lsa,
  63                                struct route_table *new_table,
  64                                struct route_table *all_rtrs,
  65                                struct route_table *new_rtrs, bool is_dry_run,
  66                                bool is_root_node);
  67 extern void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area,
  68                                     struct route_table *new_table,
  69                                     struct route_table *all_rtrs,
  70                                     struct route_table *new_rtrs);
  71 extern void ospf_spf_calculate_areas(struct ospf *ospf,
  72                                      struct route_table *new_table,
  73                                      struct route_table *all_rtrs,
  74                                      struct route_table *new_rtrs);
  75 extern void ospf_rtrs_free(struct route_table *);
  76 extern void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list);
  77 extern void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list);
  78 extern void ospf_spf_remove_resource(struct vertex *vertex,
  79                                      struct list *vertex_list,
  80                                      struct protected_resource *resource);
  81 extern struct vertex *ospf_spf_vertex_find(struct in_addr id,
  82                                            struct list *vertex_list);
  83 extern struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root,
  84                                                  struct in_addr *nexthop);
  85 extern struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id,
  86                                                          struct vertex *vertex);
  87 extern int vertex_parent_cmp(void *aa, void *bb);
  88
  89 extern void ospf_spf_print(struct vty *vty, struct vertex *v, int i);
  90 extern void ospf_restart_spf(struct ospf *ospf);
  91 /* void ospf_spf_calculate_timer_add (); */
  92 #endif /* _QUAGGA_OSPF_SPF_H */