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