Relocation erreur

Question

#include <stdio.h> 

#define MAX 1000000 

int dp[MAX]; 
int P[MAX], C[MAX], K[MAX], child[MAX][1000], index[MAX]; 
int mod = 1000000007; 

void dfs(int i) { 
    int j = 1; 
    while (j <= index[i]) { 
     dfs(child[i][j]); 
     if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1)) 
      dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod; 
     ++j; 
    } 
} 

int main() { 
    int T, N, X, i, j; 
    scanf("%d", &T); 
    while (T--) { 
     scanf("%d%d", &N, &X); 

     for (i = 0; i < N; ++i) 
      index[i] = 0; 

     for (i = 1; i < N; ++i) { 
      scanf("%d", &P[i]); 
      child[P[i]][++index[P[i]]] = i; 
     } 
     for (i = 0; i < N; ++i) 
      scanf("%d", &C[i]); 
     for (i = 0; i < N; ++i) { 
      scanf("%d", &K[i]); 
      if (K[i]) 
       dp[i] = 0; 
      else 
       dp[i] = 1; 
     } 
     dfs(0); 
     for (i = 0; i < N; ++i) 
      printf("%d\n", dp[i]); 
    } 
    return 0; 
} 

Quand je compilé le code ci-dessus, je me suis l'erreur suivante:

In function `dfs': 
(.text+0xa): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x3b): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x4f): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x56): relocation truncated to fit: R_X86_64_32S against symbol `C' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x60): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x67): relocation truncated to fit: R_X86_64_32S against symbol `K' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x74): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x84): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o 
(.text+0x97): relocation truncated to fit: R_X86_64_32S against symbol `dp' defined in COMMON section in /tmp/cc0VMXET.o 
In function `main': 
(.text.startup+0x6e): relocation truncated to fit: R_X86_64_32S against symbol `index' defined in COMMON section in /tmp/cc0VMXET.o 
(.text.startup+0xba): additional relocation overflows omitted from the output 
error: ld returned 1 exit status 

Je sais ce que cette erreur est, comment se produit-il. Je l'ai cherché dans stackoverflow, mais je ne peux pas comprendre comment le corriger. Quelqu'un peut-il me dire comment corriger mon code?

Answer 1

Vous pouvez avoir atteint une limite sur la taille des variables globales définies dans votre programme: le tableau 2D child seul a une taille de 4000000000 octets (4 milliards d'octets).

Réduisez la taille de certaines de ces variables globales ou attribuez-les à partir du tas au moment du démarrage avec calloc().

Essayez cette version, où child est allouée dans le tas:

#include <stdio.h> 
#include <stdlib.h> 

#define MAX 1000000 

int dp[MAX], P[MAX], C[MAX], K[MAX], index[MAX]; 
int (*child)[1000]; 
int mod = 1000000007; 

void dfs(int i) { 
    int j = 1; 
    while (j <= index[i]) { 
     dfs(child[i][j]); 
     if ((C[child[i][j]] == C[i]) && (K[i] - K[child[i][j]] == 1)) 
      dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod; 
     ++j; 
    } 
} 

int main(void) { 
    int T, N, X, i; 

    child = calloc(MAX, sizeof(*child)); 
    if (child == NULL) { 
     fprintf(stderr, "cannot allocate child array (%llu bytes)\n", 
       (unsigned long long)MAX * sizeof(*child)); 
     return 1; 
    } 

    scanf("%d", &T); 
    while (T--) { 
     scanf("%d%d", &N, &X); 

     for (i = 0; i < N; ++i) 
      index[i] = 0; 

     for (i = 1; i < N; ++i) { 
      scanf("%d", &P[i]); 
      child[P[i]][++index[P[i]]] = i; 
     } 
     for (i = 0; i < N; ++i) 
      scanf("%d", &C[i]); 
     for (i = 0; i < N; ++i) { 
      scanf("%d", &K[i]); 
      if (K[i]) 
       dp[i] = 0; 
      else 
       dp[i] = 1; 
     } 
     dfs(0); 
     for (i = 0; i < N; ++i) 
      printf("%d\n", dp[i]); 
    } 
    free(child); 
    return 0; 
} 

Notes:

• Vous devriez également vérifier si les valeurs lues à partir de l'entrée standard sont compatibles avec les tailles attribuées (N <= MAX et P[i] < 1000). Vous pouvez réduire MAX ou 1000 si l'allocation échoue.

• dp[i] = (dp[i] % mod + dp[child[i][j]] % mod) % mod; pourrait être simplifiée comme dp[i] = (dp[i] + dp[child[i][j]]) % mod;

Answer 2

La matrice a child10^9 éléments et chaque élément est de 4 octets, de sorte que sa taille est à peu près de 4 Go. Cependant, GCC a une limite sur la taille du segment de données et le seuil par défaut est de 2 Go.

Vous avez deux façons de résoudre ce problème:

1. Réduire la taille du tableau child
2. compilez votre programme avec l'option GCC -mcmodel=medium.

Références:

http://www.network-theory.co.uk/docs/gccintro/gccintro_65.html https://gcc.gnu.org/onlinedocs/gcc-4.2.0/gcc/i386-and-x86_002d64-Options.html