spacepaste

Paste details

reply | raw

  1.  
  2. #include <stdbool.h>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. // A C program to demonstrate linked list based implementation of queue
  7. // A linked list (LL) node to store a queue entry
  8. struct trie_QNode
  9. {
  10. char * rule_name;
  11. int rule_name_index;
  12. char * key;
  13. int index;
  14. char * rule_next;
  15. int rule_next_index;
  16. struct trie_QNode *next;
  17. };
  19. // The queue, front stores the front node of LL and rear stores ths
  20. // last node of LL
  21. struct trie_Queue
  22. {
  23. struct trie_QNode *front, *rear;
  24. };
  26. // A utility function to create a new linked list node.
  27. struct trie_QNode* trie_newNode(char * a, int b, char * c, int d, char * e, int f)
  28. {
  29. struct trie_QNode *temp = (struct trie_QNode*)malloc(sizeof(struct trie_QNode));
  30. temp->rule_name = a;
  31. temp->rule_name_index = b;
  32. temp->key = c;
  33. temp->index = d;
  34. temp->rule_next = e;
  35. temp->rule_next_index = f;
  36. temp->next = NULL;
  37. return temp;
  38. }
  40. // A utility function to create an empty queue
  41. struct trie_Queue *trie_createQueue()
  42. {
  43. struct trie_Queue *q = (struct trie_Queue*)malloc(sizeof(struct trie_Queue));
  44. q->front = q->rear = NULL;
  45. return q;
  46. }
  48. 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)
  49. {
  50. // Create a new LL node
  51. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  53. // If queue is empty, then new node is front and rear both
  54. if (q->rear == NULL)
  55. {
  56. q->front = q->rear = temp;
  57. q->rear->rule_next = NULL;
  58. q->rear->rule_next_index = -1;
  59. return;
  60. }
  62. // Add the new node at the end of queue and change rear
  63. if (q->rear) {
  64. q->rear->rule_next = rule_name;
  65. q->rear->rule_next_index = rule_name_index;
  66. }
  67. q->rear->next = temp;
  68. q->rear = temp;
  69. if (q->rear) {
  70. q->rear->rule_next = NULL;
  71. q->rear->rule_next_index = -1;
  72. }
  73. }
  75. 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)
  76. {
  77. // Create a new LL node
  78. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  80. // If queue is empty, then new node is front and rear both
  81. if (q->rear == NULL)
  82. {
  83. q->front = q->rear = temp;
  84. return;
  85. }
  87. // Add the new node at the end of queue and change rear
  88. if (q->rear) {
  89. q->rear->rule_next = rule_name;
  90. q->rear->rule_next_index = rule_name_index;
  91. }
  92. q->rear->next = temp;
  93. q->rear = temp;
  94. }
  96. 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)
  97. {
  98. // Create a new LL node
  99. struct trie_QNode *temp = trie_newNode(rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  101. // If queue is empty, then new node is front and rear both
  102. if (q->rear == NULL)
  103. {
  104. q->front = q->rear = temp;
  105. return;
  106. }
  108. // Add the new node at the end of queue and change rear
  109. q->rear->next = temp;
  110. q->rear = temp;
  111. }
  113. struct trie_QNode * trie_load_asm(struct trie_Queue **q)
  114. {
  115. // If queue is empty, return NULL.
  116. if ((q) == NULL) return NULL;
  117. if ((*q) == NULL) return NULL;
  118. if ((*q)->front == NULL)
  119. return NULL;
  121. // Store previous front and move front one node ahead
  122. struct trie_QNode *temp = (*q)->front;
  123. (*q)->front = (*q)->front->next;
  125. // If front becomes NULL, then change rear also as NULL
  126. if ((*q)->front == NULL)
  127. (*q)->rear = NULL;
  128. return temp;
  129. }
  131. 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) {
  132. if (!(*q)) (*q) = trie_createQueue();
  133. trie_store_asm((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  134. return 0;
  135. }
  138. 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) {
  139. if (!(*q)) (*q) = trie_createQueue();
  140. trie_store_asm2((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  141. return 0;
  142. }
  144. 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) {
  145. if (!(*q)) (*q) = trie_createQueue();
  146. trie_store_asm3((*q), rule_name,rule_name_index,key,index,rule_next,rule_next_index);
  147. return 0;
  148. }
  150. char * trie_root = "root";
  151. char * trie_sub_root = "sub_root";
  152. char * trie_rule_prefix = "rule_";
  154. struct trie_Queue * trie_trie = NULL;
  155. int rule_index = -1;
  156. int actual_index = 0;
  157. bool passed_first = false;
  158. bool passed_next = false;
  159. int update_on_next_pass = false;
  161. int final_rule = 0;
  162. int rule_index_tmp = 0;
  163. int actual_index_tmp = 0;
  165. bool part_of_branch = false;
  167. int itterations = 0;
  169. char * getbranchcontents(char * s) {
  170. char * c = malloc(500);
  171. memset(c,0,500);
  172. int ci = 0;
  173. for(; *s; s++) {
  174. if (*s == 'b') {
  175. continue;
  176. }
  177. if (*s == 'e' || *s == 'C') {
  178. break;
  179. }
  180. if (*s == ' ' || *s == '\n' || *s == '\t') continue;
  181. if (*s == 's') {
  182. s++;
  183. c[ci] = *s;
  184. ci++;
  185. }
  186. }
  187. printf("c = %s\n", c);
  188. return c;
  189. }
  191. parse_branch(char * co) {
  192. itterations++;
  193. int actual_index_tmp = 0;
  194. char * zrule_name;
  195. int zrule_name_index;
  196. char * zkey;
  197. int zindex;
  198. if (itterations == 1) {
  199. zrule_name = trie_trie->rear->rule_name;
  200. zrule_name_index = trie_trie->rear->rule_name_index;
  201. zkey = trie_trie->rear->key;
  202. zindex = trie_trie->rear->index;
  203. rule_index_tmp = rule_index+1;
  204. final_rule = rule_index_tmp;
  205. }
  206. else if (itterations == 2) rule_index_tmp++;
  207. actual_index_tmp = actual_index+1;
  208. printf("zrule_name = %s\n", zrule_name);
  209. printf("zkey = %s\n", zkey);
  210. printf("insert(%s%d, \"%s\", %d, %s%d);\n", zrule_name, zrule_name_index, zkey, zindex, trie_rule_prefix, rule_index_tmp-(itterations==1?0:1));
  211. trie_queue_add3(&trie_trie, zrule_name, zrule_name_index, strdup(zkey), zindex, trie_rule_prefix, rule_index_tmp-(itterations==1?0:1));
  212. for (int level = 0; co[level]; level++) {
  213. char tmp[2];
  214. tmp[0] = co[level];
  215. tmp[1] = '\0';
  216. printf("insert(%s%d, \"%s\", %d, %s%d);\n", trie_rule_prefix, rule_index_tmp-1, tmp, actual_index_tmp, trie_rule_prefix, co[level+1]?rule_index_tmp:final_rule);
  217. if (itterations == 1) {
  218. if (co[level+1]) {
  219. puts("RULE");
  220. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, rule_index_tmp);
  221. } else {
  222. puts("FINAL");
  223. trie_queue_add2(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, final_rule);
  224. }
  225. } else {
  226. puts("RULE FINAL");
  227. trie_queue_add3(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, co[level+1]?rule_index_tmp:final_rule);
  228. }
  229. rule_index_tmp++;
  230. if (itterations == 1 && co[level+1]) final_rule++;
  231. actual_index_tmp++;
  232. }
  233. }
  234. char * co = NULL;
  235. int main(int argc, char **argv) {
  236. /*
  237. def0:
  238. 35:NULL
  239. 85:NULL
  241. rule1 : |1|2|def0|6|
  242. */
  244. char * s = "\
  245. i:\
  246. s1\
  247. s2\
  248. b\
  249. C\
  250. s3\
  251. s5\
  252. C\
  253. s8\
  254. s5\
  255. e\
  256. s6"; // for the sake of simplicity branches contain full strings only, not individual characters
  257. rule_index++;
  258. for(; *s; s++) {
  259. if (*s == 'b') {
  260. puts("branch start");
  261. part_of_branch = true;
  262. itterations = 0;
  263. for(; *s; s++) {
  264. if (*s == 'C') {
  265. s++;
  266. co = getbranchcontents(s);
  267. parse_branch(co);
  268. free(co);
  269. };
  270. if (*s == 'e') break;
  271. }
  272. if (*s == 'e') s--;
  273. continue;
  274. }
  275. if (*s == 'e') {
  276. puts("branch end");
  277. part_of_branch = false;
  278. itterations = 0;
  279. if (final_rule) {
  280. rule_index = final_rule;
  281. update_on_next_pass = true;
  282. final_rule = 0;
  283. }
  284. continue;
  285. }
  286. if (*s == ' ' || *s == '\n' || *s == '\t') continue;
  287. if (*s == 'i') {
  288. passed_first = true;
  289. continue;
  290. }
  291. if (*s == 's' || *s == ':') {
  292. s++;
  293. printf("key: %c\n", *s);
  294. if (part_of_branch) {
  295. }
  296. if (!part_of_branch) {
  297. if (!passed_first) {
  298. if (passed_next) {
  299. if (update_on_next_pass/* && (tmp.type & STR_TYPE_DIGIT || tmp.type & STR_TYPE_BINARY)*/) {
  300. rule_index = rule_index_tmp-1;
  301. update_on_next_pass = false;
  302. }
  303. actual_index = 0;
  304. passed_next = false;
  305. char tmp[2];
  306. tmp[0] = *s;
  307. tmp[1] = '\0';
  308. trie_queue_add(&trie_trie, trie_sub_root, -1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  309. }
  310. else {
  311. rule_index++;
  312. actual_index++;
  313. char tmp[2];
  314. tmp[0] = *s;
  315. tmp[1] = '\0';
  316. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index-1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  317. }
  318. } else {
  319. passed_first = false;
  320. passed_next = true;
  321. }
  322. }
  323. }
  324. }
  325. // trie_queue_add(&trie_trie, trie_sub_root, -1, NULL, 0, trie_rule_prefix, 0); // root>0
  326. // trie_queue_add(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  327. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  328. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  329. // trie_queue_add3(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  330. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  331. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  332. // trie_queue_add3(&trie_trie, trie_rule_prefix, 3, NULL, 1, NULL, -1); // 3>END
  333. struct trie_QNode * node = trie_newNode(NULL,0,NULL,0,NULL,0); // this gets freed anyway
  334. int nodes = 0;
  335. int start_indent = 0;
  336. int i = 0;
  337. for (i = 0; i < start_indent; i++) printf(" ");
  338. printf("struct TrieNode * %s = getNode(); \n", trie_root);
  339. for (i = 0; i < start_indent; i++) printf(" ");
  340. printf("struct TrieNode * %s = getNode(); \n", trie_sub_root);
  341. while (node != NULL) {
  342. // drain the list until empty
  343. if (node->key) free(node->key);
  344. free(node);
  345. node = trie_load_asm(&trie_trie);
  346. if (node == NULL) break;
  347. // pp(node)
  348. // pp(node->rule_name)
  349. // ps(node->rule_name)
  350. // pi(node->rule_name_index)
  351. // pp(node->key)
  352. // ps(node->key)
  353. // pi(node->index)
  354. // pp(node->rule_next)
  355. // ps(node->rule_next)
  356. // pi(node->rule_next_index)
  357. if (node->rule_next && node->rule_next_index != -1) {
  358. bool rule_does_not_exist = false;
  359. bool next_rule_does_not_exist = false;
  360. if (node->rule_name_index == -1) {
  361. // is sub_root
  362. if (rule_does_not_exist) {
  363. for (i = 0; i < start_indent+1; i++) printf(" ");
  364. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  365. }
  366. if (next_rule_does_not_exist) {
  367. for (i = 0; i < start_indent+1; i++) printf(" ");
  368. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  369. }
  370. for (i = 0; i < start_indent+1; i++) printf(" ");
  371. printf("insert(%s, \"%s\", %d, %s%d);\n", node->rule_name, node->key, node->index, node->rule_next, node->rule_next_index);
  372. }
  373. else {
  374. // is rule
  375. if (rule_does_not_exist) {
  376. for (i = 0; i < start_indent+2; i++) printf(" ");
  377. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  378. }
  379. if (next_rule_does_not_exist) {
  380. for (i = 0; i < start_indent+2; i++) printf(" ");
  381. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  382. }
  383. for (i = 0; i < start_indent+2; i++) printf(" ");
  384. 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);
  385. }
  386. } else {
  387. if (node->rule_name_index == -1) {
  388. // is sub_root
  389. for (i = 0; i < start_indent+1; i++) printf(" ");
  390. printf("insert(%s, \"%s\", %d, NULL);\n", node->rule_name, node->key, node->index);
  391. } else {
  392. // is rule
  393. for (i = 0; i < start_indent+2; i++) printf(" ");
  394. printf("insert(%s%d, \"%s\", %d, NULL);\n", node->rule_name, node->rule_name_index, node->key, node->index);
  395. }
  396. }
  397. nodes++;
  398. }
  399. return 0;
  400. }
  401.  
Powered by spacepaste. Paste removal.