]>
git.ipfire.org Git - thirdparty/bash.git/blob - array.c
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 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 extern char *quote_string (); /* XXX */
50 #define ADD_BEFORE(ae, new) \
52 ae->prev->next = new; \
53 new->prev = ae->prev; \
59 * Allocate and return a new array element with index INDEX and value
63 new_array_element(indx
, value
)
69 r
= (ARRAY_ELEMENT
*) xmalloc(sizeof(ARRAY_ELEMENT
));
71 r
->value
= value
? savestring(value
) : (char *)NULL
;
72 r
->next
= r
->prev
= (ARRAY_ELEMENT
*) NULL
;
77 destroy_array_element(ae
)
90 r
=(ARRAY
*) xmalloc(sizeof(ARRAY
));
91 r
->type
= array_indexed
;
92 r
->max_index
= r
->max_size
= -1;
94 head
= new_array_element(-1, (char *)NULL
); /* dummy head */
95 head
->prev
= head
->next
= head
;
104 register ARRAY_ELEMENT
*r
, *r1
;
108 for (r
= element_forw(a
->head
); r
!= a
->head
; ) {
109 r1
= element_forw(r
);
110 destroy_array_element(r
);
113 a
->head
->next
= a
->head
->prev
= a
->head
;
114 a
->max_index
= a
->max_size
= -1;
115 a
->num_elements
= a
->max_size
= 0;
125 destroy_array_element(a
->head
);
134 ARRAY_ELEMENT
*ae
, *new;
137 return((ARRAY
*) NULL
);
140 a1
->max_index
= a
->max_index
;
141 a1
->num_elements
= a
->num_elements
;
142 a1
->max_size
= a
->max_size
;
143 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
144 new = new_array_element(element_index(ae
), element_value(ae
));
145 ADD_BEFORE(a1
->head
, new);
150 #ifdef INCLUDE_UNUSED
152 * Make and return a new array composed of the elements in array A from
156 dup_array_subrange(array
, s
, e
)
158 ARRAY_ELEMENT
*s
, *e
;
161 ARRAY_ELEMENT
*p
, *n
;
165 a
->type
= array
->type
;
167 for (p
= s
, i
= 0; p
!= e
; p
= element_forw(p
), i
++) {
168 n
= new_array_element (i
, element_value(p
));
169 ADD_BEFORE(a
->head
, n
);
171 a
->num_elements
= a
->max_index
= i
;
176 #ifdef INCLUDE_UNUSED
178 copy_array_element(ae
)
181 return(ae
? new_array_element(element_index(ae
), element_value(ae
))
182 : (ARRAY_ELEMENT
*) NULL
);
187 * Add a new element with index I and value V to array A (a[i] = v).
190 array_add_element(a
, i
, v
)
195 register ARRAY_ELEMENT
*new, *ae
;
199 new = new_array_element(i
, v
);
200 if (i
> array_max_index(a
)) {
202 * Hook onto the end. This also works for an empty array.
203 * Fast path for the common case of allocating arrays
206 ADD_BEFORE(a
->head
, new);
212 * Otherwise we search for the spot to insert it.
214 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
215 if (element_index(ae
) == i
) {
217 * Replacing an existing element.
219 destroy_array_element(new);
220 free(element_value(ae
));
221 ae
->value
= savestring(v
);
223 } else if (element_index(ae
) > i
) {
229 return (-1); /* problem */
233 * Delete the element with index I from array A and return it so the
234 * caller can dispose of it.
237 array_delete_element(a
, i
)
241 register ARRAY_ELEMENT
*ae
;
243 if (!a
|| array_empty(a
))
244 return((ARRAY_ELEMENT
*) NULL
);
245 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
246 if (element_index(ae
) == i
) {
247 ae
->next
->prev
= ae
->prev
;
248 ae
->prev
->next
= ae
->next
;
250 if (i
== array_max_index(a
))
251 a
->max_index
= element_index(ae
->prev
);
254 return((ARRAY_ELEMENT
*) NULL
);
258 * Return the value of a[i].
261 array_reference(a
, i
)
265 register ARRAY_ELEMENT
*ae
;
267 if (a
== 0 || array_empty(a
))
268 return((char *) NULL
);
269 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
270 if (element_index(ae
) == i
)
271 return(element_value(ae
));
272 return((char *) NULL
);
277 * Walk the array, calling FUNC once for each element, with the array
278 * element as the argument.
285 register ARRAY_ELEMENT
*ae
;
287 if (a
== 0 || array_empty(a
))
289 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
295 * Return a string that is the concatenation of all the elements in A,
299 array_to_string_internal (start
, end
, sep
, quoted
)
300 ARRAY_ELEMENT
*start
, *end
;
306 int slen
, rsize
, rlen
, reg
;
308 if (start
== end
) /* XXX - should not happen */
309 return ((char *)NULL
);
312 for (rsize
= rlen
= 0, ae
= start
; ae
!= end
; ae
= element_forw(ae
)) {
314 result
= xmalloc (rsize
= 64);
315 if (element_value(ae
)) {
316 t
= quoted
? quote_string(element_value(ae
)) : element_value(ae
);
318 RESIZE_MALLOCED_BUFFER (result
, rlen
, (reg
+ slen
+ 2),
320 strcpy(result
+ rlen
, t
);
325 * Add a separator only after non-null elements.
327 if (element_forw(ae
) != end
) {
328 strcpy(result
+ rlen
, sep
);
333 result
[rlen
] = '\0'; /* XXX */
338 array_to_string (a
, sep
, quoted
)
344 return((char *)NULL
);
346 return(savestring(""));
347 return (array_to_string_internal (element_forw(a
->head
), a
->head
, sep
, quoted
));
351 array_to_assignment_string (a
)
354 char *result
, *indstr
, *valstr
;
356 int rsize
, rlen
, elen
;
358 if (a
== 0 || array_empty (a
))
359 return((char *)NULL
);
361 result
= xmalloc (rsize
= 128);
365 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
366 indstr
= itos (element_index(ae
));
367 valstr
= element_value (ae
) ? double_quote (element_value(ae
))
369 elen
= STRLEN (indstr
) + 8 + STRLEN (valstr
);
370 RESIZE_MALLOCED_BUFFER (result
, rlen
, (elen
+ 1), rsize
, rsize
);
372 result
[rlen
++] = '[';
373 strcpy (result
+ rlen
, indstr
);
374 rlen
+= STRLEN (indstr
);
375 result
[rlen
++] = ']';
376 result
[rlen
++] = '=';
378 strcpy (result
+ rlen
, valstr
);
379 rlen
+= STRLEN (valstr
);
382 if (element_forw(ae
) != a
->head
)
383 result
[rlen
++] = ' ';
388 RESIZE_MALLOCED_BUFFER (result
, rlen
, 1, rsize
, 8);
389 result
[rlen
++] = ')';
395 quoted_array_assignment_string (a
)
400 sv
= array_to_assignment_string (a
);
402 return ((char *)NULL
);
404 vstr
= single_quote (sv
);
410 /* Determine if s2 occurs in s1. If so, return a pointer to the
411 match in s1. The compare is case sensitive. */
414 register char *s1
, *s2
;
416 register int i
, l
, len
;
418 for (i
= 0, l
= strlen(s2
), len
= strlen(s1
); (len
- i
) >= l
; i
++)
419 if (strncmp (s1
+ i
, s2
, l
) == 0)
421 return ((char *)NULL
);
425 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
427 * Return an array consisting of elements in S, separated by SEP
430 string_to_array(s
, sep
)
437 return((ARRAY
*)NULL
);
438 w
= list_string (s
, sep
, 0);
440 return((ARRAY
*)NULL
);
441 a
= word_list_to_array (w
);
446 /* Convenience routines for the shell to translate to and from the form used
447 by the rest of the code. */
449 array_to_word_list(a
)
455 if (a
== 0 || array_empty(a
))
456 return((WORD_LIST
*)NULL
);
457 list
= (WORD_LIST
*)NULL
;
458 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
459 list
= make_word_list (make_bare_word(element_value(ae
)), list
);
460 return (REVERSE_LIST(list
, WORD_LIST
*));
471 if (a
== 0 || array_empty(a
))
472 return ((char **)NULL
);
473 ret
= alloc_array (array_num_elements (a
) + 1);
475 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
476 t
= element_value (ae
);
477 ret
[i
++] = t
? savestring (t
) : (char *)NULL
;
479 ret
[i
] = (char *)NULL
;
484 assign_word_list (array
, list
)
488 register WORD_LIST
*l
;
489 register arrayind_t i
;
491 for (l
= list
, i
= 0; l
; l
= l
->next
, i
++)
492 array_add_element(array
, i
, l
->word
->word
);
497 word_list_to_array (list
)
503 return((ARRAY
*)NULL
);
505 return (assign_word_list (a
, list
));
515 if (array
== 0 || array
->head
== 0 || array_empty (array
))
516 return (ARRAY
*)NULL
;
517 for (a
= element_forw(array
->head
); a
!= array
->head
; a
= element_forw(a
)) {
518 t
= quote_string (a
->value
);
526 array_subrange (a
, start
, end
, quoted
)
528 int start
, end
, quoted
;
530 ARRAY_ELEMENT
*h
, *p
;
534 if (p
== 0 || array_empty (a
) || start
> array_num_elements (a
))
535 return ((char *)NULL
);
537 for (i
= 0, p
= element_forw(p
); p
!= a
->head
&& i
< start
; i
++, p
= element_forw(p
))
540 return ((char *)NULL
);
541 for (h
= p
; p
!= a
->head
&& i
< end
; i
++, p
= element_forw(p
))
544 return (array_to_string_internal (h
, p
, " ", quoted
));
548 array_pat_subst (a
, pat
, rep
, mflags
)
557 if (array_head (a
) == 0 || array_empty (a
))
558 return ((char *)NULL
);
561 for (e
= element_forw(a2
->head
); e
!= a2
->head
; e
= element_forw(e
)) {
562 t
= pat_subst(element_value(e
), pat
, rep
, mflags
);
563 FREE(element_value(e
));
567 if (mflags
& MATCH_QUOTED
)
569 t
= array_to_string (a2
, " ", 0);
576 #if defined (TEST_ARRAY)
580 printf("array[%d] = %s\n",(int)element_index(ae
), element_value(ae
));
587 array_walk(a
, print_element
);
592 ARRAY
*a
, *new_a
, *copy_of_a
;
597 array_add_element(a
, 1, "one");
598 array_add_element(a
, 7, "seven");
599 array_add_element(a
, 4, "four");
600 array_add_element(a
, 1029, "one thousand twenty-nine");
601 array_add_element(a
, 12, "twelve");
602 array_add_element(a
, 42, "forty-two");
604 s
= array_to_string (a
, " ", 0);
605 printf("s = %s\n", s
);
606 copy_of_a
= string_to_array(s
, " ");
607 printf("copy_of_a:");
608 print_array(copy_of_a
);
609 dispose_array(copy_of_a
);
612 ae
= array_delete_element(a
, 4);
613 destroy_array_element(ae
);
614 ae
= array_delete_element(a
, 1029);
615 destroy_array_element(ae
);
616 array_add_element(a
, 16, "sixteen");
618 s
= array_to_string (a
, " ", 0);
619 printf("s = %s\n", s
);
620 copy_of_a
= string_to_array(s
, " ");
621 printf("copy_of_a:");
622 print_array(copy_of_a
);
623 dispose_array(copy_of_a
);
626 array_add_element(a
, 2, "two");
627 array_add_element(a
, 1029, "new one thousand twenty-nine");
628 array_add_element(a
, 0, "zero");
629 array_add_element(a
, 134, "");
631 s
= array_to_string (a
, ":", 0);
632 printf("s = %s\n", s
);
633 copy_of_a
= string_to_array(s
, ":");
634 printf("copy_of_a:");
635 print_array(copy_of_a
);
636 dispose_array(copy_of_a
);
639 new_a
= copy_array(a
);
641 s
= array_to_string (new_a
, ":", 0);
642 printf("s = %s\n", s
);
643 copy_of_a
= string_to_array(s
, ":", 0);
644 printf("copy_of_a:");
645 print_array(copy_of_a
);
646 dispose_array(copy_of_a
);
650 dispose_array(new_a
);
653 #endif /* TEST_ARRAY */
654 #endif /* ARRAY_VARS */