943,772 Members | Top Members by Rank

Ad:
  • C Discussion Thread
  • Unsolved
  • Views: 1190
  • C RSS
Apr 7th, 2009
1

segmentation stack problem in patricia trie

Expand Post »
hi guys im trying to code patricia trie in c using gcc and when i debuged the program im gettin segmentation stack problem in search function of it.im not sure why it is showing and i've included pat.c,pat.h and ncspatricia.h files.
i also want to know what is the difference if we assign a variable as int and as unsigned int8 or 32.
the error was in the following line:
Program received signal SIGSEGV, Segmentation fault.
0x080484d4 in search (pTree=0x804a008, key=0x64) at pat.c:26
26 }while (pNode->bit > pPrevNode->bit);

im not able to access the pNode->bit after checking above condition but no problem before checking this condition,as it shows the following error after checking the condition:
(gdb) p pNode->bit
Cannot access memory at address 0x0
before:
(gdb) p pNode->bit
$3 = -1
im also not able to print the below value (line 168 of main())and im not sure about why is it so?
//printf("%d",pNode1->key_info);

pat.c
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include "pat.h"
  4.  
  5.  
  6. static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *pTree,int *key)
  7. {
  8. NCS_PATRICIA_NODE *pNode;
  9. NCS_PATRICIA_NODE *pPrevNode;
  10.  
  11. pNode = (NCS_PATRICIA_NODE *)&pTree->root_node;
  12.  
  13. do
  14. {
  15. pPrevNode = pNode;
  16.  
  17. if (m_GET_BIT(key, pNode->bit) == 0)
  18. {
  19. pNode = pNode->left;
  20. }
  21. else
  22. {
  23. pNode = pNode->right;
  24.  
  25. }
  26. }while (pNode->bit > pPrevNode->bit);
  27.  
  28. return pNode;
  29. }
  30.  
  31. int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree,const NCS_PATRICIA_PARAMS *const pParams)
  32. {
  33. if (pParams == NULL)
  34. return 0;
  35.  
  36. if ( (pParams->key_size < 1)
  37. ||(pParams->key_size > NCS_PATRICIA_MAX_KEY_SIZE)
  38. )
  39. {
  40. return 0;
  41. }
  42.  
  43. pTree->params = *pParams;
  44.  
  45. /* Initialize the root node, which is actually part of the tree structure. */
  46. pTree->root_node.key_info =0;
  47. pTree->root_node.bit = -1;
  48. pTree->root_node.left =NULL;
  49. pTree->root_node.right =NULL;
  50. &pTree->root_node;
  51. if ((pTree->root_node.key_info= malloc(sizeof(pTree->params.key_size)))== NULL)
  52.  
  53. {
  54. return 0;
  55. }
  56.  
  57. memset(pTree->root_node.key_info, '\0',pTree->params.key_size);
  58. pTree->n_nodes = 0;
  59.  
  60. return 1;
  61. }
  62.  
  63.  
  64. int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree,
  65. NCS_PATRICIA_NODE *pNode)
  66. {
  67. NCS_PATRICIA_NODE *pSrch;
  68. NCS_PATRICIA_NODE *pTmpNode;
  69. NCS_PATRICIA_NODE *pPrevNode;
  70. int bit;
  71.  
  72. pTmpNode = search(pTree, pNode->key_info);
  73. if (m_KEY_CMP(pTree, pNode->key_info, pTmpNode->key_info) == 0)
  74. {
  75. return 0; /* duplicate!. */
  76. }
  77.  
  78. bit = 0;
  79.  
  80. while (m_GET_BIT(pNode->key_info, bit) ==
  81. ((pTmpNode->bit < 0) ? 0 : m_GET_BIT(pTmpNode->key_info, bit)))
  82. {
  83. bit++;
  84. }
  85.  
  86. pSrch = &pTree->root_node;
  87.  
  88. do
  89. {
  90. pPrevNode = pSrch;
  91. if (m_GET_BIT(pNode->key_info, pSrch->bit) == 0)
  92. pSrch = pSrch->left;
  93. else
  94. pSrch = pSrch->right;
  95. } while ((pSrch->bit < bit) && (pSrch->bit > pPrevNode->bit));
  96.  
  97. pNode->bit = bit;
  98.  
  99. if (m_GET_BIT(pNode->key_info, bit) == 0)
  100. {
  101. pNode->left = pNode;
  102. pNode->right = pSrch;
  103. }
  104. else
  105. {
  106. pNode->left = pSrch;
  107. pNode->right = pNode;
  108. }
  109.  
  110. if (m_GET_BIT(pNode->key_info, pPrevNode->bit) == 0)
  111. {
  112. pPrevNode->left = pNode;
  113. }
  114. else
  115. {
  116. pPrevNode->right = pNode;
  117. }
  118.  
  119. pTree->n_nodes++;
  120. return 1;
  121. }
  122.  
  123. int main()
  124. {
  125. NCS_PATRICIA_TREE * pTree;//*pTree2;
  126. NCS_PATRICIA_PARAMS * pParam;//*pParam1;
  127. NCS_PATRICIA_NODE * pNode,*pNode1;
  128.  
  129. int key_size;
  130. int *key_info;
  131. int pTree1,add,c;
  132.  
  133. pTree=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE));
  134. pParam=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS));
  135. pNode=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
  136.  
  137. while(1)
  138. {
  139. printf("1.INIT 2.ADD 3.EXIT\n");
  140. printf("Enter the option:\n");
  141. scanf("%d",&c);
  142. switch(c)
  143. {
  144. case 1:
  145.  
  146. printf("Enter the size of the key\n");
  147. scanf("%d",&pParam->key_size);
  148. pTree1=ncs_patricia_tree_init(pTree,pParam);
  149. if(pTree1==0)
  150. {
  151. printf("FAILURE\n");
  152. }
  153. else
  154. {
  155. printf("SUCCESS\n");
  156. }
  157. break;
  158. case 2:
  159. //NCS_PATRICIA_TREE *pTree2;
  160. //NCS_PATRICIA_NODE *pNode1;
  161.  
  162. //pTree2=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE));
  163. //pParam1=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS));
  164. pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
  165.  
  166. printf("Enter the key to be inserted\n");
  167. scanf("%d",&pNode1->key_info);
  168. //printf("%d",pNode1->key_info);
  169. add=ncs_patricia_tree_add(pTree,pNode1);
  170. if(add=0)
  171. {
  172. printf("Element Not Inserted\n");
  173. }
  174. else
  175. {
  176. printf("Element Inserted\n");
  177. }
  178. break;
  179. case 3:
  180. exit(0);
  181. }
  182. }
  183. return 0;
  184. }
