From e448fed8e6ba9cd9237b7c8045c11cc40afc8595 Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:42 +0200
Subject: string_list: add function string_list_append_nodup()

Add a new function that appends a string to a string_list without
copying it.  This can be used to pass ownership of an already-copied
string to a string_list that has strdup_strings set.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/technical/api-string-list.txt | 17 ++++++++++++++---
 string-list.c                               | 20 +++++++++++++++-----
 string-list.h                               | 18 ++++++++++++++++++
 3 files changed, 47 insertions(+), 8 deletions(-)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 5a0c14fce..113f8410e 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -20,8 +20,8 @@ If you need something advanced, you can manually malloc() the `items`
 member (you need this if you add things later) and you should set the
 `nr` and `alloc` members in that case, too.
 
-. Adds new items to the list, using `string_list_append` or
-  `string_list_insert`.
+. Adds new items to the list, using `string_list_append`,
+  `string_list_append_nodup`, or `string_list_insert`.
 
 . Can check if a string is in the list using `string_list_has_string` or
   `unsorted_string_list_has_string` and get it from the list using
@@ -100,7 +100,18 @@ write `string_list_insert(...)->util = ...;`.
 
 `string_list_append`::
 
-	Append a new string to the end of the string_list.
+	Append a new string to the end of the string_list.  If
+	`strdup_string` is set, then the string argument is copied;
+	otherwise the new `string_list_entry` refers to the input
+	string.
+
+`string_list_append_nodup`::
+
+	Append a new string to the end of the string_list.  The new
+	`string_list_entry` always refers to the input string, even if
+	`strdup_string` is set.  This function can be used to hand
+	ownership of a malloc()ed string to a `string_list` that has
+	`strdup_string` set.
 
 `sort_string_list`::
 
diff --git a/string-list.c b/string-list.c
index d9810aba4..ad2aa5af9 100644
--- a/string-list.c
+++ b/string-list.c
@@ -148,13 +148,23 @@ void print_string_list(const struct string_list *p, const char *text)
 		printf("%s:%p\n", p->items[i].string, p->items[i].util);
 }
 
-struct string_list_item *string_list_append(struct string_list *list, const char *string)
+struct string_list_item *string_list_append_nodup(struct string_list *list,
+						  char *string)
 {
+	struct string_list_item *retval;
 	ALLOC_GROW(list->items, list->nr + 1, list->alloc);
-	list->items[list->nr].string =
-		list->strdup_strings ? xstrdup(string) : (char *)string;
-	list->items[list->nr].util = NULL;
-	return list->items + list->nr++;
+	retval = &list->items[list->nr++];
+	retval->string = string;
+	retval->util = NULL;
+	return retval;
+}
+
+struct string_list_item *string_list_append(struct string_list *list,
+					    const char *string)
+{
+	return string_list_append_nodup(
+			list,
+			list->strdup_strings ? xstrdup(string) : (char *)string);
 }
 
 static int cmp_items(const void *a, const void *b)
diff --git a/string-list.h b/string-list.h
index 0684cb73b..1b3915b74 100644
--- a/string-list.h
+++ b/string-list.h
@@ -29,6 +29,7 @@ int for_each_string_list(struct string_list *list,
 #define for_each_string_list_item(item,list) \
 	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
 
+
 /* Use these functions only on sorted lists: */
 int string_list_has_string(const struct string_list *list, const char *string);
 int string_list_find_insert_index(const struct string_list *list, const char *string,
@@ -38,11 +39,28 @@ struct string_list_item *string_list_insert_at_index(struct string_list *list,
 						     int insert_at, const char *string);
 struct string_list_item *string_list_lookup(struct string_list *list, const char *string);
 
+
 /* Use these functions only on unsorted lists: */
+
+/*
+ * Add string to the end of list.  If list->strdup_string is set, then
+ * string is copied; otherwise the new string_list_entry refers to the
+ * input string.
+ */
 struct string_list_item *string_list_append(struct string_list *list, const char *string);
+
+/*
+ * Like string_list_append(), except string is never copied.  When
+ * list->strdup_strings is set, this function can be used to hand
+ * ownership of a malloc()ed string to list without making an extra
+ * copy.
+ */
+struct string_list_item *string_list_append_nodup(struct string_list *list, char *string);
+
 void sort_string_list(struct string_list *list);
 int unsorted_string_list_has_string(struct string_list *list, const char *string);
 struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
 						     const char *string);
+
 void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util);
 #endif /* STRING_LIST_H */
