spacepaste

  1.  
  2. #include <stdbool.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #define pp(x) printf("%s = %p\n", #x, x);
  7. #define pi(x) printf("%s = %d\n", #x, x);
  8. #define pc(x) printf("%s = %c\n", #x, x);
  9. #define psize_t(x) printf("%s = %zu\n", #x, x);
  10. // A C program to demonstrate linked list based implementation of queue
  11. // A linked list (LL) node to store a queue entry
  12. int index_start = -1;
  13. int ref_start = 0;
  14. int global_indent = 0;
  15. #define node_init(t, i, r, n) t->index = i; t->ref = r; t->next = n; t->level = global_indent;
  16. #define STORE_NORMAL 1
  17. #define STORE_EMPTY 2
  18. #define NODE_TYPE_NORMAL 1
  19. #define NODE_TYPE_BRANCH_START 2
  20. #define NODE_TYPE_BRANCH_END 3
  21. #define NODE_TYPE_BRANCH_CHOICE_START 4
  22. #define NODE_TYPE_BRANCH_CHOICE_END 5
  23. #define POINTER_LIST_TYPE int
  24. POINTER_LIST_TYPE ** ptr_list = NULL;
  25. ssize_t ptr_list_size = 0;
  26. int last_ref = 0;
  27. int ptr_add(POINTER_LIST_TYPE * ptr) {
  28. if (!ptr) return -1;
  29. if (!ptr_list) {
  30. ptr_list = malloc(sizeof(ptr_list)*2);
  31. ptr_list_size++;
  32. }
  33. else if (ptr_list) {
  34. ptr_list = realloc(ptr_list, sizeof(ptr_list)*(ptr_list_size+1));
  35. }
  36. ptr_list[ptr_list_size-1] = ptr;
  37. ptr_list_size++;
  38. ptr_list[ptr_list_size-1] = NULL;
  39. return 0;
  40. }
  41. int ptr_print(void) {
  42. if (!ptr_list) return -1;
  43. POINTER_LIST_TYPE ** pl;
  44. for (pl = ptr_list; *pl; pl++) pp(*pl);
  45. return 0;
  46. }
  47. int ptr_set(POINTER_LIST_TYPE data) {
  48. if (!ptr_list) return -1;
  49. POINTER_LIST_TYPE ** pl;
  50. for (pl = ptr_list; *pl; pl++) **pl = data;
  51. return 0;
  52. }
  53. int ptr_set_free(void) {
  54. if (!ptr_list) return -1;
  55. POINTER_LIST_TYPE ** pl;
  56. for (pl = ptr_list; *pl; pl++) {
  57. free(*pl);
  58. *pl = NULL;
  59. }
  60. return 0;
  61. }
  62. int ptr_free(void) {
  63. if (!ptr_list) return -1;
  64. POINTER_LIST_TYPE ** pl;
  65. for (pl = ptr_list; *pl; pl++) *pl = NULL;
  66. free(ptr_list);
  67. ptr_list = NULL;
  68. ptr_list_size = 0;
  69. return 0;
  70. }
  71. struct QNode
  72. {
  73. int level;
  74. int index;
  75. int ref;
  76. int type;
  77. struct QNode *next;
  78. };
  79. // The queue, front stores the front node of LL and rear stores ths
  80. // last node of LL
  81. struct Queue
  82. {
  83. struct QNode *front, *rear;
  84. };
  85. // A utility function to create a new linked list node.
  86. struct QNode* newNode(int type)
  87. {
  88. struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
  89. if (type == STORE_NORMAL) {
  90. node_init(temp, index_start++, ref_start++, NULL);
  91. } else if (type == STORE_EMPTY) {
  92. node_init(temp, 0, 0, NULL);
  93. }
  94. return temp;
  95. }
  96. // A utility function to create an empty queue
  97. struct Queue *createQueue()
  98. {
  99. struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
  100. q->front = q->rear = NULL;
  101. return q;
  102. }
  103. int prev_type = 0;
  104. int curr_type = 0;
  105. void store_asm(struct Queue *q, int type)
  106. {
  107. if (curr_type) prev_type = curr_type;
  108. curr_type = type;
  109. // Create a new LL node
  110. int t = 0;
  111. if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
  112. else if (
  113. type == NODE_TYPE_BRANCH_START
  114. ||
  115. type == NODE_TYPE_BRANCH_END
  116. ||
  117. type == NODE_TYPE_BRANCH_CHOICE_START
  118. ||
  119. type == NODE_TYPE_BRANCH_CHOICE_END
  120. ) t = STORE_EMPTY;
  121. struct QNode *temp = newNode(t);
  122. temp->type = type;
  123. // If queue is empty, then new node is front and rear both
  124. if (q->rear == NULL)
  125. {
  126. q->front = q->rear = temp;
  127. return;
  128. }
  129. if (prev_type == NODE_TYPE_NORMAL) {
  130. if (type == NODE_TYPE_BRANCH_CHOICE_END) {
  131. // pp(&q->rear->ref)
  132. last_ref = q->rear->ref;
  133. pi(last_ref);
  134. ptr_add(&q->rear->ref);
  135. }
  136. }
  137. else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) {
  138. pi(last_ref);
  139. ptr_set(last_ref);
  140. ptr_free();
  141. }
  142. // Add the new node at the end of queue and change rear
  143. // allocate a new array for our new item
  144. if (!q->rear->next) {
  145. q->rear->next = malloc(sizeof(struct QNode));
  146. } else {
  147. abort();
  148. }
  149. // update rear->next to point to the new item
  150. q->rear->next = temp;
  151. // 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
  152. q->rear = q->rear->next;
  153. }
  154. struct QNode * load_asm(struct Queue **q)
  155. {
  156. // If queue is empty, return NULL.
  157. if ((q) == NULL) return NULL;
  158. if ((*q) == NULL) return NULL;
  159. if ((*q)->front == NULL)
  160. return NULL;
  161. // Store previous front and move front one node ahead
  162. struct QNode *temp = (*q)->front;
  163. // check if front->next is NULL, if NULL it means we have reached the end of the queue
  164. (*q)->front = (*q)->front->next;
  165. // If front becomes NULL, then change rear also as NULL
  166. if ((*q)->front == NULL)
  167. (*q)->rear = NULL;
  168. return temp;
  169. }
  170. ssize_t free_asm(struct Queue **q)
  171. {
  172. puts("");
  173. pp(*q)
  174. ssize_t frees = 0;
  175. // If queue is empty, return NULL.
  176. if ((q) == NULL) return frees;
  177. if ((*q) == NULL) return frees;
  178. struct QNode *temp = NULL, *next = NULL;
  179. temp = (*q)->front;
  180. while (temp) {
  181. next = (*q)->front->next;
  182. frees++;
  183. free(temp);
  184. temp = NULL;
  185. (*q)->front = next;
  186. temp = next;
  187. // pp((*q)->front)
  188. // // Store previous front and move front one node ahead
  189. // ptr_add((*q)->front);
  190. // // check if front->next is NULL, if NULL it means we have reached the end of the queue
  191. //
  192. // // If front becomes NULL, then change rear also as NULL
  193. // if ((*q)->front == NULL)
  194. // (*q)->rear = NULL;
  195. }
  196. frees++;
  197. free(*q);
  198. *q = NULL;
  199. // ptr_add(*q);
  200. // ptr_print();
  201. // ptr_set_free();
  202. // ptr_free();
  203. return frees;
  204. }
  205. void add(struct Queue **q) {
  206. if (!(*q)) (*q) = createQueue();
  207. store_asm((*q), NODE_TYPE_NORMAL);
  208. }
  209. #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
  210. struct Queue * list = NULL;
  211. void print(struct QNode * p) {
  212. int indentation = 0;
  213. while(p) {
  214. indentation = p->level;
  215. add_indent(indentation);
  216. if (p->type == NODE_TYPE_BRANCH_START) {
  217. add_indent(indentation);
  218. printf("branch start\n");
  219. }
  220. else if (p->type == NODE_TYPE_BRANCH_END) {
  221. add_indent(indentation);
  222. printf("branch end\n");
  223. }
  224. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  225. add_indent(indentation);
  226. printf("branch choice start\n");
  227. }
  228. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  229. add_indent(indentation);
  230. printf("branch choice end\n");
  231. }
  232. else if (p->type == NODE_TYPE_NORMAL) {
  233. add_indent(indentation);
  234. printf("%d -> %d\n", p->index, p->ref);
  235. }
  236. p = p->next;
  237. }
  238. add_indent(indentation);
  239. puts("NULL");
  240. }
  241. void add_branch(struct Queue **q) {
  242. if (!(*q)) (*q) = createQueue();
  243. store_asm((*q), NODE_TYPE_BRANCH_START);
  244. global_indent++;
  245. }
  246. void end_branch(struct Queue **q) {
  247. global_indent--;
  248. if (!(*q)) (*q) = createQueue();
  249. store_asm((*q), NODE_TYPE_BRANCH_END);
  250. }
  251. void add_branch_choice(struct Queue **q) {
  252. if (!(*q)) (*q) = createQueue();
  253. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
  254. global_indent++;
  255. }
  256. void end_branch_choice(struct Queue **q) {
  257. global_indent--;
  258. if (!(*q)) (*q) = createQueue();
  259. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
  260. }
  261. int main(void) {
  262. index_start = 0;
  263. ref_start = 1;
  264. add(&list);
  265. add_branch(&list);
  266. add_branch_choice(&list);
  267. add(&list);
  268. add(&list);
  269. add_branch(&list);
  270. add_branch_choice(&list);
  271. add(&list);
  272. add(&list);
  273. end_branch_choice(&list);
  274. end_branch(&list);
  275. end_branch_choice(&list);
  276. add_branch_choice(&list);
  277. add(&list);
  278. add(&list);
  279. add_branch(&list);
  280. add_branch_choice(&list);
  281. add(&list);
  282. add(&list);
  283. add_branch(&list);
  284. add_branch_choice(&list);
  285. add(&list);
  286. add(&list);
  287. add_branch(&list);
  288. add_branch_choice(&list);
  289. add_branch(&list);
  290. add_branch_choice(&list);
  291. add(&list);
  292. add(&list);
  293. add_branch(&list);
  294. add_branch_choice(&list);
  295. add(&list);
  296. add(&list);
  297. end_branch_choice(&list);
  298. end_branch(&list);
  299. end_branch_choice(&list);
  300. add_branch_choice(&list);
  301. add(&list);
  302. add(&list);
  303. add_branch(&list);
  304. add_branch_choice(&list);
  305. add(&list);
  306. add(&list);
  307. add_branch(&list);
  308. add_branch_choice(&list);
  309. add(&list);
  310. add(&list);
  311. add_branch(&list);
  312. add_branch_choice(&list);
  313. add(&list);
  314. add(&list);
  315. add_branch(&list);
  316. add_branch_choice(&list);
  317. add(&list);
  318. add(&list);
  319. end_branch_choice(&list);
  320. end_branch(&list);
  321. add(&list);
  322. add(&list);
  323. add(&list);
  324. end_branch_choice(&list);
  325. add_branch_choice(&list);
  326. add(&list);
  327. add(&list);
  328. add_branch(&list);
  329. add_branch_choice(&list);
  330. add(&list);
  331. add(&list);
  332. end_branch_choice(&list);
  333. end_branch(&list);
  334. add(&list);
  335. add(&list);
  336. add(&list);
  337. end_branch_choice(&list);
  338. end_branch(&list);
  339. add_branch(&list);
  340. add_branch_choice(&list);
  341. add(&list);
  342. add(&list);
  343. end_branch_choice(&list);
  344. end_branch(&list);
  345. end_branch_choice(&list);
  346. add_branch_choice(&list);
  347. add(&list);
  348. add(&list);
  349. add_branch(&list);
  350. add_branch_choice(&list);
  351. add(&list);
  352. add(&list);
  353. end_branch_choice(&list);
  354. end_branch(&list);
  355. end_branch_choice(&list);
  356. end_branch(&list);
  357. end_branch_choice(&list);
  358. end_branch(&list);
  359. end_branch_choice(&list);
  360. end_branch(&list);
  361. add(&list);
  362. add(&list);
  363. add_branch(&list);
  364. add_branch_choice(&list);
  365. add(&list);
  366. add(&list);
  367. end_branch_choice(&list);
  368. end_branch(&list);
  369. add(&list);
  370. add(&list);
  371. add(&list);
  372. end_branch_choice(&list);
  373. add_branch_choice(&list);
  374. add(&list);
  375. add(&list);
  376. add_branch(&list);
  377. add_branch_choice(&list);
  378. add(&list);
  379. add(&list);
  380. end_branch_choice(&list);
  381. end_branch(&list);
  382. add(&list);
  383. add(&list);
  384. add(&list);
  385. end_branch_choice(&list);
  386. end_branch(&list);
  387. add_branch(&list);
  388. add_branch_choice(&list);
  389. add(&list);
  390. add(&list);
  391. end_branch_choice(&list);
  392. end_branch(&list);
  393. end_branch_choice(&list);
  394. add_branch_choice(&list);
  395. add(&list);
  396. add(&list);
  397. add_branch(&list);
  398. add_branch_choice(&list);
  399. add(&list);
  400. add(&list);
  401. end_branch_choice(&list);
  402. end_branch(&list);
  403. end_branch_choice(&list);
  404. end_branch(&list);
  405. end_branch_choice(&list);
  406. end_branch(&list);
  407. end_branch_choice(&list);
  408. end_branch(&list);
  409. add(&list);
  410. print(list->front);
  411. // this part should be left to the garbage collector to clean up
  412. // psize_t(free_asm(&list));
  413. return 0;
  414. }
  415.