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