pdtree.c

Go to the documentation of this file.

/**
 * $Id: pdtree.c 4518 2008-07-28 15:39:28Z henningw $
 *
 * Copyright (C) 2005 Voice Sistem SRL (Voice-System.RO)
 *
 * This file is part of Kamailio, a free SIP server.
 *
 * This file is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version
 *
 *
 * This file is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * History:
 * -------
 * 2005-01-25  first tree version (ramona)
 * 2006-01-30 multi domain support added (ramona)
 */

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

#include "../../dprint.h"
#include "../../mem/shm_mem.h"
#include "../../ut.h"

#include "pdtree.h"

//extern str pdt_char_list = {"1234567890*",11};
extern str pdt_char_list;

pdt_tree_t* pdt_init_tree(str* sdomain)
{
   pdt_tree_t *pt = NULL;

   pt = (pdt_tree_t*)shm_malloc(sizeof(pdt_tree_t));
   if(pt==NULL)
   {
      LM_ERR("no more shm memory\n");
      return NULL;
   }
   memset(pt, 0, sizeof(pdt_tree_t));

   pt->sdomain.s = (char*)shm_malloc((1+sdomain->len)*sizeof(char));
   if(pt->sdomain.s==NULL)
   {
      shm_free(pt);
      LM_ERR("no more shm memory\n");
      return NULL;
   }
   memset(pt->sdomain.s, 0,1+sdomain->len );
   memcpy(pt->sdomain.s, sdomain->s, sdomain->len);
   pt->sdomain.len = sdomain->len;
// printf("sdomain:%.*s\n", pt->sdomain.len, pt->sdomain.s);
   
   pt->head = (pdt_node_t*)shm_malloc(PDT_NODE_SIZE*sizeof(pdt_node_t));
   if(pt->head == NULL)
   {
      shm_free(pt->sdomain.s);
      shm_free(pt);
      LM_ERR("no more shm memory\n");
      return NULL;
   }
   memset(pt->head, 0, PDT_NODE_SIZE*sizeof(pdt_node_t));
   
   return pt;
}

int add_to_tree(pdt_tree_t *pt, str *sp, str *sd)
{
   int l;
   pdt_node_t *itn, *itn0;
   
   if(pt==NULL || sp==NULL || sp->s==NULL
         || sd==NULL || sd->s==NULL)
   {
      LM_ERR("bad parameters\n");
      return -1;
   }

   if(sp->len>=PDT_MAX_DEPTH)
   {
      LM_ERR("max prefix len exceeded\n");
      return -1;
   }
   
   l = 0;
   itn0 = pt->head;
   itn = itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].child;

   while(l < sp->len-1)
   {
      if(strpos(pdt_char_list.s,sp->s[l]) < 0)
      {
         LM_ERR("invalid char %d in prefix [%c (0x%x)]\n",
            l, sp->s[l], sp->s[l]);
         return -1;        
      }
      
      if(itn == NULL)
      {
         itn = (pdt_node_t*)shm_malloc(PDT_NODE_SIZE*sizeof(pdt_node_t));
         if(itn == NULL)
         {
            LM_ERR("no more shm mem\n");
            return -1;
         }
         memset(itn, 0, PDT_NODE_SIZE*sizeof(pdt_node_t));
         itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].child = itn;
      }
      l++;  
      itn0 = itn;
      itn = itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].child;
   }

   if(itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s!=NULL)
   {
      LM_ERR("prefix already allocated [%.*s/[%.*s]\n",
         sp->len, sp->s, sd->len, sd->s);
      return -1;
   }

   itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s
         = (char*)shm_malloc((sd->len+1)*sizeof(char));
   if(itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s==NULL)
   {
      LM_ERR("no more shm mem!\n");
      return -1;
   }
   strncpy(itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s,
         sd->s, sd->len);
   itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.len = sd->len;
   itn0[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s[sd->len]
      = '\0';
   
   return 0;
}

