clqr-hash-tables.tex

   1 % Copyright (C) 2008 Bert Burgemeister
   2 %
   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.
   8 %
   9
  10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  11 \section{Hash Tables}
  12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  13 Key-value storage similar to hash tables can as well be achieved with
  14 association lists and with property lists; see
  15 pp.\ \pageref{section:Association Lists} and
  16 \pageref{:property_lists}.
  17
  18
  19 \begin{LIST}{1cm}
  20
  21   \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  22   Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  23
  24   \IT{(\FU*{MAKE-HASH-TABLE}
  25     \orGOO{\kwd{:test}\Goo{\kwd{\#'eq}\XOR \kwd{\#'eql}\XOR \kwd{\#'equal}}\DF{\kwd{eql}}\\
  26       \kwd{:size} \VAR{ size}\\
  27       \kwd{:rehash-size} \VAR{ rehash-size}\\
  28       \kwd{:rehash-threshold} \VAR{ rehash-threshold}}{\}})}
  29   Make a \retval{hash table}.
  30
  31   \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})} \retval{Test function}
  32   used in \VAR{hash-table}.
  33
  34   \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}})} Get
  35   \retval{object with key \VAR{key} } if any or \retval{\VAR{default}}
  36   otherwise. Second return value: \T\ if found, \NIL\ otherwise
  37
  38   \IT{(\FU*{REMHASH} \VAR{key} \VAR{hash-table})}
  39   Remove from \VAR{hash-table} entry with \VAR{key} and return \retval{\T} if it
  40   existed. Return \retval{\NIL} otherwise.
  41
  42   \IT{(\FU*{CLRHASH} \VAR{hash-table})}
  43   Empty \retval{\VAR{hash-table}}.
  44
  45
  46   \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})} \retval{Number of entries} in \VAR{hash-table}.
  47
  48   \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
  49       (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
  50       (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{\}}}
  51   Current \retval{size}, \retval{rehash-size}, or
  52   \retval{rehash-threshold}, resp., as used in \FU{make-hash-table}.
  53
  54   \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  55   Iterate over \VAR{hash-table} calling \VAR{function} on \VAR{key}
  56   and \VAR{value}. Return \retval{\NIL}.
  57
  58   \IT{(\SF*{WITH-HASH-TABLE-ITERATOR} \VAR{name} \VAR{hash-table}
  59     \OPn{(\kwd{declare} \OPn{\VAR{decl}})} \OPn{form})}
  60   Return \retval{values of \VAR{form}s}. In the body, successive
  61   invocations of  (\VAR{name}) return: \T\ if an entry is returned;
  62   its key; its value.
  63
  64   \IT{(\FU*{SXHASH} \VAR{foo})} \retval{Hash code} of \VAR{foo}.
  65
  66 \end{LIST}
  67
  68