]>
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
13 #if defined (ARRAY_VARS)
15 #if defined (HAVE_UNISTD_H)
17 # include <sys/types.h>
27 #include "builtins/common.h"
29 extern char *quote_string (); /* XXX */
31 #define ADD_BEFORE(ae, new) \
33 ae->prev->next = new; \
34 new->prev = ae->prev; \
40 * Allocate and return a new array element with index INDEX and value
44 new_array_element(indx
, value
)
50 r
= (ARRAY_ELEMENT
*) xmalloc(sizeof(ARRAY_ELEMENT
));
52 r
->value
= value
? savestring(value
) : (char *)NULL
;
53 r
->next
= r
->prev
= (ARRAY_ELEMENT
*) NULL
;
58 destroy_array_element(ae
)
71 r
=(ARRAY
*) xmalloc(sizeof(ARRAY
));
72 r
->type
= array_indexed
;
73 r
->max_index
= r
->max_size
= -1;
75 head
= new_array_element(-1, (char *)NULL
); /* dummy head */
76 head
->prev
= head
->next
= head
;
85 register ARRAY_ELEMENT
*r
, *r1
;
89 for (r
= element_forw(a
->head
); r
!= a
->head
; ) {
91 destroy_array_element(r
);
94 a
->head
->next
= a
->head
->prev
= a
->head
;
95 a
->max_index
= a
->max_size
= -1;
96 a
->num_elements
= a
->max_size
= 0;
106 destroy_array_element(a
->head
);
115 ARRAY_ELEMENT
*ae
, *new;
118 return((ARRAY
*) NULL
);
121 a1
->max_index
= a
->max_index
;
122 a1
->num_elements
= a
->num_elements
;
123 a1
->max_size
= a
->max_size
;
124 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
125 new = new_array_element(element_index(ae
), element_value(ae
));
126 ADD_BEFORE(a1
->head
, new);
131 #ifdef INCLUDE_UNUSED
133 * Make and return a new array composed of the elements in array A from
137 dup_array_subrange(array
, s
, e
)
139 ARRAY_ELEMENT
*s
, *e
;
142 ARRAY_ELEMENT
*p
, *n
;
146 a
->type
= array
->type
;
148 for (p
= s
, i
= 0; p
!= e
; p
= element_forw(p
), i
++) {
149 n
= new_array_element (i
, element_value(p
));
150 ADD_BEFORE(a
->head
, n
);
152 a
->num_elements
= a
->max_index
= i
;
157 #ifdef INCLUDE_UNUSED
159 copy_array_element(ae
)
162 return(ae
? new_array_element(element_index(ae
), element_value(ae
))
163 : (ARRAY_ELEMENT
*) NULL
);
168 * Add a new element with index I and value V to array A (a[i] = v).
171 array_add_element(a
, i
, v
)
176 register ARRAY_ELEMENT
*new, *ae
;
180 new = new_array_element(i
, v
);
181 if (i
> array_max_index(a
)) {
183 * Hook onto the end. This also works for an empty array.
184 * Fast path for the common case of allocating arrays
187 ADD_BEFORE(a
->head
, new);
193 * Otherwise we search for the spot to insert it.
195 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
196 if (element_index(ae
) == i
) {
198 * Replacing an existing element.
200 destroy_array_element(new);
201 free(element_value(ae
));
202 ae
->value
= savestring(v
);
204 } else if (element_index(ae
) > i
) {
210 return (-1); /* problem */
214 * Delete the element with index I from array A and return it so the
215 * caller can dispose of it.
218 array_delete_element(a
, i
)
222 register ARRAY_ELEMENT
*ae
;
224 if (!a
|| array_empty(a
))
225 return((ARRAY_ELEMENT
*) NULL
);
226 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
227 if (element_index(ae
) == i
) {
228 ae
->next
->prev
= ae
->prev
;
229 ae
->prev
->next
= ae
->next
;
231 if (i
== array_max_index(a
))
232 a
->max_index
= element_index(ae
->prev
);
235 return((ARRAY_ELEMENT
*) NULL
);
239 * Return the value of a[i].
242 array_reference(a
, i
)
246 register ARRAY_ELEMENT
*ae
;
248 if (a
== 0 || array_empty(a
))
249 return((char *) NULL
);
250 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
251 if (element_index(ae
) == i
)
252 return(element_value(ae
));
253 return((char *) NULL
);
258 * Walk the array, calling FUNC once for each element, with the array
259 * element as the argument.
266 register ARRAY_ELEMENT
*ae
;
268 if (a
== 0 || array_empty(a
))
270 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
276 * Return a string that is the concatenation of all the elements in A,
280 array_to_string_internal (start
, end
, sep
, quoted
)
281 ARRAY_ELEMENT
*start
, *end
;
287 int slen
, rsize
, rlen
, reg
;
289 if (start
== end
) /* XXX - should not happen */
290 return ((char *)NULL
);
293 for (rsize
= rlen
= 0, ae
= start
; ae
!= end
; ae
= element_forw(ae
)) {
295 result
= xmalloc (rsize
= 64);
296 if (element_value(ae
)) {
297 t
= quoted
? quote_string(element_value(ae
)) : element_value(ae
);
299 RESIZE_MALLOCED_BUFFER (result
, rlen
, (reg
+ slen
+ 2),
301 strcpy(result
+ rlen
, t
);
306 * Add a separator only after non-null elements.
308 if (element_forw(ae
) != end
) {
309 strcpy(result
+ rlen
, sep
);
314 result
[rlen
] = '\0'; /* XXX */
319 array_to_string (a
, sep
, quoted
)
325 return((char *)NULL
);
327 return(savestring(""));
328 return (array_to_string_internal (element_forw(a
->head
), a
->head
, sep
, quoted
));
332 array_to_assignment_string (a
)
335 char *result
, *indstr
, *valstr
;
337 int rsize
, rlen
, elen
;
339 if (a
== 0 || array_empty (a
))
340 return((char *)NULL
);
342 result
= xmalloc (rsize
= 128);
346 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
)) {
347 indstr
= itos (element_index(ae
));
348 valstr
= element_value (ae
) ? double_quote (element_value(ae
))
350 elen
= STRLEN (indstr
) + 8 + STRLEN (valstr
);
351 RESIZE_MALLOCED_BUFFER (result
, rlen
, (elen
+ 1), rsize
, rsize
);
353 result
[rlen
++] = '[';
354 strcpy (result
+ rlen
, indstr
);
355 rlen
+= STRLEN (indstr
);
356 result
[rlen
++] = ']';
357 result
[rlen
++] = '=';
359 strcpy (result
+ rlen
, valstr
);
360 rlen
+= STRLEN (valstr
);
363 if (element_forw(ae
) != a
->head
)
364 result
[rlen
++] = ' ';
369 RESIZE_MALLOCED_BUFFER (result
, rlen
, 1, rsize
, 8);
370 result
[rlen
++] = ')';
376 quoted_array_assignment_string (a
)
381 sv
= array_to_assignment_string (a
);
383 return ((char *)NULL
);
385 vstr
= single_quote (sv
);
391 /* Determine if s2 occurs in s1. If so, return a pointer to the
392 match in s1. The compare is case sensitive. */
395 register char *s1
, *s2
;
397 register int i
, l
, len
;
399 for (i
= 0, l
= strlen(s2
), len
= strlen(s1
); (len
- i
) >= l
; i
++)
400 if (strncmp (s1
+ i
, s2
, l
) == 0)
402 return ((char *)NULL
);
406 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
408 * Return an array consisting of elements in S, separated by SEP
411 string_to_array(s
, sep
)
418 return((ARRAY
*)NULL
);
419 w
= list_string (s
, sep
, 0);
421 return((ARRAY
*)NULL
);
422 a
= word_list_to_array (w
);
427 /* Convenience routines for the shell to translate to and from the form used
428 by the rest of the code. */
430 array_to_word_list(a
)
436 if (a
== 0 || array_empty(a
))
437 return((WORD_LIST
*)NULL
);
438 list
= (WORD_LIST
*)NULL
;
439 for (ae
= element_forw(a
->head
); ae
!= a
->head
; ae
= element_forw(ae
))
440 list
= make_word_list (make_bare_word(element_value(ae
)), list
);
441 return (REVERSE_LIST(list
, WORD_LIST
*));
445 assign_word_list (array
, list
)
449 register WORD_LIST
*l
;
450 register arrayind_t i
;
452 for (l
= list
, i
= 0; l
; l
= l
->next
, i
++)
453 array_add_element(array
, i
, l
->word
->word
);
458 word_list_to_array (list
)
464 return((ARRAY
*)NULL
);
466 return (assign_word_list (a
, list
));
476 if (array
== 0 || array
->head
== 0 || array_empty (array
))
477 return (ARRAY
*)NULL
;
478 for (a
= element_forw(array
->head
); a
!= array
->head
; a
= element_forw(a
)) {
479 t
= quote_string (a
->value
);
487 array_subrange (a
, start
, end
, quoted
)
489 int start
, end
, quoted
;
491 ARRAY_ELEMENT
*h
, *p
;
495 if (p
== 0 || array_empty (a
) || start
> array_num_elements (a
))
496 return ((char *)NULL
);
498 for (i
= 0, p
= element_forw(p
); p
!= a
->head
&& i
< start
; i
++, p
= element_forw(p
))
501 return ((char *)NULL
);
502 for (h
= p
; p
!= a
->head
&& i
< end
; i
++, p
= element_forw(p
))
505 return (array_to_string_internal (h
, p
, " ", quoted
));
509 array_pat_subst (a
, pat
, rep
, mflags
)
518 if (array_head (a
) == 0 || array_empty (a
))
519 return ((char *)NULL
);
522 for (e
= element_forw(a2
->head
); e
!= a2
->head
; e
= element_forw(e
)) {
523 t
= pat_subst(element_value(e
), pat
, rep
, mflags
);
524 FREE(element_value(e
));
528 if (mflags
& MATCH_QUOTED
)
530 t
= array_to_string (a2
, " ", 0);
537 #if defined (TEST_ARRAY)
541 printf("array[%d] = %s\n",(int)element_index(ae
), element_value(ae
));
548 array_walk(a
, print_element
);
553 ARRAY
*a
, *new_a
, *copy_of_a
;
558 array_add_element(a
, 1, "one");
559 array_add_element(a
, 7, "seven");
560 array_add_element(a
, 4, "four");
561 array_add_element(a
, 1029, "one thousand twenty-nine");
562 array_add_element(a
, 12, "twelve");
563 array_add_element(a
, 42, "forty-two");
565 s
= array_to_string (a
, " ", 0);
566 printf("s = %s\n", s
);
567 copy_of_a
= string_to_array(s
, " ");
568 printf("copy_of_a:");
569 print_array(copy_of_a
);
570 dispose_array(copy_of_a
);
573 ae
= array_delete_element(a
, 4);
574 destroy_array_element(ae
);
575 ae
= array_delete_element(a
, 1029);
576 destroy_array_element(ae
);
577 array_add_element(a
, 16, "sixteen");
579 s
= array_to_string (a
, " ", 0);
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
);
587 array_add_element(a
, 2, "two");
588 array_add_element(a
, 1029, "new one thousand twenty-nine");
589 array_add_element(a
, 0, "zero");
590 array_add_element(a
, 134, "");
592 s
= array_to_string (a
, ":", 0);
593 printf("s = %s\n", s
);
594 copy_of_a
= string_to_array(s
, ":");
595 printf("copy_of_a:");
596 print_array(copy_of_a
);
597 dispose_array(copy_of_a
);
600 new_a
= copy_array(a
);
602 s
= array_to_string (new_a
, ":", 0);
603 printf("s = %s\n", s
);
604 copy_of_a
= string_to_array(s
, ":", 0);
605 printf("copy_of_a:");
606 print_array(copy_of_a
);
607 dispose_array(copy_of_a
);
611 dispose_array(new_a
);
614 #endif /* TEST_ARRAY */
615 #endif /* ARRAY_VARS */