clqr-hash-tables.tex

   1 % Copyright (C) 2008, 2009, 2012 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 The Loop Facility provides additional hash table-related
  14 functionality; see \kwd{loop}, page \pageref{section:Loop Facility}.
  15
  16 Key-value storage similar to hash tables can as well be achieved using
  17 association lists and property lists; see
  18 pages \pageref{section:Association Lists} and \pageref{:property_lists}.
  19
  20
  21 \begin{LIST}{1cm}
  22
  23   \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  24   {
  25   Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  26   }
  27
  28   \IT{(\FU*{MAKE-HASH-TABLE}
  29     \orGOO{\kwd{:test }\Goo{\FU{eq}\XOR \FU{eql}\XOR
  30         \FU{equal} \XOR \FU{equalp}}\DF{\kwd{\#'eql}}\\
  31       \kwd{:size} \VAR{ int}\\
  32       \kwd{:rehash-size} \VAR{ num}\\
  33       \kwd{:rehash-threshold} \VAR{ num}}{\}})}
  34   {
  35   Make a \retval{hash table}.
  36   }
  37
  38   \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}\DF{\NIL}})}
  39   {
  40   Return \retval{object} with \VAR{key} if any or \retval{\VAR{default}}
  41   otherwise; and \retvalii{\T} if found, \retvalii{\NIL}
  42   otherwise. \kwd{setf}able.
  43   }
  44
  45   \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
  46   {
  47   \retval{Number of entries} in \VAR{hash-table}.
  48   }
  49
  50   \IT{(\FU*{REMHASH} \VAR{key} \DES{\VAR{hash-table}})}
  51   {
  52   Remove from \VAR{hash-table} entry with \VAR{key} and return
  53   \retval{\T} if it existed. Return \retval{\NIL} otherwise.
  54   }
  55
  56   \IT{(\FU*{CLRHASH} \DES{\VAR{hash-table}})}
  57   {
  58   Empty \retval{\VAR{hash-table}}.
  59   }
  60
  61   \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  62   {
  63   Iterate over \VAR{hash-table} calling \VAR{function} on key
  64   and value. Return \retval{\NIL}.
  65   }
  66
  67   \IT{(\MC*{WITH-HASH-TABLE-ITERATOR} (\VAR{foo} \VAR{hash-table})
  68     \OPn{(\kwd{declare} \OPn{\NEV{\VAR{decl}}})} \PROGN{\VAR{form}})}
  69   {
  70   Return \retval{values of \VAR{form}s}. In \VAR{form}s,
  71   invocations of  (\VAR{foo}) return: \T\ if an entry is returned;
  72   its key; its value.
  73   }
  74
  75   \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})}
  76   {
  77   \retval{Test function} used in \VAR{hash-table}.
  78   }
  79
  80   \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
  81       (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
  82       (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{.}}
  83   {
  84   Current \retval{size}, \retval{rehash-size}, or
  85   \retval{rehash-threshold}, respectively, as used in \FU{make-hash-table}.
  86   }
  87
  88   \IT{(\FU*{SXHASH} \VAR{foo})}
  89      {
  90        \retval{Hash code} unique for any argument \FU{equal} \VAR{foo}.
  91      }
  92
  93 \end{LIST}
  94
  95
  96
  97 %%% Local Variables:
  98 %%% mode: latex
  99 %%% TeX-master: "clqr"
 100 %%% End: