Imported from ../bash-2.04.tar.gz.
[platform/upstream/bash.git] / array.c
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 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 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
19    version.
20
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
24    for more details.
25
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. */
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 extern char *quote_string ();   /* XXX */
49
50 #define ADD_BEFORE(ae, new) \
51         do { \
52                 ae->prev->next = new; \
53                 new->prev = ae->prev; \
54                 ae->prev = new; \
55                 new->next = ae; \
56         } while(0)
57
58 /*
59  * Allocate and return a new array element with index INDEX and value
60  * VALUE.
61  */
62 ARRAY_ELEMENT *
63 new_array_element(indx, value)
64 arrayind_t      indx;
65 char    *value;
66 {
67         ARRAY_ELEMENT *r;
68
69         r = (ARRAY_ELEMENT *) xmalloc(sizeof(ARRAY_ELEMENT));
70         r->ind = indx;
71         r->value = value ? savestring(value) : (char *)NULL;
72         r->next = r->prev = (ARRAY_ELEMENT *) NULL;
73         return(r);
74 }
75
76 void
77 destroy_array_element(ae)
78 ARRAY_ELEMENT   *ae;
79 {
80         FREE(ae->value);
81         free(ae);
82 }
83
84 ARRAY *
85 new_array()
86 {
87         ARRAY   *r;
88         ARRAY_ELEMENT   *head;
89
90         r =(ARRAY *) xmalloc(sizeof(ARRAY));
91         r->type = array_indexed;
92         r->max_index = r->max_size = -1;
93         r->num_elements = 0;
94         head = new_array_element(-1, (char *)NULL);     /* dummy head */
95         head->prev = head->next = head;
96         r->head = head;
97         return(r);
98 }
99
100 void
101 empty_array (a)
102 ARRAY   *a;
103 {
104         register ARRAY_ELEMENT *r, *r1;
105
106         if (a == 0)
107                 return;
108         for (r = element_forw(a->head); r != a->head; ) {
109                 r1 = element_forw(r);
110                 destroy_array_element(r);
111                 r = r1;
112         }
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;
116 }
117
118 void
119 dispose_array(a)
120 ARRAY   *a;
121 {
122         if (a == 0)
123                 return;
124         empty_array (a);
125         destroy_array_element(a->head);
126         free(a);
127 }
128
129 ARRAY *
130 dup_array(a)
131 ARRAY   *a;
132 {
133         ARRAY   *a1;
134         ARRAY_ELEMENT   *ae, *new;
135
136         if (!a)
137                 return((ARRAY *) NULL);
138         a1 = new_array();
139         a1->type = a->type;
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);
146         }
147         return(a1);
148 }
149
150 #ifdef INCLUDE_UNUSED
151 /*
152  * Make and return a new array composed of the elements in array A from
153  * S to E, inclusive.
154  */
155 ARRAY *
156 dup_array_subrange(array, s, e)
157 ARRAY           *array;
158 ARRAY_ELEMENT   *s, *e;
159 {
160         ARRAY   *a;
161         ARRAY_ELEMENT *p, *n;
162         int     i;
163
164         a = new_array ();
165         a->type = array->type;
166
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);
170         }
171         a->num_elements = a->max_index = i;
172         return a;
173 }
174 #endif
175
176 #ifdef INCLUDE_UNUSED
177 ARRAY_ELEMENT *
178 copy_array_element(ae)
179 ARRAY_ELEMENT   *ae;
180 {
181         return(ae ? new_array_element(element_index(ae), element_value(ae))
182                   : (ARRAY_ELEMENT *) NULL);
183 }
184 #endif
185
186 /*
187  * Add a new element with index I and value V to array A (a[i] = v).
188  */
189 int
190 array_add_element(a, i, v)
191 ARRAY   *a;
192 arrayind_t      i;
193 char    *v;
194 {
195         register ARRAY_ELEMENT *new, *ae;
196
197         if (!a)
198                 return(-1);
199         new = new_array_element(i, v);
200         if (i > array_max_index(a)) {
201                 /*
202                  * Hook onto the end.  This also works for an empty array.
203                  * Fast path for the common case of allocating arrays
204                  * sequentially.
205                  */
206                 ADD_BEFORE(a->head, new);
207                 a->max_index = i;
208                 a->num_elements++;
209                 return(0);
210         }
211         /*
212          * Otherwise we search for the spot to insert it.
213          */
214         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
215                 if (element_index(ae) == i) {
216                         /*
217                          * Replacing an existing element.
218                          */
219                         destroy_array_element(new);
220                         free(element_value(ae));
221                         ae->value = savestring(v);
222                         return(0);
223                 } else if (element_index(ae) > i) {
224                         ADD_BEFORE(ae, new);
225                         a->num_elements++;
226                         return(0);
227                 }
228         }
229         return (-1);            /* problem */
230 }
231
232 /*
233  * Delete the element with index I from array A and return it so the
234  * caller can dispose of it.
235  */
236 ARRAY_ELEMENT *
237 array_delete_element(a, i)
238 ARRAY   *a;
239 arrayind_t      i;
240 {
241         register ARRAY_ELEMENT *ae;
242
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;
249                         a->num_elements--;
250                         if (i == array_max_index(a))
251                                 a->max_index = element_index(ae->prev);
252                         return(ae);
253                 }
254         return((ARRAY_ELEMENT *) NULL);
255 }
256
257 /*
258  * Return the value of a[i].
259  */
260 char *
261 array_reference(a, i)
262 ARRAY   *a;
263 arrayind_t      i;
264 {
265         register ARRAY_ELEMENT *ae;
266
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);
273 }
274
275 #ifdef TEST_ARRAY
276 /*
277  * Walk the array, calling FUNC once for each element, with the array
278  * element as the argument.
279  */
280 void
281 array_walk(a, func)
282 ARRAY   *a;
283 Function *func;
284 {
285         register ARRAY_ELEMENT *ae;
286
287         if (a == 0 || array_empty(a))
288                 return;
289         for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
290                 (*func)(ae);
291 }
292 #endif
293
294 /*
295  * Return a string that is the concatenation of all the elements in A,
296  * separated by SEP.
297  */
298 static char *
299 array_to_string_internal (start, end, sep, quoted)
300 ARRAY_ELEMENT   *start, *end;
301 char    *sep;
302 int     quoted;
303 {
304         char    *result, *t;
305         ARRAY_ELEMENT *ae;
306         int     slen, rsize, rlen, reg;
307
308         if (start == end)       /* XXX - should not happen */
309                 return ((char *)NULL);
310
311         slen = strlen(sep);
312         for (rsize = rlen = 0, ae = start; ae != end; ae = element_forw(ae)) {
313                 if (rsize == 0)
314                         result = xmalloc (rsize = 64);
315                 if (element_value(ae)) {
316                         t = quoted ? quote_string(element_value(ae)) : element_value(ae);
317                         reg = strlen(t);
318                         RESIZE_MALLOCED_BUFFER (result, rlen, (reg + slen + 2),
319                                                 rsize, rsize);
320                         strcpy(result + rlen, t);
321                         rlen += reg;
322                         if (quoted && t)
323                                 free(t);
324                         /*
325                          * Add a separator only after non-null elements.
326                          */
327                         if (element_forw(ae) != end) {
328                                 strcpy(result + rlen, sep);
329                                 rlen += slen;
330                         }
331                 }
332         }
333         result[rlen] = '\0';    /* XXX */
334         return(result);
335 }
336
337 char *
338 array_to_string (a, sep, quoted)
339 ARRAY   *a;
340 char    *sep;
341 int     quoted;
342 {
343         if (a == 0)
344                 return((char *)NULL);
345         if (array_empty(a))
346                 return(savestring(""));
347         return (array_to_string_internal (element_forw(a->head), a->head, sep, quoted));
348 }
349
350 char *
351 array_to_assignment_string (a)
352 ARRAY   *a;
353 {
354         char    *result, *indstr, *valstr;
355         ARRAY_ELEMENT *ae;
356         int     rsize, rlen, elen;
357
358         if (a == 0 || array_empty (a))
359                 return((char *)NULL);
360
361         result = xmalloc (rsize = 128);
362         result[0] = '(';
363         rlen = 1;
364
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))
368                                             : (char *)NULL;
369                 elen = STRLEN (indstr) + 8 + STRLEN (valstr);
370                 RESIZE_MALLOCED_BUFFER (result, rlen, (elen + 1), rsize, rsize);
371
372                 result[rlen++] = '[';
373                 strcpy (result + rlen, indstr);
374                 rlen += STRLEN (indstr);
375                 result[rlen++] = ']';
376                 result[rlen++] = '=';
377                 if (valstr) {
378                         strcpy (result + rlen, valstr);
379                         rlen += STRLEN (valstr);
380                 }
381
382                 if (element_forw(ae) != a->head)
383                   result[rlen++] = ' ';
384
385                 FREE (indstr);
386                 FREE (valstr);
387         }
388         RESIZE_MALLOCED_BUFFER (result, rlen, 1, rsize, 8);
389         result[rlen++] = ')';
390         result[rlen] = '\0';
391         return(result);
392 }
393
394 char *
395 quoted_array_assignment_string (a)
396 ARRAY   *a;
397 {
398         char *vstr, *sv;
399
400         sv = array_to_assignment_string (a);
401         if (sv == 0)
402                 return ((char *)NULL);
403
404         vstr = single_quote (sv);
405         free (sv);
406         return (vstr);
407 }
408
409 #if 0
410 /* Determine if s2 occurs in s1.  If so, return a pointer to the
411    match in s1.  The compare is case sensitive. */
412 static char *
413 sindex (s1, s2)
414 register char *s1, *s2;
415 {
416         register int i, l, len;
417
418         for (i = 0, l = strlen(s2), len = strlen(s1); (len - i) >= l; i++)
419                 if (strncmp (s1 + i, s2, l) == 0)
420                         return (s1 + i);
421         return ((char *)NULL);
422 }
423 #endif
424
425 #if defined (INCLUDE_UNUSED) || defined (TEST_ARRAY)
426 /*
427  * Return an array consisting of elements in S, separated by SEP
428  */
429 ARRAY *
430 string_to_array(s, sep)
431 char    *s, *sep;
432 {
433         ARRAY   *a;
434         WORD_LIST *w;
435
436         if (s == 0)
437                 return((ARRAY *)NULL);
438         w = list_string (s, sep, 0);
439         if (w == 0)
440                 return((ARRAY *)NULL);
441         a = word_list_to_array (w);
442         return (a);
443 }
444 #endif
445
446 /* Convenience routines for the shell to translate to and from the form used
447    by the rest of the code. */
448 WORD_LIST *
449 array_to_word_list(a)
450 ARRAY   *a;
451 {
452         WORD_LIST       *list;
453         ARRAY_ELEMENT   *ae;
454
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 *));
461 }
462
463 char **
464 array_to_argv (a)
465 ARRAY   *a;
466 {
467         char            **ret, *t;
468         int             i;
469         ARRAY_ELEMENT   *ae;
470
471         if (a == 0 || array_empty(a))
472                 return ((char **)NULL);
473         ret = alloc_array (array_num_elements (a) + 1);
474         i = 0;
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;
478         }
479         ret[i] = (char *)NULL;
480         return (ret);
481 }
482         
483 ARRAY *
484 assign_word_list (array, list)
485 ARRAY   *array;
486 WORD_LIST       *list;
487 {
488         register WORD_LIST *l;
489         register arrayind_t i;
490
491         for (l = list, i = 0; l; l = l->next, i++)
492                 array_add_element(array, i, l->word->word);
493         return array;
494 }
495
496 ARRAY *
497 word_list_to_array (list)
498 WORD_LIST       *list;
499 {
500         ARRAY   *a;
501
502         if (list == 0)
503                 return((ARRAY *)NULL);
504         a = new_array();
505         return (assign_word_list (a, list));
506 }
507
508 ARRAY   *
509 array_quote(array)
510 ARRAY   *array;
511 {
512         ARRAY_ELEMENT   *a;
513         char    *t;
514
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);
519                 FREE(a->value);
520                 a->value = t;
521         }
522         return array;
523 }
524
525 char *
526 array_subrange (a, start, end, quoted)
527 ARRAY   *a;
528 int     start, end, quoted;
529 {
530         ARRAY_ELEMENT   *h, *p;
531         int     i;
532
533         p = array_head (a);
534         if (p == 0 || array_empty (a) || start > array_num_elements (a))
535                 return ((char *)NULL);
536
537         for (i = 0, p = element_forw(p); p != a->head && i < start; i++, p = element_forw(p))
538                 ;
539         if (p == a->head)
540                 return ((char *)NULL);
541         for (h = p; p != a->head && i < end; i++, p = element_forw(p))
542                 ;
543
544         return (array_to_string_internal (h, p, " ", quoted));
545 }
546
547 char *
548 array_pat_subst (a, pat, rep, mflags)
549 ARRAY   *a;
550 char    *pat, *rep;
551 int     mflags;
552 {
553         ARRAY           *a2;
554         ARRAY_ELEMENT   *e;
555         char    *t;
556
557         if (array_head (a) == 0 || array_empty (a))
558                 return ((char *)NULL);
559
560         a2 = dup_array (a);
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));
564                 e->value = t;
565         }
566
567         if (mflags & MATCH_QUOTED)
568                 array_quote (a2);
569         t = array_to_string (a2, " ", 0);
570         dispose_array (a2);
571
572         return t;
573 }
574
575
576 #if defined (TEST_ARRAY)
577 print_element(ae)
578 ARRAY_ELEMENT   *ae;
579 {
580         printf("array[%d] = %s\n",(int)element_index(ae), element_value(ae));
581 }
582
583 print_array(a)
584 ARRAY   *a;
585 {
586         printf("\n");
587         array_walk(a, print_element);
588 }
589
590 main()
591 {
592         ARRAY   *a, *new_a, *copy_of_a;
593         ARRAY_ELEMENT   *ae;
594         char    *s;
595
596         a = new_array();
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");
603         print_array(a);
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);
610         printf("\n");
611         free(s);
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");
617         print_array(a);
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);
624         printf("\n");
625         free(s);
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, "");
630         print_array(a);
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);
637         printf("\n");
638         free(s);
639         new_a = copy_array(a);
640         print_array(new_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);
647         printf("\n");
648         free(s);
649         dispose_array(a);
650         dispose_array(new_a);
651 }
652
653 #endif /* TEST_ARRAY */
654 #endif /* ARRAY_VARS */