home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / m / mawk11as.zip / REXP / REXP2.C < prev    next >
C/C++ Source or Header  |  1992-01-21  |  10KB  |  351 lines
  1.  
  2. /********************************************
  3. rexp2.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /*$Log:    rexp2.c,v $
  14.  * Revision 3.7  92/01/21  17:33:15  brennan
  15.  * added some casts so that character classes work with signed chars
  16.  * 
  17.  * Revision 3.6  91/10/29  10:54:03  brennan
  18.  * SIZE_T
  19.  * 
  20.  * Revision 3.5  91/08/13  09:10:15  brennan
  21.  * VERSION .9994
  22.  * 
  23.  * Revision 3.4  91/08/08  07:53:34  brennan
  24.  * work around for turboC realloc() bug
  25.  * 
  26.  * Revision 3.4  91/08/07  07:10:47  brennan
  27.  * work around for TurboC realloc() bug
  28.  * 
  29.  * Revision 3.3  91/08/04  15:45:57  brennan
  30.  * minor change for large model dos
  31.  * 
  32.  * Revision 3.2  91/06/10  16:18:14  brennan
  33.  * changes for V7
  34.  * 
  35.  * Revision 3.1  91/06/07  10:33:25  brennan
  36.  * VERSION 0.995
  37.  * 
  38.  * Revision 1.8  91/06/05  09:01:33  brennan
  39.  * changes to RE_new_run_stack
  40.  * 
  41.  * Revision 1.7  91/05/31  10:56:02  brennan
  42.  * stack_empty hack for DOS large model
  43.  * 
  44. */
  45.  
  46.  
  47.  
  48. /*  test a string against a machine   */
  49.  
  50. #include "rexp.h"
  51.  
  52. #define  STACKGROWTH    16
  53.  
  54. /* statics */
  55. static RT_STATE *PROTO(slow_push,(RT_STATE *,STATE*,char*,int)); 
  56.  
  57.  
  58.  
  59. RT_STATE *RE_run_stack_base; 
  60. RT_STATE *RE_run_stack_limit ;
  61.  
  62. /* Large model DOS segment arithemetic breaks the current stack.
  63.    This hack fixes it without rewriting the whole thing, 5/31/91 */
  64. RT_STATE *RE_run_stack_empty ;
  65.  
  66. /* for statistics and debug */
  67. static RT_STATE *stack_max ; 
  68.  
  69. void RE_run_stack_init()
  70. { if ( !RE_run_stack_base )
  71.   {
  72.     RE_run_stack_base = (RT_STATE *)
  73.                  RE_malloc(sizeof(RT_STATE) * STACKGROWTH ) ;
  74.     RE_run_stack_limit = RE_run_stack_base + STACKGROWTH ;
  75.     RE_run_stack_empty = stack_max = RE_run_stack_base-1 ;
  76.   }
  77. }
  78.  
  79. /* sometimes during REmatch(), this stack can grow pretty large.
  80.    In real life cases, the back tracking usually fails. Some
  81.    work is needed here to improve the algorithm.
  82.    I.e., figure out how not to stack useless paths.
  83. */
  84.  
  85. RT_STATE  *RE_new_run_stack()
  86. { int newsize = (RE_run_stack_limit - RE_run_stack_base) + STACKGROWTH ;
  87.  
  88. #ifdef  LMDOS   /* large model DOS */
  89.   /* have to worry about overflow on multiplication (ugh) */
  90.   if ( newsize >= 4096 ) RE_run_stack_base = (RT_STATE*) 0 ;
  91.   else
  92. #endif
  93.  
  94. #ifdef  __TURBOC__  
  95. /* turbo C's realloc() screws up when running out of mem  */
  96.   { RT_STATE *temp = (RT_STATE*)malloc(SIZE_T(newsize*sizeof(RT_STATE))) ;
  97.     if ( temp ) (void)memcpy(temp,RE_run_stack_base,
  98.         SIZE_T((newsize-STACKGROWTH)*sizeof(RT_STATE))) ;
  99.     free(RE_run_stack_base) ;
  100.     RE_run_stack_base = temp ;
  101.   }
  102. #else  /* normal case */
  103.   RE_run_stack_base = (RT_STATE *) realloc( RE_run_stack_base ,
  104.           SIZE_T(newsize * sizeof(RT_STATE)) ) ;
  105. #endif
  106.  
  107.   if ( ! RE_run_stack_base )
  108.   { fprintf(stderr, "out of memory for RE run time stack\n") ;
  109.     /* this is pretty unusual, I've only seen it happen on
  110.        weird input to REmatch() under 16bit DOS , the same
  111.        situation worked easily on 32bit machine.  */
  112.     exit(100) ;
  113.   }
  114.  
  115.   RE_run_stack_limit = RE_run_stack_base + newsize ;
  116.   RE_run_stack_empty = RE_run_stack_base - 1 ;
  117.   return  stack_max = RE_run_stack_base + newsize - STACKGROWTH ;
  118. }
  119.  
  120. static RT_STATE *slow_push(sp, m, s, u)
  121.   RT_STATE *sp ;
  122.   STATE *m ;
  123.   char *s ;
  124.   int   u ;
  125. { 
  126.   if ( sp > stack_max )
  127.      if ( (stack_max = sp) == RE_run_stack_limit )
  128.              sp = RE_new_run_stack() ;
  129.  
  130.   sp->m = m ; sp->s = s ; sp->u = u ;
  131.   return sp ;
  132. }
  133.  
  134. #ifdef   DEBUG
  135. void  print_max_stack(f)
  136.   FILE *f ;
  137. { fprintf(f, "stack_max = %d\n", stack_max-RE_run_stack_base+1) ; }
  138. #endif
  139.  
  140. #ifdef   DEBUG
  141. #define  push(mx,sx,ux)   stackp = slow_push(++stackp, mx, sx, ux)
  142. #else
  143. #define  push(mx,sx,ux)   if (++stackp == RE_run_stack_limit)\
  144.                                 stackp = slow_push(stackp,mx,sx,ux) ;\
  145.                           else\
  146.                           { stackp->m=mx;stackp->s=sx;stackp->u=ux;}
  147. #endif
  148.  
  149.  
  150. #define   CASE_UANY(x)  case  x + U_OFF :  case  x + U_ON
  151.  
  152. /* test if str ~ /machine/
  153. */
  154.  
  155. int  REtest( str, machine)
  156.   char *str ;
  157.   VOID *machine ;
  158. { register STATE *m = (STATE *) machine ;
  159.   register char *s = str ;
  160.   register RT_STATE *stackp ;
  161.   int u_flag ;
  162.   char *str_end ;
  163.   char *ts ; /*convenient temps */
  164.   STATE *tm ;
  165.  
  166.   /* handle the easy case quickly */
  167.   if ( (m+1)->type == M_ACCEPT && m->type == M_STR )
  168.         return  (int ) str_str(s, m->data.str, m->len) ;
  169.   else
  170.   { u_flag = U_ON ; str_end = (char *) 0 ;
  171.     stackp = RE_run_stack_empty ;
  172.     goto  reswitch ;
  173.   }
  174.  
  175. refill :
  176.   if ( stackp == RE_run_stack_empty )  return  0 ;
  177.   m = stackp->m ;
  178.   s = stackp->s ;
  179.   u_flag  = stackp-- -> u ;
  180.  
  181.  
  182. reswitch  :
  183.  
  184.   switch( m->type + u_flag )
  185.   {
  186.     case M_STR + U_OFF + END_OFF :
  187.             if ( strncmp(s, m->data.str, SIZE_T(m->len)) ) goto refill ;
  188.             s += m->len ;  m++ ;
  189.             goto reswitch ;
  190.  
  191.     case M_STR + U_OFF + END_ON :
  192.             if ( strcmp(s, m->data.str) ) goto refill ;
  193.             s += m->len ;  m++ ;
  194.             goto reswitch ;
  195.  
  196.     case M_STR + U_ON + END_OFF :
  197.             if ( !(s = str_str(s, m->data.str, m->len)) ) goto refill ;
  198.             push(m, s+1, U_ON) ;
  199.             s += m->len ; m++ ; u_flag = U_OFF ;
  200.             goto reswitch ;
  201.  
  202.     case M_STR + U_ON + END_ON :
  203.             if ( !str_end )  str_end = s + strlen(s) ;
  204.             ts = str_end - m->len ;
  205.             if (ts < s || memcmp(ts,m->data.str,SIZE_T(m->len+1))) goto refill ;
  206.             s = str_end ; m++ ; u_flag = U_OFF ;
  207.             goto reswitch ;
  208.  
  209.     case M_CLASS + U_OFF + END_OFF :
  210.             if ( !ison(*m->data.bvp, s[0] ) )  goto refill ;
  211.             s++ ; m++ ;
  212.             goto reswitch ;
  213.  
  214.     case M_CLASS + U_OFF + END_ON :
  215.             if ( s[1] || !ison(*m->data.bvp,s[0]) )  goto refill ;
  216.             s++ ; m++ ;
  217.             goto reswitch ;
  218.  
  219.     case M_CLASS + U_ON + END_OFF :
  220.             while ( !ison(*m->data.bvp,s[0]) )
  221.                 if ( s[0] == 0 )  goto refill ;
  222.                 else  s++ ;
  223.             s++ ;
  224.             push(m, s, U_ON) ;
  225.             m++ ; u_flag = U_OFF ;
  226.             goto reswitch ;
  227.  
  228.     case M_CLASS + U_ON + END_ON :
  229.             if ( ! str_end )  str_end = s + strlen(s) ;
  230.             if ( ! ison(*m->data.bvp, str_end[-1]) ) goto refill ;
  231.             s = str_end ; m++ ; u_flag = U_OFF ;
  232.             goto reswitch ;
  233.  
  234.     case M_ANY + U_OFF + END_OFF :
  235.             if ( s[0] == 0 )  goto refill ;
  236.             s++ ; m++ ;
  237.             goto  reswitch ;
  238.  
  239.     case M_ANY + U_OFF + END_ON :
  240.             if ( s[0] == 0 || s[1] != 0 )  goto refill ;
  241.             s++ ; m++ ;
  242.             goto reswitch ;
  243.  
  244.     case M_ANY + U_ON + END_OFF :
  245.             if ( s[0] == 0 )  goto refill ;
  246.             s++ ; 
  247.             push(m, s, U_ON) ;
  248.             m++ ; u_flag = U_OFF ;
  249.             goto  reswitch ;
  250.  
  251.     case M_ANY + U_ON + END_ON :
  252.             if ( s[0] == 0 )  goto refill ;
  253.             if ( ! str_end )  str_end = s + strlen(s) ;
  254.             s = str_end ; m++ ; u_flag = U_OFF ;
  255.             goto reswitch ;
  256.  
  257.     case  M_START + U_OFF + END_OFF :
  258.     case  M_START + U_ON  + END_OFF :
  259.             if ( s != str )  goto  refill ;
  260.             m++ ;  u_flag = U_OFF ;
  261.             goto  reswitch ;
  262.  
  263.     case  M_START + U_OFF + END_ON :
  264.     case  M_START + U_ON  + END_ON :
  265.             if ( s != str || s[0] != 0 )  goto  refill ;
  266.             m++ ; u_flag = U_OFF ;
  267.             goto  reswitch ;
  268.  
  269.     case  M_END + U_OFF  :
  270.             if ( s[0]  != 0 )  goto  refill ;
  271.             m++ ; goto reswitch ;
  272.  
  273.     case  M_END + U_ON :
  274.             s += strlen(s) ;
  275.             m++ ; u_flag = U_OFF ;
  276.             goto reswitch ;
  277.  
  278.     CASE_UANY(M_U) :
  279.             u_flag = U_ON ; m++ ;
  280.             goto reswitch ;
  281.  
  282.     CASE_UANY(M_1J) :
  283.             m += m->data.jump ;
  284.             goto reswitch ;
  285.  
  286.     CASE_UANY(M_2JA) : /* take the non jump branch */
  287.             /* don't stack an ACCEPT */
  288.             if ( (tm = m + m->data.jump)->type == M_ACCEPT ) return 1 ;
  289.             push(tm, s, u_flag) ;
  290.             m++ ;
  291.             goto reswitch ;
  292.  
  293.     CASE_UANY(M_2JB) : /* take the jump branch */
  294.             /* don't stack an ACCEPT */
  295.             if ( (tm = m + 1)->type == M_ACCEPT ) return 1 ;
  296.             push(tm, s, u_flag) ;
  297.             m += m->data.jump ;
  298.             goto reswitch ;
  299.  
  300.     CASE_UANY(M_ACCEPT) :
  301.             return 1 ;
  302.  
  303.     default :
  304.             RE_panic("unexpected case in REtest") ;
  305.   }
  306. }
  307.  
  308.   
  309.  
  310. #ifdef  MAWK
  311.  
  312. char *is_string_split( p, lenp )
  313.   register STATE *p ;
  314.   unsigned *lenp ;
  315. {
  316.   if ( p[0].type == M_STR && p[1].type == M_ACCEPT )
  317.   { *lenp = p->len ;
  318.     return  p->data.str ;
  319.   }
  320.   else   return  (char *) 0 ;
  321. }
  322. #else /* mawk provides its own str_str */
  323.  
  324. char *str_str(target, key, klen)
  325.   register char *target ;
  326.   register char *key ;
  327.   unsigned klen ;
  328. { int c = key[0] ;
  329.  
  330.   switch( klen )
  331.   { case 0 :  return (char *) 0 ;
  332.     case 1 :  return strchr(target, c) ;
  333.     case 2 :  
  334.               while ( target = strchr(target, c) )
  335.                     if ( target[1] == key[1] ) return target ;
  336.                     else target++ ;
  337.               break ;
  338.  
  339.     default :
  340.               klen-- ; key++ ;
  341.               while ( target = strchr(target, c) )
  342.                     if (memcmp(target+1,key,SIZE_T(klen)) == 0) return target ;
  343.                     else target++ ;
  344.               break ;
  345.   }
  346.   return (char *) 0 ;
  347. }
  348.               
  349.  
  350. #endif  /* MAWK */
  351.