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/ (cherry picked from commit 83e8a6b3)
| Name |
Last commit
|
Last update |
|---|---|---|
| .. | ||
| apply | Loading commit data... | |
| attr | Loading commit data... | |
| blame | Loading commit data... | |
| buf | Loading commit data... | |
| checkout | Loading commit data... | |
| cherrypick | Loading commit data... | |
| clar | Loading commit data... | |
| clone | Loading commit data... | |
| commit | Loading commit data... | |
| config | Loading commit data... | |
| core | Loading commit data... | |
| date | Loading commit data... | |
| delta | Loading commit data... | |
| describe | Loading commit data... | |
| diff | Loading commit data... | |
| fetchhead | Loading commit data... | |
| filter | Loading commit data... | |
| graph | Loading commit data... | |
| index | Loading commit data... | |
| iterator | Loading commit data... | |
| merge | Loading commit data... | |
| network | Loading commit data... | |
| notes | Loading commit data... | |
| object | Loading commit data... | |
| odb | Loading commit data... | |
| online | Loading commit data... | |
| pack | Loading commit data... | |
| patch | Loading commit data... | |
| path | Loading commit data... | |
| perf | Loading commit data... | |
| rebase | Loading commit data... | |
| refs | Loading commit data... | |
| remote | Loading commit data... | |
| repo | Loading commit data... | |
| reset | Loading commit data... | |
| resources | Loading commit data... | |
| revert | Loading commit data... | |
| revwalk | Loading commit data... | |
| stash | Loading commit data... | |
| status | Loading commit data... | |
| stress | Loading commit data... | |
| submodule | Loading commit data... | |
| threads | Loading commit data... | |
| trace | Loading commit data... | |
| transport | Loading commit data... | |
| transports/smart | Loading commit data... | |
| win32 | Loading commit data... | |
| worktree | Loading commit data... | |
| README.md | Loading commit data... | |
| clar.c | Loading commit data... | |
| clar.h | Loading commit data... | |
| clar_libgit2.c | Loading commit data... | |
| clar_libgit2.h | Loading commit data... | |
| clar_libgit2_timer.c | Loading commit data... | |
| clar_libgit2_timer.h | Loading commit data... | |
| clar_libgit2_trace.c | Loading commit data... | |
| clar_libgit2_trace.h | Loading commit data... | |
| generate.py | Loading commit data... | |
| generate_crlf.sh | Loading commit data... | |
| main.c | Loading commit data... | |
| valgrind-supp-mac.txt | Loading commit data... |