[C] Curioso comportamento della malloc e puntatori raminghi

[Dorian]

L'altra notte mi stavo divertendo a implementare un semplice stack (LIFO data structure), giusto per staccare dalla monotonia dello studio , e sono inciampato in due particolari problemi.
Allora, intanzo il codice incriminato è il seguente:

Codice: Seleziona tutto

typedef struct stack_{
	int* stack;
	int* top;
} stack;

[...]

const int STACK_LENGTH = 10;

int main(int argc, char** argv) {
	stack S;
	
	S = stack_init(S);

[...]

extern const int STACK_LENGTH;

stack stack_init(stack S) {

	//S.stack = calloc(STACK_LENGTH, sizeof(int));
	if ((S.stack = (int*) malloc(STACK_LENGTH)) == NULL) {
		fprintf(stdout, "Error while allocating stack.\n");
	} else {
		memset(S.stack, 0, STACK_LENGTH);
		S.top = S.stack;
	}

	return(S);
}

[...]

void push(stack S, int x) {
	if(!stack_full(S)) {
		*(S.top) = x;
		(S.top)++;
	} else {
		fprintf(stdout, "Stack overflow avoided - value discarded.\n");
	}

	return;
}

(perdonate il collage, però ho il codice distribuito in più file, ho copiato solo lo stretto indispensabile).
Il primo problema è questo: la malloc mi alloca me**a (e fin qui ok) e il memset non funziona. Eclipse mi dice che, prima dell'allocazione, nelle 15 locazioni di memoria successive al puntatore int* S.stack vi è:

Codice: Seleziona tutto

{-1075572456, -1210256496, 2, -1075572412, -1075572400, -1208863784, 0, 1, 0, 134513245, -1209004044, -1208742688, 0, -1075572456, -601784191}

e subito dopo l'allocazione la stessa stringa diventa

Codice: Seleziona tutto

{0, 0, 0, 135153, 0 <repeats 11 times>}

Quel numero è RICORRENTE, sempre e comunque. Anche se uso la calloc, quella commentata, me lo ritrovo, solo che lo ritrovo all'undicesima posizione, e essendo STACK_LENGTH = 10 il programma "funzionerebbe" anche - ma mi rifiuto di accettare quella soluzione lol. Il memset successivo non serve a nulla. Se modifico con l'IDE il valore va benissimo, lo cambia e ciccia, però non capisco da dove arrivi. NON ho ancora provato a compilare su Win, mi pesa il c**o farlo bootare .

Ok, secondo problema, molto più grave a livello funzionale, non tiene conto dell'incremento del puntatore nella push. E' un puntatore perché volevo provare una soluzione alternativa al solito uso di un indice che viene incrementato, volevo usare un puntatore allocato inizialmente all'indirizzo della prima cella di memoria del vettore e poi incrementarlo mano a mano. Funzionare funziona, noto che l'indirizzo viene incrementato correttamente durante la push, ma al ritorno al main e alla successiva chiamata di push (è in un loop che va da 0 a STACK_LENGTH) viene resettato all'indirizzo originale :dunno:.
Qualche idea su dove andare a guardare per risolvere queste cose?

[gioco]

Dopo una rapida occhiata al codice direi che il secondo problema è dovuto al fatto che usi una struttura e la modifichi in una chiamata per valore. Quando chiami la push viene creata una copia di S e viene modificata _quella_. Perciò quella nel main rimane com'era e S.top punta sempre alla stessa locazione. Di solito (almeno io sono abituato a fare così) con le struct si usano chiamate per riferimento. Questo ha alcuni vantaggi:
1) non deve essere fatta una copia della struttura in memoria (è quindi più efficiente)
2) con delle semplici funzioni che modificano lo stato della struct si rende il codice più leggibile e più facilmente manutenibile (si evitano brutti assegnamenti di struct) e si può implementare la struttura dati come ADT.

Tanto per darti un'esempio di quello che intendo eccoti una semplice implementazione del tipo di dati coda:
queue.h

Codice: Seleziona tutto

#include <stdlib.h>

typedef struct node {
	struct node *next;
} NODE;

typedef struct queue {
	NODE *head;
	NODE *tail;
} QUEUE;

int QUEUE_init(QUEUE *q);
int QUEUE_enqueue(QUEUE *q, NODE *node);
int QUEUE_dequeue(QUEUE *q, NODE **nodeptr);

queue.c

Codice: Seleziona tutto

#include "queue.h"

int QUEUE_init(QUEUE *q){

	if(q == NULL)
		return -1;

	q->head = NULL;
	q->tail = NULL;
	return 0;
}

