4 files changed, 50 insertions, 19 deletions

diff --git a/src/lisp/ao_lisp.h b/src/lisp/ao_lisp.h
index af6ff8bb..1f7c85e1 100644
--- a/src/lisp/ao_lisp.h
+++ b/src/lisp/ao_lisp.h
@@ -621,7 +621,7 @@ ao_lisp_read_eval_print(void);
 /* frame */
 extern const struct ao_lisp_type ao_lisp_frame_type;
 
-#define AO_LISP_FRAME_FREE	4
+#define AO_LISP_FRAME_FREE	6
 
 extern struct ao_lisp_frame	*ao_lisp_frame_free_list[AO_LISP_FRAME_FREE];
 
@@ -637,6 +637,9 @@ ao_lisp_frame_new(int num);
 void
 ao_lisp_frame_free(struct ao_lisp_frame *frame);
 
+void
+ao_lisp_frame_bind(struct ao_lisp_frame *frame, int num, ao_poly atom, ao_poly val);
+
 int
 ao_lisp_frame_add(struct ao_lisp_frame **frame, ao_poly atom, ao_poly val);
 
diff --git a/src/lisp/ao_lisp_frame.c b/src/lisp/ao_lisp_frame.c
index 17fa141a..05f6d253 100644
--- a/src/lisp/ao_lisp_frame.c
+++ b/src/lisp/ao_lisp_frame.c
@@ -128,14 +128,32 @@ ao_lisp_frame_print(ao_poly p)
 	printf("}");
 }
 
+static int
+ao_lisp_frame_find(struct ao_lisp_frame *frame, int top, ao_poly atom)
+{
+	int l = 0;
+	int r = top - 1;
+	while (l <= r) {
+		int m = (l + r) >> 1;
+		if (frame->vals[m].atom < atom)
+			l = m + 1;
+		else
+			r = m - 1;
+	}
+	return l;
+}
+
 ao_poly *
 ao_lisp_frame_ref(struct ao_lisp_frame *frame, ao_poly atom)
 {
-	int f;
-	for (f = 0; f < frame->num; f++)
-		if (frame->vals[f].atom == atom)
-			return &frame->vals[f].val;
-	return NULL;
+	int l = ao_lisp_frame_find(frame, frame->num, atom);
+
+	if (l >= frame->num)
+		return NULL;
+
+	if (frame->vals[l].atom != atom)
+		return NULL;
+	return &frame->vals[l].val;
 }
 
 int
@@ -234,6 +252,18 @@ ao_lisp_frame_realloc(struct ao_lisp_frame **frame_ref, int new_num)
 	return new;
 }
 
+void
+ao_lisp_frame_bind(struct ao_lisp_frame *frame, int num, ao_poly atom, ao_poly val)
+{
+	int l = ao_lisp_frame_find(frame, num, atom);
+
+	memmove(&frame->vals[l+1],
+		&frame->vals[l],
+		(num - l) * sizeof (struct ao_lisp_val));
+	frame->vals[l].atom = atom;
+	frame->vals[l].val = val;
+}
+
 int
 ao_lisp_frame_add(struct ao_lisp_frame **frame_ref, ao_poly atom, ao_poly val)
 {
@@ -251,14 +281,13 @@ ao_lisp_frame_add(struct ao_lisp_frame **frame_ref, ao_poly atom, ao_poly val)
 			f = 0;
 			frame = ao_lisp_frame_new(1);
 		}
-		atom = ao_lisp_poly_fetch(0);
-		val = ao_lisp_poly_fetch(1);
 		if (!frame)
 			return 0;
 		*frame_ref = frame;
-		frame->vals[f].atom = atom;
-		ref = &frame->vals[f].val;
-	}
-	*ref = val;
+		atom = ao_lisp_poly_fetch(0);
+		val = ao_lisp_poly_fetch(1);
+		ao_lisp_frame_bind(frame, frame->num - 1, atom, val);
+	} else
+		*ref = val;
 	return 1;
 }
diff --git a/src/lisp/ao_lisp_lambda.c b/src/lisp/ao_lisp_lambda.c
index b164cd66..526863c5 100644
--- a/src/lisp/ao_lisp_lambda.c
+++ b/src/lisp/ao_lisp_lambda.c
@@ -166,8 +166,7 @@ ao_lisp_lambda_eval(void)
 	case AO_LISP_FUNC_LAMBDA:
 		for (f = 0; f < args_wanted; f++) {
 			DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(vals->car); DBG("\n");
-			next_frame->vals[f].atom = args->car;
-			next_frame->vals[f].val = vals->car;
+			ao_lisp_frame_bind(next_frame, f, args->car, vals->car);
 			args = ao_lisp_poly_cons(args->cdr);
 			vals = ao_lisp_poly_cons(vals->cdr);
 		}
@@ -180,14 +179,12 @@ ao_lisp_lambda_eval(void)
 	case AO_LISP_FUNC_MACRO:
 		for (f = 0; f < args_wanted - 1; f++) {
 			DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(vals->car); DBG("\n");
-			next_frame->vals[f].atom = args->car;
-			next_frame->vals[f].val = vals->car;
+			ao_lisp_frame_bind(next_frame, f, args->car, vals->car);
 			args = ao_lisp_poly_cons(args->cdr);
 			vals = ao_lisp_poly_cons(vals->cdr);
 		}
 		DBGI("bind "); DBG_POLY(args->car); DBG(" = "); DBG_POLY(ao_lisp_cons_poly(vals)); DBG("\n");
-		next_frame->vals[f].atom = args->car;
-		next_frame->vals[f].val = ao_lisp_cons_poly(vals);
+		ao_lisp_frame_bind(next_frame, f, args->car, ao_lisp_cons_poly(vals));
 		break;
 	default:
 		break;
diff --git a/src/lisp/ao_lisp_mem.c b/src/lisp/ao_lisp_mem.c
index e8907cf6..1f09ede8 100644
--- a/src/lisp/ao_lisp_mem.c
+++ b/src/lisp/ao_lisp_mem.c
@@ -218,9 +218,11 @@ static const void ** const ao_lisp_cache[] = {
 	(const void **) &ao_lisp_frame_free_list[1],
 	(const void **) &ao_lisp_frame_free_list[2],
 	(const void **) &ao_lisp_frame_free_list[3],
+	(const void **) &ao_lisp_frame_free_list[4],
+	(const void **) &ao_lisp_frame_free_list[5],
 };
 
-#if AO_LISP_FRAME_FREE != 4
+#if AO_LISP_FRAME_FREE != 6
 #error Unexpected AO_LISP_FRAME_FREE value
 #endif