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 using
  14 association lists and property lists; see
  15 pages \pageref{section:Association Lists} and \pageref{:property_lists}.
  16
  17
  18 \begin{LIST}{1cm}
  19
  20   \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  21   {
  22   Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  23   }
  24
  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}}{\}})}
  31   {
  32   Make a \retval{hash table}.
  33   }
  34
  35   \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}\DF{\NIL}})}
  36   {
  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.
  40   }
  41
  42   \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
  43   {
  44   \retval{Number of entries} in \VAR{hash-table}.
  45   }
  46
  47   \IT{(\FU*{REMHASH} \VAR{key} \DES{\VAR{hash-table}})}
  48   {
  49   Remove from \VAR{hash-table} entry with \VAR{key} and return
  50   \retval{\T} if it existed. Return \retval{\NIL} otherwise.
  51   }
  52
  53   \IT{(\FU*{CLRHASH} \DES{\VAR{hash-table}})}
  54   {
  55   Empty \retval{\VAR{hash-table}}.
  56   }
  57
  58   \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  59   {
  60   Iterate over \VAR{hash-table} calling \VAR{function} on key
  61   and value. Return \retval{\NIL}.
  62   }
  63
  64   \IT{(\MC*{WITH-HASH-TABLE-ITERATOR} (\VAR{foo} \VAR{hash-table})
  65     \OPn{(\kwd{declare} \OPn{\NEV{\VAR{decl}}})} \PROGN{\VAR{form}})}
  66   {
  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.
  70   }
  71
  72   \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})}
  73   {
  74   \retval{Test function} used in \VAR{hash-table}.
  75   }
  76
  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})}{.}}
  80   {
  81   Current \retval{size}, \retval{rehash-size}, or
  82   \retval{rehash-threshold}, respectively, as used in \FU{make-hash-table}.
  83   }
  84
  85   \IT{(\FU*{SXHASH} \VAR{foo})}
  86      {
  87        \retval{Hash code} unique for any argument \FU{equal} \VAR{foo}.
  88      }
  89
  90 \end{LIST}
  91
  92
  93
  94 %%% Local Variables:
  95 %%% mode: latex
  96 %%% TeX-master: "clqr"
  97 %%% End: