Alcune domande circa il mio codice modulare utilizzando * vuoto come tipo di dati dinamici in C

https://stackoverflow.com/questions/2395216

25-09-2019
|

Domanda

Un paio di giorni fa ho postato questa domanda e tutti mi ha suggerito di utilizzare void*, che ho fatto. Credo che alcuni di loro anche rilevare alcune cose che avrei bisogno di prendersi cura di, ma non sono sicuro di cosa esattamente erano. Tuttavia, sto avendo qualche problema con questo ...

Non ho intenzione di inviare tutto il mio codice in cui causa è abbastanza grande, invece, vi posterò le cose che ritengo importanti e, auspicabilmente, sono abbastanza per voi di darmi una mano.

La mia struttura della tabella di hash è come questo:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;

    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;

    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

La firma per la mia funzione di inserimento va in questo modo:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

E da qualche parte all'interno di quella funzione, quando trovo un secchio gratuito nella tabella hash, faccio questo:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

Tutti Questo presenta alcuni problemi:

1) Come potete vedere sopra Sto semplicemente impostando ogni coppia chiave / valore della benna libera allo stesso puntatore passato come gli argomenti della funzione hashInsert chiave / valore. Questo presenta un problema come avrete già notato ... Per esempio, fare qualcosa di simile:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

E se l'ingresso è "Keya" e poi "KeyB", sia avrà "KeyB", come le chiavi secchi. La stessa cosa vale per il valore e non solo la chiave dal momento che sono fondamentalmente lo stesso tipo perché voglio avere il mio codice completamente modulare, per qualsiasi tipo di dati.

Come posso risolvere questo problema?

Il mio primo pensiero è quello di utilizzare strdup(str) e passare che alla funzione hashInsert. Questo risolverebbe il problema. E dal momento che questo è stato gestito nel codice principale, ho potuto facilmente usare malloc() troppo per altri dati di tipo ho bisogno di passare come il valore (la chiave sarà probabilmente sempre essere una stringa o un int).

ma questa soluzione presenta un altro problema ...

2) Come dovrei liberare questa memoria allocata? Certo, è stato assegnato dal "principale programmatore" e non la "tabella di hash modulo programmatore" così, il "principale programmatore" dovrebbe liberare nel codice principale, giusto? Tuttavia, ciò non sembra molto come il codice modulare a me.

Il mio codice ha anche una funzione hashDestroy, per liberare tutta la memoria allocata. Ma come posso usare questa funzione per libera tutto? Non posso iterare su ogni chiave / valore e l'uso free() su di loro causo forse alcuni di loro non erano malloc'd da qualsiasi programmatore in primo luogo e non ho bisogno di liberarli.

Come faccio a scoprire quali mia hashDestroy deve liberare e quali essa non dovrebbe?

