hsearch(3) Library Functions Manual hsearch(3) BEZEICHNUNG hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r, hsearch_r - Verwaltung von Hash-Tabellen BIBLIOTHEK Standard-C-Bibliothek (libc, -lc) UBERSICHT #include int hcreate(size_t nel); void hdestroy(void); ENTRY *hsearch(ENTRY eintrag, ACTION aktion); #define _GNU_SOURCE /* siehe feature_test_macros(7) */ #include 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 **ruckwert, struct hsearch_data *htab); BESCHREIBUNG Die drei Funktionen hcreate(), hsearch() und hdestroy() ermoglichen dem Aufrufer die Erstellung und Verwaltung einer Hash-Suchtabelle. Deren Eintrage sind Paare aus einem Schlussel (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 uberdies Programmen ermoglichen, 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 verandern). Zuerst muss mittels hcreate() eine Hash-Tabelle erzeugt werden. Das Argument nel gibt die Maximalzahl der Eintrage in der Tabelle an. (Dieses Maximum kann in der Folge nicht geandert werden, wahlen Sie es also mit Bedacht.) Es ist moglich, dass die Implementierung diesen Wert nach oben anpasst, um die Leistungsfahigkeit der resultierenden Hash-Tabelle zu verbessern. Die Funktion hcreate_r() erledigt die gleiche Aufgabe wie hcreate(), tut das aber fur 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 fur 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 Schlussel wie eintrag (wobei >>der gleiche<< mittels strcmp(3) bestimmt wird) und gibt bei Erfolg einen Zeiger auf diesen Eintrag zuruck. Das Argument eintrag ist vom Typ ENTRY, der in wie folgt definiert wird: typedef struct entry { char *key; void *data; } ENTRY; Das Feld key zeigt auf eine null-terminierte Zeichenkette, die als Suchschlussel dient. Das Feld data zeigt auf dem Schlussel zugeordnete Daten. Das Argument aktion bestimmt, was hsearch() nach einer erfolglosen Suche unternimmt. Dieses Argument muss einen von zwei Werten annehmen: fur den Wert ENTER soll eine Kopie von eintrag in die Tabelle eingefugt werden (und ein Zeiger auf den neuen Eintrag in der Hash-Tabelle als Ergebnis der Funktion zuruckgegeben werden); FIND bedeutet, dass NULL zuruckgegeben 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 *ruckwert zuruckgegeben wird und nicht als Funktionsergebnis. RUCKGABEWERT hcreate() und hcreate_r() geben bei Erfolg einen Wert ungleich null zuruck; im Fehlerfall 0, wobei errno gesetzt wird, um den Fehler anzuzeigen. Bei Erfolg gibt hsearch() einen Zeiger auf einen Eintrag in der Hash-Tabelle zuruck. Bei einem Fehler gibt hsearch() NULL zuruck. Fehler treten auf, wenn die gewunschte 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. FEHLER hcreate_r() und hdestroy_r() konnen aus den folgenden Grunden fehlschlagen: EINVAL htab ist NULL. hsearch() und hsearch_r() konnen aus den folgenden Grunden fehlschlagen: ENOMEM Die aktion war ENTER, key wurde nicht in der Tabelle gefunden und es war nicht ausreichend Platz fur einen neuen Eintrag vorhanden. ESRCH Die aktion war FIND und key wurde nicht in der Tabelle gefunden. POSIX.1 beschreibt nur den Fehler ENOMEM. ATTRIBUTE Siehe attributes(7) fur eine Erlauterung der in diesem Abschnitt verwandten Ausdrucke. +-----------------+-------------------------+--------------------------+ |Schnittstelle | Attribut | Wert | +-----------------+-------------------------+--------------------------+ |hcreate(), | Multithread-Fahigkeit | MT-Unsicher race:hsearch | |hsearch(), | | | |hdestroy() | | | +-----------------+-------------------------+--------------------------+ |hcreate_r(), | Multithread-Fahigkeit | MT-Sicher race:htab | |hsearch_r(), | | | |hdestroy_r() | | | +-----------------+-------------------------+--------------------------+ STANDARDS hcreate() hsearch() hdestroy() POSIX.1-2008. hcreate_r() hsearch_r() hdestroy_r() GNU. GESCHICHTE hcreate() hsearch() hdestroy() SVr4, POSIX.1-2001. hcreate_r() hsearch_r() hdestroy_r() GNU. 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% grosser 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 Eintrage in der Hash-Tabelle weisen. (Das konnen sie nicht tun, weil sie nicht wissen, ob diese Puffer dynamisch zugewiesen wurden.) Falls diese Puffer freigegeben werden mussen (vielleicht, weil das Programm wiederholt Hash-Tabellen erzeugt und wieder freigibt, anstatt eine einzelne Tabelle uber die Programmlaufzeit hinweg zu pflegen), dann muss das Programm Datenstrukturen zur Speicherverwaltung pflegen, um die Elemente der Tabelleneintrage freigeben zu konnen. FEHLER SVr4 und POSIX.1-2001 geben an, dass aktion nur fur erfolglose Suchen von Bedeutung ist, so dass ein ENTER nichts fur eine erfolgreiche Suche tun sollte. In Libc und Glibc (vor Version 2.3) verstosst die Implementierung gegen die Spezifikation und aktualisiert in diesem Fall data fur den gegebenen key. Einzelne Eintrage konnen der Hash-Tabelle hinzugefugt, jedoch nicht geloscht werden. BEISPIELE Das folgende Programm fugt 24 Eintrage in eine Hashtabelle ein und zeigt dann einige davon an. #include #include #include 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 auftreten */ if (ep == NULL) { fprintf(stderr, "entry failed\n"); exit(EXIT_FAILURE); } } for (size_t i = 22; i < 26; i++) { /* Zwei Eintrage 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) UBERSETZUNG Die deutsche Ubersetzung dieser Handbuchseite wurde von Martin Eberhard Schauer und Mario Blattermann erstellt. Diese Ubersetzung ist Freie Dokumentation; lesen Sie die GNU General Public License Version 3 oder neuer bezuglich der Copyright-Bedingungen. Es wird KEINE HAFTUNG ubernommen. Wenn Sie Fehler in der Ubersetzung dieser Handbuchseite finden, schicken Sie bitte eine E-Mail an die Mailingliste der Ubersetzer . Linux man-pages 6.06 31. Oktober 2023 hsearch(3)