array.c

   1 /*
   2  * array.c - functions to create, destroy, access, and manipulate arrays
   3  *           of strings.
   4  *
   5  * Arrays are sparse doubly-linked lists.  An element's index is stored
   6  * with it.
   7  *
   8  * Chet Ramey
   9  * chet@ins.cwru.edu
  10  */
  11
  12 /* Copyright (C) 1997-2009 Free Software Foundation, Inc.
  13
  14    This file is part of GNU Bash, the Bourne Again SHell.
  15
  16    Bash is free software: you can redistribute it and/or modify
  17    it under the terms of the GNU General Public License as published by
  18    the Free Software Foundation, either version 3 of the License, or
  19    (at your option) any later version.
  20
  21    Bash is distributed in the hope that it will be useful,
  22    but WITHOUT ANY WARRANTY; without even the implied warranty of
  23    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24    GNU General Public License for more details.
  25
  26    You should have received a copy of the GNU General Public License
  27    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  28 */
  29
  30 #include "config.h"
  31
  32 #if defined (ARRAY_VARS)
  33
  34 #if defined (HAVE_UNISTD_H)
  35 #  ifdef _MINIX
  36 #    include <sys/types.h>
  37 #  endif
  38 #  include <unistd.h>
  39 #endif
  40
  41 #include <stdio.h>
  42 #include "bashansi.h"
  43
  44 #include "shell.h"
  45 #include "array.h"
  46 #include "builtins/common.h"
  47
  48 #define ADD_BEFORE(ae, new) \
  49         do { \
  50                 ae->prev->next = new; \
  51                 new->prev = ae->prev; \
  52                 ae->prev = new; \
  53                 new->next = ae; \
  54         } while(0)
  55
  56 static char *array_to_string_internal __P((ARRAY_ELEMENT *, ARRAY_ELEMENT *, char *, int));
  57
  58 static ARRAY *lastarray = 0;
  59 static ARRAY_ELEMENT *lastref = 0;
  60
  61 #define IS_LASTREF(a)   ((a) == lastarray)
  62
  63 #define INVALIDATE_LASTREF(a) \
  64 do { \
  65         if ((a) == lastarray) { \
  66                 lastarray = 0; \
  67                 lastref = 0; \
  68         } \
  69 } while (0)
  70
  71 #define SET_LASTREF(a, e) \
  72 do { \
  73         lastarray = (a); \
  74         lastref = (e); \
  75 } while (0)
  76
  77 #define UNSET_LASTREF() \
  78 do { \
  79         lastarray = 0; \
  80         lastref = 0; \
  81 } while (0)
  82
  83 ARRAY *
  84 array_create()
  85 {
  86         ARRAY   *r;
  87         ARRAY_ELEMENT   *head;
  88
  89         r =(ARRAY *)xmalloc(sizeof(ARRAY));
  90         r->type = array_indexed;
  91         r->max_index = -1;
  92         r->num_elements = 0;
  93         head = array_create_element(-1, (char *)NULL);  /* dummy head */
  94         head->prev = head->next = head;
  95         r->head = head;
  96         return(r);
  97 }
  98
  99 void
 100 array_flush (a)
 101 ARRAY   *a;
 102 {
 103         register ARRAY_ELEMENT *r, *r1;
 104
 105         if (a == 0)
 106                 return;
 107         for (r = element_forw(a->head); r != a->head; ) {
 108                 r1 = element_forw(r);
 109                 array_dispose_element(r);
 110                 r = r1;
 111         }
 112         a->head->next = a->head->prev = a->head;
 113         a->max_index = -1;
 114         a->num_elements = 0;
 115         INVALIDATE_LASTREF(a);
 116 }
 117
 118 void
 119 array_dispose(a)
 120 ARRAY   *a;
 121 {
 122         if (a == 0)
 123                 return;
 124         array_flush (a);
 125         array_dispose_element(a->head);
 126         free(a);
 127 }
 128
 129 ARRAY *
 130 array_copy(a)
 131 ARRAY   *a;
 132 {
 133         ARRAY   *a1;
 134         ARRAY_ELEMENT   *ae, *new;
 135
 136         if (a == 0)
 137                 return((ARRAY *) NULL);
 138         a1 = array_create();
 139         a1->type = a->type;
 140         a1->max_index = a->max_index;
 141         a1->num_elements = a->num_elements;
 142         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 143                 new = array_create_element(element_index(ae), element_value(ae));
 144                 ADD_BEFORE(a1->head, new);
 145         }
 146         return(a1);
 147 }
 148
 149 /*
 150  * Make and return a new array composed of the elements in array A from
 151  * S to E, inclusive.
 152  */
 153 ARRAY *
 154 array_slice(array, s, e)
 155 ARRAY           *array;
 156 ARRAY_ELEMENT   *s, *e;
 157 {
 158         ARRAY   *a;
 159         ARRAY_ELEMENT *p, *n;
 160         int     i;
 161         arrayind_t mi;
 162
 163         a = array_create ();
 164         a->type = array->type;
 165
 166         for (mi = 0, p = s, i = 0; p != e; p = element_forw(p), i++) {
 167                 n = array_create_element (element_index(p), element_value(p));
 168                 ADD_BEFORE(a->head, n);
 169                 mi = element_index(n);
 170         }
 171         a->num_elements = i;
 172         a->max_index = mi;
 173         return a;
 174 }
 175
 176 /*
 177  * Walk the array, calling FUNC once for each element, with the array
 178  * element as the argument.
 179  */
 180 void
 181 array_walk(a, func, udata)
 182 ARRAY   *a;
 183 sh_ae_map_func_t *func;
 184 void    *udata;
 185 {
 186         register ARRAY_ELEMENT *ae;
 187
 188         if (a == 0 || array_empty(a))
 189                 return;
 190         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 191                 if ((*func)(ae, udata) < 0)
 192                         return;
 193 }
 194
 195 /*
 196  * Shift the array A N elements to the left.  Delete the first N elements
 197  * and subtract N from the indices of the remaining elements.  If FLAGS
 198  * does not include AS_DISPOSE, this returns a singly-linked null-terminated
 199  * list of elements so the caller can dispose of the chain.  If FLAGS
 200  * includes AS_DISPOSE, this function disposes of the shifted-out elements
 201  * and returns NULL.
 202  */
 203 ARRAY_ELEMENT *
 204 array_shift(a, n, flags)
 205 ARRAY   *a;
 206 int     n, flags;
 207 {
 208         register ARRAY_ELEMENT *ae, *ret;
 209         register int i;
 210
 211         if (a == 0 || array_empty(a) || n <= 0)
 212                 return ((ARRAY_ELEMENT *)NULL);
 213
 214         INVALIDATE_LASTREF(a);
 215         for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
 216                 ;
 217         if (ae == a->head) {
 218                 /* Easy case; shifting out all of the elements */
 219                 if (flags & AS_DISPOSE) {
 220                         array_flush (a);
 221                         return ((ARRAY_ELEMENT *)NULL);
 222                 }
 223                 for (ae = ret; element_forw(ae) != a->head; ae = element_forw(ae))
 224                         ;
 225                 element_forw(ae) = (ARRAY_ELEMENT *)NULL;
 226                 a->head->next = a->head->prev = a->head;
 227                 a->max_index = -1;
 228                 a->num_elements = 0;
 229                 return ret;
 230         }
 231         /*
 232          * ae now points to the list of elements we want to retain.
 233          * ret points to the list we want to either destroy or return.
 234          */
 235         ae->prev->next = (ARRAY_ELEMENT *)NULL;         /* null-terminate RET */
 236
 237         a->head->next = ae;             /* slice RET out of the array */
 238         ae->prev = a->head;
 239
 240         for ( ; ae != a->head; ae = element_forw(ae))
 241                 element_index(ae) -= n; /* renumber retained indices */
 242
 243         a->num_elements -= n;           /* modify bookkeeping information */
 244         a->max_index = element_index(a->head->prev);
 245
 246         if (flags & AS_DISPOSE) {
 247                 for (ae = ret; ae; ) {
 248                         ret = element_forw(ae);
 249                         array_dispose_element(ae);
 250                         ae = ret;
 251                 }
 252                 return ((ARRAY_ELEMENT *)NULL);
 253         }
 254
 255         return ret;
 256 }
 257
 258 /*
 259  * Shift array A right N indices.  If S is non-null, it becomes the value of
 260  * the new element 0.  Returns the number of elements in the array after the
 261  * shift.
 262  */
 263 int
 264 array_rshift (a, n, s)
 265 ARRAY   *a;
 266 int     n;
 267 char    *s;
 268 {
 269         register ARRAY_ELEMENT  *ae, *new;
 270
 271         if (a == 0 || (array_empty(a) && s == 0))
 272                 return 0;
 273         else if (n <= 0)
 274                 return (a->num_elements);
 275
 276         ae = element_forw(a->head);
 277         if (s) {
 278                 new = array_create_element(0, s);
 279                 ADD_BEFORE(ae, new);
 280                 a->num_elements++;
 281                 if (array_num_elements(a) == 1) {       /* array was empty */
 282                         a->max_index = 0;
 283                         return 1;
 284                 }
 285         }
 286
 287         /*
 288          * Renumber all elements in the array except the one we just added.
 289          */
 290         for ( ; ae != a->head; ae = element_forw(ae))
 291                 element_index(ae) += n;
 292
 293         a->max_index = element_index(a->head->prev);
 294
 295         INVALIDATE_LASTREF(a);
 296         return (a->num_elements);
 297 }
 298
 299 ARRAY_ELEMENT *
 300 array_unshift_element(a)
 301 ARRAY   *a;
 302 {
 303         return (array_shift (a, 1, 0));
 304 }
 305
 306 int
 307 array_shift_element(a, v)
 308 ARRAY   *a;
 309 char    *v;
 310 {
 311         return (array_rshift (a, 1, v));
 312 }
 313
 314 ARRAY *
 315 array_quote(array)
 316 ARRAY   *array;
 317 {
 318         ARRAY_ELEMENT   *a;
 319         char    *t;
 320
 321         if (array == 0 || array_head(array) == 0 || array_empty(array))
 322                 return (ARRAY *)NULL;
 323         for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
 324                 t = quote_string (a->value);
 325                 FREE(a->value);
 326                 a->value = t;
 327         }
 328         return array;
 329 }
 330
 331 ARRAY *
 332 array_quote_escapes(array)
 333 ARRAY   *array;
 334 {
 335         ARRAY_ELEMENT   *a;
 336         char    *t;
 337
 338         if (array == 0 || array_head(array) == 0 || array_empty(array))
 339                 return (ARRAY *)NULL;
 340         for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
 341                 t = quote_escapes (a->value);
 342                 FREE(a->value);
 343                 a->value = t;
 344         }
 345         return array;
 346 }
 347
 348 ARRAY *
 349 array_dequote(array)
 350 ARRAY   *array;
 351 {
 352         ARRAY_ELEMENT   *a;
 353         char    *t;
 354
 355         if (array == 0 || array_head(array) == 0 || array_empty(array))
 356                 return (ARRAY *)NULL;
 357         for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
 358                 t = dequote_string (a->value);
 359                 FREE(a->value);
 360                 a->value = t;
 361         }
 362         return array;
 363 }
 364
 365 ARRAY *
 366 array_dequote_escapes(array)
 367 ARRAY   *array;
 368 {
 369         ARRAY_ELEMENT   *a;
 370         char    *t;
 371
 372         if (array == 0 || array_head(array) == 0 || array_empty(array))
 373                 return (ARRAY *)NULL;
 374         for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
 375                 t = dequote_escapes (a->value);
 376                 FREE(a->value);
 377                 a->value = t;
 378         }
 379         return array;
 380 }
 381
 382 ARRAY *
 383 array_remove_quoted_nulls(array)
 384 ARRAY   *array;
 385 {
 386         ARRAY_ELEMENT   *a;
 387         char    *t;
 388
 389         if (array == 0 || array_head(array) == 0 || array_empty(array))
 390                 return (ARRAY *)NULL;
 391         for (a = element_forw(array->head); a != array->head; a = element_forw(a))
 392                 a->value = remove_quoted_nulls (a->value);
 393         return array;
 394 }
 395
 396 /*
 397  * Return a string whose elements are the members of array A beginning at
 398  * index START and spanning NELEM members.  Null elements are counted.
 399  * Since arrays are sparse, unset array elements are not counted.
 400  */
 401 char *
 402 array_subrange (a, start, nelem, starsub, quoted)
 403 ARRAY   *a;
 404 arrayind_t      start, nelem;
 405 int     starsub, quoted;
 406 {
 407         ARRAY           *a2;
 408         ARRAY_ELEMENT   *h, *p;
 409         arrayind_t      i;
 410         char            *ifs, *sifs, *t;
 411         int             slen;
 412
 413         p = a ? array_head (a) : 0;
 414         if (p == 0 || array_empty (a) || start > array_max_index(a))
 415                 return ((char *)NULL);
 416
 417         /*
 418          * Find element with index START.  If START corresponds to an unset
 419          * element (arrays can be sparse), use the first element whose index
 420          * is >= START.  If START is < 0, we count START indices back from
 421          * the end of A (not elements, even with sparse arrays -- START is an
 422          * index).
 423          */
 424         for (p = element_forw(p); p != array_head(a) && start > element_index(p); p = element_forw(p))
 425                 ;
 426
 427         if (p == a->head)
 428                 return ((char *)NULL);
 429
 430         /* Starting at P, take NELEM elements, inclusive. */
 431         for (i = 0, h = p; p != a->head && i < nelem; i++, p = element_forw(p))
 432                 ;
 433
 434         a2 = array_slice(a, h, p);
 435
 436         if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))
 437                 array_quote(a2);
 438         else
 439                 array_quote_escapes(a2);
 440
 441         if (starsub && (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))) {
 442                 /* ${array[*]} */
 443                 array_remove_quoted_nulls (a2);
 444                 sifs = ifs_firstchar ((int *)NULL);
 445                 t = array_to_string (a2, sifs, 0);
 446                 free (sifs);
 447         } else if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT)) {
 448                 /* ${array[@]} */
 449                 sifs = ifs_firstchar (&slen);
 450                 ifs = getifs ();
 451                 if (ifs == 0 || *ifs == 0) {
 452                         if (slen < 2)
 453                                 sifs = xrealloc(sifs, 2);
 454                         sifs[0] = ' ';
 455                         sifs[1] = '\0';
 456                 }
 457                 t = array_to_string (a2, sifs, 0);
 458                 free (sifs);
 459         } else
 460                 t = array_to_string (a2, " ", 0);
 461         array_dispose(a2);
 462
 463         return t;
 464 }
 465
 466 char *
 467 array_patsub (a, pat, rep, mflags)
 468 ARRAY   *a;
 469 char    *pat, *rep;
 470 int     mflags;
 471 {
 472         ARRAY           *a2;
 473         ARRAY_ELEMENT   *e;
 474         char    *t, *sifs, *ifs;
 475         int     slen;
 476
 477         if (a == 0 || array_head(a) == 0 || array_empty(a))
 478                 return ((char *)NULL);
 479
 480         a2 = array_copy(a);
 481         for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
 482                 t = pat_subst(element_value(e), pat, rep, mflags);
 483                 FREE(element_value(e));
 484                 e->value = t;
 485         }
 486
 487         if (mflags & MATCH_QUOTED)
 488                 array_quote(a2);
 489         else
 490                 array_quote_escapes(a2);
 491
 492         if (mflags & MATCH_STARSUB) {
 493                 array_remove_quoted_nulls (a2);
 494                 sifs = ifs_firstchar((int *)NULL);
 495                 t = array_to_string (a2, sifs, 0);
 496                 free(sifs);
 497         } else if (mflags & MATCH_QUOTED) {
 498                 /* ${array[@]} */
 499                 sifs = ifs_firstchar (&slen);
 500                 ifs = getifs ();
 501                 if (ifs == 0 || *ifs == 0) {
 502                         if (slen < 2)
 503                                 sifs = xrealloc (sifs, 2);
 504                         sifs[0] = ' ';
 505                         sifs[1] = '\0';
 506                 }
 507                 t = array_to_string (a2, sifs, 0);
 508                 free(sifs);
 509         } else
 510                 t = array_to_string (a2, " ", 0);
 511         array_dispose (a2);
 512
 513         return t;
 514 }
 515
 516 char *
 517 array_modcase (a, pat, modop, mflags)
 518 ARRAY   *a;
 519 char    *pat;
 520 int     modop;
 521 int     mflags;
 522 {
 523         ARRAY           *a2;
 524         ARRAY_ELEMENT   *e;
 525         char    *t, *sifs, *ifs;
 526         int     slen;
 527
 528         if (a == 0 || array_head(a) == 0 || array_empty(a))
 529                 return ((char *)NULL);
 530
 531         a2 = array_copy(a);
 532         for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
 533                 t = sh_modcase(element_value(e), pat, modop);
 534                 FREE(element_value(e));
 535                 e->value = t;
 536         }
 537
 538         if (mflags & MATCH_QUOTED)
 539                 array_quote(a2);
 540         else
 541                 array_quote_escapes(a2);
 542
 543         if (mflags & MATCH_STARSUB) {
 544                 array_remove_quoted_nulls (a2);
 545                 sifs = ifs_firstchar((int *)NULL);
 546                 t = array_to_string (a2, sifs, 0);
 547                 free(sifs);
 548         } else if (mflags & MATCH_QUOTED) {
 549                 /* ${array[@]} */
 550                 sifs = ifs_firstchar (&slen);
 551                 ifs = getifs ();
 552                 if (ifs == 0 || *ifs == 0) {
 553                         if (slen < 2)
 554                                 sifs = xrealloc (sifs, 2);
 555                         sifs[0] = ' ';
 556                         sifs[1] = '\0';
 557                 }
 558                 t = array_to_string (a2, sifs, 0);
 559                 free(sifs);
 560         } else
 561                 t = array_to_string (a2, " ", 0);
 562         array_dispose (a2);
 563
 564         return t;
 565 }
 566 /*
 567  * Allocate and return a new array element with index INDEX and value
 568  * VALUE.
 569  */
 570 ARRAY_ELEMENT *
 571 array_create_element(indx, value)
 572 arrayind_t      indx;
 573 char    *value;
 574 {
 575         ARRAY_ELEMENT *r;
 576
 577         r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
 578         r->ind = indx;
 579         r->value = value ? savestring(value) : (char *)NULL;
 580         r->next = r->prev = (ARRAY_ELEMENT *) NULL;
 581         return(r);
 582 }
 583
 584 #ifdef INCLUDE_UNUSED
 585 ARRAY_ELEMENT *
 586 array_copy_element(ae)
 587 ARRAY_ELEMENT   *ae;
 588 {
 589         return(ae ? array_create_element(element_index(ae), element_value(ae))
 590                   : (ARRAY_ELEMENT *) NULL);
 591 }
 592 #endif
 593
 594 void
 595 array_dispose_element(ae)
 596 ARRAY_ELEMENT   *ae;
 597 {
 598         if (ae) {
 599                 FREE(ae->value);
 600                 free(ae);
 601         }
 602 }
 603
 604 /*
 605  * Add a new element with index I and value V to array A (a[i] = v).
 606  */
 607 int
 608 array_insert(a, i, v)
 609 ARRAY   *a;
 610 arrayind_t      i;
 611 char    *v;
 612 {
 613         register ARRAY_ELEMENT *new, *ae;
 614
 615         if (a == 0)
 616                 return(-1);
 617         new = array_create_element(i, v);
 618         if (i > array_max_index(a)) {
 619                 /*
 620                  * Hook onto the end.  This also works for an empty array.
 621                  * Fast path for the common case of allocating arrays
 622                  * sequentially.
 623                  */
 624                 ADD_BEFORE(a->head, new);
 625                 a->max_index = i;
 626                 a->num_elements++;
 627                 SET_LASTREF(a, new);
 628                 return(0);
 629         }
 630         /*
 631          * Otherwise we search for the spot to insert it.
 632          */
 633         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 634                 if (element_index(ae) == i) {
 635                         /*
 636                          * Replacing an existing element.
 637                          */
 638                         array_dispose_element(new);
 639                         free(element_value(ae));
 640                         ae->value = v ? savestring(v) : (char *)NULL;
 641                         SET_LASTREF(a, ae);
 642                         return(0);
 643                 } else if (element_index(ae) > i) {
 644                         ADD_BEFORE(ae, new);
 645                         a->num_elements++;
 646                         SET_LASTREF(a, new);
 647                         return(0);
 648                 }
 649         }
 650         INVALIDATE_LASTREF(a);
 651         return (-1);            /* problem */
 652 }
 653
 654 /*
 655  * Delete the element with index I from array A and return it so the
 656  * caller can dispose of it.
 657  */
 658 ARRAY_ELEMENT *
 659 array_remove(a, i)
 660 ARRAY   *a;
 661 arrayind_t      i;
 662 {
 663         register ARRAY_ELEMENT *ae;
 664
 665         if (a == 0 || array_empty(a))
 666                 return((ARRAY_ELEMENT *) NULL);
 667         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 668                 if (element_index(ae) == i) {
 669                         ae->next->prev = ae->prev;
 670                         ae->prev->next = ae->next;
 671                         a->num_elements--;
 672                         if (i == array_max_index(a))
 673                                 a->max_index = element_index(ae->prev);
 674                         INVALIDATE_LASTREF(a);
 675                         return(ae);
 676                 }
 677         return((ARRAY_ELEMENT *) NULL);
 678 }
 679
 680 /*
 681  * Return the value of a[i].
 682  */
 683 char *
 684 array_reference(a, i)
 685 ARRAY   *a;
 686 arrayind_t      i;
 687 {
 688         register ARRAY_ELEMENT *ae;
 689
 690         if (a == 0 || array_empty(a))
 691                 return((char *) NULL);
 692         if (i > array_max_index(a))
 693                 return((char *)NULL);
 694         /* Keep roving pointer into array to optimize sequential access */
 695         if (lastref && IS_LASTREF(a))
 696                 ae = (i >= element_index(lastref)) ? lastref : element_forw(a->head);
 697         else
 698                 ae = element_forw(a->head);
 699         for ( ; ae != a->head; ae = element_forw(ae))
 700                 if (element_index(ae) == i) {
 701                         SET_LASTREF(a, ae);
 702                         return(element_value(ae));
 703                 }
 704         UNSET_LASTREF();
 705         return((char *) NULL);
 706 }
 707
 708 /* Convenience routines for the shell to translate to and from the form used
 709    by the rest of the code. */
 710
 711 WORD_LIST *
 712 array_to_word_list(a)
 713 ARRAY   *a;
 714 {
 715         WORD_LIST       *list;
 716         ARRAY_ELEMENT   *ae;
 717
 718         if (a == 0 || array_empty(a))
 719                 return((WORD_LIST *)NULL);
 720         list = (WORD_LIST *)NULL;
 721         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 722                 list = make_word_list (make_bare_word(element_value(ae)), list);
 723         return (REVERSE_LIST(list, WORD_LIST *));
 724 }
 725
 726 ARRAY *
 727 array_from_word_list (list)
 728 WORD_LIST       *list;
 729 {
 730         ARRAY   *a;
 731
 732         if (list == 0)
 733                 return((ARRAY *)NULL);
 734         a = array_create();
 735         return (array_assign_list (a, list));
 736 }
 737
 738 WORD_LIST *
 739 array_keys_to_word_list(a)
 740 ARRAY   *a;
 741 {
 742         WORD_LIST       *list;
 743         ARRAY_ELEMENT   *ae;
 744         char            *t;
 745
 746         if (a == 0 || array_empty(a))
 747                 return((WORD_LIST *)NULL);
 748         list = (WORD_LIST *)NULL;
 749         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 750                 t = itos(element_index(ae));
 751                 list = make_word_list (make_bare_word(t), list);
 752                 free(t);
 753         }
 754         return (REVERSE_LIST(list, WORD_LIST *));
 755 }
 756
 757 ARRAY *
 758 array_assign_list (array, list)
 759 ARRAY   *array;
 760 WORD_LIST       *list;
 761 {
 762         register WORD_LIST *l;
 763         register arrayind_t i;
 764
 765         for (l = list, i = 0; l; l = l->next, i++)
 766                 array_insert(array, i, l->word->word);
 767         return array;
 768 }
 769
 770 char **
 771 array_to_argv (a)
 772 ARRAY   *a;
 773 {
 774         char            **ret, *t;
 775         int             i;
 776         ARRAY_ELEMENT   *ae;
 777
 778         if (a == 0 || array_empty(a))
 779                 return ((char **)NULL);
 780         ret = strvec_create (array_num_elements (a) + 1);
 781         i = 0;
 782         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 783                 t = element_value (ae);
 784                 ret[i++] = t ? savestring (t) : (char *)NULL;
 785         }
 786         ret[i] = (char *)NULL;
 787         return (ret);
 788 }
 789
 790 /*
 791  * Return a string that is the concatenation of the elements in A from START
 792  * to END, separated by SEP.
 793  */
 794 static char *
 795 array_to_string_internal (start, end, sep, quoted)
 796 ARRAY_ELEMENT   *start, *end;
 797 char    *sep;
 798 int     quoted;
 799 {
 800         char    *result, *t;
 801         ARRAY_ELEMENT *ae;
 802         int     slen, rsize, rlen, reg;
 803
 804         if (start == end)       /* XXX - should not happen */
 805                 return ((char *)NULL);
 806
 807         slen = strlen(sep);
 808         result = NULL;
 809         for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
 810                 if (rsize == 0)
 811                         result = (char *)xmalloc (rsize = 64);
 812                 if (element_value(ae)) {
 813                         t = quoted ? quote_string(element_value(ae)) : element_value(ae);
 814                         reg = strlen(t);
 815                         RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
 816                                                 rsize, rsize);
 817                         strcpy(result + rlen, t);
 818                         rlen += reg;
 819                         if (quoted && t)
 820                                 free(t);
 821                         /*
 822                          * Add a separator only after non-null elements.
 823                          */
 824                         if (element_forw(ae) != end) {
 825                                 strcpy(result + rlen, sep);
 826                                 rlen += slen;
 827                         }
 828                 }
 829         }
 830         if (result)
 831           result[rlen] = '\0';  /* XXX */
 832         return(result);
 833 }
 834
 835 char *
 836 array_to_assign (a, quoted)
 837 ARRAY   *a;
 838 int     quoted;
 839 {
 840         char    *result, *valstr, *is;
 841         char    indstr[INT_STRLEN_BOUND(intmax_t) + 1];
 842         ARRAY_ELEMENT *ae;
 843         int     rsize, rlen, elen;
 844
 845         if (a == 0 || array_empty (a))
 846                 return((char *)NULL);
 847
 848         result = (char *)xmalloc (rsize = 128);
 849         result[0] = '(';
 850         rlen = 1;
 851
 852         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 853                 is = inttostr (element_index(ae), indstr, sizeof(indstr));
 854                 valstr = element_value (ae) ? sh_double_quote (element_value(ae))
 855                                             : (char *)NULL;
 856                 elen = STRLEN (is) + 8 + STRLEN (valstr);
 857                 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
 858
 859                 result[rlen++] = '[';
 860                 strcpy (result + rlen, is);
 861                 rlen += STRLEN (is);
 862                 result[rlen++] = ']';
 863                 result[rlen++] = '=';
 864                 if (valstr) {
 865                         strcpy (result + rlen, valstr);
 866                         rlen += STRLEN (valstr);
 867                 }
 868
 869                 if (element_forw(ae) != a->head)
 870                   result[rlen++] = ' ';
 871
 872                 FREE (valstr);
 873         }
 874         RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
 875         result[rlen++] = ')';
 876         result[rlen] = '\0';
 877         if (quoted) {
 878                 /* This is not as efficient as it could be... */
 879                 valstr = sh_single_quote (result);
 880                 free (result);
 881                 result = valstr;
 882         }
 883         return(result);
 884 }
 885
 886 char *
 887 array_to_string (a, sep, quoted)
 888 ARRAY   *a;
 889 char    *sep;
 890 int     quoted;
 891 {
 892         if (a == 0)
 893                 return((char *)NULL);
 894         if (array_empty(a))
 895                 return(savestring(""));
 896         return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
 897 }
 898
 899 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
 900 /*
 901  * Return an array consisting of elements in S, separated by SEP
 902  */
 903 ARRAY *
 904 array_from_string(s, sep)
 905 char    *s, *sep;
 906 {
 907         ARRAY   *a;
 908         WORD_LIST *w;
 909
 910         if (s == 0)
 911                 return((ARRAY *)NULL);
 912         w = list_string (s, sep, 0);
 913         if (w == 0)
 914                 return((ARRAY *)NULL);
 915         a = array_from_word_list (w);
 916         return (a);
 917 }
 918 #endif
 919
 920 #if defined (TEST_ARRAY)
 921 /*
 922  * To make a running version, compile -DTEST_ARRAY and link with:
 923  *      xmalloc.o syntax.o lib/malloc/libmalloc.a lib/sh/libsh.a
 924  */
 925 int interrupt_immediately = 0;
 926
 927 int
 928 signal_is_trapped(s)
 929 int     s;
 930 {
 931         return 0;
 932 }
 933
 934 void
 935 fatal_error(const char *s, ...)
 936 {
 937         fprintf(stderr, "array_test: fatal memory error\n");
 938         abort();
 939 }
 940
 941 void
 942 programming_error(const char *s, ...)
 943 {
 944         fprintf(stderr, "array_test: fatal programming error\n");
 945         abort();
 946 }
 947
 948 WORD_DESC *
 949 make_bare_word (s)
 950 const char      *s;
 951 {
 952         WORD_DESC *w;
 953
 954         w = (WORD_DESC *)xmalloc(sizeof(WORD_DESC));
 955         w->word = s ? savestring(s) : savestring ("");
 956         w->flags = 0;
 957         return w;
 958 }
 959
 960 WORD_LIST *
 961 make_word_list(x, l)
 962 WORD_DESC       *x;
 963 WORD_LIST       *l;
 964 {
 965         WORD_LIST *w;
 966
 967         w = (WORD_LIST *)xmalloc(sizeof(WORD_LIST));
 968         w->word = x;
 969         w->next = l;
 970         return w;
 971 }
 972
 973 WORD_LIST *
 974 list_string(s, t, i)
 975 char    *s, *t;
 976 int     i;
 977 {
 978         char    *r, *a;
 979         WORD_LIST       *wl;
 980
 981         if (s == 0)
 982                 return (WORD_LIST *)NULL;
 983         r = savestring(s);
 984         wl = (WORD_LIST *)NULL;
 985         a = strtok(r, t);
 986         while (a) {
 987                 wl = make_word_list (make_bare_word(a), wl);
 988                 a = strtok((char *)NULL, t);
 989         }
 990         return (REVERSE_LIST (wl, WORD_LIST *));
 991 }
 992
 993 GENERIC_LIST *
 994 list_reverse (list)
 995 GENERIC_LIST    *list;
 996 {
 997         register GENERIC_LIST *next, *prev;
 998
 999         for (prev = 0; list; ) {
1000                 next = list->next;
1001                 list->next = prev;
1002                 prev = list;
1003                 list = next;
1004         }
1005         return prev;
1006 }
1007
1008 char *
1009 pat_subst(s, t, u, i)
1010 char    *s, *t, *u;
1011 int     i;
1012 {
1013         return ((char *)NULL);
1014 }
1015
1016 char *
1017 quote_string(s)
1018 char    *s;
1019 {
1020         return savestring(s);
1021 }
1022
1023 print_element(ae)
1024 ARRAY_ELEMENT   *ae;
1025 {
1026         char    lbuf[INT_STRLEN_BOUND (intmax_t) + 1];
1027
1028         printf("array[%s] = %s\n",
1029                 inttostr (element_index(ae), lbuf, sizeof (lbuf)),
1030                 element_value(ae));
1031 }
1032
1033 print_array(a)
1034 ARRAY   *a;
1035 {
1036         printf("\n");
1037         array_walk(a, print_element, (void *)NULL);
1038 }
1039
1040 main()
1041 {
1042         ARRAY   *a, *new_a, *copy_of_a;
1043         ARRAY_ELEMENT   *ae, *aew;
1044         char    *s;
1045
1046         a = array_create();
1047         array_insert(a, 1, "one");
1048         array_insert(a, 7, "seven");
1049         array_insert(a, 4, "four");
1050         array_insert(a, 1029, "one thousand twenty-nine");
1051         array_insert(a, 12, "twelve");
1052         array_insert(a, 42, "forty-two");
1053         print_array(a);
1054         s = array_to_string (a, " ", 0);
1055         printf("s = %s\n", s);
1056         copy_of_a = array_from_string(s, " ");
1057         printf("copy_of_a:");
1058         print_array(copy_of_a);
1059         array_dispose(copy_of_a);
1060         printf("\n");
1061         free(s);
1062         ae = array_remove(a, 4);
1063         array_dispose_element(ae);
1064         ae = array_remove(a, 1029);
1065         array_dispose_element(ae);
1066         array_insert(a, 16, "sixteen");
1067         print_array(a);
1068         s = array_to_string (a, " ", 0);
1069         printf("s = %s\n", s);
1070         copy_of_a = array_from_string(s, " ");
1071         printf("copy_of_a:");
1072         print_array(copy_of_a);
1073         array_dispose(copy_of_a);
1074         printf("\n");
1075         free(s);
1076         array_insert(a, 2, "two");
1077         array_insert(a, 1029, "new one thousand twenty-nine");
1078         array_insert(a, 0, "zero");
1079         array_insert(a, 134, "");
1080         print_array(a);
1081         s = array_to_string (a, ":", 0);
1082         printf("s = %s\n", s);
1083         copy_of_a = array_from_string(s, ":");
1084         printf("copy_of_a:");
1085         print_array(copy_of_a);
1086         array_dispose(copy_of_a);
1087         printf("\n");
1088         free(s);
1089         new_a = array_copy(a);
1090         print_array(new_a);
1091         s = array_to_string (new_a, ":", 0);
1092         printf("s = %s\n", s);
1093         copy_of_a = array_from_string(s, ":");
1094         free(s);
1095         printf("copy_of_a:");
1096         print_array(copy_of_a);
1097         array_shift(copy_of_a, 2, AS_DISPOSE);
1098         printf("copy_of_a shifted by two:");
1099         print_array(copy_of_a);
1100         ae = array_shift(copy_of_a, 2, 0);
1101         printf("copy_of_a shifted by two:");
1102         print_array(copy_of_a);
1103         for ( ; ae; ) {
1104                 aew = element_forw(ae);
1105                 array_dispose_element(ae);
1106                 ae = aew;
1107         }
1108         array_rshift(copy_of_a, 1, (char *)0);
1109         printf("copy_of_a rshift by 1:");
1110         print_array(copy_of_a);
1111         array_rshift(copy_of_a, 2, "new element zero");
1112         printf("copy_of_a rshift again by 2 with new element zero:");
1113         print_array(copy_of_a);
1114         s = array_to_assign(copy_of_a, 0);
1115         printf("copy_of_a=%s\n", s);
1116         free(s);
1117         ae = array_shift(copy_of_a, array_num_elements(copy_of_a), 0);
1118         for ( ; ae; ) {
1119                 aew = element_forw(ae);
1120                 array_dispose_element(ae);
1121                 ae = aew;
1122         }
1123         array_dispose(copy_of_a);
1124         printf("\n");
1125         array_dispose(a);
1126         array_dispose(new_a);
1127 }
1128
1129 #endif /* TEST_ARRAY */
1130 #endif /* ARRAY_VARS */