-- 
cgit v1.2.1


From ff919f965d20d003e3882c70de667f41a86349ac Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:43 +0200
Subject: string_list: add two new functions for splitting strings

Add two new functions, string_list_split() and
string_list_split_in_place().  These split a string into a string_list
on a separator character.  The first makes copies of the substrings
(leaving the input string untouched) and the second splits the
original string in place, overwriting the separator characters with
NULs and referring to the original string's memory.

These functions are similar to the strbuf_split_*() functions except
that they work with the more powerful string_list interface.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 .gitignore                                  |  1 +
 Documentation/technical/api-string-list.txt | 22 +++++++++-
 Makefile                                    |  1 +
 string-list.c                               | 53 ++++++++++++++++++++++++
 string-list.h                               | 29 +++++++++++++
 t/t0063-string-list.sh                      | 63 +++++++++++++++++++++++++++++
 test-string-list.c                          | 45 +++++++++++++++++++++
 7 files changed, 213 insertions(+), 1 deletion(-)
 create mode 100755 t/t0063-string-list.sh
 create mode 100644 test-string-list.c

diff --git a/.gitignore b/.gitignore
index bb5c91e71..0ca7df8e0 100644
--- a/.gitignore
+++ b/.gitignore
@@ -193,6 +193,7 @@
 /test-run-command
 /test-sha1
 /test-sigchain
+/test-string-list
 /test-subprocess
 /test-svn-fe
 /common-cmds.h
diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 113f8410e..1dcad47f7 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -21,7 +21,8 @@ member (you need this if you add things later) and you should set the
 `nr` and `alloc` members in that case, too.
 
 . Adds new items to the list, using `string_list_append`,
-  `string_list_append_nodup`, or `string_list_insert`.
+  `string_list_append_nodup`, `string_list_insert`,
+  `string_list_split`, and/or `string_list_split_in_place`.
 
 . Can check if a string is in the list using `string_list_has_string` or
   `unsorted_string_list_has_string` and get it from the list using
@@ -135,6 +136,25 @@ counterpart for sorted lists, which performs a binary search.
 	is set. The third parameter controls if the `util` pointer of the
 	items should be freed or not.
 
+`string_list_split`::
+`string_list_split_in_place`::
+
+	Split a string into substrings on a delimiter character and
+	append the substrings to a `string_list`.  If `maxsplit` is
+	non-negative, then split at most `maxsplit` times.  Return the
+	number of substrings appended to the list.
++
+`string_list_split` requires a `string_list` that has `strdup_strings`
+set to true; it leaves the input string untouched and makes copies of
+the substrings in newly-allocated memory.
+`string_list_split_in_place` requires a `string_list` that has
+`strdup_strings` set to false; it splits the input string in place,
+overwriting the delimiter characters with NULs and creating new
+string_list_items that point into the original string (the original
+string must therefore not be modified or freed while the `string_list`
+is in use).
+
+
 Data structures
 ---------------
 
diff --git a/Makefile b/Makefile
index 66e82167e..ebbb381c1 100644
--- a/Makefile
+++ b/Makefile
@@ -501,6 +501,7 @@ TEST_PROGRAMS_NEED_X += test-run-command
 TEST_PROGRAMS_NEED_X += test-scrap-cache-tree
 TEST_PROGRAMS_NEED_X += test-sha1
 TEST_PROGRAMS_NEED_X += test-sigchain
+TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-subprocess
 TEST_PROGRAMS_NEED_X += test-svn-fe
 
diff --git a/string-list.c b/string-list.c
index ad2aa5af9..acb1f5b6d 100644
--- a/string-list.c
+++ b/string-list.c
@@ -204,3 +204,56 @@ void unsorted_string_list_delete_item(struct string_list *list, int i, int free_
 	list->items[i] = list->items[list->nr-1];
 	list->nr--;
 }