pat.h
  1. #ifndef _PATRICIA_H_
  2. #define _PATRICIA_H_
  3.  
  4. #include "ncspatricia.h"
  5.  
  6. #define m_KEY_CMP(t, k1, k2) memcmp(k1, k2, (size_t)(t)->params.key_size)
  7. #define m_GET_BIT(key, bit) ((bit < 0) ? 0 : ((int)((*((key) + (bit >> 3))) >> (7 - (bit & 0x07))) & 0x01))
  8.  
  9. #endif
  1. #ifndef _NCSPATRICIA_H_
  2. #define _NCSPATRICIA_H_
  3.  
  4. #ifdef __cplusplus
  5. extern "C" {
  6. #endif
  7.  
  8. typedef struct ncs_patricia_params
  9. {
  10. int key_size; /* 1..NCS_PATRICIA_MAX_KEY_SIZE - in OCTETS */
  11. int info_size; /* NOT USED! Present for backward-compatibility only! */
  12. int actual_key_size; /* NOT USED! Present for backward-compatibility only! */
  13. int node_size; /* NOT USED! Present for backward compatibitity only! */
  14. } NCS_PATRICIA_PARAMS;
  15.  
  16. #define NCS_PATRICIA_MAX_KEY_SIZE 600 /* # octets */
  17.  
  18.  
  19. typedef struct ncs_patricia_node
  20. {
  21. int bit; /* must be signed type (bits start at -1) */
  22. struct ncs_patricia_node *left;
  23. struct ncs_patricia_node *right;
  24. int *key_info;
  25. } NCS_PATRICIA_NODE;
  26.  
  27. #define NCS_PATRICIA_NODE_NULL ((NCS_PATRICIA_NODE *)0)
  28.  
  29. //typedef uns8 NCS_PATRICIA_LEXICAL_STACK; /* ancient history... */
  30.  
  31. typedef struct ncs_patricia_tree
  32. {
  33. NCS_PATRICIA_NODE root_node; /* A tree always has a root node. */
  34. NCS_PATRICIA_PARAMS params;
  35. int n_nodes;
  36. } NCS_PATRICIA_TREE;
  37.  
  38. int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree,
  39. const NCS_PATRICIA_PARAMS *const pParams);
  40.  
  41.  
  42. int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree,
  43. NCS_PATRICIA_NODE *pNode);
  44.  
  45. #ifdef __cplusplus
  46. }
  47. #endif
  48.  
  49. #endif
