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