[C] Heap, errore "deferencing pointer to incomplete type"

[darth_19]

salve, svolgendo un esercizio di programmazione sulle code a priorità implementate mediante heap ho incontrato questo errore, non riesco a capire come risolverlo dato che a livello logico mi sembra sia tutto apposto, l'algoritmo dovrebbe andare senza problemi, pensavo fosse qualche problema di allocazione ma anche implementando la memoria dinamica non sono riuscito a risolvere il problema, qui c'è il codice:

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

#include "job.h"
#include "pqueue.h"

#define MAXJOB 100
#define LEFT(i) ( (i*2) + 1 )
#define RIGHT(i) ( (i*2) + 2 )
#define PARENT(i) ( (i-1) / 2 )

struct PQUEUEtype
{
job* heap; /*puntatore a job*/
int heapsize;
};

.
.
.

void PQUEUEinsert ( pqueue x, job item ) /*item è l'elemento da inserire in pqueue*/
{
int i;

i =++(x->heapsize); /*aggiungo un elemento vuoto e parto dall'ultimo elemento dell'heap*/

while ( i>1 && ( x->heap[PARENT(i)]->priority ) < item->priority ) /*finchè: 1)non esco fuori dall'heap e
2)il padre dell'elemento corrente dell'heap è minore dell'elemento da inserire (confronto le priorità!) */
{
x->heap[i] = x->heap[PARENT(i)]; /*faccio scendere il padre (puntatore job!) */
i = PARENT(i);
}

x->heap[i]=item;
}

.
.
.

void PQUEUEheapify ( pqueue x, int i )
{
int l, r, largest;

l = LEFT(i);
r = RIGHT(i);

if ( l < x->heapsize && x->heap[l]->priority > x->heap[i]->priority )
largest=l;
else largest = i;

if ( r < x->heapsize && x->heap[r]->priority > x->heap[largest]->priority)
largest=r;
if ( largest != i )
{
SWAP( x, i, largest );
PQUEUEheapify( x, largest );
}
}

l'errore lo riscontro in queste due funzioni, nell'header legato al .c ho la dichiarazione del tipo "pqueue" che è un puntatore a struct PQUEUEtype, riuscireste ad aiutarmi a capire perchè continua a darmi questo problema???

Vi ringrazio! :)

[vbextreme]

non ho capito ne l'errore ne cosa vuoi fare...

[darth_19]

Posto il codice completo per chiarezza:

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

#include "job.h"
#include "pqueue.h"

#define MAXJOB 100
#define LEFT(i) ( (i*2) + 1 )
#define RIGHT(i) ( (i*2) + 2 )
#define PARENT(i) ( (i-1) / 2 )

struct PQUEUEtype
{
job* heap; /*puntatore a job*/
int heapsize;
};


pqueue PQUEUEcreate ( )
{
pqueue x;

printf("-> Creazione di una Coda a Priorità...\n");
x = malloc( sizeof(*x) );

x->heap= malloc( sizeof(job)*MAXJOB );
x->heapsize = 0 ;
printf("-> Coda inizializzata.\n");

return x;
}

void PQUEUEdelete ( pqueue x )
{
printf("-> eliminazione di una Coda a Priorità...");
free(x);
printf(" ...Coda eliminata.\n");
}

void PQUEUEshow ( pqueue x )
{
int i;

printf("---> Visualizzazione di una Coda a Priorità: \n");

for(i=0; i< x->heapsize; i++)
{
JOBdisplay( x->heap[i] );
}

printf("---> Coda Visualizzata. \n");

}

void PQUEUEinsert ( pqueue x, job item ) /*item è l'elemento da inserire in pqueue*/
{
int i;

i =++(x->heapsize); /*aggiungo un elemento vuoto e parto dall'ultimo elemento dell'heap*/

while ( i>1 && ( x->heap[PARENT(i)]->priority ) < item->priority ) /*finchè: 1)non esco fuori dall'heap e
2)il padre dell'elemento corrente dell'heap è minore dell'elemento da inserire (confronto le priorità!) */
{
x->heap[i] = x->heap[PARENT(i)]; /*faccio scendere il padre (puntatore job!) */
i = PARENT(i);
}

x->heap[i]=item;
}

void SWAP ( pqueue x, int index1, int index2)
{
job temp;

temp = x->heap[index1];
x->heap[index1] = x->heap[index2];
x->heap[index2] = temp;
}

