threads / patch / 38037

patch, 3 partsstring_list: document string_list_(insert,lookup)

Subject: [PATCH 1/3] string_list: document string_list_(insert,lookup)

## tl;dr

5 messages between Nov 24, 2014 and Nov 25, 2014. Diffs are folded; open one to read it.

replies: 4people: 2as markdown or json

Stefan Beller· Nov 24, 2014, 21:22 UTC · lore
Signed-off-by: Stefan Beller <sbeller@google.com>
---
 string-list.h | 10 ++++++++++
 1 file changed, 10 insertions(+)
Show changes to string-list.h +10 −0
diff --git a/string-list.h b/string-list.h
index 494eb5d..40ffe0c 100644
--- a/string-list.h
+++ b/string-list.h
@@ -55,9 +55,19 @@ void string_list_remove_empty_items(struct string_list *list, int free_util);
 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,
 				  int negative_existing_index);
+/*
+ * Inserts the given string into the sorted list.
+ * If the string already exists, the list is not altered.
+ * Returns the string_list_item, the string is part of.
+ */
 struct string_list_item *string_list_insert(struct string_list *list, const char *string);
 struct string_list_item *string_list_insert_at_index(struct string_list *list,
 						     int insert_at, const char *string);
+
+/*
+ * Checks if the given string is part of a sorted list. If it is part of the list,
+ * return the coresponding string_list_item, NULL otherwise.
+ */
 struct string_list_item *string_list_lookup(struct string_list *list, const char *string);
 
 /*

-- 
2.2.0.rc3
Stefan Beller· Nov 24, 2014, 21:22 UTC · re: Stefan Beller · lore

[PATCH 2/3] mailmap: use higher level string list functions

No functional changes intended. This commit makes user of higher level and better documented functions of the string list API, so the code is more understandable.

Note that also the required computational amount should not change in principal as we need to look up the item no matter if it is already part of the list or not. Once looked up, insertion comes for free.

Signed-off-by: Stefan Beller <sbeller@google.com>
---
 mailmap.c | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)
Show changes to mailmap.c +3 −8
diff --git a/mailmap.c b/mailmap.c
index 81890a6..f0df350 100644
--- a/mailmap.c
+++ b/mailmap.c
@@ -78,15 +78,10 @@ static void add_mapping(struct string_list *map,
 		new_email = NULL;
 	}
 
-	if ((index = string_list_find_insert_index(map, old_email, 1)) < 0) {
-		/* mailmap entry exists, invert index value */
-		index = -1 - index;
-		me = (struct mailmap_entry *)map->items[index].util;
+	struct string_list_item *item = string_list_insert(map, old_email);
+	if (item->util) {
+		me = (struct mailmap_entry *)item->util;
 	} else {
-		/* create mailmap entry */
-		struct string_list_item *item;
-
-		item = string_list_insert_at_index(map, index, old_email);
 		me = xcalloc(1, sizeof(struct mailmap_entry));
 		me->namemap.strdup_strings = 1;
 		me->namemap.cmp = namemap_cmp;

-- 
2.2.0.rc3
Stefan Beller· Nov 24, 2014, 21:22 UTC · re: Stefan Beller · lore

[PATCH 3/3] string_list: Remove string_list_insert_at_index from its API

This function behaves the same as string_list_insert, just the starting indexes for searching, where to insert into the list is also a parameter. So if you have knowledge on where to search for the string to be inserted, you may have a speed up version of string_list_insert.

As we're not using this function throughout the codebase, get rid of it.
Signed-off-by: Stefan Beller <sbeller@google.com>
---
 string-list.c | 8 +-------
 string-list.h | 2 --
 2 files changed, 1 insertion(+), 9 deletions(-)
Show changes to 2 files +1 −9

string-list.c, string-list.h

diff --git a/string-list.c b/string-list.c
index c5aa076..9584fa6 100644
--- a/string-list.c
+++ b/string-list.c
@@ -59,13 +59,7 @@ 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(list, -1, string);
-}
-
-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);
+	int index = add_entry(-1, list, string);
 
 	if (index < 0)
 		index = -1 - index;
diff --git a/string-list.h b/string-list.h
index 40ffe0c..ee9b100 100644
--- a/string-list.h
+++ b/string-list.h
@@ -61,8 +61,6 @@ int string_list_find_insert_index(const struct string_list *list, const char *st
  * Returns the string_list_item, the string is part of.
  */
 struct string_list_item *string_list_insert(struct string_list *list, const char *string);
-struct string_list_item *string_list_insert_at_index(struct string_list *list,
-						     int insert_at, const char *string);
 
 /*
  * Checks if the given string is part of a sorted list. If it is part of the list,

-- 
2.2.0.rc3
Junio C Hamano· Nov 25, 2014, 00:25 UTC · re: Stefan Beller · lore

Re: [PATCH 3/3] string_list: Remove string_list_insert_at_index from its API

Stefan Beller <sbeller@google.com> writes:
> This function behaves the same as string_list_insert, just the
> starting indexes for searching, where to insert into the list is also
> a parameter. So if you have knowledge on where to search for the string
> to be inserted, you may have a speed up version of string_list_insert.

The last half-sentence I am having trouble parsing. If you have that knowledge where the item should go, you can insert it at the right location faster than calling string_list_insert()?

That sounds like a useful feature to me.

But if nobody uses that feature, there is no point keeping it, no matter how useful it may sound. So,... I am not sure.

The function would be error prone if used on a string-list that is accessed via string_list_insert() API, which makes it only useful if the user of the API is in full control of the sort order, so I do not mind removing it and won't be saying "that is useful, we should keep it and use it more."

But your log message confuses me....
Show 41 quoted lines
>
> As we're not using this function throughout the codebase, get rid of it.
>
> Signed-off-by: Stefan Beller <sbeller@google.com>
> ---
>  string-list.c | 8 +-------
>  string-list.h | 2 --
>  2 files changed, 1 insertion(+), 9 deletions(-)
>
> diff --git a/string-list.c b/string-list.c
> index c5aa076..9584fa6 100644
> --- a/string-list.c
> +++ b/string-list.c
> @@ -59,13 +59,7 @@ 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(list, -1, string);
> -}
> -
> -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);
> +	int index = add_entry(-1, list, string);
>  
>  	if (index < 0)
>  		index = -1 - index;
> diff --git a/string-list.h b/string-list.h
> index 40ffe0c..ee9b100 100644
> --- a/string-list.h
> +++ b/string-list.h
> @@ -61,8 +61,6 @@ int string_list_find_insert_index(const struct string_list *list, const char *st
>   * Returns the string_list_item, the string is part of.
>   */
>  struct string_list_item *string_list_insert(struct string_list *list, const char *string);
> -struct string_list_item *string_list_insert_at_index(struct string_list *list,
> -						     int insert_at, const char *string);
>  
>  /*
>   * Checks if the given string is part of a sorted list. If it is part of the list,
Stefan Beller· Nov 25, 2014, 01:16 UTC · re: Junio C Hamano · lore

Re: [PATCH 3/3] string_list: Remove string_list_insert_at_index from its API

On Mon, Nov 24, 2014 at 4:25 PM, Junio C Hamano <gitster@pobox.com> wrote:
Show 24 quoted lines
> Stefan Beller <sbeller@google.com> writes:
>
>> This function behaves the same as string_list_insert, just the
>> starting indexes for searching, where to insert into the list is also
>> a parameter. So if you have knowledge on where to search for the string
>> to be inserted, you may have a speed up version of string_list_insert.
>
> The last half-sentence I am having trouble parsing.  If you have
> that knowledge where the item should go, you can insert it at the
> right location faster than calling string_list_insert()?
>
> That sounds like a useful feature to me.
>
> But if nobody uses that feature, there is no point keeping it, no
> matter how useful it may sound.  So,... I am not sure.
>
> The function would be error prone if used on a string-list that is
> accessed via string_list_insert() API, which makes it only useful if
> the user of the API is in full control of the sort order, so I do
> not mind removing it and won't be saying "that is useful, we should
> keep it and use it more."
>
> But your log message confuses me....
>
Well, I'm sorry for the confusion, here is what I was trying to say:

We do not remove functionality from the API, but rather remove a a highly optimized version of a function, which we are not using after patch 2 of the series anyway.

We should keep it around only iff we strongly believe there will be a use case later again. But for now I do have the opinion, we're better off removing the function as a smaller API / header file serves us better. Specially new comers may appreciate a smaller API but documented there.

Maybe we can drop the commit message altogether if my thoughts are still confusing?

← back to recent threads