Move command line history from heap to a fixed-sized char array

2 files changed, 128 insertions, 107 deletions

diff --git a/avr/cli_readline.c b/avr/cli_readline.c
index 2fdc56e..d4c2c92 100644
--- a/avr/cli_readline.c
+++ b/avr/cli_readline.c
@@ -15,7 +15,6 @@
 #include "common.h"
 #include <string.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <stdbool.h>
 #include <ctype.h>
 
@@ -23,6 +22,13 @@
 #include "con-utils.h"
 #include "print-utils.h"
 #include "command.h"
+#include "debug.h"
+
+
+#define DEBUG_READLINE	0	/* set to 1 to debug */
+
+#define debug_readline(fmt, args...)                                           \
+	debug_cond(DEBUG_READLINE, fmt, ##args)
 
 
 
@@ -217,188 +223,190 @@ int vt_parse (void)
  */
 
 
-struct hist_node_s {
-	struct hist_node_s *next;
-	char line[];
-};
-typedef struct hist_node_s hist_node;
-
+char histbuf[CONFIG_SYS_HISTSIZE+1];
+#define HISTBUFE (histbuf+CONFIG_SYS_HISTSIZE)
 
-static hist_node *hist_head;
-static hist_node *hist_cur;
+static char *hist_head;
+static char *hist_cur;
 
 static void hist_reset(void)
 {
+	if (hist_head == NULL)
+		hist_head = HISTBUFE;
 	hist_cur = hist_head;
 }
 
-static hist_node *hist_search_node(char *line)
+static char *hist_entry_next(char *p)
 {
-	hist_node *p = hist_head;
+	if (*p)
+		while (*p++);
 
-	while (p && strcmp(p->line, line))
-		p = p->next;
 	return p;
 }
 
-#if 0
-static hist_node *hist_insert(char *line)
+static char *hist_entry_prev(char *p)
 {
-	hist_node *p = (hist_node *) malloc(sizeof (hist_node) + strlen(line) + 1);
+	if (p == hist_head)
+		return NULL;
+
+	--p;
+	while (p != hist_head && *(p-1) != 0)
+		--p;
 
-	if (p) {
-		strcpy(p->line, line);
-		p->next = hist_head;
-		hist_head = p;
-	}
 	return p;
 }
-#endif
 
-static hist_node *hist_new(char *line)
+static char *hist_search_entry(char *line)
 {
-	hist_node *p = (hist_node *) malloc(sizeof (hist_node) + strlen(line) + 1);
+	char *p = hist_head;
 
-	if (p) {
-		strcpy(p->line, line);
-		p->next = NULL;
-	}
-	return p;
+	while (*p && strcmp(p, line))
+		p = hist_entry_next(p);
+	return *p ? p : NULL;
 }
 
-static hist_node *hist_delete(void)
+static char *hist_delete(size_t amount)
 {
-	hist_node *p = NULL;
-	hist_node *q = hist_head;
+	char *p;
 
-	if (q) {
-		while(q->next) {
-			p = q;
-			q = q->next;
-		}
-		free(q);
-		if (p)
-			p->next = NULL;
+	p = HISTBUFE - amount;
+	if (p < hist_head)
+		p = hist_head;
+
+	while (p > hist_head && *(p-1))
+		--p;
+
+	if (p == hist_head)
+		hist_head = HISTBUFE;
+	else {
+		size_t shift = HISTBUFE - p;
+		size_t len = p - hist_head;
+		hist_head = memmove(hist_head + shift, hist_head, len);
 	}
-	return p;
+	return hist_head;
 }
 
-static hist_node *hist_unlink(hist_node *pos)
+static char *hist_delete_entry(char *entry)
 {
-	hist_node *p = NULL;
-	hist_node *q = hist_head;
+	size_t shift = strlen(entry) + 1;
+	size_t len = entry - hist_head;
 
-	while(q && q != pos) {
-		p = q;
-		q = q->next;
-	}
-	if (q) {
-		if (p)
-			p->next = q->next;
-		else
-			hist_head = q->next;
-		q->next = NULL;
-	}
-	return q;
+	hist_head = memmove(hist_head + shift, hist_head, len);
+
+	return hist_head;
 }
 
-static uint_fast8_t hist_count(void)
+
+static char *hist_add_entry(char *line)
 {
-	hist_node *p = hist_head;
+	char *p = hist_head;
+
+	if (p == NULL)
+		p = HISTBUFE;
+
+	char *q = p - strlen(line) - 1;
+	if (q < histbuf)
+		q = histbuf;
+
+	strlcpy(q, line, p - q);
+
+	hist_head = q;
+
+	return hist_head;
+}
+
+static uint_fast8_t hist_get_count(void)
+{
+	char *p = hist_head;
 	uint_fast8_t n = 0;
 
-	while (p) {
+	while (*p) {
 		++n;
-		p = p->next;
+		while (*p++);
 	}
 	return n;
 }
 
-static hist_node *cread_add_to_hist(char *line)
+static int hist_get_size(void)
 {
-	hist_node * p;
+	return HISTBUFE - hist_head;
+}
 
-	p = hist_search_node(line);
-	if (p)
-		hist_unlink(p);
-	else
-		p = hist_new(line);
+static char *cread_add_to_hist(char *line)
+{
+	char *p;
 
-	if (p) {
-		p->next = hist_head;
-		hist_head = p;
+	p = hist_search_entry(line);
+	if (p)
+		hist_delete_entry(p);
+	else {
+		size_t free = hist_head - histbuf;
+		if (free < strlen(line) + 1)
+			hist_delete(strlen(line) + 1 - free);
 	}
+	hist_add_entry(line);
 
-	if (hist_count() > CONFIG_SYS_HIST_MAX)
-		hist_delete();
 	return p;
 }
 
 static char *hist_prev(void)
 {
-	hist_node *p = hist_cur;
+	char *p = hist_cur;
 
-	if (p == NULL)
+	if (*p == '\0')
 		return NULL;
-	hist_cur = p->next;
+	hist_cur = hist_entry_next(p);
 
-	return  p->line;
+	return  p;
 }
 
 static char *hist_next(void)
 {
-	hist_node *p = NULL;
-	hist_node *q = hist_head;
+	char *p = hist_cur;
 
-	if(q == hist_cur)
+	if(p == hist_head)
 		return NULL;
 
-	while(q->next != hist_cur) {
-		p = q;
-		q = q->next;
-	}
-	hist_cur = q;
+	p = hist_entry_prev(p);
+	hist_cur = p;
 
-	return p ? p->line : "";
+	return p == hist_head ? "" : hist_entry_prev(p);
 }
 
 static char *hist_search_backward(char* buf, uint8_t num)
 {
-	hist_node *p = hist_cur;
+	char *p = hist_cur;
 
-	if (p == NULL)
+	if (*p == '\0')
 		return NULL;
 
-	while (p->next && strncmp(p->line, buf, num))
-		p = p->next;
+	while (*p  && strncmp(p, buf, num))
+		p = hist_entry_next(p);
 
-	if(!strncmp(p->line, buf, num)) {
-		hist_cur = p->next;
-		return  p->line;
+	if(!strncmp(p, buf, num)) {
+		hist_cur = hist_entry_next(p);
+		return  p;
 	}
+
 	return NULL;
 }
 
 static char *hist_search_forward (char* buf, uint8_t num)
 {
-	hist_node *p = NULL;
-	hist_node *match = NULL;
-	hist_node *q = hist_head;
+	char *p = hist_cur;
 
-	if(q == hist_cur)
-		return NULL;
+	if(p != hist_head && (p = hist_entry_prev(p)) != NULL) {
+		do {
+			p = hist_entry_prev(p);
+		} while (p && strncmp(p, buf, num) != 0);
 
-	while(q->next != hist_cur) {
-		p = q;
-		q = q->next;
-		if (p && !strncmp(p->line, buf, num))
-			match = p;
+		//if(!strncmp(p, buf, num)) {
+		if(p) {
+			hist_cur = hist_entry_next(p);
+			return p;
+		}
 	}
 
-	if(match) {
-		hist_cur = match->next;
-		return  match->line;
-	}
 	return NULL;
 }
 
@@ -659,8 +667,20 @@ static int cread_line(const FLASH char *const prompt, char *buf,
 		--eol_num;			/* remove trailing blanks */
 	buf[eol_num] = '\0';	/* lose the newline */
 
-	if (enable_history && buf[0])
+	uint_fast8_t i = 0;
+	while (buf[i] == ' ')
+		++i;				/* remove leading blanks */
+	if (i) {
+		eol_num -= i;
+		memmove(buf, buf+i, eol_num+1);
+	}
+
+	debug_readline("### hist_head: %p, hist_cur: %p\n",	hist_head, hist_cur);
+	if (enable_history && buf[0]) {
 		cread_add_to_hist(buf);
+		debug_readline("### hist_head: %p, hist_cur: %p, hist_size: %3d, hist_count: %2d\n",
+				hist_head, hist_cur, hist_get_size(), hist_get_count());
+	}
 	return eol_num;
 }
 
diff --git a/include/config.h b/include/config.h
index b56b316..630e175 100644
--- a/include/config.h
+++ b/include/config.h
@@ -64,6 +64,7 @@
 #define CONFIG_SYS_HIST_MAX	20
 #define CONFIG_SYS_MAXARGS	20
 #define CONFIG_SYS_ENV_NAMELEN	16
+#define CONFIG_SYS_HISTSIZE			(CONFIG_SYS_CBSIZE*2)
 
 #define CONFIG_SYS_PROMPT			"-> "
 #define CONFIG_SYS_PROMPT_REPEAT	"=> "