$ ./new FOUND BRANCH START FOUND BRANCH START 0 -> 1 (data: 1) printing branches printing branch 0 branch start branch choice start 1 -> 2 (data: 2) branch choice end NULL finished printing branch 0 branch start printing branches printing branch 0 branch choice start 1 -> 2 (data: 2) branch choice end NULL finished printing branch 0 printing branch 1 branch choice start 2 -> 3 (data: 8) branch choice end branch end 3 -> 4 (data: 13) NULL finished printing branch 1 branch choice start printing branches printing branch 0 1 -> 2 (data: 2) branch choice end NULL finished printing branch 0 1 -> 2 (data: 2) printing branches printing branch 0 branch choice end NULL finished printing branch 0 branch choice end NULL printing previous NULL 3 -> 4 (data: 13) branch end branch choice end 2 -> 3 (data: 8) branch choice start branch choice end 1 -> 2 (data: 2) branch choice start branch start 0 -> 1 (data: 1) $ 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); #define LINKED 1 #define TREE 2 #define NODE_TYPE TREE struct QNode { int level; int index; int ref; int data; int type; #if NODE_TYPE == LINKED struct QNode *next; #elif NODE_TYPE == TREE int next_count; struct QNode **next; #endif struct QNode* prev; // Pointer to previous node in DLL }; // The queue, front stores the front node of LL and rear stores ths // last node of LL struct Queue { struct QNode *front, *rear; }; ssize_t free_asm(struct Queue **q) { puts(""); ssize_t frees = 0; if ((q) == NULL) return frees; if ((*q) == NULL) return frees; struct QNode *temp = NULL, *next = NULL; temp = (*q)->front; while (temp) { #if NODE_TYPE == LINKED next = (*q)->front->next; #elif NODE_TYPE == TREE // unknown, would use this /* if (node->next) { if (node->next[0]) { free(node->next[0]); nodes++; } free(node->next); nodes++; */ next = (*q)->front->next[0]; #endif frees++; free(temp); temp = NULL; (*q)->front = next; temp = next; } frees++; free(*q); *q = NULL; return frees; } // 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; #if NODE_TYPE == LINKED #define node_init(t, i, r, d, n) t->index = i; t->ref = r; t->data = d; t->next = n; t->level = global_indent; t->prev = NULL; #elif NODE_TYPE == TREE #define node_init(t, i, r, d, nc, n) t->index = i; t->ref = r; t->data = d; t->next_count = nc; t->next = n; t->level = global_indent; t->prev = NULL; #endif #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_set_free(void) { if (!ptr_list) return -1; POINTER_LIST_TYPE ** pl; for (pl = ptr_list; *pl; pl++) { free(*pl); *pl = NULL; } 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; } // A utility function to create a new linked list node. struct QNode* newNode(int data, int type) { struct QNode *temp = (struct QNode*)malloc(sizeof(*temp)); #if NODE_TYPE == LINKED if (type == STORE_NORMAL) { node_init(temp, index_start++, ref_start++, data, NULL); } else if (type == STORE_EMPTY) { node_init(temp, 0, 0, 0, NULL); } #elif NODE_TYPE == TREE if (type == STORE_NORMAL) { node_init(temp, index_start++, ref_start++, data, 0, NULL); } else if (type == STORE_EMPTY) { node_init(temp, 0, 0, 0, 0, NULL); } #endif return temp; } // A utility function to create an empty queue struct Queue *createQueue() { struct Queue *q = (struct Queue*)malloc(sizeof(*q)); q->front = q->rear = NULL; return q; } int prev_type = 0; int curr_type = 0; void store_asm(struct Queue *q, int data, 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(data, t); temp->type = type; // If queue is empty, then new node is front and rear both if (q->rear == NULL) { temp->prev = NULL; q->front = q->rear = temp; return; } if (prev_type == NODE_TYPE_NORMAL) { if (type == NODE_TYPE_BRANCH_CHOICE_END) { // we reach a the end of a branch choice, add the address of the last reference, the pointer to the next node, to an array of pointers // last_ref = q->rear->ref; // printf("adding %d to the pointer list\n", last_ref); // ptr_add(&q->rear->ref); } } else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) { // we reach a node and we where previously at a branch, set all referenced logged to the value of the current node reference, then we free the pointer list // printf("setting pointer list to %d\n", last_ref); // ptr_set(last_ref); // ptr_free(); } // Add the new node at the end of queue and change rear temp->prev = q->rear; // allocate a new array for our new item #if NODE_TYPE == LINKED if (!q->rear->next) { q->rear->next = malloc(sizeof(*q->rear->next)); } else { abort(); } // update rear->next to point to the new item q->rear->next = temp; // update rear to point to the rear->next, which is the item we just added, updating the pointer rear from our old item to our new item q->rear = q->rear->next; #elif NODE_TYPE == TREE struct QNode * p = q->rear; if (type == NODE_TYPE_BRANCH_CHOICE_START) { while(p) { if (p->type == NODE_TYPE_BRANCH_START) { puts("FOUND BRANCH START"); q->rear = p; break; } if (p->prev) p = p->prev; else p = NULL; } } // allocate a new array for our new item 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); } // update rear->next to point to the new item q->rear->next[q->rear->next_count-1] = temp; // update rear to point to the rear->next, which is the item we just added, updating the pointer rear from our old item to our new item q->rear = q->rear->next[q->rear->next_count-1]; #endif } 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; // check if front->next is NULL, if NULL it means we have reached the end of the queue #if NODE_TYPE == LINKED (*q)->front = (*q)->front->next; #elif NODE_TYPE == TREE if ((*q)->front->next) (*q)->front = (*q)->front->next[0]; else (*q)->front = NULL; #endif // If front becomes NULL, then change rear also as NULL if ((*q)->front == NULL) (*q)->rear = NULL; return temp; } #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); } struct Queue * list = NULL; void printnode(struct QNode * p) { int 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 (data: %d)\n", p->index, p->ref, p->data); } #if NODE_TYPE == TREE // pi(p->next_count) #endif } void print_prev(struct QNode * p) { puts("NULL"); while(p) { printnode(p); if (p->prev) p = p->prev; else p = NULL; } } void print_(struct QNode * p) { while(p) { printnode(p); #if NODE_TYPE == LINKED p = p->next; #elif NODE_TYPE == TREE if (p->next) p = p->next[0]; else p = NULL; #endif } puts("NULL"); } void print(struct QNode * p) { while(p) { printnode(p); #if NODE_TYPE == LINKED p = p->next; #elif NODE_TYPE == TREE if (p->next_count) { puts("printing branches"); for (int i = 0; i < p->next_count; i++) { printf("printing branch %d\n", i); print_(p->next[i]); printf("finished printing branch %d\n", i); } } if (p->next) p = p->next[0]; else p = NULL; #endif } puts("NULL"); } void fix(struct Queue *p); void add(struct Queue **q, int data) { if (!(*q)) (*q) = createQueue(); store_asm((*q), data, NODE_TYPE_NORMAL); } void add_branch(struct Queue **q) { if (!(*q)) (*q) = createQueue(); store_asm((*q), 0, NODE_TYPE_BRANCH_START); global_indent++; } void end_branch(struct Queue **q) { global_indent--; if (!(*q)) (*q) = createQueue(); store_asm((*q), 0, NODE_TYPE_BRANCH_END); } void add_branch_choice(struct Queue **q) { if (!(*q)) (*q) = createQueue(); store_asm((*q), 0, NODE_TYPE_BRANCH_CHOICE_START); global_indent++; } void end_branch_choice(struct Queue **q) { global_indent--; if (!(*q)) (*q) = createQueue(); // if we have a branch_end, we need to go backwards in out linked list to the node that came before the branch start store_asm((*q), 0, NODE_TYPE_BRANCH_CHOICE_END); } int main(void) { index_start = 0; ref_start = 1; /* attempt to visualize this in a expression grammar root ::= 0 A 61 A ::= 1 2 B 5 6 C B ::= 3 4 C ::= 7 8 D D ::= 9 10 F R 57 58 S F ::= G 41 42 P 45 46 47 48 49 Q 52 53 54 G ::= 11 12 H 15 16 I H ::= 13 14 I ::= 17 18 J J ::= 19 20 K N 37 38 O K ::= 21 22 L 25 26 27 28 29 M 32 33 34 L ::= 23 24 M ::= 30 31 N ::= 35 36 O ::= 39 40 P ::= 43 44 Q ::= 50 51 R ::= 55 56 S ::= 59 60 structure: root: 0 A 61 > NULL A: 1 2 B B: 3 4 > 61 // currently 4 > 25 A: 5 6 C C: 7 8 D D: 9 10 F R F: G 41 42 P 45 46 47 > 55 (R) // currently 47 > 52 G: 11 12 H H: 13 14 > 41 // currently 14 > 25 G: 15 16 I I: 16 18 J J: 19 20 K N K: 21 22 L 25 26 27 > 35 (N) // currently 27 > 32 L: 23 24 > 25 K: 28 29 M 32 33 34 > 35 (N) M: 30 31 > 32 N: 35 36 > 41 J: 37 38 O O: 39 40 > 41 P: 43 44 > 45 F: 48 49 Q 52 53 54 > 55 (R) Q: 50 51 > 52 R: 55 56 > 61 D: 57 58 S S: 59 60 > 61 add(&list, 1); add_branch(&list); add_branch_choice(&list); add(&list, 2); add(&list, 3); add_branch(&list); add_branch_choice(&list); add(&list, 4); add(&list, 5); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list, 6); add(&list, 7); add_branch(&list); add_branch_choice(&list); add(&list, 8); add(&list, 9); add_branch(&list); add_branch_choice(&list); add(&list, 10); add(&list, 11); add_branch(&list); add_branch_choice(&list); add_branch(&list); add_branch_choice(&list); add(&list, 12); add(&list, 13); add_branch(&list); add_branch_choice(&list); add(&list, 14); add(&list, 15); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list, 16); add(&list, 17); add_branch(&list); add_branch_choice(&list); add(&list, 18); add(&list, 19); add_branch(&list); add_branch_choice(&list); add(&list, 20); add(&list, 21); add_branch(&list); add_branch_choice(&list); add(&list, 22); add(&list, 23); add_branch(&list); add_branch_choice(&list); add(&list, 24); add(&list, 25); end_branch_choice(&list); end_branch(&list); add(&list, 26); add(&list, 27); add(&list, 28); end_branch_choice(&list); add_branch_choice(&list); add(&list, 29); add(&list, 30); add_branch(&list); add_branch_choice(&list); add(&list, 31); add(&list, 32); end_branch_choice(&list); end_branch(&list); add(&list, 33); add(&list, 34); add(&list, 35); end_branch_choice(&list); end_branch(&list); add_branch(&list); add_branch_choice(&list); add(&list, 36); add(&list, 37); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list, 38); add(&list, 39); add_branch(&list); add_branch_choice(&list); add(&list, 40); add(&list, 41); 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, 42); add(&list, 43); add_branch(&list); add_branch_choice(&list); add(&list, 44); add(&list, 45); end_branch_choice(&list); end_branch(&list); add(&list, 46); add(&list, 47); add(&list, 48); end_branch_choice(&list); add_branch_choice(&list); add(&list, 49); add(&list, 50); add_branch(&list); add_branch_choice(&list); add(&list, 51); add(&list, 52); end_branch_choice(&list); end_branch(&list); add(&list, 53); add(&list, 54); add(&list, 55); end_branch_choice(&list); end_branch(&list); add_branch(&list); add_branch_choice(&list); add(&list, 56); add(&list, 57); end_branch_choice(&list); end_branch(&list); end_branch_choice(&list); add_branch_choice(&list); add(&list, 58); add(&list, 59); add_branch(&list); add_branch_choice(&list); add(&list, 60); add(&list, 61); 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, 62); */ /* attempt to visualize this in a expression grammar root ::= 1 A 13 A ::= 2 3 B 6 7 8 C B ::= 4 C ::= 9 10 D D ::= 11 structure: root: 1 A 13 > NULL A: 2 3 B 6 > 13 B: 4 5 > 6 A: 7 8 C C: 9 10 D D: 11 > 13 */ add(&list, 1); add_branch(&list); add_branch_choice(&list); add(&list, 2); // add(&list, 3); // add_branch(&list); // add_branch_choice(&list); // add(&list, 4); // add(&list, 5); // end_branch_choice(&list); // end_branch(&list); // add(&list, 6); end_branch_choice(&list); add_branch_choice(&list); // add(&list, 7); add(&list, 8); // add_branch(&list); // add_branch_choice(&list); // add(&list, 9); // add(&list, 10); // add_branch(&list); // add_branch_choice(&list); // add(&list, 11); // add(&list, 12); // end_branch_choice(&list); // end_branch(&list); // end_branch_choice(&list); // end_branch(&list); end_branch_choice(&list); end_branch(&list); add(&list, 13); print(list->front); puts("printing previous"); print_prev(list->rear); // fix(list); // this part should be left to the garbage collector to clean up #if NODE_TYPE == LINKED psize_t(free_asm(&list)); #endif return 0; } void print_indentation(struct QNode * p, int indentation) { printf("printing nodes with an indentation level of %d\n", indentation); while(p) { if (p->level == indentation) { 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 (data: %d)\n", p->index, p->ref, p->data); } } #if NODE_TYPE == LINKED p = p->next; #elif NODE_TYPE == TREE if (p->next) p = p->next[0]; else p = NULL; #endif } } void fix(struct Queue * list) { int indent = 0; print_indentation(list->front, indent++); print_indentation(list->front, indent++); print_indentation(list->front, indent++); print_indentation(list->front, indent++); print_indentation(list->front, indent++); puts("NULL"); }