home *** CD-ROM | disk | FTP | other *** search
/ Acorn User 11 / AUCD11B.iso / LANGUAGES / WraithSet / AwkStuff / MawkSrc / c / array next >
Encoding:
Text File  |  1996-09-17  |  17.0 KB  |  606 lines
  1. /*
  2. array.c 
  3. copyright 1991-96, Michael D. Brennan
  4.  
  5. This is a source file for mawk, an implementation of
  6. the AWK programming language.
  7.  
  8. Mawk is distributed without warranty under the terms of
  9. the GNU General Public License, version 2, 1991.
  10. */
  11.  
  12. /*
  13. This file was generated with the command
  14.  
  15.    notangle -R'"array.c"' array.w > array.c
  16.  
  17. Notangle is part of Norman Ramsey's noweb literate programming package
  18. available from CTAN(ftp.shsu.edu).
  19.  
  20. It's easiest to read or modify this file by working with array.w.
  21. */
  22.  
  23. #include "mawk.h"
  24. #include "symtype.h"
  25. #include "memory.h"
  26. #include "field.h"
  27. #include "bi_vars.h"
  28. struct anode ;
  29. typedef struct {struct anode *slink, *ilink ;} DUAL_LINK ;
  30.  
  31. typedef struct anode {
  32.    struct anode *slink ;
  33.    struct anode  *ilink ;
  34.    STRING *sval ;
  35.    unsigned hval ;
  36.    Int     ival ;
  37.    CELL    cell ;
  38. } ANODE ;
  39.  
  40.  
  41. #define NOT_AN_IVALUE (-Max_Int-1)  /* usually 0x80000000 */
  42.  
  43. #define STARTING_HMASK    63  /* 2^6-1, must have form 2^n-1 */
  44. #define MAX_AVE_LIST_LENGTH   12
  45. #define hmask_to_limit(x) (((x)+1)*MAX_AVE_LIST_LENGTH)
  46.  
  47. static ANODE* PROTO(find_by_ival,(ARRAY, Int, int)) ;
  48. static ANODE* PROTO(find_by_sval,(ARRAY, STRING*, int)) ;
  49. static void PROTO(add_string_associations,(ARRAY)) ;
  50. static void PROTO(make_empty_table,(ARRAY, int)) ;
  51. static void PROTO(convert_split_array_to_table,(ARRAY)) ;
  52. static void PROTO(double_the_hash_table,(ARRAY)) ;
  53. static unsigned PROTO(ahash, (STRING*)) ;
  54.  
  55.  
  56. CELL* array_find(A, cp, create_flag)
  57.    ARRAY A ;
  58.    CELL *cp ;
  59.    int create_flag ;
  60. {
  61.    ANODE *ap ;
  62.    if (A->size == 0 && !create_flag) 
  63.       /* eliminating this trivial case early avoids unnecessary conversions later */
  64.       return (CELL*) 0 ;
  65.    switch (cp->type) {
  66.       case C_DOUBLE:
  67.          {
  68.             double d = cp->dval ;
  69.             Int ival = d_to_I(d) ;
  70.             if ((double)ival == d) {
  71.                if (A->type == AY_SPLIT) {
  72.                   if (ival >= 1 && ival <= A->size) 
  73.                      return (CELL*)A->ptr+(ival-1) ;
  74.                   if (!create_flag) return (CELL*) 0 ;
  75.                   convert_split_array_to_table(A) ;
  76.                }
  77.                else if (A->type == AY_NULL) make_empty_table(A, AY_INT) ;
  78.                ap = find_by_ival(A, ival, create_flag) ;
  79.             }
  80.             else {
  81.                /* convert to string */
  82.                char buff[260] ;
  83.                STRING *sval ;
  84.                sprintf(buff, string(CONVFMT)->str, d) ;
  85.                sval = new_STRING(buff) ;
  86.                ap = find_by_sval(A,sval,create_flag) ;
  87.                free_STRING(sval) ;
  88.             }
  89.          }
  90.  
  91.          break ;
  92.       case C_NOINIT:
  93.          ap = find_by_sval(A, &null_str, create_flag) ;
  94.          break ;
  95.       default:
  96.          ap = find_by_sval(A, string(cp), create_flag) ;
  97.          break ;
  98.    }
  99.    return ap ? &ap->cell : (CELL *) 0 ;
  100. }
  101.  
  102. void array_delete(A, cp)
  103.    ARRAY A ;
  104.    CELL *cp ;
  105. {
  106.    ANODE *ap ;
  107.    if (A->size == 0) return ; 
  108.    switch(cp->type) {
  109.       case C_DOUBLE :
  110.          {
  111.             double d = cp->dval ;
  112.             Int ival = d_to_I(d) ;
  113.             if ((double)ival == d) {
  114.                                       if (A->type == AY_SPLIT)
  115.                                          if (ival >=1 && ival <= A->size) convert_split_array_to_table(A) ;
  116.                                          else return ; /* ival not in range */
  117.                                       ap = find_by_ival(A, ival, NO_CREATE) ;
  118.                                       if (ap) { /* remove from the front of the ilist */
  119.                                          DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
  120.                                          table[ap->ival & A->hmask].ilink = ap->ilink ;
  121.                                          if (ap->sval) {
  122.                                             ANODE *p, *q = 0 ;
  123.                                             int index = ap->hval & A->hmask ;
  124.                                             p = table[index].slink ;
  125.                                             while(p != ap) { q = p ; p = q->slink ; }
  126.                                             if (q) q->slink = p->slink ;
  127.                                             else table[index].slink = p->slink ;
  128.                                             free_STRING(ap->sval) ;
  129.                                          }
  130.  
  131.                                          cell_destroy(&ap->cell) ;
  132.                                          ZFREE(ap) ;
  133.                                          if (--A->size == 0) array_clear(A) ;
  134.  
  135.  
  136.                                       }
  137.                                       return ;
  138.                                    }
  139.  
  140.             else { /* get the string value */
  141.                char buff[260] ;
  142.                STRING *sval ;
  143.                sprintf(buff, string(CONVFMT)->str, d) ;
  144.                sval = new_STRING(buff) ;
  145.                ap = find_by_sval(A, sval, NO_CREATE) ;
  146.                free_STRING(sval) ;
  147.             }
  148.          }
  149.          break ;
  150.       case C_NOINIT :
  151.          ap = find_by_sval(A, &null_str, NO_CREATE) ;
  152.          break ;
  153.       default :
  154.          ap = find_by_sval(A, string(cp), NO_CREATE) ;
  155.          break ;
  156.    }
  157.    if (ap) { /* remove from the front of the slist */
  158.       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
  159.       table[ap->hval&A->hmask].slink = ap->slink ;
  160.       if (ap->ival != NOT_AN_IVALUE) {
  161.          ANODE *p, *q = 0 ;
  162.          int index = ap->ival & A->hmask ;
  163.          p = table[index].ilink ;
  164.          while(p != ap) { q = p ; p = q->ilink ; }
  165.          if (q) q->ilink = p->ilink ;
  166.          else table[index].ilink = p->ilink ;
  167.       }
  168.  
  169.       free_STRING(ap->sval) ;
  170.       cell_destroy(&ap->cell) ;
  171.       ZFREE(ap) ;
  172.       if (--A->size == 0) array_clear(A) ;
  173.  
  174.  
  175.    }
  176. }
  177.  
  178. void array_load(A, cnt)
  179.    ARRAY A ;
  180.    int cnt ;
  181. {
  182.    CELL *cells ; /* storage for A[1..cnt] */
  183.    int i ;  /* index into cells[] */
  184.    if (A->type != AY_SPLIT || A->limit < cnt) {
  185.       array_clear(A) ;
  186.       A->limit = (cnt&~3)+4 ;
  187.       A->ptr = zmalloc(A->limit*sizeof(CELL)) ;
  188.       A->type = AY_SPLIT ;
  189.    }
  190.    else
  191.       for(i=0;i < A->size; i++)  cell_destroy((CELL*)A->ptr+i) ;
  192.  
  193.    cells = (CELL*) A->ptr ;
  194.    A->size = cnt ;
  195.    if (cnt > MAX_SPLIT) {
  196.       SPLIT_OV *p = split_ov_list ;
  197.       SPLIT_OV *q ;
  198.       split_ov_list = (SPLIT_OV*) 0 ;
  199.       i = MAX_SPLIT ;  
  200.       while( p ) {
  201.          cells[i].type = C_MBSTRN ;
  202.          cells[i].ptr = (PTR) p->sval ;
  203.          q = p ; p = q->link ; ZFREE(q) ;
  204.          i++ ;
  205.       }
  206.       cnt = MAX_SPLIT ;
  207.    }
  208.  
  209.    for(i=0;i < cnt; i++) {
  210.       cells[i].type = C_MBSTRN ;
  211.       cells[i].ptr = split_buff[i] ;
  212.    }
  213. }
  214.  
  215. void array_clear(A)
  216.    ARRAY A ;
  217. {
  218.    int i ;
  219.    ANODE *p, *q ;
  220.    if (A->type == AY_SPLIT) {
  221.       for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
  222.       zfree(A->ptr, A->limit * sizeof(CELL)) ;
  223.    }
  224.    else if (A->type & AY_STR) {
  225.       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
  226.       for(i=0;i <= A->hmask; i++) {
  227.          p = table[i].slink ;
  228.          while(p) {
  229.             q = p ; p = q->slink ;
  230.             free_STRING(q->sval) ;
  231.             cell_destroy(&q->cell) ;
  232.             ZFREE(q) ;
  233.          }
  234.       }
  235.       zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
  236.    }
  237.    else if (A->type & AY_INT) {
  238.       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
  239.       for(i=0;i <= A->hmask; i++) {
  240.          p = table[i].ilink ;
  241.          while(p) {
  242.             q = p ; p = q->ilink ;
  243.             cell_destroy(&q->cell) ;
  244.             ZFREE(q) ;
  245.          }
  246.       }
  247.       zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
  248.    }
  249.    memset(A, 0, sizeof(*A)) ;
  250. }
  251.  
  252.  
  253.  
  254. STRING** array_loop_vector(A, sizep)
  255.    ARRAY A ;
  256.    unsigned *sizep ;
  257. {
  258.    STRING** ret ;
  259.    *sizep = A->size ;
  260.    if (A->size > 0) {
  261.       if (!(A->type & AY_STR)) add_string_associations(A) ;
  262.       ret = (STRING**) zmalloc(A->size*sizeof(STRING*)) ;
  263.       {
  264.          int r = 0 ; /* indexes ret */
  265.          DUAL_LINK* table = (DUAL_LINK*) A->ptr ;
  266.          int i ; /* indexes table */
  267.          ANODE *p ; /* walks slists */
  268.          for(i=0;i <= A->hmask; i++) {
  269.             for(p = table[i].slink; p ; p = p->slink) {
  270.                ret[r++] = p->sval ;
  271.                p->sval->ref_cnt++ ;
  272.             }
  273.          }
  274.       }
  275.  
  276.       return ret ;
  277.    }
  278.    else return (STRING**) 0 ;
  279. }
  280.  
  281. CELL *array_cat(sp, cnt)
  282.    CELL *sp ;
  283.    int cnt ;
  284. {
  285.    CELL *p ;  /* walks the eval stack */
  286.    CELL subsep ;  /* local copy of SUBSEP */
  287.    unsigned subsep_len ; /* string length of subsep_str */
  288.    char *subsep_str ;   
  289.  
  290.    unsigned total_len ;  /* length of cat'ed expression */
  291.    CELL *top ;   /* value of sp at entry */
  292.    char *target ;  /* build cat'ed char* here */
  293.    STRING *sval ;  /* build cat'ed STRING here */
  294.    cellcpy(&subsep, SUBSEP) ;
  295.    if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
  296.    subsep_len = string(&subsep)->len ;
  297.    subsep_str = string(&subsep)->str ;
  298.  
  299.    top = sp ; sp -= (cnt-1) ;
  300.  
  301.    total_len = (cnt-1)*subsep_len ;
  302.    for(p = sp ; p <= top ; p++) {
  303.       if ( p->type < C_STRING ) cast1_to_s(p) ;
  304.       total_len += string(p)->len ;
  305.    }
  306.  
  307.    sval = new_STRING0(total_len) ;
  308.    target = sval->str ;
  309.    for(p = sp ; p < top ; p++) {
  310.       memcpy(target, string(p)->str, string(p)->len) ;
  311.       target += string(p)->len ;
  312.       memcpy(target, subsep_str, subsep_len) ;
  313.       target += subsep_len ;
  314.    }
  315.    /* now p == top */
  316.    memcpy(target, string(p)->str, string(p)->len) ;
  317.  
  318.    for(p = sp; p <= top ; p++) free_STRING(string(p)) ;
  319.    free_STRING(string(&subsep)) ;
  320.    /* set contents of sp , sp->type > C_STRING is possible so reset */
  321.    sp->type = C_STRING ; 
  322.    sp->ptr = (PTR) sval ;
  323.    return sp ;
  324.  
  325. }
  326.  
  327. static ANODE* find_by_ival(A, ival, create_flag)
  328.    ARRAY A ;
  329.    Int ival ;
  330.    int create_flag ;
  331. {
  332.    DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
  333.    unsigned index = ival & A->hmask ;
  334.    ANODE *p = table[index].ilink ; /* walks ilist */
  335.    ANODE *q = (ANODE*) 0 ; /* trails p */
  336.    while(1) {
  337.       if (!p) {
  338.           /* search failed */
  339.           if (A->type & AY_STR) {
  340.              /* need to search by string */
  341.              char buff[256] ;
  342.              STRING *sval ;
  343.              sprintf(buff, INT_FMT, ival) ;
  344.              sval = new_STRING(buff) ;
  345.              p = find_by_sval(A, sval, create_flag) ;
  346.              free_STRING(sval) ;
  347.              if (!p) return (ANODE*) 0 ;
  348.           }
  349.           else if (create_flag) {
  350.              p = ZMALLOC(ANODE) ;
  351.              p->sval = (STRING*) 0 ;
  352.              p->cell.type = C_NOINIT ;
  353.              if (++A->size > A->limit) {
  354.                 double_the_hash_table(A) ; /* changes table, may change index */
  355.                 table = (DUAL_LINK*) A->ptr ;
  356.                 index = A->hmask & ival ;
  357.              }
  358.           }
  359.           else return (ANODE*) 0 ;
  360.           p->ival = ival ;
  361.           A->type |= AY_INT ;
  362.  
  363.           break ;
  364.       }
  365.       else if (p->ival == ival) { 
  366.          /* found it, now move to the front */
  367.          if (!q) /* already at the front */
  368.             return p ;
  369.          /* delete for insertion at the front */
  370.          q->ilink = p->ilink ;
  371.          break ;
  372.       }
  373.       q = p ; p = q->ilink ;
  374.    }
  375.    /* insert at the front */
  376.    p->ilink = table[index].ilink ;
  377.    table[index].ilink = p ;
  378.    return p ;
  379. }
  380.  
  381. static ANODE* find_by_sval(A, sval, create_flag)
  382.    ARRAY A ;
  383.    STRING *sval ;
  384.    int create_flag ;
  385. {
  386.    unsigned hval = ahash(sval) ;
  387.    char *str = sval->str ;
  388.    DUAL_LINK *table ;
  389.    int index ;
  390.    ANODE *p ;  /* walks list */
  391.    ANODE *q = (ANODE*) 0 ; /* trails p */
  392.    if (! (A->type & AY_STR)) add_string_associations(A) ;
  393.    table = (DUAL_LINK*) A->ptr ;
  394.    index = hval & A->hmask ;
  395.    p = table[index].slink ;
  396.    while(1) {
  397.       if (!p)  {
  398.          if (create_flag) {
  399.             {
  400.                p = ZMALLOC(ANODE) ;
  401.                p->sval = sval ;
  402.                sval->ref_cnt++ ;
  403.                p->ival = NOT_AN_IVALUE ;
  404.                p->hval = hval ;
  405.                p->cell.type = C_NOINIT ;
  406.                if (++A->size > A->limit) {
  407.                   double_the_hash_table(A) ; /* changes table, may change index */
  408.                   table = (DUAL_LINK*) A->ptr ;
  409.                   index = hval & A->hmask ;
  410.                }
  411.             }
  412.  
  413.             break ;
  414.          }
  415.          else return (ANODE*) 0 ;
  416.       }
  417.       else if (p->hval == hval && strcmp(p->sval->str,str) == 0 ) {
  418.          /* found */
  419.          if (!q) /* already at the front */
  420.             return p ;
  421.          else { /* delete for move to the front */
  422.             q->slink = p->slink ;
  423.             break ;
  424.          }
  425.       }
  426.       q = p ; p = q->slink ;
  427.    }
  428.    p->slink = table[index].slink ;
  429.    table[index].slink = p ;
  430.    return p ;
  431. }
  432.  
  433. static void add_string_associations(A)
  434.    ARRAY A ;
  435. {
  436.    if (A->type == AY_NULL) make_empty_table(A, AY_STR) ;
  437.    else {
  438.       DUAL_LINK *table ;
  439.       int i ; /* walks table */
  440.       ANODE *p ; /* walks ilist */
  441.       char buff[256] ;
  442.       if (A->type == AY_SPLIT) convert_split_array_to_table(A) ;
  443.       table = (DUAL_LINK*) A->ptr ;
  444.       for(i=0;i <= A->hmask; i++) {
  445.          p = table[i].ilink ;
  446.          while(p) {
  447.             sprintf(buff, INT_FMT, p->ival) ;
  448.             p->sval = new_STRING(buff) ;
  449.             p->hval = ahash(p->sval) ;
  450.             p->slink = table[A->hmask&p->hval].slink ;
  451.             table[A->hmask&p->hval].slink = p ;
  452.             p = p->ilink ;
  453.          }
  454.       }
  455.       A->type |= AY_STR ;
  456.    }
  457. }
  458.  
  459. static void make_empty_table(A, type)
  460.    ARRAY A ;
  461.    int type ; /* AY_INT or AY_STR */
  462. {
  463.    size_t sz = (STARTING_HMASK+1)*sizeof(DUAL_LINK) ;
  464.    A->type = type ;
  465.    A->hmask = STARTING_HMASK ;
  466.    A->limit = hmask_to_limit(STARTING_HMASK) ;
  467.    A->ptr = memset(zmalloc(sz), 0, sz) ;
  468. }
  469.  
  470. static void convert_split_array_to_table(A)
  471.    ARRAY A ;
  472. {
  473.    CELL *cells = (CELL*) A->ptr ;
  474.    int i ; /* walks cells */
  475.    DUAL_LINK *table ;
  476.    int j ; /* walks table */
  477.    unsigned entry_limit = A->limit ;
  478.    A->hmask = STARTING_HMASK ;
  479.    A->limit = hmask_to_limit(STARTING_HMASK) ;
  480.    while(A->size > A->limit) {
  481.       A->hmask = (A->hmask<<1) + 1 ; /* double the size */
  482.       A->limit = hmask_to_limit(A->hmask) ;
  483.    }
  484.    {
  485.       size_t sz = (A->hmask+1)*sizeof(DUAL_LINK) ;
  486.       A->ptr = memset(zmalloc(sz), 0, sz) ;
  487.       table = (DUAL_LINK*) A->ptr ;
  488.    }
  489.  
  490.  
  491.    /* insert each cells[i] in the new hash table on an ilist */
  492.    for(i=0, j=1 ;i < A->size; i++) {
  493.       ANODE *p = ZMALLOC(ANODE) ;
  494.       p->sval = (STRING*) 0 ;
  495.       p->ival = i+1 ;
  496.       p->cell = cells[i] ;
  497.       p->ilink = table[j].ilink ;
  498.       table[j].ilink = p ;
  499.       j++ ; j &= A->hmask ;
  500.    }
  501.    A->type = AY_INT ;
  502.    zfree(cells, entry_limit*sizeof(CELL)) ;
  503. }
  504.  
  505. static void double_the_hash_table(A)
  506.    ARRAY A ;
  507. {
  508.    unsigned old_hmask = A->hmask ;
  509.    unsigned new_hmask = (old_hmask<<1)+1 ;
  510.    DUAL_LINK *table ;
  511.    A->ptr = zrealloc(A->ptr, (old_hmask+1)*sizeof(DUAL_LINK),
  512.                              (new_hmask+1)*sizeof(DUAL_LINK)) ;
  513.    table = (DUAL_LINK*) A->ptr ;
  514.    /* zero out the new part which is the back half */
  515.    memset(&table[old_hmask+1], 0, (old_hmask+1)*sizeof(DUAL_LINK)) ;
  516.  
  517.    if (A->type & AY_STR) {
  518.       int i ; /* index to old lists */
  519.       int j ; /* index to new lists */
  520.       ANODE *p ; /* walks an old list */
  521.       ANODE *q ; /* trails p for deletion */
  522.       ANODE *tail ; /* builds new list from the back */
  523.       ANODE dummy0, dummy1 ;
  524.       for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++) 
  525.          {
  526.             q = &dummy0 ;
  527.             q->slink = p = table[i].slink ;
  528.             tail = &dummy1 ;
  529.             while (p) {
  530.                if ((p->hval&new_hmask) != i) { /* move it */
  531.                   q->slink = p->slink ;
  532.                   tail = tail->slink = p ;
  533.                }
  534.                else q = p ;
  535.                p = q->slink ;
  536.             }
  537.             table[i].slink = dummy0.slink ;
  538.             tail->slink = (ANODE*) 0 ;
  539.             table[j].slink = dummy1.slink ;
  540.          }
  541.  
  542.    }
  543.  
  544.    if (A->type & AY_INT) {
  545.       int i ; /* index to old lists */
  546.       int j ; /* index to new lists */
  547.       ANODE *p ; /* walks an old list */
  548.       ANODE *q ; /* trails p for deletion */
  549.       ANODE *tail ; /* builds new list from the back */
  550.       ANODE dummy0, dummy1 ;
  551.       for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++) 
  552.          {
  553.             q = &dummy0 ;
  554.             q->ilink = p = table[i].ilink ;
  555.             tail = &dummy1 ;
  556.             while (p) {
  557.                if ((p->ival&new_hmask) != i) { /* move it */
  558.                   q->ilink = p->ilink ;
  559.                   tail = tail->ilink = p ;
  560.                }
  561.                else q = p ;
  562.                p = q->ilink ;
  563.             }
  564.             table[i].ilink = dummy0.ilink ;
  565.             tail->ilink = (ANODE*) 0 ;
  566.             table[j].ilink = dummy1.ilink ;
  567.          }
  568.  
  569.    }
  570.  
  571.    A->hmask = new_hmask ;
  572.    A->limit = hmask_to_limit(new_hmask) ;
  573. }
  574.  
  575.  
  576. static unsigned ahash(sval)
  577.    STRING* sval ;
  578. {
  579.    unsigned sum1 = sval->len ;
  580.    unsigned sum2 = sum1 ;
  581.    unsigned char *p , *q ;
  582.    if (sum1 <= 10) {
  583.       for(p=(unsigned char*)sval->str; *p ; p++) {
  584.          sum1 += sum1 + *p ;
  585.          sum2 += sum1 ;
  586.       }
  587.    }
  588.    else {
  589.       int cnt = 5 ;
  590.       p = (unsigned char*)sval->str ; /* p starts at the front */
  591.       q = (unsigned char*)sval->str + (sum1-1) ; /* q starts at the back */
  592.       while( cnt ) {
  593.          cnt-- ;
  594.          sum1 += sum1 + *p ;
  595.          sum2 += sum1 ;
  596.          sum1 += sum1 + *q ;
  597.          sum2 += sum1 ;
  598.          p++ ; q-- ;
  599.       }
  600.    }
  601.    return sum2 ;
  602. }
  603.  
  604.  
  605.  
  606.