From 417b15919d381565b8bd6766c535ed5dcf6b87d8 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Rapha=C3=ABl=20Gertz?= Date: Tue, 5 Jul 2016 17:40:48 +0200 Subject: [PATCH] Add analyse.c version --- analyse.c | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 231 insertions(+) create mode 100644 analyse.c diff --git a/analyse.c b/analyse.c new file mode 100644 index 0000000..1adcdd9 --- /dev/null +++ b/analyse.c @@ -0,0 +1,231 @@ +/** + * 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 . + * + * Written by Raphaël Gertz + */ + +/* exit EXIT_FAILURE EXIT_SUCCESS */ +#include + +/* printf */ +#include + +/* stat S_ISREG */ +#include + +/* access R_OK */ +#include + +/* open O_RDONLY */ +#include + +/* strspn */ +#include + +/* 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; +} -- 2.41.1