Mercurial > hg > xemacs-beta
annotate man/lispref/hash-tables.texi @ 5908:6174848f3e6c
Use parse_integer() in read_atom(); support bases with ratios like integers
src/ChangeLog addition:
2015-05-08 Aidan Kehoe <kehoea@parhasard.net>
* data.c (init_errors_once_early):
Move the Qunsupported_type here from numbers.c, so it's available
when the majority of our types are not supported.
* general-slots.h: Add it here, too.
* number.c: Remove the definition of Qunsupported_type from here.
* lread.c (read_atom):
Check if the first character could reflect a rational, if so, call
parse_integer(), don't check the syntax of the other
characters. This allows us to accept the non-ASCII digit
characters too.
If that worked partially, but not completely, and the next char is
a slash, try to parse as a ratio.
If that fails, try isfloat_string(), but only if the first
character could plausibly be part of a float.
Otherwise, treat as a symbol.
* lread.c (read_rational):
Rename from read_integer. Handle ratios with the same radix
specification as was used for integers.
* lread.c (read1):
Rename read_integer in this function. Support the Common Lisp
#NNNrMMM syntax for parsing a number MMM of arbitrary radix NNN.
man/ChangeLog addition:
2015-05-08 Aidan Kehoe <kehoea@parhasard.net>
* lispref/numbers.texi (Numbers):
Describe the newly-supported arbitrary-base syntax for rationals
(integers and ratios). Describe that ratios can take the same base
specification as integers, something also new.
tests/ChangeLog addition:
2015-05-08 Aidan Kehoe <kehoea@parhasard.net>
* automated/lisp-reader-tests.el:
Check the arbitrary-base integer reader syntax support, just
added. Check the reader base support for ratios, just added.
Check the non-ASCII-digit support in the reader, just added.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Sat, 09 May 2015 00:40:57 +0100 |
| parents | 9fae6227ede5 |
| children |
| rev | line source |
|---|---|
| 428 | 1 @c -*-texinfo-*- |
| 2 @c This is part of the XEmacs Lisp Reference Manual. | |
| 3 @c Copyright (C) 1996 Ben Wing. | |
| 4 @c See the file lispref.texi for copying conditions. | |
| 5 @setfilename ../../info/hash-tables.info | |
|
5791
9fae6227ede5
Silence texinfo 5.2 warnings, primarily by adding next, prev, and up
Jerry James <james@xemacs.org>
parents:
5191
diff
changeset
|
6 @node Hash Tables, Range Tables, Display, Top |
| 428 | 7 @chapter Hash Tables |
| 8 @cindex hash table | |
| 9 | |
| 10 @defun hash-table-p object | |
| 11 This function returns @code{t} if @var{object} is a hash table, else @code{nil}. | |
| 12 @end defun | |
| 13 | |
| 14 @menu | |
| 15 * Introduction to Hash Tables:: Hash tables are fast data structures for | |
| 16 implementing simple tables (i.e. finite | |
| 17 mappings from keys to values). | |
| 18 * Working With Hash Tables:: Hash table functions. | |
| 19 * Weak Hash Tables:: Hash tables with special garbage-collection | |
| 20 behavior. | |
| 21 @end menu | |
| 22 | |
|
5791
9fae6227ede5
Silence texinfo 5.2 warnings, primarily by adding next, prev, and up
Jerry James <james@xemacs.org>
parents:
5191
diff
changeset
|
23 @node Introduction to Hash Tables, Working With Hash Tables, Hash Tables, Hash Tables |
| 428 | 24 @section Introduction to Hash Tables |
| 25 | |
| 26 A @dfn{hash table} is a data structure that provides mappings from | |
| 27 arbitrary Lisp objects called @dfn{keys} to other arbitrary Lisp objects | |
| 28 called @dfn{values}. A key/value pair is sometimes called an | |
| 29 @dfn{entry} in the hash table. There are many ways other than hash | |
| 30 tables of implementing the same sort of mapping, e.g. association lists | |
| 31 (@pxref{Association Lists}) and property lists (@pxref{Property Lists}), | |
| 32 but hash tables provide much faster lookup when there are many entries | |
| 33 in the mapping. Hash tables are an implementation of the abstract data | |
| 34 type @dfn{dictionary}, also known as @dfn{associative array}. | |
| 35 | |
| 36 Internally, hash tables are hashed using the @dfn{linear probing} hash | |
| 37 table implementation method. This method hashes each key to a | |
| 38 particular spot in the hash table, and then scans forward sequentially | |
| 39 until a blank entry is found. To look up a key, hash to the appropriate | |
| 40 spot, then search forward for the key until either a key is found or a | |
| 41 blank entry stops the search. This method is used in preference to | |
| 42 double hashing because of changes in recent hardware. The penalty for | |
| 43 non-sequential access to memory has been increasing, and this | |
| 44 compensates for the problem of clustering that linear probing entails. | |
| 45 | |
| 46 When hash tables are created, the user may (but is not required to) | |
| 47 specify initial properties that influence performance. | |
| 48 | |
| 49 Use the @code{:size} parameter to specify the number of entries that are | |
| 50 likely to be stored in the hash table, to avoid the overhead of resizing | |
| 51 the table. But if the pre-allocated space for the entries is never | |
| 52 used, it is simply wasted and makes XEmacs slower. Excess unused hash | |
| 53 table entries exact a small continuous performance penalty, since they | |
| 54 must be scanned at every garbage collection. If the number of entries | |
| 55 in the hash table is unknown, simply avoid using the @code{:size} | |
| 56 keyword. | |
| 57 | |
| 58 Use the @code{:rehash-size} and @code{:rehash-threshold} keywords to | |
| 59 adjust the algorithm for deciding when to rehash the hash table. For | |
| 60 temporary hash tables that are going to be very heavily used, use a | |
| 61 small rehash threshold, for example, 0.4 and a large rehash size, for | |
| 62 example 2.0. For permanent hash tables that will be infrequently used, | |
| 63 specify a large rehash threshold, for example 0.8. | |
| 64 | |
| 65 Hash tables can also be created by the lisp reader using structure | |
| 66 syntax, for example: | |
| 67 @example | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
68 #s(hash-table :size 20 :data (foo 1 bar 2)) |
| 428 | 69 @end example |
| 70 | |
|
4820
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
71 The structure syntax accepts the same keywords as |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
72 @code{make-hash-table}, as well as the additional keyword @code{data}, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
73 which specifies the initial hash table contents. Older versions of |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
74 XEmacs required that the keywords not have the initial ``:'' in the |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
75 structure syntax, and this version of XEmacs still supports that syntax, |
|
e6dec75ded0e
Use keywords, not ordinary symbols, in the structure syntax for hash tables.
Aidan Kehoe <kehoea@parhasard.net>
parents:
442
diff
changeset
|
76 but you cannot mix the two styles within one structure. |
| 428 | 77 |
| 78 @defun make-hash-table &key @code{test} @code{size} @code{rehash-size} @code{rehash-threshold} @code{weakness} | |
| 79 This function returns a new empty hash table object. | |
| 80 | |
|
5191
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
81 Keyword @code{:test} can be @code{eq}, @code{eql} (default), |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
82 @code{equal}, or @code{equalp}. |
| 428 | 83 Comparison between keys is done using this function. |
| 84 If speed is important, consider using @code{eq}. | |
|
5191
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
85 When storing strings in the hash table, you will likely need to use |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
86 @code{equal}, or @code{equalp} for case-insensitivity. |
| 428 | 87 |
| 88 Keyword @code{:size} specifies the number of keys likely to be inserted. | |
| 89 This number of entries can be inserted without enlarging the hash table. | |
| 90 | |
| 91 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies | |
| 92 the factor by which to increase the size of the hash table when enlarging. | |
| 93 | |
| 94 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0, | |
| 95 and specifies the load factor of the hash table which triggers enlarging. | |
| 96 | |
| 442 | 97 Non-standard keyword @code{:weakness} can be @code{nil} (default), |
| 98 @code{t}, @code{key-and-value}, @code{key}, @code{value} or | |
| 99 @code{key-or-value}. @code{t} is an alias for @code{key-and-value}. | |
| 428 | 100 |
| 442 | 101 A key-and-value-weak hash table, also known as a fully-weak or simply |
| 102 as a weak hash table, is one whose pointers do not count as GC | |
| 103 referents: for any key-value pair in the hash table, if the only | |
| 104 remaining pointer to either the key or the value is in a weak hash | |
| 105 table, then the pair will be removed from the hash table, and the key | |
| 106 and value collected. A non-weak hash table (or any other pointer) | |
| 107 would prevent the object from being collected. | |
| 428 | 108 |
| 109 A key-weak hash table is similar to a fully-weak hash table except that | |
| 110 a key-value pair will be removed only if the key remains unmarked | |
| 111 outside of weak hash tables. The pair will remain in the hash table if | |
| 112 the key is pointed to by something other than a weak hash table, even | |
| 113 if the value is not. | |
| 114 | |
| 115 A value-weak hash table is similar to a fully-weak hash table except | |
| 116 that a key-value pair will be removed only if the value remains | |
| 117 unmarked outside of weak hash tables. The pair will remain in the | |
| 118 hash table if the value is pointed to by something other than a weak | |
| 119 hash table, even if the key is not. | |
| 442 | 120 |
| 121 A key-or-value-weak hash table is similar to a fully-weak hash table except | |
| 122 that a key-value pair will be removed only if the value and the key remain | |
| 123 unmarked outside of weak hash tables. The pair will remain in the | |
| 124 hash table if the value or key are pointed to by something other than a weak | |
| 125 hash table, even if the other is not. | |
| 428 | 126 @end defun |
| 127 | |
| 128 @defun copy-hash-table hash-table | |
| 129 This function returns a new hash table which contains the same keys and | |
| 130 values as @var{hash-table}. The keys and values will not themselves be | |
| 131 copied. | |
| 132 @end defun | |
| 133 | |
| 134 @defun hash-table-count hash-table | |
| 135 This function returns the number of entries in @var{hash-table}. | |
| 136 @end defun | |
| 137 | |
| 138 @defun hash-table-test hash-table | |
| 139 This function returns the test function of @var{hash-table}. | |
|
5191
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
140 This can be one of @code{eq}, @code{eql}, @code{equal}, @code{equalp}, |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
141 or some @var{name} parameter given to @code{define-hash-table-test}. |
| 428 | 142 @end defun |
| 143 | |
| 144 @defun hash-table-size hash-table | |
| 145 This function returns the current number of slots in @var{hash-table}, | |
| 146 whether occupied or not. | |
| 147 @end defun | |
| 148 | |
| 149 @defun hash-table-rehash-size hash-table | |
| 150 This function returns the current rehash size of @var{hash-table}. | |
| 151 This is a float greater than 1.0; the factor by which @var{hash-table} | |
| 152 is enlarged when the rehash threshold is exceeded. | |
| 153 @end defun | |
| 154 | |
| 155 @defun hash-table-rehash-threshold hash-table | |
| 156 This function returns the current rehash threshold of @var{hash-table}. | |
| 157 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of | |
| 158 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing. | |
| 159 @end defun | |
| 160 | |
| 161 @defun hash-table-weakness hash-table | |
| 162 This function returns the weakness of @var{hash-table}. | |
| 163 This can be one of @code{nil}, @code{t}, @code{key} or @code{value}. | |
| 164 @end defun | |
| 165 | |
|
5791
9fae6227ede5
Silence texinfo 5.2 warnings, primarily by adding next, prev, and up
Jerry James <james@xemacs.org>
parents:
5191
diff
changeset
|
166 @node Working With Hash Tables, Weak Hash Tables, Introduction to Hash Tables, Hash Tables |
| 428 | 167 @section Working With Hash Tables |
| 168 | |
| 169 @defun puthash key value hash-table | |
| 170 This function hashes @var{key} to @var{value} in @var{hash-table}. | |
| 171 @end defun | |
| 172 | |
| 173 @defun gethash key hash-table &optional default | |
| 174 This function finds the hash value for @var{key} in @var{hash-table}. | |
| 175 If there is no entry for @var{key} in @var{hash-table}, @var{default} is | |
| 176 returned (which in turn defaults to @code{nil}). | |
| 177 @end defun | |
| 178 | |
| 179 @defun remhash key hash-table | |
| 180 This function removes the entry for @var{key} from @var{hash-table}. | |
| 181 Does nothing if there is no entry for @var{key} in @var{hash-table}. | |
| 182 @end defun | |
| 183 | |
| 184 @defun clrhash hash-table | |
| 185 This function removes all entries from @var{hash-table}, leaving it empty. | |
| 186 @end defun | |
| 187 | |
| 188 @defun maphash function hash-table | |
| 189 This function maps @var{function} over entries in @var{hash-table}, | |
| 190 calling it with two args, each key and value in the hash table. | |
| 191 | |
| 192 @var{function} may not modify @var{hash-table}, with the one exception | |
| 193 that @var{function} may remhash or puthash the entry currently being | |
| 194 processed by @var{function}. | |
| 195 @end defun | |
| 196 | |
|
5191
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
197 @defun define-hash-table-test name test-function hash-function |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
198 Creates a new hash table test function, beyond the four specified by |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
199 Common Lisp. @var{name} is a symbol, and @code{define-hash-table-test} |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
200 will error if there exists a hash table test with that name already. |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
201 (If you want to repeatedly define hash tables, use a symbol generated |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
202 with @code{gensym} for @var{name}). |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
203 |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
204 @var{test-function} must accept two arguments and return non-nil if both |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
205 arguments are the same. |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
206 |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
207 @var{hash-function} must accept one argument and return an integer hash |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
208 code for its argument. @var{hash-function} should use the entire range |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
209 of the underlying C long type, typically represented with two more value |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
210 bits than the Lisp fixnum type. |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
211 |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
212 Returns t on success, an incompatibility with GNU Emacs, which returns |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
213 a list comprising @var{test-function} and @var{hash-function}. |
|
71ee43b8a74d
Add #'equalp as a hash test by default; add #'define-hash-table-test, GNU API
Aidan Kehoe <kehoea@parhasard.net>
parents:
4820
diff
changeset
|
214 @end defun |
| 428 | 215 |
|
5791
9fae6227ede5
Silence texinfo 5.2 warnings, primarily by adding next, prev, and up
Jerry James <james@xemacs.org>
parents:
5191
diff
changeset
|
216 @node Weak Hash Tables, , Working With Hash Tables, Hash Tables |
| 428 | 217 @section Weak Hash Tables |
| 218 @cindex hash table, weak | |
| 219 @cindex weak hash table | |
| 220 | |
| 221 A @dfn{weak hash table} is a special variety of hash table whose | |
| 222 elements do not count as GC referents. For any key-value pair in such a | |
| 223 hash table, if either the key or value (or in some cases, if one | |
| 224 particular one of the two) has no references to it outside of weak hash | |
| 225 tables (and similar structures such as weak lists), the pair will be | |
| 226 removed from the table, and the key and value collected. A non-weak | |
| 227 hash table (or any other pointer) would prevent the objects from being | |
| 228 collected. | |
| 229 | |
| 230 Weak hash tables are useful for keeping track of information in a | |
| 231 non-obtrusive way, for example to implement caching. If the cache | |
| 232 contains objects such as buffers, markers, image instances, etc. that | |
| 233 will eventually disappear and get garbage-collected, using a weak hash | |
| 234 table ensures that these objects are collected normally rather than | |
| 235 remaining around forever, long past their actual period of use. | |
| 236 (Otherwise, you'd have to explicitly map over the hash table every so | |
| 237 often and remove unnecessary elements.) | |
| 238 | |
| 442 | 239 There are four types of weak hash tables: |
| 428 | 240 |
| 241 @table @asis | |
| 442 | 242 @item key-and-value-weak hash tables |
| 243 In these hash tables, also known as fully weak or simply as weak hash | |
| 244 tables, a pair disappears if either the key or the value is unreferenced | |
| 245 outside of the table. | |
| 428 | 246 @item key-weak hash tables |
| 247 In these hash tables, a pair disappears if the key is unreferenced outside | |
| 248 of the table, regardless of how the value is referenced. | |
| 249 @item value-weak hash tables | |
| 250 In these hash tables, a pair disappears if the value is unreferenced outside | |
| 251 of the table, regardless of how the key is referenced. | |
| 442 | 252 @item key-or-value-weak hash tables |
| 253 In these hash tables, a pair disappears if both the key and the value | |
| 254 are unreferenced outside of the table. | |
| 428 | 255 @end table |
| 256 | |
| 257 Also see @ref{Weak Lists}. | |
| 258 | |
| 259 Weak hash tables are created by specifying the @code{:weakness} keyword to | |
| 260 @code{make-hash-table}. |