spacepaste

Paste details

reply | raw

  1.  
  2. $ ./new
  3. FOUND BRANCH START
  4. FOUND BRANCH START
  5. 0 -> 1 (data: 1)
  6. p->next = (nil)
  7. NULL
  8. printing previous
  9. NULL
  10. 3 -> 4 (data: 13)
  11. branch end
  12. branch choice end
  13. 2 -> 3 (data: 8)
  14. branch choice start
  15. branch choice end
  16. 1 -> 2 (data: 2)
  17. branch choice start
  18. branch start
  19. 0 -> 1 (data: 1)
  21. $ cat new.c
  22. #include <stdbool.h>
  23. #include <stdio.h>
  24. #include <stdlib.h>
  25. #include <string.h>
  27. #define pp(x) printf("%s = %p\n", #x, x);
  28. #define pi(x) printf("%s = %d\n", #x, x);
  29. #define pc(x) printf("%s = %c\n", #x, x);
  30. #define psize_t(x) printf("%s = %zu\n", #x, x);
  32. #define LINKED 1
  33. #define TREE 2
  34. #define NODE_TYPE TREE
  36. struct QNode
  37. {
  38. int level;
  39. int index;
  40. int ref;
  41. int data;
  42. int type;
  43. struct QNode *next;
  44. struct QNode* prev; // Pointer to previous node in DLL
  45. #if NODE_TYPE == TREE
  46. int branch_count;
  47. struct QNode **branch;
  48. #endif
  49. };
  51. // The queue, front stores the front node of LL and rear stores ths
  52. // last node of LL
  53. struct Queue
  54. {
  55. struct QNode *front, *rear;
  56. };
  58. ssize_t free_asm(struct Queue **q)
  59. {
  60. puts("");
  61. ssize_t frees = 0;
  62. if ((q) == NULL) return frees;
  63. if ((*q) == NULL) return frees;
  64. struct QNode *temp = NULL, *next = NULL;
  65. temp = (*q)->front;
  66. while (temp) {
  67. next = (*q)->front->next;
  68. frees++;
  69. free(temp);
  70. temp = NULL;
  71. (*q)->front = next;
  72. temp = next;
  73. }
  74. frees++;
  75. free(*q);
  76. *q = NULL;
  77. return frees;
  78. }
  81. // A C program to demonstrate linked list based implementation of queue
  82. // A linked list (LL) node to store a queue entry
  83. int index_start = -1;
  84. int ref_start = 0;
  85. int global_indent = 0;
  87. #if NODE_TYPE == LINKED
  88. #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;
  89. #elif NODE_TYPE == TREE
  90. #define node_init(t, i, r, d, n, bc, b) t->index = i; t->ref = r; t->data = d; t->next = n; t->branch_count = bc; t->branch = b; t->level = global_indent; t->prev = NULL;
  91. #endif
  93. #define STORE_NORMAL 1
  94. #define STORE_EMPTY 2
  96. #define NODE_TYPE_NORMAL 1
  97. #define NODE_TYPE_BRANCH_START 2
  98. #define NODE_TYPE_BRANCH_END 3
  99. #define NODE_TYPE_BRANCH_CHOICE_START 4
  100. #define NODE_TYPE_BRANCH_CHOICE_END 5
  102. #define POINTER_LIST_TYPE int
  104. POINTER_LIST_TYPE ** ptr_list = NULL;
  105. ssize_t ptr_list_size = 0;
  107. int last_ref = 0;
  109. int ptr_add(POINTER_LIST_TYPE * ptr) {
  110. if (!ptr) return -1;
  111. if (!ptr_list) {
  112. ptr_list = malloc(sizeof(*ptr_list)*2);
  113. ptr_list_size++;
  114. }
  115. else if (ptr_list) {
  116. ptr_list = realloc(ptr_list, sizeof(*ptr_list)*(ptr_list_size+1));
  117. }
  118. ptr_list[ptr_list_size-1] = ptr;
  119. ptr_list_size++;
  120. ptr_list[ptr_list_size-1] = NULL;
  121. return 0;
  122. }
  124. int ptr_print(void) {
  125. if (!ptr_list) return -1;
  126. POINTER_LIST_TYPE ** pl;
  127. for (pl = ptr_list; *pl; pl++) pp(*pl);
  128. return 0;
  129. }
  131. int ptr_set(POINTER_LIST_TYPE data) {
  132. if (!ptr_list) return -1;
  133. POINTER_LIST_TYPE ** pl;
  134. for (pl = ptr_list; *pl; pl++) **pl = data;
  135. return 0;
  136. }
  138. int ptr_set_free(void) {
  139. if (!ptr_list) return -1;
  140. POINTER_LIST_TYPE ** pl;
  141. for (pl = ptr_list; *pl; pl++) {
  142. free(*pl);
  143. *pl = NULL;
  144. }
  145. return 0;
  146. }
  148. int ptr_free(void) {
  149. if (!ptr_list) return -1;
  150. POINTER_LIST_TYPE ** pl;
  151. for (pl = ptr_list; *pl; pl++) *pl = NULL;
  152. free(ptr_list);
  153. ptr_list = NULL;
  154. ptr_list_size = 0;
  155. return 0;
  156. }
  158. // A utility function to create a new linked list node.
  159. struct QNode* newNode(int data, int type)
  160. {
  161. struct QNode *temp = (struct QNode*)malloc(sizeof(*temp));
  162. #if NODE_TYPE == LINKED
  163. if (type == STORE_NORMAL) {
  164. node_init(temp, index_start++, ref_start++, data, NULL);
  165. } else if (type == STORE_EMPTY) {
  166. node_init(temp, 0, 0, 0, 0, NULL);
  167. }
  168. #elif NODE_TYPE == TREE
  169. if (type == STORE_NORMAL) {
  170. node_init(temp, index_start++, ref_start++, data, NULL, 0, NULL);
  171. } else if (type == STORE_EMPTY) {
  172. node_init(temp, 0, 0, 0, NULL, 0, NULL);
  173. }
  174. #endif
  175. return temp;
  176. }
  178. // A utility function to create an empty queue
  179. struct Queue *createQueue()
  180. {
  181. struct Queue *q = (struct Queue*)malloc(sizeof(*q));
  182. q->front = q->rear = NULL;
  183. return q;
  184. }
  185. int prev_type = 0;
  186. int curr_type = 0;
  187. void store_asm(struct Queue *q, int data, int type)
  188. {
  189. if (curr_type) prev_type = curr_type;
  190. curr_type = type;
  191. // Create a new LL node
  192. int t = 0;
  193. if (type == NODE_TYPE_NORMAL) t = STORE_NORMAL;
  194. else if (
  195. type == NODE_TYPE_BRANCH_START
  196. ||
  197. type == NODE_TYPE_BRANCH_END
  198. ||
  199. type == NODE_TYPE_BRANCH_CHOICE_START
  200. ||
  201. type == NODE_TYPE_BRANCH_CHOICE_END
  202. ) t = STORE_EMPTY;
  203. struct QNode *temp = newNode(data, t);
  204. temp->type = type;
  206. // If queue is empty, then new node is front and rear both
  207. if (q->rear == NULL)
  208. {
  209. temp->prev = NULL;
  210. q->front = q->rear = temp;
  211. return;
  212. }
  213. if (prev_type == NODE_TYPE_NORMAL) {
  215. if (type == NODE_TYPE_BRANCH_CHOICE_END) {
  216. // 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
  217. // last_ref = q->rear->ref;
  218. // printf("adding %d to the pointer list\n", last_ref);
  219. // ptr_add(&q->rear->ref);
  220. }
  221. }
  222. else if(type == NODE_TYPE_NORMAL && prev_type == NODE_TYPE_BRANCH_END) {
  223. // 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
  224. // printf("setting pointer list to %d\n", last_ref);
  225. // ptr_set(last_ref);
  226. // ptr_free();
  227. }
  228. // Add the new node at the end of queue and change rear
  230. temp->prev = q->rear;
  231. // allocate a new array for our new item
  232. #if NODE_TYPE == LINKED
  233. if (!q->rear->next) {
  234. q->rear->next = malloc(sizeof(*q->rear->next));
  235. } else {
  236. abort();
  237. }
  238. // update rear->next to point to the new item
  239. q->rear->next = temp;
  240. // 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
  241. q->rear = q->rear->next;
  242. #elif NODE_TYPE == TREE
  243. struct QNode * p = q->rear;
  244. if (type == NODE_TYPE_BRANCH_CHOICE_START) {
  245. while(p) {
  246. if (p->type == NODE_TYPE_BRANCH_START) {
  247. puts("FOUND BRANCH START");
  248. q->rear = p;
  249. break;
  250. }
  251. if (p->prev) p = p->prev;
  252. else p = NULL;
  253. }
  254. }
  255. // allocate a new array for our new item
  256. if (!q->rear->branch) {
  257. q->rear->branch_count = 1;
  258. q->rear->branch = malloc(sizeof(struct QNode)*q->rear->branch_count);
  259. } else {
  260. q->rear->branch_count++;
  261. q->rear->branch = realloc(q->rear->branch, sizeof(struct QNode)*q->rear->branch_count);
  262. }
  263. // update rear->next to point to the new item
  264. q->rear->branch[q->rear->branch_count-1] = temp;
  266. // 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
  267. q->rear = q->rear->branch[q->rear->branch_count-1];
  268. #endif
  269. }
  271. struct QNode * load_asm(struct Queue **q)
  272. {
  273. // If queue is empty, return NULL.
  274. if ((q) == NULL) return NULL;
  275. if ((*q) == NULL) return NULL;
  276. if ((*q)->front == NULL)
  277. return NULL;
  279. // Store previous front and move front one node ahead
  280. struct QNode *temp = (*q)->front;
  281. // check if front->next is NULL, if NULL it means we have reached the end of the queue
  282. (*q)->front = (*q)->front->next;
  283. // If front becomes NULL, then change rear also as NULL
  284. if ((*q)->front == NULL)
  285. (*q)->rear = NULL;
  286. return temp;
  287. }
  289. #define add_indent(indent) { int i = 0; for (; i < indent; i++) printf(" "); }
  291. struct Queue * list = NULL;
  293. void printnode(struct QNode * p) {
  294. int indentation = p->level;
  295. add_indent(indentation);
  296. if (p->type == NODE_TYPE_BRANCH_START) {
  297. add_indent(indentation);
  298. printf("branch start\n");
  299. }
  300. else if (p->type == NODE_TYPE_BRANCH_END) {
  301. add_indent(indentation);
  302. printf("branch end\n");
  303. }
  304. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  305. add_indent(indentation);
  306. printf("branch choice start\n");
  307. }
  308. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  309. add_indent(indentation);
  310. printf("branch choice end\n");
  311. }
  312. else if (p->type == NODE_TYPE_NORMAL) {
  313. add_indent(indentation);
  314. printf("%d -> %d (data: %d)\n", p->index, p->ref, p->data);
  315. }
  316. #if NODE_TYPE == TREE
  317. // pi(p->branch_count)
  318. #endif
  319. }
  321. void print_prev(struct QNode * p) {
  322. puts("NULL");
  323. while(p) {
  324. printnode(p);
  325. if (p->prev) p = p->prev;
  326. else p = NULL;
  327. }
  328. }
  330. void print_(struct QNode * p) {
  331. while(p) {
  332. printnode(p);
  333. #if NODE_TYPE == LINKED
  334. p = p->next;
  335. #elif NODE_TYPE == TREE
  336. if (p->next) p = p->next;
  337. else p = NULL;
  338. #endif
  339. }
  340. puts("NULL");
  341. }
  343. void print(struct QNode * p) {
  344. while(p) {
  345. printnode(p);
  346. // #if NODE_TYPE == TREE
  347. // if (p->branch_count) {
  348. // pi(p->branch_count)
  349. // puts("printing branches");
  350. // for (int i = 0; i < p->branch_count; i++) {
  351. // printf("printing branch %d\n", i);
  352. // print_(p->branch[i]);
  353. // printf("finished printing branch %d\n", i);
  354. // }
  355. // }
  356. // #endif
  357. pp(p->next)
  358. p = p->next;
  359. }
  360. puts("NULL");
  361. }
  363. void fix(struct Queue *p);
  365. void add(struct Queue **q, int data) {
  366. if (!(*q)) (*q) = createQueue();
  367. store_asm((*q), data, NODE_TYPE_NORMAL);
  368. }
  370. void add_branch(struct Queue **q) {
  371. if (!(*q)) (*q) = createQueue();
  372. store_asm((*q), 0, NODE_TYPE_BRANCH_START);
  373. global_indent++;
  374. }
  376. void end_branch(struct Queue **q) {
  377. global_indent--;
  378. if (!(*q)) (*q) = createQueue();
  379. store_asm((*q), 0, NODE_TYPE_BRANCH_END);
  380. }
  382. void add_branch_choice(struct Queue **q) {
  383. if (!(*q)) (*q) = createQueue();
  384. store_asm((*q), 0, NODE_TYPE_BRANCH_CHOICE_START);
  385. global_indent++;
  386. }
  388. void end_branch_choice(struct Queue **q) {
  389. global_indent--;
  390. if (!(*q)) (*q) = createQueue();
  391. // if we have a branch_end, we need to go backwards in out linked list to the node that came before the branch start
  392. store_asm((*q), 0, NODE_TYPE_BRANCH_CHOICE_END);
  393. }
  395. int main(void) {
  396. index_start = 0;
  397. ref_start = 1;
  399. /* attempt to visualize this in a expression grammar
  400. root ::= 0 A 61
  401. A ::=
  402. 1 2 B
  403. 5 6 C
  404. B ::=
  405. 3 4
  406. C ::=
  407. 7 8 D
  408. D ::=
  409. 9 10 F R
  410. 57 58 S
  411. F ::=
  412. G 41 42 P 45 46 47
  413. 48 49 Q 52 53 54
  414. G ::=
  415. 11 12 H
  416. 15 16 I
  417. H ::=
  418. 13 14
  419. I ::=
  420. 17 18 J
  421. J ::=
  422. 19 20 K N
  423. 37 38 O
  424. K ::=
  425. 21 22 L 25 26 27
  426. 28 29 M 32 33 34
  427. L ::=
  428. 23 24
  429. M ::=
  430. 30 31
  431. N ::=
  432. 35 36
  433. O ::=
  434. 39 40
  435. P ::=
  436. 43 44
  437. Q ::=
  438. 50 51
  439. R ::=
  440. 55 56
  441. S ::=
  442. 59 60
  444. structure:
  446. root: 0 A 61 > NULL
  447. A: 1 2 B
  448. B: 3 4 > 61 // currently 4 > 25
  449. A: 5 6 C
  450. C: 7 8 D
  451. D: 9 10 F R
  452. F: G 41 42 P 45 46 47 > 55 (R) // currently 47 > 52
  453. G: 11 12 H
  454. H: 13 14 > 41 // currently 14 > 25
  455. G: 15 16 I
  456. I: 16 18 J
  457. J: 19 20 K N
  458. K: 21 22 L 25 26 27 > 35 (N) // currently 27 > 32
  459. L: 23 24 > 25
  460. K: 28 29 M 32 33 34 > 35 (N)
  461. M: 30 31 > 32
  462. N: 35 36 > 41
  463. J: 37 38 O
  464. O: 39 40 > 41
  465. P: 43 44 > 45
  466. F: 48 49 Q 52 53 54 > 55 (R)
  467. Q: 50 51 > 52
  468. R: 55 56 > 61
  469. D: 57 58 S
  470. S: 59 60 > 61
  471. add(&list, 1);
  472. add_branch(&list);
  473. add_branch_choice(&list);
  474. add(&list, 2);
  475. add(&list, 3);
  476. add_branch(&list);
  477. add_branch_choice(&list);
  478. add(&list, 4);
  479. add(&list, 5);
  480. end_branch_choice(&list);
  481. end_branch(&list);
  482. end_branch_choice(&list);
  483. add_branch_choice(&list);
  484. add(&list, 6);
  485. add(&list, 7);
  486. add_branch(&list);
  487. add_branch_choice(&list);
  488. add(&list, 8);
  489. add(&list, 9);
  490. add_branch(&list);
  491. add_branch_choice(&list);
  492. add(&list, 10);
  493. add(&list, 11);
  494. add_branch(&list);
  495. add_branch_choice(&list);
  496. add_branch(&list);
  497. add_branch_choice(&list);
  498. add(&list, 12);
  499. add(&list, 13);
  500. add_branch(&list);
  501. add_branch_choice(&list);
  502. add(&list, 14);
  503. add(&list, 15);
  504. end_branch_choice(&list);
  505. end_branch(&list);
  506. end_branch_choice(&list);
  507. add_branch_choice(&list);
  508. add(&list, 16);
  509. add(&list, 17);
  510. add_branch(&list);
  511. add_branch_choice(&list);
  512. add(&list, 18);
  513. add(&list, 19);
  514. add_branch(&list);
  515. add_branch_choice(&list);
  516. add(&list, 20);
  517. add(&list, 21);
  518. add_branch(&list);
  519. add_branch_choice(&list);
  520. add(&list, 22);
  521. add(&list, 23);
  522. add_branch(&list);
  523. add_branch_choice(&list);
  524. add(&list, 24);
  525. add(&list, 25);
  526. end_branch_choice(&list);
  527. end_branch(&list);
  528. add(&list, 26);
  529. add(&list, 27);
  530. add(&list, 28);
  531. end_branch_choice(&list);
  532. add_branch_choice(&list);
  533. add(&list, 29);
  534. add(&list, 30);
  535. add_branch(&list);
  536. add_branch_choice(&list);
  537. add(&list, 31);
  538. add(&list, 32);
  539. end_branch_choice(&list);
  540. end_branch(&list);
  541. add(&list, 33);
  542. add(&list, 34);
  543. add(&list, 35);
  544. end_branch_choice(&list);
  545. end_branch(&list);
  546. add_branch(&list);
  547. add_branch_choice(&list);
  548. add(&list, 36);
  549. add(&list, 37);
  550. end_branch_choice(&list);
  551. end_branch(&list);
  552. end_branch_choice(&list);
  553. add_branch_choice(&list);
  554. add(&list, 38);
  555. add(&list, 39);
  556. add_branch(&list);
  557. add_branch_choice(&list);
  558. add(&list, 40);
  559. add(&list, 41);
  560. end_branch_choice(&list);
  561. end_branch(&list);
  562. end_branch_choice(&list);
  563. end_branch(&list);
  564. end_branch_choice(&list);
  565. end_branch(&list);
  566. end_branch_choice(&list);
  567. end_branch(&list);
  568. add(&list, 42);
  569. add(&list, 43);
  570. add_branch(&list);
  571. add_branch_choice(&list);
  572. add(&list, 44);
  573. add(&list, 45);
  574. end_branch_choice(&list);
  575. end_branch(&list);
  576. add(&list, 46);
  577. add(&list, 47);
  578. add(&list, 48);
  579. end_branch_choice(&list);
  580. add_branch_choice(&list);
  581. add(&list, 49);
  582. add(&list, 50);
  583. add_branch(&list);
  584. add_branch_choice(&list);
  585. add(&list, 51);
  586. add(&list, 52);
  587. end_branch_choice(&list);
  588. end_branch(&list);
  589. add(&list, 53);
  590. add(&list, 54);
  591. add(&list, 55);
  592. end_branch_choice(&list);
  593. end_branch(&list);
  594. add_branch(&list);
  595. add_branch_choice(&list);
  596. add(&list, 56);
  597. add(&list, 57);
  598. end_branch_choice(&list);
  599. end_branch(&list);
  600. end_branch_choice(&list);
  601. add_branch_choice(&list);
  602. add(&list, 58);
  603. add(&list, 59);
  604. add_branch(&list);
  605. add_branch_choice(&list);
  606. add(&list, 60);
  607. add(&list, 61);
  608. end_branch_choice(&list);
  609. end_branch(&list);
  610. end_branch_choice(&list);
  611. end_branch(&list);
  612. end_branch_choice(&list);
  613. end_branch(&list);
  614. end_branch_choice(&list);
  615. end_branch(&list);
  616. add(&list, 62);
  617. */
  621. /* attempt to visualize this in a expression grammar
  622. root ::= 1 A 13
  623. A ::=
  624. 2 3 B 6
  625. 7 8 C
  626. B ::=
  627. 4
  628. C ::=
  629. 9 10 D
  630. D ::=
  631. 11
  633. structure:
  635. root: 1 A 13 > NULL
  636. A: 2 3 B 6 > 13
  637. B: 4 5 > 6
  638. A: 7 8 C
  639. C: 9 10 D
  640. D: 11 > 13
  641. */
  642. add(&list, 1);
  643. add_branch(&list);
  644. add_branch_choice(&list);
  645. add(&list, 2);
  646. // add(&list, 3);
  647. // add_branch(&list);
  648. // add_branch_choice(&list);
  649. // add(&list, 4);
  650. // add(&list, 5);
  651. // end_branch_choice(&list);
  652. // end_branch(&list);
  653. // add(&list, 6);
  654. end_branch_choice(&list);
  655. add_branch_choice(&list);
  656. // add(&list, 7);
  657. add(&list, 8);
  658. // add_branch(&list);
  659. // add_branch_choice(&list);
  660. // add(&list, 9);
  661. // add(&list, 10);
  662. // add_branch(&list);
  663. // add_branch_choice(&list);
  664. // add(&list, 11);
  665. // add(&list, 12);
  666. // end_branch_choice(&list);
  667. // end_branch(&list);
  668. // end_branch_choice(&list);
  669. // end_branch(&list);
  670. end_branch_choice(&list);
  671. end_branch(&list);
  672. add(&list, 13);
  673. print(list->front);
  674. puts("printing previous");
  675. print_prev(list->rear);
  677. // fix(list);
  678. // this part should be left to the garbage collector to clean up
  679. #if NODE_TYPE == LINKED
  680. psize_t(free_asm(&list));
  681. #endif
  682. return 0;
  683. }
  685. void print_indentation(struct QNode * p, int indentation) {
  686. printf("printing nodes with an indentation level of %d\n", indentation);
  687. while(p) {
  688. if (p->level == indentation) {
  689. add_indent(indentation);
  690. if (p->type == NODE_TYPE_BRANCH_START) {
  691. add_indent(indentation);
  692. printf("branch start\n");
  693. }
  694. else if (p->type == NODE_TYPE_BRANCH_END) {
  695. add_indent(indentation);
  696. printf("branch end\n");
  697. }
  698. else if (p->type == NODE_TYPE_BRANCH_CHOICE_START) {
  699. add_indent(indentation);
  700. printf("branch choice start\n");
  701. }
  702. else if (p->type == NODE_TYPE_BRANCH_CHOICE_END) {
  703. add_indent(indentation);
  704. printf("branch choice end\n");
  705. }
  706. else if (p->type == NODE_TYPE_NORMAL) {
  707. add_indent(indentation);
  708. printf("%d -> %d (data: %d)\n", p->index, p->ref, p->data);
  709. }
  710. }
  711. p = p->next;
  712. // #if NODE_TYPE == LINKED
  713. // #elif NODE_TYPE == TREE
  714. // else p = NULL;
  715. // #endif
  716. }
  717. }
  719. void fix(struct Queue * list) {
  720. int indent = 0;
  721. print_indentation(list->front, indent++);
  722. print_indentation(list->front, indent++);
  723. print_indentation(list->front, indent++);
  724. print_indentation(list->front, indent++);
  725. print_indentation(list->front, indent++);
  726. puts("NULL");
  727. }
  728.  
Powered by spacepaste. Paste removal.