]>
Commit | Line | Data |
---|---|---|
782d9789 QY |
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 | */ | |
92055a92 | 8 | |
9d0662e0 | 9 | #include "command_graph.h" |
eceb1066 | 10 | #include <zebra.h> |
2a23ca6e | 11 | #include "memory.h" |
92055a92 | 12 | |
782d9789 QY |
13 | struct graph_node * |
14 | add_node(struct graph_node *parent, struct graph_node *child) | |
92055a92 | 15 | { |
782d9789 | 16 | struct graph_node *p_child; |
92055a92 | 17 | |
340a2b4a | 18 | for (unsigned int i = 0; i < vector_active(parent->children); i++) |
782d9789 | 19 | { |
340a2b4a | 20 | p_child = vector_slot(parent->children, i); |
782d9789 QY |
21 | if (cmp_node(child, p_child)) |
22 | return p_child; | |
23 | } | |
24 | vector_set(parent->children, child); | |
de9d7e4f | 25 | child->refs++; |
782d9789 | 26 | return child; |
92055a92 QY |
27 | } |
28 | ||
782d9789 QY |
29 | int |
30 | cmp_node(struct graph_node *first, struct graph_node *second) | |
92055a92 | 31 | { |
340a2b4a QY |
32 | // compare types |
33 | if (first->type != second->type) return 0; | |
34 | ||
35 | switch (first->type) { | |
5a5d576b QY |
36 | case WORD_GN: |
37 | case VARIABLE_GN: | |
340a2b4a QY |
38 | if (first->text && second->text) { |
39 | if (strcmp(first->text, second->text)) return 0; | |
40 | } | |
41 | else if (first->text != second->text) return 0; | |
42 | break; | |
5a5d576b | 43 | case RANGE_GN: |
340a2b4a QY |
44 | if (first->min != second->min || first->max != second->max) |
45 | return 0; | |
46 | break; | |
5a5d576b | 47 | case NUMBER_GN: |
340a2b4a QY |
48 | if (first->value != second->value) return 0; |
49 | break; | |
50 | /* selectors and options should be equal if all paths are equal, | |
51 | * but the graph isomorphism problem is not solvable in polynomial | |
52 | * time so we consider selectors and options inequal in all cases | |
53 | */ | |
54 | case SELECTOR_GN: | |
55 | case OPTION_GN: | |
56 | return 0; | |
5a5d576b QY |
57 | /* end nodes are always considered equal, since each node may only |
58 | * have one at a time | |
59 | */ | |
60 | case START_GN: | |
880e24a1 | 61 | case END_GN: |
de9d7e4f | 62 | case NUL_GN: |
340a2b4a QY |
63 | default: |
64 | break; | |
65 | } | |
66 | ||
67 | return 1; | |
92055a92 QY |
68 | } |
69 | ||
782d9789 QY |
70 | struct graph_node * |
71 | new_node(enum graph_node_type type) | |
92055a92 | 72 | { |
5a5d576b QY |
73 | struct graph_node *node = |
74 | XMALLOC(MTYPE_CMD_TOKENS, sizeof(struct graph_node)); | |
75 | ||
782d9789 QY |
76 | node->type = type; |
77 | node->children = vector_init(VECTOR_MIN_SIZE); | |
5a5d576b QY |
78 | node->end = NULL; |
79 | node->text = NULL; | |
de9d7e4f QY |
80 | node->element = NULL; |
81 | node->arg = NULL; | |
82 | node->is_start = 0; | |
5a5d576b QY |
83 | node->value = 0; |
84 | node->min = 0; | |
85 | node->max = 0; | |
de9d7e4f | 86 | node->refs = 0; |
92055a92 | 87 | |
782d9789 | 88 | return node; |
92055a92 | 89 | } |
4b0abf24 | 90 | |
5a5d576b QY |
91 | void |
92 | free_node (struct graph_node *node) | |
93 | { | |
94 | if (!node) return; | |
1a8c390d QY |
95 | if (node->children) vector_free (node->children); |
96 | if (node->element) free_cmd_element (node->element); | |
5a5d576b QY |
97 | free (node->text); |
98 | free (node->arg); | |
5a5d576b QY |
99 | free (node); |
100 | } | |
101 | ||
de9d7e4f QY |
102 | void |
103 | free_graph (struct graph_node *start) | |
104 | { | |
105 | if (start && start->children && vector_active(start->children) > 0) { | |
106 | for (unsigned int i = 0; i < vector_active(start->children); i++) { | |
107 | free_graph (vector_slot(start->children, i)); | |
108 | vector_unset(start->children, i); | |
109 | } | |
110 | } | |
111 | ||
112 | if (--(start->refs) == 0) | |
113 | free_node (start); | |
114 | } | |
115 | ||
880e24a1 QY |
116 | char * |
117 | describe_node(struct graph_node *node, char* buffer, unsigned int bufsize) | |
4b0abf24 | 118 | { |
18be0e59 | 119 | if (node == NULL) { |
880e24a1 QY |
120 | snprintf(buffer, bufsize, "(null node)"); |
121 | return buffer; | |
18be0e59 QY |
122 | } |
123 | ||
4b0abf24 | 124 | // print this node |
18be0e59 | 125 | switch (node->type) { |
4b0abf24 QY |
126 | case WORD_GN: |
127 | case IPV4_GN: | |
128 | case IPV4_PREFIX_GN: | |
129 | case IPV6_GN: | |
130 | case IPV6_PREFIX_GN: | |
131 | case VARIABLE_GN: | |
132 | case RANGE_GN: | |
880e24a1 | 133 | snprintf(buffer, bufsize, node->text); |
4b0abf24 QY |
134 | break; |
135 | case NUMBER_GN: | |
eceb1066 | 136 | snprintf(buffer, bufsize, "%ld", node->value); |
4b0abf24 QY |
137 | break; |
138 | case SELECTOR_GN: | |
880e24a1 | 139 | snprintf(buffer, bufsize, "<>"); |
4b0abf24 QY |
140 | break; |
141 | case OPTION_GN: | |
880e24a1 | 142 | snprintf(buffer, bufsize, "[]"); |
4b0abf24 QY |
143 | break; |
144 | case NUL_GN: | |
880e24a1 QY |
145 | snprintf(buffer, bufsize, "NUL"); |
146 | break; | |
147 | case END_GN: | |
148 | snprintf(buffer, bufsize, "END"); | |
4b0abf24 | 149 | break; |
5a5d576b QY |
150 | case START_GN: |
151 | snprintf(buffer, bufsize, "START"); | |
152 | break; | |
4b0abf24 | 153 | default: |
880e24a1 | 154 | snprintf(buffer, bufsize, "ERROR"); |
4b0abf24 | 155 | } |
880e24a1 QY |
156 | |
157 | return buffer; | |
18be0e59 | 158 | } |
4b0abf24 | 159 | |
18be0e59 QY |
160 | |
161 | void | |
162 | walk_graph(struct graph_node *start, int level) | |
163 | { | |
880e24a1 | 164 | char* desc = malloc(50); |
18be0e59 | 165 | // print this node |
880e24a1 QY |
166 | fprintf(stderr, "%s[%d] ", describe_node(start, desc, 50), vector_active(start->children)); |
167 | free(desc); | |
18be0e59 QY |
168 | |
169 | if (vector_active(start->children)) { | |
170 | if (vector_active(start->children) == 1) | |
171 | walk_graph(vector_slot(start->children, 0), level); | |
172 | else { | |
173 | fprintf(stderr, "\n"); | |
174 | for (unsigned int i = 0; i < vector_active(start->children); i++) { | |
175 | struct graph_node *r = vector_slot(start->children, i); | |
176 | for (int j = 0; j < level+1; j++) | |
177 | fprintf(stderr, " "); | |
178 | walk_graph(r, level+1); | |
4b0abf24 QY |
179 | } |
180 | } | |
18be0e59 QY |
181 | } |
182 | else | |
4b0abf24 | 183 | fprintf(stderr, "\n"); |
4b0abf24 | 184 | } |
5a5d576b | 185 | |
de9d7e4f QY |
186 | void |
187 | dump_node (struct graph_node *node) | |
188 | { | |
189 | char buf[50]; | |
190 | describe_node(node, buf, 50); | |
191 | fprintf(stderr, "%s[%d]\n", buf, node->type); | |
192 | fprintf(stderr, "\t->text: %s\n", node->text); | |
193 | fprintf(stderr, "\t->value: %ld\n", node->value); | |
194 | fprintf(stderr, "\t->is_start: %d\n", node->is_start); | |
195 | fprintf(stderr, "\t->element: %p\n", node->element); | |
196 | fprintf(stderr, "\t->min: %ld\n->max: %ld\n", node->min, node->max); | |
197 | fprintf(stderr, "\t->arg: %s\n", node->arg); | |
198 | fprintf(stderr, "\t->refs: %d\n", node->refs); | |
199 | fprintf(stderr, "\tnum children: %d\n", vector_active(node->children)); | |
200 | } |