From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: storm@cua.dk (Kim F. Storm) Newsgroups: gmane.emacs.devel Subject: Re: bool-vector implementation in the Emacs core Date: 24 Jan 2004 03:11:22 +0100 Sender: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Message-ID: References: <4nd69dfdn2.fsf@collins.bwh.harvard.edu> <4nhdym4dw1.fsf@collins.bwh.harvard.edu> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1074906856 23808 80.91.224.253 (24 Jan 2004 01:14:16 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sat, 24 Jan 2004 01:14:16 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Sat Jan 24 02:14:10 2004 Return-path: Original-Received: from quimby.gnus.org ([80.91.224.244]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AkCNG-0000YJ-00 for ; Sat, 24 Jan 2004 02:14:10 +0100 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1AkCNG-0005ii-00 for ; Sat, 24 Jan 2004 02:14:10 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AkCM0-0004T9-KP for emacs-devel@quimby.gnus.org; Fri, 23 Jan 2004 20:12:52 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AkCLV-0004QT-QM for emacs-devel@gnu.org; Fri, 23 Jan 2004 20:12:21 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AkCKu-00040s-CN for emacs-devel@gnu.org; Fri, 23 Jan 2004 20:12:16 -0500 Original-Received: from [199.232.41.8] (helo=mx20.gnu.org) by monty-python.gnu.org with esmtp (TLSv1:DES-CBC3-SHA:168) (Exim 4.24) id 1AkCKt-0003z3-Ht for emacs-devel@gnu.org; Fri, 23 Jan 2004 20:11:43 -0500 Original-Received: from [195.41.46.235] (helo=pfepa.post.tele.dk) by mx20.gnu.org with esmtp (Exim 4.24) id 1AkCKj-0001b2-OO for emacs-devel@gnu.org; Fri, 23 Jan 2004 20:11:33 -0500 Original-Received: from kfs-l.imdomain.dk.cua.dk (0x503e2644.bynxx3.adsl-dhcp.tele.dk [80.62.38.68]) by pfepa.post.tele.dk (Postfix) with SMTP id 9D92147FF98; Sat, 24 Jan 2004 02:11:32 +0100 (CET) Original-To: Ted Zlatanov In-Reply-To: <4nhdym4dw1.fsf@collins.bwh.harvard.edu> Original-Lines: 83 User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3.50 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Emacs development discussions. List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Xref: main.gmane.org gmane.emacs.devel:19468 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:19468 Ted Zlatanov writes: > On 23 Jan 2004, no-spam@cua.dk wrote: > > > Ted Zlatanov 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 . 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 http://www.cua.dk