[libc] Add memchr implementation.

[cgyurgyik]

Summary

[libc] Adds memchr implementation with corresponding unit tests. Uses a simple loop to iterate through the string.

[sivachandra]

libc/src/string/memchr.cpp

19

Do you need the explicit static cast? Without it, wouldn't the compile time implicit cast do the same thing?

23

I think you don't need need the cast to void*.

25

Return nullptr?

libc/test/src/string/memchr_test.cpp

19

To avoid the noisy casts to const char *, may be use a helper function call call_memchr here and in other tests.

20

I don't think you need the casts to void* here and in the rest of the tests.

23

Why not ASSERT_STREQ?

33

Ditto.

[cgyurgyik]

Changes in accordance with Siva's review.

[cgyurgyik]

libc/src/string/memchr.cpp

19

Semantically they're the same thing. I just assumed that when narrowing or widening, its always better to be explicit.

libc/test/src/string/memchr_test.cpp

33

Since src is not null-terminated, ASSERT_STREQ is going to look beyond the end of the array. I could add a null terminator to the end of ret, but don't know if that's much better than this approach. Is there an approach you were thinking of?

[sivachandra]

libc/config/linux/x86_64/entrypoints.txt

30

Add it to the aarch64 list as well?

libc/src/string/CMakeLists.txt

54

Do we need this dependency?

libc/test/src/string/memchr_test.cpp

33

Acknowledged.

[sivachandra]

libc/src/string/memchr.cpp

19

You still need a cast. I was asking about the explicit static cast, but at least the implicit cast is requried. That is:

unsigned char ch = c;
for (; n && *str != ch; --n, ++str)
...

Without this, and if char type were signed char, then this will happen:

char c = -1;
char mem[5] = {c, c, c, c, c};
memchr(mem, c, 5);

The unsigned char values in mem are all 255. But, they will get promoted to an int value of 255 and then compared with an int value of -1. So memchr will return nullptr.

Sorry for not catching this earlier.

libc/config/linux/aarch64/entrypoints.txt

 set(TARGET_LIBC_ENTRYPOINTS
     # errno.h entrypoints
     libc.src.errno.__errno_location
 
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
+    libc.src.string.memchr
 )
 
 set(TARGET_LIBM_ENTRYPOINTS
     # math.h entrypoints
     libc.src.math.copysign
     libc.src.math.copysignf
     libc.src.math.copysignl
     libc.src.math.ceil

libc/config/linux/x86_64/entrypoints.txt

set(TARGET_LIBC_ENTRYPOINTS
     # string.h entrypoints
     libc.src.string.bzero
     libc.src.string.memcpy
     libc.src.string.memset
     libc.src.string.strcpy
     libc.src.string.strcat
     libc.src.string.strlen
     libc.src.string.strcmp
+    libc.src.string.memchr
 
     # sys/mman.h entrypoints
     libc.src.sys.mman.mmap
     libc.src.sys.mman.munmap
 
     # threads.h entrypoints
     libc.src.threads.call_once
     libc.src.threads.mtx_init

libc/src/string/CMakeLists.txt

add_entrypoint_object(
   SRCS
     strcmp.cpp
   HDRS
     strcmp.h
   DEPENDS
     libc.include.string
 )
 
+add_entrypoint_object(
+  memchr
+  SRCS
+    memchr.cpp
+  HDRS
+    memchr.h
+)
+
+
 # Helper to define a function with multiple implementations
 # - Computes flags to satisfy required/rejected features and arch,
 # - Declares an entry point,
 # - Attach the REQUIRE_CPU_FEATURES property to the target,
 # - Add the fully qualified target to `${name}_implementations` global property for tests.
 function(add_implementation name impl_name)
   cmake_parse_arguments(
     "ADD_IMPL"

libc/src/string/memchr.h

+//===-- Implementation header for memchr ------------------------*- 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_MEMCHR_H
+#define LLVM_LIBC_SRC_STRING_MEMCHR_H
+
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+void *memchr(const void *src, int c, size_t n);
+
+} // namespace __llvm_libc
+
+#endif // LLVM_LIBC_SRC_STRING_MEMCHR_H

libc/src/string/memchr.cpp

+//===-- Implementation of memchr ------------------------------------------===//
+//
+// 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/memchr.h"
+#include "src/__support/common.h"
+#include <stddef.h>
+
+namespace __llvm_libc {
+
+// TODO: Look at performance benefits of comparing words.
+void *LLVM_LIBC_ENTRYPOINT(memchr)(const void *src, int c, size_t n) {
+  const unsigned char *str = reinterpret_cast<const unsigned char *>(src);
+  for (; n && *str != c; --n, ++str)
+    ;
+  return n ? const_cast<unsigned char *>(str) : nullptr;
+}
+
+} // namespace __llvm_libc

libc/test/src/CMakeLists.txt

DEPENDS
       clang-tidy ${public_test}
   )
   add_dependencies(libc-integration-test libc-integration-test-tidy)
 endif()
 
 target_link_libraries(libc-integration-test
   PRIVATE
   ${library_files}
-)
+)
 No newline at end of file

libc/test/src/string/CMakeLists.txt

add_libc_unittest(
   SUITE
     libc_string_unittests
   SRCS
     strcmp_test.cpp
   DEPENDS
     libc.src.string.strcmp
 )
 
