Ein paar Fragen zu meinem modularen Code void * als dynamischer Datentyp in C

StackOverflow https://stackoverflow.com/questions/2395216

Frage

Vor ein paar Tagen ich gepostet und jeder schlug mich void* zu verwenden, was ich auch tat. Ich denke, einige von ihnen auch ein paar Dinge beachtet, dass ich brauchen würde zu kümmern, aber ich bin sicher nicht das, was sie genau waren. Allerdings bin ich ein paar Probleme mit diesem mit ...

Ich werde nicht alle meinen Code schreiben, wo denn es ist recht groß, stattdessen werde ich die Dinge schreiben, dass ich denke, sind wichtig und hoffentlich genug für Sie, mir zu helfen.

Meine Hash-Tabelle Struktur ist wie folgt: 

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;

Die Signatur für meine Insert-Funktion geht wie folgt aus: 

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

Und irgendwo innerhalb dieser Funktion, wenn ich einen freien Eimer in der Hash-Tabelle finden, ich dies tun: 

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

All dies stellt ein paar Probleme:

1) Wie Sie sehen oben ich einfach bin jeden Schlüssel / Wert-Paar des freien Eimer auf den gleichen Zeiger wie die Schlüssel / Wert hashInsert Funktion übergebenen Argumente zu setzen. Dies stellt ein Problem, wie Sie schon bemerkt haben können ... So etwas wie dies zu tun: 

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

Und wenn der Eingang „KeyA“ und dann „KeyB“, werden beide „KeyB“, wie die Eimer Tasten. Das Gleiche gilt für den Wert und nicht nur den Schlüssel, da sie im Grunde die gleiche Art sind, weil ich meinen Code will voll modular haben, für jeden Datentyp.

Wie kann ich dieses Problem lösen?

Mein erster obwohl ist strdup(str) zu nutzen und weiterzugeben, dass auf die hashInsert Funktion. Das würde das Problem lösen. Und da dies im Haupt Code behandelt wurde, habe ich leicht malloc() auch für alle anderen Datentypen Ich muß passieren als Wert verwenden könnte (der Schlüssel wird wohl immer ein String oder ein int sein).

Aber diese Lösung stellt ein weiteres Problem ...

2) Wie soll ich diesen zugewiesenen Speicher frei? Sicher, es wurde von dem „Haupt-Programmierer“ zugeordnet und nicht die „Hash-Tabellen-Modul Programmierer“ so, die „Haupt Programmierer“ sollte es in dem Haupt-Code befreien, nicht wahr? Allerdings sieht das nicht viel, wie modularer Code zu mir.

Mein Code hat auch eine hashDestroy Funktion, alle zugewiesenen Speicher freizugeben. Aber wie kann ich diese Funktion kostenlos alles benutzen? Ich kann nicht einfach über Iterierte jeden Schlüssel / Wert und die Verwendung free() auf sie verursachen vielleicht einige von ihnen nicht malloc'd in erster Linie von jedem Programmierer waren und ich nicht zu befreien, sie benötigen.

Wie kann ich herausfinden, welche davon meine hashDestroy müssen frei und welche sollte es nicht?

3) zu beenden, ich denke, ich auch dieses Problem in den Mix werfen ... In Punkt eins war mein Vorschlag strdup() oder malloc zu „reparieren“ zu verwenden, das spezifische Problem (während andere) die Einführung, sondern dass auch sehen nicht sehr modular zu mir. Diese Speicherzuweisung soll in dem Hash-Tabelle Modulcode und nicht im Hauptcode von dem „Haupt Programmierer“.

gemacht

Wie schlagen Sie mir dieses Problem lösen? Ich meine, können die Datentypen alles sein und während die Verwendung von strdup() viel hilft, es funktioniert nur für Streicher. Was passiert, wenn ich Speicher für einige spezifische Struktur oder nur ein int zuweisen müssen?

Sorry für den großen Beitrag, aber ich denke, diese Fragen sind alle im Zusammenhang und ich brauche etwas Hilfe, um sie aus, da mein C Wissen herauszufinden ist nicht so extrem. Ich erst vor kurzem gelernt, über void* so ...

War es hilfreich?

Lösung

Wow: dies wird einige Beantwortung vollständig zu übernehmen. Doch eines der wichtigsten Dinge, die Sie brauchen werden, ist die Größe von was auch immer es ist, dass Sie verarbeiten - es in Ordnung ist, einen void-Zeiger zu verwenden, aber Sie müssen wissen, wie groß das Objekt, deren Adresse Sie erhalten ist.

  

[...] jeder schlug mich void * zu verwenden, was ich auch tat. [...]

     

