spacepaste

Paste details

reply | raw

  1.  
  2. $ cat new.c
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  8. #define pp(x) printf("%s = %p\n", #x, x);
  9. #define pi(x) printf("%s = %d\n", #x, x);
  10. #define pc(x) printf("%s = %c\n", #x, x);
  12. // A C program to demonstrate linked list based implementation of queue
  13. // A linked list (LL) node to store a queue entry
  14. int index_start = -1;
  15. int ref_start = 0;
  16. int global_indent = 0;
  18. #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;
  20. #define STORE_NORMAL 1
  21. #define STORE_EMPTY 2
  23. #define NODE_TYPE_NORMAL 1
  24. #define NODE_TYPE_BRANCH_START 2
  25. #define NODE_TYPE_BRANCH_END 3
  26. #define NODE_TYPE_BRANCH_CHOICE_START 4
  27. #define NODE_TYPE_BRANCH_CHOICE_END 5
  29. struct QNode
  30. {
  31. int level;
  32. int index;
  33. int ref;
  34. int next_count;
  35. int type;
  36. struct QNode **next;
  37. };
  39. // The queue, front stores the front node of LL and rear stores ths
  40. // last node of LL
  41. struct Queue
  42. {
  43. struct QNode *front, *rear;
  44. };
  47. // A utility function to create a new linked list node.
  48. struct QNode* newNode(int type)
  49. {
  50. struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
  51. if (type == STORE_NORMAL) {
  52. node_init(temp, index_start++, ref_start++, 0, NULL);
  53. } else if (type == STORE_EMPTY) {
  54. node_init(temp, 0, 0, 0, NULL);
  55. }
  56. return temp;
  57. }
  59. // A utility function to create an empty queue
  60. struct Queue *createQueue()
  61. {
  62. struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
  63. q->front = q->rear = NULL;
  64. return q;
  65. }
  67. void store_asm(struct Queue *q, int type)
  68. {
  69. // Create a new LL node
  70. int t = 0;
  71. if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
  72. else if (
  73. type == NODE_TYPE_BRANCH_START
  74. ||
  75. type == NODE_TYPE_BRANCH_END
  76. ||
  77. type == NODE_TYPE_BRANCH_CHOICE_START
  78. ||
  79. type == NODE_TYPE_BRANCH_CHOICE_END
  80. ) t = STORE_EMPTY;
  81. struct QNode *temp = newNode(t);
  82. temp->type = type;
  84. // If queue is empty, then new node is front and rear both
  85. if (q->rear == NULL)
  86. {
  87. q->front = q->rear = temp;
  88. if (!q->rear->next) {
  89. q->rear->next_count = 1;
  90. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  91. } else {
  92. q->rear->next_count++;
  93. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  94. }
  95. return;
  96. }
  98. // Add the new node at the end of queue and change rear
  99. q->rear->next[q->rear->next_count-1] = temp;
  100. q->rear = temp;
  101. if (!q->rear->next) {
  102. q->rear->next_count = 1;
  103. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  104. } else {
  105. q->rear->next_count++;
  106. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  107. }
  108. }
  110. void add(struct Queue **q) {
  111. if (!(*q)) (*q) = createQueue();
  112. store_asm((*q), NODE_TYPE_NORMAL);
  113. }
  116. #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
  118. struct Queue * list = NULL;
  120. void print(struct QNode * p, int indent) {
  121. int indentation = 0;
  122. while(p) {
  123. indentation = p->level;
  124. add_indent(indentation);
  125. if (p->type == NODE_TYPE_BRANCH_START) {
  126. add_indent(indentation);
  127. printf("branch start\n");
  128. }
  129. else if (p->type == NODE_TYPE_BRANCH_END) {
  130. add_indent(indentation);
  131. printf("branch end\n");
  132. }
  133. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  134. add_indent(indentation);
  135. printf("branch choise start\n");
  136. }
  137. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  138. add_indent(indentation);
  139. printf("branch choise end\n");
  140. }
  141. else if (p->type == NODE_TYPE_NORMAL) {
  142. add_indent(indentation);
  143. printf("%d -> %d\n", p->index, p->ref);
  144. if (p->next_count > 1) print(p->next[1], indent+1);
  145. }
  146. if (p->next) p = p->next[0];
  147. else p = NULL;
  148. }
  149. add_indent(indentation);
  150. puts("NULL");
  151. }
  153. void add_branch(struct Queue **q) {
  154. if (!(*q)) (*q) = createQueue();
  155. store_asm((*q), NODE_TYPE_BRANCH_START);
  156. global_indent++;
  157. }
  159. void end_branch(struct Queue **q) {
  160. global_indent--;
  161. if (!(*q)) (*q) = createQueue();
  162. store_asm((*q), NODE_TYPE_BRANCH_END);
  163. }
  165. void add_branch_choice(struct Queue **q) {
  166. if (!(*q)) (*q) = createQueue();
  167. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
  168. global_indent++;
  169. }
  171. void end_branch_choice(struct Queue **q) {
  172. global_indent--;
  173. if (!(*q)) (*q) = createQueue();
  174. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
  175. }
  177. int main(void) {
  178. index_start = 0;
  179. ref_start = 1;
  180. add(&list);
  181. add_branch(&list);
  182. add_branch_choice(&list);
  183. add(&list);
  184. add(&list);
  185. end_branch_choice(&list);
  186. add_branch_choice(&list);
  187. add(&list);
  188. add(&list);
  189. end_branch_choice(&list);
  190. end_branch(&list);
  191. add(&list);
  193. print(list->front, 0);
  194. return 0;
  195. }
  197. $ gcc new.c -o new
  200. $ ./new
  201. 0 -> 1
  202. branch start
  203. branch choise start
  204. 1 -> 2
  205. 2 -> 3
  206. branch choise end
  207. branch choise start
  208. 3 -> 4
  209. 4 -> 5
  210. branch choise end
  211. branch end
  212. 5 -> 6
  213. NULL
  214.  
Powered by spacepaste. Paste removal.