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 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                         if ((*base = malloc(sizeof(struct branch))) == NULL) {
 202                                 perror("Malloc failed");
 203                                 exit(EXIT_FAILURE);
 204                         }
 205                         ((struct branch *)*base)->key = key[index] - ZERO_OFFSET;
 206                         ((struct branch *)*base)->next = NULL;
 207                         ((struct branch *)*base)->child = NULL;
 208                         ret = lookupLeaf(&(((struct branch *)*base)->child), key, index + 1);
 209                 /* Leaf level */
 210                 } else {
 211                         if ((*base = malloc(sizeof(struct leaf))) == NULL) {
 212                                 perror("Malloc failed");
 213                                 exit(EXIT_FAILURE);
 214                         }
 215                         ((struct leaf *)*base)->key = key[index] - ZERO_OFFSET;
 216                         ((struct leaf *)*base)->next = NULL;
 217                         ((struct leaf *)*base)->count = 0;
 218                         ret = (struct leaf *)*base;
 219                 }
 220         /* Search horizontaly next node */
 221         } else {
 222                 /* Current node for horizontal search */
 223                 void *current = *base, *prev;
 224                 /* Branch level */
 225                 if (index < 8) {
 226                         /* Lookup node matching key or allocate it */
 227                         while(((struct branch *)current)->key != key[index] - ZERO_OFFSET) {
 228                                 /* End of horizontal search */
 229                                 if (((struct branch *)current)->next == NULL) {
 230                                         /* Backup current in prev */
 231                                         prev = current;
 232                                         /* Create new branch with key */
 233                                         if ((current = malloc(sizeof(struct branch))) == NULL) {
 234                                                 perror("Malloc failed");
 235                                                 exit(EXIT_FAILURE);
 236                                         }
 237                                         ((struct branch *)current)->key = key[index] - ZERO_OFFSET;
 238                                         ((struct branch *)current)->next = NULL;
 239                                         ((struct branch *)current)->child = NULL;
 240                                         ((struct branch *)prev)->next = (struct branch *)current;
 241                                 } else {
 242                                         /* Pass to next one */
 243                                         current = ((struct branch *)current)->next;
 244                                 }
 245                         }
 246
 247                         /* Lookup leaf or branch in next level */
 248                         ret = lookupLeaf(&(((struct branch *)current)->child), key, index + 1);
 249                 /* Leaf level */
 250                 } else {
 251                         /* Lookup node matching key or allocate it */
 252                         while(((struct leaf *)current)->key != key[index] - ZERO_OFFSET) {
 253                                 /* End of horizontal search */
 254                                 if (((struct leaf *)current)->next == NULL) {
 255                                         /* Backup current in prev */
 256                                         prev = current;
 257                                         /* Create new leaf with key */
 258                                         if ((current = malloc(sizeof(struct leaf))) == NULL) {
 259                                                 perror("Malloc failed");
 260                                                 exit(EXIT_FAILURE);
 261                                         }
 262                                         ((struct leaf *)current)->key = key[index] - ZERO_OFFSET;
 263                                         ((struct leaf *)current)->next = NULL;
 264                                         ((struct leaf *)current)->count = 0;
 265                                         ((struct leaf *)prev)->next = (struct leaf *)current;
 266                                 } else {
 267                                         /* Pass to next one */
 268                                         current = ((struct leaf *)current)->next;
 269                                 }
 270                         }
 271
 272                         /* Found leaf, return it */
 273                         ret = (struct leaf *)current;
 274                 }
 275         }
 276
 277         /* Return leaf */
 278         return ret;
 279 }