El programa ejecuta diferentes algoritmos de ordenación sobre arrays, el problema ocurre al modificar los valores dentro de un array.
Durante la ejecución primero se lanza un test para comprobar que el algoritmo ordena bien y aquí funciona, a continuación se genera una serie de vectores de diferente tamaño con valores crecientes, decrecientes y pseudoaleatorios, cuando se ejecuta la ordenación sobre estos el código falla, en ambos casos se reservo memoria dinámica para los vectores.
En dos situaciones semejantes ocurren cosas distintas, estoy un poco perdido con el porqué de que esto ocurra.
==13523== Memcheck, a memory error detector
==13523== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==13523== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==13523== Command: ../build/fusion
==13523==
==13523== error calling PR_SET_PTRACER, vgdb might block
-2, 10, 6, -9, 7, -6, -3, 6, -5, -1,
-9, -6, -5, -3, -2, -1, 6, 6, 7, 10,
- Leyendo tiempos
************************************
ALGORITMO > fusion
SITUATION > ascendente
==13523== Invalid read of size 4
==13523== at 0x109FC6: fusion (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A098: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A083: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A083: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A0C1: ord_fusion (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x108C28: leerTiempo_v (c_computacional.c:43)
==13523== Address 0x36 is not stack'd, malloc'd or (recently) free'd
==13523==
==13523==
==13523== Process terminating with default action of signal 11 (SIGSEGV)
==13523== Access not within mapped region at address 0x36
==13523== at 0x109FC6: fusion (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A098: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A083: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A083: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A06C: fusion_rec (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x10A0C1: ord_fusion (in /mnt/c/users/manuc/Desktop/Q1/Algoritmos/empiricaLT/build/fusion)
==13523== by 0x108C28: leerTiempo_v (c_computacional.c:43)
==13523== If you believe this happened as a result of a stack
==13523== overflow in your program's main thread (unlikely but
==13523== possible), you can try to increase the size of the
==13523== main thread stack using the --main-stacksize= flag.
==13523== The main thread stack size used in this run was 8388608.
==13523==
==13523== HEAP SUMMARY:
==13523== in use at exit: 2,000 bytes in 1 blocks
==13523== total heap usage: 3 allocs, 2 frees, 6,136 bytes allocated
==13523==
==13523== LEAK SUMMARY:
==13523== definitely lost: 0 bytes in 0 blocks
==13523== indirectly lost: 0 bytes in 0 blocks
==13523== possibly lost: 0 bytes in 0 blocks
==13523== still reachable: 2,000 bytes in 1 blocks
==13523== suppressed: 0 bytes in 0 blocks
==13523== Rerun with --leak-check=full to see details of leaked memory
==13523==
==13523== For counts of detected and suppressed errors, rerun with: -v
==13523== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)
Includes
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <math.h>
#include <memory.h>
#include <time.h>
Estas son las estructuras y los tipos definidos
typedef void (*typeSituationFunction)(int *v, int nargs);
typedef void (*typeAlgorithemFunction)(int *v, int nargs);
#define NUM_SITUACIONES 3
#define NUM_ALGORITMOS 1
typedef struct {
char name[256];
int isComplex;
int index;
} funcion;
#define LOG (funcion) {"log(n)",0,0}
#define N_x (funcion) {"n",0,1}
#define NxLogN (funcion) {"n*log(n)",0,2}
#define Nexp_x (funcion) {"n^$",1,3}
#define Nexp_x_LOG (funcion) {"n^$*log(n)",1,4}
typedef struct {
funcion cota;
double exp;
}cota_t;
typedef struct {
int is_under_500;
int is_anomalo;
double tiempo;
} tempos;
typedef struct {
cota_t sobre;
cota_t ajus;
cota_t sub;
typeSituationFunction func;
tempos tiempos[256];
int valN[256];
char sit_name[256];
} situacion;
typedef struct {
int ini;
int fin;
int mult;
int nTemp;
typeAlgorithemFunction func;
char alg_name[256];
situacion sList[NUM_SITUACIONES];
} algoritmo;
Esta es una de las herramientas
void inicializar_semilla() {
srand(time(NULL));
}
void aleatorio(int *v, int n) {/* se generan números pseudoaleatorio_t entre -n y +n */
int i, m=2*n+1;
for (i=0; i < n; i++)
v[i] = (rand() % m) - n;
}
void ascendente(int *v, int n) {
int i;
for (i=0; i < n; i++)
v[i] = i;
}
void descendente(int *v, int n){
int i;
for (i = 0; i < n; i++) {
v[i] = n - i - 1;
}
}
Esta es la otra
double microsegundos(){
struct timeval t;
if (gettimeofday(&t, NULL) < 0)
return 0.0;
return (t.tv_usec + t.tv_sec * 1000000.0);
}
void leerTiempo_v(algoritmo alg, situacion sit, tempos tiempos[], int *tamV){
double ta, tb, t, ti;
int k, n, i;
int *v;
typeSituationFunction ini = sit.func;
typeAlgorithemFunction ord = alg.func;
int inicio = alg.ini;
int fin = alg.fin;
int mult = alg.mult;
i = 0;
printf("ALGORITMO > %s\n",alg.alg_name);
printf("\tSITUATION > %s\n",sit.sit_name);
for (n = inicio; n <= fin; n = n * mult) {
tamV[i]=n;
v = malloc(sizeof(int) * n);
ini(v, n);
ta = microsegundos();
ord(v, n);
tb = microsegundos();
t = tb - ta;
if (t < 500) {
ta = microsegundos();
for (k = 0; k < 1000; k++) {
ini(v, n);
ord(v, n);
}
tb = microsegundos();
t = tb - ta;
ta = microsegundos();
for (k = 0; k < 1000; k++) {
ini(v, n);
}
tb = microsegundos();
ti = tb - ta;
t = (t - ti) / k;
tiempos[i] = (tempos){1,0,t};
printf("\t\t > tiempo %f \n", tiempos[i].tiempo);
} else {
tiempos[i] = (tempos){0,0,t};
printf("\t\t > tiempo %f \n", tiempos[i].tiempo);
}
i++;
free(v);
}
}
cota_t genCota(funcion func, double exp){
cota_t cota;
char *token1;
char *token2;
char aux[256];
if(func.isComplex){
cota.cota = func;
cota.exp = exp;
token1 = strtok(cota.cota.name,"$");
token2 = strtok(NULL,"$");
if(token2 != NULL) {
sprintf(aux, "%s%2.1f%s", token1, cota.exp, token2);
strcpy(cota.cota.name, aux);
} else {
sprintf(aux, "%s%2.1f", token1, cota.exp);
strcpy(cota.cota.name, aux);
}
} else {
cota.cota = func;
cota.exp = 0;
}
return cota;
}
double execute(funcion op , int n, double exp, int derivada){
if (!derivada) {
switch (op.index) {
case 0:
return log(n);
case 1:
return n;
case 2:
return n*log(n);
case 3:
return pow(n,exp);
case 4:
return pow(n,exp)*log(n);
default:
return -1;
}
} else {
switch (op.index) {
case 0:
return 1.0/n;
case 1:
return 0;
case 2:
return log(n)+(1);
case 3:
if(exp == 0)
return 1;
else
return exp*pow(n,exp-1);
case 4:
if(exp == 0)
return 1.0;
else
return (exp*pow(n,exp-1)*log(n))+(pow(n,exp)*1/n);
default:
return -1;
}
}
}
algoritmo initAlgorithem(char *name, typeAlgorithemFunction func, situacion sList[], int ini
, int mult, int fin, int nTemp){
algoritmo algoritmo;
strcpy(algoritmo.alg_name, name);
algoritmo.func = func;
algoritmo.ini = ini;
algoritmo.mult = mult;
algoritmo.fin = fin;
algoritmo.nTemp = nTemp;
memcpy(algoritmo.sList, sList, NUM_SITUACIONES * sizeof(situacion));
return algoritmo;
}
situacion initSituation(char *name, typeSituationFunction func, cota_t sobre, cota_t ajus, cota_t sub) {
situacion sit ;
strcpy(sit.sit_name, name);
sit.func = func;
sit.sobre = sobre;
sit.ajus = ajus;
sit.sub = sub;
return sit;
}
void lecturaTiempos_v(algoritmo algoritmos[]){
int i;
int j;
printf(" - Leyendo tiempos \n");
printf(" ************************************ \n");
for(i = 0; i<NUM_ALGORITMOS; i++) {
for (j = 0; j < NUM_SITUACIONES; j++) {
leerTiempo_v(algoritmos[i],
algoritmos[i].sList[j],
algoritmos[i].sList[j].tiempos,
algoritmos[i].sList[j].valN);
}
}
}
void mostrarResultados(algoritmo algoritmos[]){
int j, i, k;
int valN;
double tiempo;
for(i = 0; i < NUM_ALGORITMOS; i++) {
for (j = 0; j < NUM_SITUACIONES; j++) {
printf("\n-------------------------------------------------------------\n");
printf("\nOrdenación %s con inicialización %s\n\n", algoritmos[i].alg_name
, algoritmos[i].sList[j].sit_name);
printf(" %-10s%-15s%-15s%-15s%-15s%-7s\n", "n", "t(n)",algoritmos[i].sList[j].sobre.cota.name,
algoritmos[i].sList[j].ajus.cota.name,algoritmos[i].sList[j].sub.cota.name,"anomala");
for (k = 0; k<algoritmos[i].nTemp; k++) {
valN = algoritmos[i].sList[j].valN[k];
tiempo = algoritmos[i].sList[j].tiempos[k].tiempo;
if(algoritmos[i].sList[j].tiempos[k].is_under_500) {
printf("(*)%-10d%-15.5f%-15.8f%-15.8f%-15.8f%7d\n", valN, tiempo,
tiempo / execute(algoritmos[i].sList[j].sobre.cota, valN, algoritmos[i].sList[j].sobre.exp,0),
tiempo / execute(algoritmos[i].sList[j].ajus.cota, valN, algoritmos[i].sList[j].ajus.exp,0),
tiempo / execute(algoritmos[i].sList[j].sub.cota, valN, algoritmos[i].sList[j].sub.exp,0),
algoritmos[i].sList[j].tiempos[k].is_anomalo
);
} else {
printf(" %-10d%-15.5f%-15.8f%-15.8f%-15.8f%7d\n", valN, tiempo,
tiempo / execute(algoritmos[i].sList[j].sobre.cota, valN, algoritmos[i].sList[j].sobre.exp,0),
tiempo / execute(algoritmos[i].sList[j].ajus.cota, valN, algoritmos[i].sList[j].ajus.exp,0),
tiempo / execute(algoritmos[i].sList[j].sub.cota, valN, algoritmos[i].sList[j].sub.exp,0),
algoritmos[i].sList[j].tiempos[k].is_anomalo
);
}
}
}
}
}
Y este el algoritmo de ordenacion
void insercion (int v[], int n){
int i;
int j;
int aux;
for(i=1; i<n; i++){
aux = v[i];
j = i - 1;
while(j>=0 && v[j]>aux){
v[j+1] = v[j];
j--;
}
v[j+1] = aux;
}
}
void fusion(int *v, int Izda, int Dcha, int Ctro){
int i, j, k;
int aux[Dcha - Izda + 1];
i = Izda; j = Ctro + 1; k = Izda;
while (i <= Ctro && j <= Dcha) aux[k++] = ((v)[i] <= (v)[j]) ? (v)[i++] : (v)[j++];
while (i <= Ctro) aux[k++] = (v)[i++];
while (j <= Dcha) aux[k++] = (v)[j++];
for(k = Izda; k<=Dcha; k++) (v)[k] = aux[k];
}
void fusion_rec(int *v, int Izda, int Dcha){
int Ctro;
if(Izda + UMBRAL < Dcha){
Ctro = (Izda + Dcha) / 2;
fusion_rec(v, Izda, Ctro);
fusion_rec(v, Ctro + 1, Dcha);
fusion(v, Izda, Dcha, Ctro);
}
}
void ord_fusion(int *v, int n){
fusion_rec(v, 0, n - 1);
}
int main(int argc, char **argv)
{
inicializar_semilla();
//test(10);
situacion sList[NUM_SITUACIONES] = {
initSituation("ascendente", ascendente, genCota(Nexp_x, 1.0), genCota(Nexp_x, 1.2), genCota(Nexp_x, 1.4)),
initSituation("descendente", descendente, genCota(Nexp_x, 1.0), genCota(Nexp_x, 1.2), genCota(Nexp_x, 1.4)),
initSituation("aleatorio", aleatorio, genCota(Nexp_x, 1.0), genCota(Nexp_x, 1.2), genCota(Nexp_x, 1.4))};
algoritmo algs[NUM_ALGORITMOS] = {initAlgorithem("fusion", ord_fusion, sList, 500, 2, 30000, 6)};
lecturaTiempos_v(algs);
mostrarResultados(algs);
/* */
return 0;
}
Para compilar en Ubuntu
gcc <file_name>.c -o <binary_name> -lm
Para windows creo que no hace falta el -lm
dejo aquí el enlace git
inicio==0
? Si eso sucede el malloc no va a reservar memoria ya quesizeof(int)*0 = 0