C：通过结构数组使用 realloc 实现高性能

Question

我正在使用 realloc 调整包含 3 个点 x、y 和 z 的结构数组的大小。此结构封装在另一个结构中，该结构包含数组、数组的长度和一个 "reserved" 值，该值用于预分配策略，以便在明显将附加更多点结构时实现更快的性能到结构数组。
我正在使用如下所示的 Makefile 进行编译：

CFLAGS = -g -Wall
LIBS = -lm

default: echo "You must specify a target, e.g. file1, file2" 


file2:
    gcc $(CFLAGS) -o $@ test.c file2.c $(LIBS)

我有一个初始化空数组结构的函数，一个是将数组重置为空并释放任何动态分配的内存，一个是将一个点附加到数组的末尾，另一个是删除指定的点指数值。

我收到两个无法找到原因的错误。一个是我的代码 returns 一个非零状态代码 1，另一个是当我附加几千点时，长度似乎偏离了一个。
我让 append 函数完成所有工作，但如果我应该在初始化时分配动态内存，请告诉我。我很确定我的重置和删除功能正在按预期工作。也请看一下 append。

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <assert.h>

typedef struct point
{
  int x, y, z;
} point_t;

typedef struct 
{
  // number of points in the array
  size_t len;

  // pointer to an array of point_t structs

  point_t* points;


  size_t reserved; 

} point_array_t;


void point_array_initial( point_array_t* pa )
{
    assert(pa);
    pa->len = 0;
    pa->reserved = 0;
    pa->points=NULL;
}   


void point_array_reset( point_array_t* pa )
{//just free the array and set pa to NULL

    assert(pa);

    pa->points = memset(pa->points, 0, sizeof(point_t)*(pa->len));
    pa->len = 0;
    pa->reserved=0;
    free(pa->points);
    pa->points=NULL;
}


int point_array_append( point_array_t* pa, point_t* p )
{

    assert(pa);
    assert(p);
    if(pa == NULL)//something wrong with intialization or reset
    {
        return 1;
    }
    if(p == NULL)//nothing to append
    {
        return 1;
    }
    //append the first point 
    if(pa->len == 0)
    {
        pa->len=1;
        pa->reserved=pa->len*2;
        pa->points = malloc(sizeof(point_t)* (pa->reserved));
        if(pa->points == NULL)//malloc failed
        {
            return 1;
        }

        pa->points[pa->len-1].x = p->x;
        pa->points[pa->len-1].y = p->y;
        pa->points[pa->len-1].z = p->z;
    }

    if (pa->reserved > pa->len )
    {
        pa->len+=1;
        pa->points[pa->len-1].x = p->x;//insert at index 0
        pa->points[pa->len-1].y = p->y;
        pa->points[pa->len-1].z = p->z;

    }
    //when we run out of space in reserved (len has caught up)
    else if(pa->reserved == pa->len)
    {
        pa->len+=1;
        pa->reserved=pa->len*2;
        pa->points=realloc(pa->points, sizeof(point_t)*(pa->reserved));//doubling size of array
        pa->points[pa->len-1].x = p->x;//TODO: change formula to find insertion point
        pa->points[pa->len-1].y = p->y;
        pa->points[pa->len-1].z = p->z;
    }



    return 0;
}


int point_array_remove( point_array_t* pa, unsigned int i )
{

    assert(pa);
    if (i >= pa->len)//out of bounds
    {
        return 1;
    }   

    if(pa->len==0)//0 elements trying to remove from empty array
    {
        //pa->len=0;
        //free(pa->points);
        //pa->points=NULL; 
        return 1;
    }
    else if(pa->len ==1)//remove only element
    {
        pa->len-=1;//no copying required, just shorten
        pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));
        //free(pa->points);
        //pa->points=NULL;
    }
    else//array size is longer than 1 or 0
    {
        pa->points[i].x = pa->points[pa->len-1].x;
        pa->points[i].y = pa->points[pa->len-1].y;
        pa->points[i].z = pa->points[pa->len-1].z;  
        pa->len-= 1;//shorten array size
        pa->reserved = pa->len*2;
        pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));//could reallocate for reserve here to increase speed.
    }   

    return 0;
}

Answer 1

追加函数中 if(pa->len == 0) 主体后缺少 else：第一个点追加了两次。

请注意，您在此函数中的特殊情况太多。可以简化为一次测试：如果数组太小，重新分配它，并附加点。

可以进行其他简化：

