Re: [PATCH 3/4] Add a new function, string_list_remove_duplicates()

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

On 09/09/2012 11:45 AM, Junio C Hamano wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
>> ---
>>  Documentation/technical/api-string-list.txt |  4 ++++
>>  string-list.c                               | 17 +++++++++++++++++
>>  string-list.h                               |  5 +++++
>>  3 files changed, 26 insertions(+)
>>
>> diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
>> index 15b8072..9206f8f 100644
>> --- a/Documentation/technical/api-string-list.txt
>> +++ b/Documentation/technical/api-string-list.txt
>> @@ -104,6 +104,10 @@ 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 entry that has a given string value.
> 
> Unlike the previous patch, free_util is not documented?

Fixed.

> It is kind of shame that the string list must be sorted for this
> function to work, but I guess you do not have a need for a version
> that works on both sorted and unsorted (yet).  We can introduce a
> variant with "unsorted_" prefix later when it becomes necessary, so
> OK.

Not only that; for an unsorted list it is not quite as obvious what a
caller would want.  Often lists are used as a poor man's set, in which
case the caller would probably not mind sorting the list anyway.  There
are two operations that one might conceive of for unsorted lists: (1)
remove duplicates while preserving the order of the remaining entries,
or (2) remove duplicates while not worrying about the order of the
remaining entries.  (Admittedly the first is not much more expensive
than the second.)  These are more complicated to program, require
temporary space, and are of less obvious utility than removing
duplicates from a sorted list.

>>  * Functions for unsorted lists only
>>  
>>  `string_list_append`::
>> diff --git a/string-list.c b/string-list.c
>> index 72610ce..bfef6cf 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 84996aa..c4dc659 100644
>> --- a/string-list.h
>> +++ b/string-list.h
>> @@ -38,6 +38,7 @@ 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);
>>  
>> +
>>  /* 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,
>> @@ -47,6 +48,10 @@ 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 entry that has a given string value. */
>> +void string_list_remove_duplicates(struct string_list *list, int free_util);
>> +
>> +
>>  /* Use these functions only on unsorted lists: */
>>  struct string_list_item *string_list_append(struct string_list *list, const char *string);
>>  void sort_string_list(struct string_list *list);


-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/