int QUEUE_enqueue(QUEUE *q, NODE *node){

	if(q == NULL || node == NULL)
		return -1;

	node->next = NULL;
	if(q->head == NULL)
		q->head = node;
	else
		q->tail->next = node;
	q->tail = node;
	return 0;
}

int QUEUE_dequeue(QUEUE *q, NODE **nodeptr){

	if(q == NULL || nodeptr == NULL)
		return -1;

	*nodeptr = q->head;
	if(q->head != NULL)
		q->head = q->head->next;
	return 0;
}

Per quanto riguarda primo problema, invece, non credo di aver capito bene. Se allochi 10 bytes con la malloc e con la memset scrivi '0' in 10 bytes perchè vai a vedere cosa c'è nell'11-esimo? Devi assumere che tutta la memoria all'infuori di quella da te allocata e inizializzata abbia contenuto indefinito. La malloc poi ti restituisce una zona di memoria non inizializzata, come riportato nel man.

[targzeta]

Quoto gioco in toto, le strutture dovrebbero essere sempre passate per riferimento e non per copia, come fa di default il C. Visto che gioco ha già postato un implementazione di una coda FIFO, ti posto una possibile implementazione per la tia pila LIFO di interi.

File stack.h

Codice: Seleziona tutto

 struct Stack
{
  int *stack;
  int last;
  int size;
};

struct Stack *stack_init(int s);
int stack_push(struct Stack *s, int e);
int stack_pop(struct Stack *s, int *e);
void stack_free(struct Stack *s);

File stack.c

Codice: Seleziona tutto

#include "stack.h"
#include <stdlib.h>

struct Stack *stack_init(int size)
{
  struct Stack *s;

  if ( size <= 0 )
    return NULL;

  if ( (s=malloc(sizeof(struct Stack))) == NULL )
    return NULL;

  if ( (s->stack=malloc(size * sizeof(int))) == NULL )
    {
      free(s);
      return NULL;
    }

  s->size=size;
  s->last=0;
 
  return s;
}

int stack_push(struct Stack *s, int e)
{
  if ( s->last == s->size )
    return -1;

  s->stack[(s->last)++]=e;

  return 0;
}

int stack_pop(struct Stack *s, int *e)
{
  if ( s->last == 0 )
    return -1;

  *e=s->stack[--(s->last)];

  return 0;
}

void stack_free(struct Stack *s)
{
  free(s->stack);
  free(s);
}

File main.c

Codice: Seleziona tutto

#include "stack.h"
#include <stdio.h>

int main()
{
  struct Stack *s;
  int i;

  if ( (s=stack_init(10)) == NULL )
    {
      printf("Errore di allocazione di memoria");
      return 1;
    }

  for ( i=0; i < 10; i++ )
    stack_push(s,i);

  while ( stack_pop(s,&i) == 0 )
    printf("%i\n",i);

  stack_free(s);

  return 0;
}

Da compilare con:

Codice: Seleziona tutto

gcc -Wall -pedantic main.c stack.c

Spina

[phobos3576]

Il passaggio per valore, apparentemente può andare anche bene visto che si sta passando una "piccola" struttura di tipo stack che occupa lo spazio necessario per contenere due puntatori a int; il problema è che, all'interno di stack_init, viene inizializzato il puntatore S.stack il quale però appartiene alla copia di S e non all'originale creato in main.

Quindi, ha ragione Gioco!

In più, ho qualche dubbio anche su questa riga:

Codice: Seleziona tutto

