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:
  36     case VARIABLE_GN:
  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:
  43       if (first->min != second->min || first->max != second->max)
  44         return 0;
  45       break;
  46     case NUMBER_GN:
  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      */
  59     case START_GN:
  60     case END_GN:
  61     default:
  62       break;
  63   }
  64
  65   return 1;
  66 }
  67
  68 struct graph_node *
  69 new_node(enum graph_node_type type)
  70 {
  71   struct graph_node *node =
  72      XMALLOC(MTYPE_CMD_TOKENS, sizeof(struct graph_node));
  73
  74   node->type = type;
  75   node->children = vector_init(VECTOR_MIN_SIZE);
  76   node->is_start = 0;
  77   node->end      = NULL;
  78   node->text     = NULL;
  79   node->value    = 0;
  80   node->min      = 0;
  81   node->max      = 0;
  82   node->element  = NULL;
  83
  84   return node;
  85 }
  86
  87 void
  88 free_node (struct graph_node *node)
  89 {
  90   if (!node) return;
  91   free_node (node->end);
  92   vector_free (node->children);
  93   free (node->text);
  94   free (node->arg);
  95   free (node->element);
  96   free (node);
  97 }
  98
  99 char *
 100 describe_node(struct graph_node *node, char* buffer, unsigned int bufsize)
 101 {
 102   if (node == NULL) {
 103     snprintf(buffer, bufsize, "(null node)");
 104     return buffer;
 105   }
 106
 107   // print this node
 108   switch (node->type) {
 109     case WORD_GN:
 110     case IPV4_GN:
 111     case IPV4_PREFIX_GN:
 112     case IPV6_GN:
 113     case IPV6_PREFIX_GN:
 114     case VARIABLE_GN:
 115     case RANGE_GN:
 116       snprintf(buffer, bufsize, node->text);
 117       break;
 118     case NUMBER_GN:
 119       snprintf(buffer, bufsize, "%ld", node->value);
 120       break;
 121     case SELECTOR_GN:
 122       snprintf(buffer, bufsize, "<>");
 123       break;
 124     case OPTION_GN:
 125       snprintf(buffer, bufsize, "[]");
 126       break;
 127     case NUL_GN:
 128       snprintf(buffer, bufsize, "NUL");
 129       break;
 130     case END_GN:
 131       snprintf(buffer, bufsize, "END");
 132       break;
 133     case START_GN:
 134       snprintf(buffer, bufsize, "START");
 135       break;
 136     default:
 137       snprintf(buffer, bufsize, "ERROR");
 138   }
 139
 140   return buffer;
 141 }
 142
 143
 144 void
 145 walk_graph(struct graph_node *start, int level)
 146 {
 147   char* desc = malloc(50);
 148   // print this node
 149   fprintf(stderr, "%s[%d] ", describe_node(start, desc, 50), vector_active(start->children));
 150   free(desc);
 151
 152   if (vector_active(start->children)) {
 153     if (vector_active(start->children) == 1)
 154       walk_graph(vector_slot(start->children, 0), level);
 155     else {
 156       fprintf(stderr, "\n");
 157       for (unsigned int i = 0; i < vector_active(start->children); i++) {
 158         struct graph_node *r = vector_slot(start->children, i);
 159         for (int j = 0; j < level+1; j++)
 160           fprintf(stderr, "    ");
 161         walk_graph(r, level+1);
 162       }
 163     }
 164   }
 165   else
 166     fprintf(stderr, "\n");
 167 }
 168