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 000000000..ddd83c8c7 --- /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 ddd83c8c7..15e14cf47 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 15e14cf47..1ac536e63 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