Skip to contentSkip to conversation

add strnncmp() function

PATCH Superseded Jeremiah Mahler 2 participants 8 messages Jun 15, 2016

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover add strnncmp() function

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(-)
Signature · 1 line
2.0.0
#1 lore raw

PATCH 1/3 add strnncmp() function

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

---
 strbuf.c | 6 ++++++
 strbuf.h | 2 ++
 2 files changed, 8 insertions(+)
strbuf.c +6 -0
index ac62982..bd486c3 100644
@@ -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));
+}
strbuf.h +2 -0
index e9ad03e..88af9bf 100644
@@ -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 */
Signature · 1 line
2.0.0
#2 lore raw
Quoted 2 lines · Jeremiah Mahler

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?

#3 lore raw

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

In reply to Jeremiah Mahler

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

---
 tree-walk.c | 16 +++-------------
 1 file changed, 3 insertions(+), 13 deletions(-)
tree-walk.c +3 -13
index 4dc86c7..efbd3b7 100644
@@ -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);
 			}
 		}
Signature · 1 line
2.0.0
#4 lore raw

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

Quoted 2 lines · Jeremiah Mahler
tree-walk.c +0 -0

[...]

tree-walk.c static int check_entry_match(const char *a, int a_len, const char *b, int b_len) · line 167

Quoted 6 lines
tree-walk.c +1 -1
@@ -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.

#5 lore raw

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

Jonathan,

Quoted 9 lines · Jonathan Nieder
Quoted 2 lines · Jeremiah Mahler
tree-walk.c +0 -0

[...]

Quoted 4 lines
tree-walk.c +0 -0
@@ -174,7 +164,7 @@ static int check_entry_match(const char *a, int a_len, const char *b, int b_len)
 	 * scanning further.
 	 */
 
Quoted 6 lines

tree-walk.c static int check_entry_match(const char *a, int a_len, const char *b, int b_len) · line 167

Quoted 2 lines
tree-walk.c +1 -1
-	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.

Signature · 3 lines
Jeremiah Mahler
[email protected]
http://github.com/jmahler
#6 lore raw

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

In reply to Jeremiah Mahler

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

---
 unpack-trees.c | 13 +------------
 1 file changed, 1 insertion(+), 12 deletions(-)
unpack-trees.c +1 -12
index 4a9cdf2..9a71b5a 100644
@@ -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.
Signature · 1 line
2.0.0
#7 lore raw

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

Quoted 2 lines · Jeremiah Mahler
unpack-trees.c +0 -0

[...]

unpack-trees.c static int find_cache_pos(struct traverse_info *info, · line 670

Quoted 6 lines
unpack-trees.c +1 -1
@@ -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.