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
Comments
thanks for properly formatting code, and including enough info to reproduce.

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

#include<stdio.h>
#include<stdlib.h>
#include "pat.h"


static NCS_PATRICIA_NODE *search(NCS_PATRICIA_TREE *const 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 *const 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 = 
   pTree->root_node.right = &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 *const pTree,
                                  NCS_PATRICIA_NODE *const 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!. 
   }
   else	 
   {	
   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 ncs_patricia_tree_del(NCS_PATRICIA_TREE *const pTree,
                                  NCS_PATRICIA_NODE *const pNode)
{
   NCS_PATRICIA_NODE *pNextNode;
   NCS_PATRICIA_NODE **pLegDownToNode;
   NCS_PATRICIA_NODE *pDelNode;
   NCS_PATRICIA_NODE **pPrevLeg;
   NCS_PATRICIA_NODE **pNextLeg;
   int UpWentRight;

   UpWentRight = 0;

   pNextNode = &pTree->root_node;
   pLegDownToNode = &pNextNode->left;

   while ((pDelNode = *pLegDownToNode) != pNode)
   {
      if (pDelNode->bit <= pNextNode->bit)
      {
      return 0;  /* Key not found. */
      }

      pNextNode = pDelNode;
      pLegDownToNode = ((m_GET_BIT(pNode->key_info, pNextNode->bit) != 0) ?
                        &pNextNode->right : &pNextNode->left);

   }


   pPrevLeg = pLegDownToNode;
   pNextNode = pNode;

   while (1)
   {
      UpWentRight = (m_GET_BIT(pNode->key_info, pNextNode->bit) != 0);
      pNextLeg = ((UpWentRight) ? &pNextNode->right : &pNextNode->left);
      pDelNode = *pNextLeg;

      if (pDelNode == pNode)
         break;

      else if(pDelNode->bit <= pNextNode->bit)
      {
         return 0; /* panic??? */
      }

      /* loop around again. */
      pNextNode = pDelNode;
      pPrevLeg = pNextLeg;
   }

   pNextNode->bit = pNode->bit;  /* it gets the 'bit' value of the evacuee. */
   *pLegDownToNode = pNextNode;

   *pPrevLeg = ((UpWentRight) ? pNextNode->left : pNextNode->right); 
   pNextNode->right = pNode->right;
   pNextNode->left = pNode->left;

   pTree->n_nodes--;

   return 1;
}

int main()
{
	NCS_PATRICIA_TREE * pTree;
	NCS_PATRICIA_PARAMS * pParam;
	NCS_PATRICIA_NODE * pNode,*pNode1;
	
	int key_size;
	int *key_info;
	int pTree1,add,c,del,b;
	
	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.DELETE 4.COUNT 5.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:

                pNode1=(NCS_PATRICIA_NODE *)malloc(sizeof(NCS_PATRICIA_NODE));
                int a=0; 	
		printf("Enter the key to be inserted\n");
                scanf("%d",&a);
                pNode1->key_info = &a;
		printf("%d",*(pNode1->key_info));
        	//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:

		printf("Enter the key to be deleted\n");
		scanf("%d",&b);
    		pNode1->key_info=&b;
		del=ncs_patricia_tree_del(pTree,pNode1);
		if(del==0)
		{
			printf("Element Not Found\n");
		}
		else
		{
			printf("Element Deleted\n");
		}
		break;
	case 4:
		printf("The No: of Nodes in Tree is: %d\n",pTree->n_nodes);
		break;

	case 5:
		exit(0);
	}
	}
	return 0;
}

i've added one more function to delete in above file and so its prototype is also defined in ncspatricia.h file.

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.


.

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.

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.

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


.

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/4525eace/sharing.html

thanks

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...

This article has been dead for over six months. Start a new discussion instead.