如何在 C 中连接字节数组

Question

我当前的连接函数：

char* concat(char* a, int a_size,
             char* b, int b_size) {
    char* c = malloc(a_size + b_size);
    memcpy(c, a,            a_size);
    memcpy(c + a_size, b,   b_size);
    free(a);
    free(b);
    return c;
}

但这使用了额外的内存。是否可以使用 realloc 附加两个字节数组而不增加额外的内存 space?

喜欢：

void append(char* a, int a_size, char* b, int b_size)
...

char* a = malloc(2);
char* b = malloc(2);

void append(a, 2, b, 2);
//The size of a will be 4.

Answer 1

是的，因为如果新大小更大，realloc 将保留缓冲区的开头：

char* concat(char* a, size_t a_size,
             char* b, size_t b_size) {
    char* c = realloc(a, a_size + b_size);
    memcpy(c + a_size, b,  b_size);  // dest is after "a" data, source is b with b_size
    free(b);
    return c;
}

c 可能与 a 不同（如果系统无法将原始内存块就地连续调整为新大小），但如果是这种情况，则指向的位置a会被free（一定不能free），原来的数据会是"moved".

我的建议是警告函数的用户输入缓冲区必须使用 malloc 分配，否则会严重崩溃。

Answer 2

虽然 Jean-François Fabre 回答了上述问题，但我想指出您可以通过使用结构更好地管理此类字节数组：

typedef struct {
    size_t         max;  /* Number of chars allocated for */
    size_t         len;  /* Number of chars in use */
    unsigned char *data;
} bytearray;
#define  BYTEARRAY_INIT  { 0, 0, NULL }

void bytearray_init(bytearray *barray)
{
    barray->max  = 0;
    barray->len  = 0;
    barray->data = NULL;
}

void bytearray_free(bytearray *barray)
{
    free(barray->data);
    barray->max  = 0;
    barray->len  = 0;
    barray->data = NULL;
}

要声明空字节数组，您可以使用 bytearray myba = BYTEARRAY_INIT; 或 bytearray myba; bytearray_init(&myba);。两者是等价的

当你不再需要数组时，调用bytearray_free(&myba);。请注意，free(NULL) 是安全的，什么都不做，因此释放已初始化但未使用的 bytearray 是完全安全的。

追加到 bytearray:

int bytearray_append(bytearray *barray, const void *from, const size_t size)
{
    if (barray->len + size > barray->max) {
        const size_t  len = barray->len + size;
        size_t        max;
        void         *data;

        /* Example policy: */
        if (len < 8)
            max = 8; /* At least 8 chars, */
        else
        if (len < 4194304)
            max = (3*len) / 2;  /* grow by 50% up to 4,194,304 bytes, */
        else
            max = (len | 2097151) + 2097153 - 24; /* then pad to next multiple of 2,097,152 sans 24 bytes. */

        data = realloc(barray->data, max);
        if (!data) {
            /* Not enough memory available. Old data is still valid. */
            return -1;
        }

        barray->max  = max;
        barray->data = data;
    }

    /* Copy appended data; we know there is room now. */
    memmove(barray->data + barray->len, from, size);
    barray->len += size;

    return 0;
}

由于此函数至少在理论上可以重新分配内存失败，因此如果成功，它将 return 0，如果无法重新分配足够的内存，它将非零。

不需要 malloc() 调用，因为 realloc(NULL, size) 完全等同于 malloc(size)。

"growth policy" 是一个很有争议的问题。你可以只做 max = barray->len + size，并完成它。然而，动态内存管理功能相对较慢，所以在实践中，我们不想为每个小的加法调用realloc()。

上述政策试图做得更好，但又不太激进：它总是分配至少 8 个字符，即使需要更少的字符也是如此。最多4,194,304个字符，额外分配50%。在此之上，它将分配大小四舍五入为 2,097,152 的下一个倍数并减去 24。这背后的推理很复杂，但它更多的是为了说明和理解，而不是其他任何东西；它绝对不是 "this is best, and this is what you should do too"。该策略确保每个字节数组最多分配 4,194,304 = 2²² 个未使用的字符。但是，2,097,152 = 2²¹ 是 AMD64 (x86-64) 上大页面的大小，并且是基本上所有体系结构上本机页面大小的二次幂。它也足够大，可以在基本上所有这样做的架构上从所谓的 sbrk() 分配切换到内存映射。这意味着如此巨大的分配为每个分配使用堆的单独部分，而未使用的部分通常只是虚拟内存，在访问之前不一定由任何 RAM 支持。因此，此策略 倾向于 在大多数体系结构上对非常短的字节数组和非常长的字节数组都能很好地工作。

当然，如果您知道（或测量！）典型工作负载中字节数组的典型大小，您可以为此优化增长策略，并变得更好结果。

最后，它使用 memmove() 而不是 memcpy()，以防万一有人希望重复同一字节数组的一部分：memcpy() 仅在源和目标区域有效不要重叠； memmove() 即使在那种情况下也有效。

