MoveToFrontADT.c

[Ftrivelloni]

Buenas Noches,

No entiendo porque mi funcion * get no funciona (mas alla de que no es la forma correcta de hacerla, porque borro el nodo y lo vuelvo a crear al principio de la lista) ya que devuelvo un puntero a un elemtype nuevo. Pero el fsanitize me dice que el address no es conocido?

El error ocurre en esta linea del main:

printf("%d %s\n", q->code, q->name); 

.c

#include "moveToFront.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>

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

typedef struct node * TList;

typedef struct moveToFrontCDT{
    TList first;
    size_t count;
    TList firstIter;
    compare cmp
    }moveToFrontCDT;

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

static TList addRec(TList l, elemType elem, int *ok, compare cmp){
    if (l == NULL) {
        TList aux = malloc(sizeof(struct node));
        aux->elem = elem;
        aux->tail = NULL;
        *ok = 1;
        return aux;
    }
    int c= cmp(l->elem, elem);
    if(c == 0){
        *ok = 0;
        return l;
    }
    l->tail = addRec(l->tail, elem, ok, cmp);
}

unsigned int add(moveToFrontADT moveToFront, elemType elem){
    int ok;
    moveToFront->first = addRec(moveToFront->first, elem, &ok, moveToFront->cmp);
    moveToFront->count += ok;
    return ok;
}

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

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

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

elemType next(moveToFrontADT moveToFront){
    if (!hasNext(moveToFront))
        exit(1);

    TList aux = moveToFront->firstIter;
    moveToFront->firstIter = moveToFront->firstIter->tail;
    return aux->elem;
}

static TList getRec(TList l, elemType elem, int *ok, compare cmp){
    if (l == NULL){
        *ok = 0;
        return l;
    }   

    if (cmp(l->elem, elem) == 0){
        TList aux = l->tail;
        free(l);
        *ok = 1;
        return aux;
    }
    l->tail = getRec(l->tail, elem, ok, cmp);
}

elemType * get(moveToFrontADT moveToFront, elemType elem){
    int ok;
    moveToFront->first = getRec(moveToFront->first, elem, &ok, moveToFront->cmp);

    if (ok){
        TList new = malloc(sizeof(struct node));
        new->elem = elem;
        new->tail = moveToFront->first;
        moveToFront->first = new;
        elemType * new2 = malloc(sizeof(elemType));
        *new2 = elem;
        return new2;
    }
    return NULL;    
}

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

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

main (tp11.5.c)

#include "moveToFront.h"
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Para este test completar el .h con:
/*
typedef struct {
    int code;
    char name[20];
} elemType;     
*/

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;
}

.h

#ifndef __movetofront__h
#define __movetofront__h

typedef struct moveToFrontCDT * moveToFrontADT;

typedef struct {
    int code;
    char name[20];
}elemType;      // Tipo de elemento a insertar

/*
** Retorna 0 si los elementos son iguales, negativo si e1 es "menor" que e2 y positivo 
** si e1 es "mayor" que e2
*/
typedef int (*compare) (elemType e1, elemType e2);

/* Retorna un nuevo conjunto de elementos genéricos. Al inicio está vacío */
moveToFrontADT newMoveToFront(compare cmp);

/* Libera toda la memoria reservada por el TAD */
void freeMoveToFront(moveToFrontADT moveToFront);

/* Inserta un elemento si no está. Lo inserta al final.
** Retorna 1 si lo agregó, 0 si no.
*/
unsigned int add(moveToFrontADT moveToFront, elemType elem);

/* Retorna la cantidad de elementos que hay en la colección */
unsigned int size(moveToFrontADT moveToFront);

/* Se ubica al principio del conjunto, para poder iterar sobre el mismo */
void toBegin(moveToFrontADT moveToFront);

/* Retorna 1 si hay un elemento siguiente en el iterador, 0 si no */
int hasNext(moveToFrontADT moveToFront);

/* Retorna el siguiente elemento. Si no hay siguiente elemento, aborta */
elemType next(moveToFrontADT moveToFront);

/* Retorna una copia del elemento. Si no existe retorna NULL.
** Para saber si el elemento está, usa la función compare. 
** Si el elemento estaba lo ubica al principio.
 */
elemType * get(moveToFrontADT moveToFront, elemType elem);
#endif

Saludos.

[marcelogarberoglio]

El ejemplo está hecho a propósito para que se den cuenta que no sirve retornar el elemento que se le pasa a la función sino que tienen que retornar el elemento que almacenaron, porque paso un struct que solo tiene el valor del campo code pero basura en el otro. En getRec estás perdiendo lo que se almacenó originalmente y reemplazándolo por lo que mandó el usuario Deberías "mover" el nodo, haciendo que el anterior apunte al siguiente, y ubicando el nodo al principio. Por ejemplo getRec podría simplemente devolver el tail (como hace ahora pero sin liberar) y en un parámetro de salida el nodo encontrado, para que get lo enganche al principio (si es que lo encontró)

en addRec te faltó un return al final

[Ftrivelloni]

Ok creo que entendi, ahora en este codigo, muevo el nodo que busco al principio, le paso los valores del mismo nodo al puntero a elemType, pero sigo teniendo el mismo AddressSanitizer y no logro encontrar ahora el error.

static TList getRec(TList l, elemType elem, TList *nodo, compare cmp){
    if (l == NULL){
        *nodo = NULL;
        return NULL;
    }   

    if (cmp(l->elem, elem) == 0){
        *nodo = l;
        return l->tail;
    }
    l->tail = getRec(l->tail, elem, nodo, cmp);
    return l;
}

