Bash-4.1 distribution source

[thirdparty/bash.git] / array.c

diff --git a/array.c b/array.c
index a8c7766e1e81c4d1006e5f5830a75f7d3e059c1d..27fe17083ff0db306f0efb8bbf56d941ac05fb72 100644 (file)
--- a/array.c
+++ b/array.c
@@ -55,6 +55,31 @@
 
 static char *array_to_string_internal __P((ARRAY_ELEMENT *, ARRAY_ELEMENT *, char *, int));
 
+static ARRAY *lastarray = 0;
+static ARRAY_ELEMENT *lastref = 0;
+
+#define IS_LASTREF(a)  ((a) == lastarray)
+
+#define INVALIDATE_LASTREF(a) \
+do { \
+       if ((a) == lastarray) { \
+               lastarray = 0; \
+               lastref = 0; \
+       } \
+} while (0)
+
+#define SET_LASTREF(a, e) \
+do { \
+       lastarray = (a); \
+       lastref = (e); \
+} while (0)
+
+#define UNSET_LASTREF() \
+do { \
+       lastarray = 0; \
+       lastref = 0; \
+} while (0)
+
 ARRAY *
 array_create()
 {
@@ -87,6 +112,7 @@ ARRAY        *a;
        a->head->next = a->head->prev = a->head;
        a->max_index = -1;
        a->num_elements = 0;
+       INVALIDATE_LASTREF(a);
 }
 
 void
@@ -185,6 +211,7 @@ int n, flags;
        if (a == 0 || array_empty(a) || n <= 0)
                return ((ARRAY_ELEMENT *)NULL);
 
+       INVALIDATE_LASTREF(a);
        for (i = 0, ret = ae = element_forw(a->head); ae != a->head && i < n; ae = element_forw(ae), i++)
                ;
        if (ae == a->head) {
@@ -214,7 +241,7 @@ int n, flags;
                element_index(ae) -= n; /* renumber retained indices */
 
        a->num_elements -= n;           /* modify bookkeeping information */
-       a->max_index -= n;
+       a->max_index = element_index(a->head->prev);
 
        if (flags & AS_DISPOSE) {
                for (ae = ret; ae; ) {
@@ -251,8 +278,10 @@ char       *s;
                new = array_create_element(0, s);
                ADD_BEFORE(ae, new);
                a->num_elements++;
-               if (array_num_elements(a) == 1)         /* array was empty */
+               if (array_num_elements(a) == 1) {       /* array was empty */
+                       a->max_index = 0;
                        return 1;
+               }
        }
 
        /*
@@ -263,6 +292,7 @@ char        *s;
 
        a->max_index = element_index(a->head->prev);
 
+       INVALIDATE_LASTREF(a);
        return (a->num_elements);
 }
 
@@ -594,6 +624,7 @@ char        *v;
                ADD_BEFORE(a->head, new);
                a->max_index = i;
                a->num_elements++;
+               SET_LASTREF(a, new);
                return(0);
        }
        /*
@@ -607,13 +638,16 @@ char      *v;
                        array_dispose_element(new);
                        free(element_value(ae));
                        ae->value = v ? savestring(v) : (char *)NULL;
+                       SET_LASTREF(a, ae);
                        return(0);
                } else if (element_index(ae) > i) {
                        ADD_BEFORE(ae, new);
                        a->num_elements++;
+                       SET_LASTREF(a, new);
                        return(0);
                }
        }
+       INVALIDATE_LASTREF(a);
        return (-1);            /* problem */
 }
 
@@ -637,6 +671,7 @@ arrayind_t  i;
                        a->num_elements--;
                        if (i == array_max_index(a))
                                a->max_index = element_index(ae->prev);
+                       INVALIDATE_LASTREF(a);
                        return(ae);
                }
        return((ARRAY_ELEMENT *) NULL);
@@ -654,9 +689,19 @@ arrayind_t i;
 
        if (a == 0 || array_empty(a))
                return((char *) NULL);
-       for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
-               if (element_index(ae) == i)
+       if (i > array_max_index(a))
+               return((char *)NULL);
+       /* Keep roving pointer into array to optimize sequential access */
+       if (lastref && IS_LASTREF(a))
+               ae = (i >= element_index(lastref)) ? lastref : element_forw(a->head);
+       else
+               ae = element_forw(a->head);
+       for ( ; ae != a->head; ae = element_forw(ae))
+               if (element_index(ae) == i) {
+                       SET_LASTREF(a, ae);
                        return(element_value(ae));
+               }
+       UNSET_LASTREF();
        return((char *) NULL);
 }