$ ./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 #include #include #include #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; }