a

3 files changed, 308 insertions, 0 deletions

diff --git a/build.sh b/build.sh
new file mode 100755
index 0000000..06058c0
--- /dev/null
+++ b/build.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -xe
+
+gcc -o main main.c -Wall -Wextra -pedantic -g
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..6ab79d4
--- /dev/null
+++ b/main.c
@@ -0,0 +1,173 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+
+#define POOL_CAP 512
+
+typedef struct node {
+    bool is_char;
+    char ch;
+
+    size_t references;
+    int direction; // 0 - left; 1 - right
+
+    struct node *parent;
+} node_t;
+
+// void liner_insert(void base[.size * .nmemb + 1],
+//                  size_t nmemb, size_t size, void *el,
+//                  int (*compar)(const void [.size], const void [.size]));
+void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)(const void *, const void *));
+
+int compare_nodes(const void *p1, const void *p2);
+
+void node_char_init(node_t *node, size_t ref, char ch);
+void node_link_init(node_t *node, node_t* left, node_t* right);
+void node_print(node_t *node, int indent);
+
+node_t pool[POOL_CAP];
+size_t pool_sz;
+
+node_t *encoding_table[256];
+
+int main(int argc, char **argv)
+{
+    if(argc != 2) {
+        fprintf(stderr, "ERROR: Not enough command line arguments\n");
+        exit(1);
+    }
+
+    //-------------------------------------------------//
+
+    pool_sz = 0;
+
+    for(int i = 0; i < 256; i++)
+        encoding_table[i] = NULL;
+
+    //-------------------------------------------------//
+    // Load the file data
+    int times_seen[256] = {0};
+
+    FILE *fp = fopen(argv[1], "rb");
+    if(!fp) {
+        fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
+        exit(1);
+    }
+
+    char mem[1024];
+    size_t sz;
+    while((sz = fread(mem, sizeof(char), 1024, fp)) != 0)
+    {
+        for(size_t i = 0; i < sz; i++) {
+            times_seen[(size_t)mem[i]]++;
+        }
+        memset(mem, '\0', sizeof(char) * 1024);
+    }
+    rewind(fp);
+
+    //-------------------------------------------------//
+    // Load everything into nodes array and sort
+
+    node_t *nodes[256];
+    size_t nodes_sz = 0;
+
+    for(int i = 0; i < 256; i++) {
+        if(times_seen[i] <= 0) {
+            continue;
+        }
+
+        nodes[nodes_sz] = malloc(sizeof(node_t));
+        node_char_init(nodes[nodes_sz], times_seen[i], (char)i);
+        encoding_table[i] = nodes[nodes_sz];
+        nodes_sz++;
+    }
+
+    qsort(nodes, nodes_sz, sizeof(node_t *), compare_nodes);
+
+    //-------------------------------------------------//
+    // Continuously sort and build the tree
+
+    while(nodes_sz != 1)
+    {
+        nodes_sz--;
+        node_link_init(&pool[pool_sz], nodes[nodes_sz], nodes[nodes_sz-1]);
+
+        liner_insert(nodes, nodes_sz-1, sizeof(node_t *), &pool[pool_sz++], compare_nodes);
+
+        for(size_t i = 0; i < nodes_sz; i++)
+            node_print(nodes[i], 0);
+    }
+
+
+    //-------------------------------------------------//
+
+    for(int i = 0; i < 256; i++)
+        if(encoding_table[i] != NULL) free(encoding_table[i]);
+    fclose(fp);
+    return 0;
+}
+
+void liner_insert(void *base, size_t nmemb, size_t size, void *el, int (*compar)(const void *, const void *))
+{
+    for(size_t i = 0; i < nmemb; i++)
+    {
+        void *cur = base + (i * size);
+        if(compar(cur, &el) < 0) continue;
+
+        for(size_t j = nmemb; j >= i; j--) {
+            void *src = base + (j * size);
+            void *dest = src + size;
+            memcpy(dest, src, size);
+        }
+
+        memcpy(cur, &el, size);
+        break;
+    }
+}
+
+int compare_nodes(const void *p1, const void *p2)
+{
+    // printf("ff\t%d %d\n", (*(node_t **)p2)->references, (*(node_t **)p1)->references);
+    return (*(node_t **)p2)->references - (*(node_t **)p1)->references;
+}
+
+void node_char_init(node_t *node, size_t ref, char ch)
+{
+    node->is_char = true;
+    node->ch = ch;
+    node->references = ref;
+    node->parent = NULL;
+}
+
+void node_link_init(node_t *node, node_t* left, node_t* right)
+{
+    node->is_char = false;
+    node->references = left->references + right->references;
+    node->parent = NULL;
+
+    left->parent = node;
+    right->parent = node;
+    left->direction = 0;
+    right->direction = 1;
+}
+
+void node_print(node_t *node, int indent)
+{
+    for(int i = 0; i < indent; i++) printf(" ");
+    printf("ref: %ld\n", node->references);
+
+
+    if(node->is_char) {
+        for(int i = 0; i < indent; i++) printf(" ");
+        printf("char: %c\n", node->ch);
+    } else {
+        for(int i = 0; i < indent; i++) printf(" ");
+        printf("link thing\n");
+    }
+
+    if(node->parent != NULL) {
+        for(int i = 0; i < indent; i++) printf(" ");
+        printf("dir: %d\n", node->direction);        node_print(node->parent, indent + 4);
+    }
+}
diff --git a/text.txt b/text.txt
new file mode 100644
index 0000000..67c0ae4
--- /dev/null
+++ b/text.txt
@@ -0,0 +1,130 @@
+This is a text. This is a text. Blah Blah Blah things.
+mmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrrmmmmmmaaaaaaaarrrrrrrrrrrttttttttttttttttyyyyyyyyy
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr
+tttttttttttttuuuuuuuuuuuuuuuuuiiiiiiiiiiiiiiippppp
+fffffffffffffhhhhhhhhhhhhhqqqqqqqqqqqqqqqqrrrrrrr