+add_libc_unittest(
+  memchr_test
+  SUITE
+    libc_string_unittests
+  SRCS
+    memchr_test.cpp
+  DEPENDS
+    libc.src.string.memchr
+)
+
 # Tests all implementations that can run on the host.
 function(add_libc_multi_impl_test name)
   get_property(fq_implementations GLOBAL PROPERTY ${name}_implementations)
   foreach(fq_config_name IN LISTS fq_implementations)
     get_target_property(required_cpu_features ${fq_config_name} REQUIRE_CPU_FEATURES)
     host_supports(can_run "${required_cpu_features}")
     if(can_run)
       add_libc_unittest(
         ${fq_config_name}_test
         SUITE
           libc_string_unittests
         DEPENDS
           ${fq_config_name}
         ${ARGN}
       )
     else()
       message(STATUS "Skipping test for '${fq_config_name}' insufficient host cpu features '${required_cpu_features}'")
     endif()
   endforeach()
 endfunction()
 
 add_libc_multi_impl_test(memcpy SRCS memcpy_test.cpp)
 add_libc_multi_impl_test(memset SRCS memset_test.cpp)
 add_libc_multi_impl_test(bzero SRCS bzero_test.cpp)
-

libc/test/src/string/memchr_test.cpp

+//===-- Unittests for memchr ----------------------------------------------===//
+//
+// 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/memchr.h"
+#include "utils/UnitTest/Test.h"
+#include <stddef.h>
+
+// A helper function that calls memchr and abstracts away the explicit cast for
+// readability purposes.
+const char *call_memchr(const void *src, int c, size_t size) {
+  return reinterpret_cast<const char *>(__llvm_libc::memchr(src, c, size));
+}
+
+TEST(MemChrTest, FindsCharacterAfterNullTerminator) {
+  // memchr should continue searching after a null terminator.
+  const size_t size = 5;
+  const unsigned char src[size] = {'a', '\0', 'b', 'c', '\0'};
+  // Should return 'b', 'c', '\0' even when after null terminator.
+  ASSERT_STREQ(call_memchr(src, 'b', size), "bc");
+}
+
+TEST(MemChrTest, FindsCharacterInNonNullTerminatedCollection) {
+  const size_t size = 3;
+  const unsigned char src[size] = {'a', 'b', 'c'};
+  // Should return 'b', 'c'.
+  const char *ret = call_memchr(src, 'b', size);
+  ASSERT_EQ(ret[0], 'b');
+  ASSERT_EQ(ret[1], 'c');
+}
+
+TEST(MemChrTest, 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_memchr(src, 'a', size), "abcde");
+}
+
+TEST(MemChrTest, 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_memchr(src, 'c', size), "cde");
+}
+
+TEST(MemChrTest, 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_memchr(src, 'e', size), "e");
+}
+
+TEST(MemChrTest, FindsNullTerminator) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  // Should return null terminator.
+  ASSERT_STREQ(call_memchr(src, '\0', size), "");
+}
+
+TEST(MemChrTest, 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_memchr(src, 'z', size), nullptr);
+}
+
+TEST(MemChrTest, CharacterNotWithinSizeShouldReturnNullptr) {
+  const unsigned char src[5] = {'1', '2', '3', '4', '\0'};
+  // Since '4' is not the first or second character, this should return nullptr.
+  const size_t size = 2;
+  ASSERT_STREQ(call_memchr(src, '4', size), nullptr);
+}
+
+TEST(MemChrTest, TheSourceShouldNotChange) {
+  const size_t size = 6;
+  const unsigned char src[size] = {'a', 'b', 'c', 'd', 'e', '\0'};
+  const char *src_copy = reinterpret_cast<const char *>(src);
+  // When the character is found, the source string should not change.
+  __llvm_libc::memchr(src, 'd', size);
+  ASSERT_STREQ(reinterpret_cast<const char *>(src), src_copy);
+  // Same case for when the character is not found.
+  __llvm_libc::memchr(src, 'z', size);
+  ASSERT_STREQ(reinterpret_cast<const char *>(src), src_copy);
+}
+
+TEST(MemChrTest, ShouldFindFirstOfDuplicates) {
+  const size_t size = 12; // 11 characters + null terminator.
+  const char *dups = "abc1def1ghi";
+  // 1 is duplicated in 'dups', but it should find the first copy.
+  ASSERT_STREQ(call_memchr(dups, '1', size), "1def1ghi");
+}
+
+TEST(MemChrTest, EmptyStringShouldOnlyMatchNullTerminator) {
+  const size_t size = 1; // Null terminator.
+  const char *empty_string = "";
+  // Null terminator should match.
+  ASSERT_STREQ(call_memchr(empty_string, '\0', size), "");
+  // All other characters should not match.
+  ASSERT_STREQ(call_memchr(empty_string, 'A', size), nullptr);
+  ASSERT_STREQ(call_memchr(empty_string, '9', size), nullptr);
+  ASSERT_STREQ(call_memchr(empty_string, '?', size), nullptr);
+}
+
+TEST(MemChrTest, SingleRepeatedCharacterShouldReturnFirst) {
+  const char *dups = "XXXXX";
+  const size_t size = 6; // 5 characters + null terminator.
+  // Should return original string since X is first character.
+  ASSERT_STREQ(call_memchr(dups, 'X', size), dups);
+}