Paste #HlsCV76f7NCqP2v3noxq at spacepaste

$ ./new
last_ref = 5
last_ref = 15
last_ref = 25
last_ref = 25
last_ref = 28
last_ref = 32
last_ref = 32
last_ref = 35
last_ref = 37
last_ref = 41
last_ref = 41
last_ref = 45
last_ref = 45
last_ref = 48
last_ref = 52
last_ref = 52
last_ref = 55
last_ref = 57
last_ref = 61
last_ref = 61
0 -> 1
branch start
branch choice start
1 -> 2
2 -> 3
branch start
branch choice start
3 -> 4
4 -> 25
branch choice end
branch end
branch choice end
branch choice start
5 -> 6
6 -> 7
branch start
branch choice start
7 -> 8
8 -> 9
branch start
branch choice start
9 -> 10
10 -> 11
branch start
branch choice start
branch start
branch choice start
11 -> 12
12 -> 13
branch start
branch choice start
13 -> 14
14 -> 25
branch choice end
branch end
branch choice end
branch choice start
15 -> 16
16 -> 17
branch start
branch choice start
17 -> 18
18 -> 19
branch start
branch choice start
19 -> 20
20 -> 21
branch start
branch choice start
21 -> 22
22 -> 23
branch start
branch choice start
23 -> 24
24 -> 25
branch choice end
branch end
25 -> 26
26 -> 27
27 -> 32
branch choice end
branch choice start
28 -> 29
29 -> 30
branch start
branch choice start
30 -> 31
31 -> 32
branch choice end
branch end
32 -> 33
33 -> 34
34 -> 41
branch choice end
branch end
branch start
branch choice start
35 -> 36
36 -> 41
branch choice end
branch end
branch choice end
branch choice start
37 -> 38
38 -> 39
branch start
branch choice start
39 -> 40
40 -> 41
branch choice end
branch end
branch choice end
branch end
branch choice end
branch end
branch choice end
branch end
41 -> 42
42 -> 43
branch start
branch choice start
43 -> 44
44 -> 45
branch choice end
branch end
45 -> 46
46 -> 47
47 -> 52
branch choice end
branch choice start
48 -> 49
49 -> 50
branch start
branch choice start
50 -> 51
51 -> 52
branch choice end
branch end
52 -> 53
53 -> 54
54 -> 61
branch choice end
branch end
branch start
branch choice start
55 -> 56
56 -> 61
branch choice end
branch end
branch choice end
branch choice start
57 -> 58
58 -> 59
branch start
branch choice start
59 -> 60
60 -> 61
branch choice end
branch end
branch choice end
branch end
branch choice end
branch end
branch choice end
branch end
61 -> 62
NULL
freed 438 nodes
$ cat new.c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define pp(x) printf("%s = %p\n", #x, x);
#define pi(x) printf("%s = %d\n", #x, x);
#define pc(x) printf("%s = %c\n", #x, x);
#define psize_t(x) printf("%s = %zu\n", #x, x);
// A C program to demonstrate linked list based implementation of queue
// A linked list (LL) node to store a queue entry
int index_start = -1;
int ref_start = 0;
int global_indent = 0;
#define node_init(t, i, r, nc, n) t->index = i; t->ref = r; t->next_count = nc; t->next = n; t->level = global_indent;
#define STORE_NORMAL 1
#define STORE_EMPTY 2
#define NODE_TYPE_NORMAL 1
#define NODE_TYPE_BRANCH_START 2
#define NODE_TYPE_BRANCH_END 3
#define NODE_TYPE_BRANCH_CHOICE_START 4
#define NODE_TYPE_BRANCH_CHOICE_END 5
#define POINTER_LIST_TYPE int
POINTER_LIST_TYPE ** ptr_list = NULL;
ssize_t ptr_list_size = 0;
int last_ref = 0;
int ptr_add(POINTER_LIST_TYPE * ptr) {
if (!ptr) return -1;
if (!ptr_list) {
ptr_list = malloc(sizeof(ptr_list)*2);
ptr_list_size++;
}
else if (ptr_list) {
ptr_list = realloc(ptr_list, sizeof(ptr_list)*(ptr_list_size+1));
}
ptr_list[ptr_list_size-1] = ptr;
ptr_list_size++;
ptr_list[ptr_list_size-1] = NULL;
return 0;
}
int ptr_print(void) {
if (!ptr_list) return -1;
POINTER_LIST_TYPE ** pl;
for (pl = ptr_list; *pl; pl++) pp(*pl);
return 0;
}
int ptr_set(POINTER_LIST_TYPE data) {
if (!ptr_list) return -1;
POINTER_LIST_TYPE ** pl;
for (pl = ptr_list; *pl; pl++) **pl = data;
return 0;
}
int ptr_free(void) {
if (!ptr_list) return -1;
POINTER_LIST_TYPE ** pl;
for (pl = ptr_list; *pl; pl++) *pl = NULL;
free(ptr_list);
ptr_list = NULL;
ptr_list_size = 0;
return 0;
}
struct QNode
{
int level;
int index;
int ref;
int next_count;
int type;
struct QNode **next;
};
// The queue, front stores the front node of LL and rear stores ths
// last node of LL
struct Queue
{
struct QNode *front, *rear;
};
// A utility function to create a new linked list node.
struct QNode* newNode(int type)
{
struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
if (type == STORE_NORMAL) {
node_init(temp, index_start++, ref_start++, 0, NULL);
} else if (type == STORE_EMPTY) {
node_init(temp, 0, 0, 0, NULL);
}
return temp;
}
// A utility function to create an empty queue
struct Queue *createQueue()
{
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
int prev_type = 0;
int curr_type = 0;
void store_asm(struct Queue *q, int type)
{
if (curr_type) prev_type = curr_type;
curr_type = type;
// Create a new LL node
int t = 0;
if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
else if (
type == NODE_TYPE_BRANCH_START
||
type == NODE_TYPE_BRANCH_END
||
type == NODE_TYPE_BRANCH_CHOICE_START
||
type == NODE_TYPE_BRANCH_CHOICE_END
) t = STORE_EMPTY;
struct QNode *temp = newNode(t);
temp->type = type;
// If queue is empty, then new node is front and rear both
if (q->rear == NULL)
{
q->front = q->rear = temp;
if (!q->rear->next) {
q->rear->next_count = 1;
q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
} else {
q->rear->next_count++;
q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
}
return;
}
if (prev_type == NODE_TYPE_NORMAL) {
if (type == NODE_TYPE_BRANCH_CHOICE_END) {
// pp(&q->rear->ref)
last_ref = q->rear->ref;
pi(last_ref);
ptr_add(&q->rear->ref);
}
}
else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) {
pi(last_ref);
ptr_set(last_ref);
ptr_free();
}
// Add the new node at the end of queue and change rear
q->rear->next[q->rear->next_count-1] = temp;
q->rear = temp;
if (!q->rear->next) {
q->rear->next_count = 1;
q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
} else {
q->rear->next_count++;
q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
}
}
struct QNode * load_asm(struct Queue **q)
{
// If queue is empty, return NULL.
if ((q) == NULL) return NULL;
if ((*q) == NULL) return NULL;
if ((*q)->front == NULL)
return NULL;
// Store previous front and move front one node ahead
struct QNode *temp = (*q)->front;
(*q)->front = (*q)->front->next[0];
// If front becomes NULL, then change rear also as NULL
if ((*q)->front == NULL)
(*q)->rear = NULL;
return temp;
}
void add(struct Queue **q) {
if (!(*q)) (*q) = createQueue();
store_asm((*q), NODE_TYPE_NORMAL);
}
#define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
struct Queue * list = NULL;
void print(struct QNode * p) {
int indentation = 0;
while(p) {
indentation = p->level;
add_indent(indentation);
if (p->type == NODE_TYPE_BRANCH_START) {
add_indent(indentation);
printf("branch start\n");
}
else if (p->type == NODE_TYPE_BRANCH_END) {
add_indent(indentation);
printf("branch end\n");
}
else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
add_indent(indentation);
printf("branch choice start\n");
}
else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
add_indent(indentation);
printf("branch choice end\n");
}
else if (p->type == NODE_TYPE_NORMAL) {
add_indent(indentation);
printf("%d -> %d\n", p->index, p->ref);
}
if (p->next) p = p->next[0];
else p = NULL;
}
add_indent(indentation);
puts("NULL");
}
void add_branch(struct Queue **q) {
if (!(*q)) (*q) = createQueue();
store_asm((*q), NODE_TYPE_BRANCH_START);
global_indent++;
}
void end_branch(struct Queue **q) {
global_indent--;
if (!(*q)) (*q) = createQueue();
store_asm((*q), NODE_TYPE_BRANCH_END);
}
void add_branch_choice(struct Queue **q) {
if (!(*q)) (*q) = createQueue();
store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
global_indent++;
}
void end_branch_choice(struct Queue **q) {
global_indent--;
if (!(*q)) (*q) = createQueue();
store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
}
int main(void) {
index_start = 0;
ref_start = 1;
add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add(&list); add(&list); add(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add(&list); add(&list); add(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list); add(&list); add_branch(&list); add_branch_choice(&list); add(&list); add(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); end_branch(&list); add(&list);
print(list->front);
ptr_print();
// this part should be left to the garbage collector to clean up
struct QNode * node = load_asm(&list);
ssize_t nodes = 0;
while (node != NULL) {
if (node->next) {
if (node->next[0]) {
free(node->next[0]);
nodes++;
}
free(node->next);
nodes++;
}
free(node);
nodes++;
node = load_asm(&list);
}
free(list);
nodes++;
printf("freed %zu node%s\n", nodes, nodes==1?"":"s");
return 0;
}

spacepaste

Paste details