Last edited by karthik.c; Apr 7th, 2009 at 9:23 am.
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009
Apr 17th, 2009
0

Re: segmentation stack problem in patricia trie

hi again,i've modified the above coding for pat.c and now im not getting any segmentation stack problem,but im stuck with logical error i.e im not able to insert /delete properly .it would be great if someone could help me out.thanks
pat.c
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include "pat.h"
  4.  
  5.  
  6. static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *const pTree,int* key)
  7. {
  8. NCS_PATRICIA_NODE *pNode;
  9. NCS_PATRICIA_NODE *pPrevNode;
  10.  
  11. pNode = (NCS_PATRICIA_NODE *)&pTree->root_node;
  12.  
  13. do
  14. {
  15. pPrevNode = pNode;
  16.  
  17. if (m_GET_BIT(key, pNode->bit) == 0)
  18. {
  19. pNode = pNode->left;
  20. }
  21. else
  22. {
  23. pNode = pNode->right;
  24.  
  25. }
  26. }while (pNode->bit > pPrevNode->bit);
  27.  
  28. return pNode;
  29. }
  30.  
  31. int ncs_patricia_tree_init(NCS_PATRICIA_TREE *const pTree,const NCS_PATRICIA_PARAMS *const pParams)
  32. {
  33. if (pParams == NULL)
  34. return 0;
  35.  
  36. if ( (pParams->key_size < 1)
  37. ||(pParams->key_size > NCS_PATRICIA_MAX_KEY_SIZE)
  38. )
  39. {
  40. return 0;
  41. }
  42.  
  43. pTree->params = *pParams;
  44.  
  45. /* Initialize the root node, which is actually part of the tree structure. */
  46. pTree->root_node.key_info =0;
  47. pTree->root_node.bit = -1;
  48. pTree->root_node.left =
  49. pTree->root_node.right = &pTree->root_node;
  50. if ((pTree->root_node.key_info= malloc(sizeof(pTree->params.key_size)))== NULL)
  51.  
  52. {
  53. return 0;
  54. }
  55.  
  56. memset(pTree->root_node.key_info, '\0',pTree->params.key_size);
  57. pTree->n_nodes = 0;
  58.  
  59. return 1;
  60. }
  61.  
  62.  
  63. int ncs_patricia_tree_add(NCS_PATRICIA_TREE *const pTree,
  64. NCS_PATRICIA_NODE *const pNode)
  65. {
  66. NCS_PATRICIA_NODE *pSrch;
  67. NCS_PATRICIA_NODE *pTmpNode;
  68. NCS_PATRICIA_NODE *pPrevNode;
  69. int bit;
  70.  
  71. pTmpNode = search(pTree, pNode->key_info);
  72. if (m_KEY_CMP(pTree, pNode->key_info, pTmpNode->key_info) == 0)
  73. {
  74. return 0; //duplicate!.
  75. }
  76. else
  77. {
  78. bit = 0;
  79.  
  80. while (m_GET_BIT(pNode->key_info, bit) ==
  81. ((pTmpNode->bit < 0) ? 0 : m_GET_BIT(pTmpNode->key_info, bit)))
  82. {
  83. bit++;
  84. }
  85.  
  86. pSrch = &pTree->root_node;
  87.  
  88. do
  89. {
  90. pPrevNode = pSrch;
  91. if (m_GET_BIT(pNode->key_info, pSrch->bit) == 0)
  92. pSrch = pSrch->left;
  93. else
  94. pSrch = pSrch->right;
  95. } while ((pSrch->bit < bit) && (pSrch->bit > pPrevNode->bit));
  96.  
  97. pNode->bit = bit;
  98.  
  99. if (m_GET_BIT(pNode->key_info, bit) == 0)
  100. {
  101. pNode->left = pNode;
  102. pNode->right = pSrch;
  103. }
  104. else
  105. {
  106. pNode->left = pSrch;
  107. pNode->right = pNode;
  108. }
  109.  
  110. if (m_GET_BIT(pNode->key_info, pPrevNode->bit) == 0)
  111. {
  112. pPrevNode->left = pNode;
  113. }
  114. else
  115. {
  116. pPrevNode->right = pNode;
  117. }
  118.  
  119. pTree->n_nodes++;
  120. return 1;
  121. }
  122. }
  123.  
  124. int ncs_patricia_tree_del(NCS_PATRICIA_TREE *const pTree,
  125. NCS_PATRICIA_NODE *const pNode)
  126. {
  127. NCS_PATRICIA_NODE *pNextNode;
  128. NCS_PATRICIA_NODE **pLegDownToNode;
  129. NCS_PATRICIA_NODE *pDelNode;
  130. NCS_PATRICIA_NODE **pPrevLeg;
  131. NCS_PATRICIA_NODE **pNextLeg;
  132. int UpWentRight;
  133.  
  134. UpWentRight = 0;
  135.  
  136. pNextNode = &pTree->root_node;
  137. pLegDownToNode = &pNextNode->left;
  138.  
  139. while ((pDelNode = *pLegDownToNode) != pNode)
  140. {
  141. if (pDelNode->bit <= pNextNode->bit)
  142. {
  143. return 0; /* Key not found. */
  144. }
  145.  
  146. pNextNode = pDelNode;
  147. pLegDownToNode = ((m_GET_BIT(pNode->key_info, pNextNode->bit) != 0) ?
  148. &pNextNode->right : &pNextNode->left);
  149.  
  150. }
  151.  
  152.  
  153. pPrevLeg = pLegDownToNode;
  154. pNextNode = pNode;
  155.  
  156. while (1)
  157. {
  158. UpWentRight = (m_GET_BIT(pNode->key_info, pNextNode->bit) != 0);
  159. pNextLeg = ((UpWentRight) ? &pNextNode->right : &pNextNode->left);
  160. pDelNode = *pNextLeg;
  161.  
  162. if (pDelNode == pNode)
  163. break;
  164.  
  165. else if(pDelNode->bit <= pNextNode->bit)
  166. {
  167. return 0; /* panic??? */
  168. }
  169.  
  170. /* loop around again. */
  171. pNextNode = pDelNode;
  172. pPrevLeg = pNextLeg;
  173. }
  174.  
  175. pNextNode->bit = pNode->bit; /* it gets the 'bit' value of the evacuee. */
  176. *pLegDownToNode = pNextNode;
  177.  
  178. *pPrevLeg = ((UpWentRight) ? pNextNode->left : pNextNode->right);
  179. pNextNode->right = pNode->right;
  180. pNextNode->left = pNode->left;
  181.  
  182. pTree->n_nodes--;
  183.  
  184. return 1;
  185. }
  186.  
  187. int main()
  188. {
  189. NCS_PATRICIA_TREE * pTree;
  190. NCS_PATRICIA_PARAMS * pParam;
  191. NCS_PATRICIA_NODE * pNode,*pNode1;
  192.  
  193. int key_size;
  194. int *key_info;
  195. int pTree1,add,c,del,b;
  196.  
  197. pTree=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE));
  198. pParam=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS));
  199. //pNode=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
  200.  
  201. while(1)
  202. {
  203. printf("1.INIT 2.ADD 3.DELETE 4.COUNT 5.EXIT\n");
  204. printf("Enter the option:\n");
  205. scanf("%d",&c);
  206. switch(c)
  207. {
  208. case 1:
  209.  
  210. printf("Enter the size of the key\n");
  211. scanf("%d",&pParam->key_size);
  212. pTree1=ncs_patricia_tree_init(pTree,pParam);
  213. if(pTree1==0)
  214. {
  215. printf("FAILURE\n");
  216. }
  217. else
  218. {
  219. printf("SUCCESS\n");
  220. }
  221. break;
  222. case 2:
  223.  
  224. pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
  225. int a=0;
  226. printf("Enter the key to be inserted\n");
  227. scanf("%d",&a);
  228. pNode1->key_info = &a;
  229. printf("%d",*(pNode1->key_info));
  230. //scanf("%d",&pNode1->key_info);
  231. //printf("%d",pNode1->key_info);
  232. add=ncs_patricia_tree_add(pTree,pNode1);
  233. if(add==0)
  234. {
  235. printf("Element Not Inserted\n");
  236. }
  237. else
  238. {
  239. printf("Element Inserted\n");
  240. }
  241. break;
  242. case 3:
  243.  
  244. printf("Enter the key to be deleted\n");
  245. scanf("%d",&b);
  246. pNode1->key_info=&b;
  247. del=ncs_patricia_tree_del(pTree,pNode1);
  248. if(del==0)
  249. {
  250. printf("Element Not Found\n");
  251. }
  252. else
  253. {
  254. printf("Element Deleted\n");
  255. }
  256. break;
  257. case 4:
  258. printf("The No: of Nodes in Tree is: %d\n",pTree->n_nodes);
  259. break;
  260.  
  261. case 5:
  262. exit(0);
  263. }
  264. }
  265. return 0;
  266. }
