C-树算法中内存的动态分配和重新分配

Question

我正在编程模拟的树算法。每个处理器都有自己的树。在程序中的特定点，我必须检查特定树中不属于那里的粒子。我收集它们并将其发送到正确的树/处理器。

我的问题是关于我收集粒子并将它们放入动态大小列表的过程。由于我必须发送到另一棵树的粒子数不是恒定的，所以我必须使用动态数组。

我实施了一个应该发生所有这些的小程序。但它仅适用于小N。但对于小N，有时会出现错误。重新分配过程可能不起作用。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DIM 2
// Struct for particles
typedef struct {
    double m;
    double x[DIM];
    int id;
} Particle;
// Structs for lists I want to fill with particle data
typedef struct {
    double **list; // every processor has its own list
    int *counter; // length of the list
} ParticleList;
void generateParticles(Particle *p, int N);
void buildList(Particle *p, ParticleList *plist, int numprocs, int N);
int main() {
    time_t t;
    srand((unsigned)time(&t));
    // Generate and print data
    int N = 3;
    Particle *p = (Particle*)malloc(N * sizeof(*p));
    generateParticles(p, N);
    for (int i = 0; i < N; i++) {
        printf("id: %d m: %lf x: %lf %lfn", p[i].id, p[i].m, p[i].x[0], p[i].x[1]);
    }
    // Fill lists
    int numprocs = 4;
    ParticleList plist;
    plist.list = malloc(sizeof(double*) * numprocs);
    // At the beginning every list should be of size zero
    // Therefore I initialize lists for every processor of size zero
    for (int k = 0; k < numprocs; k++)
        plist.list[k] = malloc(sizeof(double) * 0);
    plist.counter = calloc(numprocs, sizeof(int));
    // Fill the lists randomly
    buildList(p, &plist, numprocs, N);
    for (int k = 0; k < numprocs; k++) {
        printf("%dn", plist.counter[k]);
        for (int c = 0; c < (DIM * plist.counter[k]); c++) {
            printf("%lf ", plist.list[k][c]);
        }
        printf("n");
    }
    free(p);
    return 0;
}
void buildList(Particle *p, ParticleList *plist, int numprocs, int N) {
    for (int k = 0; k < numprocs; k++) {
        for (int i = 0; i < N; i++) {
            if (rand() % 10 < 3) { // randomly choose particles to fill the list
                plist->counter[k]++;
                // Here might be the problem?
                plist->list[k] = realloc(plist->list[k], DIM * sizeof(plist->list[k]));
                for (int j = plist->counter[k]; j < (plist->counter[k] + DIM); j++)
                    plist->list[k][j] = p[i].x[j];
            }
        }
    }
}
void generateParticles(Particle *p, int N) {
    for (int i = 0; i < N; i++) {
        for (int d = 0; d < DIM; d++) {
            p[i].x[d] = rand() % 10;
        }
        p[i].m = rand() % 10;
        p[i].id = i;
    }
}

问题可能在此行中：plist->list[k] = realloc(plist->list[k], DIM * sizeof(plist->list[k]));

我有以下错误：

