vtysh: Replace linked-list in vtysh_config with RB-tree

...for faster look-ups

Fixes: 4673
Signed-off-by: Juergen Werner <juergen@opensourcerouting.org>

1 files changed, 21 insertions, 17 deletions

diff --git a/vtysh/vtysh_config.c b/vtysh/vtysh_config.c
index 1e45e6f97..c8ecb12fe 100644
--- a/vtysh/vtysh_config.c
+++ b/vtysh/vtysh_config.c
@@ -23,6 +23,7 @@
 #include "command.h"
 #include "linklist.h"
 #include "memory.h"
+#include "typesafe.h"
 
 #include "vtysh/vtysh.h"
 #include "vtysh/vtysh_user.h"
@@ -33,6 +34,8 @@ DEFINE_MTYPE_STATIC(MVTYSH, VTYSH_CONFIG_LINE, "Vtysh configuration line")
 
 vector configvec;
 
+PREDECL_RBTREE_UNIQ(config_master);
+
 struct config {
 	/* Configuration node name. */
 	char *name;
@@ -45,6 +48,9 @@ struct config {
 
 	/* Index of this config. */
 	uint32_t index;
+
+	/* Node entry for the typed Red-black tree */
+	struct config_master_item rbt_item;
 };
 
 struct list *config_top;
@@ -66,7 +72,7 @@ static struct config *config_new(void)
 	return config;
 }
 
-static int config_cmp(struct config *c1, struct config *c2)
+static int config_cmp(const struct config *c1, const struct config *c2)
 {
 	return strcmp(c1->name, c2->name);
 }
@@ -78,28 +84,23 @@ static void config_del(struct config *config)
 	XFREE(MTYPE_VTYSH_CONFIG, config);
 }
 
+DECLARE_RBTREE_UNIQ(config_master, struct config, rbt_item, config_cmp)
+
 static struct config *config_get(int index, const char *line)
 {
 	struct config *config;
-	struct config *config_loop;
-	struct list *master;
-	struct listnode *node, *nnode;
-
-	config = config_loop = NULL;
+	struct config_master_head *master;
 
 	master = vector_lookup_ensure(configvec, index);
 
 	if (!master) {
-		master = list_new();
-		master->del = (void (*)(void *))config_del;
-		master->cmp = (int (*)(void *, void *))config_cmp;
+		master = XMALLOC(MTYPE_VTYSH_CONFIG, sizeof(struct config_master_head));
+		config_master_init(master);
 		vector_set_index(configvec, index, master);
 	}
 
-	for (ALL_LIST_ELEMENTS(master, node, nnode, config_loop)) {
-		if (strcmp(config_loop->name, line) == 0)
-			config = config_loop;
-	}
+	const struct config config_ref = { .name = (char *)line };
+	config = config_master_find(master, &config_ref);
 
 	if (!config) {
 		config = config_new();
@@ -108,7 +109,7 @@ static struct config *config_get(int index, const char *line)
 		config->line->cmp = (int (*)(void *, void *))line_cmp;
 		config->name = XSTRDUP(MTYPE_VTYSH_CONFIG_LINE, line);
 		config->index = index;
-		listnode_add(master, config);
+		config_master_add(master, config);
 	}
 	return config;
 }
@@ -435,7 +436,7 @@ void vtysh_config_dump(void)
 	struct listnode *node, *nnode;
 	struct listnode *mnode, *mnnode;
 	struct config *config;
-	struct list *master;
+	struct config_master_head *master;
 	char *line;
 	unsigned int i;
 
@@ -446,7 +447,7 @@ void vtysh_config_dump(void)
 
 	for (i = 0; i < vector_active(configvec); i++)
 		if ((master = vector_slot(configvec, i)) != NULL) {
-			for (ALL_LIST_ELEMENTS(master, node, nnode, config)) {
+			while ((config = config_master_pop(master))) {
 				/* Don't print empty sections for interface.
 				 * Route maps on the
 				 * other hand could have a legitimate empty
@@ -466,6 +467,8 @@ void vtysh_config_dump(void)
 					vty_out(vty, "%s\n", line);
 				if (!NO_DELIMITER(i))
 					vty_out(vty, "!\n");
+
+				config_del(config);
 			}
 			if (NO_DELIMITER(i))
 				vty_out(vty, "!\n");
@@ -473,7 +476,8 @@ void vtysh_config_dump(void)
 
 	for (i = 0; i < vector_active(configvec); i++)
 		if ((master = vector_slot(configvec, i)) != NULL) {
-			list_delete(&master);
+			config_master_fini(master);
+			XFREE(MTYPE_VTYSH_CONFIG, master);
 			vector_slot(configvec, i) = NULL;
 		}
 	list_delete_all_node(config_top);