i've added one more function to delete in above file and so its prototype is also defined in ncspatricia.h file.
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009
Apr 17th, 2009
0

Re: segmentation stack problem in patricia trie

when you build your program and it complains: "warning: implicit declaration of function `memset'" ... you have to pay attention to that.

memset() and memcmp() require that you #include <string.h>

theres could be other issues, but start with that and lets see what happens.


.
Last edited by jephthah; Apr 17th, 2009 at 2:10 pm.
Reputation Points: 2143
Solved Threads: 178
Posting Maven
jephthah is offline Offline
2,567 posts
since Feb 2008
Apr 18th, 2009
0

Re: segmentation stack problem in patricia trie

Click to Expand / Collapse  Quote originally posted by jephthah ...
when you build your program and it complains: "warning: implicit declaration of function `memset'" ... you have to pay attention to that.

memset() and memcmp() require that you #include <string.h>

theres could be other issues, but start with that and lets see what happens.


.
actually i didnt get the warning what you are saying and im actually passing two int * argument(and so im not passing any strings here) in memcmp() function instead of passing void *, which can relate to any datatype. so will that be a problem?
i did tried your suggestion by including string.h,but still the problem remains while inserting/deleting.
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009
Apr 18th, 2009
0

Re: segmentation stack problem in patricia trie

