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 extern char *quote_string ();   /* XXX */
  49
  50 #define ADD_BEFORE(ae, new) \
  51         do { \
  52                 ae->prev->next = new; \
  53                 new->prev = ae->prev; \
  54                 ae->prev = new; \
  55                 new->next = ae; \
  56         } while(0)
  57
  58 /*
  59  * Allocate and return a new array element with index INDEX and value
  60  * VALUE.
  61  */
  62 ARRAY_ELEMENT *
  63 new_array_element(indx, value)
  64 arrayind_t      indx;
  65 char    *value;
  66 {
  67         ARRAY_ELEMENT *r;
  68
  69         r = (ARRAY_ELEMENT *) xmalloc(sizeof(ARRAY_ELEMENT));
  70         r->ind = indx;
  71         r->value = value ? savestring(value) : (char *)NULL;
  72         r->next = r->prev = (ARRAY_ELEMENT *) NULL;
  73         return(r);
  74 }
  75
  76 void
  77 destroy_array_element(ae)
  78 ARRAY_ELEMENT   *ae;
  79 {
  80         FREE(ae->value);
  81         free(ae);
  82 }
  83
  84 ARRAY *
  85 new_array()
  86 {
  87         ARRAY   *r;
  88         ARRAY_ELEMENT   *head;
  89
  90         r =(ARRAY *) xmalloc(sizeof(ARRAY));
  91         r->type = array_indexed;
  92         r->max_index = r->max_size = -1;
  93         r->num_elements = 0;
  94         head = new_array_element(-1, (char *)NULL);     /* dummy head */
  95         head->prev = head->next = head;
  96         r->head = head;
  97         return(r);
  98 }
  99
 100 void
 101 empty_array (a)
 102 ARRAY   *a;
 103 {
 104         register ARRAY_ELEMENT *r, *r1;
 105
 106         if (a == 0)
 107                 return;
 108         for (r = element_forw(a->head); r != a->head; ) {
 109                 r1 = element_forw(r);
 110                 destroy_array_element(r);
 111                 r = r1;
 112         }
 113         a->head->next = a->head->prev = a->head;
 114         a->max_index = a->max_size = -1;
 115         a->num_elements = a->max_size = 0;
 116 }
 117
 118 void
 119 dispose_array(a)
 120 ARRAY   *a;
 121 {
 122         if (a == 0)
 123                 return;
 124         empty_array (a);
 125         destroy_array_element(a->head);
 126         free(a);
 127 }
 128
 129 ARRAY *
 130 dup_array(a)
 131 ARRAY   *a;
 132 {
 133         ARRAY   *a1;
 134         ARRAY_ELEMENT   *ae, *new;
 135
 136         if (!a)
 137                 return((ARRAY *) NULL);
 138         a1 = new_array();
 139         a1->type = a->type;
 140         a1->max_index = a->max_index;
 141         a1->num_elements = a->num_elements;
 142         a1->max_size = a->max_size;
 143         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 144                 new = new_array_element(element_index(ae), element_value(ae));
 145                 ADD_BEFORE(a1->head, new);
 146         }
 147         return(a1);
 148 }
 149
 150 #ifdef INCLUDE_UNUSED
 151 /*
 152  * Make and return a new array composed of the elements in array A from
 153  * S to E, inclusive.
 154  */
 155 ARRAY *
 156 dup_array_subrange(array, s, e)
 157 ARRAY           *array;
 158 ARRAY_ELEMENT   *s, *e;
 159 {
 160         ARRAY   *a;
 161         ARRAY_ELEMENT *p, *n;
 162         int     i;
 163
 164         a = new_array ();
 165         a->type = array->type;
 166
 167         for (p = s, i = 0; p != e; p = element_forw(p), i++) {
 168                 n = new_array_element (i, element_value(p));
 169                 ADD_BEFORE(a->head, n);
 170         }
 171         a->num_elements = a->max_index = i;
 172         return a;
 173 }
 174 #endif
 175
 176 #ifdef INCLUDE_UNUSED
 177 ARRAY_ELEMENT *
 178 copy_array_element(ae)
 179 ARRAY_ELEMENT   *ae;
 180 {
 181         return(ae ? new_array_element(element_index(ae), element_value(ae))
 182                   : (ARRAY_ELEMENT *) NULL);
 183 }
 184 #endif
 185
 186 /*
 187  * Add a new element with index I and value V to array A (a[i] = v).
 188  */
 189 int
 190 array_add_element(a, i, v)
 191 ARRAY   *a;
 192 arrayind_t      i;
 193 char    *v;
 194 {
 195         register ARRAY_ELEMENT *new, *ae;
 196
 197         if (!a)
 198                 return(-1);
 199         new = new_array_element(i, v);
 200         if (i > array_max_index(a)) {
 201                 /*
 202                  * Hook onto the end.  This also works for an empty array.
 203                  * Fast path for the common case of allocating arrays
 204                  * sequentially.
 205                  */
 206                 ADD_BEFORE(a->head, new);
 207                 a->max_index = i;
 208                 a->num_elements++;
 209                 return(0);
 210         }
 211         /*
 212          * Otherwise we search for the spot to insert it.
 213          */
 214         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
 215                 if (element_index(ae) == i) {
 216                         /*
 217                          * Replacing an existing element.
 218                          */
 219                         destroy_array_element(new);
 220                         free(element_value(ae));
 221                         ae->value = savestring(v);
 222                         return(0);
 223                 } else if (element_index(ae) > i) {
 224                         ADD_BEFORE(ae, new);
 225                         a->num_elements++;
 226                         return(0);
 227                 }
 228         }
 229         return (-1);            /* problem */
 230 }
 231
 232 /*
 233  * Delete the element with index I from array A and return it so the
 234  * caller can dispose of it.
 235  */
 236 ARRAY_ELEMENT *
 237 array_delete_element(a, i)
 238 ARRAY   *a;
 239 arrayind_t      i;
 240 {
 241         register ARRAY_ELEMENT *ae;
 242
 243         if (!a || array_empty(a))
 244                 return((ARRAY_ELEMENT *) NULL);
 245         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 246                 if (element_index(ae) == i) {
 247                         ae->next->prev = ae->prev;
 248                         ae->prev->next = ae->next;
 249                         a->num_elements--;
 250                         if (i == array_max_index(a))
 251                                 a->max_index = element_index(ae->prev);
 252                         return(ae);
 253                 }
 254         return((ARRAY_ELEMENT *) NULL);
 255 }
 256
 257 /*
 258  * Return the value of a[i].
 259  */
 260 char *
 261 array_reference(a, i)
 262 ARRAY   *a;
 263 arrayind_t      i;
 264 {
 265         register ARRAY_ELEMENT *ae;
 266
 267         if (a == 0 || array_empty(a))
 268                 return((char *) NULL);
 269         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 270                 if (element_index(ae) == i)
 271                         return(element_value(ae));
 272         return((char *) NULL);
 273 }
 274
 275 #ifdef TEST_ARRAY
 276 /*
 277  * Walk the array, calling FUNC once for each element, with the array
 278  * element as the argument.
 279  */
 280 void
 281 array_walk(a, func)
 282 ARRAY   *a;
 283 Function *func;
 284 {
 285         register ARRAY_ELEMENT *ae;
 286
 287         if (a == 0 || array_empty(a))
 288                 return;
 289         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
 290                 (*func)(ae);
 291 }
 292 #endif
 293
 294 /*
 295  * Return a string that is the concatenation of all the elements in A,
 296  * separated by SEP.
 297  */
 298 static char *
 299 array_to_string_internal (start, end, sep, quoted)
 300 ARRAY_ELEMENT   *start, *end;
 301 char    *sep;
 302 int     quoted;
 303 {
 304         char    *result, *t;
 305         ARRAY_ELEMENT *ae;
 306         int     slen, rsize, rlen, reg;
 307
 308         if (start == end)       /* XXX - should not happen */
 309                 return ((char *)NULL);
 310
 311         slen = strlen(sep);
 312         for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
 313                 if (rsize == 0)
 314                         result = xmalloc (rsize = 64);
 315                 if (element_value(ae)) {
 316                         t = quoted ? quote_string(element_value(ae)) : element_value(ae);
 317                         reg = strlen(t);
 318                         RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
 319                                                 rsize, rsize);
 320                         strcpy(result + rlen, t);
 321                         rlen += reg;
 322                         if (quoted && t)
 323                                 free(t);
 324                         /*
 325                          * Add a separator only after non-null elements.
 326                          */
 327                         if (element_forw(ae) != end) {
 328                                 strcpy(result + rlen, sep);
 329                                 rlen += slen;
 330                         }
 331                 }
 332         }
 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 = 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) ? 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 = 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 int     start, end, quoted;
 529 {
 530         ARRAY_ELEMENT   *h, *p;
 531         int     i;
 532
 533         p = array_head (a);
 534         if (p == 0 || array_empty (a) || start > array_num_elements (a))
 535                 return ((char *)NULL);
 536
 537         for (i = 0, p = element_forw(p); p != a->head && i < start; i++, p = element_forw(p))
 538                 ;
 539         if (p == a->head)
 540                 return ((char *)NULL);
 541         for (h = p; p != a->head && i < end; i++, p = element_forw(p))
 542                 ;
 543
 544         return (array_to_string_internal (h, p, " ", quoted));
 545 }
 546
 547 char *
 548 array_pat_subst (a, pat, rep, mflags)
 549 ARRAY   *a;
 550 char    *pat, *rep;
 551 int     mflags;
 552 {
 553         ARRAY           *a2;
 554         ARRAY_ELEMENT   *e;
 555         char    *t;
 556
 557         if (array_head (a) == 0 || array_empty (a))
 558                 return ((char *)NULL);
 559
 560         a2 = dup_array (a);
 561         for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
 562                 t = pat_subst(element_value(e), pat, rep, mflags);
 563                 FREE(element_value(e));
 564                 e->value = t;
 565         }
 566
 567         if (mflags & MATCH_QUOTED)
 568                 array_quote (a2);
 569         t = array_to_string (a2, " ", 0);
 570         dispose_array (a2);
 571
 572         return t;
 573 }
 574
 575
 576 #if defined (TEST_ARRAY)
 577 print_element(ae)
 578 ARRAY_ELEMENT   *ae;
 579 {
 580         printf("array[%d] = %s\n",(int)element_index(ae), element_value(ae));
 581 }
 582
 583 print_array(a)
 584 ARRAY   *a;
 585 {
 586         printf("\n");
 587         array_walk(a, print_element);
 588 }
 589
 590 main()
 591 {
 592         ARRAY   *a, *new_a, *copy_of_a;
 593         ARRAY_ELEMENT   *ae;
 594         char    *s;
 595
 596         a = new_array();
 597         array_add_element(a, 1, "one");
 598         array_add_element(a, 7, "seven");
 599         array_add_element(a, 4, "four");
 600         array_add_element(a, 1029, "one thousand twenty-nine");
 601         array_add_element(a, 12, "twelve");
 602         array_add_element(a, 42, "forty-two");
 603         print_array(a);
 604         s = array_to_string (a, " ", 0);
 605         printf("s = %s\n", s);
 606         copy_of_a = string_to_array(s, " ");
 607         printf("copy_of_a:");
 608         print_array(copy_of_a);
 609         dispose_array(copy_of_a);
 610         printf("\n");
 611         free(s);
 612         ae = array_delete_element(a, 4);
 613         destroy_array_element(ae);
 614         ae = array_delete_element(a, 1029);
 615         destroy_array_element(ae);
 616         array_add_element(a, 16, "sixteen");
 617         print_array(a);
 618         s = array_to_string (a, " ", 0);
 619         printf("s = %s\n", s);
 620         copy_of_a = string_to_array(s, " ");
 621         printf("copy_of_a:");
 622         print_array(copy_of_a);
 623         dispose_array(copy_of_a);
 624         printf("\n");
 625         free(s);
 626         array_add_element(a, 2, "two");
 627         array_add_element(a, 1029, "new one thousand twenty-nine");
 628         array_add_element(a, 0, "zero");
 629         array_add_element(a, 134, "");
 630         print_array(a);
 631         s = array_to_string (a, ":", 0);
 632         printf("s = %s\n", s);
 633         copy_of_a = string_to_array(s, ":");
 634         printf("copy_of_a:");
 635         print_array(copy_of_a);
 636         dispose_array(copy_of_a);
 637         printf("\n");
 638         free(s);
 639         new_a = copy_array(a);
 640         print_array(new_a);
 641         s = array_to_string (new_a, ":", 0);
 642         printf("s = %s\n", s);
 643         copy_of_a = string_to_array(s, ":", 0);
 644         printf("copy_of_a:");
 645         print_array(copy_of_a);
 646         dispose_array(copy_of_a);
 647         printf("\n");
 648         free(s);
 649         dispose_array(a);
 650         dispose_array(new_a);
 651 }
 652
 653 #endif /* TEST_ARRAY */
 654 #endif /* ARRAY_VARS */