Occupazione struttura!

[drakend]

Dato questo frammento di codice:

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

struct cifrabinaria
{
unsigned char c;
struct cifrabinaria *next;
};

int main()
{
printf("%u\n",sizeof(unsigned char)+sizeof(struct cifrabinaria *));
printf("%u",sizeof(struct cifrabinaria));
}

Perché eseguendolo ottengo sulla prima linea 5 byte (somma delle dimensioni dei singoli componenti della struttura) e sulla seconda linea 8 byte (dimensione della struttura)... non capisco questa differenza di 3 byte.... qualcuno mi può illuminare?
Se no mi consigliate qualche altro modo di memorizzare una stringa di lunghezza variabile di cui non è possibile fissare un limite massimo?

[recoil]

non ricordo perfettamente come lavora il sizeof ma probabilmente ti restituisce 8 byte nel secondo caso perché considera la memoria occupata in multipli di 4 byte (una word)

[Ziosilvio]

Ti sei imbattuto in una caratteristica del linguaggio C che dipende squisitamente dal compilatore e dalla macchina.
Dipende, in sostanza, da come viene "allineata" la memoria.
Ci dovrebbe essere qualcosa in proposito sul sito delle FAQ del newsgroup comp.lang.c, ma non mi ricordo in che punto.
Forse c'è qualcosa anche sul Kernighan e Ritchie, ma non ne sono sicuro.

[drakend]

Ma quindi quando occupa la struttura? 5 o 8 byte?

[recoil]

Originariamente inviato da drakend
Ma quindi quando occupa la struttura? 5 o 8 byte?

ti ha risposto bene Ziosilvio
dipende da come è organizzata la memoria. cmq quando la allochi devi prendere un multiplo di 4 byte, quindi anche se la struttura occupa 5 va a finire che ne sprechi 3

[ilsensine]

8 byte, a meno che il tuo compilatore non consenta di "impacchettarla" in qualche modo dentro i 5 byte.

Per curiosità, intendi usare una struttura per ogni carattere della tua stringa variabile? Non ti sembra un pò contorto?

[drakend]

Originariamente inviato da ilsensine
8 byte, a meno che il tuo compilatore non consenta di "impacchettarla" in qualche modo dentro i 5 byte.

Per curiosità, intendi usare una struttura per ogni carattere della tua stringa variabile? Non ti sembra un pò contorto?

Il fatto è che devo fare un programma in cui ho la necessità di sommare e sottrarre stringhe contenenti configurazioni binarie ed in più non posso mettere un limite massimo alla lunghezza di queste stringhe. Quindi non posso sicuramente usare gli array, se non creando buffer progressivamente più grandi e copiandoci gli array più piccoli, ma questo porta via un bel po' di tempo ed ho la necessità di rendere il programma il più veloce possibile (è per un esame universitario)... d'altro canto non posso nemmeno allocare un megabyte solo per il buffer stringa. Quindi inizialmente avevo pensato ad una lista strutturata come hai già visto: solo che per ogni byte ci sono 4 byte per il puntatore... non è un uso esattamente razionale della memoria. Quindi ho pensato a questo compromesso:

struct cifrabinaria
{
unsigned char cifre[32];
struct cifrabinaria *next;
};

Che ne dici?

[ilsensine]

realloc

[Ziosilvio]

Originariamente inviato da drakend
Ma quindi quando occupa la struttura? 5 o 8 byte?

Il valore restituito da sizeof corrisponde sempre al numero di byte realmente occupati.
Quindi, se sizeof dice 8, sono 8.

[drakend]

Originariamente inviato da ilsensine
realloc

La conosco un po' questa funzione, però se non ci dovesse essere più memoria nello heap a disposizione del programma che succede?

[Ziosilvio]

Originariamente inviato da ilsensine
realloc

realloc alloca blocchi contigui di memoria, per cui se la stringa è veramente molto ma molto lunga assai credo sia meglio usare la lista, magari nella seconda versione e con un conteggio dello spazio rimasto libero.
(Potrebbe non esserci 1 blocco libero da 1 gozziliardo di byte, ma esserci 2000 blocchi liberi da 1 millesimo di gozziliardo di byte.)

