X-Git-Url: http://review.tizen.org/git/?p=platform%2Fupstream%2Fbash.git;a=blobdiff_plain;f=array.c;h=4359a52fa1d88e4d52fcff439092bb89950e9084;hp=a8c7766e1e81c4d1006e5f5830a75f7d3e059c1d;hb=HEAD;hpb=3185942a5234e26ab13fa02f9c51d340cec514f8

diff --git a/array.c b/array.c
index a8c7766..4359a52 100644
--- a/array.c
+++ b/array.c
@@ -55,6 +55,35 @@
 
 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)	(lastarray && (a) == lastarray)
+
+#define LASTREF_START(a, i) \
+	(IS_LASTREF(a) && i >= element_index(lastref)) ? lastref \
+						       : element_forw(a->head)
+
+#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 +116,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 +215,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 +245,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 +282,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 +296,7 @@ char	*s;
 
 	a->max_index = element_index(a->head->prev);
 
+	INVALIDATE_LASTREF(a);
 	return (a->num_elements);
 }
 
@@ -580,7 +614,7 @@ ARRAY	*a;
 arrayind_t	i;
 char	*v;
 {
-	register ARRAY_ELEMENT *new, *ae;
+	register ARRAY_ELEMENT *new, *ae, *start;
 
 	if (a == 0)
 		return(-1);
@@ -594,12 +628,20 @@ char	*v;
 		ADD_BEFORE(a->head, new);
 		a->max_index = i;
 		a->num_elements++;
+		SET_LASTREF(a, new);
 		return(0);
 	}
+#if OPTIMIZE_SEQUENTIAL_ARRAY_ASSIGNMENT
 	/*
-	 * Otherwise we search for the spot to insert it.
+	 * Otherwise we search for the spot to insert it.  The lastref
+	 * handle optimizes the case of sequential or almost-sequential
+	 * assignments that are not at the end of the array.
 	 */
-	for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae)) {
+	start = LASTREF_START(a, i);
+#else
+	start = element_forw(ae->head);
+#endif
+	for (ae = start; ae != a->head; ae = element_forw(ae)) {
 		if (element_index(ae) == i) {
 			/*
 			 * Replacing an existing element.
@@ -607,13 +649,17 @@ 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);
 		}
 	}
+	array_dispose_element(new);
+	INVALIDATE_LASTREF(a);
 	return (-1);		/* problem */
 }
 
@@ -626,17 +672,28 @@ array_remove(a, i)
 ARRAY	*a;
 arrayind_t	i;
 {
-	register ARRAY_ELEMENT *ae;
+	register ARRAY_ELEMENT *ae, *start;
 
 	if (a == 0 || array_empty(a))
 		return((ARRAY_ELEMENT *) NULL);
-	for (ae = element_forw(a->head); ae != a->head; ae = element_forw(ae))
+	start = LASTREF_START(a, i);
+	for (ae = start; ae != a->head; ae = element_forw(ae))
 		if (element_index(ae) == i) {
 			ae->next->prev = ae->prev;
 			ae->prev->next = ae->next;
 			a->num_elements--;
 			if (i == array_max_index(a))
 				a->max_index = element_index(ae->prev);
+#if 0
+			INVALIDATE_LASTREF(a);
+#else
+			if (ae->next != a->head)
+				SET_LASTREF(a, ae->next);
+			else if (ae->prev != a->head)
+				SET_LASTREF(a, ae->prev);
+			else
+				INVALIDATE_LASTREF(a);
+#endif
 			return(ae);
 		}
 	return((ARRAY_ELEMENT *) NULL);
@@ -650,13 +707,19 @@ array_reference(a, i)
 ARRAY	*a;
 arrayind_t	i;
 {
-	register ARRAY_ELEMENT *ae;
+	register ARRAY_ELEMENT *ae, *start;
 
 	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 */
+	start = LASTREF_START(a, i);
+	for (ae = start; 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);
 }