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

问题描述 投票：0回答：2

我正在使用 realloc 来调整包含 3 个点 x、y 和 z 的结构数组的大小。 该结构封装在另一个结构中，该结构包含数组、数组的长度和“保留”值，该值用于预分配策略，以便在显然将更多的点结构附加到结构时获得更快的性能。结构体数组。
我正在使用如下所示的 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)

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

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

#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;
}
c dynamic structure realloc
2个回答
1
投票
追加函数中

else

 主体后面缺少 
if(pa->len == 0)
：第一个点被追加两次。

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

还可以进行其他简化：

  • 测试

    if (pa->len == 0)//0 elements trying to remove from empty array
    与上一个测试是多余的。

  • 利用

    realloc(NULL, size)
    相当于
    malloc(size)
    ，
    realloc(p, 0)
    相当于
    free(p)
    ，
    free(NULL)
    就可以了。

  • 请注意，

    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;
}
1
投票

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

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

-Wall -Wextra -O3

添加 

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

永远不要 

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

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
将数组缩短一个（我会等到所有添加/删除操作完成，然后对 
len
元素调用最终的重新分配以精确调整您的数组大小）内存使用）。相反，我会将上面的全部内容替换为：

else
    pa->len -= 1;

无需搞乱其他任何事情。您实际上忽略了最后一行中的数据 - 这不会伤害任何东西，直到您的下一个添加覆盖这些值。

最新问题
© www.soinside.com 2019 - 2025. All rights reserved.