Unfortunately, neither the `memmem` nor the `strnstr` functions are part of any C standard but are merely extensions of C that are implemented by e.g. glibc. Thus, there is no standardized way to search for a string in a block of memory with a limited size, and using `strstr` is to be considered unsafe in case where the buffer has not been sanitized. In fact, there are some uses of `strstr` in exactly that unsafe way in our codebase. Provide a new function `git__memmem` that implements the `memmem` semantics. That is in a given haystack of `n` bytes, search for the occurrence of a byte sequence of `m` bytes and return a pointer to the first occurrence. The implementation chosen is the "Not So Naive" algorithm from [1]. It was chosen as the implementation is comparably simple while still being reasonably efficient in most cases. Preprocessing happens in constant time and space, searching has a time complexity of O(n*m) with a slightly sub-linear average case. [1]: http://www-igm.univ-mlv.fr/~lecroq/string/
Name |
Last commit
|
Last update |
---|---|---|
.. | ||
array.c | Loading commit data... | |
bitvec.c | Loading commit data... | |
buffer.c | Loading commit data... | |
copy.c | Loading commit data... | |
dirent.c | Loading commit data... | |
encoding.c | Loading commit data... | |
env.c | Loading commit data... | |
errors.c | Loading commit data... | |
features.c | Loading commit data... | |
filebuf.c | Loading commit data... | |
ftruncate.c | Loading commit data... | |
futils.c | Loading commit data... | |
hex.c | Loading commit data... | |
iconv.c | Loading commit data... | |
init.c | Loading commit data... | |
link.c | Loading commit data... | |
memmem.c | Loading commit data... | |
mkdir.c | Loading commit data... | |
oid.c | Loading commit data... | |
oidmap.c | Loading commit data... | |
opts.c | Loading commit data... | |
path.c | Loading commit data... | |
pool.c | Loading commit data... | |
posix.c | Loading commit data... | |
pqueue.c | Loading commit data... | |
rmdir.c | Loading commit data... | |
sha1.c | Loading commit data... | |
sortedcache.c | Loading commit data... | |
stat.c | Loading commit data... | |
stream.c | Loading commit data... | |
string.c | Loading commit data... | |
strmap.c | Loading commit data... | |
strtol.c | Loading commit data... | |
structinit.c | Loading commit data... | |
useragent.c | Loading commit data... | |
vector.c | Loading commit data... | |
zstream.c | Loading commit data... |