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)
24 #include "builtins/common.h"
26 extern char *quote_string (); /* XXX */
28 #define ADD_BEFORE(ae, new) \
30 ae->prev->next = new; \
31 new->prev = ae->prev; \
37 * Allocate and return a new array element with index INDEX and value
41 new_array_element(indx, value)
47 r = (ARRAY_ELEMENT *) xmalloc(sizeof(ARRAY_ELEMENT));
49 r->value = value ? savestring(value) : (char *)NULL;
50 r->next = r->prev = (ARRAY_ELEMENT *) NULL;
55 destroy_array_element(ae)
68 r =(ARRAY *) xmalloc(sizeof(ARRAY));
69 r->type = array_indexed;
70 r->max_index = r->max_size = -1;
72 head = new_array_element(-1, (char *)NULL); /* dummy head */
73 head->prev = head->next = head;
82 register ARRAY_ELEMENT *r, *r1;
86 for (r = element_forw(a->head); r != a->head; ) {
88 destroy_array_element(r);
91 a->head->next = a->head->prev = a->head;
92 a->max_index = a->max_size = -1;
93 a->num_elements = a->max_size = 0;
103 destroy_array_element(a->head);
112 ARRAY_ELEMENT *ae, *new;
115 return((ARRAY *) NULL);
118 a1->max_index = a->max_index;
119 a1->num_elements = a->num_elements;
120 a1->max_size = a->max_size;
121 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
122 new = new_array_element(element_index(ae), element_value(ae));
123 ADD_BEFORE(a1->head, new);
128 #ifdef INCLUDE_UNUSED
130 * Make and return a new array composed of the elements in array A from
134 dup_array_subrange(array, s, e)
136 ARRAY_ELEMENT *s, *e;
139 ARRAY_ELEMENT *p, *n;
143 a->type = array->type;
145 for (p = s, i = 0; p != e; p = element_forw(p), i++) {
146 n = new_array_element (i, element_value(p));
147 ADD_BEFORE(a->head, n);
149 a->num_elements = a->max_index = i;
155 copy_array_element(ae)
158 return(ae ? new_array_element(element_index(ae), element_value(ae))
159 : (ARRAY_ELEMENT *) NULL);
163 * Add a new element with index I and value V to array A (a[i] = v).
166 array_add_element(a, i, v)
171 register ARRAY_ELEMENT *new, *ae;
175 new = new_array_element(i, v);
176 if (i > array_max_index(a)) {
178 * Hook onto the end. This also works for an empty array.
179 * Fast path for the common case of allocating arrays
182 ADD_BEFORE(a->head, new);
188 * Otherwise we search for the spot to insert it.
190 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
191 if (element_index(ae) == i) {
193 * Replacing an existing element.
195 destroy_array_element(new);
196 free(element_value(ae));
197 ae->value = savestring(v);
199 } else if (element_index(ae) > i) {
205 return (-1); /* problem */
209 * Delete the element with index I from array A and return it so the
210 * caller can dispose of it.
213 array_delete_element(a, i)
217 register ARRAY_ELEMENT *ae;
219 if (!a || array_empty(a))
220 return((ARRAY_ELEMENT *) NULL);
221 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
222 if (element_index(ae) == i) {
223 ae->next->prev = ae->prev;
224 ae->prev->next = ae->next;
226 if (i == array_max_index(a))
227 a->max_index = element_index(ae->prev);
230 return((ARRAY_ELEMENT *) NULL);
234 * Return the value of a[i].
237 array_reference(a, i)
241 register ARRAY_ELEMENT *ae;
243 if (a == 0 || array_empty(a))
244 return((char *) NULL);
245 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
246 if (element_index(ae) == i)
247 return(element_value(ae));
248 return((char *) NULL);
252 * Walk the array, calling FUNC once for each element, with the array
253 * element as the argument.
260 register ARRAY_ELEMENT *ae;
262 if (a == 0 || array_empty(a))
264 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
269 * Return a string that is the concatenation of all the elements in A,
273 array_to_string_internal (start, end, sep, quoted)
274 ARRAY_ELEMENT *start, *end;
280 int slen, rsize, rlen, reg;
282 if (start == end) /* XXX - should not happen */
283 return ((char *)NULL);
286 for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
288 result = xmalloc (rsize = 64);
289 if (element_value(ae)) {
290 t = quoted ? quote_string(element_value(ae)) : element_value(ae);
292 RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
294 strcpy(result + rlen, t);
299 * Add a separator only after non-null elements.
301 if (element_forw(ae) != end) {
302 strcpy(result + rlen, sep);
307 result[rlen] = '\0'; /* XXX */
312 array_to_string (a, sep, quoted)
318 return((char *)NULL);
320 return(savestring(""));
321 return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
325 array_to_assignment_string (a)
328 char *result, *indstr, *valstr;
330 int rsize, rlen, elen;
332 if (a == 0 || array_empty (a))
333 return((char *)NULL);
335 result = xmalloc (rsize = 128);
339 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
340 indstr = itos (element_index(ae));
341 valstr = element_value (ae) ? double_quote (element_value(ae))
343 elen = STRLEN (indstr) + 8 + STRLEN (valstr);
344 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
346 result[rlen++] = '[';
347 strcpy (result + rlen, indstr);
348 rlen += STRLEN (indstr);
349 result[rlen++] = ']';
350 result[rlen++] = '=';
352 strcpy (result + rlen, valstr);
353 rlen += STRLEN (valstr);
356 if (element_forw(ae) != a->head)
357 result[rlen++] = ' ';
362 RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
363 result[rlen++] = ')';
369 quoted_array_assignment_string (a)
374 sv = array_to_assignment_string (a);
376 return ((char *)NULL);
378 vstr = single_quote (sv);
384 /* Determine if s2 occurs in s1. If so, return a pointer to the
385 match in s1. The compare is case sensitive. */
388 register char *s1, *s2;
390 register int i, l, len;
392 for (i = 0, l = strlen(s2), len = strlen(s1); (len - i) >= l; i++)
393 if (strncmp (s1 + i, s2, l) == 0)
395 return ((char *)NULL);
399 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
401 * Return an array consisting of elements in S, separated by SEP
404 string_to_array(s, sep)
411 return((ARRAY *)NULL);
412 w = list_string (s, sep, 0);
414 return((ARRAY *)NULL);
415 a = word_list_to_array (w);
420 /* Convenience routines for the shell to translate to and from the form used
421 by the rest of the code. */
423 array_to_word_list(a)
429 if (a == 0 || array_empty(a))
430 return((WORD_LIST *)NULL);
431 list = (WORD_LIST *)NULL;
432 for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
433 list = make_word_list (make_bare_word(element_value(ae)), list);
434 return (REVERSE_LIST(list, WORD_LIST *));
438 assign_word_list (array, list)
442 register WORD_LIST *l;
443 register arrayind_t i;
445 for (l = list, i = 0; l; l = l->next, i++)
446 array_add_element(array, i, l->word->word);
451 word_list_to_array (list)
457 return((ARRAY *)NULL);
459 return (assign_word_list (a, list));
469 if (array == 0 || array->head == 0 || array_empty (array))
470 return (ARRAY *)NULL;
471 for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
472 t = quote_string (a->value);
480 array_subrange (a, start, end, quoted)
482 int start, end, quoted;
484 ARRAY_ELEMENT *h, *p;
488 if (p == 0 || array_empty (a) || start > array_num_elements (a))
489 return ((char *)NULL);
491 for (i = 0, p = element_forw(p); p != a->head && i < start; i++, p = element_forw(p))
494 return ((char *)NULL);
495 for (h = p; p != a->head && i < end; i++, p = element_forw(p))
498 return (array_to_string_internal (h, p, " ", quoted));
502 array_pat_subst (a, pat, rep, mflags)
511 if (array_head (a) == 0 || array_empty (a))
512 return ((char *)NULL);
515 for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
516 t = pat_subst(element_value(e), pat, rep, mflags);
517 FREE(element_value(e));
521 if (mflags & MATCH_QUOTED)
523 t = array_to_string (a2, " ", 0);
530 #if defined (TEST_ARRAY)
534 printf("array[%d] = %s\n",(int)element_index(ae), element_value(ae));
541 array_walk(a, print_element);
546 ARRAY *a, *new_a, *copy_of_a;
551 array_add_element(a, 1, "one");
552 array_add_element(a, 7, "seven");
553 array_add_element(a, 4, "four");
554 array_add_element(a, 1029, "one thousand twenty-nine");
555 array_add_element(a, 12, "twelve");
556 array_add_element(a, 42, "forty-two");
558 s = array_to_string (a, " ", 0);
559 printf("s = %s\n", s);
560 copy_of_a = string_to_array(s, " ");
561 printf("copy_of_a:");
562 print_array(copy_of_a);
563 dispose_array(copy_of_a);
566 ae = array_delete_element(a, 4);
567 destroy_array_element(ae);
568 ae = array_delete_element(a, 1029);
569 destroy_array_element(ae);
570 array_add_element(a, 16, "sixteen");
572 s = array_to_string (a, " ", 0);
573 printf("s = %s\n", s);
574 copy_of_a = string_to_array(s, " ");
575 printf("copy_of_a:");
576 print_array(copy_of_a);
577 dispose_array(copy_of_a);
580 array_add_element(a, 2, "two");
581 array_add_element(a, 1029, "new one thousand twenty-nine");
582 array_add_element(a, 0, "zero");
583 array_add_element(a, 134, "");
585 s = array_to_string (a, ":", 0);
586 printf("s = %s\n", s);
587 copy_of_a = string_to_array(s, ":");
588 printf("copy_of_a:");
589 print_array(copy_of_a);
590 dispose_array(copy_of_a);
593 new_a = copy_array(a);
595 s = array_to_string (new_a, ":", 0);
596 printf("s = %s\n", s);
597 copy_of_a = string_to_array(s, ":", 0);
598 printf("copy_of_a:");
599 print_array(copy_of_a);
600 dispose_array(copy_of_a);
604 dispose_array(new_a);
607 #endif /* TEST_ARRAY */
608 #endif /* ARRAY_VARS */