]>
git.gir.st - base65536.git/blob - generate_struct.c
2 this is a helper program to generate c code for a complete binary
3 search tree, containg the codepoints used for base65536, as defined by
5 why a binary search tree? because i am studying compsci - that's why! :P
6 the struct bnode contains the data in the same format as will be used
7 in the 'real' program, but the btree array is not yet in tree form.
9 execute `gcc -std=c99 generate_struct.c -lm`
11 (C) 2016 Tobias Girstmair, http://isticktoit.net/
12 Released under the GNU GPL v3. See LICENSE for details.
19 int block
; /* index for the blocks, as defined by ferno */
20 int start
; /* start of each block, as defined by ferno */
23 /* it is easier to create a full (perfect) tree, and add those extra bits
24 afterwards to the leftmost node in the bottom row. */
25 struct bnode extra
[] = {
29 struct bnode btree
[] = {
295 int find_part (int n
) {
296 /* http://stackoverflow.com/a/26896494 */
298 while (x
<= n
/2) x
*=2;
300 if (x
/2 - 1 <= (n
-x
)) return x
-1;
304 struct lnode
* gen_tree (struct bnode
* a
, int start
, int end
) {
305 if (start
> end
) return NULL
;
306 //int mid = (end-start)/2+start; //will be right-aligned
307 //int mid = ceil ((end-start)/2.0)+start; //will be half left-, half middle-aligned
308 int mid
= find_part (end
-start
)+start
;
310 struct lnode
* b
= malloc (sizeof (struct lnode
));
311 b
->data
.block
= a
[mid
].block
;
312 b
->data
.start
= a
[mid
].start
;
313 b
->left
= gen_tree (a
, start
, mid
-1);
314 b
->right
= gen_tree (a
, mid
+1, end
);
319 /* to print it breadth first, we need to implement a queue first :| */
324 int empty (struct queue
* q
) {return q
== NULL
;}
325 void prepend (struct queue
** q
, struct lnode
* d
) {
326 struct queue
* tmp
= malloc (sizeof (struct queue
));
331 struct lnode
* get_e (struct queue
* q
, int index
) {
332 for (int i
= 0; i
< index
; q
= q
->next
, i
++);
335 void del_e (struct queue
** q
, int index
) {
337 struct queue
* tmp
= (*q
)->next
;
341 struct queue
* p
= (*q
);
342 for (int i
= 0; i
< index
-1; p
= p
->next
, i
++);
344 p
->next
= p
->next
->next
;
347 void enqueue (struct queue
** q
, struct lnode
* d
, int* size
) {
351 struct lnode
* dequeue (struct queue
** q
, int* size
) {
353 struct lnode
* retval
= get_e (*q
, *size
);
357 void print (struct lnode
* l
) {
358 struct queue
* q
= NULL
;
363 struct lnode
* node
= dequeue (&q
, &s
);
364 if (node
->data
.start
!= 0) printf ("{%d, %d}, \n", node
->data
.block
, node
->data
.start
);
365 if (node
->left
!= NULL
) enqueue (&q
, node
->left
, &s
);
366 if (node
->right
!= NULL
) enqueue (&q
, node
->right
, &s
);
368 // add the extra bits:
369 printf ("{%d, %d}, \n{%d, %d}", extra
[0].block
, extra
[0].start
, extra
[1].block
, extra
[1].start
);
375 struct lnode
* s
= gen_tree (btree
, 0, len
);
378 //NOTE: memory occupied by the tree-as-linked-list is not freed. deal with it.