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