clqr-hash-tables.tex

% Copyright (C) 2008, 2009 Bert Burgemeister
%
% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.2 or any later version published by the Free Software
% Foundation; with no Invariant Sections, no Front-Cover Texts and
% no Back-Cover Texts. For details see file COPYING.
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Hash Tables} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Key-value storage similar to hash tables can as well be achieved using
association lists and property lists; see
pages \pageref{section:Association Lists} and \pageref{:property_lists}. 


\begin{LIST}{1cm}

  \IT{(\FU*{HASH-TABLE-P} \VAR{foo})}
  {
  Return \retval{\T} if \VAR{foo} is of type \kwd{hash-table}.
  }

  \IT{(\FU*{MAKE-HASH-TABLE} 
    \orGOO{\kwd{:test }\Goo{\FU{eq}\XOR \FU{eql}\XOR
        \FU{equal} \XOR \FU{equalp}}\DF{\kwd{\#'eql}}\\ 
      \kwd{:size} \VAR{ int}\\
      \kwd{:rehash-size} \VAR{ num}\\
      \kwd{:rehash-threshold} \VAR{ num}}{\}})}
  {
  Make a \retval{hash table}. 
  }

  \IT{(\FU*{GETHASH} \VAR{key} \VAR{hash-table} \Op{\VAR{default}\DF{\NIL}})}
  {
  Return \retval{object} with \VAR{key} if any or \retval{\VAR{default}}
  otherwise; and \retvalii{\T} if found, \retvalii{\NIL}
  otherwise. \kwd{setf}able. 
  }

  \IT{(\FU*{HASH-TABLE-COUNT} \VAR{hash-table})}
  {
  \retval{Number of entries} in \VAR{hash-table}.
  }

  \IT{(\FU*{REMHASH} \VAR{key} \DES{\VAR{hash-table}})}
  {
  Remove from \VAR{hash-table} entry with \VAR{key} and return
  \retval{\T} if it existed. Return \retval{\NIL} otherwise. 
  }

  \IT{(\FU*{CLRHASH} \DES{\VAR{hash-table}})}
  {
  Empty \retval{\VAR{hash-table}}.
  }

  \IT{(\FU*{MAPHASH} \VAR{function} \VAR{hash-table})}
  {
  Iterate over \VAR{hash-table} calling \VAR{function} on key
  and value. Return \retval{\NIL}.
  }

  \IT{(\MC*{WITH-HASH-TABLE-ITERATOR} (\VAR{foo} \VAR{hash-table})
    \OPn{(\kwd{declare} \OPn{\NEV{\VAR{decl}}})} \PROGN{\VAR{form}})}
  {
  Return \retval{values of \VAR{form}s}. In \VAR{form}s,
  invocations of  (\VAR{foo}) return: \T\ if an entry is returned;
  its key; its value.
  }

  \IT{(\FU*{HASH-TABLE-TEST} \VAR{hash-table})}
  {
  \retval{Test function} used in \VAR{hash-table}.
  }

  \IT{\arrGOO{(\FU*{HASH-TABLE-SIZE} \VAR{ hash-table})\\
      (\FU*{HASH-TABLE-REHASH-SIZE} \VAR{ hash-table})\\
      (\FU*{HASH-TABLE-REHASH-THRESHOLD} \VAR{ hash-table})}{.}}
  {
  Current \retval{size}, \retval{rehash-size}, or
  \retval{rehash-threshold}, respectively, as used in \FU{make-hash-table}. 
  }

  \IT{(\FU*{SXHASH} \VAR{foo})}
     {
       \retval{Hash code} unique for any argument \FU{equal} \VAR{foo}.
     }

\end{LIST}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "clqr"
%%% End: