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-2009 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
17 it under the terms of the GNU General Public License as published by
18 the Free Software Foundation, either version 3 of the License, or
19 (at your option) any later version.
21 Bash is distributed in the hope that it will be useful,
22 but WITHOUT ANY WARRANTY; without even the implied warranty of
23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 GNU General Public License for more details.
26 You should have received a copy of the GNU General Public License
27 along with Bash. If not, see <http://www.gnu.org/licenses/>.
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));
58 static ARRAY *lastarray = 0;
59 static ARRAY_ELEMENT *lastref = 0;
61 #define IS_LASTREF(a) (lastarray && (a) == lastarray)
63 #define LASTREF_START(a, i) \
64 (IS_LASTREF(a) && i >= element_index(lastref)) ? lastref \
65 : element_forw(a->head)
67 #define INVALIDATE_LASTREF(a) \
69 if ((a) == lastarray) { \
75 #define SET_LASTREF(a, e) \
81 #define UNSET_LASTREF() \
93 r =(ARRAY *)xmalloc(sizeof(ARRAY));
94 r->type = array_indexed;
97 head = array_create_element(-1, (char *)NULL); /* dummy head */
98 head->prev = head->next = head;
107 register ARRAY_ELEMENT *r, *r1;
111 for (r = element_forw(a->head); r != a->head; ) {
112 r1 = element_forw(r);
113 array_dispose_element(r);
116 a->head->next = a->head->prev = a->head;
119 INVALIDATE_LASTREF(a);
129 array_dispose_element(a->head);
138 ARRAY_ELEMENT *ae, *new;
141 return((ARRAY *) NULL);
144 a1->max_index = a->max_index;
145 a1->num_elements = a->num_elements;
146 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
147 new = array_create_element(element_index(ae), element_value(ae));
148 ADD_BEFORE(a1->head, new);
154 * Make and return a new array composed of the elements in array A from
158 array_slice(array, s, e)
160 ARRAY_ELEMENT *s, *e;
163 ARRAY_ELEMENT *p, *n;
168 a->type = array->type;
170 for (mi = 0, p = s, i = 0; p != e; p = element_forw(p), i++) {
171 n = array_create_element (element_index(p), element_value(p));
172 ADD_BEFORE(a->head, n);
173 mi = element_index(n);
181 * Walk the array, calling FUNC once for each element, with the array
182 * element as the argument.
185 array_walk(a, func, udata)
187 sh_ae_map_func_t *func;
190 register ARRAY_ELEMENT *ae;
192 if (a == 0 || array_empty(a))
194 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
195 if ((*func)(ae, udata) < 0)
200 * Shift the array A N elements to the left. Delete the first N elements
201 * and subtract N from the indices of the remaining elements. If FLAGS
202 * does not include AS_DISPOSE, this returns a singly-linked null-terminated
203 * list of elements so the caller can dispose of the chain. If FLAGS
204 * includes AS_DISPOSE, this function disposes of the shifted-out elements
208 array_shift(a, n, flags)
212 register ARRAY_ELEMENT *ae, *ret;
215 if (a == 0 || array_empty(a) || n <= 0)
216 return ((ARRAY_ELEMENT *)NULL);
218 INVALIDATE_LASTREF(a);
219 for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
222 /* Easy case; shifting out all of the elements */
223 if (flags & AS_DISPOSE) {
225 return ((ARRAY_ELEMENT *)NULL);
227 for (ae = ret; element_forw(ae) != a->head; ae = element_forw(ae))
229 element_forw(ae) = (ARRAY_ELEMENT *)NULL;
230 a->head->next = a->head->prev = a->head;
236 * ae now points to the list of elements we want to retain.
237 * ret points to the list we want to either destroy or return.
239 ae->prev->next = (ARRAY_ELEMENT *)NULL; /* null-terminate RET */
241 a->head->next = ae; /* slice RET out of the array */
244 for ( ; ae != a->head; ae = element_forw(ae))
245 element_index(ae) -= n; /* renumber retained indices */
247 a->num_elements -= n; /* modify bookkeeping information */
248 a->max_index = element_index(a->head->prev);
250 if (flags & AS_DISPOSE) {
251 for (ae = ret; ae; ) {
252 ret = element_forw(ae);
253 array_dispose_element(ae);
256 return ((ARRAY_ELEMENT *)NULL);
263 * Shift array A right N indices. If S is non-null, it becomes the value of
264 * the new element 0. Returns the number of elements in the array after the
268 array_rshift (a, n, s)
273 register ARRAY_ELEMENT *ae, *new;
275 if (a == 0 || (array_empty(a) && s == 0))
278 return (a->num_elements);
280 ae = element_forw(a->head);
282 new = array_create_element(0, s);
285 if (array_num_elements(a) == 1) { /* array was empty */
292 * Renumber all elements in the array except the one we just added.
294 for ( ; ae != a->head; ae = element_forw(ae))
295 element_index(ae) += n;
297 a->max_index = element_index(a->head->prev);
299 INVALIDATE_LASTREF(a);
300 return (a->num_elements);
304 array_unshift_element(a)
307 return (array_shift (a, 1, 0));
311 array_shift_element(a, v)
315 return (array_rshift (a, 1, v));
325 if (array == 0 || array_head(array) == 0 || array_empty(array))
326 return (ARRAY *)NULL;
327 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
328 t = quote_string (a->value);
336 array_quote_escapes(array)
342 if (array == 0 || array_head(array) == 0 || array_empty(array))
343 return (ARRAY *)NULL;
344 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
345 t = quote_escapes (a->value);
359 if (array == 0 || array_head(array) == 0 || array_empty(array))
360 return (ARRAY *)NULL;
361 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
362 t = dequote_string (a->value);
370 array_dequote_escapes(array)
376 if (array == 0 || array_head(array) == 0 || array_empty(array))
377 return (ARRAY *)NULL;
378 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
379 t = dequote_escapes (a->value);
387 array_remove_quoted_nulls(array)
393 if (array == 0 || array_head(array) == 0 || array_empty(array))
394 return (ARRAY *)NULL;
395 for (a = element_forw(array->head); a != array->head; a = element_forw(a))
396 a->value = remove_quoted_nulls (a->value);
401 * Return a string whose elements are the members of array A beginning at
402 * index START and spanning NELEM members. Null elements are counted.
403 * Since arrays are sparse, unset array elements are not counted.
406 array_subrange (a, start, nelem, starsub, quoted)
408 arrayind_t start, nelem;
412 ARRAY_ELEMENT *h, *p;
414 char *ifs, *sifs, *t;
417 p = a ? array_head (a) : 0;
418 if (p == 0 || array_empty (a) || start > array_max_index(a))
419 return ((char *)NULL);
422 * Find element with index START. If START corresponds to an unset
423 * element (arrays can be sparse), use the first element whose index
424 * is >= START. If START is < 0, we count START indices back from
425 * the end of A (not elements, even with sparse arrays -- START is an
428 for (p = element_forw(p); p != array_head(a) && start > element_index(p); p = element_forw(p))
432 return ((char *)NULL);
434 /* Starting at P, take NELEM elements, inclusive. */
435 for (i = 0, h = p; p != a->head && i < nelem; i++, p = element_forw(p))
438 a2 = array_slice(a, h, p);
440 if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))
443 array_quote_escapes(a2);
445 if (starsub && (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))) {
447 array_remove_quoted_nulls (a2);
448 sifs = ifs_firstchar ((int *)NULL);
449 t = array_to_string (a2, sifs, 0);
451 } else if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT)) {
453 sifs = ifs_firstchar (&slen);
455 if (ifs == 0 || *ifs == 0) {
457 sifs = xrealloc(sifs, 2);
461 t = array_to_string (a2, sifs, 0);
464 t = array_to_string (a2, " ", 0);
471 array_patsub (a, pat, rep, mflags)
478 char *t, *sifs, *ifs;
481 if (a == 0 || array_head(a) == 0 || array_empty(a))
482 return ((char *)NULL);
485 for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
486 t = pat_subst(element_value(e), pat, rep, mflags);
487 FREE(element_value(e));
491 if (mflags & MATCH_QUOTED)
494 array_quote_escapes(a2);
496 if (mflags & MATCH_STARSUB) {
497 array_remove_quoted_nulls (a2);
498 sifs = ifs_firstchar((int *)NULL);
499 t = array_to_string (a2, sifs, 0);
501 } else if (mflags & MATCH_QUOTED) {
503 sifs = ifs_firstchar (&slen);
505 if (ifs == 0 || *ifs == 0) {
507 sifs = xrealloc (sifs, 2);
511 t = array_to_string (a2, sifs, 0);
514 t = array_to_string (a2, " ", 0);
521 array_modcase (a, pat, modop, mflags)
529 char *t, *sifs, *ifs;
532 if (a == 0 || array_head(a) == 0 || array_empty(a))
533 return ((char *)NULL);
536 for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
537 t = sh_modcase(element_value(e), pat, modop);
538 FREE(element_value(e));
542 if (mflags & MATCH_QUOTED)
545 array_quote_escapes(a2);
547 if (mflags & MATCH_STARSUB) {
548 array_remove_quoted_nulls (a2);
549 sifs = ifs_firstchar((int *)NULL);
550 t = array_to_string (a2, sifs, 0);
552 } else if (mflags & MATCH_QUOTED) {
554 sifs = ifs_firstchar (&slen);
556 if (ifs == 0 || *ifs == 0) {
558 sifs = xrealloc (sifs, 2);
562 t = array_to_string (a2, sifs, 0);
565 t = array_to_string (a2, " ", 0);
571 * Allocate and return a new array element with index INDEX and value
575 array_create_element(indx, value)
581 r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
583 r->value = value ? savestring(value) : (char *)NULL;
584 r->next = r->prev = (ARRAY_ELEMENT *) NULL;
588 #ifdef INCLUDE_UNUSED
590 array_copy_element(ae)
593 return(ae ? array_create_element(element_index(ae), element_value(ae))
594 : (ARRAY_ELEMENT *) NULL);
599 array_dispose_element(ae)
609 * Add a new element with index I and value V to array A (a[i] = v).
612 array_insert(a, i, v)
617 register ARRAY_ELEMENT *new, *ae, *start;
621 new = array_create_element(i, v);
622 if (i > array_max_index(a)) {
624 * Hook onto the end. This also works for an empty array.
625 * Fast path for the common case of allocating arrays
628 ADD_BEFORE(a->head, new);
634 #if OPTIMIZE_SEQUENTIAL_ARRAY_ASSIGNMENT
636 * Otherwise we search for the spot to insert it. The lastref
637 * handle optimizes the case of sequential or almost-sequential
638 * assignments that are not at the end of the array.
640 start = LASTREF_START(a, i);
642 start = element_forw(ae->head);
644 for (ae = start; ae != a->head; ae = element_forw(ae)) {
645 if (element_index(ae) == i) {
647 * Replacing an existing element.
649 array_dispose_element(new);
650 free(element_value(ae));
651 ae->value = v ? savestring(v) : (char *)NULL;
654 } else if (element_index(ae) > i) {
661 array_dispose_element(new);
662 INVALIDATE_LASTREF(a);
663 return (-1); /* problem */
667 * Delete the element with index I from array A and return it so the
668 * caller can dispose of it.
675 register ARRAY_ELEMENT *ae, *start;
677 if (a == 0 || array_empty(a))
678 return((ARRAY_ELEMENT *) NULL);
679 start = LASTREF_START(a, i);
680 for (ae = start; ae != a->head; ae = element_forw(ae))
681 if (element_index(ae) == i) {
682 ae->next->prev = ae->prev;
683 ae->prev->next = ae->next;
685 if (i == array_max_index(a))
686 a->max_index = element_index(ae->prev);
688 INVALIDATE_LASTREF(a);
690 if (ae->next != a->head)
691 SET_LASTREF(a, ae->next);
692 else if (ae->prev != a->head)
693 SET_LASTREF(a, ae->prev);
695 INVALIDATE_LASTREF(a);
699 return((ARRAY_ELEMENT *) NULL);
703 * Return the value of a[i].
706 array_reference(a, i)
710 register ARRAY_ELEMENT *ae, *start;
712 if (a == 0 || array_empty(a))
713 return((char *) NULL);
714 if (i > array_max_index(a))
715 return((char *)NULL); /* Keep roving pointer into array to optimize sequential access */
716 start = LASTREF_START(a, i);
717 for (ae = start; ae != a->head; ae = element_forw(ae))
718 if (element_index(ae) == i) {
720 return(element_value(ae));
723 return((char *) NULL);
726 /* Convenience routines for the shell to translate to and from the form used
727 by the rest of the code. */
730 array_to_word_list(a)
736 if (a == 0 || array_empty(a))
737 return((WORD_LIST *)NULL);
738 list = (WORD_LIST *)NULL;
739 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
740 list = make_word_list (make_bare_word(element_value(ae)), list);
741 return (REVERSE_LIST(list, WORD_LIST *));
745 array_from_word_list (list)
751 return((ARRAY *)NULL);
753 return (array_assign_list (a, list));
757 array_keys_to_word_list(a)
764 if (a == 0 || array_empty(a))
765 return((WORD_LIST *)NULL);
766 list = (WORD_LIST *)NULL;
767 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
768 t = itos(element_index(ae));
769 list = make_word_list (make_bare_word(t), list);
772 return (REVERSE_LIST(list, WORD_LIST *));
776 array_assign_list (array, list)
780 register WORD_LIST *l;
781 register arrayind_t i;
783 for (l = list, i = 0; l; l = l->next, i++)
784 array_insert(array, i, l->word->word);
796 if (a == 0 || array_empty(a))
797 return ((char **)NULL);
798 ret = strvec_create (array_num_elements (a) + 1);
800 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
801 t = element_value (ae);
802 ret[i++] = t ? savestring (t) : (char *)NULL;
804 ret[i] = (char *)NULL;
809 * Return a string that is the concatenation of the elements in A from START
810 * to END, separated by SEP.
813 array_to_string_internal (start, end, sep, quoted)
814 ARRAY_ELEMENT *start, *end;
820 int slen, rsize, rlen, reg;
822 if (start == end) /* XXX - should not happen */
823 return ((char *)NULL);
827 for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
829 result = (char *)xmalloc (rsize = 64);
830 if (element_value(ae)) {
831 t = quoted ? quote_string(element_value(ae)) : element_value(ae);
833 RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
835 strcpy(result + rlen, t);
840 * Add a separator only after non-null elements.
842 if (element_forw(ae) != end) {
843 strcpy(result + rlen, sep);
849 result[rlen] = '\0'; /* XXX */
854 array_to_assign (a, quoted)
858 char *result, *valstr, *is;
859 char indstr[INT_STRLEN_BOUND(intmax_t) + 1];
861 int rsize, rlen, elen;
863 if (a == 0 || array_empty (a))
864 return((char *)NULL);
866 result = (char *)xmalloc (rsize = 128);
870 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
871 is = inttostr (element_index(ae), indstr, sizeof(indstr));
872 valstr = element_value (ae) ? sh_double_quote (element_value(ae))
874 elen = STRLEN (is) + 8 + STRLEN (valstr);
875 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
877 result[rlen++] = '[';
878 strcpy (result + rlen, is);
880 result[rlen++] = ']';
881 result[rlen++] = '=';
883 strcpy (result + rlen, valstr);
884 rlen += STRLEN (valstr);
887 if (element_forw(ae) != a->head)
888 result[rlen++] = ' ';
892 RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
893 result[rlen++] = ')';
896 /* This is not as efficient as it could be... */
897 valstr = sh_single_quote (result);
905 array_to_string (a, sep, quoted)
911 return((char *)NULL);
913 return(savestring(""));
914 return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
917 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
919 * Return an array consisting of elements in S, separated by SEP
922 array_from_string(s, sep)
929 return((ARRAY *)NULL);
930 w = list_string (s, sep, 0);
932 return((ARRAY *)NULL);
933 a = array_from_word_list (w);
938 #if defined (TEST_ARRAY)
940 * To make a running version, compile -DTEST_ARRAY and link with:
941 * xmalloc.o syntax.o lib/malloc/libmalloc.a lib/sh/libsh.a
943 int interrupt_immediately = 0;
953 fatal_error(const char *s, ...)
955 fprintf(stderr, "array_test: fatal memory error\n");
960 programming_error(const char *s, ...)
962 fprintf(stderr, "array_test: fatal programming error\n");
972 w = (WORD_DESC *)xmalloc(sizeof(WORD_DESC));
973 w->word = s ? savestring(s) : savestring ("");
985 w = (WORD_LIST *)xmalloc(sizeof(WORD_LIST));
1000 return (WORD_LIST *)NULL;
1002 wl = (WORD_LIST *)NULL;
1005 wl = make_word_list (make_bare_word(a), wl);
1006 a = strtok((char *)NULL, t);
1008 return (REVERSE_LIST (wl, WORD_LIST *));
1015 register GENERIC_LIST *next, *prev;
1017 for (prev = 0; list; ) {
1027 pat_subst(s, t, u, i)
1031 return ((char *)NULL);
1038 return savestring(s);
1044 char lbuf[INT_STRLEN_BOUND (intmax_t) + 1];
1046 printf("array[%s] = %s\n",
1047 inttostr (element_index(ae), lbuf, sizeof (lbuf)),
1055 array_walk(a, print_element, (void *)NULL);
1060 ARRAY *a, *new_a, *copy_of_a;
1061 ARRAY_ELEMENT *ae, *aew;
1065 array_insert(a, 1, "one");
1066 array_insert(a, 7, "seven");
1067 array_insert(a, 4, "four");
1068 array_insert(a, 1029, "one thousand twenty-nine");
1069 array_insert(a, 12, "twelve");
1070 array_insert(a, 42, "forty-two");
1072 s = array_to_string (a, " ", 0);
1073 printf("s = %s\n", s);
1074 copy_of_a = array_from_string(s, " ");
1075 printf("copy_of_a:");
1076 print_array(copy_of_a);
1077 array_dispose(copy_of_a);
1080 ae = array_remove(a, 4);
1081 array_dispose_element(ae);
1082 ae = array_remove(a, 1029);
1083 array_dispose_element(ae);
1084 array_insert(a, 16, "sixteen");
1086 s = array_to_string (a, " ", 0);
1087 printf("s = %s\n", s);
1088 copy_of_a = array_from_string(s, " ");
1089 printf("copy_of_a:");
1090 print_array(copy_of_a);
1091 array_dispose(copy_of_a);
1094 array_insert(a, 2, "two");
1095 array_insert(a, 1029, "new one thousand twenty-nine");
1096 array_insert(a, 0, "zero");
1097 array_insert(a, 134, "");
1099 s = array_to_string (a, ":", 0);
1100 printf("s = %s\n", s);
1101 copy_of_a = array_from_string(s, ":");
1102 printf("copy_of_a:");
1103 print_array(copy_of_a);
1104 array_dispose(copy_of_a);
1107 new_a = array_copy(a);
1109 s = array_to_string (new_a, ":", 0);
1110 printf("s = %s\n", s);
1111 copy_of_a = array_from_string(s, ":");
1113 printf("copy_of_a:");
1114 print_array(copy_of_a);
1115 array_shift(copy_of_a, 2, AS_DISPOSE);
1116 printf("copy_of_a shifted by two:");
1117 print_array(copy_of_a);
1118 ae = array_shift(copy_of_a, 2, 0);
1119 printf("copy_of_a shifted by two:");
1120 print_array(copy_of_a);
1122 aew = element_forw(ae);
1123 array_dispose_element(ae);
1126 array_rshift(copy_of_a, 1, (char *)0);
1127 printf("copy_of_a rshift by 1:");
1128 print_array(copy_of_a);
1129 array_rshift(copy_of_a, 2, "new element zero");
1130 printf("copy_of_a rshift again by 2 with new element zero:");
1131 print_array(copy_of_a);
1132 s = array_to_assign(copy_of_a, 0);
1133 printf("copy_of_a=%s\n", s);
1135 ae = array_shift(copy_of_a, array_num_elements(copy_of_a), 0);
1137 aew = element_forw(ae);
1138 array_dispose_element(ae);
1141 array_dispose(copy_of_a);
1144 array_dispose(new_a);
1147 #endif /* TEST_ARRAY */
1148 #endif /* ARRAY_VARS */