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 |
|---|---|---|
| .github | Loading commit data... | |
| ci | Loading commit data... | |
| cmake/Modules | Loading commit data... | |
| deps | Loading commit data... | |
| docs | Loading commit data... | |
| examples | Loading commit data... | |
| include | Loading commit data... | |
| script | Loading commit data... | |
| src | Loading commit data... | |
| tests | Loading commit data... | |
| .HEADER | Loading commit data... | |
| .editorconfig | Loading commit data... | |
| .gitattributes | Loading commit data... | |
| .gitignore | Loading commit data... | |
| .mailmap | Loading commit data... | |
| AUTHORS | Loading commit data... | |
| CHANGELOG.md | Loading commit data... | |
| CMakeLists.txt | Loading commit data... | |
| CODE_OF_CONDUCT.md | Loading commit data... | |
| CONTRIBUTING.md | Loading commit data... | |
| CONVENTIONS.md | Loading commit data... | |
| COPYING | Loading commit data... | |
| PROJECTS.md | Loading commit data... | |
| README.md | Loading commit data... | |
| THREADING.md | Loading commit data... | |
| api.docurium | Loading commit data... | |
| azure-pipelines.yml | Loading commit data... | |
| git.git-authors | Loading commit data... | |
| libgit2.pc.in | Loading commit data... | |
| libgit2_clar.supp | Loading commit data... |