Re: bool-vector implementation in the Emacs core

[Ted Zlatanov <tzz@lifelogs.com>]

On Sat, 24 Jan 2004, rms@gnu.org wrote:

> Why not just write code to use such a list explicitly?

I can write it myself in ELisp (the code is very simple), but I had
two reasons for bringing it up on emacs-devel:

- I think other Emacs developers could benefit from the same code.
  Inversion lists are very fast in most cases, and for sparse ranges
  are significantly faster and use less memory than the current
  implementation of bool-vector (which is basically a bitstring).

- I thought that a straight C implementation might be even better
  than using ELisp primitives; it's best to ask that question of the
  Emacs developers since I'm not familiar with the Emacs internals.

> Why do you need it to be hidden inside of a bool-vector?

Because the aref/aset API of bool-vector is nice, and existing code
that uses bool-vector can use inversion lists without major changes.

Also, bool-vector is definitely the right abstraction for what
inversion lists do.  There's no need to invent a new data type, with a
new API, for basically a bool-vector with an alternate internal
representation.

You can specify hashtable size when you create it.  In the same way
you could specify the bool-vector preference to be 'dense or 'sparse
for the range.  Then Emacs would give you an inversion list for sparse
ranges or a bitstring for dense ranges.  That's what I was really
hoping for.

Thank you
Ted