Meine Hash-Tabelle Struktur ist wie folgt: 

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;

Sie sind wahrscheinlich ein size_t key_sz; und ein size_t val_sz; Mitglied in HashItem müssen. Ihre Hash-Funktion Zeiger müssen wissen, wie groß der Schlüssel gehasht werden soll.

Ich bin in zwei Köpfen über das, was der HashKey sein sollte. Es hängt davon ab, wie Sie dieses Material verwenden. Es sieht aus wie Sie wollen:

  • dieser Schlüsselwert meiner Wahl gegeben,
  • Speichern / Rück diese Daten, die mit ihm verbunden ist.

In diesem Fall müssen Sie wahrscheinlich auch die Hash-Zahl irgendwo in der HashItem speichern; Das ist der Wert, der durch Ihre Hash-Funktion zurückgegeben - anscheinend eine ganze Zahl ohne Vorzeichen. Ich bin mir nicht sicher, was die Unterschrift auf dem compare Funktion (Funktionszeiger) sein sollte; Ich bin misstrauisch, dass es entweder ein Paar HashKey-und-Größenwerte oder möglicherweise ein Paar HashItem Zeigers nehmen soll.

  

Die Signatur für meine Insert-Funktion geht wie folgt aus: 

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

Und irgendwo innerhalb dieser Funktion, wenn ich einen freien Eimer in der Hash-Tabelle finden, ich dies tun: 

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

All dies stellt ein paar Probleme:

     

1) Wie Sie sehen oben ich einfach bin jeden Schlüssel / Wert-Paar des freien Eimer auf den gleichen Zeiger wie die Schlüssel / Wert hashInsert Funktion übergebenen Argumente zu setzen. Dies stellt ein Problem, wie Sie schon bemerkt haben können ... So etwas wie dies zu tun: 

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

Der Schlüssel zum void * mit Adressen ist zu laufen um. Gießen sollte in C unnötig sein Sie müssen auch die Größe der Dinge passieren. Daraus folgt: 

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));

Intern werden Sie die Daten kopieren -. Nicht mit ‚strdup ()‘, da Sie nicht wissen, dass es nicht innere NUL ‚\ 0‘ Bytes in ihm

  

Und wenn der Eingang „KeyA“ und dann „KeyB“, werden beide „KeyB“, wie die Eimer Tasten. Das Gleiche gilt für den Wert und nicht nur den Schlüssel, da sie im Grunde die gleiche Art sind, weil ich meinen Code will voll modular haben, für jeden Datentyp.

     

Wie kann ich dieses Problem lösen?

Sie müssen definieren, wer was besitzt, und ob (und wie) die Container kopiert Daten. In C ++, machen die Behälter eine Kopie von was auch immer sie sind, zu speichern.

  

Mein erster Gedanke ist strdup zu verwenden (str) und die Funktion zum hashInsert passieren. Das würde das Problem lösen. Und da dies im Haupt Code behandelt wurde, ich leicht malloc verwenden könnte () auch für alle anderen Datentyp muss ich als Wert zu übergeben (der Schlüssel wird wohl immer ein String oder ein int sein).

Sie können nicht, weil in der Regel verwenden ‚strdup ()‘, weder die Werte noch die Schlüssel sind Strings. Wenn sie sind immer Strings, warum verwenden Sie 'void *' anstelle von 'char *'?

Sie können entscheiden, den Wert und die Schlüssel zu kopieren -. So lange, wie Sie die Größen kennen

  

Aber diese Lösung stellt ein weiteres Problem ...

     

2) Wie soll ich diesen zugewiesenen Speicher frei? Sicher, es wurde von dem „Haupt-Programmierer“ zugeordnet und nicht die „Hash-Tabellen-Modul Programmierer“ so, die „Haupt Programmierer“ sollte es in dem Haupt-Code befreien, nicht wahr? Sie jedoch, dass nicht viel wie modularer Code mir sieht.

     

Mein Code hat auch eine hashDestroy Funktion, alle zugewiesenen Speicher freizugeben. Aber wie kann ich diese Funktion kostenlos alles benutzen? Ich kann nicht nur Iterierte über jeden Schlüssel / Wert und frei verwenden () auf sie vielleicht dazu führen, einige von ihnen nicht von jedem Programm malloc'd wurdenr an erster Stelle und ich nicht brauchen, um sie zu befreien.

     

Wie kann ich herausfinden, welche davon meine hashDestroy müssen frei und welche sollte es nicht?

