diff --git a/libc/config/linux/aarch64/entrypoints.txt b/libc/config/linux/aarch64/entrypoints.txt --- a/libc/config/linux/aarch64/entrypoints.txt +++ b/libc/config/linux/aarch64/entrypoints.txt @@ -13,6 +13,7 @@ libc.src.string.strchr libc.src.string.strstr libc.src.string.strnlen + libc.src.string.memrchr ) set(TARGET_LIBM_ENTRYPOINTS diff --git a/libc/config/linux/api.td b/libc/config/linux/api.td --- a/libc/config/linux/api.td +++ b/libc/config/linux/api.td @@ -216,7 +216,8 @@ "strtok", "strerror", "strlen", - "strnlen" + "strnlen", + "memrchr" ]; let TypeDeclarations = [ diff --git a/libc/config/linux/x86_64/entrypoints.txt b/libc/config/linux/x86_64/entrypoints.txt --- a/libc/config/linux/x86_64/entrypoints.txt +++ b/libc/config/linux/x86_64/entrypoints.txt @@ -31,6 +31,7 @@ libc.src.string.strchr libc.src.string.strstr libc.src.string.strnlen + libc.src.string.memrchr # sys/mman.h entrypoints libc.src.sys.mman.mmap diff --git a/libc/spec/gnu_ext.td b/libc/spec/gnu_ext.td --- a/libc/spec/gnu_ext.td +++ b/libc/spec/gnu_ext.td @@ -12,8 +12,22 @@ >, ] >; + + HeaderSpec String = HeaderSpec< + "string.h", + [], // Macros + [], // Types + [], // Enumerations + [ + FunctionSpec< + "memrchr", + RetValSpec, + [ArgSpec, ArgSpec, ArgSpec] + >, + ] + >; let Headers = [ - Math, + Math, String, ]; } diff --git a/libc/src/string/CMakeLists.txt b/libc/src/string/CMakeLists.txt --- a/libc/src/string/CMakeLists.txt +++ b/libc/src/string/CMakeLists.txt @@ -78,6 +78,14 @@ .memchr ) +add_entrypoint_object( + memrchr + SRCS + memrchr.cpp + HDRS + memrchr.h +) + # Helper to define a function with multiple implementations # - Computes flags to satisfy required/rejected features and arch, # - Declares an entry point, diff --git a/libc/src/string/memrchr.h b/libc/src/string/memrchr.h new file mode 100644 --- /dev/null +++ b/libc/src/string/memrchr.h @@ -0,0 +1,20 @@ +//===-- Implementation header for memrchr -----------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIBC_SRC_STRING_MEMRCHR_H +#define LLVM_LIBC_SRC_STRING_MEMRCHR_H + +#include + +namespace __llvm_libc { + +void *memrchr(const void *src, int c, size_t n); + +} // namespace __llvm_libc + +#endif // LLVM_LIBC_SRC_STRING_MEMRCHR_H diff --git a/libc/src/string/memrchr.cpp b/libc/src/string/memrchr.cpp new file mode 100644 --- /dev/null +++ b/libc/src/string/memrchr.cpp @@ -0,0 +1,26 @@ +//===-- Implementation of memrchr -----------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/string/memrchr.h" +#include "src/__support/common.h" +#include + +namespace __llvm_libc { + +void *LLVM_LIBC_ENTRYPOINT(memrchr)(const void *src, int c, size_t n) { + const unsigned char *str = reinterpret_cast(src); + const unsigned char ch = c; + for (; n != 0; --n) { + const unsigned char *s = str + n - 1; + if (*s == ch) + return const_cast(s); + } + return nullptr; +} + +} // namespace __llvm_libc diff --git a/libc/test/src/string/CMakeLists.txt b/libc/test/src/string/CMakeLists.txt --- a/libc/test/src/string/CMakeLists.txt +++ b/libc/test/src/string/CMakeLists.txt @@ -82,6 +82,16 @@ libc.src.string.strnlen ) +add_libc_unittest( + memrchr_test + SUITE + libc_string_unittests + SRCS + memrchr_test.cpp + DEPENDS + libc.src.string.memrchr +) + # Tests all implementations that can run on the host. function(add_libc_multi_impl_test name) get_property(fq_implementations GLOBAL PROPERTY ${name}_implementations) diff --git a/libc/test/src/string/memrchr_test.cpp b/libc/test/src/string/memrchr_test.cpp new file mode 100644 --- /dev/null +++ b/libc/test/src/string/memrchr_test.cpp @@ -0,0 +1,114 @@ +//===-- Unittests for memrchr ---------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "src/string/memrchr.h" +#include "utils/UnitTest/Test.h" +#include + +// A helper function that calls memrchr and abstracts away the explicit cast for +// readability purposes. +const char *call_memrchr(const void *src, int c, size_t size) { + return reinterpret_cast(__llvm_libc::memrchr(src, c, size)); +} + +TEST(MemRChrTest, FindsCharacterAfterNullTerminator) { + // memrchr should continue searching after a null terminator. + const size_t size = 6; + const unsigned char src[size] = {'a', '\0', 'b', 'c', 'd', '\0'}; + // Should return 'b', 'c', 'd', '\0' even when after null terminator. + ASSERT_STREQ(call_memrchr(src, 'b', size), "bcd"); +} + +TEST(MemRChrTest, FindsCharacterInNonNullTerminatedCollection) { + const size_t size = 3; + const unsigned char src[size] = {'a', 'b', 'c'}; + // Should return 'b', 'c'. + const char *ret = call_memrchr(src, 'b', size); + ASSERT_EQ(ret[0], 'b'); + ASSERT_EQ(ret[1], 'c'); +} + +TEST(MemRChrTest, FindsFirstCharacter) { + const size_t size = 6; + const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'}; + // Should return original array since 'a' is the first character. + ASSERT_STREQ(call_memrchr(src, 'a', size), "abcde"); +} + +TEST(MemRChrTest, FindsMiddleCharacter) { + const size_t size = 6; + const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'}; + // Should return characters after (and including) 'c'. + ASSERT_STREQ(call_memrchr(src, 'c', size), "cde"); +} + +TEST(MemRChrTest, FindsLastCharacterThatIsNotNullTerminator) { + const size_t size = 6; + const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'}; + // Should return 'e' and null-terminator. + ASSERT_STREQ(call_memrchr(src, 'e', size), "e"); +} + +TEST(MemRChrTest, FindsNullTerminator) { + const size_t size = 6; + const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'}; + // Should return null terminator. + ASSERT_STREQ(call_memrchr(src, '\0', size), ""); +} + +TEST(MemRChrTest, CharacterNotWithinStringShouldReturnNullptr) { + const size_t size = 4; + const unsigned char src[size] = {'1', '2', '3', '?'}; + // Since 'z' is not within 'characters', should return nullptr. + ASSERT_STREQ(call_memrchr(src, 'z', size), nullptr); +} + +TEST(MemRChrTest, CharacterNotWithinSizeShouldReturnNullptr) { + const unsigned char src[5] = {'1', '2', '3', '4', '\0'}; + // Since '4' is not within the first 2 characters, this should return nullptr. + const size_t size = 2; + ASSERT_STREQ(call_memrchr(src, '4', size), nullptr); +} + +TEST(MemRChrTest, ShouldFindLastOfDuplicates) { + size_t size = 12; // 11 characters + null terminator. + const char *dups = "abc1def1ghi"; + // 1 is duplicated in 'dups', but it should find the last copy. + ASSERT_STREQ(call_memrchr(dups, '1', size), "1ghi"); + + const char *repeated = "XXXXX"; + size = 6; // 5 characters + null terminator. + // Should return the last X with the null terminator. + ASSERT_STREQ(call_memrchr(repeated, 'X', size), "X"); +} + +TEST(MemRChrTest, EmptyStringShouldOnlyMatchNullTerminator) { + const size_t size = 1; // Null terminator. + const char *empty_string = ""; + // Null terminator should match. + ASSERT_STREQ(call_memrchr(empty_string, '\0', size), ""); + // All other characters should not match. + ASSERT_STREQ(call_memrchr(empty_string, 'A', size), nullptr); + ASSERT_STREQ(call_memrchr(empty_string, '9', size), nullptr); + ASSERT_STREQ(call_memrchr(empty_string, '?', size), nullptr); +} + +TEST(MemRChrTest, SignedCharacterFound) { + char c = -1; + const size_t size = 1; + char src[size] = {c}; + const char *actual = call_memrchr(src, c, size); + // Should find the last character 'c'. + ASSERT_EQ(actual[0], c); +} + +TEST(MemRChrTest, ZeroLengthShouldReturnNullptr) { + const unsigned char src[4] = {'a', 'b', 'c', '\0'}; + // This will iterate over exactly zero characters, so should return nullptr. + ASSERT_STREQ(call_memrchr(src, 'd', 0), nullptr); +}