c-在对内存中的值进行排序时进行重新分配的最有效方法

Question

我分配了32字节的连续内存(使用malloc(来保存八个连续的32位值。在这段内存上执行了某些任务后，值如下所示：

+---+---+---+---+---+---+---+---+
| d |   |   |   |   | a | b | c |
+---+---+---+---+---+---+---+---+

注意到有个洞了吗？不再需要这些值，可以忽略这些值。该洞将始终是主分配的一半大小，并且始终是连续的。

在将值重新排序为这样的同时，重新分配这段内存的最有效、最快的方法是什么？

+---+---+---+---+
| a | b | c | d |
+---+---+---+---+

任何建议都会很有帮助。

Answer 1

我会编写尽可能简单的代码，使编译器易于优化。一个好的编译器(甚至是一个坏的编译器，TBH(比我有更好的机会为使用中的平台提供最快的程序集

因此，例如(为简洁起见，已排除malloc/realloc错误检查(：

uint32_t *buf = malloc(32);
// your operations here
buf[3] = buf[0];
buf[0] = buf[5];
buf[1] = buf[6];
buf[2] = buf[7];
// optional obviously, waste of time if that 16 bytes isn't a dealbreaker
buf = realloc(buf, 16);     

Answer 2

uint32_t *values;
if(offset == 0)
{
    values[0] = values[4];
    values[1] = values[5];
    values[2] = values[6];
    values[3] = values[7];
}
else if(offset == 1)
{
    values[3] = values[0];
    values[0] = values[5];
    values[1] = values[6];
    values[2] = values[7];
}
else if(offset == 2)
{
    values[2] = values[0];
    values[3] = values[1];
    values[0] = values[6];
    values[1] = values[7];
}
else if(offset == 3)
{
    values[3] = values[2];
    values[2] = values[1];
    values[1] = values[0];
    values[0] = values[7];
}

我知道，一个非常"愚蠢"的解决方案
但包含多达一个带有可变参数的memmove的所有内容
对我来说，在速度方面(以及模…嗯，是的。(

Answer 3

根据mafso的回答，我最终使用了一个memmove和一个memcpy来使用此解决方案。

开始：

+---+---+---+---+---+---+---+---+
| d |   |   |   |   | a | b | c |
+---+---+---+---+---+---+---+---+

memmove右边的第一个元素：

+---+---+---+---+---+---+---+---+
| d |   |   | d |   | a | b | c |
+---+---+---+---+---+---+---+---+

memcpy从结束元素到开始元素：

+---+---+---+---+---+---+---+---+
| a | b | c | d |   | a | b | c |
+---+---+---+---+---+---+---+---+

然后realloc缩短：

+---+---+---+---+
| a | b | c | d |
+---+---+---+---+

简单，轮廓非常快。

Answer 4

假设整个数组中有偶数个32位值(8是偶数(，则如下所示：

#include <string.h>
#include <stdint.h>
#include <stdio.h>
void re_sort_buffer(uint32_t *arr, size_t head_len, size_t hole_len, size_t tail_len) {
    memmove(arr+hole_len-head_len, arr, head_len*sizeof *arr); // see below
    memcpy(arr, arr+head_len+hole_len, tail_len*sizeof *arr);
}
int main(void) {
    uint32_t test[] = { 'b', 'c', 'd', '*', '*', '*', '*', 'a' };
    re_sort_buffer(test, 3, 4, 1);
    for(size_t i=0; i < 3+4+1; ++i) printf("'%c' ", test[i]);
    putchar('n');
}

输出：

'a' 'b' 'c' 'd' '*' '*' '*' 'a' 

您可能需要对re_sort_buffer的一些参数进行硬编码或传递不同的参数等。

如果hole_len-head_len≥head_len(等效地，如果hole_len÷2(在您的情况下为2(≥head_len(，则可以通过使用memcpy来避免使用memmove；否则，我看不出更好的办法了。在这种情况下，也许最好使用临时缓冲区；我认为，进一步的一切都将是针对特定平台的。

HTH