From c455c87c5cd42bbbe586b31cea1143132f3a39e4 Mon Sep 17 00:00:00 2001 From: Johannes Schindelin Date: Mon, 21 Jul 2008 19:03:49 +0100 Subject: Rename path_list to string_list The name path_list was correct for the first usage of that data structure, but it really is a general-purpose string list. $ perl -i -pe 's/path-list/string-list/g' $(git grep -l path-list) $ perl -i -pe 's/path_list/string_list/g' $(git grep -l path_list) $ git mv path-list.h string-list.h $ git mv path-list.c string-list.c $ perl -i -pe 's/has_path/has_string/g' $(git grep -l has_path) $ perl -i -pe 's/path/string/g' string-list.[ch] $ git mv Documentation/technical/api-path-list.txt \ Documentation/technical/api-string-list.txt $ perl -i -pe 's/strdup_paths/strdup_strings/g' $(git grep -l strdup_paths) ... and then fix all users of string-list to access the member "string" instead of "path". Documentation/technical/api-string-list.txt needed some rewrapping, too. Signed-off-by: Johannes Schindelin Signed-off-by: Junio C Hamano --- string-list.c | 134 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 134 insertions(+) create mode 100644 string-list.c (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c new file mode 100644 index 0000000000..ddd83c8c76 --- /dev/null +++ b/string-list.c @@ -0,0 +1,134 @@ +#include "cache.h" +#include "string-list.h" + +/* if there is no exact match, point to the index where the entry could be + * inserted */ +static int get_entry_index(const struct string_list *list, const char *string, + int *exact_match) +{ + int left = -1, right = list->nr; + + while (left + 1 < right) { + int middle = (left + right) / 2; + int compare = strcmp(string, list->items[middle].string); + if (compare < 0) + right = middle; + else if (compare > 0) + left = middle; + else { + *exact_match = 1; + return middle; + } + } + + *exact_match = 0; + return right; +} + +/* returns -1-index if already exists */ +static int add_entry(struct string_list *list, const char *string) +{ + int exact_match; + int index = get_entry_index(list, string, &exact_match); + + if (exact_match) + return -1 - index; + + if (list->nr + 1 >= list->alloc) { + list->alloc += 32; + list->items = xrealloc(list->items, list->alloc + * sizeof(struct string_list_item)); + } + if (index < list->nr) + memmove(list->items + index + 1, list->items + index, + (list->nr - index) + * sizeof(struct string_list_item)); + list->items[index].string = list->strdup_strings ? + xstrdup(string) : (char *)string; + list->items[index].util = NULL; + list->nr++; + + return index; +} + +struct string_list_item *string_list_insert(const char *string, struct string_list *list) +{ + int index = add_entry(list, string); + + if (index < 0) + index = -1 - index; + + return list->items + index; +} + +int string_list_has_string(const struct string_list *list, const char *string) +{ + int exact_match; + get_entry_index(list, string, &exact_match); + return exact_match; +} + +struct string_list_item *string_list_lookup(const char *string, struct string_list *list) +{ + int exact_match, i = get_entry_index(list, string, &exact_match); + if (!exact_match) + return NULL; + return list->items + i; +} + +void string_list_clear(struct string_list *list, int free_util) +{ + if (list->items) { + int i; + if (list->strdup_strings) { + for (i = 0; i < list->nr; i++) + free(list->items[i].string); + } + if (free_util) { + for (i = 0; i < list->nr; i++) + free(list->items[i].util); + } + free(list->items); + } + list->items = NULL; + list->nr = list->alloc = 0; +} + +void print_string_list(const char *text, const struct string_list *p) +{ + int i; + if ( text ) + printf("%s\n", text); + for (i = 0; i < p->nr; i++) + printf("%s:%p\n", p->items[i].string, p->items[i].util); +} + +struct string_list_item *string_list_append(const char *string, struct string_list *list) +{ + ALLOC_GROW(list->items, list->nr + 1, list->alloc); + list->items[list->nr].string = + list->strdup_strings ? xstrdup(string) : (char *)string; + return list->items + list->nr++; +} + +static int cmp_items(const void *a, const void *b) +{ + const struct string_list_item *one = a; + const struct string_list_item *two = b; + return strcmp(one->string, two->string); +} + +void sort_string_list(struct string_list *list) +{ + qsort(list->items, list->nr, sizeof(*list->items), cmp_items); +} + +int unsorted_string_list_has_string(struct string_list *list, const char *string) +{ + int i; + for (i = 0; i < list->nr; i++) + if (!strcmp(string, list->items[i].string)) + return 1; + return 0; +} + -- cgit v1.2.1 From cfa1ee6b340172a415049704cd848593392b9064 Mon Sep 17 00:00:00 2001 From: Marius Storm-Olsen Date: Sun, 8 Feb 2009 15:34:28 +0100 Subject: Add find_insert_index, insert_at_index and clear_func functions to string_list string_list_find_insert_index() and string_list_insert_at_index() enables you to see if an item is in the string_list, and to insert at the appropriate index in the list, if not there. This is usefull if you need to manipulate an existing item, if present, and insert a new item if not. Future mailmap code will use this construct to enable complex (old_name, old_email) -> (new_name, new_email) lookups. The string_list_clear_func() allows to call a custom cleanup function on each item in a string_list, which is useful is the util member points to a complex structure. Signed-off-by: Marius Storm-Olsen Signed-off-by: Junio C Hamano --- string-list.c | 43 +++++++++++++++++++++++++++++++++++++++---- 1 file changed, 39 insertions(+), 4 deletions(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index ddd83c8c76..15e14cf47a 100644 --- a/string-list.c +++ b/string-list.c @@ -26,10 +26,10 @@ static int get_entry_index(const struct string_list *list, const char *string, } /* returns -1-index if already exists */ -static int add_entry(struct string_list *list, const char *string) +static int add_entry(int insert_at, struct string_list *list, const char *string) { - int exact_match; - int index = get_entry_index(list, string, &exact_match); + int exact_match = 0; + int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match); if (exact_match) return -1 - index; @@ -53,7 +53,13 @@ static int add_entry(struct string_list *list, const char *string) struct string_list_item *string_list_insert(const char *string, struct string_list *list) { - int index = add_entry(list, string); + return string_list_insert_at_index(-1, string, list); +} + +struct string_list_item *string_list_insert_at_index(int insert_at, + const char *string, struct string_list *list) +{ + int index = add_entry(insert_at, list, string); if (index < 0) index = -1 - index; @@ -68,6 +74,16 @@ int string_list_has_string(const struct string_list *list, const char *string) return exact_match; } +int string_list_find_insert_index(const struct string_list *list, const char *string, + int negative_existing_index) +{ + int exact_match; + int index = get_entry_index(list, string, &exact_match); + if (exact_match) + index = -1 - (negative_existing_index ? index : 0); + return index; +} + struct string_list_item *string_list_lookup(const char *string, struct string_list *list) { int exact_match, i = get_entry_index(list, string, &exact_match); @@ -94,6 +110,25 @@ void string_list_clear(struct string_list *list, int free_util) list->nr = list->alloc = 0; } +void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc) +{ + if (list->items) { + int i; + if (clearfunc) { + for (i = 0; i < list->nr; i++) + clearfunc(list->items[i].util, list->items[i].string); + } + if (list->strdup_strings) { + for (i = 0; i < list->nr; i++) + free(list->items[i].string); + } + free(list->items); + } + list->items = NULL; + list->nr = list->alloc = 0; +} + + void print_string_list(const char *text, const struct string_list *p) { int i; -- cgit v1.2.1 From c6f5a7a916b36fc9dd00bb6dce3b68260579abe1 Mon Sep 17 00:00:00 2001 From: Jay Soffian Date: Wed, 25 Feb 2009 03:32:18 -0500 Subject: string-list: new for_each_string_list() function Add a convenience function for iterating over a string_list's items via a callback. Signed-off-by: Jay Soffian Signed-off-by: Junio C Hamano --- string-list.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 15e14cf47a..1ac536e638 100644 --- a/string-list.c +++ b/string-list.c @@ -92,6 +92,16 @@ struct string_list_item *string_list_lookup(const char *string, struct string_li return list->items + i; } +int for_each_string_list(string_list_each_func_t fn, + struct string_list *list, void *cb_data) +{ + int i, ret = 0; + for (i = 0; i < list->nr; i++) + if ((ret = fn(&list->items[i], cb_data))) + break; + return ret; +} + void string_list_clear(struct string_list *list, int free_util) { if (list->items) { -- cgit v1.2.1 From e242148012196772e3fe2652d538fb923b91ca92 Mon Sep 17 00:00:00 2001 From: Stephen Boyd Date: Wed, 24 Mar 2010 00:16:02 -0700 Subject: string-list: add unsorted_string_list_lookup() Sometimes users need to lookup a string in an unsorted string_list. In that case they should use this function instead of the version for sorted strings. Signed-off-by: Stephen Boyd Signed-off-by: Junio C Hamano --- string-list.c | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 1ac536e638..c9ad7fcd49 100644 --- a/string-list.c +++ b/string-list.c @@ -168,12 +168,19 @@ void sort_string_list(struct string_list *list) qsort(list->items, list->nr, sizeof(*list->items), cmp_items); } -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) { int i; for (i = 0; i < list->nr; i++) if (!strcmp(string, list->items[i].string)) - return 1; - return 0; + return list->items + i; + return NULL; +} + +int unsorted_string_list_has_string(struct string_list *list, + const char *string) +{ + return unsorted_string_list_lookup(list, string) != NULL; } -- cgit v1.2.1 From cb944f6b5009e4788041a5194d73b92a0620c9d9 Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:33 +0100 Subject: string_list: Fix argument order for print_string_list Update the definition and callers of print_string_list to use the string_list as the first argument. This helps make the API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index c9ad7fcd49..b7e57a407c 100644 --- a/string-list.c +++ b/string-list.c @@ -139,7 +139,7 @@ void string_list_clear_func(struct string_list *list, string_list_clear_func_t c } -void print_string_list(const char *text, const struct string_list *p) +void print_string_list(const struct string_list *p, const char *text) { int i; if ( text ) -- cgit v1.2.1 From b684e977363ee5cb53d83c69f2298d7898c5f89a Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:34 +0100 Subject: string_list: Fix argument order for for_each_string_list Update the definition and callers of for_each_string_list to use the string_list as the first argument. This helps make the string_list API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index b7e57a407c..09798a2dc8 100644 --- a/string-list.c +++ b/string-list.c @@ -92,8 +92,8 @@ struct string_list_item *string_list_lookup(const char *string, struct string_li return list->items + i; } -int for_each_string_list(string_list_each_func_t fn, - struct string_list *list, void *cb_data) +int for_each_string_list(struct string_list *list, + string_list_each_func_t fn, void *cb_data) { int i, ret = 0; for (i = 0; i < list->nr; i++) -- cgit v1.2.1 From 78a395d371ec9fd14297178ec98b8b1042a64fb6 Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:35 +0100 Subject: string_list: Fix argument order for string_list_insert Update the definition and callers of string_list_insert to use the string_list as the first argument. This helps make the string_list API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 09798a2dc8..de89efd2d8 100644 --- a/string-list.c +++ b/string-list.c @@ -51,7 +51,7 @@ static int add_entry(int insert_at, struct string_list *list, const char *string return index; } -struct string_list_item *string_list_insert(const char *string, struct string_list *list) +struct string_list_item *string_list_insert(struct string_list *list, const char *string) { return string_list_insert_at_index(-1, string, list); } -- cgit v1.2.1 From aadceea641806b363ca555ffdc04109ea716c497 Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:36 +0100 Subject: string_list: Fix argument order for string_list_insert_at_index Update the definition and callers of string_list_insert_at_index to use the string_list as the first argument. This helps make the string_list API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index de89efd2d8..84444c2c19 100644 --- a/string-list.c +++ b/string-list.c @@ -53,11 +53,11 @@ static int add_entry(int insert_at, struct string_list *list, const char *string struct string_list_item *string_list_insert(struct string_list *list, const char *string) { - return string_list_insert_at_index(-1, string, list); + return string_list_insert_at_index(list, -1, string); } -struct string_list_item *string_list_insert_at_index(int insert_at, - const char *string, struct string_list *list) +struct string_list_item *string_list_insert_at_index(struct string_list *list, + int insert_at, const char *string) { int index = add_entry(insert_at, list, string); -- cgit v1.2.1 From e8c8b7139c87c3e3017d3bff07f91c4349850d58 Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:37 +0100 Subject: string_list: Fix argument order for string_list_lookup Update the definition and callers of string_list_lookup to use the string_list as the first argument. This helps make the string_list API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 84444c2c19..7b616ae825 100644 --- a/string-list.c +++ b/string-list.c @@ -84,7 +84,7 @@ int string_list_find_insert_index(const struct string_list *list, const char *st return index; } -struct string_list_item *string_list_lookup(const char *string, struct string_list *list) +struct string_list_item *string_list_lookup(struct string_list *list, const char *string) { int exact_match, i = get_entry_index(list, string, &exact_match); if (!exact_match) -- cgit v1.2.1 From 1d2f80fa79cdc6f7f4fa1cefb47d7d19be3bc5ee Mon Sep 17 00:00:00 2001 From: Julian Phillips Date: Sat, 26 Jun 2010 00:41:38 +0100 Subject: string_list: Fix argument order for string_list_append Update the definition and callers of string_list_append to use the string_list as the first argument. This helps make the string_list API easier to use by being more consistent. Signed-off-by: Julian Phillips Signed-off-by: Junio C Hamano --- string-list.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 7b616ae825..9b023a2584 100644 --- a/string-list.c +++ b/string-list.c @@ -148,7 +148,7 @@ 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(const char *string, struct string_list *list) +struct string_list_item *string_list_append(struct string_list *list, const char *string) { ALLOC_GROW(list->items, list->nr + 1, list->alloc); list->items[list->nr].string = -- cgit v1.2.1 From 62b8102c60a716e66cfd2a33e596e9d5be134267 Mon Sep 17 00:00:00 2001 From: Jeff King Date: Sat, 12 Feb 2011 00:18:51 -0500 Subject: string_list_append: always set util pointer to NULL It is not immediately obvious that the util field may contain random bytes after appending an item. Especially since the string_list_insert* functions _do_ explicitly zero the util pointer. This does not appear to be a bug in any current git code, as all callers either fill in the util field immediately or never use it. However, it is worth it to be less surprising to new users of the string-list API who may expect it to be intialized to NULL. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano --- string-list.c | 1 + 1 file changed, 1 insertion(+) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 9b023a2584..51681189e8 100644 --- a/string-list.c +++ b/string-list.c @@ -153,6 +153,7 @@ struct string_list_item *string_list_append(struct string_list *list, const char 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++; } -- cgit v1.2.1 From 86d4b528d8a4752cc689279fb6d38c8697a507bb Mon Sep 17 00:00:00 2001 From: Johannes Sixt Date: Thu, 11 Aug 2011 23:20:00 -0600 Subject: string-list: Add API to remove an item from an unsorted list Teach the string-list API how to remove an entry in O(1) runtime by moving the last entry to the vacated spot. As such, the routine works only for unsorted lists. Signed-off-by: Johannes Sixt Signed-off-by: Elijah Newren Signed-off-by: Junio C Hamano --- string-list.c | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'string-list.c') diff --git a/string-list.c b/string-list.c index 51681189e8..d9810aba42 100644 --- a/string-list.c +++ b/string-list.c @@ -185,3 +185,12 @@ int unsorted_string_list_has_string(struct string_list *list, return unsorted_string_list_lookup(list, string) != NULL; } +void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util) +{ + if (list->strdup_strings) + free(list->items[i].string); + if (free_util) + free(list->items[i].util); + list->items[i] = list->items[list->nr-1]; + list->nr--; +} -- cgit v1.2.1