Line data Source code
1 : /*
2 : * array.c - functions to create, destroy, access, and manipulate arrays
3 : * of strings.
4 : *
5 : * Arrays are sparse doubly-linked lists. An element's index is stored
6 : * with it.
7 : *
8 : * Chet Ramey
9 : * chet@ins.cwru.edu
10 : */
11 :
12 : /* Copyright (C) 1997-2009 Free Software Foundation, Inc.
13 :
14 : This file is part of GNU Bash, the Bourne Again SHell.
15 :
16 : Bash is free software: you can redistribute it and/or modify
17 : it under the terms of the GNU General Public License as published by
18 : the Free Software Foundation, either version 3 of the License, or
19 : (at your option) any later version.
20 :
21 : Bash is distributed in the hope that it will be useful,
22 : but WITHOUT ANY WARRANTY; without even the implied warranty of
23 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 : GNU General Public License for more details.
25 :
26 : You should have received a copy of the GNU General Public License
27 : along with Bash. If not, see <http://www.gnu.org/licenses/>.
28 : */
29 :
30 : #include "config.h"
31 :
32 : #if defined (ARRAY_VARS)
33 :
34 : #if defined (HAVE_UNISTD_H)
35 : # ifdef _MINIX
36 : # include <sys/types.h>
37 : # endif
38 : # include <unistd.h>
39 : #endif
40 :
41 : #include <stdio.h>
42 : #include "bashansi.h"
43 :
44 : #include "shell.h"
45 : #include "array.h"
46 : #include "builtins/common.h"
47 :
48 : #define ADD_BEFORE(ae, new) \
49 : do { \
50 : ae->prev->next = new; \
51 : new->prev = ae->prev; \
52 : ae->prev = new; \
53 : new->next = ae; \
54 : } while(0)
55 :
56 : static char *array_to_string_internal __P((ARRAY_ELEMENT *, ARRAY_ELEMENT *, char *, int));
57 :
58 : /* lastref should be moved into the array structure so each array can be
59 : optimized separately */
60 :
61 : static ARRAY *lastarray = 0;
62 : static ARRAY_ELEMENT *lastref = 0;
63 :
64 : #define IS_LASTREF(a) (lastarray && (a) == lastarray)
65 :
66 : #define LASTREF_START(a, i) \
67 : (IS_LASTREF(a) && i >= element_index(lastref)) ? lastref \
68 : : element_forw(a->head)
69 :
70 : #define INVALIDATE_LASTREF(a) \
71 : do { \
72 : if ((a) == lastarray) { \
73 : lastarray = 0; \
74 : lastref = 0; \
75 : } \
76 : } while (0)
77 :
78 : #define SET_LASTREF(a, e) \
79 : do { \
80 : lastarray = (a); \
81 : lastref = (e); \
82 : } while (0)
83 :
84 : #define UNSET_LASTREF() \
85 : do { \
86 : lastarray = 0; \
87 : lastref = 0; \
88 : } while (0)
89 :
90 : ARRAY *
91 85894630 : array_create()
92 : {
93 85894630 : ARRAY *r;
94 85894630 : ARRAY_ELEMENT *head;
95 :
96 85894630 : r =(ARRAY *)xmalloc(sizeof(ARRAY));
97 85894630 : r->type = array_indexed;
98 85894630 : r->max_index = -1;
99 85894630 : r->num_elements = 0;
100 85894630 : head = array_create_element(-1, (char *)NULL); /* dummy head */
101 85894630 : head->prev = head->next = head;
102 85894630 : r->head = head;
103 85894630 : return(r);
104 : }
105 :
106 : void
107 19496 : array_flush (a)
108 : ARRAY *a;
109 : {
110 19496 : register ARRAY_ELEMENT *r, *r1;
111 :
112 19496 : if (a == 0)
113 : return;
114 58077 : for (r = element_forw(a->head); r != a->head; ) {
115 38581 : r1 = element_forw(r);
116 38581 : array_dispose_element(r);
117 38581 : r = r1;
118 : }
119 19496 : a->head->next = a->head->prev = a->head;
120 19496 : a->max_index = -1;
121 19496 : a->num_elements = 0;
122 19496 : INVALIDATE_LASTREF(a);
123 : }
124 :
125 : void
126 8592 : array_dispose(a)
127 : ARRAY *a;
128 : {
129 8592 : if (a == 0)
130 : return;
131 8592 : array_flush (a);
132 8592 : array_dispose_element(a->head);
133 8592 : free(a);
134 : }
135 :
136 : ARRAY *
137 8592 : array_copy(a)
138 : ARRAY *a;
139 : {
140 8592 : ARRAY *a1;
141 8592 : ARRAY_ELEMENT *ae, *new;
142 :
143 8592 : if (a == 0)
144 : return((ARRAY *) NULL);
145 8592 : a1 = array_create();
146 8592 : a1->type = a->type;
147 8592 : a1->max_index = a->max_index;
148 8592 : a1->num_elements = a->num_elements;
149 20689 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
150 12097 : new = array_create_element(element_index(ae), element_value(ae));
151 12097 : ADD_BEFORE(a1->head, new);
152 : }
153 : return(a1);
154 : }
155 :
156 : /*
157 : * Make and return a new array composed of the elements in array A from
158 : * S to E, inclusive.
159 : */
160 : ARRAY *
161 0 : array_slice(array, s, e)
162 : ARRAY *array;
163 : ARRAY_ELEMENT *s, *e;
164 : {
165 0 : ARRAY *a;
166 0 : ARRAY_ELEMENT *p, *n;
167 0 : int i;
168 0 : arrayind_t mi;
169 :
170 0 : a = array_create ();
171 0 : a->type = array->type;
172 :
173 0 : for (mi = 0, p = s, i = 0; p != e; p = element_forw(p), i++) {
174 0 : n = array_create_element (element_index(p), element_value(p));
175 0 : ADD_BEFORE(a->head, n);
176 0 : mi = element_index(n);
177 : }
178 0 : a->num_elements = i;
179 0 : a->max_index = mi;
180 0 : return a;
181 : }
182 :
183 : /*
184 : * Walk the array, calling FUNC once for each element, with the array
185 : * element as the argument.
186 : */
187 : void
188 0 : array_walk(a, func, udata)
189 : ARRAY *a;
190 : sh_ae_map_func_t *func;
191 : void *udata;
192 : {
193 0 : register ARRAY_ELEMENT *ae;
194 :
195 0 : if (a == 0 || array_empty(a))
196 : return;
197 0 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
198 0 : if ((*func)(ae, udata) < 0)
199 : return;
200 : }
201 :
202 : /*
203 : * Shift the array A N elements to the left. Delete the first N elements
204 : * and subtract N from the indices of the remaining elements. If FLAGS
205 : * does not include AS_DISPOSE, this returns a singly-linked null-terminated
206 : * list of elements so the caller can dispose of the chain. If FLAGS
207 : * includes AS_DISPOSE, this function disposes of the shifted-out elements
208 : * and returns NULL.
209 : */
210 : ARRAY_ELEMENT *
211 95456067 : array_shift(a, n, flags)
212 : ARRAY *a;
213 : int n, flags;
214 : {
215 95456067 : register ARRAY_ELEMENT *ae, *ret;
216 95456067 : register int i;
217 :
218 95456067 : if (a == 0 || array_empty(a) || n <= 0)
219 : return ((ARRAY_ELEMENT *)NULL);
220 :
221 95456067 : INVALIDATE_LASTREF(a);
222 190912134 : for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
223 95456067 : ;
224 95456067 : if (ae == a->head) {
225 : /* Easy case; shifting out all of the elements */
226 47737551 : if (flags & AS_DISPOSE) {
227 0 : array_flush (a);
228 0 : return ((ARRAY_ELEMENT *)NULL);
229 : }
230 47737551 : for (ae = ret; element_forw(ae) != a->head; ae = element_forw(ae))
231 : ;
232 47737551 : element_forw(ae) = (ARRAY_ELEMENT *)NULL;
233 47737551 : a->head->next = a->head->prev = a->head;
234 47737551 : a->max_index = -1;
235 47737551 : a->num_elements = 0;
236 47737551 : return ret;
237 : }
238 : /*
239 : * ae now points to the list of elements we want to retain.
240 : * ret points to the list we want to either destroy or return.
241 : */
242 47718516 : ae->prev->next = (ARRAY_ELEMENT *)NULL; /* null-terminate RET */
243 :
244 47718516 : a->head->next = ae; /* slice RET out of the array */
245 47718516 : ae->prev = a->head;
246 :
247 97098666 : for ( ; ae != a->head; ae = element_forw(ae))
248 49380150 : element_index(ae) -= n; /* renumber retained indices */
249 :
250 47718516 : a->num_elements -= n; /* modify bookkeeping information */
251 47718516 : a->max_index = element_index(a->head->prev);
252 :
253 47718516 : if (flags & AS_DISPOSE) {
254 0 : for (ae = ret; ae; ) {
255 0 : ret = element_forw(ae);
256 0 : array_dispose_element(ae);
257 0 : ae = ret;
258 : }
259 : return ((ARRAY_ELEMENT *)NULL);
260 : }
261 :
262 : return ret;
263 : }
264 :
265 : /*
266 : * Shift array A right N indices. If S is non-null, it becomes the value of
267 : * the new element 0. Returns the number of elements in the array after the
268 : * shift.
269 : */
270 : int
271 95459289 : array_rshift (a, n, s)
272 : ARRAY *a;
273 : int n;
274 : char *s;
275 : {
276 95459289 : register ARRAY_ELEMENT *ae, *new;
277 :
278 95459289 : if (a == 0 || (array_empty(a) && s == 0))
279 : return 0;
280 95459289 : else if (n <= 0)
281 : return (a->num_elements);
282 :
283 95459289 : ae = element_forw(a->head);
284 95459289 : if (s) {
285 95459289 : new = array_create_element(0, s);
286 95459289 : ADD_BEFORE(ae, new);
287 95459289 : a->num_elements++;
288 95459289 : if (array_num_elements(a) == 1) { /* array was empty */
289 47737611 : a->max_index = 0;
290 47737611 : return 1;
291 : }
292 : }
293 :
294 : /*
295 : * Renumber all elements in the array except the one we just added.
296 : */
297 98769783 : for ( ; ae != a->head; ae = element_forw(ae))
298 51048105 : element_index(ae) += n;
299 :
300 47721678 : a->max_index = element_index(a->head->prev);
301 :
302 47721678 : INVALIDATE_LASTREF(a);
303 47721678 : return (a->num_elements);
304 : }
305 :
306 : ARRAY_ELEMENT *
307 0 : array_unshift_element(a)
308 : ARRAY *a;
309 : {
310 0 : return (array_shift (a, 1, 0));
311 : }
312 :
313 : int
314 0 : array_shift_element(a, v)
315 : ARRAY *a;
316 : char *v;
317 : {
318 0 : return (array_rshift (a, 1, v));
319 : }
320 :
321 : ARRAY *
322 0 : array_quote(array)
323 : ARRAY *array;
324 : {
325 0 : ARRAY_ELEMENT *a;
326 0 : char *t;
327 :
328 0 : if (array == 0 || array_head(array) == 0 || array_empty(array))
329 : return (ARRAY *)NULL;
330 0 : for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
331 0 : t = quote_string (a->value);
332 0 : FREE(a->value);
333 0 : a->value = t;
334 : }
335 : return array;
336 : }
337 :
338 : ARRAY *
339 0 : array_quote_escapes(array)
340 : ARRAY *array;
341 : {
342 0 : ARRAY_ELEMENT *a;
343 0 : char *t;
344 :
345 0 : if (array == 0 || array_head(array) == 0 || array_empty(array))
346 : return (ARRAY *)NULL;
347 0 : for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
348 0 : t = quote_escapes (a->value);
349 0 : FREE(a->value);
350 0 : a->value = t;
351 : }
352 : return array;
353 : }
354 :
355 : ARRAY *
356 0 : array_dequote(array)
357 : ARRAY *array;
358 : {
359 0 : ARRAY_ELEMENT *a;
360 0 : char *t;
361 :
362 0 : if (array == 0 || array_head(array) == 0 || array_empty(array))
363 : return (ARRAY *)NULL;
364 0 : for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
365 0 : t = dequote_string (a->value);
366 0 : FREE(a->value);
367 0 : a->value = t;
368 : }
369 : return array;
370 : }
371 :
372 : ARRAY *
373 0 : array_dequote_escapes(array)
374 : ARRAY *array;
375 : {
376 0 : ARRAY_ELEMENT *a;
377 0 : char *t;
378 :
379 0 : if (array == 0 || array_head(array) == 0 || array_empty(array))
380 : return (ARRAY *)NULL;
381 0 : for (a = element_forw(array->head); a != array->head; a = element_forw(a)) {
382 0 : t = dequote_escapes (a->value);
383 0 : FREE(a->value);
384 0 : a->value = t;
385 : }
386 : return array;
387 : }
388 :
389 : ARRAY *
390 0 : array_remove_quoted_nulls(array)
391 : ARRAY *array;
392 : {
393 0 : ARRAY_ELEMENT *a;
394 :
395 0 : if (array == 0 || array_head(array) == 0 || array_empty(array))
396 : return (ARRAY *)NULL;
397 0 : for (a = element_forw(array->head); a != array->head; a = element_forw(a))
398 0 : a->value = remove_quoted_nulls (a->value);
399 : return array;
400 : }
401 :
402 : /*
403 : * Return a string whose elements are the members of array A beginning at
404 : * index START and spanning NELEM members. Null elements are counted.
405 : * Since arrays are sparse, unset array elements are not counted.
406 : */
407 : char *
408 0 : array_subrange (a, start, nelem, starsub, quoted)
409 : ARRAY *a;
410 : arrayind_t start, nelem;
411 : int starsub, quoted;
412 : {
413 0 : ARRAY *a2;
414 0 : ARRAY_ELEMENT *h, *p;
415 0 : arrayind_t i;
416 0 : char *ifs, *sifs, *t;
417 0 : int slen;
418 :
419 0 : p = a ? array_head (a) : 0;
420 0 : if (p == 0 || array_empty (a) || start > array_max_index(a))
421 : return ((char *)NULL);
422 :
423 : /*
424 : * Find element with index START. If START corresponds to an unset
425 : * element (arrays can be sparse), use the first element whose index
426 : * is >= START. If START is < 0, we count START indices back from
427 : * the end of A (not elements, even with sparse arrays -- START is an
428 : * index).
429 : */
430 0 : for (p = element_forw(p); p != array_head(a) && start > element_index(p); p = element_forw(p))
431 0 : ;
432 :
433 0 : if (p == a->head)
434 : return ((char *)NULL);
435 :
436 : /* Starting at P, take NELEM elements, inclusive. */
437 0 : for (i = 0, h = p; p != a->head && i < nelem; i++, p = element_forw(p))
438 0 : ;
439 :
440 0 : a2 = array_slice(a, h, p);
441 :
442 0 : if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))
443 0 : array_quote(a2);
444 : else
445 0 : array_quote_escapes(a2);
446 :
447 0 : if (starsub && (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT))) {
448 : /* ${array[*]} */
449 0 : array_remove_quoted_nulls (a2);
450 0 : sifs = ifs_firstchar ((int *)NULL);
451 0 : t = array_to_string (a2, sifs, 0);
452 0 : free (sifs);
453 0 : } else if (quoted & (Q_DOUBLE_QUOTES|Q_HERE_DOCUMENT)) {
454 : /* ${array[@]} */
455 0 : sifs = ifs_firstchar (&slen);
456 0 : ifs = getifs ();
457 0 : if (ifs == 0 || *ifs == 0) {
458 0 : if (slen < 2)
459 0 : sifs = xrealloc(sifs, 2);
460 0 : sifs[0] = ' ';
461 0 : sifs[1] = '\0';
462 : }
463 0 : t = array_to_string (a2, sifs, 0);
464 0 : free (sifs);
465 : } else
466 0 : t = array_to_string (a2, " ", 0);
467 0 : array_dispose(a2);
468 :
469 0 : return t;
470 : }
471 :
472 : char *
473 0 : array_patsub (a, pat, rep, mflags)
474 : ARRAY *a;
475 : char *pat, *rep;
476 : int mflags;
477 : {
478 0 : ARRAY *a2;
479 0 : ARRAY_ELEMENT *e;
480 0 : char *t, *sifs, *ifs;
481 0 : int slen;
482 :
483 0 : if (a == 0 || array_head(a) == 0 || array_empty(a))
484 : return ((char *)NULL);
485 :
486 0 : a2 = array_copy(a);
487 0 : for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
488 0 : t = pat_subst(element_value(e), pat, rep, mflags);
489 0 : FREE(element_value(e));
490 0 : e->value = t;
491 : }
492 :
493 0 : if (mflags & MATCH_QUOTED)
494 0 : array_quote(a2);
495 : else
496 0 : array_quote_escapes(a2);
497 :
498 0 : if (mflags & MATCH_STARSUB) {
499 0 : array_remove_quoted_nulls (a2);
500 0 : sifs = ifs_firstchar((int *)NULL);
501 0 : t = array_to_string (a2, sifs, 0);
502 0 : free(sifs);
503 0 : } else if (mflags & MATCH_QUOTED) {
504 : /* ${array[@]} */
505 0 : sifs = ifs_firstchar (&slen);
506 0 : ifs = getifs ();
507 0 : if (ifs == 0 || *ifs == 0) {
508 0 : if (slen < 2)
509 0 : sifs = xrealloc (sifs, 2);
510 0 : sifs[0] = ' ';
511 0 : sifs[1] = '\0';
512 : }
513 0 : t = array_to_string (a2, sifs, 0);
514 0 : free(sifs);
515 : } else
516 0 : t = array_to_string (a2, " ", 0);
517 0 : array_dispose (a2);
518 :
519 0 : return t;
520 : }
521 :
522 : char *
523 0 : array_modcase (a, pat, modop, mflags)
524 : ARRAY *a;
525 : char *pat;
526 : int modop;
527 : int mflags;
528 : {
529 0 : ARRAY *a2;
530 0 : ARRAY_ELEMENT *e;
531 0 : char *t, *sifs, *ifs;
532 0 : int slen;
533 :
534 0 : if (a == 0 || array_head(a) == 0 || array_empty(a))
535 : return ((char *)NULL);
536 :
537 0 : a2 = array_copy(a);
538 0 : for (e = element_forw(a2->head); e != a2->head; e = element_forw(e)) {
539 0 : t = sh_modcase(element_value(e), pat, modop);
540 0 : FREE(element_value(e));
541 0 : e->value = t;
542 : }
543 :
544 0 : if (mflags & MATCH_QUOTED)
545 0 : array_quote(a2);
546 : else
547 0 : array_quote_escapes(a2);
548 :
549 0 : if (mflags & MATCH_STARSUB) {
550 0 : array_remove_quoted_nulls (a2);
551 0 : sifs = ifs_firstchar((int *)NULL);
552 0 : t = array_to_string (a2, sifs, 0);
553 0 : free(sifs);
554 0 : } else if (mflags & MATCH_QUOTED) {
555 : /* ${array[@]} */
556 0 : sifs = ifs_firstchar (&slen);
557 0 : ifs = getifs ();
558 0 : if (ifs == 0 || *ifs == 0) {
559 0 : if (slen < 2)
560 0 : sifs = xrealloc (sifs, 2);
561 0 : sifs[0] = ' ';
562 0 : sifs[1] = '\0';
563 : }
564 0 : t = array_to_string (a2, sifs, 0);
565 0 : free(sifs);
566 : } else
567 0 : t = array_to_string (a2, " ", 0);
568 0 : array_dispose (a2);
569 :
570 0 : return t;
571 : }
572 : /*
573 : * Allocate and return a new array element with index INDEX and value
574 : * VALUE.
575 : */
576 : ARRAY_ELEMENT *
577 248205259 : array_create_element(indx, value)
578 : arrayind_t indx;
579 : char *value;
580 : {
581 248205259 : ARRAY_ELEMENT *r;
582 :
583 248205259 : r = (ARRAY_ELEMENT *)xmalloc(sizeof(ARRAY_ELEMENT));
584 248205259 : r->ind = indx;
585 248205259 : r->value = value ? savestring(value) : (char *)NULL;
586 248205259 : r->next = r->prev = (ARRAY_ELEMENT *) NULL;
587 248205259 : return(r);
588 : }
589 :
590 : #ifdef INCLUDE_UNUSED
591 : ARRAY_ELEMENT *
592 : array_copy_element(ae)
593 : ARRAY_ELEMENT *ae;
594 : {
595 : return(ae ? array_create_element(element_index(ae), element_value(ae))
596 : : (ARRAY_ELEMENT *) NULL);
597 : }
598 : #endif
599 :
600 : void
601 95503240 : array_dispose_element(ae)
602 : ARRAY_ELEMENT *ae;
603 : {
604 95503240 : if (ae) {
605 95503240 : FREE(ae->value);
606 95503240 : free(ae);
607 : }
608 95503240 : }
609 :
610 : /*
611 : * Add a new element with index I and value V to array A (a[i] = v).
612 : */
613 : int
614 66839243 : array_insert(a, i, v)
615 : ARRAY *a;
616 : arrayind_t i;
617 : char *v;
618 : {
619 66839243 : register ARRAY_ELEMENT *new, *ae, *start;
620 :
621 66839243 : if (a == 0)
622 : return(-1);
623 66839243 : new = array_create_element(i, v);
624 66839243 : if (i > array_max_index(a)) {
625 : /*
626 : * Hook onto the end. This also works for an empty array.
627 : * Fast path for the common case of allocating arrays
628 : * sequentially.
629 : */
630 66839243 : ADD_BEFORE(a->head, new);
631 66839243 : a->max_index = i;
632 66839243 : a->num_elements++;
633 66839243 : SET_LASTREF(a, new);
634 66839243 : return(0);
635 : }
636 : #if OPTIMIZE_SEQUENTIAL_ARRAY_ASSIGNMENT
637 : /*
638 : * Otherwise we search for the spot to insert it. The lastref
639 : * handle optimizes the case of sequential or almost-sequential
640 : * assignments that are not at the end of the array.
641 : */
642 0 : start = LASTREF_START(a, i);
643 : #else
644 : start = element_forw(ae->head);
645 : #endif
646 0 : for (ae = start; ae != a->head; ae = element_forw(ae)) {
647 0 : if (element_index(ae) == i) {
648 : /*
649 : * Replacing an existing element.
650 : */
651 0 : array_dispose_element(new);
652 0 : free(element_value(ae));
653 0 : ae->value = v ? savestring(v) : (char *)NULL;
654 0 : SET_LASTREF(a, ae);
655 0 : return(0);
656 0 : } else if (element_index(ae) > i) {
657 0 : ADD_BEFORE(ae, new);
658 0 : a->num_elements++;
659 0 : SET_LASTREF(a, new);
660 0 : return(0);
661 : }
662 : }
663 0 : array_dispose_element(new);
664 0 : INVALIDATE_LASTREF(a);
665 : return (-1); /* problem */
666 : }
667 :
668 : /*
669 : * Delete the element with index I from array A and return it so the
670 : * caller can dispose of it.
671 : */
672 : ARRAY_ELEMENT *
673 0 : array_remove(a, i)
674 : ARRAY *a;
675 : arrayind_t i;
676 : {
677 0 : register ARRAY_ELEMENT *ae, *start;
678 :
679 0 : if (a == 0 || array_empty(a))
680 : return((ARRAY_ELEMENT *) NULL);
681 0 : start = LASTREF_START(a, i);
682 0 : for (ae = start; ae != a->head; ae = element_forw(ae))
683 0 : if (element_index(ae) == i) {
684 0 : ae->next->prev = ae->prev;
685 0 : ae->prev->next = ae->next;
686 0 : a->num_elements--;
687 0 : if (i == array_max_index(a))
688 0 : a->max_index = element_index(ae->prev);
689 : #if 0
690 : INVALIDATE_LASTREF(a);
691 : #else
692 0 : if (ae->next != a->head)
693 0 : SET_LASTREF(a, ae->next);
694 0 : else if (ae->prev != a->head)
695 0 : SET_LASTREF(a, ae->prev);
696 : else
697 0 : INVALIDATE_LASTREF(a);
698 : #endif
699 0 : return(ae);
700 : }
701 : return((ARRAY_ELEMENT *) NULL);
702 : }
703 :
704 : /*
705 : * Return the value of a[i].
706 : */
707 : char *
708 12469078 : array_reference(a, i)
709 : ARRAY *a;
710 : arrayind_t i;
711 : {
712 12469078 : register ARRAY_ELEMENT *ae, *start;
713 :
714 12469078 : if (a == 0 || array_empty(a))
715 : return((char *) NULL);
716 17886 : if (i > array_max_index(a))
717 : return((char *)NULL); /* Keep roving pointer into array to optimize sequential access */
718 17886 : start = LASTREF_START(a, i);
719 17886 : for (ae = start; ae != a->head; ae = element_forw(ae))
720 17886 : if (element_index(ae) == i) {
721 17886 : SET_LASTREF(a, ae);
722 17886 : return(element_value(ae));
723 : }
724 0 : UNSET_LASTREF(); /* XXX SET_LASTREF(a, start) ? */
725 0 : return((char *) NULL);
726 : }
727 :
728 : /* Convenience routines for the shell to translate to and from the form used
729 : by the rest of the code. */
730 :
731 : WORD_LIST *
732 0 : array_to_word_list(a)
733 : ARRAY *a;
734 : {
735 0 : WORD_LIST *list;
736 0 : ARRAY_ELEMENT *ae;
737 :
738 0 : if (a == 0 || array_empty(a))
739 : return((WORD_LIST *)NULL);
740 0 : list = (WORD_LIST *)NULL;
741 0 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
742 0 : list = make_word_list (make_bare_word(element_value(ae)), list);
743 0 : return (REVERSE_LIST(list, WORD_LIST *));
744 : }
745 :
746 : ARRAY *
747 0 : array_from_word_list (list)
748 : WORD_LIST *list;
749 : {
750 0 : ARRAY *a;
751 :
752 0 : if (list == 0)
753 : return((ARRAY *)NULL);
754 0 : a = array_create();
755 0 : return (array_assign_list (a, list));
756 : }
757 :
758 : WORD_LIST *
759 0 : array_keys_to_word_list(a)
760 : ARRAY *a;
761 : {
762 0 : WORD_LIST *list;
763 0 : ARRAY_ELEMENT *ae;
764 0 : char *t;
765 :
766 0 : if (a == 0 || array_empty(a))
767 : return((WORD_LIST *)NULL);
768 0 : list = (WORD_LIST *)NULL;
769 0 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
770 0 : t = itos(element_index(ae));
771 0 : list = make_word_list (make_bare_word(t), list);
772 0 : free(t);
773 : }
774 0 : return (REVERSE_LIST(list, WORD_LIST *));
775 : }
776 :
777 : ARRAY *
778 0 : array_assign_list (array, list)
779 : ARRAY *array;
780 : WORD_LIST *list;
781 : {
782 0 : register WORD_LIST *l;
783 0 : register arrayind_t i;
784 :
785 0 : for (l = list, i = 0; l; l = l->next, i++)
786 0 : array_insert(array, i, l->word->word);
787 0 : return array;
788 : }
789 :
790 : char **
791 0 : array_to_argv (a)
792 : ARRAY *a;
793 : {
794 0 : char **ret, *t;
795 0 : int i;
796 0 : ARRAY_ELEMENT *ae;
797 :
798 0 : if (a == 0 || array_empty(a))
799 : return ((char **)NULL);
800 0 : ret = strvec_create (array_num_elements (a) + 1);
801 0 : i = 0;
802 0 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
803 0 : t = element_value (ae);
804 0 : ret[i++] = t ? savestring (t) : (char *)NULL;
805 : }
806 0 : ret[i] = (char *)NULL;
807 0 : return (ret);
808 : }
809 :
810 : /*
811 : * Return a string that is the concatenation of the elements in A from START
812 : * to END, separated by SEP.
813 : */
814 : static char *
815 0 : array_to_string_internal (start, end, sep, quoted)
816 : ARRAY_ELEMENT *start, *end;
817 : char *sep;
818 : int quoted;
819 : {
820 0 : char *result, *t;
821 0 : ARRAY_ELEMENT *ae;
822 0 : int slen, rsize, rlen, reg;
823 :
824 0 : if (start == end) /* XXX - should not happen */
825 : return ((char *)NULL);
826 :
827 0 : slen = strlen(sep);
828 0 : result = NULL;
829 0 : for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
830 0 : if (rsize == 0)
831 0 : result = (char *)xmalloc (rsize = 64);
832 0 : if (element_value(ae)) {
833 0 : t = quoted ? quote_string(element_value(ae)) : element_value(ae);
834 0 : reg = strlen(t);
835 0 : RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
836 : rsize, rsize);
837 0 : strcpy(result + rlen, t);
838 0 : rlen += reg;
839 0 : if (quoted)
840 0 : free(t);
841 : /*
842 : * Add a separator only after non-null elements.
843 : */
844 0 : if (element_forw(ae) != end) {
845 0 : strcpy(result + rlen, sep);
846 0 : rlen += slen;
847 : }
848 : }
849 : }
850 0 : if (result)
851 0 : result[rlen] = '\0'; /* XXX */
852 : return(result);
853 : }
854 :
855 : char *
856 1328 : array_to_assign (a, quoted)
857 : ARRAY *a;
858 : int quoted;
859 : {
860 1328 : char *result, *valstr, *is;
861 1328 : char indstr[INT_STRLEN_BOUND(intmax_t) + 1];
862 1328 : ARRAY_ELEMENT *ae;
863 1328 : int rsize, rlen, elen;
864 :
865 1328 : if (a == 0 || array_empty (a))
866 : return((char *)NULL);
867 :
868 386 : result = (char *)xmalloc (rsize = 128);
869 386 : result[0] = '(';
870 386 : rlen = 1;
871 :
872 1917 : for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
873 1531 : is = inttostr (element_index(ae), indstr, sizeof(indstr));
874 3062 : valstr = element_value (ae) ?
875 1531 : (ansic_shouldquote (element_value (ae)) ?
876 1531 : ansic_quote (element_value(ae), 0, (int *)0) :
877 1531 : sh_double_quote (element_value (ae)))
878 1531 : : (char *)NULL;
879 1531 : elen = STRLEN (is) + 8 + STRLEN (valstr);
880 1531 : RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
881 :
882 1531 : result[rlen++] = '[';
883 1531 : strcpy (result + rlen, is);
884 1531 : rlen += STRLEN (is);
885 1531 : result[rlen++] = ']';
886 1531 : result[rlen++] = '=';
887 1531 : if (valstr) {
888 1531 : strcpy (result + rlen, valstr);
889 1531 : rlen += STRLEN (valstr);
890 : }
891 :
892 1531 : if (element_forw(ae) != a->head)
893 1145 : result[rlen++] = ' ';
894 :
895 1531 : FREE (valstr);
896 : }
897 386 : RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
898 386 : result[rlen++] = ')';
899 386 : result[rlen] = '\0';
900 386 : if (quoted) {
901 : /* This is not as efficient as it could be... */
902 0 : valstr = sh_single_quote (result);
903 0 : free (result);
904 0 : result = valstr;
905 : }
906 : return(result);
907 : }
908 :
909 : char *
910 0 : array_to_string (a, sep, quoted)
911 : ARRAY *a;
912 : char *sep;
913 : int quoted;
914 : {
915 0 : if (a == 0)
916 : return((char *)NULL);
917 0 : if (array_empty(a))
918 0 : return(savestring(""));
919 0 : return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
920 : }
921 :
922 : #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
923 : /*
924 : * Return an array consisting of elements in S, separated by SEP
925 : */
926 : ARRAY *
927 : array_from_string(s, sep)
928 : char *s, *sep;
929 : {
930 : ARRAY *a;
931 : WORD_LIST *w;
932 :
933 : if (s == 0)
934 : return((ARRAY *)NULL);
935 : w = list_string (s, sep, 0);
936 : if (w == 0)
937 : return((ARRAY *)NULL);
938 : a = array_from_word_list (w);
939 : return (a);
940 : }
941 : #endif
942 :
943 : #if defined (TEST_ARRAY)
944 : /*
945 : * To make a running version, compile -DTEST_ARRAY and link with:
946 : * xmalloc.o syntax.o lib/malloc/libmalloc.a lib/sh/libsh.a
947 : */
948 : int interrupt_immediately = 0;
949 :
950 : int
951 : signal_is_trapped(s)
952 : int s;
953 : {
954 : return 0;
955 : }
956 :
957 : void
958 : fatal_error(const char *s, ...)
959 : {
960 : fprintf(stderr, "array_test: fatal memory error\n");
961 : abort();
962 : }
963 :
964 : void
965 : programming_error(const char *s, ...)
966 : {
967 : fprintf(stderr, "array_test: fatal programming error\n");
968 : abort();
969 : }
970 :
971 : WORD_DESC *
972 : make_bare_word (s)
973 : const char *s;
974 : {
975 : WORD_DESC *w;
976 :
977 : w = (WORD_DESC *)xmalloc(sizeof(WORD_DESC));
978 : w->word = s ? savestring(s) : savestring ("");
979 : w->flags = 0;
980 : return w;
981 : }
982 :
983 : WORD_LIST *
984 : make_word_list(x, l)
985 : WORD_DESC *x;
986 : WORD_LIST *l;
987 : {
988 : WORD_LIST *w;
989 :
990 : w = (WORD_LIST *)xmalloc(sizeof(WORD_LIST));
991 : w->word = x;
992 : w->next = l;
993 : return w;
994 : }
995 :
996 : WORD_LIST *
997 : list_string(s, t, i)
998 : char *s, *t;
999 : int i;
1000 : {
1001 : char *r, *a;
1002 : WORD_LIST *wl;
1003 :
1004 : if (s == 0)
1005 : return (WORD_LIST *)NULL;
1006 : r = savestring(s);
1007 : wl = (WORD_LIST *)NULL;
1008 : a = strtok(r, t);
1009 : while (a) {
1010 : wl = make_word_list (make_bare_word(a), wl);
1011 : a = strtok((char *)NULL, t);
1012 : }
1013 : return (REVERSE_LIST (wl, WORD_LIST *));
1014 : }
1015 :
1016 : GENERIC_LIST *
1017 : list_reverse (list)
1018 : GENERIC_LIST *list;
1019 : {
1020 : register GENERIC_LIST *next, *prev;
1021 :
1022 : for (prev = 0; list; ) {
1023 : next = list->next;
1024 : list->next = prev;
1025 : prev = list;
1026 : list = next;
1027 : }
1028 : return prev;
1029 : }
1030 :
1031 : char *
1032 : pat_subst(s, t, u, i)
1033 : char *s, *t, *u;
1034 : int i;
1035 : {
1036 : return ((char *)NULL);
1037 : }
1038 :
1039 : char *
1040 : quote_string(s)
1041 : char *s;
1042 : {
1043 : return savestring(s);
1044 : }
1045 :
1046 : print_element(ae)
1047 : ARRAY_ELEMENT *ae;
1048 : {
1049 : char lbuf[INT_STRLEN_BOUND (intmax_t) + 1];
1050 :
1051 : printf("array[%s] = %s\n",
1052 : inttostr (element_index(ae), lbuf, sizeof (lbuf)),
1053 : element_value(ae));
1054 : }
1055 :
1056 : print_array(a)
1057 : ARRAY *a;
1058 : {
1059 : printf("\n");
1060 : array_walk(a, print_element, (void *)NULL);
1061 : }
1062 :
1063 : main()
1064 : {
1065 : ARRAY *a, *new_a, *copy_of_a;
1066 : ARRAY_ELEMENT *ae, *aew;
1067 : char *s;
1068 :
1069 : a = array_create();
1070 : array_insert(a, 1, "one");
1071 : array_insert(a, 7, "seven");
1072 : array_insert(a, 4, "four");
1073 : array_insert(a, 1029, "one thousand twenty-nine");
1074 : array_insert(a, 12, "twelve");
1075 : array_insert(a, 42, "forty-two");
1076 : print_array(a);
1077 : s = array_to_string (a, " ", 0);
1078 : printf("s = %s\n", s);
1079 : copy_of_a = array_from_string(s, " ");
1080 : printf("copy_of_a:");
1081 : print_array(copy_of_a);
1082 : array_dispose(copy_of_a);
1083 : printf("\n");
1084 : free(s);
1085 : ae = array_remove(a, 4);
1086 : array_dispose_element(ae);
1087 : ae = array_remove(a, 1029);
1088 : array_dispose_element(ae);
1089 : array_insert(a, 16, "sixteen");
1090 : print_array(a);
1091 : s = array_to_string (a, " ", 0);
1092 : printf("s = %s\n", s);
1093 : copy_of_a = array_from_string(s, " ");
1094 : printf("copy_of_a:");
1095 : print_array(copy_of_a);
1096 : array_dispose(copy_of_a);
1097 : printf("\n");
1098 : free(s);
1099 : array_insert(a, 2, "two");
1100 : array_insert(a, 1029, "new one thousand twenty-nine");
1101 : array_insert(a, 0, "zero");
1102 : array_insert(a, 134, "");
1103 : print_array(a);
1104 : s = array_to_string (a, ":", 0);
1105 : printf("s = %s\n", s);
1106 : copy_of_a = array_from_string(s, ":");
1107 : printf("copy_of_a:");
1108 : print_array(copy_of_a);
1109 : array_dispose(copy_of_a);
1110 : printf("\n");
1111 : free(s);
1112 : new_a = array_copy(a);
1113 : print_array(new_a);
1114 : s = array_to_string (new_a, ":", 0);
1115 : printf("s = %s\n", s);
1116 : copy_of_a = array_from_string(s, ":");
1117 : free(s);
1118 : printf("copy_of_a:");
1119 : print_array(copy_of_a);
1120 : array_shift(copy_of_a, 2, AS_DISPOSE);
1121 : printf("copy_of_a shifted by two:");
1122 : print_array(copy_of_a);
1123 : ae = array_shift(copy_of_a, 2, 0);
1124 : printf("copy_of_a shifted by two:");
1125 : print_array(copy_of_a);
1126 : for ( ; ae; ) {
1127 : aew = element_forw(ae);
1128 : array_dispose_element(ae);
1129 : ae = aew;
1130 : }
1131 : array_rshift(copy_of_a, 1, (char *)0);
1132 : printf("copy_of_a rshift by 1:");
1133 : print_array(copy_of_a);
1134 : array_rshift(copy_of_a, 2, "new element zero");
1135 : printf("copy_of_a rshift again by 2 with new element zero:");
1136 : print_array(copy_of_a);
1137 : s = array_to_assign(copy_of_a, 0);
1138 : printf("copy_of_a=%s\n", s);
1139 : free(s);
1140 : ae = array_shift(copy_of_a, array_num_elements(copy_of_a), 0);
1141 : for ( ; ae; ) {
1142 : aew = element_forw(ae);
1143 : array_dispose_element(ae);
1144 : ae = aew;
1145 : }
1146 : array_dispose(copy_of_a);
1147 : printf("\n");
1148 : array_dispose(a);
1149 : array_dispose(new_a);
1150 : }
1151 :
1152 : #endif /* TEST_ARRAY */
1153 : #endif /* ARRAY_VARS */
|
