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
#include<stdio.h>
#include<stdlib.h>
#include "pat.h"
static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *pTree,int *key)
{
NCS_PATRICIA_NODE *pNode;
NCS_PATRICIA_NODE *pPrevNode;
pNode = (NCS_PATRICIA_NODE *)&pTree->root_node;
do
{
pPrevNode = pNode;
if (m_GET_BIT(key, pNode->bit) == 0)
{
pNode = pNode->left;
}
else
{
pNode = pNode->right;
}
}while (pNode->bit > pPrevNode->bit);
return pNode;
}
int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree,const NCS_PATRICIA_PARAMS *const pParams)
{
if (pParams == NULL)
return 0;
if ( (pParams->key_size < 1)
||(pParams->key_size > NCS_PATRICIA_MAX_KEY_SIZE)
)
{
return 0;
}
pTree->params = *pParams;
/* Initialize the root node, which is actually part of the tree structure. */
pTree->root_node.key_info =0;
pTree->root_node.bit = -1;
pTree->root_node.left =NULL;
pTree->root_node.right =NULL;
&pTree->root_node;
if ((pTree->root_node.key_info= malloc(sizeof(pTree->params.key_size)))== NULL)
{
return 0;
}
memset(pTree->root_node.key_info, '\0',pTree->params.key_size);
pTree->n_nodes = 0;
return 1;
}
int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree,
NCS_PATRICIA_NODE *pNode)
{
NCS_PATRICIA_NODE *pSrch;
NCS_PATRICIA_NODE *pTmpNode;
NCS_PATRICIA_NODE *pPrevNode;
int bit;
pTmpNode = search(pTree, pNode->key_info);
if (m_KEY_CMP(pTree, pNode->key_info, pTmpNode->key_info) == 0)
{
return 0; /* duplicate!. */
}
bit = 0;
while (m_GET_BIT(pNode->key_info, bit) ==
((pTmpNode->bit < 0) ? 0 : m_GET_BIT(pTmpNode->key_info, bit)))
{
bit++;
}
pSrch = &pTree->root_node;
do
{
pPrevNode = pSrch;
if (m_GET_BIT(pNode->key_info, pSrch->bit) == 0)
pSrch = pSrch->left;
else
pSrch = pSrch->right;
} while ((pSrch->bit < bit) && (pSrch->bit > pPrevNode->bit));
pNode->bit = bit;
if (m_GET_BIT(pNode->key_info, bit) == 0)
{
pNode->left = pNode;
pNode->right = pSrch;
}
else
{
pNode->left = pSrch;
pNode->right = pNode;
}
if (m_GET_BIT(pNode->key_info, pPrevNode->bit) == 0)
{
pPrevNode->left = pNode;
}
else
{
pPrevNode->right = pNode;
}
pTree->n_nodes++;
return 1;
}
int main()
{
NCS_PATRICIA_TREE * pTree;//*pTree2;
NCS_PATRICIA_PARAMS * pParam;//*pParam1;
NCS_PATRICIA_NODE * pNode,*pNode1;
int key_size;
int *key_info;
int pTree1,add,c;
pTree=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE));
pParam=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS));
pNode=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
while(1)
{
printf("1.INIT 2.ADD 3.EXIT\n");
printf("Enter the option:\n");
scanf("%d",&c);
switch(c)
{
case 1:
printf("Enter the size of the key\n");
scanf("%d",&pParam->key_size);
pTree1=ncs_patricia_tree_init(pTree,pParam);
if(pTree1==0)
{
printf("FAILURE\n");
}
else
{
printf("SUCCESS\n");
}
break;
case 2:
//NCS_PATRICIA_TREE *pTree2;
//NCS_PATRICIA_NODE *pNode1;
//pTree2=(NCS_PATRICIA_TREE *)malloc(sizeof(NCS_PATRICIA_TREE));
//pParam1=(NCS_PATRICIA_PARAMS *)malloc(sizeof(NCS_PATRICIA_PARAMS));
pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
printf("Enter the key to be inserted\n");
scanf("%d",&pNode1->key_info);
//printf("%d",pNode1->key_info);
add=ncs_patricia_tree_add(pTree,pNode1);
if(add=0)
{
printf("Element Not Inserted\n");
}
else
{
printf("Element Inserted\n");
}
break;
case 3:
exit(0);
}
}
return 0;
}pat.h
#ifndef _PATRICIA_H_
#define _PATRICIA_H_
#include "ncspatricia.h"
#define m_KEY_CMP(t, k1, k2) memcmp(k1, k2, (size_t)(t)->params.key_size)
#define m_GET_BIT(key, bit) ((bit < 0) ? 0 : ((int)((*((key) + (bit >> 3))) >> (7 - (bit & 0x07))) & 0x01))
#endif#ifndef _NCSPATRICIA_H_
#define _NCSPATRICIA_H_
#ifdef __cplusplus
extern "C" {
#endif
typedef struct ncs_patricia_params
{
int key_size; /* 1..NCS_PATRICIA_MAX_KEY_SIZE - in OCTETS */
int info_size; /* NOT USED! Present for backward-compatibility only! */
int actual_key_size; /* NOT USED! Present for backward-compatibility only! */
int node_size; /* NOT USED! Present for backward compatibitity only! */
} NCS_PATRICIA_PARAMS;
#define NCS_PATRICIA_MAX_KEY_SIZE 600 /* # octets */
typedef struct ncs_patricia_node
{
int bit; /* must be signed type (bits start at -1) */
struct ncs_patricia_node *left;
struct ncs_patricia_node *right;
int *key_info;
} NCS_PATRICIA_NODE;
#define NCS_PATRICIA_NODE_NULL ((NCS_PATRICIA_NODE *)0)
//typedef uns8 NCS_PATRICIA_LEXICAL_STACK; /* ancient history... */
typedef struct ncs_patricia_tree
{
NCS_PATRICIA_NODE root_node; /* A tree always has a root node. */
NCS_PATRICIA_PARAMS params;
int n_nodes;
} NCS_PATRICIA_TREE;
int ncs_patricia_tree_init(NCS_PATRICIA_TREE *pTree,
const NCS_PATRICIA_PARAMS *const pParams);
int ncs_patricia_tree_add(NCS_PATRICIA_TREE *pTree,
NCS_PATRICIA_NODE *pNode);
#ifdef __cplusplus
}
#endif
#endif