annotate man/lispref/range-tables.texi @ 4885:6772ce4d982b

Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums lisp/ChangeLog addition: 2010-01-24 Aidan Kehoe <kehoea@parhasard.net> Correct the semantics of #'member*, #'eql, #'assoc* in the presence of bignums; change the integerp byte code to fixnump semantics. * bytecomp.el (fixnump, integerp, byte-compile-integerp): Change the integerp byte code to fixnump; add a byte-compile method to integerp using fixnump and numberp and avoiding a funcall most of the time, since in the non-core contexts where integerp is used, it's mostly distinguishing between fixnums and things that are not numbers at all. * byte-optimize.el (side-effect-free-fns, byte-after-unbind-ops) (byte-compile-side-effect-and-error-free-ops): Replace the integerp bytecode with fixnump; add fixnump to the side-effect-free-fns. Add the other extended number type predicates to the list in passing. * obsolete.el (floatp-safe): Mark this as obsolete. * cl.el (eql): Go into more detail in the docstring here. Don't bother checking whether both arguments are numbers; one is enough, #'equal will fail correctly if they have distinct types. (subst): Replace a call to #'integerp (deciding whether to use #'memq or not) with one to #'fixnump. Delete most-positive-fixnum, most-negative-fixnum from this file; they're now always in C, so they can't be modified from Lisp. * cl-seq.el (member*, assoc*, rassoc*): Correct these functions in the presence of bignums. * cl-macs.el (cl-make-type-test): The type test for a fixnum is now fixnump. Ditch floatp-safe, use floatp instead. (eql): Correct this compiler macro in the presence of bignums. (assoc*): Correct this compiler macro in the presence of bignums. * simple.el (undo): Change #'integerp to #'fixnump here, since we use #'delq with the same value as ELT a few lines down. src/ChangeLog addition: 2010-01-24 Aidan Kehoe <kehoea@parhasard.net> Fix problems with #'eql, extended number types, and the hash table implementation; change the Bintegerp bytecode to fixnump semantics even on bignum builds, since #'integerp can have a fast implementation in terms of #'fixnump for most of its extant uses, but not vice-versa. * lisp.h: Always #include number.h; we want the macros provided in it, even if the various number types are not available. * number.h (NON_FIXNUM_NUMBER_P): New macro, giving 1 when its argument is of non-immediate number type. Equivalent to FLOATP if WITH_NUMBER_TYPES is not defined. * elhash.c (lisp_object_eql_equal, lisp_object_eql_hash): Use NON_FIXNUM_NUMBER_P in these functions, instead of FLOATP, giving more correct behaviour in the presence of the extended number types. * bytecode.c (Bfixnump, execute_optimized_program): Rename Bintegerp to Bfixnump; change its semantics to reflect the new name on builds with bignum support. * data.c (Ffixnump, Fintegerp, syms_of_data, vars_of_data): Always make #'fixnump available, even on non-BIGNUM builds; always implement #'integerp in this file, even on BIGNUM builds. Move most-positive-fixnum, most-negative-fixnum here from number.c, so they are Lisp constants even on builds without number types, and attempts to change or bind them error. Use the NUMBERP and INTEGERP macros even on builds without extended number types. * data.c (fixnum_char_or_marker_to_int): Rename this function from integer_char_or_marker_to_int, to better reflect the arguments it accepts. * number.c (Fevenp, Foddp, syms_of_number): Never provide #'integerp in this file. Remove #'oddp, #'evenp; their implementations are overridden by those in cl.el. * number.c (vars_of_number): most-positive-fixnum, most-negative-fixnum are no longer here. man/ChangeLog addition: 2010-01-23 Aidan Kehoe <kehoea@parhasard.net> Generally: be careful to say fixnum, not integer, when talking about fixed-precision integral types. I'm sure I've missed instances, both here and in the docstrings, but this is a decent start. * lispref/text.texi (Columns): Document where only fixnums, not integers generally, are accepted. (Registers): Remove some ancient char-int confoundance here. * lispref/strings.texi (Creating Strings, Creating Strings): Be more exact in describing where fixnums but not integers in general are accepted. (Creating Strings): Use a more contemporary example to illustrate how concat deals with lists including integers about #xFF. Delete some obsolete documentation on same. (Char Table Types): Document that only fixnums are accepted as values in syntax tables. * lispref/searching.texi (String Search, Search and Replace): Be exact in describing where fixnums but not integers in general are accepted. * lispref/range-tables.texi (Range Tables): Be exact in describing them; only fixnums are accepted to describe ranges. * lispref/os.texi (Killing XEmacs, User Identification) (Time of Day, Time Conversion): Be more exact about using fixnum where only fixed-precision integers are accepted. * lispref/objects.texi (Integer Type): Be more exact (and up-to-date) about the possible values for integers. Cross-reference to documentation of the bignum extension. (Equality Predicates): (Range Table Type): (Array Type): Use fixnum, not integer, to describe a fixed-precision integer. (Syntax Table Type): Correct some English syntax here. * lispref/numbers.texi (Numbers): Change the phrasing here to use fixnum to mean the fixed-precision integers normal in emacs. Document that our terminology deviates from that of Common Lisp, and that we're working on it. (Compatibility Issues): Reiterate the Common Lisp versus Emacs Lisp compatibility issues. (Comparison of Numbers, Arithmetic Operations): * lispref/commands.texi (Command Loop Info, Working With Events): * lispref/buffers.texi (Modification Time): Be more exact in describing where fixnums but not integers in general are accepted.
author Aidan Kehoe <kehoea@parhasard.net>
date Sun, 24 Jan 2010 15:21:27 +0000
parents ab71ad6ff3dd
children 9fae6227ede5
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
1 @c -*-texinfo-*-
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
2 @c This is part of the XEmacs Lisp Reference Manual.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
3 @c Copyright (C) 1996 Ben Wing.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
4 @c See the file lispref.texi for copying conditions.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
5 @setfilename ../../info/range-tables.info
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
6 @node Range Tables, Databases, Hash Tables, top
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
7 @chapter Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
8 @cindex Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
9
4885
6772ce4d982b Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums
Aidan Kehoe <kehoea@parhasard.net>
parents: 2421
diff changeset
10 A range table is a table that efficiently associates values with
6772ce4d982b Fix hash tables, #'member*, #'assoc*, #'eql compiler macros if bignums
Aidan Kehoe <kehoea@parhasard.net>
parents: 2421
diff changeset
11 ranges of fixnums.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
12
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
13 Note that range tables have a read syntax, like this:
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
14
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
15 @example
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
16 #s(range-table type start-closed-end-open data ((-3 2) foo (5 20) bar))
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
17 @end example
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
18
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
19 This maps integers in the range [-3, 2) to @code{foo} and integers
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
20 in the range [5, 20) to @code{bar}.
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
21
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
22 By default, range tables have a @var{type} of
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
23 @code{start-closed-end-open}. (@strong{NOTE}: This is a change from
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
24 21.4 and earlier, where there was no @var{type} and range tables were always
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
25 closed on both ends.) This makes them work like text properties.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
26
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
27 @defun range-table-p object
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
28 Return non-@code{nil} if @var{object} is a range table.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
29 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
30
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
31 @menu
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
32 * Introduction to Range Tables:: Range tables efficiently map ranges of
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
33 integers to values.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
34 * Working With Range Tables:: Range table functions.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
35 @end menu
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
36
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
37 @node Introduction to Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
38 @section Introduction to Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
39
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
40 @defun make-range-table &optional type
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
41 Make a new, empty range table.
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
42
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
43 @var{type} is a symbol indicating how ranges are assumed to function
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
44 at their ends. It can be one of
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
45
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
46 @example
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
47 SYMBOL RANGE-START RANGE-END
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
48 ------ ----------- ---------
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
49 `start-closed-end-open' (the default) closed open
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
50 `start-closed-end-closed' closed closed
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
51 `start-open-end-open' open open
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
52 `start-open-end-closed' open closed
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
53 @end example
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
54
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
55 A @dfn{closed} endpoint of a range means that the number at that end
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
56 is included in the range. For an @dfn{open} endpoint, the number
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
57 would not be included.
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
58
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
59 For example, a closed-open range from 5 to 20 would be indicated as
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
60 @samp{[5, 20)} where a bracket indicates a closed end and a
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
61 parenthesis an open end, and would mean `all the numbers between 5 and
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
62 20', including 5 but not 20. This seems a little strange at first but
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
63 is in fact extremely common in the outside world as well as in
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
64 computers and makes things work sensibly. For example, if I say
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
65 "there are seven days between today and next week today", I'm
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
66 including today but not next week today; if I included both, there
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
67 would be eight days. Similarly, there are 15 (= 20 - 5) elements in
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
68 the range @samp{[5, 20)}, but 16 in the range @samp{[5, 20]}.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
69 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
70
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
71 @defun copy-range-table range-table
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
72 This function returns a new range table which contains the same values
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
73 for the same ranges as @var{range-table}. The values will not
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
74 themselves be copied.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
75 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
76
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
77 @node Working With Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
78 @section Working With Range Tables
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
79
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
80 @defun get-range-table pos range-table &optional default
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
81 This function finds value for position @var{pos} in @var{range-table}.
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
82 If there is no corresponding value, return @var{default} (defaults to
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
83 @code{nil}).
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
84
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
85 @strong{NOTE}: If you are working with ranges that are closed at the
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
86 start and open at the end (the default), and you put a value for a
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
87 range with @var{start} equal to @var{end}, @code{get-range-table} will
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
88 @strong{not} return that value! You would need to set @var{end} one
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
89 greater than @var{start}.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
90 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
91
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
92 @defun put-range-table start end value range-table
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
93 This function sets the value for range (@var{start}, @var{end}) to be
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
94 @var{value} in @var{range-table}.
2421
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
95
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
96 @strong{NOTE}: Unless you are working with ranges that are closed at
ab71ad6ff3dd [xemacs-hg @ 2004-12-06 03:50:53 by ben]
ben
parents: 444
diff changeset
97 both ends, nothing will happen if @var{start} equals @var{end}.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
98 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
99
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
100 @defun remove-range-table start end range-table
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
101 This function removes the value for range (@var{start}, @var{end}) in
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
102 @var{range-table}.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
103 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
104
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
105 @defun clear-range-table range-table
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
106 This function flushes @var{range-table}.
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
107 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
108
444
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
109 @defun map-range-table function range-table
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
110 This function maps @var{function} over entries in @var{range-table},
576fb035e263 Import from CVS: tag r21-2-37
cvs
parents: 0
diff changeset
111 calling it with three args, the beginning and end of the range and the
0
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
112 corresponding value.
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
113 @end defun
376386a54a3c Import from CVS: tag r19-14
cvs
parents:
diff changeset
114