array.c

   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                                         {
 116                                          if (ival >=1 && ival <= A->size) convert_split_array_to_table(A) ;
 117                                          else return ; /* ival not in range */
 118                                         }
 119                                       ap = find_by_ival(A, ival, NO_CREATE) ;
 120                                       if (ap) { /* remove from the front of the ilist */
 121                                          DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
 122                                          table[ap->ival & A->hmask].ilink = ap->ilink ;
 123                                          if (ap->sval) {
 124                                             ANODE *p, *q = 0 ;
 125                                             int index = ap->hval & A->hmask ;
 126                                             p = table[index].slink ;
 127                                             while(p != ap) { q = p ; p = q->slink ; }
 128                                             if (q) q->slink = p->slink ;
 129                                             else table[index].slink = p->slink ;
 130                                             free_STRING(ap->sval) ;
 131                                          }
 132
 133                                          cell_destroy(&ap->cell) ;
 134                                          ZFREE(ap) ;
 135                                          if (--A->size == 0) array_clear(A) ;
 136
 137
 138                                       }
 139                                       return ;
 140                                    }
 141
 142             else { /* get the string value */
 143                char buff[260] ;
 144                STRING *sval ;
 145                sprintf(buff, string(CONVFMT)->str, d) ;
 146                sval = new_STRING(buff) ;
 147                ap = find_by_sval(A, sval, NO_CREATE) ;
 148                free_STRING(sval) ;
 149             }
 150          }
 151          break ;
 152       case C_NOINIT :
 153          ap = find_by_sval(A, &null_str, NO_CREATE) ;
 154          break ;
 155       default :
 156          ap = find_by_sval(A, string(cp), NO_CREATE) ;
 157          break ;
 158    }
 159    if (ap) { /* remove from the front of the slist */
 160       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
 161       table[ap->hval&A->hmask].slink = ap->slink ;
 162       if (ap->ival != NOT_AN_IVALUE) {
 163          ANODE *p, *q = 0 ;
 164          int index = ap->ival & A->hmask ;
 165          p = table[index].ilink ;
 166          while(p != ap) { q = p ; p = q->ilink ; }
 167          if (q) q->ilink = p->ilink ;
 168          else table[index].ilink = p->ilink ;
 169       }
 170
 171       free_STRING(ap->sval) ;
 172       cell_destroy(&ap->cell) ;
 173       ZFREE(ap) ;
 174       if (--A->size == 0) array_clear(A) ;
 175
 176
 177    }
 178 }
 179
 180 void array_load(A, cnt)
 181    ARRAY A ;
 182    int cnt ;
 183 {
 184    CELL *cells ; /* storage for A[1..cnt] */
 185    int i ;  /* index into cells[] */
 186    if (A->type != AY_SPLIT || A->limit < cnt) {
 187       array_clear(A) ;
 188       A->limit = (cnt&~3)+4 ;
 189       A->ptr = zmalloc(A->limit*sizeof(CELL)) ;
 190       A->type = AY_SPLIT ;
 191    }
 192    else
 193       for(i=0;i < A->size; i++)  cell_destroy((CELL*)A->ptr+i) ;
 194
 195    cells = (CELL*) A->ptr ;
 196    A->size = cnt ;
 197    if (cnt > MAX_SPLIT) {
 198       SPLIT_OV *p = split_ov_list ;
 199       SPLIT_OV *q ;
 200       split_ov_list = (SPLIT_OV*) 0 ;
 201       i = MAX_SPLIT ;
 202       while( p ) {
 203          cells[i].type = C_MBSTRN ;
 204          cells[i].ptr = (PTR) p->sval ;
 205          q = p ; p = q->link ; ZFREE(q) ;
 206          i++ ;
 207       }
 208       cnt = MAX_SPLIT ;
 209    }
 210
 211    for(i=0;i < cnt; i++) {
 212       cells[i].type = C_MBSTRN ;
 213       cells[i].ptr = split_buff[i] ;
 214    }
 215 }
 216
 217 void array_clear(A)
 218    ARRAY A ;
 219 {
 220    int i ;
 221    ANODE *p, *q ;
 222    if (A->type == AY_SPLIT) {
 223       for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
 224       zfree(A->ptr, A->limit * sizeof(CELL)) ;
 225    }
 226    else if (A->type & AY_STR) {
 227       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
 228       for(i=0;i <= A->hmask; i++) {
 229          p = table[i].slink ;
 230          while(p) {
 231             q = p ; p = q->slink ;
 232             free_STRING(q->sval) ;
 233             cell_destroy(&q->cell) ;
 234             ZFREE(q) ;
 235          }
 236       }
 237       zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
 238    }
 239    else if (A->type & AY_INT) {
 240       DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
 241       for(i=0;i <= A->hmask; i++) {
 242          p = table[i].ilink ;
 243          while(p) {
 244             q = p ; p = q->ilink ;
 245             cell_destroy(&q->cell) ;
 246             ZFREE(q) ;
 247          }
 248       }
 249       zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
 250    }
 251    memset(A, 0, sizeof(*A)) ;
 252 }
 253
 254
 255
 256 STRING** array_loop_vector(A, sizep)
 257    ARRAY A ;
 258    unsigned *sizep ;
 259 {
 260    STRING** ret ;
 261    *sizep = A->size ;
 262    if (A->size > 0) {
 263       if (!(A->type & AY_STR)) add_string_associations(A) ;
 264       ret = (STRING**) zmalloc(A->size*sizeof(STRING*)) ;
 265       {
 266          int r = 0 ; /* indexes ret */
 267          DUAL_LINK* table = (DUAL_LINK*) A->ptr ;
 268          int i ; /* indexes table */
 269          ANODE *p ; /* walks slists */
 270          for(i=0;i <= A->hmask; i++) {
 271             for(p = table[i].slink; p ; p = p->slink) {
 272                ret[r++] = p->sval ;
 273                p->sval->ref_cnt++ ;
 274             }
 275          }
 276       }
 277
 278       return ret ;
 279    }
 280    else return (STRING**) 0 ;
 281 }
 282
 283 CELL *array_cat(sp, cnt)
 284    CELL *sp ;
 285    int cnt ;
 286 {
 287    CELL *p ;  /* walks the eval stack */
 288    CELL subsep ;  /* local copy of SUBSEP */
 289    unsigned subsep_len ; /* string length of subsep_str */
 290    char *subsep_str ;
 291
 292    unsigned total_len ;  /* length of cat'ed expression */
 293    CELL *top ;   /* value of sp at entry */
 294    char *target ;  /* build cat'ed char* here */
 295    STRING *sval ;  /* build cat'ed STRING here */
 296    cellcpy(&subsep, SUBSEP) ;
 297    if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
 298    subsep_len = string(&subsep)->len ;
 299    subsep_str = string(&subsep)->str ;
 300
 301    top = sp ; sp -= (cnt-1) ;
 302
 303    total_len = (cnt-1)*subsep_len ;
 304    for(p = sp ; p <= top ; p++) {
 305       if ( p->type < C_STRING ) cast1_to_s(p) ;
 306       total_len += string(p)->len ;
 307    }
 308
 309    sval = new_STRING0(total_len) ;
 310    target = sval->str ;
 311    for(p = sp ; p < top ; p++) {
 312       memcpy(target, string(p)->str, string(p)->len) ;
 313       target += string(p)->len ;
 314       memcpy(target, subsep_str, subsep_len) ;
 315       target += subsep_len ;
 316    }
 317    /* now p == top */
 318    memcpy(target, string(p)->str, string(p)->len) ;
 319
 320    for(p = sp; p <= top ; p++) free_STRING(string(p)) ;
 321    free_STRING(string(&subsep)) ;
 322    /* set contents of sp , sp->type > C_STRING is possible so reset */
 323    sp->type = C_STRING ;
 324    sp->ptr = (PTR) sval ;
 325    return sp ;
 326
 327 }
 328
 329 static ANODE* find_by_ival(A, ival, create_flag)
 330    ARRAY A ;
 331    Int ival ;
 332    int create_flag ;
 333 {
 334    DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
 335    unsigned index = ival & A->hmask ;
 336    ANODE *p = table[index].ilink ; /* walks ilist */
 337    ANODE *q = (ANODE*) 0 ; /* trails p */
 338    while(1) {
 339       if (!p) {
 340           /* search failed */
 341           if (A->type & AY_STR) {
 342              /* need to search by string */
 343              char buff[256] ;
 344              STRING *sval ;
 345              sprintf(buff, INT_FMT, ival) ;
 346              sval = new_STRING(buff) ;
 347              p = find_by_sval(A, sval, create_flag) ;
 348              free_STRING(sval) ;
 349              if (!p) return (ANODE*) 0 ;
 350           }
 351           else if (create_flag) {
 352              p = ZMALLOC(ANODE) ;
 353              p->sval = (STRING*) 0 ;
 354              p->cell.type = C_NOINIT ;
 355              if (++A->size > A->limit) {
 356                 double_the_hash_table(A) ; /* changes table, may change index */
 357                 table = (DUAL_LINK*) A->ptr ;
 358                 index = A->hmask & ival ;
 359              }
 360           }
 361           else return (ANODE*) 0 ;
 362           p->ival = ival ;
 363           A->type |= AY_INT ;
 364
 365           break ;
 366       }
 367       else if (p->ival == ival) {
 368          /* found it, now move to the front */
 369          if (!q) /* already at the front */
 370             return p ;
 371          /* delete for insertion at the front */
 372          q->ilink = p->ilink ;
 373          break ;
 374       }
 375       q = p ; p = q->ilink ;
 376    }
 377    /* insert at the front */
 378    p->ilink = table[index].ilink ;
 379    table[index].ilink = p ;
 380    return p ;
 381 }
 382
 383 static ANODE* find_by_sval(A, sval, create_flag)
 384    ARRAY A ;
 385    STRING *sval ;
 386    int create_flag ;
 387 {
 388    unsigned hval = ahash(sval) ;
 389    char *str = sval->str ;
 390    DUAL_LINK *table ;
 391    int index ;
 392    ANODE *p ;  /* walks list */
 393    ANODE *q = (ANODE*) 0 ; /* trails p */
 394    if (! (A->type & AY_STR)) add_string_associations(A) ;
 395    table = (DUAL_LINK*) A->ptr ;
 396    index = hval & A->hmask ;
 397    p = table[index].slink ;
 398    while(1) {
 399       if (!p)  {
 400          if (create_flag) {
 401             {
 402                p = ZMALLOC(ANODE) ;
 403                p->sval = sval ;
 404                sval->ref_cnt++ ;
 405                p->ival = NOT_AN_IVALUE ;
 406                p->hval = hval ;
 407                p->cell.type = C_NOINIT ;
 408                if (++A->size > A->limit) {
 409                   double_the_hash_table(A) ; /* changes table, may change index */
 410                   table = (DUAL_LINK*) A->ptr ;
 411                   index = hval & A->hmask ;
 412                }
 413             }
 414
 415             break ;
 416          }
 417          else return (ANODE*) 0 ;
 418       }
 419       else if (p->hval == hval && strcmp(p->sval->str,str) == 0 ) {
 420          /* found */
 421          if (!q) /* already at the front */
 422             return p ;
 423          else { /* delete for move to the front */
 424             q->slink = p->slink ;
 425             break ;
 426          }
 427       }
 428       q = p ; p = q->slink ;
 429    }
 430    p->slink = table[index].slink ;
 431    table[index].slink = p ;
 432    return p ;
 433 }
 434
 435 static void add_string_associations(A)
 436    ARRAY A ;
 437 {
 438    if (A->type == AY_NULL) make_empty_table(A, AY_STR) ;
 439    else {
 440       DUAL_LINK *table ;
 441       int i ; /* walks table */
 442       ANODE *p ; /* walks ilist */
 443       char buff[256] ;
 444       if (A->type == AY_SPLIT) convert_split_array_to_table(A) ;
 445       table = (DUAL_LINK*) A->ptr ;
 446       for(i=0;i <= A->hmask; i++) {
 447          p = table[i].ilink ;
 448          while(p) {
 449             sprintf(buff, INT_FMT, p->ival) ;
 450             p->sval = new_STRING(buff) ;
 451             p->hval = ahash(p->sval) ;
 452             p->slink = table[A->hmask&p->hval].slink ;
 453             table[A->hmask&p->hval].slink = p ;
 454             p = p->ilink ;
 455          }
 456       }
 457       A->type |= AY_STR ;
 458    }
 459 }
 460
 461 static void make_empty_table(A, type)
 462    ARRAY A ;
 463    int type ; /* AY_INT or AY_STR */
 464 {
 465    size_t sz = (STARTING_HMASK+1)*sizeof(DUAL_LINK) ;
 466    A->type = type ;
 467    A->hmask = STARTING_HMASK ;
 468    A->limit = hmask_to_limit(STARTING_HMASK) ;
 469    A->ptr = memset(zmalloc(sz), 0, sz) ;
 470 }
 471
 472 static void convert_split_array_to_table(A)
 473    ARRAY A ;
 474 {
 475    CELL *cells = (CELL*) A->ptr ;
 476    int i ; /* walks cells */
 477    DUAL_LINK *table ;
 478    int j ; /* walks table */
 479    unsigned entry_limit = A->limit ;
 480    A->hmask = STARTING_HMASK ;
 481    A->limit = hmask_to_limit(STARTING_HMASK) ;
 482    while(A->size > A->limit) {
 483       A->hmask = (A->hmask<<1) + 1 ; /* double the size */
 484       A->limit = hmask_to_limit(A->hmask) ;
 485    }
 486    {
 487       size_t sz = (A->hmask+1)*sizeof(DUAL_LINK) ;
 488       A->ptr = memset(zmalloc(sz), 0, sz) ;
 489       table = (DUAL_LINK*) A->ptr ;
 490    }
 491
 492
 493    /* insert each cells[i] in the new hash table on an ilist */
 494    for(i=0, j=1 ;i < A->size; i++) {
 495       ANODE *p = ZMALLOC(ANODE) ;
 496       p->sval = (STRING*) 0 ;
 497       p->ival = i+1 ;
 498       p->cell = cells[i] ;
 499       p->ilink = table[j].ilink ;
 500       table[j].ilink = p ;
 501       j++ ; j &= A->hmask ;
 502    }
 503    A->type = AY_INT ;
 504    zfree(cells, entry_limit*sizeof(CELL)) ;
 505 }
 506
 507 static void double_the_hash_table(A)
 508    ARRAY A ;
 509 {
 510    unsigned old_hmask = A->hmask ;
 511    unsigned new_hmask = (old_hmask<<1)+1 ;
 512    DUAL_LINK *table ;
 513    A->ptr = zrealloc(A->ptr, (old_hmask+1)*sizeof(DUAL_LINK),
 514                              (new_hmask+1)*sizeof(DUAL_LINK)) ;
 515    table = (DUAL_LINK*) A->ptr ;
 516    /* zero out the new part which is the back half */
 517    memset(&table[old_hmask+1], 0, (old_hmask+1)*sizeof(DUAL_LINK)) ;
 518
 519    if (A->type & AY_STR) {
 520       int i ; /* index to old lists */
 521       int j ; /* index to new lists */
 522       ANODE *p ; /* walks an old list */
 523       ANODE *q ; /* trails p for deletion */
 524       ANODE *tail ; /* builds new list from the back */
 525       ANODE dummy0, dummy1 ;
 526       for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
 527          {
 528             q = &dummy0 ;
 529             q->slink = p = table[i].slink ;
 530             tail = &dummy1 ;
 531             while (p) {
 532                if ((p->hval&new_hmask) != i) { /* move it */
 533                   q->slink = p->slink ;
 534                   tail = tail->slink = p ;
 535                }
 536                else q = p ;
 537                p = q->slink ;
 538             }
 539             table[i].slink = dummy0.slink ;
 540             tail->slink = (ANODE*) 0 ;
 541             table[j].slink = dummy1.slink ;
 542          }
 543
 544    }
 545
 546    if (A->type & AY_INT) {
 547       int i ; /* index to old lists */
 548       int j ; /* index to new lists */
 549       ANODE *p ; /* walks an old list */
 550       ANODE *q ; /* trails p for deletion */
 551       ANODE *tail ; /* builds new list from the back */
 552       ANODE dummy0, dummy1 ;
 553       for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
 554          {
 555             q = &dummy0 ;
 556             q->ilink = p = table[i].ilink ;
 557             tail = &dummy1 ;
 558             while (p) {
 559                if ((p->ival&new_hmask) != i) { /* move it */
 560                   q->ilink = p->ilink ;
 561                   tail = tail->ilink = p ;
 562                }
 563                else q = p ;
 564                p = q->ilink ;
 565             }
 566             table[i].ilink = dummy0.ilink ;
 567             tail->ilink = (ANODE*) 0 ;
 568             table[j].ilink = dummy1.ilink ;
 569          }
 570
 571    }
 572
 573    A->hmask = new_hmask ;
 574    A->limit = hmask_to_limit(new_hmask) ;
 575 }
 576
 577
 578 static unsigned ahash(sval)
 579    STRING* sval ;
 580 {
 581    unsigned sum1 = sval->len ;
 582    unsigned sum2 = sum1 ;
 583    unsigned char *p , *q ;
 584    if (sum1 <= 10) {
 585       for(p=(unsigned char*)sval->str; *p ; p++) {
 586          sum1 += sum1 + *p ;
 587          sum2 += sum1 ;
 588       }
 589    }
 590    else {
 591       int cnt = 5 ;
 592       p = (unsigned char*)sval->str ; /* p starts at the front */
 593       q = (unsigned char*)sval->str + (sum1-1) ; /* q starts at the back */
 594       while( cnt ) {
 595          cnt-- ;
 596          sum1 += sum1 + *p ;
 597          sum2 += sum1 ;
 598          sum1 += sum1 + *q ;
 599          sum2 += sum1 ;
 600          p++ ; q-- ;
 601       }
 602    }
 603    return sum2 ;
 604 }
 605
 606
 607