]>
git.ipfire.org Git - thirdparty/bash.git/blob - array.c
a73be55a8afe2c24084f8990b8a63ab5c5faf252
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-2002 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.
159 sh_ae_map_func_t
*func
;
161 register ARRAY_ELEMENT
*ae
;
163 if (a
== 0 || array_empty(a
))
165 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
171 * Shift the array A N elements to the left. Delete the first N elements
172 * and subtract N from the indices of the remaining elements. If FLAGS
173 * does not include AS_DISPOSE, this returns a singly-linked null-terminated
174 * list of elements so the caller can dispose of the chain. If FLAGS
175 * includes AS_DISPOSE, this function disposes of the shifted-out elements
179 array_shift(a
, n
, flags
)
183 register ARRAY_ELEMENT
*ae
, *ret
;
186 if (a
== 0 || array_empty(a
) || n
<= 0)
187 return ((ARRAY_ELEMENT
*)NULL
);
189 for (i
= 0, ret
= ae
= element_forw(a
->head
); ae
!= a
->head
&& i
< n
; ae
= element_forw(ae
), i
++)
192 /* Easy case; shifting out all of the elements */
193 if (flags
& AS_DISPOSE
) {
195 return ((ARRAY_ELEMENT
*)NULL
);
197 for (ae
= ret
; element_forw(ae
) != a
->head
; ae
= element_forw(ae
))
199 element_forw(ae
) = (ARRAY_ELEMENT
*)NULL
;
200 a
->head
->next
= a
->head
->prev
= a
->head
;
206 * ae now points to the list of elements we want to retain.
207 * ret points to the list we want to either destroy or return.
209 ae
->prev
->next
= (ARRAY_ELEMENT
*)NULL
; /* null-terminate RET */
211 a
->head
->next
= ae
; /* slice RET out of the array */
214 for ( ; ae
!= a
->head
; ae
= element_forw(ae
))
215 element_index(ae
) -= n
; /* renumber retained indices */
217 a
->num_elements
-= n
; /* modify bookkeeping information */
220 if (flags
& AS_DISPOSE
) {
221 for (ae
= ret
; ae
; ) {
222 ret
= element_forw(ae
);
223 array_dispose_element(ae
);
226 return ((ARRAY_ELEMENT
*)NULL
);
233 * Shift array A right N indices. If S is non-null, it becomes the value of
234 * the new element 0. Returns the number of elements in the array after the
238 array_rshift (a
, n
, s
)
243 register ARRAY_ELEMENT
*ae
, *new;
248 return (a
->num_elements
);
250 ae
= element_forw(a
->head
);
252 new = array_create_element(0, s
);
260 * Renumber all elements in the array except the one we just added.
262 for ( ; ae
!= a
->head
; ae
= element_forw(ae
))
263 element_index(ae
) += n
;
265 return (a
->num_elements
);
275 if (array
== 0 || array
->head
== 0 || array_empty (array
))
276 return (ARRAY
*)NULL
;
277 for (a
= element_forw(array
->head
); a
!= array
->head
; a
= element_forw(a
)) {
278 t
= quote_string (a
->value
);
286 array_subrange (a
, start
, end
, quoted
)
288 arrayind_t start
, end
;
291 ARRAY_ELEMENT
*h
, *p
;
295 if (p
== 0 || array_empty (a
) || start
> array_num_elements (a
))
296 return ((char *)NULL
);
298 for (i
= 0, p
= element_forw(p
); p
!= a
->head
&& i
< start
; i
++, p
= element_forw(p
))
301 return ((char *)NULL
);
302 for (h
= p
; p
!= a
->head
&& i
< end
; i
++, p
= element_forw(p
))
305 return (array_to_string_internal (h
, p
, " ", quoted
));
309 array_patsub (a
, pat
, rep
, mflags
)
318 if (array_head (a
) == 0 || array_empty (a
))
319 return ((char *)NULL
);
322 for (e
= element_forw(a2
->head
); e
!= a2
->head
; e
= element_forw(e
)) {
323 t
= pat_subst(element_value(e
), pat
, rep
, mflags
);
324 FREE(element_value(e
));
328 if (mflags
& MATCH_QUOTED
)
330 t
= array_to_string (a2
, " ", 0);
337 * Allocate and return a new array element with index INDEX and value
341 array_create_element(indx
, value
)
347 r
= (ARRAY_ELEMENT
*)xmalloc(sizeof(ARRAY_ELEMENT
));
349 r
->value
= value
? savestring(value
) : (char *)NULL
;
350 r
->next
= r
->prev
= (ARRAY_ELEMENT
*) NULL
;
354 #ifdef INCLUDE_UNUSED
356 array_copy_element(ae
)
359 return(ae
? array_create_element(element_index(ae
), element_value(ae
))
360 : (ARRAY_ELEMENT
*) NULL
);
365 array_dispose_element(ae
)
373 * Add a new element with index I and value V to array A (a[i] = v).
376 array_insert(a
, i
, v
)
381 register ARRAY_ELEMENT
*new, *ae
;
385 new = array_create_element(i
, v
);
386 if (i
> array_max_index(a
)) {
388 * Hook onto the end. This also works for an empty array.
389 * Fast path for the common case of allocating arrays
392 ADD_BEFORE(a
->head
, new);
398 * Otherwise we search for the spot to insert it.
400 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
401 if (element_index(ae
) == i
) {
403 * Replacing an existing element.
405 array_dispose_element(new);
406 free(element_value(ae
));
407 ae
->value
= savestring(v
);
409 } else if (element_index(ae
) > i
) {
415 return (-1); /* problem */
419 * Delete the element with index I from array A and return it so the
420 * caller can dispose of it.
427 register ARRAY_ELEMENT
*ae
;
429 if (!a
|| array_empty(a
))
430 return((ARRAY_ELEMENT
*) NULL
);
431 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
432 if (element_index(ae
) == i
) {
433 ae
->next
->prev
= ae
->prev
;
434 ae
->prev
->next
= ae
->next
;
436 if (i
== array_max_index(a
))
437 a
->max_index
= element_index(ae
->prev
);
440 return((ARRAY_ELEMENT
*) NULL
);
444 * Return the value of a[i].
447 array_reference(a
, i
)
451 register ARRAY_ELEMENT
*ae
;
453 if (a
== 0 || array_empty(a
))
454 return((char *) NULL
);
455 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
456 if (element_index(ae
) == i
)
457 return(element_value(ae
));
458 return((char *) NULL
);
461 /* Convenience routines for the shell to translate to and from the form used
462 by the rest of the code. */
464 array_to_word_list(a
)
470 if (a
== 0 || array_empty(a
))
471 return((WORD_LIST
*)NULL
);
472 list
= (WORD_LIST
*)NULL
;
473 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
474 list
= make_word_list (make_bare_word(element_value(ae
)), list
);
475 return (REVERSE_LIST(list
, WORD_LIST
*));
479 array_from_word_list (list
)
485 return((ARRAY
*)NULL
);
487 return (array_assign_list (a
, list
));
491 array_assign_list (array
, list
)
495 register WORD_LIST
*l
;
496 register arrayind_t i
;
498 for (l
= list
, i
= 0; l
; l
= l
->next
, i
++)
499 array_insert(array
, i
, l
->word
->word
);
511 if (a
== 0 || array_empty(a
))
512 return ((char **)NULL
);
513 ret
= strvec_create (array_num_elements (a
) + 1);
515 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
516 t
= element_value (ae
);
517 ret
[i
++] = t
? savestring (t
) : (char *)NULL
;
519 ret
[i
] = (char *)NULL
;
524 * Return a string that is the concatenation of all the elements in A,
528 array_to_string_internal (start
, end
, sep
, quoted
)
529 ARRAY_ELEMENT
*start
, *end
;
535 int slen
, rsize
, rlen
, reg
;
537 if (start
== end
) /* XXX - should not happen */
538 return ((char *)NULL
);
542 for (rsize
= rlen
= 0, ae
= start
; ae
!= end
; ae
= element_forw(ae
)) {
544 result
= (char *)xmalloc (rsize
= 64);
545 if (element_value(ae
)) {
546 t
= quoted
? quote_string(element_value(ae
)) : element_value(ae
);
548 RESIZE_MALLOCED_BUFFER (result
, rlen
, (reg
+ slen
+ 2),
550 strcpy(result
+ rlen
, t
);
555 * Add a separator only after non-null elements.
557 if (element_forw(ae
) != end
) {
558 strcpy(result
+ rlen
, sep
);
564 result
[rlen
] = '\0'; /* XXX */
569 array_to_assign (a
, quoted
)
573 char *result
, *valstr
, *is
;
574 char indstr
[INT_STRLEN_BOUND(intmax_t) + 1];
576 int rsize
, rlen
, elen
;
578 if (a
== 0 || array_empty (a
))
579 return((char *)NULL
);
581 result
= (char *)xmalloc (rsize
= 128);
585 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
586 is
= inttostr (element_index(ae
), indstr
, sizeof(indstr
));
587 valstr
= element_value (ae
) ? sh_double_quote (element_value(ae
))
589 elen
= STRLEN (indstr
) + 8 + STRLEN (valstr
);
590 RESIZE_MALLOCED_BUFFER (result
, rlen
, (elen
+ 1), rsize
, rsize
);
592 result
[rlen
++] = '[';
593 strcpy (result
+ rlen
, is
);
595 result
[rlen
++] = ']';
596 result
[rlen
++] = '=';
598 strcpy (result
+ rlen
, valstr
);
599 rlen
+= STRLEN (valstr
);
602 if (element_forw(ae
) != a
->head
)
603 result
[rlen
++] = ' ';
607 RESIZE_MALLOCED_BUFFER (result
, rlen
, 1, rsize
, 8);
608 result
[rlen
++] = ')';
611 /* This is not as efficient as it could be... */
612 valstr
= sh_single_quote (result
);
620 array_to_string (a
, sep
, quoted
)
626 return((char *)NULL
);
628 return(savestring(""));
629 return (array_to_string_internal (element_forw(a
->head
), a
->head
, sep
, quoted
));
632 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
634 * Return an array consisting of elements in S, separated by SEP
637 array_from_string(s
, sep
)
644 return((ARRAY
*)NULL
);
645 w
= list_string (s
, sep
, 0);
647 return((ARRAY
*)NULL
);
648 a
= array_from_word_list (w
);
653 #if defined (TEST_ARRAY)
655 * To make a running version, compile -DTEST_ARRAY and link with:
656 * xmalloc.o syntax.o lib/malloc/libmalloc.a lib/sh/libsh.a
658 int interrupt_immediately
= 0;
668 fatal_error(const char *s
, ...)
670 fprintf(stderr
, "array_test: fatal memory error\n");
675 programming_error(const char *s
, ...)
677 fprintf(stderr
, "array_test: fatal programming error\n");
687 w
= (WORD_DESC
*)xmalloc(sizeof(WORD_DESC
));
688 w
->word
= s
? savestring(s
) : savestring ("");
700 w
= (WORD_LIST
*)xmalloc(sizeof(WORD_LIST
));
715 return (WORD_LIST
*)NULL
;
717 wl
= (WORD_LIST
*)NULL
;
720 wl
= make_word_list (make_bare_word(a
), wl
);
721 a
= strtok((char *)NULL
, t
);
723 return (REVERSE_LIST (wl
, WORD_LIST
*));
730 register GENERIC_LIST
*next
, *prev
;
732 for (prev
= 0; list
; ) {
742 pat_subst(s
, t
, u
, i
)
746 return ((char *)NULL
);
753 return savestring(s
);
759 char lbuf
[INT_STRLEN_BOUND (intmax_t) + 1];
761 printf("array[%s] = %s\n",
762 inttostr (element_index(ae
), lbuf
, sizeof (lbuf
)),
770 array_walk(a
, print_element
);
775 ARRAY
*a
, *new_a
, *copy_of_a
;
776 ARRAY_ELEMENT
*ae
, *aew
;
780 array_insert(a
, 1, "one");
781 array_insert(a
, 7, "seven");
782 array_insert(a
, 4, "four");
783 array_insert(a
, 1029, "one thousand twenty-nine");
784 array_insert(a
, 12, "twelve");
785 array_insert(a
, 42, "forty-two");
787 s
= array_to_string (a
, " ", 0);
788 printf("s = %s\n", s
);
789 copy_of_a
= array_from_string(s
, " ");
790 printf("copy_of_a:");
791 print_array(copy_of_a
);
792 array_dispose(copy_of_a
);
795 ae
= array_remove(a
, 4);
796 array_dispose_element(ae
);
797 ae
= array_remove(a
, 1029);
798 array_dispose_element(ae
);
799 array_insert(a
, 16, "sixteen");
801 s
= array_to_string (a
, " ", 0);
802 printf("s = %s\n", s
);
803 copy_of_a
= array_from_string(s
, " ");
804 printf("copy_of_a:");
805 print_array(copy_of_a
);
806 array_dispose(copy_of_a
);
809 array_insert(a
, 2, "two");
810 array_insert(a
, 1029, "new one thousand twenty-nine");
811 array_insert(a
, 0, "zero");
812 array_insert(a
, 134, "");
814 s
= array_to_string (a
, ":", 0);
815 printf("s = %s\n", s
);
816 copy_of_a
= array_from_string(s
, ":");
817 printf("copy_of_a:");
818 print_array(copy_of_a
);
819 array_dispose(copy_of_a
);
822 new_a
= array_copy(a
);
824 s
= array_to_string (new_a
, ":", 0);
825 printf("s = %s\n", s
);
826 copy_of_a
= array_from_string(s
, ":");
828 printf("copy_of_a:");
829 print_array(copy_of_a
);
830 array_shift(copy_of_a
, 2, AS_DISPOSE
);
831 printf("copy_of_a shifted by two:");
832 print_array(copy_of_a
);
833 ae
= array_shift(copy_of_a
, 2, 0);
834 printf("copy_of_a shifted by two:");
835 print_array(copy_of_a
);
837 aew
= element_forw(ae
);
838 array_dispose_element(ae
);
841 array_rshift(copy_of_a
, 1, (char *)0);
842 printf("copy_of_a rshift by 1:");
843 print_array(copy_of_a
);
844 array_rshift(copy_of_a
, 2, "new element zero");
845 printf("copy_of_a rshift again by 2 with new element zero:");
846 print_array(copy_of_a
);
847 s
= array_to_assign(copy_of_a
, 0);
848 printf("copy_of_a=%s\n", s
);
850 ae
= array_shift(copy_of_a
, array_num_elements(copy_of_a
), 0);
852 aew
= element_forw(ae
);
853 array_dispose_element(ae
);
856 array_dispose(copy_of_a
);
859 array_dispose(new_a
);
862 #endif /* TEST_ARRAY */
863 #endif /* ARRAY_VARS */