Sie können nicht. Sie müssen eine Politik definieren und nur dann, wenn diese Politik ermöglicht es Ihnen, die Zerstörung tun sollten Sie es tun. Wenn Sie alles zu kopieren, Sie eine einfache Zeit haben. Wenn Sie nichts kopieren, haben Sie eine andere einfache Zeit (wohl einfacher), aber Ihre Kunden haben eine Hölle einer Zeit, weil sie eine Struktur, um zu verfolgen, was Sie brauchen müssen sie lösen - vielleicht eine Hash-Liste ...

  

3) zu beenden, ich glaube, ich auch dieses Problem in den Mix werfen ... In Punkt eines war mein Vorschlag strdup () oder malloc „fix“, dass spezifisches Problem zu verwenden (während eines andere Einführung), aber das auch sieht nicht sehr modular zu mir. Diese Speicherzuweisung soll in dem Hash-Tabelle Modulcode und nicht im Hauptcode von dem „Haupt Programmierer“.

gemacht

Ja ... das ist im Grunde meine Empfehlung.

  

Wie schlagen Sie mir dieses Problem lösen? Ich meine, können die Datentypen alles sein und während die Verwendung von strdup () hilft viel, es funktioniert nur für Streicher. Was passiert, wenn ich Speicher für einige spezifische Struktur oder nur ein int zuweisen müssen?

Beachten Sie, dass das Kopieren funktioniert nur flache Kopien. Wenn die Strukturen Sie kopieren Zeiger enthalten, dann wird die Duplizierung Code kopieren nur den Zeiger und nicht die auf Daten spitzen.

Also, eine allgemeine Lösung wird eine Art Kopierfunktion benötigen. Sie können fordern haben, dass der Benutzer gibt Ihnen eine ‚Freigabe‘ -Funktion, dass gibt den Speicher in einem Element. Sie können was Sie benötigen die Benutzer zur Verfügung stellen mit bereits vollständig zugeordneten Daten. Sie müssen darüber nachdenken, wer was besitzt die Suchfunktion zurückkehrt - ist es immer noch ‚in‘ der Hash-Tabelle oder hat sie entfernt wurde. Schauen Sie hart an dem C ++ STL-System - es allgemein gesprochen hat eine ausgezeichnete Arbeit und Modellierung Ihre Anforderungen an, was es erfordert, kann sinnvoll sein. Aber denken Sie daran, C ++ hat Konstruktoren und Destruktoren zu helfen.

Andere Tipps

würde ich alle Daten malloc, und ermöglichen es dem Client an die Hash-Funktionen eine item_free() Funktion bei Hash-Tabelle init Zeit registrieren. Auf diese Weise ist es an die „Haupt Programmierer“, wie es zu behandeln.

Hmmm, was ich in Ihrem Beispiel zu sehen ist das Problem nicht hashtable Kollisionen (obwohl Sie scheinen dieses Problem zu haben, als auch), ist es, wie die Erinnerung an den Elementen in der Tabelle gespeichert zu verwalten. Ich denke, dass der normale Weg, diese Art der Sache zu tun, ist der Benutzer in der Datenstruktur zu erzwingen (die Hash-Tabelle), um die Arbeit der Verteilung der Platz für all die Dinge zu tun, die in den Tisch gelegt werden soll. Die Hash-Tabelle sollte nur Sorge um die Zeiger. Angenommen, Sie tun tun, um eine Zuordnung kopieren Sie dann in der Datenstruktur: Wie würde der Benutzer weiß, wie der Speicher freizugeben, wenn das Element aus dem hastable entfernt

Es gibt zwei allgemeine Lösungen für Kollisionen in einer Hash-Tabelle zu tun:

  1. Verwenden Sie den nächsten freien Eimer statt.
  2. Ein Eimer speichert eine verknüpfte Liste, so können mehrere Elemente in dem gleichen Eimer gespeichert werden.

Mit entweder von denen, die Frage, wann zu befreien, was nie entsteht, da alle Arten von Daten entweder von der Hash-Tabelle zugeordnet sind, oder durch die Client-Hash-Tabelle. Wenn Sie immer noch neugierig sind, dann ist die kurze Antwort auf dieses Dilemma zu verwenden Smart Pointer .

eine Hash-Tabelle zu implementieren, müssen wir eine Reihe von Eimern. Und da mehrere Elemente auf den gleichen Speicherbereich-Hash kann jeder Eimer muss eine verknüpfte Liste.

Does 

HashItem *items;

führen Sie die zweite Anforderung oben?

Von Ihrer Erklärung, es ist nicht klar, ob es funktioniert.

Für ein hervorragendes Beispiel, siehe K & R Abschnitt 6.6. Link wo name = HashKey und defn = HashValue. alt text http: //www.goldfish .org / Bücher / Das% 20C% 20Programming% 20Language% 20-% 20K & R / pic64.gif

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top