void PQUEUEheapify ( pqueue x, int i )
{
int l, r, largest;

l = LEFT(i);
r = RIGHT(i);

if ( l < x->heapsize && x->heap[l]->priority > x->heap[i]->priority )
largest=l;
else largest = i;

if ( r < x->heapsize && x->heap[r]->priority > x->heap[largest]->priority)
largest=r;
if ( largest != i )
{
SWAP( x, i, largest );
PQUEUEheapify( x, largest );
}
}

void PQUEUEbuildheap ( pqueue x)
{
int i;
for ( i = (x->heapsize)/2-1 ; i >= 0; i--)
{
PQUEUEheapify(x, i);
}
}


praticamente è un modulo per l'implementazione delle code a priorità mediante Heap, l'esercizio fondamentalmente consiste nello gestire una coda a priorità

l'errore mi viene dato nelle righe in cui c'è il passaggio di puntatori "coda a priorità"->"vettore di job"->"singolo job", ovvero nel while della funzione PQUEUEinsert e nelle if della funzione PQUEUEheapify

il "tipojob" è un puntatore ad una struct jobtype che contiene un intero, la priorità del "job", ed una stringa. C'è tutto questo passaggio di puntatori perchè viene richiesto di implementare sia il "tipo coda a priorità" che il "tipo job" come ADT di prima categoria...

spero di aver dato abbastanza informazioni, è la prima volta che scrivo in questa sezione del forum :) mi scuso se non sono stato chiaro, o se continuo a non esserlo...

[vbextreme]

che errore ti da?

[darth_19]

l'ho scritto nel titolo! :D

"deferencing pointer to incomplete type"

[marco.r]

"a naso", il problema e' che o pqueue o job non sono state dichiarate correttamente per cui quando cerchi di andare a dereferenziare i puntatori non sa cosa c'e' dentro (incompete type solitamente vuol dire che proprio non sa come e' definita la struttura dati), ma senza sapere cos ahai scritto in job.h e pqueue.h e' difficile dare una risposta precisa.

[darth_19]

allora non avendo problemi di diritti d'autore vi posto anche i file header :D

job.h:
/*--- MODULO PER LA GESTIONE DEI SINGOLI JOB ---*/

/*
ogni job è caratterizzato da:
- livello di priorità (intero positivo)
- informazioni sul processo (stringa di massimo 30 caratteri)
*/

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

typedef struct JOBtype* job; /*il singolo job è un puntatore a una struct jobtype*/

/*--- FUNZIONI DI INTERFACCIA ---*/

job JOBcreate( ); /*creazione di un job (vuoto) e sua inizilizzazione*/
void JOBdelete( job ); /*eliminazione del job passato alla funzione*/
void JOBdisplay (job); /*visualizzazione a video delle informazioni del job passato alla funzione*/



pqueue.h:
/*--- MODULO PER LA GESTIONE DEllA PRIORITY QUEUE ---*/

/*
La priority queue è implementata mediante uno heap.
Si possono gestire al massimo 100 job.
*/

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

#include "job.h"

typedef struct PQUEUEtype* pqueue;

/*--- FUNZIONI DI INTERFACCIA ---*/

pqueue PQUEUEcreate ( ); /* alloca una coda a priorità */
void PQUEUEdelete ( pqueue ); /* elimina una coda a priorità */
void PQUEUEshow ( pqueue ); /* visualizza a video una coda*/

void PQUEUEinsert ( pqueue, job ); /* inserisce un elemento job in pqueue */
void SWAP ( pqueue, int, int ); /*scambia di posto due job all'interno della coda*/
void PQUEUEbuildheap ( pqueue ); /*costruisce uno heap a partire dal vettore di job*/
void PQUEUEheapify ( pqueue, int ); /*applica la proprietà funzionale degli heap al sotto albero: i, left(i), right(i) (con i indice dell'elemento job)*/



mi sembra sia tutto apposto, ho dichiarato il tipo di dato astratto pqueue e job come puntatore alla struct dichiarata nel .c, non è la prima volta che lavoro con gli ADT ed ho sempre fatto così, non lo so magari mi sfugge qualcosa...riuscite a scovare il problema?

[vendettaaaaa]

Non ho letto il codice, non ho voglia, ma ti posso dire che io uso il C++ e "incomplete type" significa che il tipo è stato solo dichiarato senza definirlo. O meglio, quando tenti di usare un oggetto di cui il compilatore non conosce la definizione, e quindi il layout in memoria. Puoi invece dichiarare puntatori a tipi incompleti in quanto non serve sapere quanto occupano. Esempio:
class Foo; // Solo dichiarata e non definita

int main()
{
Foo a; // Errore: per allocare nella stack una variabile Foo devo sapere cosa contiene e quindi quanta memoria occupa
Foo* a; // OK
}
Quindi sarà qualcosa di simile nel tuo codice.

