1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
.\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
.\"
.\" This is free documentation; you can redistribute it and/or
.\" modify it under the terms of the GNU General Public License as
.\" published by the Free Software Foundation; either version 2 of
.\" the License, or (at your option) any later version.
.\"
.\" The GNU General Public License's references to "object code"
.\" and "executables" are to be interpreted as the output of any
.\" document formatting or typesetting system, including
.\" intermediate and printed output.
.\"
.\" This manual is distributed in the hope that it will be useful,
.\" but WITHOUT ANY WARRANTY; without even the implied warranty of
.\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
.\" GNU General Public License for more details.
.\"
.\" You should have received a copy of the GNU General Public
.\" License along with this manual; if not, write to the Free
.\" Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139,
.\" USA.
.\"
.\" References consulted:
.\" SunOS 4.1.1 man pages
.\"
.\" Traduction 04/11/1996 par Christophe Blaess (ccb@club-internet.fr)
.\"
.TH HSEARCH 3 "4 Novembre 1996" GNU "Manuel du programmeur Linux"
.SH NOM
hsearch, hcreate, hdestroy \- Gestion de table de hachage.
.SH SYNOPSIS
.nf
.B #include <search.h>
.sp
.BI "ENTRY *hsearch (ENTRY " item ", ACTION " action ");
.sp
.BI "int hcreate (unsigned " nel ");"
.sp
.B void hdestroy (void);
.RE
.fi
.SH DESCRIPTION
Ces trois fonctions permettent l'utilisateur de ceer une table de
hachage du type \fIENTRY\fP (definie dans \fB<search.h>\fP) qui associe
une cl avec des donnes quelconques.
.PP
La table doit d'abord tre cre avec la fonction \fBhcreate()\fP.
\fInel\fP est une estimation du nombre d'lments dans la table.
\fBhcreate()\fP permet d'ajuster cette valeur ultrieurement, afin
d'amliorer les performances de la table de hachage.
.PP
La fonction \fIhdestroy()\fP libre la mmoire occupe par la table, afin
de pouvoir en construire une nouvelle.
.PP
\fIitem\fP est du type \fBENTRY\fP, qui est dfinie dans \fI<search.h>\fP
ainsi:
.sp
.nf
typedef struct entry
{
char *\fIkey\fP;
char *\fIdata\fP;
} ENTRY;
.fi
.sp
\fIkey\fP pointe sur une chane de caractres ASCII termine par un
caractre nul. Cette chane est la cl de recherche.
\fIdata\fP pointe sur les donnes associes cette cl.
Un pointeur sur un type diffrent de \fIchar\fP doit tre convertit
explicitement en \fI(char *)\fP.
La fonction \fBhsearch()\fP recherche dans la table un lment associ
la mme cl que \fIitem\fP, et si elle russit, elle renvoie un pointeur
sur cet lment.
Le paramtre \fIaction\fP dtermine ce que fera \fBhsearch()\fP si la
recherche est infructueuse.
Si \fIaction\fP vaut \fBENTER\fP alors \fBhsearch()\fP insrera le nouvel
lment dans la table. Si \fIaction\fP vaut \fBFIND\fP alors elle renverra
\fBNULL\fP.
.SH "VALEUR RENVOYE"
\fBhcreate()\fP renvoie \fBNULL\fP si la table ne peut PAS tre installe.
.PP
\fBhsearch()\fP renvoie \fINULL\fP si l'action est \fIENTER\fP et si la
table est pleine ou si l'action est \fIFIND\fP et si l'\fIitem\fP n'est
pas trouv dans la table.
.SH BOGUES
L'implmentation ne permet que la gestion d'une seule table de hachage
la fois.
Les entres ne peuvent tre qu'ajoutes dans la table, on ne peut pas les
supprimer individuellement.
.SH EXEMPLE
.PP
Le programme suivant insre 24 lments dans une table de hachage, puis
affiche quelques uns d'entre-eux.
.nf
#include <stdio.h>
#include <search.h>
char *data[]={ "alpha", "bravo", "charlie", "delta", "echo",
"foxtrot", "golf", "hotel", "inde", "juliette",
"kilo", "lima", "mike", "novembre", "oscar",
"papa", "quebec", "romeo", "sierra", "tango",
"uniforme", "victor", "whisky", "x-ray", "rikain",
"zoulou"
};
int
main ()
{
ENTRY e, *ep;
int i;
/* On commence avec une petite table, qu'on agrandit ensuite */
hcreate(3);
for (i = 0; i < 24; i++) {
e.key = data[i];
/* Les donnes sont de simples entiers, pas des pointeur */
e.data = (char *)i;
ep = hsearch(e, ENTER);
/* Il ne devrait pas y avoir d'chec */
if (ep == NULL) {
fprintf (stderr, "Echec\\n"); exit(1);}
}
for (i = 22; i < 26; i++) {
/* Afficher 2 entres, et vrifier que 2 autres sont absentes */
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);
}
return (0);
}
.fi
.SH "VOIR AUSSI"
.BR bsearch "(3), " lsearch "(3), " malloc "(3)"
.SH TRADUCTION
Christophe Blaess, 1997.
|