测试if (pa->len == 0)//0 elements trying to remove from empty array与前一个测试是多余的。
利用realloc(NULL, size)相当于malloc(size)，realloc(p, 0)相当于free(p)，free(NULL)就OK .
注意 realloc() 可能会失败，即使在缩小块时也是如此。
你应该只在数组变得太稀疏时收缩数组，而不是每次调用 point_array_remove。

这是一个更简单的版本：

#include <assert.h>
#include <stdlib.h>

typedef struct point {
    int x, y, z;
} point_t;

typedef struct {
    size_t len;      // number of valid points in the array
    size_t reserved; // allocated number of points in the array
    point_t *points; // pointer to an array of point_t structs
} point_array_t;

void point_array_initial(point_array_t *pa) {
    assert(pa);
    pa->len = 0;
    pa->reserved = 0;
    pa->points = NULL;
}

void point_array_reset(point_array_t *pa) {
    assert(pa);
    free(pa->points);
    pa->len = 0;
    pa->reserved = 0;
    pa->points = NULL;
}

int point_array_append(point_array_t *pa, const point_t *p) {
    point_t *points;

    assert(pa);
    assert(p);
    // no need to test pa nor p, asserts would already abort
    points = pa->points;
    if (pa->len >= pa->reserved || points == NULL) {
        // reallocate of points array is too small
        size_t newsize = pa->reserved;
        if (newsize < pa->len)
            newsize = pa->len;
        if (newsize < 1)
            newsize = 1;
        newsize += newsize;
        points = realloc(points, newsize * sizeof(*points);
        if (points == NULL)
            return 1;
        pa->points = points;
        pa->reserved = newsize;
    }
    // append point structure
    points[pa->len++] = *p;
    return 0;
}

int point_array_remove(point_array_t *pa, unsigned int i) {
    point_t *points;

    assert(pa);
    if (i >= pa->len || pa->points == NULL) { //out of bounds or invalid array
        return 1;
    }
    if (pa->len - i > 1) {
        memmove(&pa->points + i, &pa->points + i + 1,
                sizeof(*pa->points) * (pa->len - i - 1));
    }
    pa->len--;
    if (pa->reserved >= pa->len * 3) {
        size_t newsize = pa->len * 2;
        // shorten the array with care.
        // note that the array will be freed when it becomes empty
        // no special case needed.
        points = realloc(pa->points, sizeof(*points) * newsize);
        if (points != NULL) {
            pa->points = points;
            pa->reserved = newsize;
        }
    }
    return 0;
}

Answer 2

除了 chqrlie 指出的错误之外，这里还有一些关于您的代码的额外想法。

对于非调试构建，CFLAGS 的更好选择是

-Wall -Wextra -O3

添加 -pedantic 以获得一些额外的警告，您可以将 -Ofast 与 gcc >= 4.6 一起使用。

从不 realloc 指针本身，如果 realloc 失败，返回 NULL 并且您丢失了对原始内存块的引用 - 并造成内存泄漏，因为您块的起始地址不再为 free。在验证 realloc 成功之前，不要递增 len 或 reserved。相反，始终使用临时指针并仅在成功时递增值，例如

else if(pa->reserved == pa->len)
{
    void *tmp = realloc(pa->points, sizeof(point_t)*(pa->len + 1) * 2);
    if (!tmp) {
        /* handle error - exit or return */
    }
    pa->points = tmp;
    pa->len+=1;
    pa->reserved=pa->len*2;
}

如果您只是想将数组缩短一个，那么下面看起来像是一个问题：

else if(pa->len ==1)//remove only element
{
    pa->len-=1;//no copying required, just shorten
    pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));
    //free(pa->points);
    //pa->points=NULL;
}
else//array size is longer than 1 or 0
{
    pa->points[i].x = pa->points[pa->len-1].x;
    pa->points[i].y = pa->points[pa->len-1].y;
    pa->points[i].z = pa->points[pa->len-1].z;  
    pa->len-= 1;//shorten array size
    pa->reserved = pa->len*2;
    pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));//could reallocate for reserve here to increase speed.
}

在上面的 else 中，您将前一点分配给最后一点，然后砍掉最后一点——要么我不明白您想要完成什么，要么它没有按照您的想法进行这是。在任何一种情况下，除非你有一些令人信服的理由想要 realloc 将数组缩短一个（我会等到所有 add/remove 操作完成然后在 [=20= 上调用最终的重新分配] 元素来准确调整您的内存使用量）。相反，我会将上面的全部内容替换为：

else
    pa->len -= 1;

不用管别的了。您实际上忽略了最后一行中的数据——这不会造成任何伤害，直到您的下一次添加覆盖这些值。

C：通过结构数组使用 realloc 实现高性能

C: using realloc for high performance with an array of structs

c

structure

dynamic

realloc