[drakend]

Originariamente inviato da Ziosilvio
realloc alloca blocchi contigui di memoria, per cui se la stringa è veramente molto ma molto lunga assai credo sia meglio usare la lista, magari nella seconda versione e con un conteggio dello spazio rimasto libero.
(Potrebbe non esserci 1 blocco libero da 1 gozziliardo di byte, ma esserci 2000 blocchi liberi da 1 millesimo di gozziliardo di byte.)

Io devo sostenere un esame di algoritmi e strutture dati, per questo mi sto scervellando nella scelta della struttura dati in cui memorizzare queste benedette stringhe binarie, stando molto attento anche a non fare semplificazioni del tipo "eh ma tanto non le metterà mai stringhe così lunghe", perché poi il caro prof mi chiede il perché ho trascurato quell'aspetto potenziale e mi boccia. Il fatto che sia statisticamente bassa la possibilità che mi dia un numero binario con milioni di cifre questo non mi autorizza ad eliminare questa possibilità, credo.
Ho pensato quindi ad una soluzione che mantenesse il vantaggio
dell'indicizzazione degli array ed eliminasse il problema della loro
dimensione statica. Fra l'altro mi sembra che realloc, se non trova
un blocco contiguo nella memoria della dimensione richiesta fallisce, vero?

[Ziosilvio]

Originariamente inviato da drakend
Fra l'altro mi sembra che realloc, se non trova un blocco contiguo nella memoria della dimensione richiesta fallisce, vero?

Sì.

Ragion per cui, IMHO, la soluzione con le liste è il miglior compromesso fra efficienza e complessità, purché la grandezza degli array al loro interno sia opportuna. Io direi 64, 80 o 128, in base al principio che "tanto l'utente di solito non fornisce input troppo grandi" e la tua lista avrà 2 o 3 elementi nel caso "ordinario"

[cionci]

struct cifrabinaria 
{ 
  unsigned int cifre; 
  struct cifrabinaria *next; 
};

Un byte per ogni bit è uno spreco (soprattutto se poi devi leggerli/scriverli su disco visto che devi ritrasformarli in sequenza di bit)...
E poi ci accedi ai vari bit con le operazioni di and/or...
Se prevedi che la struttura sia lunga puoi subito usare un vettore:

struct cifrabinaria 
{ 
  unsigned int cifre[1024]; 
  int bit_usati;
  struct cifrabinaria *next; 
};

[ilsensine]

Originariamente inviato da drakend
La conosco un po' questa funzione, però se non ci dovesse essere più memoria nello heap a disposizione del programma che succede?

Che il tuo programma è fatto male, in quanto gli vuoi far gestire più memoria di quanto è possibile

Il fatto è che devo fare un programma in cui ho la necessità di sommare e sottrarre stringhe contenenti configurazioni binarie

Se intendi cose tipo "011011...", allora fai come ti ha consigliato Cionci (o simili varianti sul tema, se il numero di cifre può essere molto elevato).

Originariamente inviato da drakend realloc alloca blocchi contigui di memoria

No, alloca blocchi contigui di indirizzi virtuali. Ogni s/o ne mette a disposizione 2 o 3 GB indipendentemente dalla memoria disica disponibile.

[drakend]

Ho risolto il problema della struttura dati da utilizzare: alloco un unsigned int e poi uso gli operatori bitwise per manipolare i singoli bit... Così ho 32 configurazioni disponibili con soli 4 byte... con possibilità di espandere la struttura ulteriormente mediante puntatore. Che ne dite della soluzione?
Mi si presenta però un altro problema: "passare" come sorta di parametro di input della funzione un pezzo di cifre che sta nello standard input viola il principio di indipendenza delle funzioni dal contesto in cui sono collocate?
Ovviamente non c'è alcun passaggio reale di parametro, è solo per rendere l'idea...