+
+int string_list_split(struct string_list *list, const char *string,
+		      int delim, int maxsplit)
+{
+	int count = 0;
+	const char *p = string, *end;
+
+	if (!list->strdup_strings)
+		die("internal error in string_list_split(): "
+		    "list->strdup_strings must be set");
+	for (;;) {
+		count++;
+		if (maxsplit >= 0 && count > maxsplit) {
+			string_list_append(list, p);
+			return count;
+		}
+		end = strchr(p, delim);
+		if (end) {
+			string_list_append_nodup(list, xmemdupz(p, end - p));
+			p = end + 1;
+		} else {
+			string_list_append(list, p);
+			return count;
+		}
+	}
+}
+
+int string_list_split_in_place(struct string_list *list, char *string,
+			       int delim, int maxsplit)
+{
+	int count = 0;
+	char *p = string, *end;
+
+	if (list->strdup_strings)
+		die("internal error in string_list_split_in_place(): "
+		    "list->strdup_strings must not be set");
+	for (;;) {
+		count++;
+		if (maxsplit >= 0 && count > maxsplit) {
+			string_list_append(list, p);
+			return count;
+		}
+		end = strchr(p, delim);
+		if (end) {
+			*end = '\0';
+			string_list_append(list, p);
+			p = end + 1;
+		} else {
+			string_list_append(list, p);
+			return count;
+		}
+	}
+}
diff --git a/string-list.h b/string-list.h
index 1b3915b74..dc5fbc80a 100644
--- a/string-list.h
+++ b/string-list.h
@@ -63,4 +63,33 @@ struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
 						     const char *string);
 
 void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util);
+
+/*
+ * Split string into substrings on character delim and append the
+ * substrings to list.  The input string is not modified.
+ * list->strdup_strings must be set, as new memory needs to be
+ * allocated to hold the substrings.  If maxsplit is non-negative,
+ * then split at most maxsplit times.  Return the number of substrings
+ * appended to list.
+ *
+ * Examples:
+ *   string_list_split(l, "foo:bar:baz", ':', -1) -> ["foo", "bar", "baz"]
+ *   string_list_split(l, "foo:bar:baz", ':', 0) -> ["foo:bar:baz"]
+ *   string_list_split(l, "foo:bar:baz", ':', 1) -> ["foo", "bar:baz"]
+ *   string_list_split(l, "foo:bar:", ':', -1) -> ["foo", "bar", ""]
+ *   string_list_split(l, "", ':', -1) -> [""]
+ *   string_list_split(l, ":", ':', -1) -> ["", ""]
+ */
+int string_list_split(struct string_list *list, const char *string,
+		      int delim, int maxsplit);
+
+/*
+ * Like string_list_split(), except that string is split in-place: the
+ * delimiter characters in string are overwritten with NULs, and the
+ * new string_list_items point into string (which therefore must not
+ * be modified or freed while the string_list is in use).
+ * list->strdup_strings must *not* be set.
+ */
+int string_list_split_in_place(struct string_list *list, char *string,
+			       int delim, int maxsplit);
 #endif /* STRING_LIST_H */
diff --git a/t/t0063-string-list.sh b/t/t0063-string-list.sh
new file mode 100755
index 000000000..fb8543075
--- /dev/null
+++ b/t/t0063-string-list.sh
@@ -0,0 +1,63 @@
+#!/bin/sh
+#
+# Copyright (c) 2012 Michael Haggerty
+#
+
+test_description='Test string list functionality'
+
+. ./test-lib.sh
+
+test_split () {
+	cat >expected &&
+	test_expect_success "split $1 at $2, max $3" "
+		test-string-list split '$1' '$2' '$3' >actual &&
+		test_cmp expected actual &&
+		test-string-list split_in_place '$1' '$2' '$3' >actual &&
+		test_cmp expected actual
+	"
+}
+
+test_split "foo:bar:baz" ":" "-1" <<EOF
+3
+[0]: "foo"
+[1]: "bar"
+[2]: "baz"
+EOF
+
+test_split "foo:bar:baz" ":" "0" <<EOF
+1
+[0]: "foo:bar:baz"
+EOF
+
+test_split "foo:bar:baz" ":" "1" <<EOF
+2
+[0]: "foo"
+[1]: "bar:baz"
+EOF
+
+test_split "foo:bar:baz" ":" "2" <<EOF
+3
+[0]: "foo"
+[1]: "bar"
+[2]: "baz"
+EOF
+
+test_split "foo:bar:" ":" "-1" <<EOF
+3
+[0]: "foo"
+[1]: "bar"
+[2]: ""
+EOF
+
+test_split "" ":" "-1" <<EOF
+1
+[0]: ""
+EOF
+
+test_split ":" ":" "-1" <<EOF
+2
+[0]: ""
+[1]: ""
+EOF
+
+test_done
diff --git a/test-string-list.c b/test-string-list.c
new file mode 100644
index 000000000..cdc3cf3a7
--- /dev/null
+++ b/test-string-list.c
@@ -0,0 +1,45 @@
+#include "cache.h"
+#include "string-list.h"
+
+void write_list(const struct string_list *list)
+{
+	int i;
+	for (i = 0; i < list->nr; i++)
+		printf("[%d]: \"%s\"\n", i, list->items[i].string);
+}
+
+int main(int argc, char **argv)
+{
+	if (argc == 5 && !strcmp(argv[1], "split")) {
+		struct string_list list = STRING_LIST_INIT_DUP;
+		int i;
+		const char *s = argv[2];
+		int delim = *argv[3];
+		int maxsplit = atoi(argv[4]);
+
+		i = string_list_split(&list, s, delim, maxsplit);
+		printf("%d\n", i);
+		write_list(&list);
+		string_list_clear(&list, 0);
+		return 0;
+	}
+
+	if (argc == 5 && !strcmp(argv[1], "split_in_place")) {
+		struct string_list list = STRING_LIST_INIT_NODUP;
+		int i;
+		char *s = xstrdup(argv[2]);
+		int delim = *argv[3];
+		int maxsplit = atoi(argv[4]);
+
+		i = string_list_split_in_place(&list, s, delim, maxsplit);
+		printf("%d\n", i);
+		write_list(&list);
+		string_list_clear(&list, 0);
+		free(s);
+		return 0;
+	}
+
+	fprintf(stderr, "%s: unknown function name: %s\n", argv[0],
+		argv[1] ? argv[1] : "(there was none)");
+	return 1;
+}
-- 
cgit v1.2.1


From eb5f0c7a616531a024a582b72ca6d8775ff98d46 Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:44 +0200
Subject: string_list: add a new function, filter_string_list()

This function allows entries that don't match a specified criterion to
be discarded from a string_list while preserving the order of the
remaining entries.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/technical/api-string-list.txt | 11 +++++++
 string-list.c                               | 17 ++++++++++
 string-list.h                               |  9 ++++++
 t/t0063-string-list.sh                      | 11 +++++++
 test-string-list.c                          | 48 +++++++++++++++++++++++++++++
 5 files changed, 96 insertions(+)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 1dcad47f7..300b30109 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -33,6 +33,9 @@ member (you need this if you add things later) and you should set the
 . Can remove individual items of an unsorted list using
   `unsorted_string_list_delete_item`.
 
+. Can remove items not matching a criterion from a sorted or unsorted
+  list using `filter_string_list`.
+
 . Finally it should free the list using `string_list_clear`.
 
 Example:
@@ -61,6 +64,14 @@ Functions
 
 * General ones (works with sorted and unsorted lists as well)
 
