spacepaste

Paste details

reply | raw

  1.  
  2. #include "stdio.h"
  3. #include "stdbool.h"
  4. // A C program to demonstrate linked list based implementation of queue
  5. // A linked list (LL) node to store a queue entry
  6. struct trie_QNode
  7. {
  8. char * rule_name;
  9. int rule_name_index;
  10. char * key;
  11. int index;
  12. char * rule_next;
  13. int rule_next_index;
  14. struct QNode *next;
  15. };
  17. // The queue, front stores the front node of LL and rear stores ths
  18. // last node of LL
  19. struct trie_Queue
  20. {
  21. struct trie_QNode *front, *rear;
  22. };
  24. // A utility function to create a new linked list node.
  25. struct trie_QNode* trie_newNode(char * a, int b, char * c, int d, char * e, int f)
  26. {
  27. struct trie_QNode *temp = (struct trie_QNode*)malloc(sizeof(struct trie_QNode));
  28. temp->rule_name = a;
  29. temp->rule_name_index = b;
  30. temp->key = c;
  31. temp->index = d;
  32. temp->rule_next = e;
  33. temp->rule_next_index = f;
  34. temp->next = NULL;
  35. return temp;
  36. }
  38. // A utility function to create an empty queue
  39. struct trie_Queue *trie_createQueue()
  40. {
  41. struct trie_Queue *q = (struct trie_Queue*)malloc(sizeof(struct trie_Queue));
  42. q->front = q->rear = NULL;
  43. return q;
  44. }
  46. void trie_store_asm(struct trie_Queue *q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index)
  47. {
  48. // Create a new LL node
  49. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  51. // If queue is empty, then new node is front and rear both
  52. if (q->rear == NULL)
  53. {
  54. q->front = q->rear = temp;
  55. q->rear->rule_next = NULL;
  56. q->rear->rule_next_index = -1;
  57. return;
  58. }
  60. // Add the new node at the end of queue and change rear
  61. if (q->rear) {
  62. q->rear->rule_next = rule_name;
  63. q->rear->rule_next_index = rule_name_index;
  64. }
  65. q->rear->next = temp;
  66. q->rear = temp;
  67. if (q->rear) {
  68. q->rear->rule_next = NULL;
  69. q->rear->rule_next_index = -1;
  70. }
  71. }
  73. void trie_store_asm2(struct trie_Queue *q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index)
  74. {
  75. // Create a new LL node
  76. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  78. // If queue is empty, then new node is front and rear both
  79. if (q->rear == NULL)
  80. {
  81. q->front = q->rear = temp;
  82. return;
  83. }
  85. // Add the new node at the end of queue and change rear
  86. if (q->rear) {
  87. q->rear->rule_next = rule_name;
  88. q->rear->rule_next_index = rule_name_index;
  89. }
  90. q->rear->next = temp;
  91. q->rear = temp;
  92. }
  94. void trie_store_asm3(struct trie_Queue *q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index)
  95. {
  96. // Create a new LL node
  97. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  99. // If queue is empty, then new node is front and rear both
  100. if (q->rear == NULL)
  101. {
  102. q->front = q->rear = temp;
  103. return;
  104. }
  106. // Add the new node at the end of queue and change rear
  107. q->rear->next = temp;
  108. q->rear = temp;
  109. }
  111. struct trie_QNode * trie_load_asm(struct trie_Queue **q)
  112. {
  113. // If queue is empty, return NULL.
  114. if ((q) == NULL) return NULL;
  115. if ((*q) == NULL) return NULL;
  116. if ((*q)->front == NULL)
  117. return NULL;
  119. // Store previous front and move front one node ahead
  120. struct trie_QNode *temp = (*q)->front;
  121. (*q)->front = (*q)->front->next;
  123. // If front becomes NULL, then change rear also as NULL
  124. if ((*q)->front == NULL)
  125. (*q)->rear = NULL;
  126. return temp;
  127. }
  129. int trie_queue_add(struct trie_Queue **q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index) {
  130. if (!(*q)) (*q) = trie_createQueue();
  131. trie_store_asm((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  132. return 0;
  133. }
  136. int trie_queue_add2(struct trie_Queue **q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index) {
  137. if (!(*q)) (*q) = trie_createQueue();
  138. trie_store_asm2((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  139. return 0;
  140. }
  142. int trie_queue_add3(struct trie_Queue **q, char * rule_name, int rule_name_index, char * key, int index, char * rule_next, int rule_next_index) {
  143. if (!(*q)) (*q) = trie_createQueue();
  144. trie_store_asm3((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  145. return 0;
  146. }
  148. char * trie_root = "root";
  149. char * trie_sub_root = "sub_root";
  150. char * trie_rule_prefix = "rule_";
  152. struct trie_Queue * trie_trie = NULL;
  154. int main(int argc, char **argv) {
  155. trie_queue_add(&trie_trie, trie_sub_root, -1, NULL, 0, trie_rule_prefix, 0); // root>0
  156. trie_queue_add(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  157. trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  158. trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  159. trie_queue_add3(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  160. trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  161. trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  162. trie_queue_add3(&trie_trie, trie_rule_prefix, 3, NULL, 1, NULL, -1); // 3>END
  163. struct trie_QNode * node = trie_newNode(NULL,0,NULL,0,NULL,0); // this gets freed anyway
  164. int nodes = 0;
  165. int start_indent = 0;
  166. int i = 0;
  167. for (i = 0; i < start_indent; i++) printf(" ");
  168. printf("struct TrieNode * %s = getNode(); \n", trie_root);
  169. for (i = 0; i < start_indent; i++) printf(" ");
  170. printf("struct TrieNode * %s = getNode(); \n", trie_sub_root);
  171. while (node != NULL) {
  172. // drain the list until empty
  173. if (node->key) free(node->key);
  174. free(node);
  175. node = trie_load_asm(&trie_trie);
  176. if (node == NULL) break;
  177. // pp(node)
  178. // pp(node->rule_name)
  179. // ps(node->rule_name)
  180. // pi(node->rule_name_index)
  181. // pp(node->key)
  182. // ps(node->key)
  183. // pi(node->index)
  184. // pp(node->rule_next)
  185. // ps(node->rule_next)
  186. // pi(node->rule_next_index)
  187. if (node->rule_next && node->rule_next_index != -1) {
  188. bool rule_does_not_exist = false;
  189. bool next_rule_does_not_exist = false;
  190. if (node->rule_name_index == -1) {
  191. // is sub_root
  192. if (rule_does_not_exist) {
  193. for (i = 0; i < start_indent+1; i++) printf(" ");
  194. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  195. }
  196. if (next_rule_does_not_exist) {
  197. for (i = 0; i < start_indent+1; i++) printf(" ");
  198. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  199. }
  200. for (i = 0; i < start_indent+1; i++) printf(" ");
  201. printf("insert(%s, \"%s\", %d, %s%d);\n", node->rule_name, node->key, node->index, node->rule_next, node->rule_next_index);
  202. }
  203. else {
  204. // is rule
  205. if (rule_does_not_exist) {
  206. for (i = 0; i < start_indent+2; i++) printf(" ");
  207. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  208. }
  209. if (next_rule_does_not_exist) {
  210. for (i = 0; i < start_indent+2; i++) printf(" ");
  211. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  212. }
  213. for (i = 0; i < start_indent+2; i++) printf(" ");
  214. printf("insert(%s%d, \"%s\", %d, %s%d);\n", node->rule_name, node->rule_name_index, node->key, node->index, node->rule_next, node->rule_next_index);
  215. }
  216. } else {
  217. if (node->rule_name_index == -1) {
  218. // is sub_root
  219. for (i = 0; i < start_indent+1; i++) printf(" ");
  220. printf("insert(%s, \"%s\", %d, NULL);\n", node->rule_name, node->key, node->index);
  221. } else {
  222. // is rule
  223. for (i = 0; i < start_indent+2; i++) printf(" ");
  224. printf("insert(%s%d, \"%s\", %d, NULL);\n", node->rule_name, node->rule_name_index, node->key, node->index);
  225. }
  226. }
  227. nodes++;
  228. }
  229. return 0;
  230. }
  231.  
Powered by spacepaste. Paste removal.