home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / MAWK113.ZIP / mawk113 / array.c < prev    next >
C/C++ Source or Header  |  1993-01-20  |  10KB  |  468 lines
  1.  
  2. /********************************************
  3. array.c
  4. copyright 1991, 1992.  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: array.c,v $
  14.  * Revision 5.3.1.1  1993/01/20  12:24:25  mike
  15.  * patch3: safer double to int conversions
  16.  *
  17.  * Revision 5.3  1992/11/28  23:48:42  mike
  18.  * For internal conversion numeric->string, when testing
  19.  * if integer, use longs instead of ints so 16 and 32 bit
  20.  * systems behave the same
  21.  *
  22.  * Revision 5.2  1992/04/07  17:17:31  brennan
  23.  * patch 2
  24.  * n = split(s,A,r)
  25.  * delete A[i] if i not in 1..n
  26.  * This is consistent with [ng]?awk
  27.  *
  28.  * Revision 5.1  91/12/05  07:55:32  brennan
  29.  * 1.1 pre-release
  30.  * 
  31. */
  32.  
  33. #include "mawk.h"
  34. #include "symtype.h"
  35. #include "memory.h"
  36. #include "field.h"
  37. #include "bi_vars.h"
  38.  
  39. /* convert doubles to string for array indexing */
  40. #define   NO_MOVE       2
  41. #define   NO_IVAL       (-1)
  42.  
  43. static ANODE *PROTO(find_by_sval, (ARRAY, STRING *, int) ) ;
  44. static ANODE *PROTO(find_by_index, (ARRAY, int,long,int) ) ;
  45. static ANODE *PROTO(find_by_dval, (ARRAY, double, int)) ;
  46. static void PROTO(load_array_ov, (ARRAY) ) ;
  47. static void PROTO(ilist_delete, (ARRAY, ANODE*)) ;
  48.  
  49.  
  50. extern unsigned hash() ;
  51.  
  52. /* An array A is a pointer to an array of struct array,
  53.    which is two hash tables in one.  One for strings
  54.    and one for non-negative integers (this is much simplier
  55.    and works just as well as previous versions)
  56.  
  57.    Each array is of size A_HASH_PRIME.
  58.  
  59.    When an index is deleted via  delete A[i], the
  60.    ANODE is not removed from the hash chain.  A[i].cp
  61.    and A[i].sval are both freed and sval is set NULL.
  62.    This method of deletion simplifies for( i in A ) loops.
  63.  
  64. */
  65.  
  66.  
  67. static  ANODE *find_by_sval(A, sval, cflag)
  68.   ARRAY  A ;
  69.   STRING *sval ;
  70.   int  cflag ; /* create if on */
  71. { 
  72.    char *s = sval->str ;
  73.    unsigned h = hash(s) % A_HASH_PRIME ;
  74.    register ANODE *p = A[h].link ;
  75.    ANODE *q = 0 ; /* holds first deleted ANODE */
  76.  
  77.    while ( 1 )
  78.      if ( !p )  goto not_there ;
  79.      else 
  80.      if ( p->sval )
  81.     if ( strcmp(s,p->sval->str) == 0 )  return p ;
  82.     else  p = p->link ;
  83.      else { q = p ; p = p->link ; break ; }
  84.     
  85.    while ( p )  /* q is now set */
  86.      if ( p->sval && strcmp(s,p->sval->str) == 0 )  return p ; 
  87.      else  p = p->link ;
  88.  
  89. not_there :
  90.    if ( cflag )
  91.    {
  92.        if ( q )  p = q ; /* reuse the deleted node q */
  93.        else
  94.        { p = (ANODE *)zmalloc(sizeof(ANODE)) ;
  95.          p->link = A[h].link ; A[h].link = p ;
  96.        }
  97.  
  98.        p->ival = NO_IVAL ;
  99.        p->sval = sval ;
  100.        sval->ref_cnt++ ;
  101.        p->cp = (CELL *) zmalloc(sizeof(CELL)) ;
  102.        p->cp->type = C_NOINIT ;
  103.    }
  104.    return p ;
  105. }
  106.  
  107.  
  108. /* find an array by (long) integer ival.
  109.    Caller has already computed the hash value index.
  110.    (This allows fast insertion for split())
  111. */
  112.  
  113. static ANODE  *find_by_index(A, index, ival, flag)
  114.   ARRAY  A ;
  115.   int index; 
  116.   long ival; 
  117.   int flag ;
  118. {
  119.   register ANODE *p = A[index].ilink ;
  120.   ANODE *q = 0 ; /* trails p */
  121.  
  122.   while ( p )
  123.        if ( p->ival == ival )  /* found */
  124.          if ( !q || flag == NO_MOVE )  return  p ;
  125.          else /* delete to put at front */
  126.          { q->ilink = p->ilink ; goto found ; }
  127.         
  128.        else
  129.        { q = p ; p = p->ilink ; }
  130.  
  131.    /* not there, still need to look by sval */
  132.    
  133.    { /* convert to string */
  134.      char xbuff[16] ;
  135.      STRING *sval ;
  136.      char *s = xbuff+14 ;
  137.      long x = ival ;
  138.  
  139.      xbuff[15] = 0 ;
  140.  
  141.      do { *s-- = x%10 + '0' ; x /= 10 ; } while(x) ;
  142.      sval = new_STRING(s+1) ;
  143.      p = find_by_sval(A, sval, flag) ;
  144.      free_STRING(sval) ;
  145.    }
  146.  
  147.  
  148.    if ( ! p )  return (ANODE *) 0 ;
  149.  
  150.    p->ival = ival ;
  151.  
  152. found : /* put p at front */
  153.    p->ilink = A[index].ilink ; A[index].ilink = p ;
  154.    return p ;
  155. }
  156.  
  157.  
  158. static ANODE *find_by_dval(A, d, flag)
  159.   ARRAY A ;
  160.   double d ;
  161.   int flag ;
  162. {
  163.   long lval ;
  164.   ANODE *p ;
  165.   char xbuff[260] ;
  166.   STRING *sval ;
  167.   
  168.  
  169.   lval = d_to_l(d) ;
  170.   if ( (double)lval == d ) /* integer valued */
  171.   {
  172.     if ( lval >= 0 )  
  173.     {
  174.             return 
  175.         find_by_index(A, (int)(lval%A_HASH_PRIME), lval, flag) ;
  176.     }
  177.     else
  178.     (void) sprintf(xbuff, INT_FMT, lval) ;
  179.   } 
  180.   else (void) sprintf(xbuff, string(CONVFMT)->str, d) ;
  181.  
  182.   sval = new_STRING(xbuff) ;
  183.   p = find_by_sval(A, sval, flag) ;
  184.   free_STRING(sval) ;
  185.   return p ;
  186. }
  187.  
  188.   
  189.  
  190. CELL *array_find(A, cp, create_flag)
  191.   ARRAY A ;
  192.   CELL *cp ;
  193.   int create_flag ;
  194. {
  195.   ANODE *ap ;
  196.  
  197.   switch( cp->type )
  198.   {
  199.     case C_DOUBLE :
  200.         ap = find_by_dval(A, cp->dval, create_flag) ;
  201.         break ;
  202.  
  203.     case  C_NOINIT :
  204.         ap = find_by_sval(A, &null_str, create_flag) ;
  205.         break ;
  206.  
  207.     default :
  208.         ap = find_by_sval(A, string(cp), create_flag) ;
  209.         break ;
  210.   }
  211.  
  212.   return  ap ? ap->cp : (CELL *) 0 ;
  213. }
  214.  
  215.  
  216. void  array_delete(A, cp)
  217.   ARRAY A ; CELL *cp ;
  218. {
  219.   ANODE *ap ;
  220.  
  221.   switch( cp->type )
  222.   {
  223.     case C_DOUBLE :
  224.         ap = find_by_dval(A, cp->dval, NO_CREATE) ;
  225.     /* cut the ilink */
  226.         if ( ap && ap->ival >= 0 ) /* must be at front */
  227.                 A[(int)(ap->ival%A_HASH_PRIME)].ilink = ap->ilink ;
  228.         break ;
  229.  
  230.     case  C_NOINIT :
  231.         ap = find_by_sval(A, &null_str, NO_CREATE) ;
  232.         break ;
  233.  
  234.     default :
  235.         ap = find_by_sval(A, string(cp), NO_CREATE) ;
  236.         if ( ap && ap->ival >= 0 ) ilist_delete(A, ap) ;
  237.         break ;
  238.   }
  239.  
  240.   
  241.   /* delete -- leave the empty ANODE so for(i in A)
  242.      works */
  243.   if ( ap )
  244.   { free_STRING(ap->sval) ; ap->sval = (STRING *) 0 ;
  245.     cell_destroy(ap->cp)  ; zfree(ap->cp, sizeof(CELL)) ;
  246.   }
  247. }
  248.  
  249. /* load into an array from the split_ov_list */
  250.  
  251. static void  load_array_ov(A)
  252.   ARRAY A ;
  253. {
  254.   register SPLIT_OV *p ;
  255.   register CELL *cp ;
  256.   SPLIT_OV *q ;
  257.  
  258.   int cnt = MAX_SPLIT + 1 ;
  259.   int index = (MAX_SPLIT+1) % A_HASH_PRIME ;
  260.  
  261.   p = split_ov_list ; split_ov_list = (SPLIT_OV*) 0 ;
  262.  
  263. #ifdef  DEBUG
  264.   if ( !p ) bozo("array_ov") ;
  265. #endif
  266.  
  267.   while( 1 )
  268.   {
  269.     cp = find_by_index(A, index, (long)cnt, NO_MOVE) ->cp ;
  270.     cell_destroy(cp) ;
  271.     cp->type = C_MBSTRN ;
  272.     cp->ptr = (PTR) p->sval ;
  273.  
  274.     q = p ; p = p->link ; zfree(q, sizeof(SPLIT_OV)) ;
  275.     if ( !p )  break ;
  276.  
  277.     cnt++ ;
  278.     if ( ++index == A_HASH_PRIME )  index = 0 ;
  279.   }
  280. }
  281.  
  282. /* delete an ANODE from the ilist that is known
  283.    to be there */
  284.  
  285. static  void  ilist_delete(A, d) 
  286.   ARRAY A ;
  287.   ANODE *d ;
  288. {
  289.   int index = d->ival % A_HASH_PRIME ;
  290.   register ANODE *p = A[index].ilink ;
  291.   register ANODE *q = (ANODE *) 0 ;
  292.  
  293.   while ( p != d ) { q = p ; p = p->ilink ; }
  294.  
  295.   if ( q )  q->ilink = p->ilink ;
  296.   else  A[index].ilink = p->ilink ;
  297. }
  298.  
  299.  
  300. /* this is called by bi_split()
  301.    to load strings into an array
  302. */
  303.  
  304. void  load_array( A, cnt)
  305.   ARRAY  A ;
  306.   register int cnt ;
  307. {
  308.   register CELL *cp ;
  309.   register int index ;
  310.  
  311.   { /* clear A , leaving only A[1]..A[cnt] (if exist) */
  312.     int i ;
  313.     ANODE *p ;
  314.  
  315.     for( i = 0 ; i < A_HASH_PRIME ; i++ )
  316.     {
  317.       p = A[i].link ;
  318.       while ( p )
  319.       {
  320.     if ( p->sval && (p->ival <= 0 || p->ival > cnt) )
  321.     {
  322.       if (p->ival >= 0) ilist_delete(A, p) ;
  323.  
  324.       free_STRING(p->sval) ;
  325.       p->sval = (STRING *) 0 ;
  326.       cell_destroy(p->cp) ;
  327.       ZFREE(p->cp) ;
  328.     }
  329.     p = p->link ;
  330.       }
  331.     }
  332.   }
  333.   if ( cnt > MAX_SPLIT )
  334.   {
  335.     load_array_ov(A) ;
  336.     cnt = MAX_SPLIT ;
  337.   }
  338.  
  339.   index = cnt % A_HASH_PRIME ;
  340.  
  341.   while ( cnt )
  342.   {
  343.     cp = find_by_index(A, index, (long) cnt, NO_MOVE) ->cp  ;
  344.     cell_destroy(cp) ;
  345.     cp->type = C_MBSTRN ;
  346.     cp->ptr = (PTR) split_buff[--cnt] ;
  347.  
  348.     if ( --index < 0 )  index = A_HASH_PRIME - 1 ;
  349.   }
  350. }
  351.  
  352.  
  353. /* cat together cnt elements on the eval stack to form
  354.    an array index using SUBSEP */
  355.  
  356. CELL *array_cat( sp, cnt)
  357.   register CELL *sp ;
  358.   int cnt ;
  359. { register CELL *p ;  /* walks the stack */
  360.   CELL subsep ;  /* a copy of SUBSEP */
  361.   unsigned subsep_len ;
  362.   char *subsep_str ;
  363.   unsigned total_len ; /* length of cat'ed expression */
  364.   CELL *top ;  /* sp at entry */
  365.   char *t ; /* target ptr when catting */
  366.   STRING *sval ;  /* build new STRING here */
  367.  
  368.   /* get a copy of subsep, we may need to cast */
  369.   (void) cellcpy(&subsep, SUBSEP) ;
  370.   if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
  371.   subsep_len = string(&subsep)->len ;
  372.   subsep_str = string(&subsep)->str ;
  373.   total_len = --cnt * subsep_len ;
  374.  
  375.   top = sp ;
  376.   sp -= cnt ;
  377.   for( p = sp ; p <= top ; p++ )
  378.   {
  379.     if ( p->type < C_STRING ) cast1_to_s(p) ;
  380.     total_len += string(p)->len ;
  381.   }
  382.  
  383.   sval = new_STRING((char *)0, total_len) ;
  384.   t = sval->str ;
  385.  
  386.   /* put the pieces together */
  387.   for( p = sp ; p < top ; p++ )
  388.   { (void) memcpy(t, string(p)->str, SIZE_T(string(p)->len)) ;
  389.     (void) memcpy( t += string(p)->len, subsep_str, SIZE_T(subsep_len)) ;
  390.     t += subsep_len ;
  391.   }
  392.   /* p == top */
  393.   (void) memcpy(t, string(p)->str, SIZE_T(string(p)->len)) ;
  394.  
  395.   /* done, now cleanup */
  396.   free_STRING(string(&subsep)) ;
  397.   while ( p >= sp )  { free_STRING(string(p)) ; p-- ; }
  398.   sp->type = C_STRING ;
  399.   sp->ptr = (PTR) sval ;
  400.   return sp ;
  401. }
  402.  
  403.  
  404. /* free all memory used by an array,
  405.    only used for arrays local to a function call
  406. */
  407.  
  408. void  array_free(A)
  409.   ARRAY  A ;
  410. { register ANODE *p ;
  411.   register int i ;
  412.   ANODE *q ;
  413.  
  414.   for( i = 0 ; i < A_HASH_PRIME ; i++ )
  415.   { p = A[i].link ;
  416.     while ( p )
  417.     { /* check its not a deleted node */
  418.       if ( p->sval )
  419.       { free_STRING(p->sval) ;
  420.         cell_destroy(p->cp) ;
  421.         free_CELL(p->cp) ;
  422.       }
  423.  
  424.       q = p ; p = p->link ;
  425.       zfree( q, sizeof(ANODE)) ;
  426.     }
  427.   }
  428.  
  429.   zfree(A, sizeof(A[0]) * A_HASH_PRIME ) ;
  430. }
  431.  
  432.  
  433. int  inc_aloop_state( ap )
  434.   ALOOP_STATE *ap ;
  435. {
  436.   register ANODE *p ;
  437.   register int i ;
  438.   ARRAY  A = ap->A ;
  439.   CELL *cp ;
  440.  
  441.   if ( (i = ap->index) == -1 )  p = A[++i].link ;
  442.   else  p = ap->ptr->link ;
  443.  
  444.   while ( 1 )
  445.   {
  446.     if ( !p )
  447.     if ( ++i == A_HASH_PRIME )  return 0 ;
  448.     else
  449.     { p = A[i].link ; continue ; }
  450.  
  451.     if ( p->sval )  /* found one */
  452.     {
  453.       cp = ap->var ;
  454.       cell_destroy(cp) ;
  455.       cp->type = C_STRING ;
  456.       cp->ptr = (PTR) p->sval ;
  457.       p->sval->ref_cnt++ ;
  458.  
  459.       /* save the state */
  460.       ap->index = i ;
  461.       ap->ptr = p ;
  462.       return 1 ;
  463.     }
  464.     else /* its deleted */
  465.     p = p->link ;
  466.   }
  467. }
  468.