im able to compile and run the above program without any warning/error using the same above pat.c file.problem arises when i try to insert/delete i.e sometimes it is not acceptin more than 2/more values and sometimes it is showing the key not present in tree as deleted.when i debugged using gdb,it skipped some of the lines to print those wrong output.im not getting why it is skipping those lines.
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009
Apr 20th, 2009
0

Re: segmentation stack problem in patricia trie

i'm sorry, i just tried to look at this again and you've got memory allocation faults and general protection faults everywhere. i think youre trying to reallocate the same memory in different functions.

the whole thing is making my head swim... I have to admit I'm not familiar with this trie algorithm, and so I'm afraid I don't have time to devote to what would -- at least for me -- wind up being a research project.

So I'm gonna punt. maybe one of our CSC majors can figure this out


.
Last edited by jephthah; Apr 20th, 2009 at 11:47 am.
Reputation Points: 2143
Solved Threads: 178
Posting Maven
jephthah is offline Offline
2,567 posts
since Feb 2008
Apr 21st, 2009
0

Re: segmentation stack problem in patricia trie

thanks jephthah for taking your time to read my code . i've enclosed a link to upload a pdf file which explains the concept of patricia trie and i started doing code based on this concept.because of some problem i was not able to attach that pdf here,so it would be great if anyone can go through it and help me where my logic is going wrong .patricia trie is explained in page no-573 with few examples for insertion and deletion.

http://www.4shared.com/dir/11076492/...e/sharing.html

thanks
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009
May 2nd, 2009
0

Re: segmentation stack problem in patricia trie

hi guys,ive changed the above coding to make it work with no problem while inserting ,deleting,searching which i said before ,but now im facing one new problem of segmentation fault while opting for exit operation and the error was like this:

Program received signal SIGSEGV, Segmentation fault.
0x092330a8 in ?? ()
which gives me no clue as where it is occuring or what triggers this segmentation fault.
this error is not frequent every time,as it occurs mostly after deleting some nodes in trie or emptying the trie.
any help would greatly be appreciated thanx...
Reputation Points: 16
Solved Threads: 0
Light Poster
karthik.c is offline Offline
48 posts
since Feb 2009

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C Forum Timeline: memcmp implementation - any logical errors with this one
Next Thread in C Forum Timeline: How to use a variable from fgets() in fopen()...?





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC