9
$\begingroup$

I can't help but to notice that not all str* functions have mem* counterparts, even when having them would make logical sense. Of course, a memlen() function would make absolutely 0 sense.

But why doesn't C have memmem() to find a needle of a specified length in a haystack of a specified length? This sounds a lot more useful and versatile to me than strstr() which only works on strings. If anything the former should be included and not the latter, because the strstr() could just be implemented as memmem(needle, strlen(needle), haystack, strlen(haystack)).

Another example of such a function would be memrchr().

But it's strstr() that C has and not memmem(). Why might that be? Why don't all the str* functions have logical mem* counterparts?

$\endgroup$
6
  • $\begingroup$ Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. $\endgroup$ Commented Jun 28, 2023 at 20:18
  • 3
    $\begingroup$ I don’t think you are likely to find any satisfying answer to this question. The reasons are almost certainly not because of any particular principle so much as “because that was what they needed for the programs they were writing so that was the way they did it”. $\endgroup$
    – Alexis King
    Commented Jun 28, 2023 at 20:45
  • 4
    $\begingroup$ Note that glibc and others have a memmem(const void*,size_t,const void*,size_t), using a very similar horspool algorithm as their strstr(const char*,const char*) with the main difference being the NUL detection necessary for strstr. Back when C was standardized, it was probably just not common to need one and such not widespread. $\endgroup$
    – PlasmaHH
    Commented Jun 29, 2023 at 6:46
  • 1
    $\begingroup$ memmem is also scheduled to be included in the next version of POSIX.1. austingroupbugs.net/view.php?id=1061 proposed the addition, and you can find memmem in the draft "Additional APIs for the Base Specifications Issue 8, Part 1" document. $\endgroup$
    – AJM
    Commented Jun 30, 2023 at 14:40
  • 1
    $\begingroup$ opengroup.org/austin/docs/austin_842.txt noted a difference in the behaviour of Solaris's memmem compared to the versions in glibc/BSDs. opengroup.org/austin/docs/austin_847.txt confirmed that Solaris devs were willing to change that behaviour (as were HP-UX and AIX devs - so presumably their implementations were also discovered to behave like Solaris's). This allowed a consensus on the standardised memmem to be reached. $\endgroup$
    – AJM
    Commented Jun 30, 2023 at 14:41

1 Answer 1

11
$\begingroup$

I have no particular insight into decisions made by the designers of the C standard library, but I can offer some informed speculation.

A C string is a (null-terminated) array of characters. That is, the elements in the array are a known size, the size of a character. On the other hand, a block of memory could represent anything, and even if it is an array, the stride of the array could be arbitrary. And the things in the array might make sense to compare bit-for-bit, or they might not (i.e. two values might be logically equal even if they don't have the same bit pattern).

So your proposed linear search functions would make sense if the block of memory represents an array of values which can be compared bit-for-bit, but they all need an extra argument for the array stride. And then the implementation of those functions would have a loop which increments the search address by that variable, which is less performant than incrementing by a compile-time constant, particularly incrementing by 1 for an array index.

So for performance reasons, it is better to write a linear search function that is specialised for the stride of the array you want to search.

$\endgroup$
5
  • 4
    $\begingroup$ In particular, it is very likely that any struct will contain padding bits or bytes that are often filled with garbage rather than explicitly zeroed (and arrays can have similar padding between elements) -- thus bits in the raw data that do not participate in logical equality. This is also why you can't rely on memcmping an array or struct with anything but a known previous memcpy -- other forms of assignment may or may not copy these padding bits. $\endgroup$
    – Miral
    Commented Jun 29, 2023 at 5:51
  • $\begingroup$ More precisely, in C structure assignment is allowed to do anything that behaves the equivalent of member-wise assignment -- this might actually be member-wise assignment (leaving padding unchanged), or memcpy (copying padding), or even some hybrid thereof. You can't make any assumptions and even if you test what your compiler happens to do today, circumstances might change. C++ is similar but it leans even harder toward member-wise behaviour given the possibility of copy constructors and overloaded operators. $\endgroup$
    – Miral
    Commented Jun 29, 2023 at 7:07
  • $\begingroup$ @Miral Very good point. I was thinking more like floating-point numbers, or integers represented as sign and magnitude, where 0 == -0 but they have different bit patterns; or not-necessarily-reduced fractions where (6, 4) and (3, 2) are logically equal. But padding is probably much more common, particularly now that every processor uses two's complement for integers. $\endgroup$
    – kaya3
    Commented Jun 29, 2023 at 14:36
  • $\begingroup$ Searching struct arrays for exact matches is not a common operation anyway -- usually you search for a particular member (e.g. search a phone book by name). On the other hand, it's not uncommon to search an array of integers. $\endgroup$
    – Barmar
    Commented Jun 29, 2023 at 15:01
  • $\begingroup$ Well-written code which works with strings will avoid using any str* functions other than strlen, and use mem* functions to act upon storage after measuring strings' lengths once. A memmem function could be just as useful as strstr when working with strings, but for many tasks, string-search code that knows something about the data it will likely receive can be much more efficient when fed such data than any general-purpose function could be. $\endgroup$
    – supercat
    Commented Sep 8, 2023 at 20:40

Not the answer you're looking for? Browse other questions tagged .