+`filter_string_list`::
+
+	Apply a function to each item in a list, retaining only the
+	items for which the function returns true.  If free_util is
+	true, call free() on the util members of any items that have
+	to be deleted.  Preserve the order of the items that are
+	retained.
+
 `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 acb1f5b6d..179fde421 100644
--- a/string-list.c
+++ b/string-list.c
@@ -102,6 +102,23 @@ int for_each_string_list(struct string_list *list,
 	return ret;
 }
 
+void filter_string_list(struct string_list *list, int free_util,
+			string_list_each_func_t want, void *cb_data)
+{
+	int src, dst = 0;
+	for (src = 0; src < list->nr; src++) {
+		if (want(&list->items[src], cb_data)) {
+			list->items[dst++] = list->items[src];
+		} else {
+			if (list->strdup_strings)
+				free(list->items[src].string);
+			if (free_util)
+				free(list->items[src].util);
+		}
+	}
+	list->nr = dst;
+}
+
 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 dc5fbc80a..7d18e622e 100644
--- a/string-list.h
+++ b/string-list.h
@@ -29,6 +29,15 @@ int for_each_string_list(struct string_list *list,
 #define for_each_string_list_item(item,list) \
 	for (item = (list)->items; item < (list)->items + (list)->nr; ++item)
 
+/*
+ * Apply want to each item in list, retaining only the ones for which
+ * the function returns true.  If free_util is true, call free() on
+ * the util members of any items that have to be deleted.  Preserve
+ * the order of the items that are retained.
+ */
+void filter_string_list(struct string_list *list, int free_util,
+			string_list_each_func_t want, void *cb_data);
+
 
 /* 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 fb8543075..a5f05cd20 100755
--- a/t/t0063-string-list.sh
+++ b/t/t0063-string-list.sh
@@ -60,4 +60,15 @@ test_split ":" ":" "-1" <<EOF
 [1]: ""
 EOF
 
+test_expect_success "test filter_string_list" '
+	test "x-" = "x$(test-string-list filter - y)" &&
+	test "x-" = "x$(test-string-list filter no y)" &&
+	test yes = "$(test-string-list filter yes y)" &&
+	test yes = "$(test-string-list filter no:yes y)" &&
+	test yes = "$(test-string-list filter yes:no y)" &&
+	test y1:y2 = "$(test-string-list filter y1:y2 y)" &&
+	test y2:y1 = "$(test-string-list filter y2:y1 y)" &&
+	test "x-" = "x$(test-string-list filter x1:x2 y)"
+'
+
 test_done
diff --git a/test-string-list.c b/test-string-list.c
index cdc3cf3a7..702276c1f 100644
--- a/test-string-list.c
+++ b/test-string-list.c
@@ -1,6 +1,20 @@
 #include "cache.h"
 #include "string-list.h"
 
+/*
+ * Parse an argument into a string list.  arg should either be a
+ * ':'-separated list of strings, or "-" to indicate an empty string
+ * list (as opposed to "", which indicates a string list containing a
+ * single empty string).  list->strdup_strings must be set.
+ */
+void parse_string_list(struct string_list *list, const char *arg)
+{
+	if (!strcmp(arg, "-"))
+		return;
+
+	(void)string_list_split(list, arg, ':', -1);
+}
+
 void write_list(const struct string_list *list)
 {
 	int i;
@@ -8,6 +22,25 @@ void write_list(const struct string_list *list)
 		printf("[%d]: \"%s\"\n", i, list->items[i].string);
 }
 
+void write_list_compact(const struct string_list *list)
+{
+	int i;
+	if (!list->nr)
+		printf("-\n");
+	else {
+		printf("%s", list->items[0].string);
+		for (i = 1; i < list->nr; i++)
+			printf(":%s", list->items[i].string);
+		printf("\n");
+	}
+}
+
+int prefix_cb(struct string_list_item *item, void *cb_data)
+{
+	const char *prefix = (const char *)cb_data;
+	return !prefixcmp(item->string, prefix);
+}
+
 int main(int argc, char **argv)
 {
 	if (argc == 5 && !strcmp(argv[1], "split")) {
@@ -39,6 +72,21 @@ int main(int argc, char **argv)
 		return 0;
 	}
 
+	if (argc == 4 && !strcmp(argv[1], "filter")) {
+		/*
+		 * Retain only the items that have the specified prefix.
+		 * Arguments: list|- prefix
+		 */
+		struct string_list list = STRING_LIST_INIT_DUP;
+		const char *prefix = argv[3];
+
+		parse_string_list(&list, argv[2]);
+		filter_string_list(&list, 0, prefix_cb, (void *)prefix);
+		write_list_compact(&list);
+		string_list_clear(&list, 0);
+		return 0;
+	}
+
 	fprintf(stderr, "%s: unknown function name: %s\n", argv[0],
 		argv[1] ? argv[1] : "(there was none)");
 	return 1;
-- 
cgit v1.2.1


From 31d5451eed2677531c80177ff9dc8f5285f5a187 Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:45 +0200
Subject: string_list: add a new function, string_list_remove_duplicates()

Add a function that deletes duplicate entries from a sorted
string_list.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/technical/api-string-list.txt |  9 +++++++++
 string-list.c                               | 17 +++++++++++++++++
 string-list.h                               |  7 +++++++
 t/t0063-string-list.sh                      | 17 +++++++++++++++++
 test-string-list.c                          | 10 ++++++++++
 5 files changed, 60 insertions(+)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 300b30109..0f8b7cee3 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -30,6 +30,9 @@ member (you need this if you add things later) and you should set the
 
 . Can sort an unsorted list using `sort_string_list`.
 
+. Can remove duplicate items from a sorted list using
+  `string_list_remove_duplicates`.
+
 . Can remove individual items of an unsorted list using
   `unsorted_string_list_delete_item`.
 
@@ -108,6 +111,12 @@ write `string_list_insert(...)->util = ...;`.
 	Look up a given string in the string_list, returning the containing
 	string_list_item. If the string is not found, NULL is returned.
 
+`string_list_remove_duplicates`::
+
+	Remove all but the first of consecutive entries that have the
+	same string value.  If free_util is true, call free() on the
+	util members of any items that have to be deleted.
+
 * Functions for unsorted lists only
 
 `string_list_append`::
diff --git a/string-list.c b/string-list.c
index 179fde421..decfa747f 100644
--- a/string-list.c
+++ b/string-list.c
@@ -92,6 +92,23 @@ struct string_list_item *string_list_lookup(struct string_list *list, const char
 	return list->items + i;
 }
 
+void string_list_remove_duplicates(struct string_list *list, int free_util)
+{
+	if (list->nr > 1) {
+		int src, dst;
+		for (src = dst = 1; src < list->nr; src++) {
+			if (!strcmp(list->items[dst - 1].string, list->items[src].string)) {
+				if (list->strdup_strings)
+					free(list->items[src].string);
+				if (free_util)
+					free(list->items[src].util);
+			} else
+				list->items[dst++] = list->items[src];
+		}
+		list->nr = dst;
+	}
+}
+
 int for_each_string_list(struct string_list *list,
 			 string_list_each_func_t fn, void *cb_data)
 {
diff --git a/string-list.h b/string-list.h
index 7d18e622e..3a6a6dc39 100644
--- a/string-list.h
+++ b/string-list.h
@@ -48,6 +48,13 @@ struct string_list_item *string_list_insert_at_index(struct string_list *list,
 						     int insert_at, const char *string);
 struct string_list_item *string_list_lookup(struct string_list *list, const char *string);
 
+/*
+ * Remove all but the first of consecutive entries with the same
+ * string value.  If free_util is true, call free() on the util
+ * members of any items that have to be deleted.
+ */
+void string_list_remove_duplicates(struct string_list *sorted_list, int free_util);
+
 
 /* Use these functions only on unsorted lists: */
 
diff --git a/t/t0063-string-list.sh b/t/t0063-string-list.sh
index a5f05cd20..dbfc05ebd 100755
--- a/t/t0063-string-list.sh
+++ b/t/t0063-string-list.sh
@@ -71,4 +71,21 @@ test_expect_success "test filter_string_list" '
 	test "x-" = "x$(test-string-list filter x1:x2 y)"
 '
 
+test_expect_success "test remove_duplicates" '
+	test "x-" = "x$(test-string-list remove_duplicates -)" &&
+	test "x" = "x$(test-string-list remove_duplicates "")" &&
+	test a = "$(test-string-list remove_duplicates a)" &&
+	test a = "$(test-string-list remove_duplicates a:a)" &&
+	test a = "$(test-string-list remove_duplicates a:a:a:a:a)" &&
+	test a:b = "$(test-string-list remove_duplicates a:b)" &&
+	test a:b = "$(test-string-list remove_duplicates a:a:b)" &&
+	test a:b = "$(test-string-list remove_duplicates a:b:b)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:b:c)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:a:b:c)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:b:b:c)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:b:c:c)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:a:b:b:c:c)" &&
+	test a:b:c = "$(test-string-list remove_duplicates a:a:a:b:b:b:c:c:c)"
+'
+
 test_done
diff --git a/test-string-list.c b/test-string-list.c
index 702276c1f..2d6eda707 100644
--- a/test-string-list.c
+++ b/test-string-list.c
@@ -87,6 +87,16 @@ int main(int argc, char **argv)
 		return 0;
 	}
 
+	if (argc == 3 && !strcmp(argv[1], "remove_duplicates")) {
+		struct string_list list = STRING_LIST_INIT_DUP;
+
+		parse_string_list(&list, argv[2]);
+		string_list_remove_duplicates(&list, 0);
+		write_list_compact(&list);
+		string_list_clear(&list, 0);
+		return 0;
+	}
+
 	fprintf(stderr, "%s: unknown function name: %s\n", argv[0],
 		argv[1] ? argv[1] : "(there was none)");
 	return 1;
-- 
cgit v1.2.1


From f103f95b11d087f07c0c48bf784cd9197e18f203 Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:46 +0200
Subject: string_list: add a function string_list_longest_prefix()

Add a function that finds the longest string from a string_list that
is a prefix of a given string.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 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                          | 20 +++++++++++++++++++
 5 files changed, 86 insertions(+)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 0f8b7cee3..32b35d918 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -75,6 +75,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 decfa747f..c54b81624 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 3a6a6dc39..5efd07b44 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 want, 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 dbfc05ebd..41c8826a7 100755
--- a/t/t0063-string-list.sh
+++ b/t/t0063-string-list.sh
@@ -17,6 +17,14 @@ test_split () {
 	"
 }
 
+test_longest_prefix () {
+	test "$(test-string-list longest_prefix "$1" "$2")" = "$3"
+}
+
+test_no_longest_prefix () {
+	test_must_fail test-string-list longest_prefix "$1" "$2"
+}
+
 test_split "foo:bar:baz" ":" "-1" <<EOF
 3
 [0]: "foo"
@@ -88,4 +96,26 @@ test_expect_success "test remove_duplicates" '
 	test a:b:c = "$(test-string-list remove_duplicates a:a:a:b:b:b:c:c:c)"
 '
 
+test_expect_success "test longest_prefix" '
+	test_no_longest_prefix - '' &&
+	test_no_longest_prefix - x &&
+	test_longest_prefix "" x "" &&
+	test_longest_prefix x x x &&
+	test_longest_prefix "" foo "" &&
+	test_longest_prefix : foo "" &&
+	test_longest_prefix f foo f &&
+	test_longest_prefix foo foobar foo &&
+	test_longest_prefix foo foo foo &&
+	test_no_longest_prefix bar foo &&
+	test_no_longest_prefix bar:bar foo &&
+	test_no_longest_prefix foobar foo &&
+	test_longest_prefix foo:bar foo foo &&
+	test_longest_prefix foo:bar bar bar &&
+	test_longest_prefix foo::bar foo foo &&
+	test_longest_prefix foo:foobar foo foo &&
+	test_longest_prefix foobar:foo foo foo &&
+	test_longest_prefix foo: bar "" &&
+	test_longest_prefix :foo bar ""
+'
+
 test_done
diff --git a/test-string-list.c b/test-string-list.c
index 2d6eda707..5e9631fe3 100644
--- a/test-string-list.c
+++ b/test-string-list.c
@@ -97,6 +97,26 @@ 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_DUP;
+		int retval;
+		const char *prefix_string = argv[2];
+		const char *string = argv[3];
+		const char *match;
+
+		parse_string_list(&prefixes, prefix_string);
+		match = string_list_longest_prefix(&prefixes, string);
+		if (match) {
+			printf("%s\n", match);
+			retval = 0;
+		}
+		else
+			retval = 1;
+		string_list_clear(&prefixes, 0);
+		return retval;
+	}
+
 	fprintf(stderr, "%s: unknown function name: %s\n", argv[0],
 		argv[1] ? argv[1] : "(there was none)");
 	return 1;
-- 
cgit v1.2.1


From 51f3145c2834c8f1d94c5b7cf3790baf74b9f521 Mon Sep 17 00:00:00 2001
From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Wed, 12 Sep 2012 16:04:47 +0200
Subject: api-string-list.txt: initialize the string_list the easy way

In the demo code blurb, show how to initialize the string_list using
STRING_LIST_INIT_NODUP rather than memset().

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Documentation/technical/api-string-list.txt | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 32b35d918..155ac8cb1 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -44,10 +44,9 @@ member (you need this if you add things later) and you should set the
 Example:
 
 ----
-struct string_list list;
+struct string_list list = STRING_LIST_INIT_NODUP;
 int i;
 
-memset(&list, 0, sizeof(struct string_list));
 string_list_append(&list, "foo");
 string_list_append(&list, "bar");
 for (i = 0; i < list.nr; i++)
-- 
cgit v1.2.1