2 * array.c - functions to create, destroy, access, and manipulate arrays
5 * Arrays are sparse doubly-linked lists. An element's index is stored
12 /* Copyright (C) 1997-2004 Free Software Foundation, Inc.
14 This file is part of GNU Bash, the Bourne Again SHell.
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
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
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. */
32 #if defined (ARRAY_VARS)
34 #if defined (HAVE_UNISTD_H)
36 # include <sys/types.h>
46 #include "builtins/common.h"
48 #define ADD_BEFORE(ae, new) \
50 ae->prev->next = new; \
51 new->prev = ae->prev; \
56 static char *array_to_string_internal __P((ARRAY_ELEMENT *, ARRAY_ELEMENT *, char *, int));
64 r =(ARRAY *)xmalloc(sizeof(ARRAY));
65 r->type = array_indexed;
68 head = array_create_element(-1, (char *)NULL); /* dummy head */
69 head->prev = head->next = head;
78 register ARRAY_ELEMENT *r, *r1;
82 for (r = element_forw(a->head); r != a->head; ) {
84 array_dispose_element(r);
87 a->head->next = a->head->prev = a->head;
99 array_dispose_element(a->head);
108 ARRAY_ELEMENT *ae, *new;
111 return((ARRAY *) NULL);
114 a1->max_index = a->max_index;
115 a1->num_elements = a->num_elements;
116 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
117 new = array_create_element(element_index(ae), element_value(ae));
118 ADD_BEFORE(a1->head, new);
123 #ifdef INCLUDE_UNUSED
125 * Make and return a new array composed of the elements in array A from
129 array_slice(array, s, e)
131 ARRAY_ELEMENT *s, *e;
134 ARRAY_ELEMENT *p, *n;
139 a->type = array->type;
141 for (p = s, i = 0; p != e; p = element_forw(p), i++) {
142 n = array_create_element (element_index(p), element_value(p));
143 ADD_BEFORE(a->head, n);
144 mi = element_index(ae);
153 * Walk the array, calling FUNC once for each element, with the array
154 * element as the argument.
157 array_walk(a, func, udata)
159 sh_ae_map_func_t *func;
162 register ARRAY_ELEMENT *ae;
164 if (a == 0 || array_empty(a))
166 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
167 if ((*func)(ae, udata) < 0)
172 * Shift the array A N elements to the left. Delete the first N elements
173 * and subtract N from the indices of the remaining elements. If FLAGS
174 * does not include AS_DISPOSE, this returns a singly-linked null-terminated
175 * list of elements so the caller can dispose of the chain. If FLAGS
176 * includes AS_DISPOSE, this function disposes of the shifted-out elements
180 array_shift(a, n, flags)
184 register ARRAY_ELEMENT *ae, *ret;
187 if (a == 0 || array_empty(a) || n <= 0)
188 return ((ARRAY_ELEMENT *)NULL);
190 for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
193 /* Easy case; shifting out all of the elements */
194 if (flags & AS_DISPOSE) {
196 return ((ARRAY_ELEMENT *)NULL);
198 for (ae = ret; element_forw(ae) != a->head; ae = element_forw(ae))
200 element_forw(ae) = (ARRAY_ELEMENT *)NULL;
201 a->head->next = a->head->prev = a->head;
207 * ae now points to the list of elements we want to retain.
208 * ret points to the list we want to either destroy or return.
210 ae->prev->next = (ARRAY_ELEMENT *)NULL; /* null-terminate RET */
212 a->head->next = ae; /* slice RET out of the array */
215 for ( ; ae != a->head; ae = element_forw(ae))
216 element_index(ae) -= n; /* renumber retained indices */
218 a->num_elements -= n; /* modify bookkeeping information */
221 if (flags & AS_DISPOSE) {
222 for (ae = ret; ae; ) {
223 ret = element_forw(ae);
224 array_dispose_element(ae);
227 return ((ARRAY_ELEMENT *)NULL);
234 * Shift array A right N indices. If S is non-null, it becomes the value of
235 * the new element 0. Returns the number of elements in the array after the
239 array_rshift (a, n, s)
244 register ARRAY_ELEMENT *ae, *new;
249 return (a->num_elements);
251 ae = element_forw(a->head);
253 new = array_create_element(0, s);
261 * Renumber all elements in the array except the one we just added.
263 for ( ; ae != a->head; ae = element_forw(ae))
264 element_index(ae) += n;
266 return (a->num_elements);
270 array_unshift_element(a)
273 return (array_shift (a, 1, 0));
277 array_shift_element(a, v)
281 return (array_rshift (a, 1, v));
291 if (array == 0 || array->head == 0 || array_empty (array))
292 return (ARRAY *)NULL;
293 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
294 t = quote_string (a->value);
302 * Return a string whose elements are the members of array A beginning at
303 * index START and spanning NELEM members. Null elements are counted.
304 * Since arrays are sparse, unset array elements are not counted.
307 array_subrange (a, start, nelem, starsub, quoted)
309 arrayind_t start, nelem;
312 ARRAY_ELEMENT *h, *p;
317 if (p == 0 || array_empty (a) || start > array_max_index(a))
318 return ((char *)NULL);
321 * Find element with index START. If START corresponds to an unset
322 * element (arrays can be sparse), use the first element whose index
323 * is >= START. If START is < 0, we count START indices back from
324 * the end of A (not elements, even with sparse arrays -- START is an
327 for (p = element_forw(p); p != array_head(a) && start > element_index(p); p = element_forw(p))
331 return ((char *)NULL);
333 /* Starting at P, take NELEM elements, inclusive. */
334 for (i = 0, h = p; p != a->head && i < nelem; i++, p = element_forw(p))
337 if (starsub && (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))) {
339 sep[0] = ifs ? *ifs : '\0';
344 return (array_to_string_internal (h, p, sep, quoted));
348 array_patsub (a, pat, rep, mflags)
355 char *t, *ifs, sifs[2];
357 if (array_head (a) == 0 || array_empty (a))
358 return ((char *)NULL);
361 for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
362 t = pat_subst(element_value(e), pat, rep, mflags);
363 FREE(element_value(e));
367 if (mflags & MATCH_QUOTED)
369 if (mflags & MATCH_STARSUB) {
371 sifs[0] = ifs ? *ifs : '\0';
373 t = array_to_string (a2, sifs, 0);
375 t = array_to_string (a2, " ", 0);
382 * Allocate and return a new array element with index INDEX and value
386 array_create_element(indx, value)
392 r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
394 r->value = value ? savestring(value) : (char *)NULL;
395 r->next = r->prev = (ARRAY_ELEMENT *) NULL;
399 #ifdef INCLUDE_UNUSED
401 array_copy_element(ae)
404 return(ae ? array_create_element(element_index(ae), element_value(ae))
405 : (ARRAY_ELEMENT *) NULL);
410 array_dispose_element(ae)
420 * Add a new element with index I and value V to array A (a[i] = v).
423 array_insert(a, i, v)
428 register ARRAY_ELEMENT *new, *ae;
432 new = array_create_element(i, v);
433 if (i > array_max_index(a)) {
435 * Hook onto the end. This also works for an empty array.
436 * Fast path for the common case of allocating arrays
439 ADD_BEFORE(a->head, new);
445 * Otherwise we search for the spot to insert it.
447 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
448 if (element_index(ae) == i) {
450 * Replacing an existing element.
452 array_dispose_element(new);
453 free(element_value(ae));
454 ae->value = v ? savestring(v) : (char *)NULL;
456 } else if (element_index(ae) > i) {
462 return (-1); /* problem */
466 * Delete the element with index I from array A and return it so the
467 * caller can dispose of it.
474 register ARRAY_ELEMENT *ae;
476 if (!a || array_empty(a))
477 return((ARRAY_ELEMENT *) NULL);
478 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
479 if (element_index(ae) == i) {
480 ae->next->prev = ae->prev;
481 ae->prev->next = ae->next;
483 if (i == array_max_index(a))
484 a->max_index = element_index(ae->prev);
487 return((ARRAY_ELEMENT *) NULL);
491 * Return the value of a[i].
494 array_reference(a, i)
498 register ARRAY_ELEMENT *ae;
500 if (a == 0 || array_empty(a))
501 return((char *) NULL);
502 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
503 if (element_index(ae) == i)
504 return(element_value(ae));
505 return((char *) NULL);
508 /* Convenience routines for the shell to translate to and from the form used
509 by the rest of the code. */
512 array_to_word_list(a)
518 if (a == 0 || array_empty(a))
519 return((WORD_LIST *)NULL);
520 list = (WORD_LIST *)NULL;
521 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
522 list = make_word_list (make_bare_word(element_value(ae)), list);
523 return (REVERSE_LIST(list, WORD_LIST *));
527 array_from_word_list (list)
533 return((ARRAY *)NULL);
535 return (array_assign_list (a, list));
539 array_keys_to_word_list(a)
546 if (a == 0 || array_empty(a))
547 return((WORD_LIST *)NULL);
548 list = (WORD_LIST *)NULL;
549 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
550 t = itos(element_index(ae));
551 list = make_word_list (make_bare_word(t), list);
554 return (REVERSE_LIST(list, WORD_LIST *));
558 array_assign_list (array, list)
562 register WORD_LIST *l;
563 register arrayind_t i;
565 for (l = list, i = 0; l; l = l->next, i++)
566 array_insert(array, i, l->word->word);
578 if (a == 0 || array_empty(a))
579 return ((char **)NULL);
580 ret = strvec_create (array_num_elements (a) + 1);
582 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
583 t = element_value (ae);
584 ret[i++] = t ? savestring (t) : (char *)NULL;
586 ret[i] = (char *)NULL;
591 * Return a string that is the concatenation of all the elements in A,
595 array_to_string_internal (start, end, sep, quoted)
596 ARRAY_ELEMENT *start, *end;
602 int slen, rsize, rlen, reg;
604 if (start == end) /* XXX - should not happen */
605 return ((char *)NULL);
609 for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
611 result = (char *)xmalloc (rsize = 64);
612 if (element_value(ae)) {
613 t = quoted ? quote_string(element_value(ae)) : element_value(ae);
615 RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
617 strcpy(result + rlen, t);
622 * Add a separator only after non-null elements.
624 if (element_forw(ae) != end) {
625 strcpy(result + rlen, sep);
631 result[rlen] = '\0'; /* XXX */
636 array_to_assign (a, quoted)
640 char *result, *valstr, *is;
641 char indstr[INT_STRLEN_BOUND(intmax_t) + 1];
643 int rsize, rlen, elen;
645 if (a == 0 || array_empty (a))
646 return((char *)NULL);
648 result = (char *)xmalloc (rsize = 128);
652 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
653 is = inttostr (element_index(ae), indstr, sizeof(indstr));
654 valstr = element_value (ae) ? sh_double_quote (element_value(ae))
656 elen = STRLEN (indstr) + 8 + STRLEN (valstr);
657 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
659 result[rlen++] = '[';
660 strcpy (result + rlen, is);
662 result[rlen++] = ']';
663 result[rlen++] = '=';
665 strcpy (result + rlen, valstr);
666 rlen += STRLEN (valstr);
669 if (element_forw(ae) != a->head)
670 result[rlen++] = ' ';
674 RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
675 result[rlen++] = ')';
678 /* This is not as efficient as it could be... */
679 valstr = sh_single_quote (result);
687 array_to_string (a, sep, quoted)
693 return((char *)NULL);
695 return(savestring(""));
696 return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
699 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
701 * Return an array consisting of elements in S, separated by SEP
704 array_from_string(s, sep)
711 return((ARRAY *)NULL);
712 w = list_string (s, sep, 0);
714 return((ARRAY *)NULL);
715 a = array_from_word_list (w);
720 #if defined (TEST_ARRAY)
722 * To make a running version, compile -DTEST_ARRAY and link with:
723 * xmalloc.o syntax.o lib/malloc/libmalloc.a lib/sh/libsh.a
725 int interrupt_immediately = 0;
735 fatal_error(const char *s, ...)
737 fprintf(stderr, "array_test: fatal memory error\n");
742 programming_error(const char *s, ...)
744 fprintf(stderr, "array_test: fatal programming error\n");
754 w = (WORD_DESC *)xmalloc(sizeof(WORD_DESC));
755 w->word = s ? savestring(s) : savestring ("");
767 w = (WORD_LIST *)xmalloc(sizeof(WORD_LIST));
782 return (WORD_LIST *)NULL;
784 wl = (WORD_LIST *)NULL;
787 wl = make_word_list (make_bare_word(a), wl);
788 a = strtok((char *)NULL, t);
790 return (REVERSE_LIST (wl, WORD_LIST *));
797 register GENERIC_LIST *next, *prev;
799 for (prev = 0; list; ) {
809 pat_subst(s, t, u, i)
813 return ((char *)NULL);
820 return savestring(s);
826 char lbuf[INT_STRLEN_BOUND (intmax_t) + 1];
828 printf("array[%s] = %s\n",
829 inttostr (element_index(ae), lbuf, sizeof (lbuf)),
837 array_walk(a, print_element, (void *)NULL);
842 ARRAY *a, *new_a, *copy_of_a;
843 ARRAY_ELEMENT *ae, *aew;
847 array_insert(a, 1, "one");
848 array_insert(a, 7, "seven");
849 array_insert(a, 4, "four");
850 array_insert(a, 1029, "one thousand twenty-nine");
851 array_insert(a, 12, "twelve");
852 array_insert(a, 42, "forty-two");
854 s = array_to_string (a, " ", 0);
855 printf("s = %s\n", s);
856 copy_of_a = array_from_string(s, " ");
857 printf("copy_of_a:");
858 print_array(copy_of_a);
859 array_dispose(copy_of_a);
862 ae = array_remove(a, 4);
863 array_dispose_element(ae);
864 ae = array_remove(a, 1029);
865 array_dispose_element(ae);
866 array_insert(a, 16, "sixteen");
868 s = array_to_string (a, " ", 0);
869 printf("s = %s\n", s);
870 copy_of_a = array_from_string(s, " ");
871 printf("copy_of_a:");
872 print_array(copy_of_a);
873 array_dispose(copy_of_a);
876 array_insert(a, 2, "two");
877 array_insert(a, 1029, "new one thousand twenty-nine");
878 array_insert(a, 0, "zero");
879 array_insert(a, 134, "");
881 s = array_to_string (a, ":", 0);
882 printf("s = %s\n", s);
883 copy_of_a = array_from_string(s, ":");
884 printf("copy_of_a:");
885 print_array(copy_of_a);
886 array_dispose(copy_of_a);
889 new_a = array_copy(a);
891 s = array_to_string (new_a, ":", 0);
892 printf("s = %s\n", s);
893 copy_of_a = array_from_string(s, ":");
895 printf("copy_of_a:");
896 print_array(copy_of_a);
897 array_shift(copy_of_a, 2, AS_DISPOSE);
898 printf("copy_of_a shifted by two:");
899 print_array(copy_of_a);
900 ae = array_shift(copy_of_a, 2, 0);
901 printf("copy_of_a shifted by two:");
902 print_array(copy_of_a);
904 aew = element_forw(ae);
905 array_dispose_element(ae);
908 array_rshift(copy_of_a, 1, (char *)0);
909 printf("copy_of_a rshift by 1:");
910 print_array(copy_of_a);
911 array_rshift(copy_of_a, 2, "new element zero");
912 printf("copy_of_a rshift again by 2 with new element zero:");
913 print_array(copy_of_a);
914 s = array_to_assign(copy_of_a, 0);
915 printf("copy_of_a=%s\n", s);
917 ae = array_shift(copy_of_a, array_num_elements(copy_of_a), 0);
919 aew = element_forw(ae);
920 array_dispose_element(ae);
923 array_dispose(copy_of_a);
926 array_dispose(new_a);
929 #endif /* TEST_ARRAY */
930 #endif /* ARRAY_VARS */