[PATCH 0/3] add strnncmp() function

[PATCH 0/3] add strnncmp() function

[Jeremiah Mahler]

Add a strnncmp() function which behaves like strncmp() except it uses
the length of both strings instead of just one.

Then simplify tree-walk.c and unpack-trees.c using this new function.
Replace all occurances of name_compare() with strnncmp().  Remove
name_compare(), which they both had identical copies of.

Jeremiah Mahler (3):
  add strnncmp() function
  tree-walk: simplify via strnncmp()
  unpack-trees: simplify via strnncmp()

 strbuf.c       |  6 ++++++
 strbuf.h       |  2 ++
 tree-walk.c    | 16 +++-------------
 unpack-trees.c | 13 +------------
 4 files changed, 12 insertions(+), 25 deletions(-)

-- 
2.0.0

[PATCH 1/3] add strnncmp() function

[Jeremiah Mahler]

Add a strnncmp() function which behaves like strncmp() except it uses
the length of both strings instead of just one.

Signed-off-by: Jeremiah Mahler <jmmahler@gmail.com>
---
 strbuf.c | 6 ++++++
 strbuf.h | 2 ++
 2 files changed, 8 insertions(+)

diff --git a/strbuf.c b/strbuf.c
index ac62982..bd486c3 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -600,3 +600,9 @@ char *xstrdup_tolower(const char *string)
 	result[i] = '\0';
 	return result;
 }
+
+int strnncmp(const char *a, int len_a, const char *b, int len_b)
+{
+	int min_len = (len_a < len_b) ? len_a : len_b;
+	return (memcmp(a, b, min_len) || (len_a - len_b));
+}
diff --git a/strbuf.h b/strbuf.h
index e9ad03e..88af9bf 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -187,4 +187,6 @@ extern int fprintf_ln(FILE *fp, const char *fmt, ...);
 
 char *xstrdup_tolower(const char *);
 
+extern int strnncmp(const char *a, int len_a, const char *b, int len_b);
+
 #endif /* STRBUF_H */
-- 
2.0.0

Re: [PATCH 1/3] add strnncmp() function

[Jonathan Nieder]

Jeremiah Mahler wrote:

> Add a strnncmp() function which behaves like strncmp() except it uses
> the length of both strings instead of just one.

The above description isn't very clear to me.  Problems:

 - strncmp compares prefixes of \0-terminated strings.  This function
   compares two binary buffers which can contain \0

 - strncmp is a comparison function and can even be used with functions
   like qsort (for operations like "sort on the first two characters").
   This function returns 0 or nonzero.

Would something like

  /* true if buffers have the same length and are byte-for-byte identical */
  int bufeq(const char *, int, const char *, int);

(or buf_equal, array_equal etc) make sense?

[PATCH 2/3] tree-walk: simplify via strnncmp()

[Jeremiah Mahler]

Simplify tree-walk.c using the strnncmp() function and remove the
name_compare() function.

Signed-off-by: Jeremiah Mahler <jmmahler@gmail.com>
---
 tree-walk.c | 16 +++-------------
 1 file changed, 3 insertions(+), 13 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 4dc86c7..efbd3b7 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -144,16 +144,6 @@ struct tree_desc_x {
 	struct tree_desc_skip *skip;
 };
 
-static int name_compare(const char *a, int a_len,
-			const char *b, int b_len)
-{
-	int len = (a_len < b_len) ? a_len : b_len;
-	int cmp = memcmp(a, b, len);
-	if (cmp)
-		return cmp;
-	return (a_len - b_len);
-}
-
 static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 {
 	/*
@@ -174,7 +164,7 @@ static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 	 * scanning further.
 	 */
 
-	int cmp = name_compare(a, a_len, b, b_len);
+	int cmp = strnncmp(a, a_len, b, b_len);
 
 	/* Most common case first -- reading sync'd trees */
 	if (!cmp)
@@ -369,7 +359,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 				first_len = len;
 				continue;
 			}
-			if (name_compare(e->path, len, first, first_len) < 0) {
+			if (strnncmp(e->path, len, first, first_len) < 0) {
 				first = e->path;
 				first_len = len;
 			}
@@ -383,7 +373,7 @@ int traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
 				if (!e->path)
 					continue;
 				len = tree_entry_len(e);
-				if (name_compare(e->path, len, first, first_len))
+				if (strnncmp(e->path, len, first, first_len))
 					entry_clear(e);
 			}
 		}
