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