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.

@c -*-texinfo-*-
@c This is part of the XEmacs Lisp Reference Manual.
@c Copyright (C) 1996 Ben Wing.
@c See the file lispref.texi for copying conditions.
@setfilename ../../info/range-tables.info
@node Range Tables, Databases, Hash Tables, top
@chapter Range Tables
@cindex Range Tables

A range table is a table that efficiently associates values with
ranges of fixnums.

Note that range tables have a read syntax, like this:

@example
#s(range-table type start-closed-end-open data ((-3 2) foo (5 20) bar))
@end example

This maps integers in the range [-3, 2) to @code{foo} and integers
in the range [5, 20) to @code{bar}.

By default, range tables have a @var{type} of
@code{start-closed-end-open}. (@strong{NOTE}: This is a change from
21.4 and earlier, where there was no @var{type} and range tables were always
closed on both ends.) This makes them work like text properties.

@defun range-table-p object
Return non-@code{nil} if @var{object} is a range table.
@end defun

@menu
* Introduction to Range Tables:: Range tables efficiently map ranges of
                                 integers to values.
* Working With Range Tables::    Range table functions.
@end menu

@node Introduction to Range Tables
@section Introduction to Range Tables

@defun make-range-table &optional type
Make a new, empty range table.

@var{type} is a symbol indicating how ranges are assumed to function
at their ends.  It can be one of

@example
SYMBOL                                     RANGE-START         RANGE-END
------                                     -----------         ---------
`start-closed-end-open'  (the default)     closed              open
`start-closed-end-closed'                  closed              closed
`start-open-end-open'                      open                open
`start-open-end-closed'                    open                closed
@end example

A @dfn{closed} endpoint of a range means that the number at that end
is included in the range.  For an @dfn{open} endpoint, the number
would not be included.

For example, a closed-open range from 5 to 20 would be indicated as
@samp{[5, 20)} where a bracket indicates a closed end and a
parenthesis an open end, and would mean `all the numbers between 5 and
20', including 5 but not 20.  This seems a little strange at first but
is in fact extremely common in the outside world as well as in
computers and makes things work sensibly.  For example, if I say
"there are seven days between today and next week today", I'm
including today but not next week today; if I included both, there
would be eight days.  Similarly, there are 15 (= 20 - 5) elements in
the range @samp{[5, 20)}, but 16 in the range @samp{[5, 20]}.
@end defun

@defun copy-range-table range-table
This function returns a new range table which contains the same values
for the same ranges as @var{range-table}.  The values will not
themselves be copied.
@end defun

@node Working With Range Tables
@section Working With Range Tables

@defun get-range-table pos range-table &optional default
This function finds value for position @var{pos} in @var{range-table}.
If there is no corresponding value, return @var{default} (defaults to
@code{nil}).

@strong{NOTE}: If you are working with ranges that are closed at the
start and open at the end (the default), and you put a value for a
range with @var{start} equal to @var{end}, @code{get-range-table} will
@strong{not} return that value!  You would need to set @var{end} one
greater than @var{start}.
@end defun

@defun put-range-table start end value range-table
This function sets the value for range (@var{start}, @var{end}) to be
@var{value} in @var{range-table}.

@strong{NOTE}: Unless you are working with ranges that are closed at
both ends, nothing will happen if @var{start} equals @var{end}.
@end defun

@defun remove-range-table start end range-table
This function removes the value for range (@var{start}, @var{end}) in
@var{range-table}.
@end defun

@defun clear-range-table range-table
This function flushes @var{range-table}.
@end defun

@defun map-range-table function range-table
This function maps @var{function} over entries in @var{range-table},
calling it with three args, the beginning and end of the range and the
corresponding value.
@end defun