elemType * get(moveToFrontADT moveToFront, elemType elem){
    TList nodo;
    moveToFront->first = getRec(moveToFront->first, elem, &nodo, moveToFront->cmp);

    if(nodo == NULL){
        return NULL;
    }
    nodo->tail = moveToFront->first;
    moveToFront->first = nodo;
    elemType * new2 = malloc(sizeof(elemType));
    *new2 = nodo->elem;
    return new2;
}

[marcelogarberoglio]

No veo fallas en get y getRec

¿corregiste además addRec según lo que te mencioné?

[Ftrivelloni]

Sobre el return al final de addRec? Si, si queres te envio denuevo el codigo entero

[marcelogarberoglio]

Mandalo

[Ftrivelloni]

.c

#include "moveToFront.h"
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <string.h>

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

typedef struct node * TList;

typedef struct moveToFrontCDT{
    TList first;
    size_t count;
    TList firstIter;
    compare cmp
    }moveToFrontCDT;

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

static TList addRec(TList l, elemType elem, int *ok, compare cmp){
    if (l == NULL) {
        TList aux = malloc(sizeof(struct node));
        aux->elem = elem;
        aux->tail = NULL;
        *ok = 1;
        return aux;
    }
    int c= cmp(l->elem, elem);
    if(c == 0){
        *ok = 0;
        return l;
    }
    l->tail = addRec(l->tail, elem, ok, cmp);
    return l;
}

unsigned int add(moveToFrontADT moveToFront, elemType elem){
    int ok;
    moveToFront->first = addRec(moveToFront->first, elem, &ok, moveToFront->cmp);
    moveToFront->count += ok;
    return ok;
}

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

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

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

elemType next(moveToFrontADT moveToFront){
    if (!hasNext(moveToFront))
        exit(1);

    TList aux = moveToFront->firstIter;
    moveToFront->firstIter = moveToFront->firstIter->tail;
    return aux->elem;
}

static TList getRec(TList l, elemType elem, TList *nodo, compare cmp){
    if (l == NULL){
        *nodo = NULL;
        return NULL;
    }   

    if (cmp(l->elem, elem) == 0){
        *nodo = l;
        return l->tail;
    }
    l->tail = getRec(l->tail, elem, nodo, cmp);
    return l;
}

elemType * get(moveToFrontADT moveToFront, elemType elem){
    TList nodo;
    moveToFront->first = getRec(moveToFront->first, elem, &nodo, moveToFront->cmp);

    if(nodo == NULL){
        return NULL;
    }
    nodo->tail = moveToFront->first;
    moveToFront->first = nodo;
    elemType * new = malloc(sizeof(elemType));
    *new = nodo->elem;
    return new;
}

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

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

.h

#ifndef __movetofront__h
#define __movetofront__h

typedef struct moveToFrontCDT * moveToFrontADT;

typedef struct {
    int code;
    char name[20];
}elemType;      // Tipo de elemento a insertar

/*
** Retorna 0 si los elementos son iguales, negativo si e1 es "menor" que e2 y positivo 
** si e1 es "mayor" que e2
*/
typedef int (*compare) (elemType e1, elemType e2);

/* Retorna un nuevo conjunto de elementos genéricos. Al inicio está vacío */
moveToFrontADT newMoveToFront(compare cmp);

/* Libera toda la memoria reservada por el TAD */
void freeMoveToFront(moveToFrontADT moveToFront);

/* Inserta un elemento si no está. Lo inserta al final.
** Retorna 1 si lo agregó, 0 si no.
*/
unsigned int add(moveToFrontADT moveToFront, elemType elem);

/* Retorna la cantidad de elementos que hay en la colección */
unsigned int size(moveToFrontADT moveToFront);

/* Se ubica al principio del conjunto, para poder iterar sobre el mismo */
void toBegin(moveToFrontADT moveToFront);

/* Retorna 1 si hay un elemento siguiente en el iterador, 0 si no */
int hasNext(moveToFrontADT moveToFront);

/* Retorna el siguiente elemento. Si no hay siguiente elemento, aborta */
elemType next(moveToFrontADT moveToFront);

/* Retorna una copia del elemento. Si no existe retorna NULL.
** Para saber si el elemento está, usa la función compare. 
** Si el elemento estaba lo ubica al principio.
 */
elemType * get(moveToFrontADT moveToFront, elemType elem);
#endif

main

#include "moveToFront.h"
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Para este test completar el .h con:
/*
typedef struct {
    int code;
    char name[20];
} elemType;     
*/

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;
}

[marcelogarberoglio]

Hay que corregir hasNext, debe ser

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

pero eso no debería afectar lo que retorne get. Mañana lo miro en detalle y te escribo.

[Ftrivelloni]

Dale no te preocupes, buenas noches!

[ImNotGone]

Te sigue fallando? Parece estar bien el codigo, si cambias lo que te menciono Marcelo obvio

[ImNotGone]

En el struct te falta un ; dsp de cmp

[ImNotGone]

Te anda a veces o te falla siempre?

[Ftrivelloni]

Bien dia!

Al parecer era ese ; del cmp el problema. Rarisimo porque nunca me marco el error el VS, tampoco me marcaba el error al compilarlo. Pero ya esta

Muchas gracias!

[ImNotGone]

a mi no me corre consistente, y el sanitizer no me avisa la linea. Que puede ser @marcelogarberoglio

[marcelogarberoglio]

El código está bien, por eso no encontrábamos el error. Si te falla en la segunda parte tal vez sea porque tenés poca memoria, podés bajarle el dim que aparece en el test. Lo del punto y coma que falta es un warning, anda igual pero mejor agregarlo