+/**
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Written by Raphaël Gertz <rapsys@rapsys.eu>
+ */
+
+/* exit EXIT_FAILURE EXIT_SUCCESS */
+#include <stdlib.h>
+
+/* printf */
+#include <stdio.h>
+
+/* stat S_ISREG */
+#include <sys/stat.h>
+
+/* access R_OK */
+#include <unistd.h>
+
+/* open O_RDONLY */
+#include <fcntl.h>
+
+/* strspn */
+#include <string.h>
+
+/* Zero ascii offset */
+#define ZERO_OFFSET 48
+
+/* Branch cell */
+struct branch {
+ unsigned key;
+ struct branch *next;
+ void *child;
+};
+
+/* Leaf cell */
+struct leaf {
+ unsigned key;
+ struct leaf *next;
+ unsigned count;
+};
+
+/* Lookup leaf prototype */
+struct leaf *lookupLeaf(void **, const char *, unsigned);
+
+/* Main function */
+int main(int argc, char **argv) {
+
+ /* Stat struct */
+ struct stat ss;
+
+ /* File descriptor */
+ int fd;
+
+ /* Return value */
+ int ret;
+
+ /* Line buffer */
+ char line[11] = { 0 };
+
+ /* Current leaf */
+ struct leaf *current;
+
+ /* Tree root */
+ struct branch *tree = NULL;
+
+ /* Unique counter */
+ unsigned unique = 0;
+
+ /* Duplicated counter */
+ unsigned duplicate = 0;
+
+
+ /* Check argument count */
+ if (argc < 2 || argc > 2) {
+ fprintf(stderr, "Usage: %s sirens_fxt.txt\n", argv[0]);
+ exit(EXIT_FAILURE);
+ }
+
+ /* Stat file */
+ if (stat(argv[1], &ss) == -1) {
+ perror("Stat failed");
+ exit(EXIT_FAILURE);
+ }
+
+ /* Check it is a file */
+ if (!S_ISREG(ss.st_mode)) {
+ fprintf(stderr, "%s must be a valid file\n", argv[1]);
+ exit(EXIT_FAILURE);
+ }
+
+ /* Check if readable */
+ if (access(argv[1], R_OK)) {
+ fprintf(stderr, "%s must be readable\n", argv[1]);
+ exit(EXIT_FAILURE);
+ }
+
+ /* Open file */
+ if ((fd = open(argv[1], O_RDONLY)) == -1) {
+ perror("Open failed");
+ exit(EXIT_FAILURE);
+ }
+
+ /* Read file */
+ do {
+ /* Try reading line and check line format */
+ if ((ret = read(fd, &line, 10)) == 10 && strspn(line, "0123456789") == 9 && line[9] == '\n') {
+ /* Terminate key */
+ line[9] = '\0';
+ /* Lookup matching leaf */
+ current = lookupLeaf((void **)&tree, line, 0);
+ /* Grow unique */
+ if (current->count == 0) {
+ unique++;
+ } else if (current->count == 1) {
+ unique--;
+ duplicate++;
+ }
+ current->count++;
+ /* Handle read error */
+ } else if (ret == -1) {
+ perror("Read failed");
+ exit(EXIT_FAILURE);
+ /* Handle partial read or invalid line format */
+ } else if (ret > 0) {
+ line[ret] = '\0';
+ fprintf(stderr, "%s must be filled with lines matching [0-9]{9}LF format; got \"%s\" instead\n", argv[1], line);
+ exit(EXIT_FAILURE);
+ }
+ /* Read until end of file */
+ } while (ret != 0);
+
+ /* Close file */
+ if (close(fd) == -1) {
+ perror("Close failed");
+ exit(EXIT_FAILURE);
+ }
+
+ /* Print result */
+ printf("Unique%s: %d, duplicate%s: %d\n", (unique > 1 ? "s" : ""), unique, (duplicate > 1 ? "s" : ""), duplicate);
+
+ /* Successful end */
+ exit(EXIT_SUCCESS);
+}
+
+/* Recursive lookup and populate tree function */
+struct leaf *lookupLeaf(void **base, const char *key, unsigned index) {
+ /* Return leaf */
+ struct leaf *ret;
+
+ /* Insert node on empty level */
+ if (*base == NULL) {
+ /* Branch level */
+ if (index < 8) {
+ *base = malloc(sizeof(struct branch));
+ ((struct branch *)*base)->key = key[index] - ZERO_OFFSET;
+ ((struct branch *)*base)->next = NULL;
+ ((struct branch *)*base)->child = NULL;
+ ret = lookupLeaf(&(((struct branch *)*base)->child), key, index + 1);
+ /* Leaf level */
+ } else {
+ *base = malloc(sizeof(struct leaf));
+ ((struct leaf *)*base)->key = key[index] - ZERO_OFFSET;
+ ((struct leaf *)*base)->next = NULL;
+ ((struct leaf *)*base)->count = 0;
+ ret = (struct leaf *)*base;
+ }
+ /* Search horizontaly next node */
+ } else {
+ /* Current node for horizontal search */
+ void *current = *base, *prev;
+ /* Branch level */
+ if (index < 8) {
+ /* Lookup node matching key or allocate it */
+ while(((struct branch *)current)->key != key[index] - ZERO_OFFSET) {
+ /* End of horizontal search */
+ if (((struct branch *)current)->next == NULL) {
+ /* Backup current in prev */
+ prev = current;
+ /* Create new branch with key */
+ current = malloc(sizeof(struct branch));
+ ((struct branch *)current)->key = key[index] - ZERO_OFFSET;
+ ((struct branch *)current)->next = NULL;
+ ((struct branch *)current)->child = NULL;
+ ((struct branch *)prev)->next = (struct branch *)current;
+ } else {
+ /* Pass to next one */
+ current = ((struct branch *)current)->next;
+ }
+ }
+
+ /* Lookup leaf or branch in next level */
+ ret = lookupLeaf(&(((struct branch *)current)->child), key, index + 1);
+ /* Leaf level */
+ } else {
+ /* Lookup node matching key or allocate it */
+ while(((struct leaf *)current)->key != key[index] - ZERO_OFFSET) {
+ /* End of horizontal search */
+ if (((struct leaf *)current)->next == NULL) {
+ /* Backup current in prev */
+ prev = current;
+ /* Create new leaf with key */
+ current = malloc(sizeof(struct leaf));
+ ((struct leaf *)current)->key = key[index] - ZERO_OFFSET;
+ ((struct leaf *)current)->next = NULL;
+ ((struct leaf *)current)->count = 0;
+ ((struct leaf *)prev)->next = (struct leaf *)current;
+ } else {
+ /* Pass to next one */
+ current = ((struct leaf *)current)->next;
+ }
+ }
+
+ /* Found leaf, return it */
+ ret = (struct leaf *)current;
+ }
+ }
+
+ /* Return leaf */
+ return ret;
+}
Rapsys Git / carabistouilles / commitdiff