if ((S.stack = (int *) malloc(STACK_LENGTH)) == NULL) {

Visto che si intende creare uno stack di puntatori a int, dovrebbe essere più corretto scrivere:

Codice: Seleziona tutto

if ((S.stack = (int *) malloc(STACK_LENGTH * sizeof(int *))) == NULL) {

Altrimenti viene creata un'area da 10 byte il cui indirizzo iniziale viene assegnato a S.stack!

[gioco]

Quindi, ha ragione Gioco; in più, ho qualche dubbio anche su questa riga:

Codice: Seleziona tutto

if ((S.stack = (int *) malloc(STACK_LENGTH)) == NULL) {

Visto che si intende creare uno stack di puntatori a int, dovrebbe essere più corretto scrivere:

Codice: Seleziona tutto

if ((S.stack = (int *) malloc(STACK_LENGTH * sizeof(int *))) == NULL) {

Altrimenti viene creata un'area da 10 byte il cui indirizzo iniziale viene assegnato a S.stack!

E qui ha ragione phobos3576 alla grande. Prima non avevo fatto troppo caso a quella riga. Per un int il gcc sul mio sistema utilizza 4 bytes, quindi 10 bytes non sono affatto sufficienti per 10 elementi int. Dal punto di vista stilistico (e anche per evitare errori del genere che può sempre capitare di fare) è forse più appropriato usare la calloc() che impone di specificare la dimensione in bytes del singolo elemento (per quanto poi io, ad esempio, usi abitualmente la malloc()).

Visto che siamo qui a postar codice eccovi due righe per determinare quanti bytes il vostro compilatore utilizza per rappresentare i vari tipi di dato (si è una stupidaggine, ma me la sono ritrovata fra altri sorgenti dopo tanto tempo e mi ha fatto ripensare ai primi anni di università):

Codice: Seleziona tutto

#include <stdio.h>
#include <unistd.h>

#define fatal(s) {                                                              \
		fprintf(stderr, "[%s:%d] %s\n", __FILE__, __LINE__, s);         \
		exit(1);                                                        \
}
#define FIFO_NAME "tempfifo"

struct messaggio{
	int destid;
	char buf[4092];
};

int main(){
	long r;
	
	printf("sizeof:\n\n");
	printf("       char = %3d bytes = %3d bit\n", sizeof(char),  sizeof(char) * 8);
	printf("      short = %3d bytes = %3d bit\n", sizeof(short), sizeof(short) * 8);
	printf("        int = %3d bytes = %3d bit\n", sizeof(int), sizeof(int) * 8);
	printf("       long = %3d bytes = %3d bit\n", sizeof(long), sizeof(long) * 8);
	printf("   unsigned = %3d bytes = %3d bit\n", sizeof(unsigned), sizeof(unsigned) * 8);
	printf("      float = %3d bytes = %3d bit\n", sizeof(float), sizeof(float) * 8);
	printf("     double = %3d bytes = %3d bit\n", sizeof(double), sizeof(double) * 8);
	printf("long double = %3d bytes = %3d bit\n", sizeof(long double), sizeof(long double) * 8);
	if(mkfifo(FIFO_NAME, 0666) == -1)
		fatal("mkfifo failed");
	if((r = pathconf(FIFO_NAME, _PC_PIPE_BUF)) == -1)
		fatal("pathconf failed");
	if(unlink(FIFO_NAME) == -1)
		fatal("unlink failed");
	printf("   PIPE_BUF = %4ld bytes\n", r);
	printf(" struct messaggio = %4d bytes\n", sizeof(struct messaggio));
	if(r == sizeof(struct messaggio))
		printf("OK!\n");
	printf("\n");
	return 0;
}

[Dorian]

Giustissimo. Avrei dovuto pensare a entrambe le soluzioni , non va bene fare le cose così !
Comunque, ora sto lavorando sul puntatore, ma già l'allocazione ora funge come volevo - ed effettivamente era un errore stupido -.-.
Però una cosa curiosa che vi voglio far notare è questa: stack è il puntatore alla prima cella di memoria del mio "vettore", giusto? ecco, quel vettore, diciamo così, contiene questa roba prima dell'allocazione:

Codice: Seleziona tutto

{-1080925192, -1209314416, 2, -1080925148, -1080925136, -1207921704, 0, 1, 0, 134513217, -1208061964, -1207800608, 0, -1080925192, 818364545}

e questa DOPO l'allocazione:

Codice: Seleziona tutto

{0 <repeats 11 times>, 135121, 0, 0, 0}

visto quel numero?! E' quasi lo stesso di prima e non capisco da dove salti fuori ne cosa debba rappresentare ! Se dichiaro STACK_LENGTH tipo 12 me lo ritrovo due posizioni più a destra, coerentemente

Va be', ora provo a vedere per questo puntatore!

edit: ok perfetto. Sembra andare tutto come deve andare.

Codice: Seleziona tutto

void stack_init(stack* S) {

	if ((S->stack = (int*) malloc(STACK_LENGTH * sizeof(int))) == NULL) {
		fprintf(stdout, "Error while allocating stack.\n");
	} else {
		memset(S->stack, 0, STACK_LENGTH);
		S->top = S->stack;
	}

	return;
}

bool stack_empty(stack* S) {
	if(S->top == S->stack) {
		return(true);
	} else {
		return(false);
	}
}

bool stack_full(stack* S) {
	if(S->top == S->stack + STACK_LENGTH) {
		return(true);
	} else {
		return(false);
	}
}

void push(stack* S, int x) {
	if(!stack_full(S)) {
		*(S->top) = x;
		S->top++;
	} else {
		fprintf(stdout, "Stack overflow avoided - value discarder.\n");
	}

	return;
}

int pop(stack* S) {
	int x;

	if(!stack_empty(S)) {
		S->top--;
		x = *(S->top);
	} else {
		fprintf(stdout, "Stack underflow avoided.\n");
		return(-1);
	}

	return(x);
}

l'unico accrocchio credo sia quello della stack_full(), ma non mi è venuto in mente niente di meglio, e dovrebbe essere comunque una soluzione corretta anche logicamente!

[Mario Vanoni]

Ignoro se e` pertinente al tuo problema.

http://lxer.com/

articolo:

Developer fixes 33-year-old Unix bug

in yacc(1) causato da malloc(3),
scoperto casualmente usando Sparc64
con un malloc(3) in versione 64 bit.

Essendo GNU malloc(3) un discendente,
forse il problema e` simile/uguale.

[Dorian]

We Mario, ma sai che per un momento anche io ho pensato dipendesse proprio da quello? O da qualche strano meccanismo di gestione della memoria, robe del genere. Però poi ho abbassato la cresta ed effettivamente non era un problema dalla malloc, ero proprio io a sbagliare !


@spina: te nella stack_init() hai allocato una struct tutta alll'interno della funzione, non prendendo come parametro che la dimensione della stessa. Io invece me la creo nel main, passo il puntatore alla struct, ci faccio quel che devo e bon, non restituisco che il comando al main. Come mai hai preferito fare così? per questioni di "solidità" del codice?

[targzeta]

...
@spina: te nella stack_init() hai allocato una struct tutta alll'interno della funzione, non prendendo come parametro che la dimensione della stessa. Io invece me la creo nel main, passo il puntatore alla struct, ci faccio quel che devo e bon, non restituisco che il comando al main. Come mai hai preferito fare così? per questioni di "solidità" del codice?

Perchè, dopo aver usato per molto tempo il paradigma ad oggetti, ho preso l'abitudine a crearmi "oggetti" anche in C, il mio stack_init() somiglia molto ad un costruttore non trovi?

Spina

[Dorian]

In effetti si, è simile come principio a un constructor...

[gioco]

Come mai hai preferito fare così? per questioni di "solidità" del codice?

Si fa così per una questione di riusabilità del codice. La funzione di spina ti permette di allocare uno stack senza bisogno di conoscere come è implementato. Questo è importante se il codice fa parte di una libreria perchè è possibile modificare l'implementazione senza bisogno di toccare il codice client.
Ad esempio supponiamo che tu voglia aggiungere un campo nella struct stack che memorizza il numero di interi sulla pila e supponiamo che tu utilizzi questa implementazione di stack in due progetti. Se fai l'allocazione nel main dovrai andare a modificare il codice in ognuno dei progetti. Se invece l'allocazione viene eseguita nella funzione di inizializzazione (come nel codice di spina) allora dovrai modificare solo quella funzione ed entrambi i progetti integreranno l'aggiunta. Ovvero le chiamate alle funzioni (l'interfaccia) saranno le stesse, ciò che cambierà è il codice specifico dello stack (l'implementazione).
E' buona pratica di programmazione definire un'interfaccia semplice e chiara (che non dovrà essere modificata a meno che non sia indispensabile) e mantenerla ben separata dall'implementazione. In questo modo si migliora la riusabilità e la leggibilità del codice ed è più facile mantenere ed apportare modifiche al codice.
A tal proposito ti consiglio di approfondire l'argomento degli Abstract Data Types (ADT). E' un pattern di programmazione (per quanto raramente riguardo al C si parla di patterns) che aiuta a scrivere codice C in uno stile molto simile a quello della programmazione ad oggetti (sebbene sempre di paradigma procedurale si tratta). In sostanza si definiscono i dati (ad esempio nel caso dello stack la struct) come un nuovo tipo (vedi typedef) e poi una serie di funzioni che manipolano questi dati, ognuna delle quali ha come uno dei parametri un puntatore al nuovo tipo di dato. Proprio come avviene nel codice di spina.
E' mia abitudine, ad esempio, definire per i nuovi tipi di dato alcune funzioni standard (il che facilita anche ricordarsi i prototipi):
*) TIPO_new()
alloca
*) TIPO_free()
libera la memoria
*) TIPO_NOMECAMPO()
accede ai dati

[Dorian]

Fantastico, sei stato chiarissimo! E' chiaro che ho ancora strada da fare !