]> Raphaël G. Git Repositories - carabistouilles/blob - analyse.c
Add exercice questions
[carabistouilles] / analyse.c
1 /**
2 * This program is free software: you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License as published by
4 * the Free Software Foundation, either version 3 of the License, or
5 * (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <http://www.gnu.org/licenses/>.
14 *
15 * Written by Raphaël Gertz <rapsys@rapsys.eu>
16 */
17
18 /* exit EXIT_FAILURE EXIT_SUCCESS */
19 #include <stdlib.h>
20
21 /* printf */
22 #include <stdio.h>
23
24 /* stat S_ISREG */
25 #include <sys/stat.h>
26
27 /* access R_OK */
28 #include <unistd.h>
29
30 /* open O_RDONLY */
31 #include <fcntl.h>
32
33 /* strspn */
34 #include <string.h>
35
36 /* Zero ascii offset */
37 #define ZERO_OFFSET 48
38
39 /* Branch cell */
40 struct branch {
41 unsigned key;
42 struct branch *next;
43 void *child;
44 };
45
46 /* Leaf cell */
47 struct leaf {
48 unsigned key;
49 struct leaf *next;
50 unsigned count;
51 };
52
53 /* Lookup leaf function prototype */
54 struct leaf *lookupLeaf(void **, const char *, unsigned);
55
56 /* Freeing node function prototype */
57 void freeTree(void *, unsigned);
58
59 /* Main function */
60 int main(int argc, char **argv) {
61
62 /* Stat struct */
63 struct stat ss;
64
65 /* File descriptor */
66 int fd;
67
68 /* Return value */
69 int ret;
70
71 /* Line buffer */
72 char line[11] = { 0 };
73
74 /* Current leaf */
75 struct leaf *current;
76
77 /* Tree root */
78 struct branch *tree = NULL;
79
80 /* Unique counter */
81 unsigned unique = 0;
82
83 /* Duplicated counter */
84 unsigned duplicate = 0;
85
86
87 /* Check argument count */
88 if (argc < 2 || argc > 2) {
89 fprintf(stderr, "Usage: %s sirens_fxt.txt\n", argv[0]);
90 exit(EXIT_FAILURE);
91 }
92
93 /* Stat file */
94 if (stat(argv[1], &ss) == -1) {
95 perror("Stat failed");
96 exit(EXIT_FAILURE);
97 }
98
99 /* Check it is a file */
100 if (!S_ISREG(ss.st_mode)) {
101 fprintf(stderr, "%s must be a valid file\n", argv[1]);
102 exit(EXIT_FAILURE);
103 }
104
105 /* Check if readable */
106 if (access(argv[1], R_OK)) {
107 fprintf(stderr, "%s must be readable\n", argv[1]);
108 exit(EXIT_FAILURE);
109 }
110
111 /* Open file */
112 if ((fd = open(argv[1], O_RDONLY)) == -1) {
113 perror("Open failed");
114 exit(EXIT_FAILURE);
115 }
116
117 /* Read file */
118 do {
119 /* Try reading line and check line format */
120 if ((ret = read(fd, &line, 10)) == 10 && strspn(line, "0123456789") == 9 && line[9] == '\n') {
121 /* Terminate key */
122 line[9] = '\0';
123 /* Lookup matching leaf */
124 current = lookupLeaf((void **)&tree, line, 0);
125 /* Grow unique */
126 if (current->count == 0) {
127 unique++;
128 } else if (current->count == 1) {
129 unique--;
130 duplicate++;
131 }
132 current->count++;
133 /* Handle read error */
134 } else if (ret == -1) {
135 perror("Read failed");
136 exit(EXIT_FAILURE);
137 /* Handle partial read or invalid line format */
138 } else if (ret > 0) {
139 line[ret] = '\0';
140 fprintf(stderr, "%s must be filled with lines matching [0-9]{9}LF format; got \"%s\" instead\n", argv[1], line);
141 exit(EXIT_FAILURE);
142 }
143 /* Read until end of file */
144 } while (ret != 0);
145
146 /* Free tree */
147 freeTree(tree, 0);
148
149 /* Close file */
150 if (close(fd) == -1) {
151 perror("Close failed");
152 exit(EXIT_FAILURE);
153 }
154
155 /* Print result */
156 printf("Unique%s: %d, duplicate%s: %d\n", (unique > 1 ? "s" : ""), unique, (duplicate > 1 ? "s" : ""), duplicate);
157
158 /* Successful end */
159 exit(EXIT_SUCCESS);
160 }
161
162 /* Recursive freeing of node function */
163 void freeTree(void *base, unsigned index) {
164 void *current = base, *next;
165 if (base != NULL) {
166 /* Branch level */
167 if (index < 8) {
168 /* Free horizontaly */
169 do {
170 /* Free children */
171 if (((struct branch *)current)->child != NULL) {
172 freeTree(((struct branch *)current)->child, index + 1);
173 }
174 /* Free current and switch to next */
175 next = ((struct branch *)current)->next;
176 free(current);
177 current = next;
178 } while (current != NULL);
179 /* Leaf level */
180 } else {
181 /* Free horizontaly */
182 do {
183 /* Free current and switch to next */
184 next = ((struct leaf *)current)->next;
185 free(current);
186 current = next;
187 } while (current != NULL);
188 }
189 }
190 }
191
192 /* Recursive lookup and populate tree function */
193 struct leaf *lookupLeaf(void **base, const char *key, unsigned index) {
194 /* Return leaf */
195 struct leaf *ret;
196
197 /* Insert node on empty level */
198 if (*base == NULL) {
199 /* Branch level */
200 if (index < 8) {
201 *base = malloc(sizeof(struct branch));
202 ((struct branch *)*base)->key = key[index] - ZERO_OFFSET;
203 ((struct branch *)*base)->next = NULL;
204 ((struct branch *)*base)->child = NULL;
205 ret = lookupLeaf(&(((struct branch *)*base)->child), key, index + 1);
206 /* Leaf level */
207 } else {
208 *base = malloc(sizeof(struct leaf));
209 ((struct leaf *)*base)->key = key[index] - ZERO_OFFSET;
210 ((struct leaf *)*base)->next = NULL;
211 ((struct leaf *)*base)->count = 0;
212 ret = (struct leaf *)*base;
213 }
214 /* Search horizontaly next node */
215 } else {
216 /* Current node for horizontal search */
217 void *current = *base, *prev;
218 /* Branch level */
219 if (index < 8) {
220 /* Lookup node matching key or allocate it */
221 while(((struct branch *)current)->key != key[index] - ZERO_OFFSET) {
222 /* End of horizontal search */
223 if (((struct branch *)current)->next == NULL) {
224 /* Backup current in prev */
225 prev = current;
226 /* Create new branch with key */
227 current = malloc(sizeof(struct branch));
228 ((struct branch *)current)->key = key[index] - ZERO_OFFSET;
229 ((struct branch *)current)->next = NULL;
230 ((struct branch *)current)->child = NULL;
231 ((struct branch *)prev)->next = (struct branch *)current;
232 } else {
233 /* Pass to next one */
234 current = ((struct branch *)current)->next;
235 }
236 }
237
238 /* Lookup leaf or branch in next level */
239 ret = lookupLeaf(&(((struct branch *)current)->child), key, index + 1);
240 /* Leaf level */
241 } else {
242 /* Lookup node matching key or allocate it */
243 while(((struct leaf *)current)->key != key[index] - ZERO_OFFSET) {
244 /* End of horizontal search */
245 if (((struct leaf *)current)->next == NULL) {
246 /* Backup current in prev */
247 prev = current;
248 /* Create new leaf with key */
249 current = malloc(sizeof(struct leaf));
250 ((struct leaf *)current)->key = key[index] - ZERO_OFFSET;
251 ((struct leaf *)current)->next = NULL;
252 ((struct leaf *)current)->count = 0;
253 ((struct leaf *)prev)->next = (struct leaf *)current;
254 } else {
255 /* Pass to next one */
256 current = ((struct leaf *)current)->next;
257 }
258 }
259
260 /* Found leaf, return it */
261 ret = (struct leaf *)current;
262 }
263 }
264
265 /* Return leaf */
266 return ret;
267 }