lib/command_graph.c

   1 /*
   2  * Command DFA module.
   3  * Provides a DFA data structure and associated functions for manipulating it.
   4  * Used to match user command line input.
   5  *
   6  * @author Quentin Young <qlyoung@cumulusnetworks.com>
   7  */
   8
   9 #include "command_graph.h"
  10 #include <zebra.h>
  11 #include "memory.h"
  12
  13 struct graph_node *
  14 add_node(struct graph_node *parent, struct graph_node *child)
  15 {
  16   struct graph_node *p_child;
  17
  18   for (unsigned int i = 0; i < vector_active(parent->children); i++)
  19   {
  20     p_child = vector_slot(parent->children, i);
  21     if (cmp_node(child, p_child))
  22       return p_child;
  23   }
  24   vector_set(parent->children, child);
  25   return child;
  26 }
  27
  28 int
  29 cmp_node(struct graph_node *first, struct graph_node *second)
  30 {
  31   // compare types
  32   if (first->type != second->type) return 0;
  33
  34   switch (first->type) {
  35     case WORD_GN:       // words and variables are equal if their
  36     case VARIABLE_GN:   // text value is equal
  37       if (first->text && second->text) {
  38         if (strcmp(first->text, second->text)) return 0;
  39       }
  40       else if (first->text != second->text) return 0;
  41       break;
  42     case RANGE_GN:      // ranges are equal if their bounds are equal
  43       if (first->min != second->min || first->max != second->max)
  44         return 0;
  45       break;
  46     case NUMBER_GN:     // numbers are equal if their values are equal
  47       if (first->value != second->value) return 0;
  48       break;
  49     /* selectors and options should be equal if all paths are equal,
  50      * but the graph isomorphism problem is not solvable in polynomial
  51      * time so we consider selectors and options inequal in all cases
  52      */
  53     case SELECTOR_GN:
  54     case OPTION_GN:
  55       return 0;
  56     // end nodes are always considered equal, since each node may only
  57     // have one at a time
  58     case END_GN:
  59     default:
  60       break;
  61   }
  62
  63   return 1;
  64 }
  65
  66 struct graph_node *
  67 new_node(enum graph_node_type type)
  68 {
  69   struct graph_node *node = malloc(sizeof(struct graph_node));
  70   node->type = type;
  71   node->children = vector_init(VECTOR_MIN_SIZE);
  72   node->is_root = 0;
  73   node->end = NULL;
  74   node->text = NULL;
  75   node->value = 0;
  76   node->min   = 0;
  77   node->max   = 0;
  78   node->element = NULL;
  79
  80   return node;
  81 }
  82
  83 char *
  84 describe_node(struct graph_node *node, char* buffer, unsigned int bufsize)
  85 {
  86   if (node == NULL) {
  87     snprintf(buffer, bufsize, "(null node)");
  88     return buffer;
  89   }
  90
  91   // print this node
  92   switch (node->type) {
  93     case WORD_GN:
  94     case IPV4_GN:
  95     case IPV4_PREFIX_GN:
  96     case IPV6_GN:
  97     case IPV6_PREFIX_GN:
  98     case VARIABLE_GN:
  99     case RANGE_GN:
 100       snprintf(buffer, bufsize, node->text);
 101       break;
 102     case NUMBER_GN:
 103       snprintf(buffer, bufsize, "%ld", node->value);
 104       break;
 105     case SELECTOR_GN:
 106       snprintf(buffer, bufsize, "<>");
 107       break;
 108     case OPTION_GN:
 109       snprintf(buffer, bufsize, "[]");
 110       break;
 111     case NUL_GN:
 112       snprintf(buffer, bufsize, "NUL");
 113       break;
 114     case END_GN:
 115       snprintf(buffer, bufsize, "END");
 116       break;
 117     default:
 118       snprintf(buffer, bufsize, "ERROR");
 119   }
 120
 121   return buffer;
 122 }
 123
 124
 125 void
 126 walk_graph(struct graph_node *start, int level)
 127 {
 128   char* desc = malloc(50);
 129   // print this node
 130   fprintf(stderr, "%s[%d] ", describe_node(start, desc, 50), vector_active(start->children));
 131   free(desc);
 132
 133   if (vector_active(start->children)) {
 134     if (vector_active(start->children) == 1)
 135       walk_graph(vector_slot(start->children, 0), level);
 136     else {
 137       fprintf(stderr, "\n");
 138       for (unsigned int i = 0; i < vector_active(start->children); i++) {
 139         struct graph_node *r = vector_slot(start->children, i);
 140         for (int j = 0; j < level+1; j++)
 141           fprintf(stderr, "    ");
 142         walk_graph(r, level+1);
 143       }
 144     }
 145   }
 146   else
 147     fprintf(stderr, "\n");
 148 }