spacepaste

Paste details

reply | raw

  1.  
  2. $ ./new
  3. last_ref = 5
  4. last_ref = 15
  5. last_ref = 25
  6. last_ref = 25
  7. last_ref = 28
  8. last_ref = 32
  9. last_ref = 32
  10. last_ref = 35
  11. last_ref = 37
  12. last_ref = 41
  13. last_ref = 41
  14. last_ref = 45
  15. last_ref = 45
  16. last_ref = 48
  17. last_ref = 52
  18. last_ref = 52
  19. last_ref = 55
  20. last_ref = 57
  21. last_ref = 61
  22. last_ref = 61
  23. 0 -> 1
  24. branch start
  25. branch choice start
  26. 1 -> 2
  27. 2 -> 3
  28. branch start
  29. branch choice start
  30. 3 -> 4
  31. 4 -> 25
  32. branch choice end
  33. branch end
  34. branch choice end
  35. branch choice start
  36. 5 -> 6
  37. 6 -> 7
  38. branch start
  39. branch choice start
  40. 7 -> 8
  41. 8 -> 9
  42. branch start
  43. branch choice start
  44. 9 -> 10
  45. 10 -> 11
  46. branch start
  47. branch choice start
  48. branch start
  49. branch choice start
  50. 11 -> 12
  51. 12 -> 13
  52. branch start
  53. branch choice start
  54. 13 -> 14
  55. 14 -> 25
  56. branch choice end
  57. branch end
  58. branch choice end
  59. branch choice start
  60. 15 -> 16
  61. 16 -> 17
  62. branch start
  63. branch choice start
  64. 17 -> 18
  65. 18 -> 19
  66. branch start
  67. branch choice start
  68. 19 -> 20
  69. 20 -> 21
  70. branch start
  71. branch choice start
  72. 21 -> 22
  73. 22 -> 23
  74. branch start
  75. branch choice start
  76. 23 -> 24
  77. 24 -> 25
  78. branch choice end
  79. branch end
  80. 25 -> 26
  81. 26 -> 27
  82. 27 -> 32
  83. branch choice end
  84. branch choice start
  85. 28 -> 29
  86. 29 -> 30
  87. branch start
  88. branch choice start
  89. 30 -> 31
  90. 31 -> 32
  91. branch choice end
  92. branch end
  93. 32 -> 33
  94. 33 -> 34
  95. 34 -> 41
  96. branch choice end
  97. branch end
  98. branch start
  99. branch choice start
  100. 35 -> 36
  101. 36 -> 41
  102. branch choice end
  103. branch end
  104. branch choice end
  105. branch choice start
  106. 37 -> 38
  107. 38 -> 39
  108. branch start
  109. branch choice start
  110. 39 -> 40
  111. 40 -> 41
  112. branch choice end
  113. branch end
  114. branch choice end
  115. branch end
  116. branch choice end
  117. branch end
  118. branch choice end
  119. branch end
  120. 41 -> 42
  121. 42 -> 43
  122. branch start
  123. branch choice start
  124. 43 -> 44
  125. 44 -> 45
  126. branch choice end
  127. branch end
  128. 45 -> 46
  129. 46 -> 47
  130. 47 -> 52
  131. branch choice end
  132. branch choice start
  133. 48 -> 49
  134. 49 -> 50
  135. branch start
  136. branch choice start
  137. 50 -> 51
  138. 51 -> 52
  139. branch choice end
  140. branch end
  141. 52 -> 53
  142. 53 -> 54
  143. 54 -> 61
  144. branch choice end
  145. branch end
  146. branch start
  147. branch choice start
  148. 55 -> 56
  149. 56 -> 61
  150. branch choice end
  151. branch end
  152. branch choice end
  153. branch choice start
  154. 57 -> 58
  155. 58 -> 59
  156. branch start
  157. branch choice start
  158. 59 -> 60
  159. 60 -> 61
  160. branch choice end
  161. branch end
  162. branch choice end
  163. branch end
  164. branch choice end
  165. branch end
  166. branch choice end
  167. branch end
  168. 61 -> 62
  169. NULL
  171. $ cat new.c
  172. #include <stdbool.h>
  173. #include <stdio.h>
  174. #include <stdlib.h>
  175. #include <string.h>
  177. #define pp(x) printf("%s = %p\n", #x, x);
  178. #define pi(x) printf("%s = %d\n", #x, x);
  179. #define pc(x) printf("%s = %c\n", #x, x);
  180. #define psize_t(x) printf("%s = %zu\n", #x, x);
  182. // A C program to demonstrate linked list based implementation of queue
  183. // A linked list (LL) node to store a queue entry
  184. int index_start = -1;
  185. int ref_start = 0;
  186. int global_indent = 0;
  188. #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;
  190. #define STORE_NORMAL 1
  191. #define STORE_EMPTY 2
  193. #define NODE_TYPE_NORMAL 1
  194. #define NODE_TYPE_BRANCH_START 2
  195. #define NODE_TYPE_BRANCH_END 3
  196. #define NODE_TYPE_BRANCH_CHOICE_START 4
  197. #define NODE_TYPE_BRANCH_CHOICE_END 5
  199. #define POINTER_LIST_TYPE int
  201. POINTER_LIST_TYPE ** ptr_list = NULL;
  202. ssize_t ptr_list_size = 0;
  204. int last_ref = 0;
  206. int ptr_add(POINTER_LIST_TYPE * ptr) {
  207. if (!ptr) return -1;
  208. POINTER_LIST_TYPE ** pl;
  209. if (!ptr_list) {
  210. ptr_list = malloc(sizeof(ptr_list)*2);
  211. ptr_list_size++;
  212. }
  213. else if (ptr_list) {
  214. ptr_list = realloc(ptr_list, sizeof(ptr_list)*(ptr_list_size+1));
  215. }
  216. ptr_list[ptr_list_size-1] = ptr;
  217. ptr_list_size++;
  218. ptr_list[ptr_list_size-1] = NULL;
  219. return 0;
  220. }
  222. int ptr_print(void) {
  223. if (!ptr_list) return -1;
  224. POINTER_LIST_TYPE ** pl;
  225. for (pl = ptr_list; *pl; pl++) pp(*pl);
  226. return 0;
  227. }
  229. int ptr_set(POINTER_LIST_TYPE data) {
  230. if (!ptr_list) return -1;
  231. POINTER_LIST_TYPE ** pl;
  232. for (pl = ptr_list; *pl; pl++) **pl = data;
  233. return 0;
  234. }
  236. int ptr_free(void) {
  237. if (!ptr_list) return -1;
  238. POINTER_LIST_TYPE ** pl;
  239. for (pl = ptr_list; *pl; pl++) *pl = NULL;
  240. free(ptr_list);
  241. ptr_list = NULL;
  242. ptr_list_size = 0;
  243. return 0;
  244. }
  246. struct QNode
  247. {
  248. int level;
  249. int index;
  250. int ref;
  251. int next_count;
  252. int type;
  253. struct QNode **next;
  254. };
  256. // The queue, front stores the front node of LL and rear stores ths
  257. // last node of LL
  258. struct Queue
  259. {
  260. struct QNode *front, *rear;
  261. };
  264. // A utility function to create a new linked list node.
  265. struct QNode* newNode(int type)
  266. {
  267. struct QNode *temp = (struct QNode*)malloc(sizeof(struct QNode));
  268. if (type == STORE_NORMAL) {
  269. node_init(temp, index_start++, ref_start++, 0, NULL);
  270. } else if (type == STORE_EMPTY) {
  271. node_init(temp, 0, 0, 0, NULL);
  272. }
  273. return temp;
  274. }
  276. // A utility function to create an empty queue
  277. struct Queue *createQueue()
  278. {
  279. struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
  280. q->front = q->rear = NULL;
  281. return q;
  282. }
  283. int prev_type = 0;
  284. int curr_type = 0;
  285. void store_asm(struct Queue *q, int type)
  286. {
  287. if (curr_type) prev_type = curr_type;
  288. curr_type = type;
  289. // Create a new LL node
  290. int t = 0;
  291. if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
  292. else if (
  293. type == NODE_TYPE_BRANCH_START
  294. ||
  295. type == NODE_TYPE_BRANCH_END
  296. ||
  297. type == NODE_TYPE_BRANCH_CHOICE_START
  298. ||
  299. type == NODE_TYPE_BRANCH_CHOICE_END
  300. ) t = STORE_EMPTY;
  301. struct QNode *temp = newNode(t);
  302. temp->type = type;
  304. // If queue is empty, then new node is front and rear both
  305. if (q->rear == NULL)
  306. {
  307. q->front = q->rear = temp;
  308. if (!q->rear->next) {
  309. q->rear->next_count = 1;
  310. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  311. } else {
  312. q->rear->next_count++;
  313. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  314. }
  315. return;
  316. }
  317. if (prev_type == NODE_TYPE_NORMAL) {
  319. if (type == NODE_TYPE_BRANCH_CHOICE_END) {
  320. // pp(&q->rear->ref)
  321. last_ref = q->rear->ref;
  322. pi(last_ref);
  323. ptr_add(&q->rear->ref);
  324. }
  325. }
  326. else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) {
  327. pi(last_ref);
  328. ptr_set(last_ref);
  329. ptr_free();
  330. }
  331. // Add the new node at the end of queue and change rear
  332. q->rear->next[q->rear->next_count-1] = temp;
  333. q->rear = temp;
  334. if (!q->rear->next) {
  335. q->rear->next_count = 1;
  336. q->rear->next = malloc(sizeof(struct QNode)*q->rear->next_count);
  337. } else {
  338. q->rear->next_count++;
  339. q->rear->next = realloc(q->rear->next, sizeof(struct QNode)*q->rear->next_count);
  340. }
  341. }
  343. void add(struct Queue **q) {
  344. if (!(*q)) (*q) = createQueue();
  345. store_asm((*q), NODE_TYPE_NORMAL);
  346. }
  349. #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
  351. struct Queue * list = NULL;
  353. void print(struct QNode * p, int indent) {
  354. int indentation = 0;
  355. while(p) {
  356. indentation = p->level;
  357. add_indent(indentation);
  358. if (p->type == NODE_TYPE_BRANCH_START) {
  359. add_indent(indentation);
  360. printf("branch start\n");
  361. }
  362. else if (p->type == NODE_TYPE_BRANCH_END) {
  363. add_indent(indentation);
  364. printf("branch end\n");
  365. }
  366. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  367. add_indent(indentation);
  368. printf("branch choice start\n");
  369. }
  370. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  371. add_indent(indentation);
  372. printf("branch choice end\n");
  373. }
  374. else if (p->type == NODE_TYPE_NORMAL) {
  375. add_indent(indentation);
  376. printf("%d -> %d\n", p->index, p->ref);
  377. }
  378. if (p->next) p = p->next[0];
  379. else p = NULL;
  380. }
  381. add_indent(indentation);
  382. puts("NULL");
  383. }
  385. void add_branch(struct Queue **q) {
  386. if (!(*q)) (*q) = createQueue();
  387. store_asm((*q), NODE_TYPE_BRANCH_START);
  388. global_indent++;
  389. }
  391. void end_branch(struct Queue **q) {
  392. global_indent--;
  393. if (!(*q)) (*q) = createQueue();
  394. store_asm((*q), NODE_TYPE_BRANCH_END);
  395. }
  397. void add_branch_choice(struct Queue **q) {
  398. if (!(*q)) (*q) = createQueue();
  399. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_START);
  400. global_indent++;
  401. }
  403. void end_branch_choice(struct Queue **q) {
  404. global_indent--;
  405. if (!(*q)) (*q) = createQueue();
  406. store_asm((*q), NODE_TYPE_BRANCH_CHOICE_END);
  407. }
  409. int main(void) {
  410. index_start = 0;
  411. ref_start = 1;
  412. add(&list);
  413. add_branch(&list);
  414. add_branch_choice(&list);
  415. add(&list);
  416. add(&list);
  417. add_branch(&list);
  418. add_branch_choice(&list);
  419. add(&list);
  420. add(&list);
  421. end_branch_choice(&list);
  422. end_branch(&list);
  423. end_branch_choice(&list);
  424. add_branch_choice(&list);
  425. add(&list);
  426. add(&list);
  427. add_branch(&list);
  428. add_branch_choice(&list);
  429. add(&list);
  430. add(&list);
  431. add_branch(&list);
  432. add_branch_choice(&list);
  433. add(&list);
  434. add(&list);
  435. add_branch(&list);
  436. add_branch_choice(&list);
  437. add_branch(&list);
  438. add_branch_choice(&list);
  439. add(&list);
  440. add(&list);
  441. add_branch(&list);
  442. add_branch_choice(&list);
  443. add(&list);
  444. add(&list);
  445. end_branch_choice(&list);
  446. end_branch(&list);
  447. end_branch_choice(&list);
  448. add_branch_choice(&list);
  449. add(&list);
  450. add(&list);
  451. add_branch(&list);
  452. add_branch_choice(&list);
  453. add(&list);
  454. add(&list);
  455. add_branch(&list);
  456. add_branch_choice(&list);
  457. add(&list);
  458. add(&list);
  459. add_branch(&list);
  460. add_branch_choice(&list);
  461. add(&list);
  462. add(&list);
  463. add_branch(&list);
  464. add_branch_choice(&list);
  465. add(&list);
  466. add(&list);
  467. end_branch_choice(&list);
  468. end_branch(&list);
  469. add(&list);
  470. add(&list);
  471. add(&list);
  472. end_branch_choice(&list);
  473. add_branch_choice(&list);
  474. add(&list);
  475. add(&list);
  476. add_branch(&list);
  477. add_branch_choice(&list);
  478. add(&list);
  479. add(&list);
  480. end_branch_choice(&list);
  481. end_branch(&list);
  482. add(&list);
  483. add(&list);
  484. add(&list);
  485. end_branch_choice(&list);
  486. end_branch(&list);
  487. add_branch(&list);
  488. add_branch_choice(&list);
  489. add(&list);
  490. add(&list);
  491. end_branch_choice(&list);
  492. end_branch(&list);
  493. end_branch_choice(&list);
  494. add_branch_choice(&list);
  495. add(&list);
  496. add(&list);
  497. add_branch(&list);
  498. add_branch_choice(&list);
  499. add(&list);
  500. add(&list);
  501. end_branch_choice(&list);
  502. end_branch(&list);
  503. end_branch_choice(&list);
  504. end_branch(&list);
  505. end_branch_choice(&list);
  506. end_branch(&list);
  507. end_branch_choice(&list);
  508. end_branch(&list);
  509. add(&list);
  510. add(&list);
  511. add_branch(&list);
  512. add_branch_choice(&list);
  513. add(&list);
  514. add(&list);
  515. end_branch_choice(&list);
  516. end_branch(&list);
  517. add(&list);
  518. add(&list);
  519. add(&list);
  520. end_branch_choice(&list);
  521. add_branch_choice(&list);
  522. add(&list);
  523. add(&list);
  524. add_branch(&list);
  525. add_branch_choice(&list);
  526. add(&list);
  527. add(&list);
  528. end_branch_choice(&list);
  529. end_branch(&list);
  530. add(&list);
  531. add(&list);
  532. add(&list);
  533. end_branch_choice(&list);
  534. end_branch(&list);
  535. add_branch(&list);
  536. add_branch_choice(&list);
  537. add(&list);
  538. add(&list);
  539. end_branch_choice(&list);
  540. end_branch(&list);
  541. end_branch_choice(&list);
  542. add_branch_choice(&list);
  543. add(&list);
  544. add(&list);
  545. add_branch(&list);
  546. add_branch_choice(&list);
  547. add(&list);
  548. add(&list);
  549. end_branch_choice(&list);
  550. end_branch(&list);
  551. end_branch_choice(&list);
  552. end_branch(&list);
  553. end_branch_choice(&list);
  554. end_branch(&list);
  555. end_branch_choice(&list);
  556. end_branch(&list);
  557. add(&list);
  559. print(list->front, 0);
  560. ptr_print();
  561. return 0;
  562. }
  563.  
Powered by spacepaste. Paste removal.