3) Per finire, credo che posso anche lanciare questo tema nel mix ... Al punto uno, il mio suggerimento è stato quello di utilizzare strdup() o malloc a "fissare" il problema specifico (mentre l'introduzione di un altro), ma che, inoltre, non guardare molto modulare per me. Questa allocazione di memoria dovrebbe essere fatto nel codice di modulo di tabella hash e non nel codice principale dal "principale programmatore".

Come mi consiglia io risolvere questo problema? Voglio dire, i tipi di dati possono essere qualsiasi cosa e, mentre l'uso di strdup() aiuta molto, funziona solo per le stringhe. Che cosa succede se ho bisogno di allocare memoria per un po 'di struttura specifica o solo un int?

Ci scusiamo per il grande post, ma credo che queste domande sono tutte collegate e ho bisogno di aiuto loro capire da quando la mia conoscenza C non è così estremo. Ho da poco imparato a conoscere void* così ...

Soluzione

Wow: questo sta andando a prendere un po 'di risposta in pieno. Tuttavia, una delle cose fondamentali che sta andando a bisogno è la dimensione di ciò che è si sta elaborando - è bene usare un puntatore nullo, ma è necessario sapere quanto è grande l'oggetto il cui indirizzo si sta ricevendo è.

[...] tutti mi ha suggerito di usare * vuoto, che ho fatto. [...]

La mia struttura della tabella di hash è come questo:

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;
    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;
    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

Si rischia di avere bisogno di un size_t key_sz; e membro size_t val_sz; in HashItem. Il puntatore funzione hash avrà bisogno di sapere quanto è grande la chiave da hash è.

Sono in due menti su ciò che il HashKey dovrebbe essere. Essa dipende in parte da come si utilizza questa roba. Sembra che si desidera:

Dato questo valore chiave della mia scelta,
Store / ritorno di questi dati che è associato con esso.

In questo caso, probabilmente anche bisogno di memorizzare il numero hash da qualche parte nel HashItem; vale a dire il valore restituito dalla funzione di hashing - a quanto pare un intero senza segno. Non sono sicuro di quello che la firma sulla funzione compare (puntatore a funzione) dovrebbe essere; Sono sospetto che dovrebbe prendere una coppia di valori HashKey-e-size, o forse un paio di puntatori HashItem.

La firma per la mia funzione di inserimento va in questo modo:

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

E da qualche parte all'interno di quella funzione, quando trovo un secchio gratuito nella tabella hash, faccio questo:

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

Tutti Questo presenta alcuni problemi:

1) Come si può vedere sopra Sto semplicemente impostando ogni coppia chiave / valore della benna libera allo stesso puntatore passato come gli argomenti della funzione hashInsert chiave / valore. Questo presenta un problema come avrete già notato ... Per esempio, fare qualcosa di simile:

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

La chiave per usare void * è quello di passare gli indirizzi intorno. Casting dovrebbe essere inutili in C. È inoltre necessario superare la dimensione delle cose. Quindi:

Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz,
                HashValue value, size_t val_sz);

char str[50];
scanf("%s%*c", str);
int value = 5;
hashInsert(t1, str, strlen(str)+1, &value, sizeof(value));

Internamente, si copierà i dati -. Non si usa 'strdup ()' dal momento che non si sa che non ci sono NUL interni '\ 0' byte in esso

E se l'ingresso è "Keya" e poi "KeyB", sia avrà "KeyB", come le chiavi secchi. La stessa cosa vale per il valore e non solo la chiave dal momento che sono fondamentalmente lo stesso tipo perché voglio avere il mio codice completamente modulare, per qualsiasi tipo di dati.

Come posso risolvere questo problema?

È necessario definire chi possiede cosa, e se (e come) i dati di copia del contenitore. In C ++, i contenitori fanno una copia di quello che sono la memorizzazione.

Il mio primo pensiero è quello di utilizzare strdup (str) e passare che alla funzione hashInsert. Questo risolverebbe il problema. E dal momento che questo è stato gestito nel codice principale, ho potuto facilmente usare malloc () troppo per tutti gli altri dati di tipo ho bisogno di passare come il valore (la chiave sarà probabilmente sempre essere una stringa o un int).

Non è possibile utilizzare 'strdup ()' perché in generale, né i valori né le chiavi sono stringhe. Se sono sempre stringhe, perché stai usando '* vuoto' invece di 'char *'?

E 'possibile decidere di copiare il valore e la chiave -. Fino a quando si conoscono le dimensioni

ma questa soluzione presenta un altro problema ...

2) Come dovrei liberare questa memoria allocata? Certo, è stato assegnato dal "principale programmatore" e non la "tabella di hash modulo programmatore" così, il "principale programmatore" dovrebbe liberare nel codice principale, giusto? Tuttavia, ciò non sembra molto come il codice modulare per me.

Il mio codice ha anche una funzione hashDestroy, per liberare tutta la memoria allocata. Ma come posso usare questa funzione per libera tutto? Non posso iterare su ogni chiave / valore e l'uso gratuito () su di essi causano forse alcuni di loro non sono stati malloc'd da qualsiasi programmar in primo luogo e non ho bisogno di liberarli.

Come faccio a scoprire quali mia hashDestroy deve liberare e quali essa non dovrebbe?

