clqr-hash-tables.tex

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