-- 
2.0.0

Re: [PATCH 2/3] tree-walk: simplify via strnncmp()

[Jonathan Nieder]

Jeremiah Mahler wrote:

> --- a/tree-walk.c
> +++ b/tree-walk.c
[...]
> @@ -174,7 +164,7 @@ static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
>  	 * scanning further.
>  	 */
>  
> -	int cmp = name_compare(a, a_len, b, b_len);
> +	int cmp = strnncmp(a, a_len, b, b_len);

This changes behavior: the old version would only have 0 < cmp if
'a' comes after 'b', while the new version always has 0 < cmp when
a != b.

Re: [PATCH 2/3] tree-walk: simplify via strnncmp()

[Jeremiah Mahler]

Jonathan,

On Mon, Jun 16, 2014 at 01:18:06PM -0700, Jonathan Nieder wrote:
> Jeremiah Mahler wrote:
> 
> > --- a/tree-walk.c
> > +++ b/tree-walk.c
> [...]
> > @@ -174,7 +164,7 @@ static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
> >  	 * scanning further.
> >  	 */
> >  
> > -	int cmp = name_compare(a, a_len, b, b_len);
> > +	int cmp = strnncmp(a, a_len, b, b_len);
> 
> This changes behavior: the old version would only have 0 < cmp if
> 'a' comes after 'b', while the new version always has 0 < cmp when
> a != b.

Thanks for catching this.  I did not realize that when I tried to
cleanup the logic I inadvertently changed its behavior.

    int strnncmp(const char *a, int len_a, const char *b, int len_b)
    {
           int min_len = (len_a < len_b) ? len_a : len_b;
           return (memcmp(a, b, min_len) || (len_a - len_b));
    }

is not the same as:

    static int name_compare(const char *a, int a_len,
                           const char *b, int b_len)
    {
           int len = (a_len < b_len) ? a_len : b_len;
           int cmp = memcmp(a, b, len);
           if (cmp)
                   return cmp;
           return (a_len - b_len);
    }

(-5 || 3) is 1, not -5.

-- 
Jeremiah Mahler
jmmahler@gmail.com
http://github.com/jmahler

[PATCH 3/3] unpack-trees: simplify via strnncmp()

[Jeremiah Mahler]

Simplify unpack-trees.c using the strnncmp() function and remove the
name_compare() function.

Signed-off-by: Jeremiah Mahler <jmmahler@gmail.com>
---
 unpack-trees.c | 13 +------------
 1 file changed, 1 insertion(+), 12 deletions(-)

diff --git a/unpack-trees.c b/unpack-trees.c
index 4a9cdf2..9a71b5a 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -629,17 +629,6 @@ static int unpack_failed(struct unpack_trees_options *o, const char *message)
 	return -1;
 }
 
-/* NEEDSWORK: give this a better name and share with tree-walk.c */
-static int name_compare(const char *a, int a_len,
-			const char *b, int b_len)
-{
-	int len = (a_len < b_len) ? a_len : b_len;
-	int cmp = memcmp(a, b, len);
-	if (cmp)
-		return cmp;
-	return (a_len - b_len);
-}
-
 /*
  * The tree traversal is looking at name p.  If we have a matching entry,
  * return it.  If name p is a directory in the index, do not return
@@ -678,7 +667,7 @@ static int find_cache_pos(struct traverse_info *info,
 			ce_len = ce_slash - ce_name;
 		else
 			ce_len = ce_namelen(ce) - pfxlen;
-		cmp = name_compare(p->path, p_len, ce_name, ce_len);
+		cmp = strnncmp(p->path, p_len, ce_name, ce_len);
 		/*
 		 * Exact match; if we have a directory we need to
 		 * delay returning it.
-- 
2.0.0

Re: [PATCH 3/3] unpack-trees: simplify via strnncmp()

[Jonathan Nieder]

Jeremiah Mahler wrote:

> --- a/unpack-trees.c
> +++ b/unpack-trees.c
[...]
> @@ -678,7 +667,7 @@ static int find_cache_pos(struct traverse_info *info,
>  			ce_len = ce_slash - ce_name;
>  		else
>  			ce_len = ce_namelen(ce) - pfxlen;
> -		cmp = name_compare(p->path, p_len, ce_name, ce_len);
> +		cmp = strnncmp(p->path, p_len, ce_name, ce_len);

Likewise --- the sign of the result is important here.