search

PI-ITBA / 2024_01

9 stars 0 forks source link

moveToFrontADT, EJ2 2019 RECU 1 CUATRI #382

Closed sratto0 closed 1 week ago

sratto0 commented 1 week ago

Buenas tardes, perdon las molestias pero queria saber si me podian ayudar. El codigo me pasa el assert pero me tira que tiene memory leaks en la funcion add(especificamente cuando creo la lista aux y hago el malloc).Me fije con las soluciones de la catedra pero no logro encontrar el problema.Desde ya muchas gracias

typedef struct node{
    elemType elem;
    struct node *tail;
}TNode;

typedef TNode*TList;

typedef struct moveToFrontCDT{
    TList first;
    TList iter;
    TList last;
    size_t cant_elems;
    compare cmp;
}moveToFrontCDT;

moveToFrontADT newMoveToFront(compare cmp){
    moveToFrontADT new=calloc(1, sizeof(moveToFrontCDT));
    new->cmp=cmp;
    return new;
}

static int exists(TList l, elemType elem, compare cmp){
    if(l==NULL || cmp(l->elem, elem)>0){
        return 0;
    }
    if(cmp(l->elem, elem)==0)
        return 1;
    return exists(l->tail, elem, cmp);
}

unsigned int add(moveToFrontADT moveToFront, elemType elem){
    if(exists(moveToFront->first, elem, moveToFront->cmp))
        return 0;
    TList aux=malloc(sizeof(TNode));
    aux->elem=elem;
    aux->tail=NULL;
    if(moveToFront->cant_elems==0)
        moveToFront->first=aux;
    else{
        moveToFront->last->tail=aux;
    }
    moveToFront->last=aux;
    moveToFront->cant_elems++;
    return 1;
}

unsigned int size(moveToFrontADT moveToFront){
    return moveToFront->cant_elems;
}

void toBegin(moveToFrontADT moveToFront){
    moveToFront->iter=moveToFront->first;
}

int hasNext(moveToFrontADT moveToFront){
    return moveToFront->iter!=NULL;
}

elemType next(moveToFrontADT moveToFront){
    if(!hasNext(moveToFront))
        exit(1);
    elemType ans=moveToFront->iter->elem;
    moveToFront->iter=moveToFront->iter->tail;
    return ans;
}

static TList searchAndMove(TList l, elemType elem, compare cmp, TList *found){
    if(l==NULL ){
        *found=NULL;
        return NULL;
    }
    if(cmp(l->elem, elem)==0){
        *found=l;
        return l->tail;
    }
    l->tail=searchAndMove(l->tail, elem, cmp, found);
    return l;
}

elemType * get(moveToFrontADT moveToFront, elemType elem){
    TList found;
    moveToFront->first=searchAndMove(moveToFront->first, elem, moveToFront->cmp, &found);
    if(found!=NULL){
        found->tail=moveToFront->first;
        moveToFront->first=found;
        elemType *ans=malloc(sizeof(elemType));
        *ans=found->elem;
        return ans;
    }
    return NULL;
}

static void freeRec(TList l){
    if(l==NULL)
        return ;
    free(l->tail);
    free(l);
}

void freeMoveToFront(moveToFrontADT moveToFront){
    freeRec(moveToFront->first);
    free(moveToFront);
}

static int compareStruct (elemType e1, elemType e2) {
    return e1.code - e2.code;
}

