Re: bool-vector implementation in the Emacs core

[storm@cua.dk (Kim F. Storm)]

Ted Zlatanov <tzz@lifelogs.com> writes:

> On 23 Jan 2004, no-spam@cua.dk wrote:
> 
> > Ted Zlatanov <tzz@lifelogs.com> writes:
> > 
> >> 
> >> We're talking about implementations of ranges in the Gnus developer
> >> list right now, and our implementations of ranges is written in
> >> Lisp.  I can implement inversion lists in Lisp as well, but ranges
> >> are such an essential Gnus piece that it seems like seeking core
> >> support for them would be a good idea.
> > 
> > What kind of C-level support are you looking for?
> 
> Something like a bool-vector, but internally implemented with an
> inversion list.  A double-linked C list of integers is perfect, so you
> can insert and delete quickly.  I can base it on the ELisp lists, I
> was just hoping to make the bool-vector operations insanely fast :)

If you always lookup from the start of the list, a double-linked list
isn't needed; just keep a pointer to the previous element and use
setcdr to insert or delete elements in the list and setcar to change
a specific element of the list.

> 
> Now, there are two approaches - either provide an alternate internal
> implementation of the bool-vector when you create it, or provide a
> whole new data type.  I'd rather be able to make a bool-vector with
> an inversion list internally.

Here is a starting point written in Elisp; nothing fancy yet, but I
think it shows that it can be done fairly efficiently using lists.


;;; Implement bool-vectors as inversion lists.
;;; (c) 2004 Kim F. Storm <storm@cua.dk>.  All rights reserved.

(defun make-bool-vector ()
  "Create an empty bool vector."
  '(-1))

(defun bool-vector-locate (bv elt)
  "Locate cons cell in bool vector BV which precedes element ELT.
For internal use only.  Return value is (PRED . ON)."
  (let (on (b (cdr bv)))
    (while (and (consp b) (> elt (car b)))
      (setq bv b
	    b (cdr b)
	    on (not on)))
    (cons bv on)))

(defun bool-vector-add (bv elt)
  "Add to bool vector BV the element ELT."
  (let* ((b-on (bool-vector-locate bv elt))
	 (b (car b-on)) (on (cdr b-on))
	 (c (cdr b)))
    (cond
     ((null c)
      (setcdr b (list elt (1+ elt))))
     ((< (1+ elt) (car c))
      (if (not on)
	  (setcdr b (cons elt (cons (1+ elt) (cdr b))))))
     ((< elt (car c))
      (if (not on)
	  (setcar c elt)))
     ((= elt (car c))
      (if on
	  (if (and (consp (cdr c)) (= (1+ elt) (car (cdr c))))
	      (setcdr b (cdr (cdr c)))
	    (setcar c (1+ elt)))))))
  bv)

(defun bool-vector-test (bv elt)
  "Test if bool vector BV contains element ELT."
  (let* ((b-on (bool-vector-locate bv elt))
	 (b (car b-on)) (on (cdr b-on))
	 (c (cdr b)))
    (and (consp c) 
	 (if on (< elt (car c)) (= elt (car c))))))

-- 
Kim F. Storm <storm@cua.dk> http://www.cua.dk