BEZEICHNUNG¶
hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Verwaltung von
Hash-Tabellen
ÜBERSICHT¶
#include <search.h>
int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
#define _GNU_SOURCE /* Siehe feature_test_macros(7) */
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *htab);
int hsearch_r(ENTRY item, ACTION action, ENTRY **retval,
struct hsearch_data *htab);
void hdestroy_r(struct hsearch_data *htab);
BESCHREIBUNG¶
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
item (wobei »der
gleiche« mittels
strcmp(3) bestimmt wird) und gibt bei Erfolg
einen Zeiger auf diesen Eintrag zurück.
Das Argument
item 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
action 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
item 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
action 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
*retval zurückgegeben wird und nicht als
Funktionsergebnis.
RÜCKGABEWERT¶
hcreate() und
hcreate_r() geben bei Erfolg einen Wert ungleich
null zurück; im Fehlerfall 0, wobei
errno auf die Ursache des
Fehlers gesetzt wird.
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
action
ENTER und die Hash-Tabelle voll ist oder wenn die
action
FIND ist und
item nicht in der Hash-Tabelle gefunden werden
kann. Im Fehlerfall setzen diese zwei Funktionen
errno, um die Ursache
des Fehlers anzuzeigen.
FEHLER¶
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 action war ENTER, key wurde nicht in der Tabelle
gefunden und es war nicht ausreichend Platz für einen neuen Eintrag
vorhanden.
- ESRCH
- Die action war FIND und key wurde nicht in der
Tabelle gefunden.
POSIX.1-2001 beschreibt nur den Fehler
ENOMEM.
ATTRIBUTE¶
Multithreading (siehe pthreads(7))¶
Die Funktionen
hcreate(),
hsearch(), and
hdestroy()
verwenden einen globalen Bereich zum Speichern der Tabelle und sind daher
nicht multithread-fähig.
Die Funktionen
hcreate_r(),
hsearch_r(), and
hdestroy_r()
sind multithread-fähig.
Die Funktionen
hcreate(),
hsearch() und
hdestroy() stammen
aus SVr4 und werden in POSIX.1-2001 beschrieben. Die Funktionen
hcreate_r(),
hsearch_r() und
hdestroy_r() sind
GNU-Erweiterungen.
ANMERKUNGEN¶
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.
FEHLER¶
SVr4 und POSIX.1-2001 geben an, dass
action 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.
BEISPIEL¶
Das folgende Programm fügt 24 Einträge in eine Hashtabelle ein und
zeigt dann einige davon an.
#include <stdio.h>
#include <stdlib.h>
#include <search.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, *ep;
int i;
hcreate(30);
for (i = 0; i < 24; i++) {
e.key = data[i];
/* Datum ist nur ein Integer, 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 (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);
}
SIEHE AUCH¶
bsearch(3),
lsearch(3),
malloc(3),
tsearch(3)
KOLOPHON¶
Diese Seite ist Teil der Veröffentlichung 3.74 des Projekts Linux-
man-pages. Eine Beschreibung des Projekts, Informationen, wie Fehler
gemeldet werden können sowie die aktuelle Version dieser Seite finden
sich unter
http://www.kernel.org/doc/man-pages/.
ÜBERSETZUNG¶
Die deutsche Übersetzung dieser Handbuchseite wurde von Martin Eberhard
Schauer <Martin.E.Schauer@gmx.de> 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 <debian-l10n-german@lists.debian.org>.
