add strnncmp() function

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the

strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644

strbuf.c +8 -0

+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;
+	int cmp = strncmp(a, b, min_len);
 
+	if (cmp)
+		return cmp;
+	return (len_a - len_b);
+}

Quoted 3 lines · Jeremiah Mahler

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the

minimum common length? Isn'n t that 0?
Using the word "common", I think we could call it "common length". (And more places below)

Quoted 14 lines

strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644

strbuf.c char *xstrdup_tolower(const char *string) · line 603

Quoted 4 lines

strbuf.c +1 -0

@@ -600,3 +600,12 @@ char *xstrdup_tolower(const char *string)
 	result[i] = '\0';
 	return result;
 }
+

strncmp uses size_t, not int:
int strncmp(const char *s1, const char *s2, size_t n);

Is there a special reason to allow negative string length? Some call sites use int when calling strncmp() or others, that is one thing.
But when writing a generic strnncmp() function, I think it should use size_t, unless negative values have a meaning and are handled in the code.

strbuf.c char *xstrdup_tolower(const char *string) · line 611

Quoted 10 lines

strbuf.c +8 -0

+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;
+	int cmp = strncmp(a, b, min_len);
 
+	if (cmp)
+		return cmp;
+	return (len_a - len_b);
+}

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644
@@ -600,3 +600,12 @@ char *xstrdup_tolower(const char *string)
        result[i] = '\0';
        return result;

Quoted 19 lines · Jeremiah Mahler

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644
@@ -600,3 +600,12 @@ char *xstrdup_tolower(const char *string)
        result[i] = '\0';
        return result;

strbuf.c char *xstrdup_tolower(const char *string) · line 611

Quoted 10 lines

strbuf.c +9 -0

 }
+
+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;
+       int cmp = strncmp(a, b, min_len);
+       if (cmp)
+               return cmp;
+       return (len_a - len_b);
+}

Using a name that sounds like it's from the stdlib makes me cringe a little bit. Names that start with "str" reserved for stdlib[1][2], but we already ignore this for strbuf (and perhaps some other functions). However, in this case it doesn't seem *that* unlikely that we might collide with some stdlib-extensions.

[1]: http://pubs.opengroup.org/onlinepubs/007904975/functions/xsh_chap02_02.html#tag_02_02_02
[2]: http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644
@@ -600,3 +600,12 @@ char *xstrdup_tolower(const char *string)
 	result[i] = '\0';
 	return result;

Quoted 19 lines · Jeremiah Mahler

Add a strnncmp() function which behaves like strncmp() except it takes the length of both strings instead of just one. It behaves the same as strncmp() up to the minimum common length between the strings. When the strings are identical up to this minimum common length, the length difference is returned.

Signed-off-by Jeremiah Mahler <[email protected]>

---
 strbuf.c | 9 +++++++++
 strbuf.h | 2 ++
 2 files changed, 11 insertions(+)

strbuf.c +0 -0

index ac62982..4eb7954 100644
@@ -600,3 +600,12 @@ char *xstrdup_tolower(const char *string)
 	result[i] = '\0';
 	return result;

strbuf.c char *xstrdup_tolower(const char *string) · line 611

Quoted 10 lines

strbuf.c +9 -0

 }
+
+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;
+	int cmp = strncmp(a, b, min_len);
+	if (cmp)
+		return cmp;
+	return (len_a - len_b);
+}

I am not sure if the interface into this function conceptually makes much sense. strncmp(entry, string, 14) was invented as the way to see if a NUL terminated "string" matches with the contents in an array of char "entry" that is up to 14 bytes long, and because the "entry" was allowed to fill full 14-byte space without terminated with a NUL, the maximum possible length is specified separately, but a NUL termination in "entry", if exists, is still honored. Is there any case where such a pair of "maximum N bytes but could be shorter" strings are compared, especially with different N's defined per string, in our codebase (or in other people's project for that matter)?

Further, I do think that the interface into this function and its implementation are inappropriate for implementing the name_compare() function in tree-walk.c and unpack-trees.c. These functions are designed to take counted strings; in a tuple <a, a_len> they take, "a_len" is the only thing that determines the length of string "a". There is no room for a NUL termination inside "a" come into play to make "a" shorter than "a_len".

In other words, "Two NUL-terminated strings can be compared with strcmp(a, b), but we use counted strings in many places in our codebase, and compare_counted_strings(a, a_len, b, b_len) function would help us, so let's add one and use it in name_compare()" may make good sense, but if we were to do so, I do not think strncmp() would be involved in its implementation.

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

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

Version 2 includes suggestions from Jonathan Neider [1]:

- Fix the logic which caused the new strnncmp() to behave differently from the old version. Now it is identical to strncmp().

- Improve description of strnncmp().

Also, strnncmp() was switched from using memcmp() to strncmp() internally to make it clear that this is meant for strings, not general buffers.

Quoted 9 lines · Jeremiah Mahler

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

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

Version 2 includes suggestions from Jonathan Neider [1]:

Quoted 8 lines

- Fix the logic which caused the new strnncmp() to behave differently from the old version. Now it is identical to strncmp().

- Improve description of strnncmp().

Also, strnncmp() was switched from using memcmp() to strncmp() internally to make it clear that this is meant for strings, not general buffers.

I don't think this is a good change, for 2 reasons:
- It changes the semantics of existing code, which should be carefully reviewed, documented and may be put into a seperate commit.
- Looking into the code for memcmp() and strncmp() in libc, I can see that memcmp() is written in 13 lines of assembler, (on a 386 system) with a fast

    repz cmpsb %es:(%edi),%ds:(%esi)

working as the core engine.

strncmp() uses 83 lines of assembler, because after each comparison the code needs to check of the '\0' in both strings.
- I can't see a reason to replace efficient code with less efficient code, so moving the old function "as is" into a include file, and declare it "static inline" could be the first step.

Having code inline may open the door for the compiler to decide, "Oh, I know exactly what memcmp() does, so I through in a handfull of lines assembly code, instead of calling memcmp() from libc".

And another thing:
What does cache_name_compare(name, namelen, ce->name, len)) in name-hash.c do?
Isn't that the same function ?

I like strnncmp() better than
cache_name_compare() or name_compare(),
but I agree with Erik here that strnncmp() has the potential to become a name clash some day, so that git_strnncmp() may be better.

Thanks for the effort, cleaning up is needed.

Quoted 5 lines · Jeremiah Mahler

Quoted 4 lines

Also, strnncmp() was switched from using memcmp() to strncmp() internally to make it clear that this is meant for strings, not general buffers.

Quoted 5 lines

Quoted 5 lines · Jeremiah Mahler

Quoted 4 lines

Also, strnncmp() was switched from using memcmp() to strncmp() internally to make it clear that this is meant for strings, not general buffers.

Why shouldn't I want to use this helper on arbitrary data? One of the advantages of other helpers in git that take a pointer and a length (e.g., the strbuf library) are that they are 8-bit clean and can work on binary data when it's useful.

Thanks,
Jonathan

Quoted 9 lines · Jeremiah Mahler

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

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

Version 2 includes suggestions from Jonathan Neider [1]:

Quoted 8 lines

- Fix the logic which caused the new strnncmp() to behave differently from the old version. Now it is identical to strncmp().

- Improve description of strnncmp().

Also, strnncmp() was switched from using memcmp() to strncmp() internally to make it clear that this is meant for strings, not general buffers.

I don't think this is a good change, for 2 reasons:
- It changes the semantics of existing code, which should be carefully reviewed, documented and may be put into a seperate commit.
- Looking into the code for memcmp() and strncmp() in libc, I can see that memcmp() is written in 13 lines of assembler, (on a 386 system) with a fast

    repz cmpsb %es:(%edi),%ds:(%esi)

working as the core engine.

strncmp() uses 83 lines of assembler, because after each comparison the code needs to check of the '\0' in both strings.
- I can't see a reason to replace efficient code with less efficient code, so moving the old function "as is" into a include file, and declare it "static inline" could be the first step.