Repository 32bit  Forum
Repository 64bit  Wiki

[C] Curioso comportamento della malloc e puntatori raminghi

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

[C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Dorian » sab lug 12, 2008 11:28

L'altra notte mi stavo divertendo a implementare un semplice stack (LIFO data structure), giusto per staccare dalla monotonia dello studio :D, 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 :D.

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?
Dorian
Linux 1.0
Linux 1.0
 
Messaggi: 35
Iscritto il: lun mag 05, 2008 17:59

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda gioco » sab lug 12, 2008 12:35

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.
Avatar utente
gioco
Packager
Packager
 
Messaggi: 900
Iscritto il: sab giu 18, 2005 23:00
Località: in the court of the Wesnoth king
Slackware: last stable

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda targzeta » sab lug 12, 2008 13:59

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6194
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda phobos3576 » sab lug 12, 2008 14:34

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!
Avatar utente
phobos3576
Staff
Staff
 
Messaggi: 2980
Iscritto il: sab apr 16, 2005 23:00
Slackware: 13.1
Kernel: 2.6.37-smp
Desktop: KDE 4.5.3

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda gioco » sab lug 12, 2008 14:55

phobos3576 ha scritto: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;
}
Avatar utente
gioco
Packager
Packager
 
Messaggi: 900
Iscritto il: sab giu 18, 2005 23:00
Località: in the court of the Wesnoth king
Slackware: last stable

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Dorian » sab lug 12, 2008 17:31

Giustissimo. Avrei dovuto pensare a entrambe le soluzioni :|, non va bene fare le cose così :D!
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 :D! Se dichiaro STACK_LENGTH tipo 12 me lo ritrovo due posizioni più a destra, coerentemente :D

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!
Ultima modifica di Dorian il sab lug 12, 2008 17:53, modificato 1 volta in totale.
Dorian
Linux 1.0
Linux 1.0
 
Messaggi: 35
Iscritto il: lun mag 05, 2008 17:59

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Mario Vanoni » sab lug 12, 2008 17:52

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.
Mario Vanoni
Iper Master
Iper Master
 
Messaggi: 3174
Iscritto il: lun set 03, 2007 20:20
Località: Cuasso al Monte (VA)
Nome Cognome: Mario Vanoni
Slackware: 12.2
Kernel: 3.0.4 statico
Desktop: fluxbox/seamonkey

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Dorian » sab lug 12, 2008 18:05

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 :p!


@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?
Dorian
Linux 1.0
Linux 1.0
 
Messaggi: 35
Iscritto il: lun mag 05, 2008 17:59

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda targzeta » sab lug 12, 2008 18:36

Dorian ha scritto:...
@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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6194
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Dorian » sab lug 12, 2008 18:47

In effetti si, è simile come principio a un constructor...
Dorian
Linux 1.0
Linux 1.0
 
Messaggi: 35
Iscritto il: lun mag 05, 2008 17:59

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda gioco » sab lug 12, 2008 18:50

Dorian ha scritto: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
Avatar utente
gioco
Packager
Packager
 
Messaggi: 900
Iscritto il: sab giu 18, 2005 23:00
Località: in the court of the Wesnoth king
Slackware: last stable

Re: [C] Curioso comportamento della malloc e puntatori raminghi

Messaggioda Dorian » sab lug 12, 2008 23:04

Fantastico, sei stato chiarissimo! E' chiaro che ho ancora strada da fare :D!
Dorian
Linux 1.0
Linux 1.0
 
Messaggi: 35
Iscritto il: lun mag 05, 2008 17:59


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite