Mercurial > hg > xemacs-beta
annotate man/lispref/hash-tables.texi @ 4967:0d4c9d0f6a8d
rewrite dynarr code
-------------------- ChangeLog entries follow: --------------------
src/ChangeLog addition:
2010-02-03 Ben Wing <ben@xemacs.org>
* device-x.c (x_get_resource_prefix):
* device-x.c (Fx_get_resource):
* device-x.c (Fx_get_resource_prefix):
* device-x.c (Fx_put_resource):
* dialog-msw.c:
* dialog-msw.c (handle_question_dialog_box):
* dired-msw.c (mswindows_sort_files):
* dired-msw.c (mswindows_get_files):
* extents.c (extent_fragment_sort_by_priority):
* extents.c (Fset_extent_parent):
* file-coding.c (coding_reader):
* file-coding.c (coding_writer):
* file-coding.c (gzip_convert):
* frame.c (generate_title_string):
* gutter.c (calculate_gutter_size_from_display_lines):
* indent.c (vmotion_1):
* lread.c (read_bit_vector):
* mule-coding.c (iso2022_decode):
* rangetab.c:
* rangetab.c (Fcopy_range_table):
* rangetab.c (Fget_range_table):
* rangetab.c (unified_range_table_copy_data):
* redisplay-msw.c (mswindows_output_string):
* redisplay-output.c (output_display_line):
* redisplay-output.c (redisplay_move_cursor):
* redisplay-output.c (redisplay_clear_bottom_of_window):
* redisplay-tty.c (tty_output_ichar_dynarr):
* redisplay-tty.c (set_foreground_to):
* redisplay-tty.c (set_background_to):
* redisplay-xlike-inc.c (XLIKE_output_string):
* redisplay.c (redisplay_window_text_width_string):
* redisplay.c (redisplay_text_width_string):
* redisplay.c (create_text_block):
* redisplay.c (SET_CURRENT_MODE_CHARS_PIXSIZE):
* redisplay.c (generate_fstring_runes):
* redisplay.c (regenerate_modeline):
* redisplay.c (ensure_modeline_generated):
* redisplay.c (real_current_modeline_height):
* redisplay.c (create_string_text_block):
* redisplay.c (regenerate_window):
* redisplay.c (REGEN_INC_FIND_START_END):
* redisplay.c (point_visible):
* redisplay.c (redisplay_window):
* redisplay.c (mark_glyph_block_dynarr):
* redisplay.c (line_start_cache_start):
* redisplay.c (start_with_line_at_pixpos):
* redisplay.c (update_line_start_cache):
* redisplay.c (glyph_to_pixel_translation):
* redisplay.c (pixel_to_glyph_translation):
* sysdep.c (qxe_readdir):
* text.c (dfc_convert_to_external_format):
* text.c (dfc_convert_to_internal_format):
* toolbar-common.c (common_output_toolbar_button):
* window.c (window_modeline_height):
* window.c (Fwindow_last_line_visible_height):
* window.c (window_displayed_height):
* window.c (window_scroll):
* window.c (get_current_pixel_pos):
Use Dynarr_begin() in place of Dynarr_atp (foo, 0).
* dynarr.c (Dynarr_realloc):
* dynarr.c (Dynarr_lisp_realloc):
* dynarr.c (Dynarr_resize):
* dynarr.c (Dynarr_insert_many):
* dynarr.c (Dynarr_delete_many):
* dynarr.c (Dynarr_memory_usage):
* dynarr.c (stack_like_malloc):
* dynarr.c (stack_like_free):
* lisp.h:
* lisp.h (DECLARE_DYNARR_LISP_IMP):
* lisp.h (XD_DYNARR_DESC):
* lisp.h (Dynarr_pop):
* gutter.c (output_gutter):
* redisplay-output.c (sync_rune_structs):
* redisplay-output.c (redisplay_output_window):
Redo the dynarr code, add greater checks.
Rename the `len', `largest' and `max' members to `len_',
`largest_' and `max_' to try and catch existing places that might
directly modify these values. Make new accessors Dynarr_largest()
and Dynarr_max() and make them and existing Dynarr_length() be
non-lvalues by adding '+ 0' to them; fix a couple of places in the
redisplay code that tried to modify the length directly by setting
Dynarr_length(). Use the accessors whenever possible even in the
dynarr code itself. The accessors also verify that 0 <= len <=
largest <= max. Rename settor function Dynarr_set_size() to
Dynarr_set_length() and use it more consistently; also create
lower-level Dynarr_set_length_1(). This latter function should be
the only function that directly modifies the `len_' member of a
Dynarr, and in the process makes sure that the `largest' value is
kept correct.
Consistently use ERROR_CHECK_STRUCTURES instead of
ERROR_CHECK_TYPES for error-checking code. Reintroduce the
temporarily disabled verification code on the positions of
Dynarr_at(), Dynarr_atp() and Dynarr_atp_past_end().
Also create Dynarr_resize_if() in place of a repeated
code fragment. Clean up all the functions that modify Dynarrs to
use the new macros and functions and verify the correctness of the
Dynarr both before and after the change.
Note that there are two kinds of verification -- one for accessing
and one for modifying. The difference is that the modify
verification additionally checks to make sure that the Dynarr
isn't locked. (This is used in redisplay to check for problems
with reentrancy.)
* lrecord.h: Move XD_DYNARR_DESC to lisp.h, grouping with the dynarr code.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Wed, 03 Feb 2010 20:51:18 -0600 |
| parents | e6dec75ded0e |
| children | 71ee43b8a74d |
| 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 | |
| 6 @node Hash Tables, Range Tables, Display, top | |
| 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 | |
| 23 @node Introduction to Hash Tables | |
| 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 | |
| 81 Keyword @code{:test} can be @code{eq}, @code{eql} (default) or @code{equal}. | |
| 82 Comparison between keys is done using this function. | |
| 83 If speed is important, consider using @code{eq}. | |
| 84 When storing strings in the hash table, you will likely need to use @code{equal}. | |
| 85 | |
| 86 Keyword @code{:size} specifies the number of keys likely to be inserted. | |
| 87 This number of entries can be inserted without enlarging the hash table. | |
| 88 | |
| 89 Keyword @code{:rehash-size} must be a float greater than 1.0, and specifies | |
| 90 the factor by which to increase the size of the hash table when enlarging. | |
| 91 | |
| 92 Keyword @code{:rehash-threshold} must be a float between 0.0 and 1.0, | |
| 93 and specifies the load factor of the hash table which triggers enlarging. | |
| 94 | |
| 442 | 95 Non-standard keyword @code{:weakness} can be @code{nil} (default), |
| 96 @code{t}, @code{key-and-value}, @code{key}, @code{value} or | |
| 97 @code{key-or-value}. @code{t} is an alias for @code{key-and-value}. | |
| 428 | 98 |
| 442 | 99 A key-and-value-weak hash table, also known as a fully-weak or simply |
| 100 as a weak hash table, is one whose pointers do not count as GC | |
| 101 referents: for any key-value pair in the hash table, if the only | |
| 102 remaining pointer to either the key or the value is in a weak hash | |
| 103 table, then the pair will be removed from the hash table, and the key | |
| 104 and value collected. A non-weak hash table (or any other pointer) | |
| 105 would prevent the object from being collected. | |
| 428 | 106 |
| 107 A key-weak hash table is similar to a fully-weak hash table except that | |
| 108 a key-value pair will be removed only if the key remains unmarked | |
| 109 outside of weak hash tables. The pair will remain in the hash table if | |
| 110 the key is pointed to by something other than a weak hash table, even | |
| 111 if the value is not. | |
| 112 | |
| 113 A value-weak hash table is similar to a fully-weak hash table except | |
| 114 that a key-value pair will be removed only if the value remains | |
| 115 unmarked outside of weak hash tables. The pair will remain in the | |
| 116 hash table if the value is pointed to by something other than a weak | |
| 117 hash table, even if the key is not. | |
| 442 | 118 |
| 119 A key-or-value-weak hash table is similar to a fully-weak hash table except | |
| 120 that a key-value pair will be removed only if the value and the key remain | |
| 121 unmarked outside of weak hash tables. The pair will remain in the | |
| 122 hash table if the value or key are pointed to by something other than a weak | |
| 123 hash table, even if the other is not. | |
| 428 | 124 @end defun |
| 125 | |
| 126 @defun copy-hash-table hash-table | |
| 127 This function returns a new hash table which contains the same keys and | |
| 128 values as @var{hash-table}. The keys and values will not themselves be | |
| 129 copied. | |
| 130 @end defun | |
| 131 | |
| 132 @defun hash-table-count hash-table | |
| 133 This function returns the number of entries in @var{hash-table}. | |
| 134 @end defun | |
| 135 | |
| 136 @defun hash-table-test hash-table | |
| 137 This function returns the test function of @var{hash-table}. | |
| 138 This can be one of @code{eq}, @code{eql} or @code{equal}. | |
| 139 @end defun | |
| 140 | |
| 141 @defun hash-table-size hash-table | |
| 142 This function returns the current number of slots in @var{hash-table}, | |
| 143 whether occupied or not. | |
| 144 @end defun | |
| 145 | |
| 146 @defun hash-table-rehash-size hash-table | |
| 147 This function returns the current rehash size of @var{hash-table}. | |
| 148 This is a float greater than 1.0; the factor by which @var{hash-table} | |
| 149 is enlarged when the rehash threshold is exceeded. | |
| 150 @end defun | |
| 151 | |
| 152 @defun hash-table-rehash-threshold hash-table | |
| 153 This function returns the current rehash threshold of @var{hash-table}. | |
| 154 This is a float between 0.0 and 1.0; the maximum @dfn{load factor} of | |
| 155 @var{hash-table}, beyond which the @var{hash-table} is enlarged by rehashing. | |
| 156 @end defun | |
| 157 | |
| 158 @defun hash-table-weakness hash-table | |
| 159 This function returns the weakness of @var{hash-table}. | |
| 160 This can be one of @code{nil}, @code{t}, @code{key} or @code{value}. | |
| 161 @end defun | |
| 162 | |
| 163 @node Working With Hash Tables | |
| 164 @section Working With Hash Tables | |
| 165 | |
| 166 @defun puthash key value hash-table | |
| 167 This function hashes @var{key} to @var{value} in @var{hash-table}. | |
| 168 @end defun | |
| 169 | |
| 170 @defun gethash key hash-table &optional default | |
| 171 This function finds the hash value for @var{key} in @var{hash-table}. | |
| 172 If there is no entry for @var{key} in @var{hash-table}, @var{default} is | |
| 173 returned (which in turn defaults to @code{nil}). | |
| 174 @end defun | |
| 175 | |
| 176 @defun remhash key hash-table | |
| 177 This function removes the entry for @var{key} from @var{hash-table}. | |
| 178 Does nothing if there is no entry for @var{key} in @var{hash-table}. | |
| 179 @end defun | |
| 180 | |
| 181 @defun clrhash hash-table | |
| 182 This function removes all entries from @var{hash-table}, leaving it empty. | |
| 183 @end defun | |
| 184 | |
| 185 @defun maphash function hash-table | |
| 186 This function maps @var{function} over entries in @var{hash-table}, | |
| 187 calling it with two args, each key and value in the hash table. | |
| 188 | |
| 189 @var{function} may not modify @var{hash-table}, with the one exception | |
| 190 that @var{function} may remhash or puthash the entry currently being | |
| 191 processed by @var{function}. | |
| 192 @end defun | |
| 193 | |
| 194 | |
| 195 @node Weak Hash Tables | |
| 196 @section Weak Hash Tables | |
| 197 @cindex hash table, weak | |
| 198 @cindex weak hash table | |
| 199 | |
| 200 A @dfn{weak hash table} is a special variety of hash table whose | |
| 201 elements do not count as GC referents. For any key-value pair in such a | |
| 202 hash table, if either the key or value (or in some cases, if one | |
| 203 particular one of the two) has no references to it outside of weak hash | |
| 204 tables (and similar structures such as weak lists), the pair will be | |
| 205 removed from the table, and the key and value collected. A non-weak | |
| 206 hash table (or any other pointer) would prevent the objects from being | |
| 207 collected. | |
| 208 | |
| 209 Weak hash tables are useful for keeping track of information in a | |
| 210 non-obtrusive way, for example to implement caching. If the cache | |
| 211 contains objects such as buffers, markers, image instances, etc. that | |
| 212 will eventually disappear and get garbage-collected, using a weak hash | |
| 213 table ensures that these objects are collected normally rather than | |
| 214 remaining around forever, long past their actual period of use. | |
| 215 (Otherwise, you'd have to explicitly map over the hash table every so | |
| 216 often and remove unnecessary elements.) | |
| 217 | |
| 442 | 218 There are four types of weak hash tables: |
| 428 | 219 |
| 220 @table @asis | |
| 442 | 221 @item key-and-value-weak hash tables |
| 222 In these hash tables, also known as fully weak or simply as weak hash | |
| 223 tables, a pair disappears if either the key or the value is unreferenced | |
| 224 outside of the table. | |
| 428 | 225 @item key-weak hash tables |
| 226 In these hash tables, a pair disappears if the key is unreferenced outside | |
| 227 of the table, regardless of how the value is referenced. | |
| 228 @item value-weak hash tables | |
| 229 In these hash tables, a pair disappears if the value is unreferenced outside | |
| 230 of the table, regardless of how the key is referenced. | |
| 442 | 231 @item key-or-value-weak hash tables |
| 232 In these hash tables, a pair disappears if both the key and the value | |
| 233 are unreferenced outside of the table. | |
| 428 | 234 @end table |
| 235 | |
| 236 Also see @ref{Weak Lists}. | |
| 237 | |
| 238 Weak hash tables are created by specifying the @code{:weakness} keyword to | |
| 239 @code{make-hash-table}. |