fix -Werror=misleading-indentation

[base65536.git] / generate_struct.c

/*
        this is a helper program to generate c code for a complete binary
        search tree, containg the codepoints used for base65536, as defined by
        github user ferno. 
        why a binary search tree? because i am studying compsci - that's why! :P
        the struct bnode contains the data in the same format as will be used
        in the 'real' program, but the btree array is not yet in tree form. 

        execute `gcc -std=c99 generate_struct.c -lm`

        (C) 2016 Tobias Girstmair, http://isticktoit.net/
        Released under the GNU GPL v3. See LICENSE for details.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct bnode {
        int block; /* index for the blocks, as defined by ferno */
        int start; /* start of each block, as defined by ferno */
};

/*      it is easier to create a full (perfect) tree, and add those extra bits
        afterwards to the leftmost node in the bottom row. */
struct bnode extra [] = {
        {-1, 5376},
        {1, 13568}
};
struct bnode btree [] = {
/*      {-1, 5376},*/
        {0, 13312}, 
/*      {1, 13568}, */
        {2, 13824}, 
        {3, 14080}, 
        {4, 14336}, 
        {5, 14592}, 
        {6, 14848}, 
        {7, 15104}, 
        {8, 15360}, 
        {9, 15616}, 
        {10, 15872}, 
        {11, 16128}, 
        {12, 16384}, 
        {13, 16640}, 
        {14, 16896}, 
        {15, 17152}, 
        {16, 17408}, 
        {17, 17664}, 
        {18, 17920}, 
        {19, 18176}, 
        {20, 18432}, 
        {21, 18688}, 
        {22, 18944}, 
        {23, 19200}, 
        {24, 19456}, 
        {25, 19968}, 
        {26, 20224}, 
        {27, 20480}, 
        {28, 20736}, 
        {29, 20992}, 
        {30, 21248}, 
        {31, 21504}, 
        {32, 21760}, 
        {33, 22016}, 
        {34, 22272}, 
        {35, 22528}, 
        {36, 22784}, 
        {37, 23040}, 
        {38, 23296}, 
        {39, 23552}, 
        {40, 23808}, 
        {41, 24064}, 
        {42, 24320}, 
        {43, 24576}, 
        {44, 24832}, 
        {45, 25088}, 
        {46, 25344}, 
        {47, 25600}, 
        {48, 25856}, 
        {49, 26112}, 
        {50, 26368}, 
        {51, 26624}, 
        {52, 26880}, 
        {53, 27136}, 
        {54, 27392}, 
        {55, 27648}, 
        {56, 27904}, 
        {57, 28160}, 
        {58, 28416}, 
        {59, 28672}, 
        {60, 28928}, 
        {61, 29184}, 
        {62, 29440}, 
        {63, 29696}, 
        {64, 29952}, 
        {65, 30208}, 
        {66, 30464}, 
        {67, 30720}, 
        {68, 30976}, 
        {69, 31232}, 
        {70, 31488}, 
        {71, 31744}, 
        {72, 32000}, 
        {73, 32256}, 
        {74, 32512}, 
        {75, 32768}, 
        {76, 33024}, 
        {77, 33280}, 
        {78, 33536}, 
        {79, 33792}, 
        {80, 34048}, 
        {81, 34304}, 
        {82, 34560}, 
        {83, 34816}, 
        {84, 35072}, 
        {85, 35328}, 
        {86, 35584}, 
        {87, 35840}, 
        {88, 36096}, 
        {89, 36352}, 
        {90, 36608}, 
        {91, 36864}, 
        {92, 37120}, 
        {93, 37376}, 
        {94, 37632}, 
        {95, 37888}, 
        {96, 38144}, 
        {97, 38400}, 
        {98, 38656}, 
        {99, 38912}, 
        {100, 39168}, 
        {101, 39424}, 
        {102, 39680}, 
        {103, 39936}, 
        {104, 40192}, 
        {105, 40448}, 
        {106, 41216}, 
        {107, 41472}, 
        {108, 41728}, 
        {109, 42240}, 
        {110, 67072}, 
        {111, 73728}, 
        {112, 73984}, 
        {113, 74240}, 
        {114, 77824}, 
        {115, 78080}, 
        {116, 78336}, 
        {117, 78592}, 
        {118, 82944}, 
        {119, 83200}, 
        {120, 92160}, 
        {121, 92416}, 
        {122, 131072}, 
        {123, 131328}, 
        {124, 131584}, 
        {125, 131840}, 
        {126, 132096}, 
        {127, 132352}, 
        {128, 132608}, 
        {129, 132864}, 
        {130, 133120}, 
        {131, 133376}, 
        {132, 133632}, 
        {133, 133888}, 
        {134, 134144}, 
        {135, 134400}, 
        {136, 134656}, 
        {137, 134912}, 
        {138, 135168}, 
        {139, 135424}, 
        {140, 135680}, 
        {141, 135936}, 
        {142, 136192}, 
        {143, 136448}, 
        {144, 136704}, 
        {145, 136960}, 
        {146, 137216}, 
        {147, 137472}, 
        {148, 137728}, 
        {149, 137984}, 
        {150, 138240}, 
        {151, 138496}, 
        {152, 138752}, 
        {153, 139008}, 
        {154, 139264}, 
        {155, 139520}, 
        {156, 139776}, 
        {157, 140032}, 
        {158, 140288}, 
        {159, 140544}, 
        {160, 140800}, 
        {161, 141056}, 
        {162, 141312}, 
        {163, 141568}, 
        {164, 141824}, 
        {165, 142080}, 
        {166, 142336}, 
        {167, 142592}, 
        {168, 142848}, 
        {169, 143104}, 
        {170, 143360}, 
        {171, 143616}, 
        {172, 143872}, 
        {173, 144128}, 
        {174, 144384}, 
        {175, 144640}, 
        {176, 144896}, 
        {177, 145152}, 
        {178, 145408}, 
        {179, 145664}, 
        {180, 145920}, 
        {181, 146176}, 
        {182, 146432}, 
        {183, 146688}, 
        {184, 146944}, 
        {185, 147200}, 
        {186, 147456}, 
        {187, 147712}, 
        {188, 147968}, 
        {189, 148224}, 
        {190, 148480}, 
        {191, 148736}, 
        {192, 148992}, 
        {193, 149248}, 
        {194, 149504}, 
        {195, 149760}, 
        {196, 150016}, 
        {197, 150272}, 
        {198, 150528}, 
        {199, 150784}, 
        {200, 151040}, 
        {201, 151296}, 
        {202, 151552}, 
        {203, 151808}, 
        {204, 152064}, 
        {205, 152320}, 
        {206, 152576}, 
        {207, 152832}, 
        {208, 153088}, 
        {209, 153344}, 
        {210, 153600}, 
        {211, 153856}, 
        {212, 154112}, 
        {213, 154368}, 
        {214, 154624}, 
        {215, 154880}, 
        {216, 155136}, 
        {217, 155392}, 
        {218, 155648}, 
        {219, 155904}, 
        {220, 156160}, 
        {221, 156416}, 
        {222, 156672}, 
        {223, 156928}, 
        {224, 157184}, 
        {225, 157440}, 
        {226, 157696}, 
        {227, 157952}, 
        {228, 158208}, 
        {229, 158464}, 
        {230, 158720}, 
        {231, 158976}, 
        {232, 159232}, 
        {233, 159488}, 
        {234, 159744}, 
        {235, 160000}, 
        {236, 160256}, 
        {237, 160512}, 
        {238, 160768}, 
        {239, 161024}, 
        {240, 161280}, 
        {241, 161536}, 
        {242, 161792}, 
        {243, 162048}, 
        {244, 162304}, 
        {245, 162560}, 
        {246, 162816}, 
        {247, 163072}, 
        {248, 163328}, 
        {249, 163584}, 
        {250, 163840}, 
        {251, 164096}, 
        {252, 164352}, 
        {253, 164608}, 
        {254, 164864}, 
        {255, 165120} 
};

