secure/lib/libcrypto/man/lhash.3

   1 .\" Automatically generated by Pod::Man version 1.15
   2 .\" Tue Jul 30 09:22:07 2002
   3 .\"
   4 .\" Standard preamble:
   5 .\" ======================================================================
   6 .de Sh \" Subsection heading
   7 .br
   8 .if t .Sp
   9 .ne 5
  10 .PP
  11 \fB\\$1\fR
  12 .PP
  13 ..
  14 .de Sp \" Vertical space (when we can't use .PP)
  15 .if t .sp .5v
  16 .if n .sp
  17 ..
  18 .de Ip \" List item
  19 .br
  20 .ie \\n(.$>=3 .ne \\$3
  21 .el .ne 3
  22 .IP "\\$1" \\$2
  23 ..
  24 .de Vb \" Begin verbatim text
  25 .ft CW
  26 .nf
  27 .ne \\$1
  28 ..
  29 .de Ve \" End verbatim text
  30 .ft R
  31
  32 .fi
  33 ..
  34 .\" Set up some character translations and predefined strings.  \*(-- will
  35 .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
  36 .\" double quote, and \*(R" will give a right double quote.  | will give a
  37 .\" real vertical bar.  \*(C+ will give a nicer C++.  Capital omega is used
  38 .\" to do unbreakable dashes and therefore won't be available.  \*(C` and
  39 .\" \*(C' expand to `' in nroff, nothing in troff, for use with C<>
  40 .tr \(*W-|\(bv\*(Tr
  41 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
  42 .ie n \{\
  43 .    ds -- \(*W-
  44 .    ds PI pi
  45 .    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
  46 .    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
  47 .    ds L" ""
  48 .    ds R" ""
  49 .    ds C` ""
  50 .    ds C' ""
  51 'br\}
  52 .el\{\
  53 .    ds -- \|\(em\|
  54 .    ds PI \(*p
  55 .    ds L" ``
  56 .    ds R" ''
  57 'br\}
  58 .\"
  59 .\" If the F register is turned on, we'll generate index entries on stderr
  60 .\" for titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and
  61 .\" index entries marked with X<> in POD.  Of course, you'll have to process
  62 .\" the output yourself in some meaningful fashion.
  63 .if \nF \{\
  64 .    de IX
  65 .    tm Index:\\$1\t\\n%\t"\\$2"
  66 ..
  67 .    nr % 0
  68 .    rr F
  69 .\}
  70 .\"
  71 .\" For nroff, turn off justification.  Always turn off hyphenation; it
  72 .\" makes way too many mistakes in technical documents.
  73 .hy 0
  74 .if n .na
  75 .\"
  76 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
  77 .\" Fear.  Run.  Save yourself.  No user-serviceable parts.
  78 .bd B 3
  79 .    \" fudge factors for nroff and troff
  80 .if n \{\
  81 .    ds #H 0
  82 .    ds #V .8m
  83 .    ds #F .3m
  84 .    ds #[ \f1
  85 .    ds #] \fP
  86 .\}
  87 .if t \{\
  88 .    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
  89 .    ds #V .6m
  90 .    ds #F 0
  91 .    ds #[ \&
  92 .    ds #] \&
  93 .\}
  94 .    \" simple accents for nroff and troff
  95 .if n \{\
  96 .    ds ' \&
  97 .    ds ` \&
  98 .    ds ^ \&
  99 .    ds , \&
 100 .    ds ~ ~
 101 .    ds /
 102 .\}
 103 .if t \{\
 104 .    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
 105 .    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
 106 .    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
 107 .    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
 108 .    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
 109 .    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
 110 .\}
 111 .    \" troff and (daisy-wheel) nroff accents
 112 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
 113 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
 114 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
 115 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
 116 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
 117 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
 118 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
 119 .ds ae a\h'-(\w'a'u*4/10)'e
 120 .ds Ae A\h'-(\w'A'u*4/10)'E
 121 .    \" corrections for vroff
 122 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
 123 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
 124 .    \" for low resolution devices (crt and lpr)
 125 .if \n(.H>23 .if \n(.V>19 \
 126 \{\
 127 .    ds : e
 128 .    ds 8 ss
 129 .    ds o a
 130 .    ds d- d\h'-1'\(ga
 131 .    ds D- D\h'-1'\(hy
 132 .    ds th \o'bp'
 133 .    ds Th \o'LP'
 134 .    ds ae ae
 135 .    ds Ae AE
 136 .\}
 137 .rm #[ #] #H #V #F C
 138 .\" ======================================================================
 139 .\"
 140 .IX Title "lhash 3"
 141 .TH lhash 3 "0.9.6e" "2000-11-12" "OpenSSL"
 142 .UC
 143 .SH "NAME"
 144 lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall,
 145 lh_doall_arg, lh_error \- dynamic hash table
 146 .SH "SYNOPSIS"
 147 .IX Header "SYNOPSIS"
 148 .Vb 1
 149 \& #include <openssl/lhash.h>
 150 .Ve
 151 .Vb 3
 152 \& LHASH *lh_new(unsigned long (*hash)(/*void *a*/),
 153 \&          int (*compare)(/*void *a,void *b*/));
 154 \& void lh_free(LHASH *table);
 155 .Ve
 156 .Vb 3
 157 \& void *lh_insert(LHASH *table, void *data);
 158 \& void *lh_delete(LHASH *table, void *data);
 159 \& void *lh_retrieve(LHASH *table, void *data);
 160 .Ve
 161 .Vb 3
 162 \& void lh_doall(LHASH *table, void (*func)(/*void *b*/));
 163 \& void lh_doall_arg(LHASH *table, void (*func)(/*void *a,void *b*/),
 164 \&          void *arg);
 165 .Ve
 166 .Vb 1
 167 \& int lh_error(LHASH *table);
 168 .Ve
 169 .SH "DESCRIPTION"
 170 .IX Header "DESCRIPTION"
 171 This library implements dynamic hash tables. The hash table entries
 172 can be arbitrary structures. Usually they consist of key and value
 173 fields.
 174 .PP
 175 \&\fIlh_new()\fR creates a new \fB\s-1LHASH\s0\fR structure. \fBhash\fR takes a pointer to
 176 the structure and returns an unsigned long hash value of its key
 177 field. The hash value is normally truncated to a power of 2, so make
 178 sure that your hash function returns well mixed low order
 179 bits. \fBcompare\fR takes two arguments, and returns 0 if their keys are
 180 equal, non-zero otherwise.
 181 .PP
 182 \&\fIlh_free()\fR frees the \fB\s-1LHASH\s0\fR structure \fBtable\fR. Allocated hash table
 183 entries will not be freed; consider using \fIlh_doall()\fR to deallocate any
 184 remaining entries in the hash table.
 185 .PP
 186 \&\fIlh_insert()\fR inserts the structure pointed to by \fBdata\fR into \fBtable\fR.
 187 If there already is an entry with the same key, the old value is
 188 replaced. Note that \fIlh_insert()\fR stores pointers, the data are not
 189 copied.
 190 .PP
 191 \&\fIlh_delete()\fR deletes an entry from \fBtable\fR.
 192 .PP
 193 \&\fIlh_retrieve()\fR looks up an entry in \fBtable\fR. Normally, \fBdata\fR is
 194 a structure with the key \fIfield\fR\|(s) set; the function will return a
 195 pointer to a fully populated structure.
 196 .PP
 197 \&\fIlh_doall()\fR will, for every entry in the hash table, call \fBfunc\fR with
 198 the data item as parameters.
 199 This function can be quite useful when used as follows:
 200  void cleanup(\s-1STUFF\s0 *a)
 201   { \fISTUFF_free\fR\|(a); }
 202  lh_doall(hash,cleanup);
 203  lh_free(hash);
 204 This can be used to free all the entries. \fIlh_free()\fR then cleans up the
 205 \&'buckets' that point to nothing. When doing this, be careful if you
 206 delete entries from the hash table in \fBfunc\fR: the table may decrease
 207 in size, moving item that you are currently on down lower in the hash
 208 table.  This could cause some entries to be skipped.  The best
 209 solution to this problem is to set hash->down_load=0 before you
 210 start.  This will stop the hash table ever being decreased in size.
 211 .PP
 212 \&\fIlh_doall_arg()\fR is the same as \fIlh_doall()\fR except that \fBfunc\fR will
 213 be called with \fBarg\fR as the second argument.
 214 .PP
 215 \&\fIlh_error()\fR can be used to determine if an error occurred in the last
 216 operation. \fIlh_error()\fR is a macro.
 217 .SH "RETURN VALUES"
 218 .IX Header "RETURN VALUES"
 219 \&\fIlh_new()\fR returns \fB\s-1NULL\s0\fR on error, otherwise a pointer to the new
 220 \&\fB\s-1LHASH\s0\fR structure.
 221 .PP
 222 When a hash table entry is replaced, \fIlh_insert()\fR returns the value
 223 being replaced. \fB\s-1NULL\s0\fR is returned on normal operation and on error.
 224 .PP
 225 \&\fIlh_delete()\fR returns the entry being deleted.  \fB\s-1NULL\s0\fR is returned if
 226 there is no such value in the hash table.
 227 .PP
 228 \&\fIlh_retrieve()\fR returns the hash table entry if it has been found,
 229 \&\fB\s-1NULL\s0\fR otherwise.
 230 .PP
 231 \&\fIlh_error()\fR returns 1 if an error occurred in the last operation, 0
 232 otherwise.
 233 .PP
 234 \&\fIlh_free()\fR, \fIlh_doall()\fR and \fIlh_doall_arg()\fR return no values.
 235 .SH "BUGS"
 236 .IX Header "BUGS"
 237 \&\fIlh_insert()\fR returns \fB\s-1NULL\s0\fR both for success and error.
 238 .SH "INTERNALS"
 239 .IX Header "INTERNALS"
 240 The following description is based on the SSLeay documentation:
 241 .PP
 242 The \fBlhash\fR library implements a hash table described in the
 243 \&\fICommunications of the \s-1ACM\s0\fR in 1991.  What makes this hash table
 244 different is that as the table fills, the hash table is increased (or
 245 decreased) in size via \fIOPENSSL_realloc()\fR.  When a 'resize' is done, instead of
 246 all hashes being redistributed over twice as many 'buckets', one
 247 bucket is split.  So when an 'expand' is done, there is only a minimal
 248 cost to redistribute some values.  Subsequent inserts will cause more
 249 single 'bucket' redistributions but there will never be a sudden large
 250 cost due to redistributing all the 'buckets'.
 251 .PP
 252 The state for a particular hash table is kept in the \fB\s-1LHASH\s0\fR structure.
 253 The decision to increase or decrease the hash table size is made
 254 depending on the 'load' of the hash table.  The load is the number of
 255 items in the hash table divided by the size of the hash table.  The
 256 default values are as follows.  If (hash->up_load < load) =>
 257 expand.  if (hash->down_load > load) => contract.  The
 258 \&\fBup_load\fR has a default value of 1 and \fBdown_load\fR has a default value
 259 of 2.  These numbers can be modified by the application by just
 260 playing with the \fBup_load\fR and \fBdown_load\fR variables.  The 'load' is
 261 kept in a form which is multiplied by 256.  So
 262 hash->up_load=8*256; will cause a load of 8 to be set.
 263 .PP
 264 If you are interested in performance the field to watch is
 265 num_comp_calls.  The hash library keeps track of the 'hash' value for
 266 each item so when a lookup is done, the 'hashes' are compared, if
 267 there is a match, then a full compare is done, and
 268 hash->num_comp_calls is incremented.  If num_comp_calls is not equal
 269 to num_delete plus num_retrieve it means that your hash function is
 270 generating hashes that are the same for different values.  It is
 271 probably worth changing your hash function if this is the case because
 272 even if your hash table has 10 items in a 'bucket', it can be searched
 273 with 10 \fBunsigned long\fR compares and 10 linked list traverses.  This
 274 will be much less expensive that 10 calls to you compare function.
 275 .PP
 276 \&\fIlh_strhash()\fR is a demo string hashing function:
 277 .PP
 278 .Vb 1
 279 \& unsigned long lh_strhash(const char *c);
 280 .Ve
 281 Since the \fB\s-1LHASH\s0\fR routines would normally be passed structures, this
 282 routine would not normally be passed to \fIlh_new()\fR, rather it would be
 283 used in the function passed to \fIlh_new()\fR.
 284 .SH "SEE ALSO"
 285 .IX Header "SEE ALSO"
 286 lh_stats(3)
 287 .SH "HISTORY"
 288 .IX Header "HISTORY"
 289 The \fBlhash\fR library is available in all versions of SSLeay and OpenSSL.
 290 \&\fIlh_error()\fR was added in SSLeay 0.9.1b.
 291 .PP
 292 This manpage is derived from the SSLeay documentation.