rbtree

view test/rbshell/test.c @ 15:1b77b72688fe

find changesets by author, revision, files, or words in the commit message
- fixed bug in rb_init making it ignore comparison functions other than the builtin - fixed rb_find and rb_findi return type, which should be struct rbnode*, not void*
author John Tsiombikas <nuclear@member.fsf.org>
date Sun, 02 Nov 2014 11:00:27 +0200
parents
children
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <ctype.h>
5 #include "rbtree.h"
6 #include "sym.h"
7
8 #define SEP " \t\r\n,\"\'"
9
10 /* commands */
11 enum {
12 CMD_CREATE,
13 CMD_DESTROY,
14 CMD_CLEAR,
15 CMD_COPY,
16 CMD_SIZE,
17 CMD_INSERT,
18 CMD_DELETE,
19 CMD_FIND,
20 CMD_PRINT,
21
22 MAX_CMD
23 };
24
25 int runcmd(int cmd, int argc, char **argv);
26
27 #define NUM_TREES 8
28 struct rbtree *trees[NUM_TREES];
29
30
31 int main(void)
32 {
33 char buf[512];
34
35 /* init symbol table */
36 if(init_sym() == -1) {
37 return 1;
38 }
39 add_sym("create", CMD_CREATE, 0);
40 add_sym("destroy", CMD_DESTROY, 1);
41 add_sym("clear", CMD_CLEAR, 1);
42 add_sym("copy", CMD_COPY, 2);
43 add_sym("size", CMD_SIZE, 1);
44 add_sym("insert", CMD_INSERT, 2);
45 add_sym("delete", CMD_DELETE, 2);
46 add_sym("find", CMD_FIND, 2);
47 add_sym("print", CMD_PRINT, 1);
48
49 for(;;) {
50 int argc = 0;
51 char *argv[8];
52 int cmd_id, cmd_arity;
53
54 printf("rbshell> ");
55 fflush(stdout);
56
57 if(!fgets(buf, sizeof buf, stdin)) {
58 putchar('\n');
59 break;
60 }
61
62 if(!(argv[argc] = strtok(buf, SEP)) || argv[argc][0] == '#') {
63 return 0; /* empty / comment */
64 }
65 argc++;
66
67 if((cmd_id = sym_lookup(argv[0])) == -1) {
68 continue;
69 }
70 cmd_arity = sym_arity(argv[0]);
71
72 while((argv[argc] = strtok(0, SEP))) {
73 argc++;
74 if(argc >= sizeof argv / sizeof *argv) {
75 break;
76 }
77 }
78
79 if(argc - 1 != cmd_arity) {
80 fprintf(stderr, "too many (%d) arguments for %s, expected %d\n", argc - 1, argv[0], cmd_arity);
81 continue;
82 }
83
84 runcmd(cmd_id, argc, argv);
85 }
86
87 destroy_sym();
88 return 0;
89 }
90
91 #define CHECKINT(i) \
92 if(!isdigit(argv[i][0])) { \
93 fprintf(stderr, "expected number, got: %s\n", argv[i]); \
94 return -1; \
95 }
96
97 #define CHECKVALID(idx) \
98 if((idx) < 0 || (idx) >= NUM_TREES || !trees[idx]) { \
99 fprintf(stderr, "invalid tree specified: %d\n", idx); \
100 return -1; \
101 }
102
103
104 int runcmd(int cmd, int argc, char **argv)
105 {
106 int i, idx, idx2, n;
107 struct rbnode *node;
108
109 switch(cmd) {
110 case CMD_CREATE:
111 for(i=0; i<NUM_TREES; i++) {
112 if(trees[i] == 0) {
113 if(!(trees[i] = rb_create(RB_KEY_INT))) {
114 fprintf(stderr, "failed to create a new tree\n");
115 return -1;
116 }
117 printf("created new tree: %d\n", i);
118 break;
119 }
120 }
121 if(i == NUM_TREES) {
122 fprintf(stderr, "can't create more trees\n");
123 return -1;
124 }
125 break;
126
127 case CMD_DESTROY:
128 CHECKINT(1);
129 idx = atoi(argv[1]);
130 CHECKVALID(idx);
131
132 rb_free(trees[idx]);
133 trees[idx] = 0;
134 printf("destroyed tree: %d\n", idx);
135 break;
136
137 case CMD_CLEAR:
138 CHECKINT(1);
139 idx = atoi(argv[1]);
140 CHECKVALID(idx);
141
142 rb_clear(trees[idx]);
143 printf("cleared tree: %d\n", idx);
144 break;
145
146 case CMD_COPY:
147 CHECKINT(1);
148 CHECKINT(2);
149 idx = atoi(argv[1]);
150 idx2 = atoi(argv[2]);
151 CHECKVALID(idx);
152 CHECKVALID(idx2);
153
154 rb_copy(trees[idx2], trees[idx]);
155 printf("copied %d -> %d\n", idx, idx2);
156 break;
157
158 case CMD_SIZE:
159 CHECKINT(1);
160 idx = atoi(argv[1]);
161 CHECKVALID(idx);
162
163 printf("tree size: %d\n", rb_size(trees[idx]));
164 break;
165
166 case CMD_INSERT:
167 CHECKINT(1);
168 CHECKINT(2);
169 idx = atoi(argv[1]);
170 CHECKVALID(idx);
171
172 n = atoi(argv[2]);
173 rb_inserti(trees[idx], n, 0);
174 printf("inserted: %d\n", n);
175 break;
176
177 case CMD_DELETE:
178 case CMD_FIND:
179 CHECKINT(1);
180 CHECKINT(2);
181 idx = atoi(argv[1]);
182 CHECKVALID(idx);
183 n = atoi(argv[2]);
184
185 if(!rb_findi(trees[idx], n)) {
186 fprintf(stderr, "%d not found\n", n);
187 } else {
188 if(cmd == CMD_DELETE) {
189 rb_deletei(trees[idx], n);
190 printf("deleted %d\n", n);
191 } else {
192 printf("found %d\n", n);
193 }
194 }
195 break;
196
197 case CMD_PRINT:
198 CHECKINT(1);
199 idx = atoi(argv[1]);
200 CHECKVALID(idx);
201
202 rb_begin(trees[idx]);
203 while((node = rb_next(trees[idx]))) {
204 printf("%d ", rb_node_keyi(node));
205 }
206 putchar('\n');
207 break;
208
209 default:
210 /* can't happen */
211 break;
212 }
213 return 0;
214 }