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;
  168. char co[5];
  169. void getbranchcontents(char * s) {
  170. memset(co,0,5);
  171. int ci = 0;
  172. for(; *s; s++) {
  173. if (*s == 'b') {
  174. continue;
  175. }
  176. if (*s == 'e' || *s == 'C') {
  177. break;
  178. }
  179. if (*s == ' ' || *s == '\n' || *s == '\t') continue;
  180. if (*s == 's') {
  181. s++;
  182. co[0] = *s;
  183. ci++;
  184. }
  185. }
  186. printf("c = %s\n", co);
  187. }
  189. void parse_branch(char * co) {
  190. itterations++;
  191. int actual_index_tmp = 0;
  192. char * zrule_name;
  193. int zrule_name_index;
  194. char * zkey;
  195. int zindex;
  196. if (itterations == 1) {
  197. zrule_name = trie_trie->rear->rule_name;
  198. zrule_name_index = trie_trie->rear->rule_name_index;
  199. zkey = 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("zrule_name = %s\n", zrule_name);
  207. printf("zkey = %s\n", zkey);
  208. 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));
  209. trie_queue_add3(&trie_trie, zrule_name, zrule_name_index, strdup(zkey), zindex, trie_rule_prefix, rule_index_tmp-(itterations==1?0:1));
  210. for (int level = 0; co[level]; level++) {
  211. char tmp[2];
  212. tmp[0] = co[level];
  213. tmp[1] = '\0';
  214. 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);
  215. if (itterations == 1) {
  216. if (co[level+1]) {
  217. puts("RULE");
  218. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, rule_index_tmp);
  219. } else {
  220. puts("FINAL");
  221. trie_queue_add2(&trie_trie, trie_rule_prefix, rule_index_tmp-1, strdup(tmp), actual_index_tmp, trie_rule_prefix, final_rule);
  222. }
  223. } else {
  224. puts("RULE FINAL");
  225. 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);
  226. }
  227. rule_index_tmp++;
  228. if (itterations == 1 && co[level+1]) final_rule++;
  229. actual_index_tmp++;
  230. }
  231. }
  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. getbranchcontents(s);
  264. parse_branch(co);
  265. memset(co,0,5);
  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. if (final_rule) {
  277. rule_index = final_rule;
  278. update_on_next_pass = true;
  279. final_rule = 0;
  280. }
  281. continue;
  282. }
  283. if (*s == ' ' || *s == '\n' || *s == '\t') continue;
  284. if (*s == 'i') {
  285. passed_first = true;
  286. continue;
  287. }
  288. if (*s == 's' || *s == ':') {
  289. s++;
  290. printf("key: %c\n", *s);
  291. if (!part_of_branch) {
  292. if (!passed_first) {
  293. if (passed_next) {
  294. if (update_on_next_pass/* && (tmp.type & STR_TYPE_DIGIT || tmp.type & STR_TYPE_BINARY)*/) {
  295. rule_index = rule_index_tmp-1;
  296. update_on_next_pass = false;
  297. }
  298. actual_index = 0;
  299. passed_next = false;
  300. char tmp[2];
  301. tmp[0] = *s;
  302. tmp[1] = '\0';
  303. trie_queue_add(&trie_trie, trie_sub_root, -1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  304. }
  305. else {
  306. rule_index++;
  307. actual_index++;
  308. char tmp[2];
  309. tmp[0] = *s;
  310. tmp[1] = '\0';
  311. trie_queue_add(&trie_trie, trie_rule_prefix, rule_index-1, strdup(tmp), actual_index, trie_rule_prefix, rule_index);
  312. }
  313. } else {
  314. passed_first = false;
  315. passed_next = true;
  316. }
  317. }
  318. }
  319. }
  320. // trie_queue_add(&trie_trie, trie_sub_root, -1, NULL, 0, trie_rule_prefix, 0); // root>0
  321. // trie_queue_add(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  322. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  323. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  324. // trie_queue_add3(&trie_trie, trie_rule_prefix, 0, NULL, 1, trie_rule_prefix, 1); // 0>1
  325. // trie_queue_add(&trie_trie, trie_rule_prefix, 1, NULL, 1, trie_rule_prefix, 2); // 1>2
  326. // trie_queue_add2(&trie_trie, trie_rule_prefix, 2, NULL, 1, trie_rule_prefix, 3); // 2>3
  327. // trie_queue_add3(&trie_trie, trie_rule_prefix, 3, NULL, 1, NULL, -1); // 3>END
  328. struct trie_QNode * node = trie_newNode(NULL,0,NULL,0,NULL,0); // this gets freed anyway
  329. int nodes = 0;
  330. int start_indent = 0;
  331. int i = 0;
  332. for (i = 0; i < start_indent; i++) printf(" ");
  333. printf("struct TrieNode * %s = getNode(); \n", trie_root);
  334. for (i = 0; i < start_indent; i++) printf(" ");
  335. printf("struct TrieNode * %s = getNode(); \n", trie_sub_root);
  336. while (node != NULL) {
  337. // drain the list until empty
  338. if (node->key) free(node->key);
  339. free(node);
  340. node = trie_load_asm(&trie_trie);
  341. if (node == NULL) break;
  342. // pp(node)
  343. // pp(node->rule_name)
  344. // ps(node->rule_name)
  345. // pi(node->rule_name_index)
  346. // pp(node->key)
  347. // ps(node->key)
  348. // pi(node->index)
  349. // pp(node->rule_next)
  350. // ps(node->rule_next)
  351. // pi(node->rule_next_index)
  352. if (node->rule_next && node->rule_next_index != -1) {
  353. bool rule_does_not_exist = false;
  354. bool next_rule_does_not_exist = false;
  355. if (node->rule_name_index == -1) {
  356. // is sub_root
  357. if (rule_does_not_exist) {
  358. for (i = 0; i < start_indent+1; i++) printf(" ");
  359. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  360. }
  361. if (next_rule_does_not_exist) {
  362. for (i = 0; i < start_indent+1; i++) printf(" ");
  363. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  364. }
  365. for (i = 0; i < start_indent+1; i++) printf(" ");
  366. printf("insert(%s, \"%s\", %d, %s%d);\n", node->rule_name, node->key, node->index, node->rule_next, node->rule_next_index);
  367. }
  368. else {
  369. // is rule
  370. if (rule_does_not_exist) {
  371. for (i = 0; i < start_indent+2; i++) printf(" ");
  372. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_name, node->rule_name_index);
  373. }
  374. if (next_rule_does_not_exist) {
  375. for (i = 0; i < start_indent+2; i++) printf(" ");
  376. printf("struct TrieNode * %s%d = getNode(); \n", node->rule_next, node->rule_next_index);
  377. }
  378. for (i = 0; i < start_indent+2; i++) printf(" ");
  379. 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);
  380. }
  381. } else {
  382. if (node->rule_name_index == -1) {
  383. // is sub_root
  384. for (i = 0; i < start_indent+1; i++) printf(" ");
  385. printf("insert(%s, \"%s\", %d, NULL);\n", node->rule_name, node->key, node->index);
  386. } else {
  387. // is rule
  388. for (i = 0; i < start_indent+2; i++) printf(" ");
  389. printf("insert(%s%d, \"%s\", %d, NULL);\n", node->rule_name, node->rule_name_index, node->key, node->index);
  390. }
  391. }
  392. nodes++;
  393. }
  394. return 0;
  395. }
  396.  
Powered by spacepaste. Paste removal.