当使用更高级的数据结构（如哈希表）时，上述结构的变体通常很有用。（也就是说，这在您有很多空字节数组的情况下要好得多。）

数据不是指向数据的指针，而是结构本身的一部分，作为 C99 灵活数组成员：

typedef struct {
    size_t         max;
    size_t         len;
    unsigned char  data[];
} bytearray;

您不能声明字节数组本身（即 bytearray myba; 不起作用）；你总是声明一个指针到这样的字节数组：bytearray *myba = NULL;。指针为 NULL 只是被视为与空字节数组相同。

特别是，要查看这样的数组有多少 data 项，您可以使用访问函数（也定义在与数据结构相同的头文件中），而不是 myba.len：

static inline size_t  bytearray_len(bytearray *const barray)
{
    return (barray) ? barray->len : 0;
}

static inline size_t  bytearray_max(bytearray *const barray)
{
    return (barray) ? barray->max : 0;
}

(expression) ? (if-true) : (if-false)是一个三元运算符。在这种情况下，第一个函数完全等同于

static inline size_t  bytearray_len(bytearray *const barray)
{
    if (barray)
        return barray->len;
    else
        return 0;
}

如果您对 bytearray *const barray 感到疑惑，请记住指针声明是从右向左读取的，* 为 "a pointer to"。所以，它只是意味着 barray 是常量，一个指向字节数组的指针。也就是说，我们可以改变它指向的数据，但我们不会改变指针本身。编译器通常可以自己检测到这些东西，但这可能会有所帮助；然而，要点是提醒我们人类程序员指针本身不能被改变。（此类更改仅在函数本身内可见。）

由于此类数组经常需要调整大小，调整大小通常放在单独的辅助函数中：

bytearray *bytearray_resize(bytearray *const barray, const size_t len)
{
    bytearray *temp;

    if (!len) {
        free(barray);
        errno = 0;
        return NULL;
    }

    if (!barray) {
        temp = malloc(sizeof (bytearray) + len * sizeof barray->data[0]);
        if (!temp) {
            errno = ENOMEM;
            return NULL;
        }

        temp->max = len;
        temp->len = 0;
        return temp;
    }

    if (barray->len > len)
        barray->len = len;

    if (barray->max == len)
        return barray;

    temp = realloc(barray, sizeof (bytearray) + len * sizeof barray->data[0]);
    if (!temp) {
        free(barray);
        errno = ENOMEM;
        return NULL;
    }

    temp->max = len;
    return temp;
}

errno = 0 在那里做什么？这个想法是因为 resizing/reallocating 一个字节数组可能会改变指针，所以我们 return 新的。如果分配失败，我们 return NULL 和 errno == ENOMEM，就像 malloc()/realloc() 一样。然而，由于所需的新长度为零，这通过释放旧字节数组（如果有）和 returns NULL 来节省内存。但由于这不是错误，我们将 errno 设置为零，以便调用者更容易检查是否发生错误。（如果函数 returns NULL，请检查 errno。如果 errno 非零，则发生错误；您可以使用 strerror(errno) 来获取描述性错误消息.)

您可能还注意到了 sizeof barray->data[0]，即使在 barray 为 NULL 时也会使用。这没关系，因为 sizeof 不是一个函数，而是一个运算符：它根本不访问右侧，它只计算右侧所指事物的大小。（只有当正确的大小是类型时才需要使用括号。）这种形式很好，因为它允许程序员更改 data 成员的类型，而无需更改任何其他代码。

要将数据追加到这样的字节数组，我们可能希望能够指定我们是否预期会进一步追加到同一数组，或者这是否可能是最后一次追加，以便仅准确需要的内存量是需要的。为简单起见，我将只在此处实施精确尺寸版本。请注意，此函数 return 是指向（修改后的）字节数组的指针：

bytearray *bytearray_append(bytearray *barray,
                            const void *from, const size_t size,
                            int exact)
{
    size_t  len = bytearray_len(barray) + size;

    if (exact) {
        barray = bytearray_resize(barray, len);
        if (!barray)
            return NULL; /* errno already set by bytearray_resize(). */

    } else
    if (bytearray_max(barray) < len) {            

        if (!exact) {

            /* Apply growth policy */
            if (len < 8)
                len = 8;
            else
            if (len < 4194304)
                len = (3 * len) / 2;
            else
                len = (len | 2097151) + 2097153 - 24;
        }

        barray = bytearray_resize(barray, len);
        if (!barray)
            return NULL; /* errno already set by the bytearray_resize() call */
    }

    if (size) {
        memmove(barray->data + barray->len, from, size);
        barray->len += size;
    }

    return barray;
}

这一次，我们声明了bytearray *barray，因为我们改变了函数中barray指向的位置。如果第四个参数 final 非零，则生成的字节数组恰好是所需的大小；否则应用增长政策。

如何在 C 中连接字节数组

How to concat byte arrays in C

c

memory-management

memcpy