[libc] Use best-fit binary trie to make malloc logarithmic (#106259)
[llvm-project.git] / libc / src / stdio / printf_core / vasprintf_internal.h
blob0e446f856e43815b2e242d8c4ad07cc7fb757eb4
1 //===-- Internal Implementation of asprintf ---------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
9 #include "hdr/func/free.h"
10 #include "hdr/func/malloc.h"
11 #include "hdr/func/realloc.h"
12 #include "src/__support/arg_list.h"
13 #include "src/stdio/printf.h"
14 #include "src/stdio/printf_core/core_structs.h"
15 #include "src/stdio/printf_core/printf_main.h"
16 #include "src/stdio/printf_core/writer.h"
18 namespace LIBC_NAMESPACE_DECL {
19 namespace printf_core {
21 LIBC_INLINE int resize_overflow_hook(cpp::string_view new_str, void *target) {
22 printf_core::WriteBuffer *wb =
23 reinterpret_cast<printf_core::WriteBuffer *>(target);
24 size_t new_size = new_str.size() + wb->buff_cur;
25 const bool isBuffOnStack = (wb->buff == wb->init_buff);
26 char *new_buff = static_cast<char *>(
27 isBuffOnStack ? malloc(new_size + 1)
28 : realloc(wb->buff, new_size + 1)); // +1 for null
29 if (new_buff == nullptr) {
30 if (wb->buff != wb->init_buff)
31 free(wb->buff);
32 return printf_core::ALLOCATION_ERROR;
34 if (isBuffOnStack)
35 inline_memcpy(new_buff, wb->buff, wb->buff_cur);
36 wb->buff = new_buff;
37 inline_memcpy(wb->buff + wb->buff_cur, new_str.data(), new_str.size());
38 wb->buff_cur = new_size;
39 wb->buff_len = new_size;
40 return printf_core::WRITE_OK;
43 constexpr size_t DEFAULT_BUFFER_SIZE = 200;
45 LIBC_INLINE int vasprintf_internal(char **ret, const char *__restrict format,
46 internal::ArgList args) {
47 char init_buff_on_stack[DEFAULT_BUFFER_SIZE];
48 printf_core::WriteBuffer wb(init_buff_on_stack, DEFAULT_BUFFER_SIZE,
49 resize_overflow_hook);
50 printf_core::Writer writer(&wb);
52 auto ret_val = printf_core::printf_main(&writer, format, args);
53 if (ret_val < 0) {
54 *ret = nullptr;
55 return -1;
57 if (wb.buff == init_buff_on_stack) {
58 *ret = static_cast<char *>(malloc(ret_val + 1));
59 if (ret == nullptr)
60 return printf_core::ALLOCATION_ERROR;
61 inline_memcpy(*ret, wb.buff, ret_val);
62 } else {
63 *ret = wb.buff;
65 (*ret)[ret_val] = '\0';
66 return ret_val;
68 } // namespace printf_core
69 } // namespace LIBC_NAMESPACE_DECL