struct lnode {
        struct bnode data;
        struct lnode* left;
        struct lnode* right;
};

int find_part (int n) {
        /* http://stackoverflow.com/a/26896494 */
        int x = 1;
        while (x <= n/2) x*=2;

        if (x/2 - 1 <= (n-x)) return x-1;
        else return n - x/2;
}

struct lnode* gen_tree (struct bnode* a, int start, int end) {
        if (start > end) return NULL;
        //int mid = (end-start)/2+start; //will be right-aligned
        //int mid = ceil ((end-start)/2.0)+start; //will be half left-, half middle-aligned
        int mid = find_part (end-start)+start;

        struct lnode* b = malloc (sizeof (struct lnode));
        b->data.block = a[mid].block;
        b->data.start = a[mid].start;
        b->left = gen_tree (a, start, mid-1);
        b->right = gen_tree (a, mid+1, end);

        return b;
}

/* to print it breadth first, we need to implement a queue first :| */
struct queue {
        struct lnode* data;
        struct queue* next;
};
int empty (struct queue* q) {return q == NULL;}
void prepend (struct queue** q, struct lnode* d) {
        struct queue* tmp = malloc (sizeof (struct queue));
        tmp->data = d;
        tmp->next = *q;
        *q = tmp;
}
struct lnode* get_e (struct queue* q, int index) {
        for (int i = 0; i < index; q = q->next, i++);
        return q->data;
}
void del_e (struct queue** q, int index) {
        if (index == 0) {
                struct queue* tmp = (*q)->next;
                free (*q);
                (*q) = tmp;
        } else {
                struct queue* p = (*q);
                for (int i = 0; i < index-1; p = p->next, i++);
                free (p->next);
                p->next = p->next->next;
        }
}
void enqueue (struct queue** q, struct lnode* d, int* size) {
        prepend (q, d);
        (*size)++;
}
struct lnode* dequeue (struct queue** q, int* size) {
        (*size)--;
        struct lnode* retval = get_e (*q, *size);
        del_e (q, *size);
        return retval;
}
void print (struct lnode* l) {
        struct queue* q = NULL;
        int s = 0;

        enqueue (&q, l, &s);
        while (!empty (q)) {
                struct lnode* node = dequeue (&q, &s);
                if (node->data.start != 0) printf ("{%d, %d}, \n", node->data.block, node->data.start);
                if (node->left != NULL) enqueue (&q, node->left, &s);
                if (node->right != NULL) enqueue (&q, node->right, &s);
        }
        // add the extra bits:
        printf ("{%d, %d}, \n{%d, %d}", extra[0].block, extra[0].start, extra[1].block, extra[1].start);
}


int main () {
        int len = 255;
        struct lnode* s = gen_tree (btree, 0, len);
        print (s);

        //NOTE: memory occupied by the tree-as-linked-list is not freed. deal with it. 
}