Unfinished work on figure Data Types.
[clqr.git] / clqr-hash-tables.tex
blob9596433e67c0c7df46016e9f18c6bd9b7987159c
1 % Copyright (C) 2008, 2009 Bert Burgemeister
3 % Permission is granted to copy, distribute and/or modify this
4 % document under the terms of the GNU Free Documentation License,
5 % Version 1.2 or any later version published by the Free Software
6 % Foundation; with no Invariant Sections, no Front-Cover Texts and
7 % no Back-Cover Texts. For details see file COPYING.
10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11 \section{Hash Tables}
12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13 Key-value storage similar to hash tables can as well be achieved using
14 association lists and property lists; see
15 pages \pageref{section:Association Lists} and \pageref{:property_lists}.
18 \begin{LIST}{1cm}
20 \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
22 Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
25 \IT{(\FU*{MAKE-HASH-TABLE}
26 \orGOO{\kwd{:test }\Goo{\FU{eq}\XOR \FU{eql}\XOR
27 \FU{equal} \XOR \FU{equalp}}\DF{\kwd{\#'eql}}\\
28 \kwd{:size} \VAR{ int}\\
29 \kwd{:rehash-size} \VAR{ num}\\
30 \kwd{:rehash-threshold} \VAR{ num}}{\}})}
32 Make a \retval{hash table}.
35 \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}\DF{\NIL}})}
37 Return \retval{object} with \VAR{key} if any or \retval{\VAR{default}}
38 otherwise; and \retvalii{\T} if found, \retvalii{\NIL}
39 otherwise. \kwd{setf}able.
42 \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
44 \retval{Number of entries} in \VAR{hash-table}.
47 \IT{(\FU*{REMHASH} \VAR{key} \DES{\VAR{hash-table}})}
49 Remove from \VAR{hash-table} entry with \VAR{key} and return
50 \retval{\T} if it existed. Return \retval{\NIL} otherwise.
53 \IT{(\FU*{CLRHASH} \DES{\VAR{hash-table}})}
55 Empty \retval{\VAR{hash-table}}.
58 \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
60 Iterate over \VAR{hash-table} calling \VAR{function} on key
61 and value. Return \retval{\NIL}.
64 \IT{(\MC*{WITH-HASH-TABLE-ITERATOR} (\VAR{foo} \VAR{hash-table})
65 \OPn{(\kwd{declare} \OPn{\NEV{\VAR{decl}}})} \PROGN{\VAR{form}})}
67 Return \retval{values of \VAR{form}s}. In \VAR{form}s,
68 invocations of (\VAR{foo}) return: \T\ if an entry is returned;
69 its key; its value.
72 \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})}
74 \retval{Test function} used in \VAR{hash-table}.
77 \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
78 (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
79 (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{.}}
81 Current \retval{size}, \retval{rehash-size}, or
82 \retval{rehash-threshold}, respectively, as used in \FU{make-hash-table}.
85 \IT{(\FU*{SXHASH} \VAR{foo})}
87 \retval{Hash code} unique for any argument \FU{equal} \VAR{foo}.
90 \end{LIST}
94 %%% Local Variables:
95 %%% mode: latex
96 %%% TeX-master: "clqr"
97 %%% End: