[PATCH 4/4] Add a function string_list_longest_prefix()

[Michael Haggerty <mhagger@alum.mit.edu>]

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 Documentation/technical/api-string-list.txt |  8 ++++++++
 string-list.c                               | 20 +++++++++++++++++++
 string-list.h                               |  8 ++++++++
 t/t0063-string-list.sh                      | 30 +++++++++++++++++++++++++++++
 test-string-list.c                          | 22 +++++++++++++++++++++
 5 files changed, 88 insertions(+)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 9206f8f..291ac4c 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -68,6 +68,14 @@ Functions
 	to be deleted.  Preserve the order of the items that are
 	retained.
 
+`string_list_longest_prefix`::
+
+	Return the longest string within a string_list that is a
+	prefix (in the sense of prefixcmp()) of the specified string,
+	or NULL if no such prefix exists.  This function does not
+	require the string_list to be sorted (it does a linear
+	search).
+
 `print_string_list`::
 
 	Dump a string_list to stdout, useful mainly for debugging purposes. It
diff --git a/string-list.c b/string-list.c
index bfef6cf..043f6c4 100644
--- a/string-list.c
+++ b/string-list.c
@@ -136,6 +136,26 @@ void filter_string_list(struct string_list *list, int free_util,
 	list->nr = dst;
 }
 
+char *string_list_longest_prefix(const struct string_list *prefixes,
+				 const char *string)
+{
+	int i, max_len = -1;
+	char *retval = NULL;
+
+	for (i = 0; i < prefixes->nr; i++) {
+		char *prefix = prefixes->items[i].string;
+		if (!prefixcmp(string, prefix)) {
+			int len = strlen(prefix);
+			if (len > max_len) {
+				retval = prefix;
+				max_len = len;
+			}
+		}
+	}
+
+	return retval;
+}
+
 void string_list_clear(struct string_list *list, int free_util)
 {
 	if (list->items) {
diff --git a/string-list.h b/string-list.h
index c4dc659..680916c 100644
--- a/string-list.h
+++ b/string-list.h
@@ -38,6 +38,14 @@ int for_each_string_list(struct string_list *list,
 void filter_string_list(struct string_list *list, int free_util,
 			string_list_each_func_t fn, void *cb_data);
 
+/*
+ * Return the longest string in prefixes that is a prefix (in the
+ * sense of prefixcmp()) of string, or NULL if no such prefix exists.
+ * This function does not require the string_list to be sorted (it
+ * does a linear search).
+ */
+char *string_list_longest_prefix(const struct string_list *prefixes, const char *string);
+
 
 /* Use these functions only on sorted lists: */
 int string_list_has_string(const struct string_list *list, const char *string);
diff --git a/t/t0063-string-list.sh b/t/t0063-string-list.sh
index 0eede83..fa96eba 100755
--- a/t/t0063-string-list.sh
+++ b/t/t0063-string-list.sh
@@ -15,6 +15,14 @@ string_list_split_in_place() {
 	"
 }
 
+longest_prefix() {
+	test "$(test-string-list longest_prefix "$1" "$2")" = "$3"
+}
+
+no_longest_prefix() {
+	test_must_fail test-string-list longest_prefix "$1" "$2"
+}
+
 string_list_split_in_place "foo:bar:baz" ":" "-1" <<EOF
 3
 [0]: "foo"
@@ -60,4 +68,26 @@ string_list_split_in_place ":" ":" "-1" <<EOF
 [1]: ""
 EOF
 
+test_expect_success "test longest_prefix" '
+	no_longest_prefix - '' &&
+	no_longest_prefix - x &&
+	longest_prefix "" x "" &&
+	longest_prefix x x x &&
+	longest_prefix "" foo "" &&
+	longest_prefix : foo "" &&
+	longest_prefix f foo f &&
+	longest_prefix foo foobar foo &&
+	longest_prefix foo foo foo &&
+	no_longest_prefix bar foo &&
+	no_longest_prefix bar:bar foo &&
+	no_longest_prefix foobar foo &&
+	longest_prefix foo:bar foo foo &&
+	longest_prefix foo:bar bar bar &&
+	longest_prefix foo::bar foo foo &&
+	longest_prefix foo:foobar foo foo &&
+	longest_prefix foobar:foo foo foo &&
+	longest_prefix foo: bar "" &&
+	longest_prefix :foo bar ""
+'
+
 test_done
diff --git a/test-string-list.c b/test-string-list.c
index f08d3cc..c7e71f2 100644
--- a/test-string-list.c
+++ b/test-string-list.c
@@ -19,6 +19,28 @@ int main(int argc, char **argv)
 		return 0;
 	}
 
+	if (argc == 4 && !strcmp(argv[1], "longest_prefix")) {
+		/* arguments: <colon-separated-prefixes>|- <string> */
+		struct string_list prefixes = STRING_LIST_INIT_NODUP;
+		int retval;
+		char *prefix_string = xstrdup(argv[2]);
+		char *string = argv[3];
+		char *match;
+
+		if (strcmp(prefix_string, "-"))
+			string_list_split_in_place(&prefixes, prefix_string, ':', -1);
+		match = string_list_longest_prefix(&prefixes, string);
+		if (match) {
+			printf("%s\n", match);
+			retval = 0;
+		}
+		else
+			retval = 1;
+		string_list_clear(&prefixes, 0);
+		free(prefix_string);
+		return retval;
+	}
+
 	fprintf(stderr, "%s: unknown function name: %s\n", argv[0],
 		argv[1] ? argv[1] : "(there was none)");
 	return 1;
-- 
1.7.11.3