Blatantly incorrect. Try thinking over how you might implement those two operations on a string with a length field and see if you can figure out why your statement is wrong.
(referring to an allocation-free strstr if strings had an associated length)
If a string was a (pointer,length) pair, then strstr would return a pair (pointer+offset,length-offset) where, just like in the original strstr, the new pointer points into the existing string. No allocation needed
(But what about the pointer-length pair that has to be created? Well, it will live on the stack just like the return value from the original strstr, which has to be stored somewhere also.)
Except that's not how K&R would have done it. It would have been pascal style: one byte of length directly followed by the string itself in memory. The pointer would be the address of the length byte. Now it's hard to create strstr without copying so they wouldn't. Instead you would have a new API where every call would have offsets to the beginning, likely it would be one based too. Anyway C does it the way it does cause PDP set the zero condition flag on move.
When someone makes a post demonstrating a complete failure to consider an argument before making it (claiming that a substring search requires allocation of any kind when all it does is scan and return an offset...) I don't think it's necessary for me to explain in elaborate detail why they're wrong.
I don't need to explain how I'd implement it because every obvious implementation of the strstr algorithm doesn't need to allocate because it's a substring search! Search operations are pure and don't mutate!
Every single implementation of strstr or equivalent in every single programming language I have ever seen does not require an allocation. It either returns a pointer to the location of the first matched result, or returns the character index of the first match. That's it.
Any other absurd implementation you can think up to justify null-terminated strings - like returning a copy of the string with a null terminator after the match - just doesn't make any sense. That's a different operation.
int strstr(string haystack, string needle, int offset);
DESCRIPTION
The strstr() function finds the first occurrence of the substring needle
in the string haystack, starting from position offset in haystack.
RETURN VALUE
This function returns the index of the first character in haystack after
offset where needle can be found, or -1 if the substring is not found (or
if offset is out of bounds for haystack).
Same complexity and memory overhead as C strstr(). Actually more efficient if needle is longer than haystack + offset, which can be checked in O(1) on entry.
(I don't have a problem with NUL-terminated strings, but couldn't resist a little sideways thinking on how an alternate library implementation for strings might work.)
That's a far less useful function, since you still have to do a memory copy if you want to pass the return value to a function that operates on strings.
Only if the first occurrence of needle happens to terminate the string. Otherwise the return value of the real version of strstr returns a string that starts with needle but is followed by more text.
OK, so for that one particular use case[0], the result of strstr might not be quite as convenient as the NUL-terminated strstr() case. But that's what you get with a completely different string implementation - some operations are more efficient than others, others less so. It's a bunch of trade-offs.
But strstr() finds the position of a substring within a larger string, or indicates that it doesn't exist. My suggested API for the equivalent functionality does exactly that, with no problems or performance issues for the job strstr() itself needs to do that I can see.
[0] A use case I have to say I find a little contrived. I can say that the majority of the times I've used strstr(), it's either to simply check that needle exists in haystack, or to take the part of the haystack following needle - at which point I normally need to make a copy because I can't guarantee that the source string will be around for the lifetime that I need the remainder for.
Different experiences, I guess. Your "contrived use case" is my "only reason I've ever used strstr". That said, I haven't done a ton of C programming, so maybe my experience is atypical.
Comments
Blatantly incorrect. Try thinking over how you might implement those two operations on a string with a length field and see if you can figure out why your statement is wrong.
That came across as very condescending to me. Could you tell us how you would implement this?
I for one do not see how to implement it.
(referring to an allocation-free strstr if strings had an associated length)
If a string was a (pointer,length) pair, then strstr would return a pair (pointer+offset,length-offset) where, just like in the original strstr, the new pointer points into the existing string. No allocation needed
(But what about the pointer-length pair that has to be created? Well, it will live on the stack just like the return value from the original strstr, which has to be stored somewhere also.)
Except that's not how K&R would have done it. It would have been pascal style: one byte of length directly followed by the string itself in memory. The pointer would be the address of the length byte. Now it's hard to create strstr without copying so they wouldn't. Instead you would have a new API where every call would have offsets to the beginning, likely it would be one based too. Anyway C does it the way it does cause PDP set the zero condition flag on move.
When someone makes a post demonstrating a complete failure to consider an argument before making it (claiming that a substring search requires allocation of any kind when all it does is scan and return an offset...) I don't think it's necessary for me to explain in elaborate detail why they're wrong.
I don't need to explain how I'd implement it because every obvious implementation of the strstr algorithm doesn't need to allocate because it's a substring search! Search operations are pure and don't mutate!
Every single implementation of strstr or equivalent in every single programming language I have ever seen does not require an allocation. It either returns a pointer to the location of the first matched result, or returns the character index of the first match. That's it.
Any other absurd implementation you can think up to justify null-terminated strings - like returning a copy of the string with a null terminator after the match - just doesn't make any sense. That's a different operation.
NAME
SYNOPSIS DESCRIPTION RETURN VALUE Same complexity and memory overhead as C strstr(). Actually more efficient if needle is longer than haystack + offset, which can be checked in O(1) on entry.(I don't have a problem with NUL-terminated strings, but couldn't resist a little sideways thinking on how an alternate library implementation for strings might work.)
That's a far less useful function, since you still have to do a memory copy if you want to pass the return value to a function that operates on strings.
Or you could just pass 'needle', which is already that string.
Only if the first occurrence of needle happens to terminate the string. Otherwise the return value of the real version of strstr returns a string that starts with needle but is followed by more text.
OK, so for that one particular use case[0], the result of strstr might not be quite as convenient as the NUL-terminated strstr() case. But that's what you get with a completely different string implementation - some operations are more efficient than others, others less so. It's a bunch of trade-offs.
But strstr() finds the position of a substring within a larger string, or indicates that it doesn't exist. My suggested API for the equivalent functionality does exactly that, with no problems or performance issues for the job strstr() itself needs to do that I can see.
[0] A use case I have to say I find a little contrived. I can say that the majority of the times I've used strstr(), it's either to simply check that needle exists in haystack, or to take the part of the haystack following needle - at which point I normally need to make a copy because I can't guarantee that the source string will be around for the lifetime that I need the remainder for.
Different experiences, I guess. Your "contrived use case" is my "only reason I've ever used strstr". That said, I haven't done a ton of C programming, so maybe my experience is atypical.