compare.c
上传用户:dgyhgb
上传日期:2007-01-07
资源大小:676k
文件大小:11k
源码类别:

SQL Server

开发平台:

Unix_Linux

  1. /*
  2.  *  compare.c - contains function for tree recognition
  3.  *
  4.  * This file is a part of GNU SQL Server
  5.  *
  6.  *  Copyright (c) 1996, 1997, Free Software Foundation, Inc
  7.  *  Developed at the Institute of System Software
  8.  *  This file is written by Andrew Yahin.
  9.  *
  10.  *  This program is free software; you can redistribute it and/or modify
  11.  *  it under the terms of the GNU General Public License as published by
  12.  *  the Free Software Foundation; either version 2 of the License, or
  13.  *  (at your option) any later version.
  14.  *
  15.  *  This program is distributed in the hope that it will be useful,
  16.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18.  *  GNU General Public License for more details.
  19.  *
  20.  *  You should have received a copy of the GNU General Public License
  21.  *  along with this program; if not, write to the Free Software
  22.  *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23.  *
  24.  *  Contacts: gss@ispras.ru
  25.  *
  26.  */
  27. #pragma "$Id: compare.c,v 1.245 1997/03/31 03:46:38 kml Exp $"
  28. #include <assert.h>
  29. #include <stdio.h>
  30. #include <stdarg.h>
  31. #include "kitty.h"
  32. #undef PR
  33. #define OPS_NUMBER 15
  34. typedef struct cmp_frame {
  35.   struct cmp_frame *up;
  36.   TXTREF            pattern;
  37.   TXTREF            example;
  38.   TXTREF            e_right;
  39.   TXTREF            e_down;
  40.   i4_t               state;
  41. } cmp_stack;
  42. typedef enum {
  43.   NO_DATA,              /* op does not contain any data             */
  44.   STANDARD_COMPARISION, /* op - address of the once recognized node */
  45.   MULTIPLE_COMPARISION  /* op - vector of recognized nodes          */
  46. } cmp_type;
  47. typedef struct  {
  48.   Rule1_type        rule1;
  49.   TXTREF            op[OPS_NUMBER];
  50.   i4_t               op_desc[OPS_NUMBER];
  51. } comp_data; 
  52. static int
  53. recognize_masks(MASKTYPE mx,MASKTYPE my)
  54. {
  55.   MASKTYPE msk,msk1,msk2;
  56.   
  57.   msk1=0;
  58.   SetF(msk1,MARK_CYC_F);
  59.   msk1=2*msk1-1;
  60.   SetF(msk1,MARK_F);
  61.   
  62.   msk=mx;
  63.   msk CLRVL msk1;   /* clear all bits less than MARK_CYC_F and also MARK_F */
  64.   
  65.   msk2=my;
  66.   msk2 CLRVL msk1;
  67.   if(TstF(mx,EXACT_F))
  68.     {
  69.       if(msk!=msk2)
  70. return 0;
  71.     }
  72.   else if((msk & msk2)!=msk)
  73.       return 0;
  74.   return 1;
  75. }
  76. /* 
  77.  * loc_compare compares income subtree 'y' with a pattern 'x'. 'context'
  78.  * contains information about the previous 'upper in the stack' comparision. 
  79.  * NULL value of 'context' means the upper level of comparision or 
  80.  * 'env' is a pointer to the data, which should be returned to the user.
  81.  * this function compares node of pattern tree with given node or may be
  82.  * following nodes of analized tree. Beeing recognized, node of income tree
  83.  * marked by MARK_CMP_F flag to avoid duplicate comparision. The sequence of 
  84.  * analyzing is: attributes - operands (underlied subtrees) - right brothers.
  85.  */
  86. #define RET1   goto SUCCESS_EXIT
  87. #define FAIL   goto FATAL_EXIT
  88. #define GO_UP  
  89. {  
  90.   if (!context ||
  91.       loc_compare(RIGHT_TRN(context->pattern),  
  92.   context->e_right,             
  93.   context->up,env))
  94.     RET1;
  95.   else
  96.     FAIL;
  97. }
  98. static int
  99. loc_compare (TXTREF x, TXTREF y, cmp_stack *context, comp_data *env)
  100. {
  101.   register enum token  code;
  102.   register char       *fmt ;
  103.   register i4_t         i;
  104.   auto     TXTREF      y_right; 
  105. #ifdef PR
  106.   i4_t chk_node=1;
  107.   printf("........%ld.........n",(i4_t)x);
  108. #endif
  109.   
  110.   if (x == y)
  111.     GO_UP;
  112.   /* If the end of pattern line arrived but there are some more nodes in 
  113.    * analized tree we need to check status flag. status==2 means that we've
  114.    * just begined to find 'exist_op'. (Actually it doesn't seem realistic to 
  115.    * catch x==0 in this case. */
  116.   assert(x!=0 || !context || context->state != 2);
  117.   /* state ==1 means that we are in progress of finding 'exist_op' subtree 
  118.    * state ==0 will be found if we suddenly go in the recursive search of
  119.    * this node and in the case or ordinal comparision. 
  120.    */
  121.   if( x == 0 && context && context->state == 1 ) 
  122.     GO_UP;
  123.   
  124.   if ( context && context->state > 0 )
  125.     context->state --;
  126.   
  127.   if(x == 0) 
  128.     FAIL;
  129.   assert(TstF_TRN(x,PATTERN_F));
  130.   
  131.   code = CODE_TRN (x);
  132.   
  133.   /* first step of special cases processing */
  134.   if(code == SKIP_CODES)
  135.     {
  136.       if ( RIGHT_TRN(x) == TNULL) /* { (...) (...) -- } */
  137. /* pattern satisfied by this link of subtrees ; let's check the 
  138.    next subtree in the upper level */
  139. {GO_UP;}
  140.       else /* if there are some additional test for current tree link */
  141. {
  142.   for (; y ; y = RIGHT_TRN(y))
  143.     if (loc_compare(RIGHT_TRN(x),y,context,env))
  144.       RET1;
  145.   FAIL;
  146. }
  147.     }
  148.   
  149.   if ( y == 0 )
  150.     FAIL;
  151.   
  152. #ifdef PR
  153.   printf("%s   %s  %ldn",NAME(code),NAME(CODE_TRN(y)),OPs_IND(x));
  154.   printf("=============================n");
  155. #endif
  156.   if(code == SKIP_CODE)
  157.     return loc_compare(RIGHT_TRN(x),RIGHT_TRN(y),context,env);
  158.   
  159.   if(TstF_TRN(y, MARK_CMP_F))
  160.     /* this node has been already associated with another pattern node */
  161.     FAIL;    
  162.   
  163.   if(TstF_TRN(x,EXIST_OP_F))
  164.     {
  165.       TXTREF p;
  166.       i4_t    state;
  167.       if (!context)
  168. {
  169.   debug_trn(x);
  170.   yyfatal(" 8-0 : quite strange request to find existence of then"
  171.   "pattern above in dummy context ");
  172. }
  173.       ClrF_TRN(x,EXIST_OP_F);
  174.       state = context->state;
  175.       for (p = context->e_down ; p ; p = RIGHT_TRN(p) )
  176. {
  177.   context->state = 2;
  178.   if(loc_compare(x,p,context,env))
  179.     break;
  180. }
  181.       SetF_TRN(x,EXIST_OP_F);
  182.       context->state = state;
  183.       if (!p) /* x isn't comparable to any node */
  184. FAIL;
  185.       RET1;
  186.     }
  187.   /* standart compare process begins here*/
  188.   y_right = RIGHT_TRN(y);
  189.   while(CODE_TRN(y)==NOOP)
  190.     y = DOWN_TRN(y);
  191.   if (code == OPERAND)
  192.     {
  193.       if( (env->rule1==NULL || env->rule1(y,XLNG_TRN(x,0))) && 
  194.           recognize_masks(MASK_TRN(x),MASK_TRN(y))
  195.           )
  196. goto CHECK_OPERANDS;
  197.       else 
  198. FAIL;
  199.     }
  200.   
  201.   if (code != CODE_TRN (y))
  202.     FAIL;
  203.   
  204.   if ( ! recognize_masks(MASK_TRN(x),MASK_TRN(y)))
  205.     FAIL;
  206.   
  207.   fmt = FORMAT (code);
  208.   
  209.   for (i = LENGTH (code) - 1; i >= 0; i--)
  210.     {
  211.       if(
  212. ! ( TST_BIT(XLNG_TRN(x,PTRN_OP(code,i)),PTRN_BIT(i)) )
  213. ) continue;
  214.       
  215.       switch (fmt[i])
  216.         {
  217. case 's':  
  218.   if (XLNG_TRN (x, i) == XLNG_TRN(y, i)) 
  219.     break; /* because identical literals are saved only once */
  220.   if (0==strcmp(STRING(XLTR_TRN (x, i)),STRING(XLTR_TRN(y, i))))
  221.     break;
  222.   FAIL; 
  223. case 'i':
  224.         case 'f':
  225.         case 'l':
  226. case 'y':
  227. case 'x':
  228. case 'R':
  229.   if (XLNG_TRN (x, i) != XLNG_TRN(y, i))
  230.     FAIL;
  231.   break;
  232.         case 't':
  233.         case 'v':
  234.         case 'N':
  235.   if(!loc_compare(XTXT_TRN(x,i),XTXT_TRN(y,i), NULL,env))
  236.     FAIL;
  237.   break;
  238. case '0':
  239.         case 'a': 
  240.         case 'V':
  241.   case 'p':
  242.         case 'd': /* parameters will be tested later                     */
  243.         case 'r': /* These are just pointers, so they don't matter.      */
  244.           break;
  245. case 'L': /* array of longs */
  246.   { 
  247.     TXTREF patvect=XVEC_TRN(x,i);
  248.     TXTREF invect=XVEC_TRN(y,i);
  249.     i4_t j; 
  250.     
  251.     if(patvect && (!invect))
  252.       FAIL;
  253.     if(patvect && invect)
  254.       {
  255. j=VLEN(patvect);
  256. if(j!=VLEN(invect))
  257.   FAIL;
  258. for(;j;j--)
  259.   if(VOP(patvect,j).l != VOP(invect,j).l)
  260.     FAIL;
  261.       }
  262.   }
  263.   break;
  264. case 'T': /* array of expressions */
  265.   { 
  266.     TXTREF patvect=XVEC_TRN(x,i);
  267.     TXTREF invect=XVEC_TRN(y,i);
  268.     i4_t j;
  269.     
  270.     if(patvect && (!invect))
  271.       FAIL;
  272.     if(patvect && invect)
  273.       {
  274. j=VLEN(patvect);
  275. if(j!=VLEN(invect))
  276.   FAIL;
  277. for(;j;j--)
  278.   if(!loc_compare(VOP(patvect,j).txtp,VOP(invect,j).txtp,
  279.   NULL,env) 
  280.     )
  281.     FAIL;
  282.       }
  283.   }
  284.   break;
  285.         default:
  286.   yyfatal("TRL.compare: unexpected format character");
  287.         }
  288.     }
  289. CHECK_OPERANDS: 
  290.   i=OPs_IND(x);
  291.   if(i>=0)
  292.     {
  293.       switch(env->op_desc[i])
  294. {
  295. case NO_DATA:
  296.   env->op[i]=y;
  297.   env->op_desc[i]=STANDARD_COMPARISION;
  298.   break;
  299. case STANDARD_COMPARISION:
  300.   if (env->op[i] == TNULL)
  301.     env->op[i]=y;
  302.   else if(!trn_equal_p(env->op[i],y))
  303.     FAIL;
  304.   break;
  305. default:
  306.   yyerror("Unexpected comparision mode required");
  307. }
  308.     }
  309.   if(HAS_DOWN(x) && DOWN_TRN(x) && (!HAS_DOWN(y) || !DOWN_TRN(y)))
  310.     FAIL;
  311.   SetF_TRN(y, MARK_CMP_F);
  312.   if(HAS_DOWN(x) && DOWN_TRN(x))
  313.     {
  314.       cmp_stack cur_context;
  315.       cur_context.up      = context;
  316.       cur_context.pattern = x;
  317.       cur_context.example = y;
  318.       cur_context.e_right = y_right;
  319.       cur_context.e_down  = DOWN_TRN(y);
  320.       cur_context.state   = 0;
  321.       if(!loc_compare(DOWN_TRN(x), DOWN_TRN(y), &cur_context,env))
  322. FAIL;
  323.     }
  324.   else if (!TstF_TRN(y,VCB_F) || code == COLUMN || code==SCOLUMN )
  325.     /*
  326.      * here we use y_right instead of RIGHT_TRN(y) because of specific
  327.      * of NOOP processing :
  328.      * { ... (Noop  {(y)}) ...} means the same as { ... (y) ...}
  329.      */ 
  330.     if(!loc_compare(RIGHT_TRN(x),y_right, context,env))
  331.       FAIL;
  332.   
  333. SUCCESS_EXIT:
  334.   i=1;
  335. #ifdef  PR
  336.   if(chk_node)
  337.     fprintf(stderr,"trees are equal:n");
  338. #endif
  339.   goto JUST_EXIT;
  340. FATAL_EXIT:
  341.   if (x)
  342.     {
  343.       i=OPs_IND(x);
  344.       /* clearing previously memorized pointer */
  345. if(i>=0)
  346.   switch(env->op_desc[i])
  347.     {
  348.     case NO_DATA:
  349.       break;
  350.     case STANDARD_COMPARISION:
  351.       if (env->op[i] == y)
  352. env->op[i]=TNULL;
  353.       break;
  354.     default:
  355.       yyerror("Unexpected comparision mode required");
  356.     }
  357.     }
  358.   i=0;
  359. #ifdef  PR
  360.   if(chk_node)
  361.     fprintf(stderr,"trees aren't equal:n");
  362. #endif
  363.   
  364. JUST_EXIT:
  365.   if(y)
  366.     ClrF_TRN(y,MARK_CMP_F);   
  367. #ifdef PR
  368.   if(chk_node)
  369.     {
  370.       debug_trn(x);
  371.       debug_trn(y);
  372.       fprintf(stderr,"================n");
  373.     }
  374. #endif
  375.   return i;
  376. }
  377. /*
  378.  * tree_compare routine
  379.  */
  380. int
  381. t_compare (TXTREF x,TXTREF y, TXTREF *Ops, Rule1_type Rule1)
  382. {
  383.   register i4_t rc;
  384.   comp_data    env;
  385.   
  386.   bzero(&env,sizeof(env));
  387.   env.rule1=Rule1;
  388.   rc=loc_compare(x,y, NULL, &env);
  389.   if (rc)
  390.     {
  391.       i4_t i;
  392.       for ( i=0 ; i < OPS_NUMBER; i++)
  393.         if(env.op_desc[i] != NO_DATA)
  394.           {
  395.             assert(Ops);
  396.             Ops[i] = env.op[i];
  397.           }
  398.     }
  399.   return rc;
  400. }
  401. /*--------------------------------------------------------------*/
  402. /* the following function are made for freeing patterns' memory */
  403. /*--------------------------------------------------------------*/
  404. #define DECL(typ,t2) 
  405. typedef struct s_##typ { typ *v; t2 v1; struct s_##typ *n; } typ##_list_t;  
  406. static typ##_list_t *list; register typ##_list_t *cp;
  407. #define IF_FIND(val) for(cp = list; cp; cp = cp->n ) if (cp->v==(val))
  408. #define ADDLIST(typ,val) 
  409. { cp = (typ##_list_t *)xmalloc (sizeof (typ##_list_t)); 
  410.   cp->n = list;
  411.   cp->v = val;
  412.   list = cp;
  413. }
  414. #define CLEAR_LIST(act) while(list) { cp = list; act; list = list->n; xfree(cp); }
  415. void 
  416. register_pattern(TXTREF *pattern)
  417. {
  418.   DECL(TXTREF,char);
  419.   
  420.   if(pattern)
  421.     {
  422.       IF_FIND(pattern)
  423. return;
  424.       ADDLIST(TXTREF,pattern);
  425.     }
  426.   else
  427.     {
  428.       CLEAR_LIST(*(cp->v) = TNULL);
  429.     }
  430. }
  431. TXTREF *
  432. pattern_name(char *pn)
  433. {
  434.   DECL(char,TXTREF);
  435.   
  436.   if(pn)
  437.     {
  438.       IF_FIND(pn)
  439. return &(cp->v1);
  440.       ADDLIST(char,pn);
  441.       return &(cp->v1);
  442.     }
  443.   else
  444.     {
  445.       free_patterns();
  446.       CLEAR_LIST(*(cp->v) = TNULL);
  447.     }
  448.   return NULL;
  449. }