From e5a93f28cb02fa26ae39c70555bf0fc07d447922 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Thu, 6 Dec 2007 12:38:11 +0100
Subject: [PATCH] Fitovatko.

---
 ucw/Makefile | 13 +++++++++++
 ucw/fit.c    | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 78 insertions(+)
 create mode 100644 ucw/Makefile
 create mode 100644 ucw/fit.c

diff --git a/ucw/Makefile b/ucw/Makefile
new file mode 100644
index 0000000..d14e38f
--- /dev/null
+++ b/ucw/Makefile
@@ -0,0 +1,13 @@
+LIBUCW:=$(shell cd ../../sh/main/run && pwd)
+UCWCF:=$(shell PKG_CONFIG_PATH=$(LIBUCW)/lib/pkgconfig pkg-config --cflags libucw)
+UCWLF:=$(shell PKG_CONFIG_PATH=$(LIBUCW)/lib/pkgconfig pkg-config --libs libucw)
+
+CC=gcc
+LD=gcc
+CFLAGS=-O2 -Wall -W -Wno-parentheses -Wstrict-prototypes -Wmissing-prototypes -Wundef -Wredundant-decls -std=gnu99 $(UCWCF)
+LDLIBS+=$(UCWLF)
+
+all: fit
+
+clean:
+	rm -f `find . -name "*~" -or -name "*.[oa]" -or -name "\#*\#" -or -name TAGS -or -name core -or -name .depend -or -name .#*`
diff --git a/ucw/fit.c b/ucw/fit.c
new file mode 100644
index 0000000..b310c12
--- /dev/null
+++ b/ucw/fit.c
@@ -0,0 +1,65 @@
+#include "lib/lib.h"
+#include "lib/fastbuf.h"
+#include "lib/bbuf.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+struct file {
+  char *name;
+  int blocks;
+};
+
+int main(int argc, char **argv)
+{
+  if (argc != 3)
+    die("Usage: du -sb * | fit <block-size> <num-blocks>");
+  int bs = atol(argv[1]);
+  int m = atol(argv[2]);
+
+  char buf[1024];
+  struct fastbuf *in = bopen_fd(0, NULL);
+  bb_t files_buf;
+  struct file *files = NULL;
+  int n = 0;
+  int tb = 0;
+  bb_init(&files_buf);
+  while (bgets(in, buf, sizeof(buf)))
+    {
+      char *c = strchr(buf, '\t');
+      if (!c)
+        die("Syntax error in input: %s", buf);
+      while (*c == '\t')
+        *c++ = 0;
+      files = (struct file *) bb_grow(&files_buf, sizeof(struct file) * (n+1));
+      files[n].name = xstrdup(c);
+      files[n].blocks = (atol(buf) + bs - 1) / bs;
+      printf("#%d: %s (%d blocks)\n", n, files[n].name, files[n].blocks);
+      tb += files[n].blocks;
+      n++;
+    }
+  printf("%d files of %d blocks total\n\n", n, tb);
+
+  char *map = xmalloc_zero(m+1);
+  map[0] = 1;
+  for (int i=0; i<n; i++)
+    {
+      int s = files[i].blocks;
+      for (int j=m-s; j>=0; j--)
+	if (map[j] && !map[j+s])
+	  map[j+s] = 2+i;
+    }
+  int max = m;
+  while (!map[max])
+    max--;
+
+  printf("Found subset with %d blocks:\n", max);
+  while (max)
+    {
+      int f = map[max]-2;
+      printf("%7d\t%s\n", files[f].blocks, files[f].name);
+      max -= files[f].blocks;
+    }
+
+  return 0;
+}
-- 
2.39.2