Non è possibile. È necessario definire una politica e solo nel caso che la politica ti permette di fare la distruzione si dovrebbe farlo. Se si copia tutto, si dispone di un periodo facile. Se copiate nulla, si dispone di una vita facile diverso (forse più facile), ma i vostri consumatori hanno un sacco di tempo perché hanno bisogno di una struttura per tenere traccia di ciò di cui hanno bisogno per rilasciare - forse un elenco hash ...

3) Per finire, credo che posso anche lanciare questo tema nel mix ... Al punto uno, il mio suggerimento è stato quello di utilizzare strdup () o malloc a "fissare" il problema specifico (mentre l'introduzione di un altro), ma che anche non guardare molto modulare per me. Questa allocazione di memoria dovrebbe essere fatto nel codice di modulo di tabella hash e non nel codice principale dal "principale programmatore".

Sì ... che è fondamentalmente la mia raccomandazione.

Come mi consiglia io risolvere questo problema? Voglio dire, i tipi di dati possono essere qualsiasi cosa e, mentre l'uso di strdup () aiuta molto, funziona solo per le stringhe. Che cosa succede se ho bisogno di allocare memoria per un po 'di struttura specifica o solo un int?

Si noti che la copia fa solo copie poco profonde. Se l'oggetto che sta copiando strutture contengono puntatori, poi la duplicazione del codice sarà solo copiare il puntatore e non la indicò dati.

Quindi, una soluzione generale richiede una sorta di funzione di copia. Potrebbe essere necessario richiedere che l'utente ti dà una funzione di 'rilascio' che libera la memoria in un elemento. Potrebbe essere necessario avere l'utente che si forniscono i dati già completamente assegnati. È necessario pensare a chi possiede cosa di ricerca restituisce la funzione - è ancora 'nella' tabella hash o è stato rimosso. Difficile guardare il sistema STL C ++ - è in generale fa un ottimo lavoro e modellando le vostre esigenze su ciò che richiede può avere senso. Ma ricordate, C ++ ha costruttori e distruttori per aiutarla.

Altri suggerimenti

Vorrei malloc tutti i dati, e consentire al cliente di funzioni hash registrare una funzione item_free() a tavola hash tempo init. In questo modo è fino al "principale programmatore" come gestirlo.

Hmmm, da quello che vedo nel tuo esempio il problema non è collisioni tabella di hash (anche se si sembrano avere questo problema pure), è come gestire la memoria degli elementi memorizzati nella tabella. Penso che il modo standard di fare questo genere di cose è quello di forzare l'utente della struttura dati (tabella hash) per fare il lavoro di allocare lo spazio per tutte le cose che sta per essere messo in tavola. La tabella hash dovrebbe avere solo preoccuparsi per i puntatori. Supponiamo che si fa fare una dotazione quindi copiare nella struttura dati: come sarebbe il know all'utente come deallocare la memoria quando l'articolo viene rimosso dal hastable

Ci sono due soluzioni generali per trattare con le collisioni in una tabella hash:

Utilizza il prossimo secchio libero invece.
un secchio memorizza una lista collegata in modo più elementi possono essere memorizzati nello stesso secchio.

Con uno di questi, la questione di quando per liberare ciò che non si pone, dal momento che tutti i tipi di dati vengono assegnati sia dalla tabella hash o dal cliente della tabella di hash. Se siete ancora curiosi, la breve risposta a questo dilemma è quello di utilizzare puntatori intelligenti .

Per implementare una tabella hash, abbiamo bisogno di una serie di secchi. E poiché più elementi possono hash allo stesso secchio, ciascun segmento ha bisogno di una lista collegata.

non

HashItem *items;

eseguire il secondo requisito di cui sopra?

Da tua spiegazione, la sua non è chiaro se lo fa.

Per un esempio eccellente, vedi K e R paragrafo 6.6. link dove name = HashKey e defn = HashValue. alt text http: //www.goldfish .org / libri / L'% 20C% 20Programming% 20Language% 20-% 20K & R / pic64.gif

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow