diff options
Diffstat (limited to 'secure/lib/libcrypto/man/lhash.3')
| -rw-r--r-- | secure/lib/libcrypto/man/lhash.3 | 438 |
1 files changed, 0 insertions, 438 deletions
diff --git a/secure/lib/libcrypto/man/lhash.3 b/secure/lib/libcrypto/man/lhash.3 deleted file mode 100644 index 4fdbabb46763..000000000000 --- a/secure/lib/libcrypto/man/lhash.3 +++ /dev/null @@ -1,438 +0,0 @@ -.\" Automatically generated by Pod::Man version 1.15 -.\" Wed Feb 19 16:43:05 2003 -.\" -.\" Standard preamble: -.\" ====================================================================== -.de Sh \" Subsection heading -.br -.if t .Sp -.ne 5 -.PP -\fB\\$1\fR -.PP -.. -.de Sp \" Vertical space (when we can't use .PP) -.if t .sp .5v -.if n .sp -.. -.de Ip \" List item -.br -.ie \\n(.$>=3 .ne \\$3 -.el .ne 3 -.IP "\\$1" \\$2 -.. -.de Vb \" Begin verbatim text -.ft CW -.nf -.ne \\$1 -.. -.de Ve \" End verbatim text -.ft R - -.fi -.. -.\" Set up some character translations and predefined strings. \*(-- will -.\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left -.\" double quote, and \*(R" will give a right double quote. | will give a -.\" real vertical bar. \*(C+ will give a nicer C++. Capital omega is used -.\" to do unbreakable dashes and therefore won't be available. \*(C` and -.\" \*(C' expand to `' in nroff, nothing in troff, for use with C<> -.tr \(*W-|\(bv\*(Tr -.ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' -.ie n \{\ -. ds -- \(*W- -. ds PI pi -. if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch -. if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch -. ds L" "" -. ds R" "" -. ds C` "" -. ds C' "" -'br\} -.el\{\ -. ds -- \|\(em\| -. ds PI \(*p -. ds L" `` -. ds R" '' -'br\} -.\" -.\" If the F register is turned on, we'll generate index entries on stderr -.\" for titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and -.\" index entries marked with X<> in POD. Of course, you'll have to process -.\" the output yourself in some meaningful fashion. -.if \nF \{\ -. de IX -. tm Index:\\$1\t\\n%\t"\\$2" -.. -. nr % 0 -. rr F -.\} -.\" -.\" For nroff, turn off justification. Always turn off hyphenation; it -.\" makes way too many mistakes in technical documents. -.hy 0 -.if n .na -.\" -.\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). -.\" Fear. Run. Save yourself. No user-serviceable parts. -.bd B 3 -. \" fudge factors for nroff and troff -.if n \{\ -. ds #H 0 -. ds #V .8m -. ds #F .3m -. ds #[ \f1 -. ds #] \fP -.\} -.if t \{\ -. ds #H ((1u-(\\\\n(.fu%2u))*.13m) -. ds #V .6m -. ds #F 0 -. ds #[ \& -. ds #] \& -.\} -. \" simple accents for nroff and troff -.if n \{\ -. ds ' \& -. ds ` \& -. ds ^ \& -. ds , \& -. ds ~ ~ -. ds / -.\} -.if t \{\ -. ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" -. ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' -. ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' -. ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' -. ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' -. ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' -.\} -. \" troff and (daisy-wheel) nroff accents -.ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' -.ds 8 \h'\*(#H'\(*b\h'-\*(#H' -.ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] -.ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' -.ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' -.ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] -.ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] -.ds ae a\h'-(\w'a'u*4/10)'e -.ds Ae A\h'-(\w'A'u*4/10)'E -. \" corrections for vroff -.if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' -.if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' -. \" for low resolution devices (crt and lpr) -.if \n(.H>23 .if \n(.V>19 \ -\{\ -. ds : e -. ds 8 ss -. ds o a -. ds d- d\h'-1'\(ga -. ds D- D\h'-1'\(hy -. ds th \o'bp' -. ds Th \o'LP' -. ds ae ae -. ds Ae AE -.\} -.rm #[ #] #H #V #F C -.\" ====================================================================== -.\" -.IX Title "lhash 3" -.TH lhash 3 "0.9.7a" "2003-02-19" "OpenSSL" -.UC -.SH "NAME" -lh_new, lh_free, lh_insert, lh_delete, lh_retrieve, lh_doall, lh_doall_arg, lh_error \- dynamic hash table -.SH "SYNOPSIS" -.IX Header "SYNOPSIS" -.Vb 1 -\& #include <openssl/lhash.h> -.Ve -.Vb 2 -\& LHASH *lh_new(LHASH_HASH_FN_TYPE hash, LHASH_COMP_FN_TYPE compare); -\& void lh_free(LHASH *table); -.Ve -.Vb 3 -\& void *lh_insert(LHASH *table, void *data); -\& void *lh_delete(LHASH *table, void *data); -\& void *lh_retrieve(LHASH *table, void *data); -.Ve -.Vb 3 -\& void lh_doall(LHASH *table, LHASH_DOALL_FN_TYPE func); -\& void lh_doall_arg(LHASH *table, LHASH_DOALL_ARG_FN_TYPE func, -\& void *arg); -.Ve -.Vb 1 -\& int lh_error(LHASH *table); -.Ve -.Vb 4 -\& typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *); -\& typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *); -\& typedef void (*LHASH_DOALL_FN_TYPE)(const void *); -\& typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *); -.Ve -.SH "DESCRIPTION" -.IX Header "DESCRIPTION" -This library implements dynamic hash tables. The hash table entries -can be arbitrary structures. Usually they consist of key and value -fields. -.PP -\&\fIlh_new()\fR creates a new \fB\s-1LHASH\s0\fR structure to store arbitrary data -entries, and provides the 'hash' and 'compare' callbacks to be used in -organising the table's entries. The \fBhash\fR callback takes a pointer -to a table entry as its argument and returns an unsigned long hash -value for its key field. The hash value is normally truncated to a -power of 2, so make sure that your hash function returns well mixed -low order bits. The \fBcompare\fR callback takes two arguments (pointers -to two hash table entries), and returns 0 if their keys are equal, -non-zero otherwise. If your hash table will contain items of some -particular type and the \fBhash\fR and \fBcompare\fR callbacks hash/compare -these types, then the \fB\s-1DECLARE_LHASH_HASH_FN\s0\fR and -\&\fB\s-1IMPLEMENT_LHASH_COMP_FN\s0\fR macros can be used to create callback -wrappers of the prototypes required by \fIlh_new()\fR. These provide -per-variable casts before calling the type-specific callbacks written -by the application author. These macros, as well as those used for -the \*(L"doall\*(R" callbacks, are defined as; -.PP -.Vb 7 -\& #define DECLARE_LHASH_HASH_FN(f_name,o_type) \e -\& unsigned long f_name##_LHASH_HASH(const void *); -\& #define IMPLEMENT_LHASH_HASH_FN(f_name,o_type) \e -\& unsigned long f_name##_LHASH_HASH(const void *arg) { \e -\& o_type a = (o_type)arg; \e -\& return f_name(a); } -\& #define LHASH_HASH_FN(f_name) f_name##_LHASH_HASH -.Ve -.Vb 8 -\& #define DECLARE_LHASH_COMP_FN(f_name,o_type) \e -\& int f_name##_LHASH_COMP(const void *, const void *); -\& #define IMPLEMENT_LHASH_COMP_FN(f_name,o_type) \e -\& int f_name##_LHASH_COMP(const void *arg1, const void *arg2) { \e -\& o_type a = (o_type)arg1; \e -\& o_type b = (o_type)arg2; \e -\& return f_name(a,b); } -\& #define LHASH_COMP_FN(f_name) f_name##_LHASH_COMP -.Ve -.Vb 7 -\& #define DECLARE_LHASH_DOALL_FN(f_name,o_type) \e -\& void f_name##_LHASH_DOALL(const void *); -\& #define IMPLEMENT_LHASH_DOALL_FN(f_name,o_type) \e -\& void f_name##_LHASH_DOALL(const void *arg) { \e -\& o_type a = (o_type)arg; \e -\& f_name(a); } -\& #define LHASH_DOALL_FN(f_name) f_name##_LHASH_DOALL -.Ve -.Vb 8 -\& #define DECLARE_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \e -\& void f_name##_LHASH_DOALL_ARG(const void *, const void *); -\& #define IMPLEMENT_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \e -\& void f_name##_LHASH_DOALL_ARG(const void *arg1, const void *arg2) { \e -\& o_type a = (o_type)arg1; \e -\& a_type b = (a_type)arg2; \e -\& f_name(a,b); } -\& #define LHASH_DOALL_ARG_FN(f_name) f_name##_LHASH_DOALL_ARG -.Ve -An example of a hash table storing (pointers to) structures of type '\s-1STUFF\s0' -could be defined as follows; -.PP -.Vb 14 -\& /* Calculates the hash value of 'tohash' (implemented elsewhere) */ -\& unsigned long STUFF_hash(const STUFF *tohash); -\& /* Orders 'arg1' and 'arg2' (implemented elsewhere) */ -\& int STUFF_cmp(const STUFF *arg1, const STUFF *arg2); -\& /* Create the type-safe wrapper functions for use in the LHASH internals */ -\& static IMPLEMENT_LHASH_HASH_FN(STUFF_hash, const STUFF *) -\& static IMPLEMENT_LHASH_COMP_FN(STUFF_cmp, const STUFF *); -\& /* ... */ -\& int main(int argc, char *argv[]) { -\& /* Create the new hash table using the hash/compare wrappers */ -\& LHASH *hashtable = lh_new(LHASH_HASH_FN(STUFF_hash), -\& LHASH_COMP_FN(STUFF_cmp)); -\& /* ... */ -\& } -.Ve -\&\fIlh_free()\fR frees the \fB\s-1LHASH\s0\fR structure \fBtable\fR. Allocated hash table -entries will not be freed; consider using \fIlh_doall()\fR to deallocate any -remaining entries in the hash table (see below). -.PP -\&\fIlh_insert()\fR inserts the structure pointed to by \fBdata\fR into \fBtable\fR. -If there already is an entry with the same key, the old value is -replaced. Note that \fIlh_insert()\fR stores pointers, the data are not -copied. -.PP -\&\fIlh_delete()\fR deletes an entry from \fBtable\fR. -.PP -\&\fIlh_retrieve()\fR looks up an entry in \fBtable\fR. Normally, \fBdata\fR is -a structure with the key \fIfield\fR\|(s) set; the function will return a -pointer to a fully populated structure. -.PP -\&\fIlh_doall()\fR will, for every entry in the hash table, call \fBfunc\fR with -the data item as its parameter. For \fIlh_doall()\fR and \fIlh_doall_arg()\fR, -function pointer casting should be avoided in the callbacks (see -\&\fB\s-1NOTE\s0\fR) \- instead, either declare the callbacks to match the -prototype required in \fIlh_new()\fR or use the declare/implement macros to -create type-safe wrappers that cast variables prior to calling your -type-specific callbacks. An example of this is illustrated here where -the callback is used to cleanup resources for items in the hash table -prior to the hashtable itself being deallocated: -.PP -.Vb 9 -\& /* Cleans up resources belonging to 'a' (this is implemented elsewhere) */ -\& void STUFF_cleanup(STUFF *a); -\& /* Implement a prototype-compatible wrapper for "STUFF_cleanup" */ -\& IMPLEMENT_LHASH_DOALL_FN(STUFF_cleanup, STUFF *) -\& /* ... then later in the code ... */ -\& /* So to run "STUFF_cleanup" against all items in a hash table ... */ -\& lh_doall(hashtable, LHASH_DOALL_FN(STUFF_cleanup)); -\& /* Then the hash table itself can be deallocated */ -\& lh_free(hashtable); -.Ve -When doing this, be careful if you delete entries from the hash table -in your callbacks: the table may decrease in size, moving the item -that you are currently on down lower in the hash table \- this could -cause some entries to be skipped during the iteration. The second -best solution to this problem is to set hash->down_load=0 before -you start (which will stop the hash table ever decreasing in size). -The best solution is probably to avoid deleting items from the hash -table inside a \*(L"doall\*(R" callback! -.PP -\&\fIlh_doall_arg()\fR is the same as \fIlh_doall()\fR except that \fBfunc\fR will be -called with \fBarg\fR as the second argument and \fBfunc\fR should be of -type \fB\s-1LHASH_DOALL_ARG_FN_TYPE\s0\fR (a callback prototype that is passed -both the table entry and an extra argument). As with \fIlh_doall()\fR, you -can instead choose to declare your callback with a prototype matching -the types you are dealing with and use the declare/implement macros to -create compatible wrappers that cast variables before calling your -type-specific callbacks. An example of this is demonstrated here -(printing all hash table entries to a \s-1BIO\s0 that is provided by the -caller): -.PP -.Vb 7 -\& /* Prints item 'a' to 'output_bio' (this is implemented elsewhere) */ -\& void STUFF_print(const STUFF *a, BIO *output_bio); -\& /* Implement a prototype-compatible wrapper for "STUFF_print" */ -\& static IMPLEMENT_LHASH_DOALL_ARG_FN(STUFF_print, const STUFF *, BIO *) -\& /* ... then later in the code ... */ -\& /* Print out the entire hashtable to a particular BIO */ -\& lh_doall_arg(hashtable, LHASH_DOALL_ARG_FN(STUFF_print), logging_bio); -.Ve -\&\fIlh_error()\fR can be used to determine if an error occurred in the last -operation. \fIlh_error()\fR is a macro. -.SH "RETURN VALUES" -.IX Header "RETURN VALUES" -\&\fIlh_new()\fR returns \fB\s-1NULL\s0\fR on error, otherwise a pointer to the new -\&\fB\s-1LHASH\s0\fR structure. -.PP -When a hash table entry is replaced, \fIlh_insert()\fR returns the value -being replaced. \fB\s-1NULL\s0\fR is returned on normal operation and on error. -.PP -\&\fIlh_delete()\fR returns the entry being deleted. \fB\s-1NULL\s0\fR is returned if -there is no such value in the hash table. -.PP -\&\fIlh_retrieve()\fR returns the hash table entry if it has been found, -\&\fB\s-1NULL\s0\fR otherwise. -.PP -\&\fIlh_error()\fR returns 1 if an error occurred in the last operation, 0 -otherwise. -.PP -\&\fIlh_free()\fR, \fIlh_doall()\fR and \fIlh_doall_arg()\fR return no values. -.SH "NOTE" -.IX Header "NOTE" -The various \s-1LHASH\s0 macros and callback types exist to make it possible -to write type-safe code without resorting to function-prototype -casting \- an evil that makes application code much harder to -audit/verify and also opens the window of opportunity for stack -corruption and other hard-to-find bugs. It also, apparently, violates -\&\s-1ANSI-C\s0. -.PP -The \s-1LHASH\s0 code regards table entries as constant data. As such, it -internally represents \fIlh_insert()\fR'd items with a \*(L"const void *\*(R" -pointer type. This is why callbacks such as those used by \fIlh_doall()\fR -and \fIlh_doall_arg()\fR declare their prototypes with \*(L"const\*(R", even for the -parameters that pass back the table items' data pointers \- for -consistency, user-provided data is \*(L"const\*(R" at all times as far as the -\&\s-1LHASH\s0 code is concerned. However, as callers are themselves providing -these pointers, they can choose whether they too should be treating -all such parameters as constant. -.PP -As an example, a hash table may be maintained by code that, for -reasons of encapsulation, has only \*(L"const\*(R" access to the data being -indexed in the hash table (ie. it is returned as \*(L"const\*(R" from -elsewhere in their code) \- in this case the \s-1LHASH\s0 prototypes are -appropriate as-is. Conversely, if the caller is responsible for the -life-time of the data in question, then they may well wish to make -modifications to table item passed back in the \fIlh_doall()\fR or -\&\fIlh_doall_arg()\fR callbacks (see the \*(L"STUFF_cleanup\*(R" example above). If -so, the caller can either cast the \*(L"const\*(R" away (if they're providing -the raw callbacks themselves) or use the macros to declare/implement -the wrapper functions without \*(L"const\*(R" types. -.PP -Callers that only have \*(L"const\*(R" access to data they're indexing in a -table, yet declare callbacks without constant types (or cast the -\&\*(L"const\*(R" away themselves), are therefore creating their own risks/bugs -without being encouraged to do so by the \s-1API\s0. On a related note, -those auditing code should pay special attention to any instances of -DECLARE/IMPLEMENT_LHASH_DOALL_[\s-1ARG_\s0]_FN macros that provide types -without any \*(L"const\*(R" qualifiers. -.SH "BUGS" -.IX Header "BUGS" -\&\fIlh_insert()\fR returns \fB\s-1NULL\s0\fR both for success and error. -.SH "INTERNALS" -.IX Header "INTERNALS" -The following description is based on the SSLeay documentation: -.PP -The \fBlhash\fR library implements a hash table described in the -\&\fICommunications of the \s-1ACM\s0\fR in 1991. What makes this hash table -different is that as the table fills, the hash table is increased (or -decreased) in size via \fIOPENSSL_realloc()\fR. When a 'resize' is done, instead of -all hashes being redistributed over twice as many 'buckets', one -bucket is split. So when an 'expand' is done, there is only a minimal -cost to redistribute some values. Subsequent inserts will cause more -single 'bucket' redistributions but there will never be a sudden large -cost due to redistributing all the 'buckets'. -.PP -The state for a particular hash table is kept in the \fB\s-1LHASH\s0\fR structure. -The decision to increase or decrease the hash table size is made -depending on the 'load' of the hash table. The load is the number of -items in the hash table divided by the size of the hash table. The -default values are as follows. If (hash->up_load < load) => -expand. if (hash->down_load > load) => contract. The -\&\fBup_load\fR has a default value of 1 and \fBdown_load\fR has a default value -of 2. These numbers can be modified by the application by just -playing with the \fBup_load\fR and \fBdown_load\fR variables. The 'load' is -kept in a form which is multiplied by 256. So -hash->up_load=8*256; will cause a load of 8 to be set. -.PP -If you are interested in performance the field to watch is -num_comp_calls. The hash library keeps track of the 'hash' value for -each item so when a lookup is done, the 'hashes' are compared, if -there is a match, then a full compare is done, and -hash->num_comp_calls is incremented. If num_comp_calls is not equal -to num_delete plus num_retrieve it means that your hash function is -generating hashes that are the same for different values. It is -probably worth changing your hash function if this is the case because -even if your hash table has 10 items in a 'bucket', it can be searched -with 10 \fBunsigned long\fR compares and 10 linked list traverses. This -will be much less expensive that 10 calls to your compare function. -.PP -\&\fIlh_strhash()\fR is a demo string hashing function: -.PP -.Vb 1 -\& unsigned long lh_strhash(const char *c); -.Ve -Since the \fB\s-1LHASH\s0\fR routines would normally be passed structures, this -routine would not normally be passed to \fIlh_new()\fR, rather it would be -used in the function passed to \fIlh_new()\fR. -.SH "SEE ALSO" -.IX Header "SEE ALSO" -lh_stats(3) -.SH "HISTORY" -.IX Header "HISTORY" -The \fBlhash\fR library is available in all versions of SSLeay and OpenSSL. -\&\fIlh_error()\fR was added in SSLeay 0.9.1b. -.PP -This manpage is derived from the SSLeay documentation. -.PP -In OpenSSL 0.9.7, all lhash functions that were passed function pointers -were changed for better type safety, and the function types \s-1LHASH_COMP_FN_TYPE\s0, -\&\s-1LHASH_HASH_FN_TYPE\s0, \s-1LHASH_DOALL_FN_TYPE\s0 and \s-1LHASH_DOALL_ARG_FN_TYPE\s0 -became available. |