aocc22

Advent of Code 2022
git clone git://www.tkruger.se/aocc22.git
Log | Files | Refs | README

common.c (2536B)

      1 #include "common.h"
      2 
      3 void tn_init(tn *t, char *name, const size_t size) {
      4   t->name = name;
      5   t->size = size;
      6 
      7   t->children_alloc = TN_DEFAULT_ALLOC;
      8   t->children_n = 0;
      9   t->children = malloc(t->children_alloc * sizeof(*(t->children)));
     10 
     11   t->parent = NULL;
     12 }
     13 
     14 void tn_set_parent(tn *t, tn *pere) { t->parent = pere; }
     15 
     16 void tn_add_child(tn *t, tn *fils) {
     17   if (t->children_n >= t->children_alloc) {
     18     t->children_alloc <<= 1;
     19     t->children =
     20         realloc(t->children, t->children_alloc * sizeof(*(t->children)));
     21   }
     22 
     23   t->children[t->children_n] = fils;
     24   t->children_n++;
     25   fils->parent = t;
     26 }
     27 
     28 void print_tree(tn *t, size_t level) {
     29   size_t i;
     30   for (i = 0; i < level; i++)
     31     printf(" ");
     32   printf("%s (%zu)\n", t->name, t->size);
     33   for (i = 0; i < t->children_n; i++)
     34     print_tree(t->children[i], level + 2);
     35 }
     36 
     37 void tn_cleartree(tn *t) {
     38   size_t i;
     39   for (i = 0; i < t->children_n; i++)
     40     tn_cleartree(t->children[i]);
     41   free(t->children);
     42   free(t);
     43 }
     44 
     45 tn *find_root(tn *t) {
     46   if (t->parent == NULL)
     47     return t;
     48   return find_root(t->parent);
     49 }
     50 
     51 tn *find_child(tn *t, char *s) {
     52   size_t i;
     53   for (i = 0; i < t->children_n; i++) {
     54     if (strcmp(t->children[i]->name, s) == 0)
     55       return t->children[i];
     56   }
     57   return NULL;
     58 }
     59 
     60 tn *parse_input(char **lines, size_t nlines) {
     61   size_t i;
     62 
     63   size_t ralloc = 1;
     64   size_t rn = 0;
     65   tn **r = calloc(ralloc, sizeof(*r));
     66   tn *cp = NULL;
     67 
     68   for (i = 0; i < nlines; i++) {
     69     char *line = lines[i];
     70     if (strncmp(line, "$ cd /", 6) == 0) {
     71       if (rn == 0) {
     72         ralloc = 1;
     73         r[0] = malloc(sizeof(**r));
     74         tn_init(r[0], "", 0);
     75         rn = 1;
     76       }
     77       cp = r[0];
     78     } else if (strncmp(line, "$ cd ..", 7) == 0) {
     79       assert(cp->parent != NULL);
     80       cp = cp->parent;
     81     } else if (strncmp(line, "$ cd ", 5) == 0) {
     82       char *ndir = &line[5];
     83       tn *childp;
     84       if ((childp = find_child(cp, ndir)) == NULL) {
     85         if (rn >= ralloc) {
     86           ralloc <<= 1;
     87           r = realloc(r, ralloc * sizeof(*r));
     88         }
     89 
     90         r[rn] = malloc(sizeof(**r));
     91         tn_init(r[rn], ndir, 0);
     92         childp = r[rn];
     93         rn++;
     94         tn_add_child(cp, childp);
     95       }
     96       cp = childp;
     97     } else if (line[0] != '$' && line[0] != 'd') {
     98       uint64_t tmp;
     99       sread_next_u64(&tmp, line);
    100       cp->size += tmp;
    101     }
    102   }
    103 
    104   tn *root = r[0];
    105   free(r);
    106   return root;
    107 }
    108 
    109 void sum_sizes(tn *t) {
    110   size_t i;
    111   for (i = 0; i < t->children_n; i++) {
    112     sum_sizes(t->children[i]);
    113     t->size += t->children[i]->size;
    114   }
    115 }