Bash-4.1 distribution source

1 files changed, 49 insertions, 4 deletions

diff --git a/array.c b/array.c
index a8c7766..27fe170 100644
--- 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);
 }