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 #define ADD_BEFORE(ae, new) \
50 ae->prev->next = new; \
51 new->prev = ae->prev; \
57 * Allocate and return a new array element with index INDEX and value
61 new_array_element(indx, value)
67 r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
69 r->value = value ? savestring(value) : (char *)NULL;
70 r->next = r->prev = (ARRAY_ELEMENT *) NULL;
75 destroy_array_element(ae)
88 r =(ARRAY *)xmalloc(sizeof(ARRAY));
89 r->type = array_indexed;
90 r->max_index = r->max_size = -1;
92 head = new_array_element(-1, (char *)NULL); /* dummy head */
93 head->prev = head->next = head;
102 register ARRAY_ELEMENT *r, *r1;
106 for (r = element_forw(a->head); r != a->head; ) {
107 r1 = element_forw(r);
108 destroy_array_element(r);
111 a->head->next = a->head->prev = a->head;
112 a->max_index = a->max_size = -1;
113 a->num_elements = a->max_size = 0;
123 destroy_array_element(a->head);
132 ARRAY_ELEMENT *ae, *new;
135 return((ARRAY *) NULL);
138 a1->max_index = a->max_index;
139 a1->num_elements = a->num_elements;
140 a1->max_size = a->max_size;
141 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
142 new = new_array_element(element_index(ae), element_value(ae));
143 ADD_BEFORE(a1->head, new);
148 #ifdef INCLUDE_UNUSED
150 * Make and return a new array composed of the elements in array A from
154 dup_array_subrange(array, s, e)
156 ARRAY_ELEMENT *s, *e;
159 ARRAY_ELEMENT *p, *n;
163 a->type = array->type;
165 for (p = s, i = 0; p != e; p = element_forw(p), i++) {
166 n = new_array_element (i, element_value(p));
167 ADD_BEFORE(a->head, n);
169 a->num_elements = a->max_index = i;
174 #ifdef INCLUDE_UNUSED
176 copy_array_element(ae)
179 return(ae ? new_array_element(element_index(ae), element_value(ae))
180 : (ARRAY_ELEMENT *) NULL);
185 * Add a new element with index I and value V to array A (a[i] = v).
188 array_add_element(a, i, v)
193 register ARRAY_ELEMENT *new, *ae;
197 new = new_array_element(i, v);
198 if (i > array_max_index(a)) {
200 * Hook onto the end. This also works for an empty array.
201 * Fast path for the common case of allocating arrays
204 ADD_BEFORE(a->head, new);
210 * Otherwise we search for the spot to insert it.
212 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
213 if (element_index(ae) == i) {
215 * Replacing an existing element.
217 destroy_array_element(new);
218 free(element_value(ae));
219 ae->value = savestring(v);
221 } else if (element_index(ae) > i) {
227 return (-1); /* problem */
231 * Delete the element with index I from array A and return it so the
232 * caller can dispose of it.
235 array_delete_element(a, i)
239 register ARRAY_ELEMENT *ae;
241 if (!a || array_empty(a))
242 return((ARRAY_ELEMENT *) NULL);
243 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
244 if (element_index(ae) == i) {
245 ae->next->prev = ae->prev;
246 ae->prev->next = ae->next;
248 if (i == array_max_index(a))
249 a->max_index = element_index(ae->prev);
252 return((ARRAY_ELEMENT *) NULL);
256 * Return the value of a[i].
259 array_reference(a, i)
263 register ARRAY_ELEMENT *ae;
265 if (a == 0 || array_empty(a))
266 return((char *) NULL);
267 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
268 if (element_index(ae) == i)
269 return(element_value(ae));
270 return((char *) NULL);
275 * Walk the array, calling FUNC once for each element, with the array
276 * element as the argument.
281 sh_ae_map_func_t *func;
283 register ARRAY_ELEMENT *ae;
285 if (a == 0 || array_empty(a))
287 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
293 * Return a string that is the concatenation of all the elements in A,
297 array_to_string_internal (start, end, sep, quoted)
298 ARRAY_ELEMENT *start, *end;
304 int slen, rsize, rlen, reg;
306 if (start == end) /* XXX - should not happen */
307 return ((char *)NULL);
311 for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
313 result = (char *)xmalloc (rsize = 64);
314 if (element_value(ae)) {
315 t = quoted ? quote_string(element_value(ae)) : element_value(ae);
317 RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
319 strcpy(result + rlen, t);
324 * Add a separator only after non-null elements.
326 if (element_forw(ae) != end) {
327 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 = (char *)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) ? sh_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 = sh_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 arrayind_t start, end;
531 ARRAY_ELEMENT *h, *p;
535 if (p == 0 || array_empty (a) || start > array_num_elements (a))
536 return ((char *)NULL);
538 for (i = 0, p = element_forw(p); p != a->head && i < start; i++, p = element_forw(p))
541 return ((char *)NULL);
542 for (h = p; p != a->head && i < end; i++, p = element_forw(p))
545 return (array_to_string_internal (h, p, " ", quoted));
549 array_pat_subst (a, pat, rep, mflags)
558 if (array_head (a) == 0 || array_empty (a))
559 return ((char *)NULL);
562 for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
563 t = pat_subst(element_value(e), pat, rep, mflags);
564 FREE(element_value(e));
568 if (mflags & MATCH_QUOTED)
570 t = array_to_string (a2, " ", 0);
577 #if defined (TEST_ARRAY)
581 printf("array[%ld] = %s\n", element_index(ae), element_value(ae));
588 array_walk(a, print_element);
593 ARRAY *a, *new_a, *copy_of_a;
598 array_add_element(a, 1, "one");
599 array_add_element(a, 7, "seven");
600 array_add_element(a, 4, "four");
601 array_add_element(a, 1029, "one thousand twenty-nine");
602 array_add_element(a, 12, "twelve");
603 array_add_element(a, 42, "forty-two");
605 s = array_to_string (a, " ", 0);
606 printf("s = %s\n", s);
607 copy_of_a = string_to_array(s, " ");
608 printf("copy_of_a:");
609 print_array(copy_of_a);
610 dispose_array(copy_of_a);
613 ae = array_delete_element(a, 4);
614 destroy_array_element(ae);
615 ae = array_delete_element(a, 1029);
616 destroy_array_element(ae);
617 array_add_element(a, 16, "sixteen");
619 s = array_to_string (a, " ", 0);
620 printf("s = %s\n", s);
621 copy_of_a = string_to_array(s, " ");
622 printf("copy_of_a:");
623 print_array(copy_of_a);
624 dispose_array(copy_of_a);
627 array_add_element(a, 2, "two");
628 array_add_element(a, 1029, "new one thousand twenty-nine");
629 array_add_element(a, 0, "zero");
630 array_add_element(a, 134, "");
632 s = array_to_string (a, ":", 0);
633 printf("s = %s\n", s);
634 copy_of_a = string_to_array(s, ":");
635 printf("copy_of_a:");
636 print_array(copy_of_a);
637 dispose_array(copy_of_a);
640 new_a = copy_array(a);
642 s = array_to_string (new_a, ":", 0);
643 printf("s = %s\n", s);
644 copy_of_a = string_to_array(s, ":", 0);
645 printf("copy_of_a:");
646 print_array(copy_of_a);
647 dispose_array(copy_of_a);
651 dispose_array(new_a);
654 #endif /* TEST_ARRAY */
655 #endif /* ARRAY_VARS */