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);
  11. #define psize_t(x) printf("%s = %zu\n", #x, x);
  13. // A C program to demonstrate linked list based implementation of queue
  14. // A linked list (LL) node to store a queue entry
  15. int index_start = -1;
  16. int ref_start = 0;
  17. int global_indent = 0;
  19. #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;
  21. #define STORE_NORMAL 1
  22. #define STORE_EMPTY 2
  24. #define NODE_TYPE_NORMAL 1
  25. #define NODE_TYPE_BRANCH_START 2
  26. #define NODE_TYPE_BRANCH_END 3
  27. #define NODE_TYPE_BRANCH_CHOICE_START 4
  28. #define NODE_TYPE_BRANCH_CHOICE_END 5
  30. #define POINTER_LIST_TYPE int
  32. POINTER_LIST_TYPE ** ptr_list = NULL;
  33. ssize_t ptr_list_size = 0;
  35. int last_ref = 0;
  37. int ptr_add(POINTER_LIST_TYPE * ptr) {
  38. if (!ptr) return -1;
  39. POINTER_LIST_TYPE ** pl;
  40. if (!ptr_list) {
  41. ptr_list = malloc(sizeof(ptr_list)*2);
  42. }
  43. else if (ptr_list) {
  44. ptr_list = realloc(ptr_list, sizeof(ptr_list)*(ptr_list_size+1));
  45. }
  46. ptr_list[ptr_list_size] = ptr;
  47. ptr_list_size++;
  48. ptr_list[ptr_list_size] = NULL;
  49. // psize_t(ptr_list_size);
  50. return 0;
  51. }
  53. int ptr_print(void) {
  54. if (!ptr_list) return -1;
  55. POINTER_LIST_TYPE ** pl;
  56. for (pl = ptr_list; *pl; pl++) pp(*pl);
  57. return 0;
  58. }
  60. int ptr_set(POINTER_LIST_TYPE data) {
  61. if (!ptr_list) return -1;
  62. POINTER_LIST_TYPE ** pl;
  63. for (pl = ptr_list; *pl; pl++) **pl = data;
  64. return 0;
  65. }
  67. int ptr_free(void) {
  68. if (!ptr_list) return -1;
  69. POINTER_LIST_TYPE ** pl;
  70. for (pl = ptr_list; *pl; pl++) *pl = NULL;
  71. free(ptr_list);
  72. ptr_list = NULL;
  73. ptr_list_size = 0;
  74. return 0;
  75. }
  77. struct QNode
  78. {
  79. int level;
  80. int index;
  81. int ref;
  82. int next_count;
  83. int type;
  84. struct QNode **next;
  85. };
  87. // The queue, front stores the front node of LL and rear stores ths
  88. // last node of LL
  89. struct Queue
  90. {
  91. struct QNode *front, *rear;
  92. };
  95. // A utility function to create a new linked list node.
  96. struct QNode* newNode(int type)
  97. {
  98. struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
  99. if (type == STORE_NORMAL) {
  100. node_init(temp, index_start++, ref_start++, 0, NULL);
  101. } else if (type == STORE_EMPTY) {
  102. node_init(temp, 0, 0, 0, NULL);
  103. }
  104. return temp;
  105. }
  107. // A utility function to create an empty queue
  108. struct Queue *createQueue()
  109. {
  110. struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
  111. q->front = q->rear = NULL;
  112. return q;
  113. }
  115. void store_asm(struct Queue *q, int type)
  116. {
  117. // Create a new LL node
  118. int t = 0;
  119. if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
  120. else if (
  121. type == NODE_TYPE_BRANCH_START
  122. ||
  123. type == NODE_TYPE_BRANCH_END
  124. ||
  125. type == NODE_TYPE_BRANCH_CHOICE_START
  126. ||
  127. type == NODE_TYPE_BRANCH_CHOICE_END
  128. ) t = STORE_EMPTY;
  129. struct QNode *temp = newNode(t);
  130. temp->type = type;
  132. // If queue is empty, then new node is front and rear both
  133. if (q->rear == NULL)
  134. {
  135. q->front = q->rear = temp;
  136. if (!q->rear->next) {
  137. q->rear->next_count = 1;
  138. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  139. } else {
  140. q->rear->next_count++;
  141. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  142. }
  143. return;
  144. }
  145. if (type == NODE_TYPE_BRANCH_CHOICE_END) {
  146. // pp(&q->rear->ref)
  147. last_ref = q->rear->ref;
  148. ptr_add(&q->rear->ref);
  149. }
  150. else if(type == NODE_TYPE_BRANCH_END) {
  151. // pi(last_ref);
  152. ptr_set(last_ref);
  153. ptr_free();
  154. }
  155. // Add the new node at the end of queue and change rear
  156. q->rear->next[q->rear->next_count-1] = temp;
  157. q->rear = temp;
  158. if (!q->rear->next) {
  159. q->rear->next_count = 1;
  160. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  161. } else {
  162. q->rear->next_count++;
  163. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  164. }
  165. }
  167. void add(struct Queue **q) {
  168. if (!(*q)) (*q) = createQueue();
  169. store_asm((*q), NODE_TYPE_NORMAL);
  170. }
  173. #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
  175. struct Queue * list = NULL;
  177. void print(struct QNode * p, int indent) {
  178. int indentation = 0;
  179. while(p) {
  180. indentation = p->level;
  181. add_indent(indentation);
  182. if (p->type == NODE_TYPE_BRANCH_START) {
  183. add_indent(indentation);
  184. printf("branch start\n");
  185. }
  186. else if (p->type == NODE_TYPE_BRANCH_END) {
  187. add_indent(indentation);
  188. printf("branch end\n");
  189. }
  190. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  191. add_indent(indentation);
  192. printf("branch choice start\n");
  193. }
  194. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  195. add_indent(indentation);
  196. printf("branch choice end\n");
  197. }
  198. else if (p->type == NODE_TYPE_NORMAL) {
  199. add_indent(indentation);
  200. printf("%d -> %d\n", p->index, p->ref);
  201. if (p->next_count > 1) print(p->next[1], indent+1);
  202. }
  203. if (p->next) p = p->next[0];
  204. else p = NULL;
  205. }
  206. add_indent(indentation);
  207. puts("NULL");
  208. }
  210. void add_branch(struct Queue **q) {
  211. if (!(*q)) (*q) = createQueue();
  212. store_asm((*q), NODE_TYPE_BRANCH_START);
  213. global_indent++;
  214. }
  216. void end_branch(struct Queue **q) {
  217. global_indent--;
  218. if (!(*q)) (*q) = createQueue();
  219. store_asm((*q), NODE_TYPE_BRANCH_END);
  220. }
  222. void add_branch_choice(struct Queue **q) {
  223. if (!(*q)) (*q) = createQueue();
  224. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
  225. global_indent++;
  226. }
  228. void end_branch_choice(struct Queue **q) {
  229. global_indent--;
  230. if (!(*q)) (*q) = createQueue();
  231. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
  232. }
  234. int main(void) {
  235. index_start = 0;
  236. ref_start = 1;
  237. add(&list);
  238. add_branch(&list);
  239. add_branch_choice(&list);
  240. add(&list);
  241. add(&list);
  242. end_branch_choice(&list);
  243. add_branch_choice(&list);
  244. add(&list);
  245. add(&list);
  246. end_branch_choice(&list);
  247. end_branch(&list);
  248. add(&list);
  250. print(list->front, 0);
  251. ptr_print();
  252. return 0;
  253. }
  255. $ gcc new.c -o new
  258. $ ./new
  259. 0 -> 1
  260. branch start
  261. branch choice start
  262. 1 -> 2
  263. 2 -> 5
  264. branch choice end
  265. branch choice start
  266. 3 -> 4
  267. 4 -> 5
  268. branch choice end
  269. branch end
  270. 5 -> 6
  271. NULL
  272.  
Powered by spacepaste. Paste removal.