diff options
author | Johannes Sixt <j.sixt@viscovery.net> | 2011-08-12 09:20:00 +0400 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2011-08-15 01:19:35 +0400 |
commit | 86d4b528d8a4752cc689279fb6d38c8697a507bb (patch) | |
tree | 960aa6832d1f56ba8f2ae53aa145b55eb430c0a2 | |
parent | aacb82de3ff8ae7b0a9e4cfec16c1807b6c315ef (diff) |
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 <j6t@kdbg.org>
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r-- | Documentation/technical/api-string-list.txt | 10 | ||||
-rw-r--r-- | string-list.c | 9 | ||||
-rw-r--r-- | string-list.h | 1 |
3 files changed, 20 insertions, 0 deletions
diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt index 3f575bdcff3..ce24eb96f5e 100644 --- a/Documentation/technical/api-string-list.txt +++ b/Documentation/technical/api-string-list.txt @@ -29,6 +29,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 individual items of an unsorted list using + `unsorted_string_list_delete_item`. + . Finally it should free the list using `string_list_clear`. Example: @@ -112,6 +115,13 @@ write `string_list_insert(...)->util = ...;`. The above two functions need to look through all items, as opposed to their counterpart for sorted lists, which performs a binary search. +`unsorted_string_list_delete_item`:: + + Remove an item from a string_list. The `string` pointer of the items + will be freed in case the `strdup_strings` member of the string_list + is set. The third parameter controls if the `util` pointer of the + items should be freed or not. + Data structures --------------- diff --git a/string-list.c b/string-list.c index 51681189e83..d9810aba421 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--; +} diff --git a/string-list.h b/string-list.h index bda69839832..0684cb73bfd 100644 --- a/string-list.h +++ b/string-list.h @@ -44,4 +44,5 @@ 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 */ |