spacepaste

Paste details

reply | raw

  1.  
  2. $ ./trie_binary
  3. ----------------------------------------------------------------------->called init_aux() at line 348 from vcpu/../Shell/builtins/libstring.h
  4. ----------------------------------------------------------------------->called init_env() at line 327 from vcpu/../Shell/builtins/libstring.h
  5. ----------------------------------------------------------------------->called init_argX() at line 336 from vcpu/../Shell/builtins/libstring.h
  6. segment.string = 1
  7. branch_index = 0
  8. segments_curr = 0x55608c96c360
  9. segments_prev = 0x55608c96c360
  10. branch_index = 0
  11. index = 1
  12. level = 0
  13. key[level] = 1
  14. pCrawl = 0x55608c96c360
  15. pCrawl->children = 0x55608c96c360
  16. pCrawl->children[index] = 0x55608c96d420
  17. pCrawl->next_count = 2
  18. pCrawl->next = 0x55608c96d3a0
  19. pCrawl->branch = true
  20. pCrawl->next[branch_index] = 0x55608c96c460
  21. modifying root
  22. pCrawl->branch = true
  23. segments_curr = 0x55608c96c460
  24. segments_prev = 0x55608c96c360
  25. branches = true
  26. creating backtrack reference
  27. pCrawl = 0x55608c96c260
  28. segments_curr = 0x55608c96c460
  29. segments_prev = 0x55608c96c360
  30. level = 0
  31. index = 1
  32. idx = 0
  33. key = 12456
  34. successfull
  35. idx = 0
  36. result1 = true
  37. idx = 1
  38. segment.string = 2
  39. branch_index = 0
  40. segments_curr = 0x55608c96c460
  41. segments_prev = 0x55608c96c460
  42. branch_index = 0
  43. index = 2
  44. level = 0
  45. key[level] = 2
  46. pCrawl = 0x55608c96c460
  47. pCrawl->children = 0x55608c96c460
  48. pCrawl->children[index] = 0x55608c96d5a0
  49. pCrawl->next_count = 1
  50. pCrawl->next = 0x55608c96d520
  51. pCrawl->branch = false
  52. pCrawl->next[branch_index] = 0x55608c96c560
  53. modifying root
  54. pCrawl->branch = false
  55. segments_curr = 0x55608c96c560
  56. segments_prev = 0x55608c96c460
  57. branches = false
  58. idx = 1
  59. result1 = true
  60. idx = 2
  61. segment.string = 4
  62. branch_index = 0
  63. segments_curr = 0x55608c96c560
  64. segments_prev = 0x55608c96c560
  65. branch_index = 0
  66. index = 4
  67. level = 0
  68. key[level] = 4
  69. pCrawl = 0x55608c96c560
  70. pCrawl->children = 0x55608c96c560
  71. pCrawl->children[index] = (nil)
  72. not found
  73. segments_curr = 0x55608c96c560
  74. segments_prev = 0x55608c96c560
  75. branches = false
  76. idx = 2
  77. result1 = false
  78. loading last backtrack reference
  79. pCrawl = 0x55608c96cee0
  80. segments = 0x55608c96c560
  81. level = 3
  82. index = 4
  83. idx = 2
  84. key = 12456
  85. Backtrack_node->pCrawl = 0x55608c96c260
  86. Backtrack_node->segments = 0x55608c96c360
  87. Backtrack_node->level = 0
  88. Backtrack_node->index = 1
  89. Backtrack_node->idx = 0
  90. Backtrack_node->key = 12456
  91. segment.string = 1
  92. branch_index = 1
  93. segments_curr = 0x55608c96c360
  94. segments_prev = 0x55608c96c360
  95. branch_index = 1
  96. index = 1
  97. level = 0
  98. key[level] = 1
  99. pCrawl = 0x55608c96c360
  100. pCrawl->children = 0x55608c96c360
  101. pCrawl->children[index] = 0x55608c96d420
  102. pCrawl->next_count = 2
  103. pCrawl->next = 0x55608c96d3a0
  104. pCrawl->branch = true
  105. pCrawl->next[branch_index] = 0x55608c96c860
  106. modifying root
  107. pCrawl->branch = true
  108. segments_curr = 0x55608c96c860
  109. segments_prev = 0x55608c96c360
  110. branches = true
  111. creating backtrack reference
  112. pCrawl = 0x55608c96c260
  113. segments_curr = 0x55608c96c860
  114. segments_prev = 0x55608c96c360
  115. level = 0
  116. index = 1
  117. idx = 0
  118. key = 12456
  119. successfull
  120. idx = 0
  121. result1 = true
  122. idx = 1
  123. segment.string = 2
  124. branch_index = 0
  125. segments_curr = 0x55608c96c860
  126. segments_prev = 0x55608c96c860
  127. branch_index = 0
  128. index = 2
  129. level = 0
  130. key[level] = 2
  131. pCrawl = 0x55608c96c860
  132. pCrawl->children = 0x55608c96c860
  133. pCrawl->children[index] = 0x55608c96e060
  134. pCrawl->next_count = 1
  135. pCrawl->next = 0x55608c96cce0
  136. pCrawl->branch = false
  137. pCrawl->next[branch_index] = 0x55608c96c960
  138. modifying root
  139. pCrawl->branch = false
  140. segments_curr = 0x55608c96c960
  141. segments_prev = 0x55608c96c860
  142. branches = false
  143. idx = 1
  144. result1 = true
  145. idx = 2
  146. segment.string = 4
  147. branch_index = 0
  148. segments_curr = 0x55608c96c960
  149. segments_prev = 0x55608c96c960
  150. branch_index = 0
  151. index = 4
  152. level = 0
  153. key[level] = 4
  154. pCrawl = 0x55608c96c960
  155. pCrawl->children = 0x55608c96c960
  156. pCrawl->children[index] = 0x55608c96e1e0
  157. pCrawl->next_count = 1
  158. pCrawl->next = 0x55608c96e160
  159. pCrawl->branch = false
  160. pCrawl->next[branch_index] = 0x55608c96ca60
  161. modifying root
  162. pCrawl->branch = false
  163. segments_curr = 0x55608c96ca60
  164. segments_prev = 0x55608c96c960
  165. branches = false
  166. idx = 2
  167. result1 = true
  168. idx = 3
  169. segment.string = 5
  170. branch_index = 0
  171. segments_curr = 0x55608c96ca60
  172. segments_prev = 0x55608c96ca60
  173. branch_index = 0
  174. index = 5
  175. level = 0
  176. key[level] = 5
  177. pCrawl = 0x55608c96ca60
  178. pCrawl->children = 0x55608c96ca60
  179. pCrawl->children[index] = 0x55608c96e360
  180. pCrawl->next_count = 1
  181. pCrawl->next = 0x55608c96e2e0
  182. pCrawl->branch = false
  183. pCrawl->next[branch_index] = 0x55608c96cb60
  184. modifying root
  185. pCrawl->branch = false
  186. segments_curr = 0x55608c96cb60
  187. segments_prev = 0x55608c96ca60
  188. branches = false
  189. idx = 3
  190. result1 = true
  191. idx = 4
  192. segment.string = 6
  193. branch_index = 0
  194. segments_curr = 0x55608c96cb60
  195. segments_prev = 0x55608c96cb60
  196. branch_index = 0
  197. index = 6
  198. level = 0
  199. key[level] = 6
  200. pCrawl = 0x55608c96cb60
  201. pCrawl->children = 0x55608c96cb60
  202. pCrawl->children[index] = 0x55608c96e4e0
  203. pCrawl->next_count = 1
  204. pCrawl->next = 0x55608c96e460
  205. pCrawl->branch = false
  206. pCrawl->next[branch_index] = (nil)
  207. pCrawl->branch = false
  208. segments_curr = 0x55608c96cb60
  209. segments_prev = 0x55608c96cb60
  210. branches = false
  211. idx = 4
  212. result1 = true
  213. idx = 5
  214. 12456 --- Present in trie
  216. $ cat trie_binary.c
  217. // C implementation of search and insert operations
  218. // on Trie
  219. #include <stdio.h>
  220. #include <stdlib.h>
  221. #include <string.h>
  222. #include <stdbool.h>
  223. #include "../Shell/builtins/printfmacro.h"
  224. #include "../Shell/builtins/regex_str.h"
  228. // backtracking history
  229. // A C program to demonstrate linked list based implementation of queue
  230. // A linked list (LL) node to store a queue entry
  231. struct Backtrack_QNode
  232. {
  233. struct TrieNode *pCrawl;
  234. struct TrieNode *segments;
  235. int level;
  236. int index;
  237. int idx;
  238. const char * key;
  239. struct Backtrack_QNode *next;
  240. };
  242. // The queue, front stores the front node of LL and rear stores ths
  243. // last node of LL
  244. struct Backtrack_Queue
  245. {
  246. struct Backtrack_QNode *front, *rear;
  247. };
  249. // A utility function to create a new linked list node.
  250. struct Backtrack_QNode* Backtrack_newNode(struct TrieNode *pCrawl, struct TrieNode *segments, int level, int index, int idx, const char * key)
  251. {
  252. struct Backtrack_QNode *temp = (struct Backtrack_QNode*)malloc(sizeof(struct Backtrack_QNode));
  253. temp->pCrawl = pCrawl;
  254. temp->segments = segments;
  255. temp->level = level;
  256. temp->index = index;
  257. temp->idx = idx;
  258. temp->key = key;
  259. temp->next = NULL;
  260. return temp;
  261. }
  263. // A utility function to create an empty queue
  264. struct Backtrack_Queue *Backtrack_createQueue()
  265. {
  266. struct Backtrack_Queue *q = (struct Backtrack_Queue*)malloc(sizeof(struct Backtrack_Queue));
  267. q->front = q->rear = NULL;
  268. return q;
  269. }
  271. void Backtrack_store_asm(struct Backtrack_Queue **qq, struct TrieNode *pCrawl, struct TrieNode *segments, int level, int index, int idx, const char * key)
  272. {
  273. if (*qq == NULL)
  274. *qq = Backtrack_createQueue();
  276. // Create a new LL node
  277. struct Backtrack_QNode *temp = Backtrack_newNode(pCrawl, segments, level, index, idx, key);
  279. // If queue is empty, then new node is front and rear both
  280. if ((*qq)->rear == NULL)
  281. {
  282. (*qq)->front = (*qq)->rear = temp;
  283. return;
  284. }
  286. // Add the new node at the end of queue and change rear
  287. temp->next = (*qq)->rear;
  288. (*qq)->rear = temp;
  289. }
  291. struct Backtrack_QNode * Backtrack_load_asm(struct Backtrack_Queue **qq)
  292. {
  293. if ((*qq) == NULL)
  294. return NULL;
  296. // If queue is empty, return NULL.
  297. if ((*qq)->rear == NULL)
  298. return NULL;
  300. // Store previous front and move front one node ahead
  301. struct Backtrack_QNode *temp = (*qq)->rear;
  302. (*qq)->rear = (*qq)->rear->next;
  304. // If front becomes NULL, then change rear also as NULL
  305. if ((*qq)->rear == NULL)
  306. (*qq)->front = NULL;
  307. return temp;
  308. }
  312. #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
  314. // Alphabet size (# of symbols)
  315. #define ALPHABET_SIZE (26)
  317. // Converts key current character into index
  318. // use only 'a' through 'z' and lower case
  319. #define CHAR_TO_INDEX(c) ((int)c - (int)'a')
  320. #define INT_TO_INDEX(c) ((int)c - (int)'0')
  322. // trie node
  323. struct TrieNode
  324. {
  325. struct TrieNode *children[ALPHABET_SIZE];
  326. int * idx;
  327. int count;
  328. bool branch;
  329. // isEndOfWord is true if the node represents
  330. // end of a word
  331. bool isEndOfWord;
  332. struct TrieNode ** next;
  333. int next_count;
  334. };
  336. bool is_branch = true;
  337. bool is_not_branch = false;
  339. // Returns new trie node (initialized to NULLs)
  340. struct TrieNode *getNode(void)
  341. {
  342. struct TrieNode *pNode = NULL;
  344. pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));
  346. if (pNode)
  347. {
  348. int i;
  350. pNode->isEndOfWord = false;
  351. pNode->idx = NULL;
  352. pNode->next = NULL;
  353. pNode->count = 0;
  354. for (i = 0; i < ALPHABET_SIZE; i++)
  355. pNode->children[i] = NULL;
  356. }
  358. return pNode;
  359. }
  361. // If not present, inserts key into trie
  362. // If the key is prefix of trie node, just marks leaf node
  363. void insert(struct TrieNode *root, const char *key, int dest_idx, struct TrieNode *next)
  364. {
  365. int level;
  366. int length = strlen(key);
  367. int index;
  369. struct TrieNode *pCrawl = root;
  370. // pi(dest_idx)
  371. for (level = 0; level < length; level++)
  372. {
  373. // pi(level);
  374. // pc(key[level])
  375. str_new(ch);
  376. str_insert_char(ch, key[level]);
  377. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  378. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  379. str_free(ch)
  380. // pi(index)
  381. // pp(pCrawl->children[index])
  382. if (!pCrawl->children[index]) {
  383. pCrawl->children[index] = getNode();
  384. }
  386. if (level == length-1) {
  387. // pp(pCrawl->children[index])
  388. // pp(pCrawl->children[index]->idx)
  389. pCrawl->children[index]->next_count++;
  390. if (!pCrawl->children[index]->next) {
  391. pCrawl->children[index]->next = malloc(sizeof(int*)*pCrawl->children[index]->next_count);
  392. // pp(pCrawl->children[index]->idx)
  393. }
  394. else {
  395. pCrawl->children[index]->next = realloc(pCrawl->children[index]->next, sizeof(int*)*pCrawl->children[index]->next_count);
  396. }
  397. pCrawl->children[index]->next[pCrawl->children[index]->next_count-1] = next;
  398. if (pCrawl->children[index]->next_count > 1) pCrawl->children[index]->branch = true;
  399. pCrawl->children[index]->count++;
  400. if (!pCrawl->children[index]->idx) {
  401. pCrawl->children[index]->idx = malloc(sizeof(int*)*pCrawl->children[index]->count);
  402. // pp(pCrawl->children[index]->idx)
  403. }
  404. else {
  405. pCrawl->children[index]->idx = realloc(pCrawl->children[index]->idx, sizeof(int*)*pCrawl->children[index]->count);
  406. }
  407. pCrawl->children[index]->idx[pCrawl->children[index]->count-1] = dest_idx;
  408. // pi(pCrawl->children[index]->idx[pCrawl->children[index]->count-1])
  409. }
  411. pCrawl = pCrawl->children[index];
  412. }
  414. // mark last node as leaf
  415. pCrawl->isEndOfWord = true;
  416. }
  418. // Returns true if key presents in trie, else false
  419. bool search(struct TrieNode **root, const char *key, int idx, bool * branches, int branch_index)
  420. {
  421. int level;
  422. int length = strlen(key);
  423. int index;
  424. struct TrieNode *pCrawl = *root;
  425. // pi(idx);
  426. for (level = 0; level < length; level++)
  427. {
  428. str_new(ch);
  429. str_insert_char(ch, key[level]);
  430. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  431. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  432. str_free(ch)
  433. pi(branch_index)
  434. pi(index)
  435. pi(level)
  436. pc(key[level])
  437. pp(pCrawl)
  438. pp(pCrawl->children)
  439. pp(pCrawl->children[index])
  440. if (!pCrawl->children[index]) {
  441. index = CHAR_TO_INDEX('x');
  442. if (!pCrawl->children[index]) {
  443. puts("not found");
  444. return false;
  445. }
  446. }
  448. pCrawl = pCrawl->children[index];
  449. pi(pCrawl->next_count);
  450. if (branch_index > pCrawl->next_count-1) {
  451. puts("error, branch index is greater than branch count");
  452. abort();
  453. }
  454. pp(pCrawl->next);
  455. pb(pCrawl->branch);
  456. *branches = pCrawl->branch;
  457. if (pCrawl->next) {
  458. pp(pCrawl->next[branch_index]);
  459. if (pCrawl->next[branch_index]) {
  460. puts("modifying root");
  461. *root = pCrawl->next[branch_index];
  462. }
  463. }
  464. }
  466. // pi(pCrawl->count)
  467. bool final_match = false;
  468. for (int i = 0; i < pCrawl->count; i++) {
  469. // pi(pCrawl->idx[i])
  470. if (pCrawl->idx[i] == idx) final_match = true;
  471. }
  472. // pb(final_match)
  473. pb(pCrawl->branch);
  474. return (pCrawl != NULL && pCrawl->isEndOfWord && final_match);
  475. }
  477. // Returns true if key presents in trie, else false
  478. bool search_segmented(struct TrieNode *root, struct TrieNode *segments, const char *key)
  479. {
  480. int level;
  481. int length = strlen(key);
  482. int index;
  483. int branch_index = 0;
  484. struct TrieNode *pCrawl = root;
  486. str_new(segment);
  487. int idx = 0;
  488. int undo = 0;
  489. bool next_reload = false;
  491. struct Backtrack_Queue * Backtrack_queue = NULL;
  493. for (level = 0; level < length; level++)
  494. {
  495. if (next_reload == true) {
  496. puts("loading last backtrack reference");
  497. struct Backtrack_QNode * Backtrack_node = NULL; \
  498. Backtrack_node = Backtrack_load_asm(&Backtrack_queue);
  499. if (Backtrack_node) {
  500. pp(pCrawl)
  501. pp(segments)
  502. pi(level)
  503. pi(index)
  504. pi(idx)
  505. ps(key)
  506. pp(Backtrack_node->pCrawl)
  507. pp(Backtrack_node->segments)
  508. pi(Backtrack_node->level)
  509. pi(Backtrack_node->index)
  510. pi(Backtrack_node->idx)
  511. ps(Backtrack_node->key)
  512. for (int i = 0; i < undo; i++) {
  513. str_undo_(segment);
  514. }
  515. undo = 0;
  516. pCrawl = Backtrack_node->pCrawl;
  517. segments = Backtrack_node->segments;
  518. level = Backtrack_node->level;
  519. index = Backtrack_node->index;
  520. idx = Backtrack_node->idx;
  521. key = Backtrack_node->key;
  522. branch_index++;
  523. }
  524. }
  525. str_new(ch);
  526. str_insert_char(ch, key[level]);
  527. if (ch.type & STR_TYPE_DIGIT) index = INT_TO_INDEX(key[level]);
  528. else if (ch.type & STR_TYPE_ALPHABETIC) index = CHAR_TO_INDEX(key[level]);
  529. str_free(ch)
  531. str_insert_char(segment, key[level]);
  533. ps(segment.string);
  534. // pp(segments)
  535. bool branches = false;
  536. pi(branch_index);
  537. struct TrieNode *segments_prev = segments, *segments_curr = segments;
  538. pp(segments_curr)
  539. pp(segments_prev)
  540. bool result1 = search(&segments, segment.string, idx, &branches, branch_index);
  541. segments_curr = segments;
  542. pp(segments_curr)
  543. pp(segments_prev)
  544. pb(branches)
  545. if (branches) {
  546. // store a backtrack reference to this branch
  547. puts("creating backtrack reference");
  548. pp(pCrawl)
  549. pp(segments_curr)
  550. pp(segments_prev)
  551. pi(level)
  552. pi(index)
  553. pi(idx)
  554. ps(key)
  555. Backtrack_store_asm(&Backtrack_queue, pCrawl, segments_prev, level, index, idx, key);
  556. puts("successfull");
  557. }
  558. // pp(segments)
  559. pi(idx)
  560. pb(result1);
  561. undo++;
  562. next_reload = false;
  563. if (result1) {
  564. str_reset(segment);
  565. idx++;
  566. undo = 0;
  567. branch_index = 0;
  568. }
  569. else {
  570. next_reload = true;
  571. continue;
  572. }
  573. // sleep(5);
  574. pi(idx)
  576. if (!pCrawl->children[index]) {
  577. index = CHAR_TO_INDEX('x');
  578. if (!pCrawl->children[index]) return false;
  579. }
  581. pCrawl = pCrawl->children[index];
  582. }
  583. str_free(segment);
  584. return (pCrawl != NULL && pCrawl->isEndOfWord);
  585. }
  587. #define isp(root, segments, c) printf("%s --- %s\n", c, output[search_segmented(root, segments, c)] )
  589. // Driver
  590. int main()
  591. {
  592. char output[][32] = {"Not present in trie", "Present in trie"};
  594. /*
  595. // Construct trie
  596. insert(segments, "0011", 0, segments1);
  597. pp(segments->next)
  598. insert(segments1, "001", 1, NULL);
  599. insert(segments1, "0", 2, NULL);
  600. insert(segments1, "0", 3, NULL);
  601. insert(root, "001100100", 0, NULL);
  603. // Search for different keys
  604. isp(root, segments, "001100100");
  605. */
  607. // Construct trie
  609. /* shall aim to be equivilant to this
  611. rule_1 ::= "1" "0";
  612. rule_2 ::= "0" "1";
  613. rule_3 ::= "0" "0";
  615. */
  616. // rule 1
  618. // when adding a new rule indexing resets to 0
  620. struct TrieNode *root = getNode();
  621. struct TrieNode *sub_root = getNode();
  622. struct TrieNode *rule_1 = getNode();
  623. struct TrieNode *rule_2 = getNode();
  624. struct TrieNode *rule_3 = getNode();
  625. struct TrieNode *rule_4 = getNode();
  626. struct TrieNode *rule_5 = getNode();
  627. struct TrieNode *rule_6 = getNode();
  628. struct TrieNode *rule_7 = getNode();
  629. struct TrieNode *rule_8 = getNode();
  631. insert(root, "12356", 0, NULL);
  632. insert(sub_root, "1", 0, rule_1);
  633. insert(rule_1, "2", 1, rule_2);
  634. insert(rule_2, "3", 2, rule_3);
  635. insert(rule_3, "5", 3, rule_4);
  636. insert(rule_4, "6", 4, NULL);
  638. insert(root, "12456", 0, NULL);
  639. insert(sub_root, "1", 0, rule_5);
  640. insert(rule_5, "2", 1, rule_6);
  641. insert(rule_6, "4", 2, rule_7);
  642. insert(rule_7, "5", 3, rule_8);
  643. insert(rule_8, "6", 4, NULL);
  645. // Search for different keys
  646. // isp(root, sub_root, "12356");
  647. isp(root, sub_root, "12456");
  648. // isp(root, sub_root, "12356");
  649. return 0;
  650. }
  652. /*
  654. adding rule 1: segments [0, 1, 0] root [010]
  655. adding rule 2: segments [0, 1, 1] root [011]
  656. segment.string = 0
  657. result = true
  658. segment.string = 1
  659. result = true
  660. segment.string = 0
  661. result = false
  662. 010 --- Present in trie
  663. segment.string = 0
  664. result = true
  665. segment.string = 1
  666. result = true
  667. segment.string = 1
  668. result = true
  669. 011 --- Present in trie
  671. */
  672.  
Powered by spacepaste. Paste removal.