hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Verwaltung von
Hash-Tabellen
Standard-C-Bibliothek (
libc,
-lc)
#include <search.h>
int hcreate(size_t nel);
void hdestroy(void);
ENTRY *hsearch(ENTRY eintrag, ACTION aktion);
#define _GNU_SOURCE /* siehe feature_test_macros(7) */
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab);
int hsearch_r(ENTRY eintrag, ACTION aktion, ENTRY **rückwert,
struct hsearch_data *htab);
Die drei Funktionen
hcreate(),
hsearch() und
hdestroy()
ermöglichen dem Aufrufer die Erstellung und Verwaltung einer
Hash-Suchtabelle. Deren Einträge sind Paare aus einem Schlüssel
(eine Zeichenkette) und zugeordneten Daten. Mit diesen Funktionen kann immer
nur eine Hash-Tabelle genutzt werden.
Die drei Funktionen
hcreate_r(),
hsearch_r(),
hdestroy_r()
sind ablaufinvariante Funktionen, die überdies Programmen
ermöglichen, mit mehreren Hash-Tabellen gleichzeitig zu arbeiten. Das
letzte Argument,
htab, zeigt auf eine Struktur mit der Beschreibung der
Hash-Tabelle, die die Funktion verwenden soll. Der Programmierer sollte diese
Struktur als »undurchsichtig« behandeln (d.h. er sollte nicht
versuchen, direkt auf Felder der Struktur zuzugreifen oder zu
verändern).
Zuerst muss mittels
hcreate() eine Hash-Tabelle erzeugt werden. Das
Argument
nel gibt die Maximalzahl der Einträge in der Tabelle
an. (Dieses Maximum kann in der Folge nicht geändert werden,
wählen Sie es also mit Bedacht.) Es ist möglich, dass die
Implementierung diesen Wert nach oben anpasst, um die
Leistungsfähigkeit der resultierenden Hash-Tabelle zu verbessern.
Die Funktion
hcreate_r() erledigt die gleiche Aufgabe wie
hcreate(), tut das aber für die Tabelle, die durch die Struktur
*htab beschrieben wird. Vor dem ersten Aufruf von
hcreate_r()
muss die Struktur
htab mit Nullen initialisiert werden.
Die Funktion
hdestroy() gibt den Speicher frei, den die von
hcreate() erzeugte Hash-Tabelle beansprucht. Nach dem Aufruf von
hdestroy() kann mittels
hcreate() eine neue Hash-Tabelle erzeugt
werden. Die Funktion
hdestroy_r() erledigt die analoge Aufgabe
für die durch
*htab beschriebene Hash-Tabelle, die zuvor mittels
hcreate_r() erzeugt wurde.
Die Funktion
hsearch() durchsucht die Hash-Tabelle nach einem Eintrag mit
dem gleichen Schlüssel wie
eintrag (wobei »der
gleiche« mittels
strcmp(3) bestimmt wird) und gibt bei Erfolg
einen Zeiger auf diesen Eintrag zurück.
Das Argument
eintrag ist vom Typ
ENTRY, der in
<search.h> wie folgt definiert wird:
typedef struct entry {
char *key;
void *data;
} ENTRY;
Das Feld
key zeigt auf eine null-terminierte Zeichenkette, die als
Suchschlüssel dient. Das Feld
data zeigt auf dem
Schlüssel zugeordnete Daten.
Das Argument
aktion bestimmt, was
hsearch() nach einer erfolglosen
Suche unternimmt. Dieses Argument muss einen von zwei Werten annehmen:
für den Wert
ENTER soll eine Kopie von
eintrag in die
Tabelle eingefügt werden (und ein Zeiger auf den neuen Eintrag in der
Hash-Tabelle als Ergebnis der Funktion zurückgegeben werden);
FIND bedeutet, dass NULL zurückgegeben werden sollte. (Falls
aktion gleich
FIND ist, wird
data ignoriert.)
Die Funktion
hsearch_r() arbeitet wie
hsearch(), aber mit der
durch
*htab beschriebenen Hash-Tabelle. Der Unterschied zwischen
hsearch_r() und
hsearch() ist, das der Zeiger auf den gefundenen
Eintrag in
*rückwert zurückgegeben wird und nicht als
Funktionsergebnis.
hcreate() und
hcreate_r() geben bei Erfolg einen Wert ungleich
null zurück; im Fehlerfall 0, wobei
errno gesetzt wird, um den
Fehler anzuzeigen.
Bei Erfolg gibt
hsearch() einen Zeiger auf einen Eintrag in der
Hash-Tabelle zurück. Bei einem Fehler gibt
hsearch() NULL
zurück. Fehler treten auf, wenn die gewünschte
aktion
ENTER und die Hash-Tabelle voll ist oder wenn die
aktion
FIND ist und
eintrag nicht in der Hash-Tabelle gefunden werden
kann. Im Fehlerfall setzen diese zwei Funktionen
errno, um den Fehler
anzuzeigen.
hcreate_r() und
hdestroy_r() können aus den folgenden
Gründen fehlschlagen:
- EINVAL
-
htab ist NULL.
hsearch() und
hsearch_r() können aus den folgenden
Gründen fehlschlagen:
- ENOMEM
- Die aktion war ENTER, key wurde nicht
in der Tabelle gefunden und es war nicht ausreichend Platz für
einen neuen Eintrag vorhanden.
- ESRCH
- Die aktion war FIND und key wurde
nicht in der Tabelle gefunden.
POSIX.1 beschreibt nur den Fehler
ENOMEM.
Siehe
attributes(7) für eine Erläuterung der in diesem
Abschnitt verwandten Ausdrücke.
| Schnittstelle |
Attribut |
Wert |
|
hcreate(), hsearch(), hdestroy() |
Multithread-Fähigkeit |
MT-Unsafe race:hsearch |
|
hcreate_r(), hsearch_r(), hdestroy_r() |
Multithread-Fähigkeit |
MT-Safe race:htab |
Die Funktionen
hcreate(),
hsearch() und
hdestroy() stammen
aus SVr4 und werden in POSIX.1-2001 und POSIX.1-2008 beschrieben.
Die Funktionen
hcreate_r(),
hsearch_r() und
hdestroy_r()
sind GNU-Erweiterungen.
Implementierungen von Hash-Tabellen sind in der Regel effizienter, wenn die
Tabelle ausreichend freien Raum bereitstellt, um Kollisionen zu reduzieren.
Typischerweise bedeutet das, dass
nel mindestens 25%
größer als sein sollte als die maximale Anzahl von Elementen,
die der Aufrufende in der Tabelle zu speichern erwartet.
Die Funktionen
hdestroy() und
hdestroy_r() geben die Puffer nicht
frei, auf die die Elemente
key und
data der Einträge in
der Hash-Tabelle weisen. (Das können sie nicht tun, weil sie nicht
wissen, ob diese Puffer dynamisch zugewiesen wurden.) Falls diese Puffer
freigegeben werden müssen (vielleicht, weil das Programm wiederholt
Hash-Tabellen erzeugt und wieder freigibt, anstatt eine einzelne Tabelle
über die Programmlaufzeit hinweg zu pflegen), dann muss das Programm
Datenstrukturen zur Speicherverwaltung pflegen, um die Elemente der
Tabelleneinträge freigeben zu können.
SVr4 und POSIX.1-2001 geben an, dass
aktion nur für erfolglose
Suchen von Bedeutung ist, so dass ein
ENTER nichts für eine
erfolgreiche Suche tun sollte. In Libc und Glibc (vor Version 2.3)
verstößt die Implementierung gegen die Spezifikation und
aktualisiert in diesem Fall
data für den gegebenen
key.
Einzelne Einträge können der Hash-Tabelle hinzugefügt,
jedoch nicht gelöscht werden.
Das folgende Programm fügt 24 Einträge in eine Hashtabelle ein und
zeigt dann einige davon an.
#include <search.h>
#include <stdio.h>
#include <stdlib.h>
static char *data[] = { "alpha", "bravo", "charlie", "delta",
"echo", "foxtrot", "golf", "hotel", "india", "juliet",
"kilo", "lima", "mike", "november", "oscar", "papa",
"quebec", "romeo", "sierra", "tango", "uniform",
"victor", "whisky", "x-ray", "yankee", "zulu"
};
int
main(void)
{
ENTRY e;
ENTRY *ep;
hcreate(30);
for (size_t i = 0; i < 24; i++) {
e.key = data[i];
/* Datum ist nur eine Ganzzahl, anstatt eines
Zeigers auf irgendwas */
e.data = (void *) i;
ep = hsearch(e, ENTER);
/* Es sollten keine Fehler eintreten */
if (ep == NULL) {
fprintf(stderr, "Eintrag fehlgeschlagen\n");
exit(EXIT_FAILURE);
}
}
for (size_t i = 22; i < 26; i++) {
/* Zwei Einträge aus der Tabelle ausgeben und zeigen,
dass zwei nicht in der Tabelle sind */
e.key = data[i];
ep = hsearch(e, FIND);
printf("%9.9s -> %9.9s:%d\n", e.key,
ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
}
hdestroy();
exit(EXIT_SUCCESS);
}
bsearch(3),
lsearch(3),
malloc(3),
tsearch(3)
Die deutsche Übersetzung dieser Handbuchseite wurde von Martin Eberhard
Schauer <
[email protected]> und Mario Blättermann
<
[email protected]> erstellt.
Diese Übersetzung ist Freie Dokumentation; lesen Sie die
GNU
General Public License Version 3 oder neuer bezüglich der
Copyright-Bedingungen. Es wird KEINE HAFTUNG übernommen.
Wenn Sie Fehler in der Übersetzung dieser Handbuchseite finden, schicken
Sie bitte eine E-Mail an die
Mailingliste
der Übersetzer