pdt_tree_t* pdt_get_tree(pdt_tree_t *pl, str *sdomain)
{
   pdt_tree_t *it;
            
   if(pl==NULL)
      return NULL;

   if( sdomain==NULL || sdomain->s==NULL)
   {
      LM_ERR("bad parameters\n");
      return NULL;
   }

   it = pl;
   /* search the tree for the asked sdomain */
   while(it!=NULL && str_strcmp(&it->sdomain, sdomain)<0)
      it = it->next;

   if(it==NULL || str_strcmp(&it->sdomain, sdomain)>0)
      return NULL;
   
   return it;
}

int pdt_add_to_tree(pdt_tree_t **dpt, str *sdomain, str *code, str *domain)
{
   pdt_tree_t *ndl, *it, *prev;

   if( sdomain==NULL || sdomain->s==NULL
         || code==NULL || code->s==NULL
         || domain==NULL || domain->s==NULL)
   {
      LM_ERR("bad parameters\n");
      return -1;
   }
   
   ndl = NULL;
   
   it = *dpt;
   prev = NULL;
   /* search the it position before which to insert new domain */
   while(it!=NULL && str_strcmp(&it->sdomain, sdomain)<0)
   {  
      prev = it;
      it = it->next;
   }
// printf("sdomain:%.*s\n", sdomain->len, sdomain->s);

   /* add new sdomain*/
   if(it==NULL || str_strcmp(&it->sdomain, sdomain)>0)
   {
      ndl = pdt_init_tree(sdomain);
      if(ndl==NULL)
      {
         LM_ERR("no more shm memory\n");
         return -1; 
      }

      if(add_to_tree(ndl, code, domain)<0)
      {
         LM_ERR("internal error!\n");
         return -1;
      }
      ndl->next = it;
      
      /* new domain must be added as first element */
      if(prev==NULL)
         *dpt = ndl;
      else
         prev->next=ndl;

   }
   else 
      /* add (prefix, code) to already present sdomain */
      if(add_to_tree(it, code, domain)<0)
      {
         LM_ERR("internal error!\n");
         return -1;
      }

   return 0;
}

