ucw/fit.c

   1 #include "ucw/lib.h"
   2 #include "ucw/fastbuf.h"
   3 #include "ucw/bbuf.h"
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7
   8 struct file {
   9   char *name;
  10   int blocks;
  11 };
  12
  13 int main(int argc, char **argv)
  14 {
  15   if (argc != 3)
  16     die("Usage: du -sb * | fit <block-size> <num-blocks>");
  17   int bs = atol(argv[1]);
  18   int m = atol(argv[2]);
  19
  20   char buf[1024];
  21   struct fastbuf *in = bopen_fd(0, NULL);
  22   bb_t files_buf;
  23   struct file *files = NULL;
  24   int n = 0;
  25   int tb = 0;
  26   bb_init(&files_buf);
  27   while (bgets(in, buf, sizeof(buf)))
  28     {
  29       char *c = strchr(buf, '\t');
  30       if (!c)
  31         die("Syntax error in input: %s", buf);
  32       while (*c == '\t')
  33         *c++ = 0;
  34       files = (struct file *) bb_grow(&files_buf, sizeof(struct file) * (n+1));
  35       files[n].name = xstrdup(c);
  36       files[n].blocks = (atol(buf) + bs - 1) / bs;
  37       printf("#%d: %s (%d blocks)\n", n, files[n].name, files[n].blocks);
  38       tb += files[n].blocks;
  39       n++;
  40     }
  41   printf("%d files of %d blocks total\n\n", n, tb);
  42
  43   char *map = xmalloc_zero(m+1);
  44   map[0] = 1;
  45   for (int i=0; i<n; i++)
  46     {
  47       int s = files[i].blocks;
  48       for (int j=m-s; j>=0; j--)
  49         if (map[j] && !map[j+s])
  50           map[j+s] = 2+i;
  51     }
  52   int max = m;
  53   while (!map[max])
  54     max--;
  55
  56   printf("Found subset with %d blocks of %d (%.2f%%):\n", max, m, 100.*max/m);
  57   int free = m-max;
  58   while (max)
  59     {
  60       int f = map[max]-2;
  61       printf("%7d\t%s\n", files[f].blocks, files[f].name);
  62       max -= files[f].blocks;
  63     }
  64   printf("%7d\t*FREE*\n", free);
  65
  66   return 0;
  67 }