[marco.r]

typedef struct JOBtype* job;

Manca la definizione di JOBtype;

[darth_19]

Non ho letto il codice, non ho voglia, ma ti posso dire che io uso il C++ e "incomplete type" significa che il tipo è stato solo dichiarato senza definirlo. O meglio, quando tenti di usare un oggetto di cui il compilatore non conosce la definizione, e quindi il layout in memoria. Puoi invece dichiarare puntatori a tipi incompleti in quanto non serve sapere quanto occupano. Esempio:
class Foo; // Solo dichiarata e non definita

int main()
{
Foo a; // Errore: per allocare nella stack una variabile Foo devo sapere cosa contiene e quindi quanta memoria occupa
Foo* a; // OK
}
Quindi sarà qualcosa di simile nel tuo codice.


ti ringrazio per la risposta, potresti dare un'occhiata al codice di job.h (dove dichiaro il puntatore alla struct) e job.c (dove dichiaro effettivamente la struct), io so che in c posso dichiare puntatori a struct non ancora dichiarate, e questo mi permette di implementare i cosiddetti "ADT di prima categoria", come vengono chiamati dal mio libro di riferimento (il Sedghewick), ora, io penso di aver messo tutto al posto giusto, il mio sarebbe una specie di "puntatore opaco", non capisco però perchè mi dia quell'errore...anche perchè mettendo a paragone con altri programmi che ho scritto, sempre seguendo la stessa modalità, non trovo differenze...

ecco il passaggio a cui mi riferisco:



job.h:

typedef struct JOBtype* job; /*il singolo job è un puntatore a una struct jobtype*/

job.c:

struct JOBtype
{
int priority;
char process_info[MAXCHAR];
};

[marco.r]

ti ringrazio per la risposta, potresti dare un'occhiata al codice di job.h (dove dichiaro il puntatore alla struct) e job.c (dove dichiaro effettivamente la struct), io so che in c posso dichiare puntatori a struct non ancora dichiarate, e questo mi permette di implementare i cosiddetti "ADT di prima categoria", come vengono chiamati dal mio libro di riferimento (il Sedghewick), ora, io penso di aver messo tutto al posto giusto, il mio sarebbe una specie di "puntatore opaco", non capisco però perchè mi dia quell'errore...anche perchè mettendo a paragone con altri programmi che ho scritto, sempre seguendo la stessa modalità, non trovo differenze...

Buona l'idea del puntatore opaco, ma allora devi fornire delle operazioni affinche' chi usa la tua struttura possa non sapere come e' fatta.
Ad esempio nel tuo caso potresti implementare job.h qualcosa come

typedef struct JOBtype* job; /*il singolo job è un puntatore a una struct jobtype*/

int get_priority(job j);
void set_priority(job j,int priority);
void get_process_info(job,char process_info[MAXCHAR]);
void set_process_info(job,char process_info[MAXCHAR]);

In job.c oltre alla definizione della struttura metti anche quella delle operazioni che ci vuoi associare.

struct JOBtype
{
int priority;
char process_info[MAXCHAR];
};

int get_priority(job j)
{
return job->priority;
}

void set_priority(job j,int priority)
{
job->priority = priority;
}

void get_process_info(job,char process_info[MAXCHAR]) { /* ... */ }
void set_process_info(job,char process_info[MAXCHAR]) { /* ... */ }


Ci sono anche alternative. Se JOBtype e' un tipo "interno" utilizzato solo da un'altra struttura, ad esempio dalla tua coda, uno potrebbe considerare eccessiva tutta questa astrazione. In questo caso JOBtype potrebbe essere noto alla coda, e opaco all'esterno, e quindi la sua definizione deve essere visibile anche dal codice che hai riportato sopra.
In questo potresti creare allora un header (job_impl.h ad esempio) che contenta la definizione della struttura e che venga incluso solo da chi di dovere

[darth_19]

Marco infatti ho fatto così :) quello che ho postato era un estratto dei file .h e .c, nel file .h ci sono i prototipi e la dichiarazione del puntatore opaco, mentre nel file .c c'è la dichiarazione della struttura a cui punta il puntatore opaco e le funzioni..

..ma ancora l'errore continua a darmelo :(

RISOLTO! :D

avevi ragione marco l'errore stava in una deferenziazione dove passavo da un puntatore alla struct che avevo definito nel file pqueue.c ad una che avevo definito nel file job.c... mi mancava appunto una stupidissima funzione nel .c che dato un puntatre job mi ritornava il campo priority... che stupidaggine .-.

int JOBpriority( job x)
{
return x->priority;
}

grazie a tutti per l'aiuto!