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