str* get_domain(pdt_tree_t *pt, str *sp, int *plen)
{
   int l, len;
   pdt_node_t *itn;
   str *domain;

   if(pt==NULL || sp==NULL || sp->s==NULL)
   {
      LM_ERR("bad parameters\n");
      return NULL;
   }
   
   l = len = 0;
   itn = pt->head;
   domain = NULL;

   while(itn!=NULL && l < sp->len && l < PDT_MAX_DEPTH)
   {
      /* check validity */
      if(strpos(pdt_char_list.s,sp->s[l]) < 0)
      {
         LM_ERR("invalid char at %d in [%.*s]\n", l, sp->len, sp->s);
         return NULL;
      }

      if(itn[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain.s!=NULL)
      {
         domain = &itn[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].domain;
         len = l+1;
      }
      
      itn = itn[strpos(pdt_char_list.s,sp->s[l])%PDT_NODE_SIZE].child;
      l++;  
   }
   
   if(plen!=NULL)
      *plen = len;
   
   return domain;
   
}
str* pdt_get_domain(pdt_tree_t *pl, str* sdomain, str *code, int *plen)
{
   pdt_tree_t *it;
   int len;
   str *domain=NULL;

   if(pl==NULL || sdomain==NULL || sdomain->s==NULL || code == NULL
         || code->s == NULL)
   {
      LM_ERR("bad parameters\n");
      return NULL;
   }

   it = pl;
   while(it!=NULL && str_strcmp(&it->sdomain, sdomain)<0)
      it = it->next;
   
   if(it==NULL || str_strcmp(&it->sdomain, sdomain)>0)
      return NULL;
   
   domain = get_domain(it, code, &len);
   if(plen!=NULL)
         *plen = len;
   return domain;
}

void pdt_free_node(pdt_node_t *pn)
{
   int i;
   if(pn==NULL)
      return;

   for(i=0; i<PDT_NODE_SIZE; i++)
   {
      if(pn[i].domain.s!=NULL)
      {
         shm_free(pn[i].domain.s);
         pn[i].domain.s   = NULL;
         pn[i].domain.len = 0;
      }
      if(pn[i].child!=NULL)
      {
         pdt_free_node(pn[i].child);
         pn[i].child = NULL;
      }
   }
   shm_free(pn);
   pn = NULL;
   
   return;
}

void pdt_free_tree(pdt_tree_t *pt)
{
   if(pt == NULL)
      return;

   if(pt->head!=NULL) 
      pdt_free_node(pt->head);
   if(pt->next!=NULL)
      pdt_free_tree(pt->next);
   if(pt->sdomain.s!=NULL)
      shm_free(pt->sdomain.s);
   
   shm_free(pt);
   pt = NULL;
   return;
}

int pdt_print_node(pdt_node_t *pn, char *code, int len)
{
   int i;

   if(pn==NULL || code==NULL || len>=PDT_MAX_DEPTH)
      return 0;
   
   for(i=0; i<PDT_NODE_SIZE; i++)
   {
      code[len]=pdt_char_list.s[i];
      if(pn[i].domain.s!=NULL)
         LM_DBG("[%.*s] [%.*s]\n",
               len+1, code, pn[i].domain.len, pn[i].domain.s);
      pdt_print_node(pn[i].child, code, len+1);
   }

   return 0;
}

static char pdt_code_buf[PDT_MAX_DEPTH+1];
int pdt_print_tree(pdt_tree_t *pt)
{
   int len;

   if(pt == NULL)
   {
      LM_DBG("tree is empty\n");
      return 0;
   }
   
   LM_DBG("[%.*s]\n", pt->sdomain.len, pt->sdomain.s);
   len = 0;
   pdt_print_node(pt->head, pdt_code_buf, len);
   return pdt_print_tree(pt->next);
}

int pdt_check_pd_node(pdt_node_t *pn, str *sp, str *sd,
      char *code, int len)
{
   int i;
   int ret;
 
   if(pn==NULL || code==NULL || len>=PDT_MAX_DEPTH)
      return 0;
   ret = 0;
   for(i=0; i<PDT_NODE_SIZE; i++)
   {
      code[len]=pdt_char_list.s[i];
      if(pn[i].domain.s!=NULL)
      {
         /* we have a domain - check for duplicates */
         LM_DBG("[%.*s] [%.*s]\n",
               len+1, code, pn[i].domain.len, pn[i].domain.s);
         if(sp->len == len+1 &&
               strncmp(sp->s, code, sp->len)==0)
         {
            LM_DBG("duplicated prefix\n");
            return 1;
         }
         if(sd->len == pn[i].domain.len &&
               strncmp(sd->s, pn[i].domain.s, sd->len)==0)
         {
            LM_DBG("duplicated domain\n");
            return 1;
         }
      }
      ret = pdt_check_pd_node(pn[i].child, sp, sd, code, len+1);
      if(ret != 0)
         break;
   }

   return ret;
}

/* returns 
 * 1 if prefix or domain already exists 
 * 0 if prefix or domain does not exist
 * -1 if any error
 */
int pdt_check_pd(pdt_tree_t *pt, str* sdomain, str *sp, str *sd)
{
   int len;
   int ret;
   pdt_tree_t *it;
      
   if(pt==NULL || sp==NULL || sd==NULL)
   {
      LM_ERR("bad parameters\n");
      return -1;
   }

   it = pt;
   while(it!=NULL)
   {
      if(it->sdomain.len==sdomain->len
            && strncasecmp(it->sdomain.s, sdomain->s, sdomain->len)==0)
         break;
      it = it->next;
   }
   if(it == NULL)
      return 0;

   len = 0;
   ret = pdt_check_pd_node(it->head, sp, sd, pdt_code_buf, len);
   return ret;
}