Raphaël G. Git Repositories - carabistouilles/blob - 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 prototype */
  54 struct leaf *lookupLeaf(void **, const char *, unsigned);
  55
  56 /* Main function */
  57 int main(int argc, char **argv) {
  58
  59         /* Stat struct */
  60         struct stat ss;
  61
  62         /* File descriptor */
  63         int fd;
  64
  65         /* Return value */
  66         int ret;
  67
  68         /* Line buffer */
  69         char line[11] = { 0 };
  70
  71         /* Current leaf */
  72         struct leaf *current;
  73
  74         /* Tree root */
  75         struct branch *tree = NULL;
  76
  77         /* Unique counter */
  78         unsigned unique = 0;
  79
  80         /* Duplicated counter */
  81         unsigned duplicate = 0;
  82
  83
  84         /* Check argument count */
  85         if (argc < 2 || argc > 2) {
  86                 fprintf(stderr, "Usage: %s sirens_fxt.txt\n", argv[0]);
  87                 exit(EXIT_FAILURE);
  88         }
  89
  90         /* Stat file */
  91         if (stat(argv[1], &ss) == -1) {
  92                 perror("Stat failed");
  93                 exit(EXIT_FAILURE);
  94         }
  95
  96         /* Check it is a file */
  97         if (!S_ISREG(ss.st_mode)) {
  98                 fprintf(stderr, "%s must be a valid file\n", argv[1]);
  99                 exit(EXIT_FAILURE);
 100         }
 101
 102         /* Check if readable */
 103         if (access(argv[1], R_OK)) {
 104                 fprintf(stderr, "%s must be readable\n", argv[1]);
 105                 exit(EXIT_FAILURE);
 106         }
 107
 108         /* Open file */
 109         if ((fd = open(argv[1], O_RDONLY)) == -1) {
 110                 perror("Open failed");
 111                 exit(EXIT_FAILURE);
 112         }
 113
 114         /* Read file */
 115         do {
 116                 /* Try reading line and check line format */
 117                 if ((ret = read(fd, &line, 10)) == 10 && strspn(line, "0123456789") == 9 && line[9] == '\n') {
 118                         /* Terminate key */
 119                         line[9] = '\0';
 120                         /* Lookup matching leaf */
 121                         current = lookupLeaf((void **)&tree, line, 0);
 122                         /* Grow unique */
 123                         if (current->count == 0) {
 124                                 unique++;
 125                         } else if (current->count == 1) {
 126                                 unique--;
 127                                 duplicate++;
 128                         }
 129                         current->count++;
 130                 /* Handle read error */
 131                 } else if (ret == -1) {
 132                         perror("Read failed");
 133                         exit(EXIT_FAILURE);
 134                 /* Handle partial read or invalid line format */
 135                 } else if (ret > 0) {
 136                         line[ret] = '\0';
 137                         fprintf(stderr, "%s must be filled with lines matching [0-9]{9}LF format; got \"%s\" instead\n", argv[1], line);
 138                         exit(EXIT_FAILURE);
 139                 }
 140         /* Read until end of file */
 141         } while (ret != 0);
 142
 143         /* Close file */
 144         if (close(fd) == -1) {
 145                 perror("Close failed");
 146                 exit(EXIT_FAILURE);
 147         }
 148
 149         /* Print result */
 150         printf("Unique%s: %d, duplicate%s: %d\n", (unique > 1 ? "s" : ""), unique, (duplicate > 1 ? "s" : ""), duplicate);
 151
 152         /* Successful end */
 153         exit(EXIT_SUCCESS);
 154 }
 155
 156 /* Recursive lookup and populate tree function */
 157 struct leaf *lookupLeaf(void **base, const char *key, unsigned index) {
 158         /* Return leaf */
 159         struct leaf *ret;
 160
 161         /* Insert node on empty level */
 162         if (*base == NULL) {
 163                 /* Branch level */
 164                 if (index < 8) {
 165                         *base = malloc(sizeof(struct branch));
 166                         ((struct branch *)*base)->key = key[index] - ZERO_OFFSET;
 167                         ((struct branch *)*base)->next = NULL;
 168                         ((struct branch *)*base)->child = NULL;
 169                         ret = lookupLeaf(&(((struct branch *)*base)->child), key, index + 1);
 170                 /* Leaf level */
 171                 } else {
 172                         *base = malloc(sizeof(struct leaf));
 173                         ((struct leaf *)*base)->key = key[index] - ZERO_OFFSET;
 174                         ((struct leaf *)*base)->next = NULL;
 175                         ((struct leaf *)*base)->count = 0;
 176                         ret = (struct leaf *)*base;
 177                 }
 178         /* Search horizontaly next node */
 179         } else {
 180                 /* Current node for horizontal search */
 181                 void *current = *base, *prev;
 182                 /* Branch level */
 183                 if (index < 8) {
 184                         /* Lookup node matching key or allocate it */
 185                         while(((struct branch *)current)->key != key[index] - ZERO_OFFSET) {
 186                                 /* End of horizontal search */
 187                                 if (((struct branch *)current)->next == NULL) {
 188                                         /* Backup current in prev */
 189                                         prev = current;
 190                                         /* Create new branch with key */
 191                                         current = malloc(sizeof(struct branch));
 192                                         ((struct branch *)current)->key = key[index] - ZERO_OFFSET;
 193                                         ((struct branch *)current)->next = NULL;
 194                                         ((struct branch *)current)->child = NULL;
 195                                         ((struct branch *)prev)->next = (struct branch *)current;
 196                                 } else {
 197                                         /* Pass to next one */
 198                                         current = ((struct branch *)current)->next;
 199                                 }
 200                         }
 201
 202                         /* Lookup leaf or branch in next level */
 203                         ret = lookupLeaf(&(((struct branch *)current)->child), key, index + 1);
 204                 /* Leaf level */
 205                 } else {
 206                         /* Lookup node matching key or allocate it */
 207                         while(((struct leaf *)current)->key != key[index] - ZERO_OFFSET) {
 208                                 /* End of horizontal search */
 209                                 if (((struct leaf *)current)->next == NULL) {
 210                                         /* Backup current in prev */
 211                                         prev = current;
 212                                         /* Create new leaf with key */
 213                                         current = malloc(sizeof(struct leaf));
 214                                         ((struct leaf *)current)->key = key[index] - ZERO_OFFSET;
 215                                         ((struct leaf *)current)->next = NULL;
 216                                         ((struct leaf *)current)->count = 0;
 217                                         ((struct leaf *)prev)->next = (struct leaf *)current;
 218                                 } else {
 219                                         /* Pass to next one */
 220                                         current = ((struct leaf *)current)->next;
 221                                 }
 222                         }
 223
 224                         /* Found leaf, return it */
 225                         ret = (struct leaf *)current;
 226                 }
 227         }
 228
 229         /* Return leaf */
 230         return ret;
 231 }