int 
main(void) {
    moveToFrontADT p = newMoveToFront(compareStruct);

    elemType aux = {1, "uno"};
    assert(add(p, aux)==1);
    strcpy(aux.name, "dos");
    assert(add(p, aux)==0);
    aux.code = 2;
    assert(add(p, aux)==1);
    aux.code = 3;
    strcpy(aux.name, "tres");
    assert(add(p, aux)==1);
    aux.code = 4;
    strcpy(aux.name, "cuatro");
    assert(add(p, aux)==1);
    toBegin(p);

    while (hasNext(p)) {
       aux = next(p);
       printf("%d %s ", aux.code, aux.name);
    }
    putchar('\n'); 

    aux.code = 5;
    elemType * q = get(p, aux); 
    assert(q==NULL);

    aux.code = 3;
    q = get(p, aux);
    printf("%d %s\n", q->code, q->name);    
    assert(q->code==3);
    assert(strcmp(q->name, "tres")==0);
    free(q);

    // Volvemos a pedir el 3, que ahora debe estar al principio
    aux.code = 3;
    q = get(p, aux);
    printf("%d %s\n", q->code, q->name);    
    assert(q->code==3);
    assert(strcmp(q->name, "tres")==0);
    free(q);

    toBegin(p);
    printf("Debe imprimir 3 tres 1 uno 2 dos 4 cuatro\n");
    int vec[] = {3, 1, 2, 4};
    int i=0;
    while (hasNext(p)) {
       aux = next(p);
       printf("%d %s ", aux.code, aux.name);
       assert(aux.code == vec[i++]);
    }
    putchar('\n');

    aux.code = 5;
    strcpy(aux.name, "cinco");
    assert(add(p, aux)==1);
    q = get(p, aux);
    assert(q->code==5);
    assert(strcmp(q->name, "cinco")==0);
    free(q);
    toBegin(p);
    assert(next(p).code == 5);
    assert(next(p).code == 3);

    freeMoveToFront(p);
    puts("OK primera parte!"); 

    // Insertamos miles de elementos
    int dim=50000;
    p = newMoveToFront(compareStruct);
    for(int i=1; i <= dim; i++) {
        elemType aux = {i, "foo"};
        assert(add(p, aux));
    }
    assert(size(p)==dim);
    aux.code = dim + 1;
    q = get(p, aux);    
    assert(q==NULL);    

    aux.code = dim - 10;
    q = get(p, aux);
    assert(q!=NULL);
    assert(q->code == dim-10);
    free(q);
    toBegin(p);
    assert(next(p).code == dim-10);
    assert(next(p).code == 1);

    freeMoveToFront(p);
    puts("OK segunda parte!"); 
    return 0;
}

El error:


1 uno 2 dos 3 tres 4 cuatro 
3 tres
3 tres
Debe imprimir 3 tres 1 uno 2 dos 4 cuatro
3 tres 1 uno 2 dos 4 cuatro 
OK primera parte!
OK segunda parte!

=================================================================
==488548==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x7fd440f2d887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55f3dba246e8 in add /home/sofi/PI/R2/2019_R2C/ej2.c:40
    #2 0x55f3dba2689c in main /home/sofi/PI/R2/2019_R2C/ej2.c:189
    #3 0x7fd440b92d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

Direct leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x7fd440f2d887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55f3dba246e8 in add /home/sofi/PI/R2/2019_R2C/ej2.c:40
    #2 0x55f3dba255bb in main /home/sofi/PI/R2/2019_R2C/ej2.c:121
    #3 0x7fd440b92d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

Indirect leak of 1599904 byte(s) in 49997 object(s) allocated from:
    #0 0x7fd440f2d887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55f3dba246e8 in add /home/sofi/PI/R2/2019_R2C/ej2.c:40
    #2 0x55f3dba2689c in main /home/sofi/PI/R2/2019_R2C/ej2.c:189
    #3 0x7fd440b92d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

Indirect leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x7fd440f2d887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55f3dba246e8 in add /home/sofi/PI/R2/2019_R2C/ej2.c:40
    #2 0x55f3dba259dc in main /home/sofi/PI/R2/2019_R2C/ej2.c:131
    #3 0x7fd440b92d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

Indirect leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x7fd440f2d887 in __interceptor_malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:145
    #1 0x55f3dba246e8 in add /home/sofi/PI/R2/2019_R2C/ej2.c:40
    #2 0x55f3dba2579c in main /home/sofi/PI/R2/2019_R2C/ej2.c:125
    #3 0x7fd440b92d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f)

SUMMARY: AddressSanitizer: 1600032 byte(s) leaked in 50001 allocation(s).
marcelogarberoglio commented 1 week ago

static void freeRec(TList l){ if(l==NULL) return ; free(l->tail); free(l); }

free no es lo mismo que freeRec

sratto0 commented 1 week ago

Ahí está, muchas gracias y perdón por las molestias