Linked list for history buffer

1 files changed, 113 insertions, 47 deletions

diff --git a/avr/cli_readline.c b/avr/cli_readline.c
index 32c15c8..e34f0c8 100644
--- a/avr/cli_readline.c
+++ b/avr/cli_readline.c
@@ -213,79 +213,146 @@ static void putnstr(char *str, int n)
 #define getcmd_getch()		vt_parse()
 #define getcmd_cbeep()		getcmd_putch('\a')
 
-#define HIST_MAX			20
 
-static int_fast8_t hist_max;
-static int_fast8_t hist_add_idx;
-static int_fast8_t hist_cur = -1;
+struct hist_node_s {
+	struct hist_node_s *next;
+	char line[];
+};
+typedef struct hist_node_s hist_node;
+
 
-static char *hist_list[HIST_MAX];
+static hist_node *hist_head;
+static hist_node *hist_cur;
 
-static void cread_add_to_hist(char *line)
+static hist_node *hist_search_node(char *line)
 {
-	if (hist_max) {
-		int_fast8_t last = hist_add_idx;
-		if (--last < 0)
-			last = hist_max;
+	hist_node *p = hist_head;
 
-		if (!strcmp(line, hist_list[last]))
-			return;
+	while (p && strcmp(p->line, line))
+		p = p->next;
+	return p;
+}
+
+#if 0
+static hist_node *hist_insert(char *line)
+{
+	hist_node *p = (hist_node *) malloc(sizeof (hist_node) + strlen(line) + 1);
+
+	if (p) {
+		strcpy(p->line, line);
+		p->next = hist_head;
+		hist_head = p;
 	}
+	return p;
+}
+#endif
+
+static hist_node *hist_new(char *line)
+{
+	hist_node *p = (hist_node *) malloc(sizeof (hist_node) + strlen(line) + 1);
 
-	char *p = strdup(line);
 	if (p) {
-		free(hist_list[hist_add_idx]);
-		hist_list[hist_add_idx] = p;
+		strcpy(p->line, line);
+		p->next = NULL;
+	}
+	return p;
+}
 
-		if (++hist_add_idx >= HIST_MAX)
-			hist_add_idx = 0;
+static hist_node *hist_delete(void)
+{
+	hist_node *p = NULL;
+	hist_node *q = hist_head;
 
-		if (hist_add_idx > hist_max)
-			hist_max = hist_add_idx;
+	if (q) {
+		while(q->next) {
+			p = q;
+			q = q->next;
+		}
+		free(q);
+		if (p)
+			p->next = NULL;
 	}
+	return p;
 }
 
-static char *hist_prev(void)
+static hist_node *hist_unlink(hist_node *pos)
 {
-	char *ret;
-	int_fast8_t old_cur;
+	hist_node *p = NULL;
+	hist_node *q = hist_head;
 
-	if (hist_cur < 0)
-		return NULL;
+	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;
+}
 
-	old_cur = hist_cur;
-	if (--hist_cur < 0)
-		hist_cur = hist_max;
+static uint_fast8_t hist_count(void)
+{
+	hist_node *p = hist_head;
+	uint_fast8_t n = 0;
 
-	if (hist_cur == hist_add_idx) {
-		hist_cur = old_cur;
-		ret = NULL;
-	} else {
-		ret = hist_list[hist_cur];
+	while (p) {
+		++n;
+		p = p->next;
 	}
+	return n;
+}
 
-	return ret;
+static hist_node *cread_add_to_hist(char *line)
+{
+	hist_node * p;
+
+	p = hist_search_node(line);
+	if (p)
+		hist_unlink(p);
+	else
+		p = hist_new(line);
+
+	if (p) {
+		p->next = hist_head;
+		hist_head = p;
+	}
+
+	if (hist_count() > CONFIG_SYS_HIST_MAX)
+		hist_delete();
+	return p;
 }
 
-static char *hist_next(void)
+static char *hist_prev(void)
 {
-	char *ret;
+	hist_node *p = hist_cur;
 
-	if (hist_cur < 0)
+	if (p == NULL)
 		return NULL;
 
-	if (hist_cur == hist_add_idx)
-		return NULL;
+	hist_cur = hist_cur->next;
 
-	if (++hist_cur > hist_max)
-		hist_cur = 0;
+	return  p->line;
+}
 
-	if (hist_cur == hist_add_idx)
-		ret = "";
-	else
-		ret = hist_list[hist_cur];
+static char *hist_next(void)
+{
+	hist_node *p = NULL;
+	hist_node *q = hist_head;
+
+	if(q == hist_cur)
+		return NULL;
+
+	while(q->next != hist_cur) {
+		p = q;
+		q = q->next;
+	}
+	hist_cur = q;
 
-	return ret;
+	return p ? p->line : "";
 }
 
 
@@ -516,8 +583,7 @@ static int cread_line(const FLASH char *const prompt, char *buf,
 
 	if (enable_history) {
 		if (buf[0])
-			cread_add_to_hist(buf);
-		hist_cur = hist_add_idx;
+		hist_cur = cread_add_to_hist(buf);
 	}
 	return 0;
 }