*** Error in `./append_struct': realloc(): invalid next size: 0x00000000015df540 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fc931b3e7e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x834aa)[0x7fc931b4a4aa]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x179)[0x7fc931b4b839]
./append_struct[0x400b5e]
./append_struct[0x4009bf]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7fc931ae7830]
./append_struct[0x4007b9]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:02 3670408                            /home/exp/append_struct
00601000-00602000 r--p 00001000 08:02 3670408                            /home/exp/append_struct
00602000-00603000 rw-p 00002000 08:02 3670408                            /home/exp/append_struct
015df000-01600000 rw-p 00000000 00:00 0                                  [heap]
7fc92c000000-7fc92c021000 rw-p 00000000 00:00 0 
7fc92c021000-7fc930000000 ---p 00000000 00:00 0 
7fc9318b1000-7fc9318c7000 r-xp 00000000 08:02 4985364                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc9318c7000-7fc931ac6000 ---p 00016000 08:02 4985364                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc931ac6000-7fc931ac7000 rw-p 00015000 08:02 4985364                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fc931ac7000-7fc931c87000 r-xp 00000000 08:02 4994073                    /lib/x86_64-linux-gnu/libc-2.23.so
7fc931c87000-7fc931e87000 ---p 001c0000 08:02 4994073                    /lib/x86_64-linux-gnu/libc-2.23.so
7fc931e87000-7fc931e8b000 r--p 001c0000 08:02 4994073                    /lib/x86_64-linux-gnu/libc-2.23.so
7fc931e8b000-7fc931e8d000 rw-p 001c4000 08:02 4994073                    /lib/x86_64-linux-gnu/libc-2.23.so
7fc931e8d000-7fc931e91000 rw-p 00000000 00:00 0 
7fc931e91000-7fc931ea9000 r-xp 00000000 08:02 4994056                    /lib/x86_64-linux-gnu/libpthread-2.23.so
7fc931ea9000-7fc9320a8000 ---p 00018000 08:02 4994056                    /lib/x86_64-linux-gnu/libpthread-2.23.so
7fc9320a8000-7fc9320a9000 r--p 00017000 08:02 4994056                    /lib/x86_64-linux-gnu/libpthread-2.23.so
7fc9320a9000-7fc9320aa000 rw-p 00018000 08:02 4994056                    /lib/x86_64-linux-gnu/libpthread-2.23.so
7fc9320aa000-7fc9320ae000 rw-p 00000000 00:00 0 
7fc9320ae000-7fc9320d4000 r-xp 00000000 08:02 4994051                    /lib/x86_64-linux-gnu/ld-2.23.so
7fc9322b5000-7fc9322b8000 rw-p 00000000 00:00 0 
7fc9322d0000-7fc9322d3000 rw-p 00000000 00:00 0 
7fc9322d3000-7fc9322d4000 r--p 00025000 08:02 4994051                    /lib/x86_64-linux-gnu/ld-2.23.so
7fc9322d4000-7fc9322d5000 rw-p 00026000 08:02 4994051                    /lib/x86_64-linux-gnu/ld-2.23.so
7fc9322d5000-7fc9322d6000 rw-p 00000000 00:00 0 
7ffc92bdb000-7ffc92bfc000 rw-p 00000000 00:00 0                          [stack]
7ffc92bfc000-7ffc92bfe000 r--p 00000000 00:00 0                          [vvar]
7ffc92bfe000-7ffc92c00000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)

编辑：

我的示例代码只是一个粗略的草图，我认为自己是C的初学者。这可能是我的问题并不清楚的原因。在我的实际代码中，我正在用粒子(2D中的Quadtree和3D中的Octree(建立一个树结构。每个处理器都有其他颗粒。我使用递归树路中的树中的位置来识别错误的粒子，然后将它们发送到其他处理器，因为我想要紧凑的树结构。为此，我必须将错误的粒子放入列表中，然后我可以将其传递到MPI库，以将数据发送给其他处理器。粒子的数量通常大于处理器数量(n>> numproc(。

Answer 1

我不完全理解您的推理，它可能会用于优化计算速度，但是您需要有一个工作程序来考虑这样做。

另外，您用于将粒子分配给处理器的算法不起作用。正如书写的那样，粒子的机会不分配到任何列表中的70％。

在您对粒子列表的声明中：

typedef struct {
    double **list; // a list of double* ?  It's going to be hard to find which double
                   // belongs to which Particle, this makes your app more confusing
                   // and much harder to write than it ought to.
    int *counter;  // a length of lengths?  what's its length?
} ParticleList;

您应该考虑这样做。这可能会更好，我省略了对Calloc((结果检查错误的错误检查，您应该始终这样做。我选择了Calloc((，因为它清除了它分配的内存。

typedef struct {
  struct Particle* next;
  double m;
  double x[DIM];
  int id;
} Particle;
typedef struct Particle* ParticleList;
// this should look familiar to you.
void insert_particle(ParticleList* list, struct Particle* part)
{
  part->next = NULL;  // just to make sure we don't introduce bugs here
  if (*list == NULL)
  {
    *list = part;
    return;
  }
  struct Particle* p = *list;
  while (p)
  {
    if (p->next == NULL)
    {
      p->next = part
      return;
    }
    p = p->next;
  }
}
int main()
{
   int i;
   int numProcs = 4;
   int assigned_proc;
   int N = 3;  // less particles than threads?  This does not sound right...
   // ...
   // allocate empty lists and all particles.
   ParticleList* procparts = calloc(numprocs, sizeof(ParticleList));
   struct Particle* particles = calloc(N, sizeof(struct Particle));
   for (i = 0; i < N; ++i)                        // for each particle ...
   {
     // initialize particle location...
     particles[i].id = i;
     // ... and x[]...
     assigned_proc = rand() % numprocs;           // pick a processor...
     insert_particle(&procparts[assigned_proc], &particles[i]);
   }
   // ...
}

请注意，执行过程中此实现不需要对Realloc((的任何调用。

一旦您的应用使用"普通"线程工作，将其兼容的MPI将变得更加简单。