[cionci]

Originariamente inviato da drakend
Ho risolto il problema della struttura dati da utilizzare: alloco un unsigned int e poi uso gli operatori bitwise per manipolare i singoli bit... Così ho 32 configurazioni disponibili con soli 4 byte... con possibilità di espandere la struttura ulteriormente mediante puntatore. Che ne dite della soluzione?

Cioè come ti avevo detto io ?!?!?
Allocarne uno alla volta è un graaaande spreco di memoria... Fare una lista in questo modo:

struct bits
{
   unsigned int data;
   struct bits *next;
};

Comporta l'allocazione di 8 byte per ogni 32 bit... Di conseguenza sprechi la metà della memoria allocata...

Originariamente inviato da drakend
Mi si presenta però un altro problema: "passare" come sorta di parametro di input della funzione un pezzo di cifre che sta nello standard input viola il principio di indipendenza delle funzioni dal contesto in cui sono collocate?
Ovviamente non c'è alcun passaggio reale di parametro, è solo per rendere l'idea...

non ho capito...

[drakend]

Originariamente inviato da cionci
Cioè come ti avevo detto io ?!?!?
Allocarne uno alla volta è un graaaande spreco di memoria... Fare una lista in questo modo:

struct bits
{
   unsigned int data;
   struct bits *next;
};

Comporta l'allocazione di 8 byte per ogni 32 bit... Di conseguenza sprechi la metà della memoria allocata...

non ho capito...

Sì come avevi detto tu! Ti ringrazio per avermi nominato gli operatori bitwise, non me li ricordavo!
Per quanto riguarda la questione dello standard input intendo dire che avrei una funzione che mi prende dei caratteri da lì (mettiamo la tastiera ad es) e poi me li mette dentro la struttura. Mi spiego meglio: io devo fare un programma che interpreta righe di comando del tipo

s 11001110

s è il nome dell'operazione da fare, e la uso per selezionare la funzione specifica... poi il restante pezzo lo farei "digerire" alla funzione specifica. Mi domando se questo ragionamento costituisca una violazione del principio di indipedenza delle funzioni o meno.

[cionci]

Semplice...fai fare la lettura dell stdin da un'altra funzione... Questa funzione avrà il compito di interpretare i comandi e di estrarre le informazioni...
Ad esempio:

#define LEN 128
#define BYTELEN 32

struct bits
{
   unsigned int data[BYTELEN];
   int pos; /*indica il primo libero*/
   struct bits *next;
};

int inserisci_bit(struct bits **data, char cbit)
{
    unsiegned int op;
    if(!(cbit == '0' || cbit == '1'))
       return -1;
    if((*data)->pos == LEN) /* è pieno */
    {
       while((*data)->next)
           (*data) = (*data)->next;

       (*data)->next = alloca_bits();
       (*data) = (*data)->next;
    }
    op = 1 << ((*data)->pos)%(sizeof(int)*8);
    if(cbit == '1')
       ((*data)->data[((*data)->pos)/(sizeof(int)*8)] |= op;
    else 
       ((*data)->data[((*data)->pos)/(sizeof(int)*8)] &= ~op;
    return 0;
}

int inserisci(struct bits *data, char *sbits)
{
    if(!sbits || !data)
       return -1;
    while(strlen(sbits) > 0) {
       if(inserisci_bit(&data, *sbits))
          return -1;
       ++sbits;
    }
    return 0;
}

int leggi_input(FILE *in = stdin)
{
   struct bits *data;
   data = alloca(data);
   /*ora leggi da "in" l'input,
   quando hai trovato il comando e la stringa di bit
   semplicemente richiami: */
   inserisci(data, stringa_bits);
}

Quale principio viola ? L'inserimento si potrebbe in teoria fare meglio... Invece di un bit alla volta si potrebbero inserire tutti i bit contemporaneamente (o quasi tutti)...

[Scoperchiatore]

mi chiedo come farò a fare Algoritmi e strutture dati in Java