[quagga-dev 8033] [PATCH] vty: Optimize longest common subsequence search

Masashi Honma honma at ictec.co.jp
Tue Jun 15 06:23:21 BST 2010


Hello.

This patch little bit optimizes command completion. Currently the
cmd_lcd() checks all the character in the string every time. But the
cmd_lcd() should not check more than current common length.


diff --git a/lib/command.c b/lib/command.c
index 478125f..cc16620 100644
--- a/lib/command.c
+++ b/lib/command.c
@@ -1757,29 +1757,19 @@ cmd_lcd (char **matched)
 {
   int i;
   int j;
-  int lcd = -1;
-  char *s1, *s2;
-  char c1, c2;
+  int lcd;
 
   if (matched[0] == NULL || matched[1] == NULL)
     return 0;
 
+  lcd = strlen(matched[0]);
   for (i = 1; matched[i] != NULL; i++)
     {
-      s1 = matched[i - 1];
-      s2 = matched[i];
-
-      for (j = 0; (c1 = s1[j]) && (c2 = s2[j]); j++)
-	if (c1 != c2)
+      for (j = 0; j < lcd; j++)
+	if (matched[i - 1][j] != matched[i][j])
 	  break;
-
-      if (lcd < 0)
+      if (lcd > j)
 	lcd = j;
-      else
-	{
-	  if (lcd > j)
-	    lcd = j;
-	}
     }
   return lcd;
 }


And the following code is my test code. I have checked cnt_error == 0
on ubuntu 9.10-server.

int main(void)
{
	char **matched;
	int cnt_error = 0;

	matched = malloc(sizeof(char *) * 10);

	matched[0] = NULL;
	matched[1] = NULL;
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "abc";
	matched[1] = NULL;
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = NULL;
	matched[0] = "abc";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "";
	matched[1] = "";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "";
	matched[1] = "a";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "a";
	matched[1] = "";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "a";
	matched[1] = "a";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "ab";
	matched[1] = "a";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "a";
	matched[1] = "ab";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "a";
	matched[1] = "ab";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "a";
	matched[1] = "ab";
	matched[2] = "abc";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "abc";
	matched[1] = "ab";
	matched[2] = "a";
	if (cmd_lcd(matched) != 1)
		cnt_error++;

	matched[0] = "ab";
	matched[1] = "a";
	matched[2] = "";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	matched[0] = "";
	matched[1] = "a";
	matched[2] = "ab";
	if (cmd_lcd(matched) != 0)
		cnt_error++;

	free(matched);
	printf("cnt_error=%d\n", cnt_error);
	return 0;
}


Regards,
Masashi Honma.



More information about the Quagga-dev mailing list