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(2);
  171. memset(c,0,2);
  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. int zrule_name_index;
  192. char * zkey;
  193. int zindex;
  194. void parse_branch(char * co) {
  195. itterations++;
  196. int actual_index_tmp = 0;
  197. if (itterations == 1) {
  198. zrule_name_index = trie_trie->rear->rule_name_index;
  199. zkey = strdup(trie_trie->rear->key);
  200. zindex = trie_trie->rear->index;
  201. rule_index_tmp = rule_index+1;
  202. final_rule = rule_index_tmp;
  203. }
  204. else if (itterations == 2) rule_index_tmp++;
  205. actual_index_tmp = actual_index+1;
  206. printf("zkey = %s\n", zkey);
  207. printf("insert(%s%d, \"%s\", %d, %s%d);\n", trie_rule_prefix, zrule_name_index, zkey, zindex, trie_rule_prefix, rule_index_tmp-(itterations==1?0:1));
  208. trie_queue_add3(&trie_trie, trie_rule_prefix, zrule_name_index, strdup(zkey), zindex, trie_rule_prefix, rule_index_tmp-(itterations==1?0:1));
  209. for (int level = 0; co[level]; level++) {
  210. char tmp[2];
  211. tmp[0] = co[level];
  212. tmp[1] = '\0';
  213. 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);
  214. if (itterations == 1) {
  215. if (co[level+1]) {
  216. puts("RULE");
  217. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, rule_index_tmp);
  218. } else {
  219. puts("FINAL");
  220. trie_queue_add2(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, final_rule);
  221. }
  222. } else {
  223. puts("RULE FINAL");
  224. 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);
  225. }
  226. rule_index_tmp++;
  227. if (itterations == 1 && co[level+1]) final_rule++;
  228. actual_index_tmp++;
  229. }
  230. }
  231. char * co = NULL;
  232. int main(int argc, char **argv) {
  233. /*
  234. def0:
  235. 35:NULL
  236. 85:NULL
  238. rule1 : |1|2|def0|6|
  239. */
  241. char * s = "\
  242. i:\
  243. s1\
  244. s2\
  245. b\
  246. C\
  247. s3\
  248. s5\
  249. C\
  250. s8\
  251. s5\
  252. e\
  253. s6"; // for the sake of simplicity branches contain full strings only, not individual characters
  254. rule_index++;
  255. for(; *s; s++) {
  256. if (*s == 'b') {
  257. puts("branch start");
  258. part_of_branch = true;
  259. itterations = 0;
  260. for(; *s; s++) {
  261. if (*s == 'C') {
  262. s++;
  263. co = getbranchcontents(s);
  264. parse_branch(co);
  265. free(co);
  266. };
  267. if (*s == 'e') break;
  268. }
  269. if (*s == 'e') s--;
  270. continue;
  271. }
  272. if (*s == 'e') {
  273. puts("branch end");
  274. part_of_branch = false;
  275. itterations = 0;
  276. zrule_name_index = 0;
  277. free(zkey);
  278. zkey = NULL;
  279. zindex = 0;
  280. if (final_rule) {
  281. rule_index = final_rule;
  282. update_on_next_pass = true;
  283. final_rule = 0;
  284. }
  285. continue;
  286. }
  287. if (*s == ' ' || *s == '\n' || *s == '\t') continue;
  288. if (*s == 'i') {
  289. passed_first = true;
  290. continue;
  291. }
  292. if (*s == 's' || *s == ':') {
  293. s++;
  294. printf("key: %c\n", *s);
  295. if (part_of_branch) {
  296. }
  297. if (!part_of_branch) {
  298. if (!passed_first) {
  299. if (passed_next) {
  300. if (update_on_next_pass/* && (tmp.type & STR_TYPE_DIGIT || tmp.type & STR_TYPE_BINARY)*/) {
  301. rule_index = rule_index_tmp-1;
  302. update_on_next_pass = false;
  303. }
  304. actual_index = 0;
  305. passed_next = false;
  306. char tmp[2];
  307. tmp[0] = *s;
  308. tmp[1] = '\0';
  309. trie_queue_add(&trie_trie, trie_sub_root, -1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  310. }
  311. else {
  312. rule_index++;
  313. actual_index++;
  314. char tmp[2];
  315. tmp[0] = *s;
  316. tmp[1] = '\0';
  317. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index-1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  318. }
  319. } else {
  320. passed_first = false;
  321. passed_next = true;
  322. }
  323. }
  324. }
  325. }
  326. // trie_queue_add(&trie_trie, trie_sub_root, -1, NULL, 0, trie_rule_prefix, 0); // root>0
  327. // trie_queue_add(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  328. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  329. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  330. // trie_queue_add3(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  331. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  332. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  333. // trie_queue_add3(&trie_trie, trie_rule_prefix, 3, NULL, 1, NULL, -1); // 3>END
  334. struct trie_QNode * node = trie_newNode(NULL,0,NULL,0,NULL,0); // this gets freed anyway
  335. int nodes = 0;
  336. int start_indent = 0;
  337. int i = 0;
  338. for (i = 0; i < start_indent; i++) printf(" ");
  339. printf("struct TrieNode * %s = getNode(); \n", trie_root);
  340. for (i = 0; i < start_indent; i++) printf(" ");
  341. printf("struct TrieNode * %s = getNode(); \n", trie_sub_root);
  342. while (node != NULL) {
  343. // drain the list until empty
  344. if (node->key) free(node->key);
  345. free(node);
  346. node = trie_load_asm(&trie_trie);
  347. if (node == NULL) break;
  348. // pp(node)
  349. // pp(node->rule_name)
  350. // ps(node->rule_name)
  351. // pi(node->rule_name_index)
  352. // pp(node->key)
  353. // ps(node->key)
  354. // pi(node->index)
  355. // pp(node->rule_next)
  356. // ps(node->rule_next)
  357. // pi(node->rule_next_index)
  358. if (node->rule_next && node->rule_next_index != -1) {
  359. bool rule_does_not_exist = false;
  360. bool next_rule_does_not_exist = false;
  361. if (node->rule_name_index == -1) {
  362. // is sub_root
  363. if (rule_does_not_exist) {
  364. for (i = 0; i < start_indent+1; i++) printf(" ");
  365. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  366. }
  367. if (next_rule_does_not_exist) {
  368. for (i = 0; i < start_indent+1; i++) printf(" ");
  369. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  370. }
  371. for (i = 0; i < start_indent+1; i++) printf(" ");
  372. printf("insert(%s, \"%s\", %d, %s%d);\n", node->rule_name, node->key, node->index, node->rule_next, node->rule_next_index);
  373. }
  374. else {
  375. // is rule
  376. if (rule_does_not_exist) {
  377. for (i = 0; i < start_indent+2; i++) printf(" ");
  378. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  379. }
  380. if (next_rule_does_not_exist) {
  381. for (i = 0; i < start_indent+2; i++) printf(" ");
  382. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  383. }
  384. for (i = 0; i < start_indent+2; i++) printf(" ");
  385. 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);
  386. }
  387. } else {
  388. if (node->rule_name_index == -1) {
  389. // is sub_root
  390. for (i = 0; i < start_indent+1; i++) printf(" ");
  391. printf("insert(%s, \"%s\", %d, NULL);\n", node->rule_name, node->key, node->index);
  392. } else {
  393. // is rule
  394. for (i = 0; i < start_indent+2; i++) printf(" ");
  395. printf("insert(%s%d, \"%s\", %d, NULL);\n", node->rule_name, node->rule_name_index, node->key, node->index);
  396. }
  397. }
  398. nodes++;
  399. }
  400. free(trie_trie);
  401. return 0;
  402. }
  403.  
Powered by spacepaste. Paste removal.