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 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 it under
  17    the terms of the GNU General Public License as published by the Free
  18    Software Foundation; either version 2, or (at your option) any later
  19    version.
  20
  21    Bash is distributed in the hope that it will be useful, but WITHOUT ANY
  22    WARRANTY; without even the implied warranty of MERCHANTABILITY or
  23    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  24    for more details.
  25
  26    You should have received a copy of the GNU General Public License along
  27    with Bash; see the file COPYING.  If not, write to the Free Software
  28    Foundation, 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
  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 /*
  57  * Allocate and return a new array element with index INDEX and value
  58  * VALUE.
  59  */
  60 ARRAY_ELEMENT *
  61 new_array_element(indx, value)
  62 arrayind_t      indx;
  63 char    *value;
  64 {
  65         ARRAY_ELEMENT *r;
  66
  67         r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
  68         r->ind = indx;
  69         r->value = value ? savestring(value) : (char *)NULL;
  70         r->next = r->prev = (ARRAY_ELEMENT *) NULL;
  71         return(r);
  72 }
  73
  74 void
  75 destroy_array_element(ae)
  76 ARRAY_ELEMENT   *ae;
  77 {
  78         FREE(ae->value);
  79         free(ae);
  80 }
  81
  82 ARRAY *
  83 new_array()
  84 {
  85         ARRAY   *r;
  86         ARRAY_ELEMENT   *head;
  87
  88         r =(ARRAY *)xmalloc(sizeof(ARRAY));
  89         r->type = array_indexed;
  90         r->max_index = r->max_size = -1;
  91         r->num_elements = 0;
  92         head = new_array_element(-1, (char *)NULL);     /* dummy head */
  93         head->prev = head->next = head;
  94         r->head = head;
  95         return(r);
  96 }
  97
  98 void
  99 empty_array (a)
 100 ARRAY   *a;
 101 {
 102         register ARRAY_ELEMENT *r, *r1;
 103
 104         if (a == 0)
 105                 return;
 106         for (r = element_forw(a->head); r != a->head; ) {
 107                 r1 = element_forw(r);
 108                 destroy_array_element(r);
 109                 r = r1;
 110         }
 111         a->head->next = a->head->prev = a->head;
 112         a->max_index = a->max_size = -1;
 113         a->num_elements = a->max_size = 0;
 114 }
 115
 116 void
 117 dispose_array(a)
 118 ARRAY   *a;
 119 {
 120         if (a == 0)
 121                 return;
 122         empty_array (a);
 123         destroy_array_element(a->head);
 124         free(a);
 125 }
 126
 127 ARRAY *
 128 dup_array(a)
 129 ARRAY   *a;
 130 {
 131         ARRAY   *a1;
 132         ARRAY_ELEMENT   *ae, *new;
 133
 134         if (!a)
 135                 return((ARRAY *) NULL);
 136         a1 = new_array();
 137         a1->type = a->type;
 138         a1->max_index = a->max_index;
 139         a1->num_elements = a->num_elements;
 140         a1->max_size = a->max_size;
 141         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 142                 new = new_array_element(element_index(ae), element_value(ae));
 143                 ADD_BEFORE(a1->head, new);
 144         }
 145         return(a1);
 146 }
 147
 148 #ifdef INCLUDE_UNUSED
 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 dup_array_subrange(array, s, e)
 155 ARRAY           *array;
 156 ARRAY_ELEMENT   *s, *e;
 157 {
 158         ARRAY   *a;
 159         ARRAY_ELEMENT *p, *n;
 160         arrayind_t i;
 161
 162         a = new_array ();
 163         a->type = array->type;
 164
 165         for (p = s, i = 0; p != e; p = element_forw(p), i++) {
 166                 n = new_array_element (i, element_value(p));
 167                 ADD_BEFORE(a->head, n);
 168         }
 169         a->num_elements = a->max_index = i;
 170         return a;
 171 }
 172 #endif
 173
 174 #ifdef INCLUDE_UNUSED
 175 ARRAY_ELEMENT *
 176 copy_array_element(ae)
 177 ARRAY_ELEMENT   *ae;
 178 {
 179         return(ae ? new_array_element(element_index(ae), element_value(ae))
 180                   : (ARRAY_ELEMENT *) NULL);
 181 }
 182 #endif
 183
 184 /*
 185  * Add a new element with index I and value V to array A (a[i] = v).
 186  */
 187 int
 188 array_add_element(a, i, v)
 189 ARRAY   *a;
 190 arrayind_t      i;
 191 char    *v;
 192 {
 193         register ARRAY_ELEMENT *new, *ae;
 194
 195         if (!a)
 196                 return(-1);
 197         new = new_array_element(i, v);
 198         if (i > array_max_index(a)) {
 199                 /*
 200                  * Hook onto the end.  This also works for an empty array.
 201                  * Fast path for the common case of allocating arrays
 202                  * sequentially.
 203                  */
 204                 ADD_BEFORE(a->head, new);
 205                 a->max_index = i;
 206                 a->num_elements++;
 207                 return(0);
 208         }
 209         /*
 210          * Otherwise we search for the spot to insert it.
 211          */
 212         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 213                 if (element_index(ae) == i) {
 214                         /*
 215                          * Replacing an existing element.
 216                          */
 217                         destroy_array_element(new);
 218                         free(element_value(ae));
 219                         ae->value = savestring(v);
 220                         return(0);
 221                 } else if (element_index(ae) > i) {
 222                         ADD_BEFORE(ae, new);
 223                         a->num_elements++;
 224                         return(0);
 225                 }
 226         }
 227         return (-1);            /* problem */
 228 }
 229
 230 /*
 231  * Delete the element with index I from array A and return it so the
 232  * caller can dispose of it.
 233  */
 234 ARRAY_ELEMENT *
 235 array_delete_element(a, i)
 236 ARRAY   *a;
 237 arrayind_t      i;
 238 {
 239         register ARRAY_ELEMENT *ae;
 240
 241         if (!a || array_empty(a))
 242                 return((ARRAY_ELEMENT *) NULL);
 243         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 244                 if (element_index(ae) == i) {
 245                         ae->next->prev = ae->prev;
 246                         ae->prev->next = ae->next;
 247                         a->num_elements--;
 248                         if (i == array_max_index(a))
 249                                 a->max_index = element_index(ae->prev);
 250                         return(ae);
 251                 }
 252         return((ARRAY_ELEMENT *) NULL);
 253 }
 254
 255 /*
 256  * Return the value of a[i].
 257  */
 258 char *
 259 array_reference(a, i)
 260 ARRAY   *a;
 261 arrayind_t      i;
 262 {
 263         register ARRAY_ELEMENT *ae;
 264
 265         if (a == 0 || array_empty(a))
 266                 return((char *) NULL);
 267         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 268                 if (element_index(ae) == i)
 269                         return(element_value(ae));
 270         return((char *) NULL);
 271 }
 272
 273 #ifdef TEST_ARRAY
 274 /*
 275  * Walk the array, calling FUNC once for each element, with the array
 276  * element as the argument.
 277  */
 278 void
 279 array_walk(a, func)
 280 ARRAY   *a;
 281 sh_ae_map_func_t *func;
 282 {
 283         register ARRAY_ELEMENT *ae;
 284
 285         if (a == 0 || array_empty(a))
 286                 return;
 287         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 288                 (*func)(ae);
 289 }
 290 #endif
 291
 292 /*
 293  * Return a string that is the concatenation of all the elements in A,
 294  * separated by SEP.
 295  */
 296 static char *
 297 array_to_string_internal (start, end, sep, quoted)
 298 ARRAY_ELEMENT   *start, *end;
 299 char    *sep;
 300 int     quoted;
 301 {
 302         char    *result, *t;
 303         ARRAY_ELEMENT *ae;
 304         int     slen, rsize, rlen, reg;
 305
 306         if (start == end)       /* XXX - should not happen */
 307                 return ((char *)NULL);
 308
 309         slen = strlen(sep);
 310         result = NULL;
 311         for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
 312                 if (rsize == 0)
 313                         result = (char *)xmalloc (rsize = 64);
 314                 if (element_value(ae)) {
 315                         t = quoted ? quote_string(element_value(ae)) : element_value(ae);
 316                         reg = strlen(t);
 317                         RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
 318                                                 rsize, rsize);
 319                         strcpy(result + rlen, t);
 320                         rlen += reg;
 321                         if (quoted && t)
 322                                 free(t);
 323                         /*
 324                          * Add a separator only after non-null elements.
 325                          */
 326                         if (element_forw(ae) != end) {
 327                                 strcpy(result + rlen, sep);
 328                                 rlen += slen;
 329                         }
 330                 }
 331         }
 332         if (result)
 333           result[rlen] = '\0';  /* XXX */
 334         return(result);
 335 }
 336
 337 char *
 338 array_to_string (a, sep, quoted)
 339 ARRAY   *a;
 340 char    *sep;
 341 int     quoted;
 342 {
 343         if (a == 0)
 344                 return((char *)NULL);
 345         if (array_empty(a))
 346                 return(savestring(""));
 347         return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
 348 }
 349
 350 char *
 351 array_to_assignment_string (a)
 352 ARRAY   *a;
 353 {
 354         char    *result, *indstr, *valstr;
 355         ARRAY_ELEMENT *ae;
 356         int     rsize, rlen, elen;
 357
 358         if (a == 0 || array_empty (a))
 359                 return((char *)NULL);
 360
 361         result = (char *)xmalloc (rsize = 128);
 362         result[0] = '(';
 363         rlen = 1;
 364
 365         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 366                 indstr = itos (element_index(ae));
 367                 valstr = element_value (ae) ? sh_double_quote (element_value(ae))
 368                                             : (char *)NULL;
 369                 elen = STRLEN (indstr) + 8 + STRLEN (valstr);
 370                 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
 371
 372                 result[rlen++] = '[';
 373                 strcpy (result + rlen, indstr);
 374                 rlen += STRLEN (indstr);
 375                 result[rlen++] = ']';
 376                 result[rlen++] = '=';
 377                 if (valstr) {
 378                         strcpy (result + rlen, valstr);
 379                         rlen += STRLEN (valstr);
 380                 }
 381
 382                 if (element_forw(ae) != a->head)
 383                   result[rlen++] = ' ';
 384
 385                 FREE (indstr);
 386                 FREE (valstr);
 387         }
 388         RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
 389         result[rlen++] = ')';
 390         result[rlen] = '\0';
 391         return(result);
 392 }
 393
 394 char *
 395 quoted_array_assignment_string (a)
 396 ARRAY   *a;
 397 {
 398         char *vstr, *sv;
 399
 400         sv = array_to_assignment_string (a);
 401         if (sv == 0)
 402                 return ((char *)NULL);
 403
 404         vstr = sh_single_quote (sv);
 405         free (sv);
 406         return (vstr);
 407 }
 408
 409 #if 0
 410 /* Determine if s2 occurs in s1.  If so, return a pointer to the
 411    match in s1.  The compare is case sensitive. */
 412 static char *
 413 sindex (s1, s2)
 414 register char *s1, *s2;
 415 {
 416         register int i, l, len;
 417
 418         for (i = 0, l = strlen(s2), len = strlen(s1); (len - i) >= l; i++)
 419                 if (strncmp (s1 + i, s2, l) == 0)
 420                         return (s1 + i);
 421         return ((char *)NULL);
 422 }
 423 #endif
 424
 425 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
 426 /*
 427  * Return an array consisting of elements in S, separated by SEP
 428  */
 429 ARRAY *
 430 string_to_array(s, sep)
 431 char    *s, *sep;
 432 {
 433         ARRAY   *a;
 434         WORD_LIST *w;
 435
 436         if (s == 0)
 437                 return((ARRAY *)NULL);
 438         w = list_string (s, sep, 0);
 439         if (w == 0)
 440                 return((ARRAY *)NULL);
 441         a = word_list_to_array (w);
 442         return (a);
 443 }
 444 #endif
 445
 446 /* Convenience routines for the shell to translate to and from the form used
 447    by the rest of the code. */
 448 WORD_LIST *
 449 array_to_word_list(a)
 450 ARRAY   *a;
 451 {
 452         WORD_LIST       *list;
 453         ARRAY_ELEMENT   *ae;
 454
 455         if (a == 0 || array_empty(a))
 456                 return((WORD_LIST *)NULL);
 457         list = (WORD_LIST *)NULL;
 458         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 459                 list = make_word_list (make_bare_word(element_value(ae)), list);
 460         return (REVERSE_LIST(list, WORD_LIST *));
 461 }
 462
 463 char **
 464 array_to_argv (a)
 465 ARRAY   *a;
 466 {
 467         char            **ret, *t;
 468         int             i;
 469         ARRAY_ELEMENT   *ae;
 470
 471         if (a == 0 || array_empty(a))
 472                 return ((char **)NULL);
 473         ret = alloc_array (array_num_elements (a) + 1);
 474         i = 0;
 475         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 476                 t = element_value (ae);
 477                 ret[i++] = t ? savestring (t) : (char *)NULL;
 478         }
 479         ret[i] = (char *)NULL;
 480         return (ret);
 481 }
 482
 483 ARRAY *
 484 assign_word_list (array, list)
 485 ARRAY   *array;
 486 WORD_LIST       *list;
 487 {
 488         register WORD_LIST *l;
 489         register arrayind_t i;
 490
 491         for (l = list, i = 0; l; l = l->next, i++)
 492                 array_add_element(array, i, l->word->word);
 493         return array;
 494 }
 495
 496 ARRAY *
 497 word_list_to_array (list)
 498 WORD_LIST       *list;
 499 {
 500         ARRAY   *a;
 501
 502         if (list == 0)
 503                 return((ARRAY *)NULL);
 504         a = new_array();
 505         return (assign_word_list (a, list));
 506 }
 507
 508 ARRAY   *
 509 array_quote(array)
 510 ARRAY   *array;
 511 {
 512         ARRAY_ELEMENT   *a;
 513         char    *t;
 514
 515         if (array == 0 || array->head == 0 || array_empty (array))
 516                 return (ARRAY *)NULL;
 517         for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
 518                 t = quote_string (a->value);
 519                 FREE(a->value);
 520                 a->value = t;
 521         }
 522         return array;
 523 }
 524
 525 char *
 526 array_subrange (a, start, end, quoted)
 527 ARRAY   *a;
 528 arrayind_t      start, end;
 529 int     quoted;
 530 {
 531         ARRAY_ELEMENT   *h, *p;
 532         arrayind_t      i;
 533
 534         p = array_head (a);
 535         if (p == 0 || array_empty (a) || start > array_num_elements (a))
 536                 return ((char *)NULL);
 537
 538         for (i = 0, p = element_forw(p); p != a->head && i < start; i++, p = element_forw(p))
 539                 ;
 540         if (p == a->head)
 541                 return ((char *)NULL);
 542         for (h = p; p != a->head && i < end; i++, p = element_forw(p))
 543                 ;
 544
 545         return (array_to_string_internal (h, p, " ", quoted));
 546 }
 547
 548 char *
 549 array_pat_subst (a, pat, rep, mflags)
 550 ARRAY   *a;
 551 char    *pat, *rep;
 552 int     mflags;
 553 {
 554         ARRAY           *a2;
 555         ARRAY_ELEMENT   *e;
 556         char    *t;
 557
 558         if (array_head (a) == 0 || array_empty (a))
 559                 return ((char *)NULL);
 560
 561         a2 = dup_array (a);
 562         for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
 563                 t = pat_subst(element_value(e), pat, rep, mflags);
 564                 FREE(element_value(e));
 565                 e->value = t;
 566         }
 567
 568         if (mflags & MATCH_QUOTED)
 569                 array_quote (a2);
 570         t = array_to_string (a2, " ", 0);
 571         dispose_array (a2);
 572
 573         return t;
 574 }
 575
 576
 577 #if defined (TEST_ARRAY)
 578 print_element(ae)
 579 ARRAY_ELEMENT   *ae;
 580 {
 581         printf("array[%ld] = %s\n", element_index(ae), element_value(ae));
 582 }
 583
 584 print_array(a)
 585 ARRAY   *a;
 586 {
 587         printf("\n");
 588         array_walk(a, print_element);
 589 }
 590
 591 main()
 592 {
 593         ARRAY   *a, *new_a, *copy_of_a;
 594         ARRAY_ELEMENT   *ae;
 595         char    *s;
 596
 597         a = new_array();
 598         array_add_element(a, 1, "one");
 599         array_add_element(a, 7, "seven");
 600         array_add_element(a, 4, "four");
 601         array_add_element(a, 1029, "one thousand twenty-nine");
 602         array_add_element(a, 12, "twelve");
 603         array_add_element(a, 42, "forty-two");
 604         print_array(a);
 605         s = array_to_string (a, " ", 0);
 606         printf("s = %s\n", s);
 607         copy_of_a = string_to_array(s, " ");
 608         printf("copy_of_a:");
 609         print_array(copy_of_a);
 610         dispose_array(copy_of_a);
 611         printf("\n");
 612         free(s);
 613         ae = array_delete_element(a, 4);
 614         destroy_array_element(ae);
 615         ae = array_delete_element(a, 1029);
 616         destroy_array_element(ae);
 617         array_add_element(a, 16, "sixteen");
 618         print_array(a);
 619         s = array_to_string (a, " ", 0);
 620         printf("s = %s\n", s);
 621         copy_of_a = string_to_array(s, " ");
 622         printf("copy_of_a:");
 623         print_array(copy_of_a);
 624         dispose_array(copy_of_a);
 625         printf("\n");
 626         free(s);
 627         array_add_element(a, 2, "two");
 628         array_add_element(a, 1029, "new one thousand twenty-nine");
 629         array_add_element(a, 0, "zero");
 630         array_add_element(a, 134, "");
 631         print_array(a);
 632         s = array_to_string (a, ":", 0);
 633         printf("s = %s\n", s);
 634         copy_of_a = string_to_array(s, ":");
 635         printf("copy_of_a:");
 636         print_array(copy_of_a);
 637         dispose_array(copy_of_a);
 638         printf("\n");
 639         free(s);
 640         new_a = copy_array(a);
 641         print_array(new_a);
 642         s = array_to_string (new_a, ":", 0);
 643         printf("s = %s\n", s);
 644         copy_of_a = string_to_array(s, ":", 0);
 645         printf("copy_of_a:");
 646         print_array(copy_of_a);
 647         dispose_array(copy_of_a);
 648         printf("\n");
 649         free(s);
 650         dispose_array(a);
 651         dispose_array(new_a);
 652 }
 653
 654 #endif /* TEST_ARRAY */
 655 #endif /* ARRAY_VARS */