annotate lisp/gnus/rtree.el @ 111789:f97704487fb3

Merge changes made in Gnus trunk. nnir.el: Batch header retrieval. proto-stream.el: New library to provide protocol-specific TLS/STARTTLS connections for IMAP, NNTP, SMTP, POP3 and similar protocols. nnimap.el (nnimap-open-connection): Use it. proto-stream.el (open-proto-stream): Complete the documentation. nnimap.el (nnimap-open-connection): Check for "OK" from the greeting. nntp.el: Use proto-streams for the relevant connections types. nntp.el (nntp-open-connection): Switch on STARTTLS on supported servers. proto-stream.el (open-proto-stream): Add a way to specify what the end of a command is. proto-stream.el (proto-stream-open-tls): Delete output from openssl if we're using tls.el. proto-stream.el (proto-stream-open-network): If we don't have gnutls-cli or gnutls built in, then don't try to establish a STARTTLS connection. color.el (color-lab->srgb): Fix function call name. proto-stream.el: Fix the syntax in the comment. nntp.el (nntp-open-connection): Fix the STARTTLS command syntax. proto-stream.el (proto-stream-open-starttls): Actually implement the starttls.el STARTTLS. proto-stream.el (proto-stream-always-use-starttls): New variable. proto-stream.el (proto-stream-open-starttls): De-duplicate the starttls code. proto-stream.el (proto-stream-open-starttls): Folded back into the main function. proto-stream.el (proto-stream-command): Refactor out. nnimap.el (nnimap-stream): Change default to `undecided'. nnimap.el (nnimap-open-connection): If `nnimap-stream' is `undecided', try ssl first, and then network. nnimap.el (nnimap-open-connection-1): Respect nnimap-server-port. nnimap.el (nnimap-open-connection): Be more backwards-compatible. proto-stream.el (open-protocol-stream): Renamed from open-proto-stream. proto-stream.el (proto-stream-open-network): When doing opportunistic TLS upgrades we don't really care about the identity of the peer. gnus.texi (Customizing the IMAP Connection): Note the new defaults. gnus.texi (Direct Functions): Note the STARTTLS upgrade. proto-stream.el (proto-stream-open-network): Force starttls.el to use gnutls-cli, since that what we've checked for. proto-stream.el (proto-stream-always-use-starttls): Only default to t if open-gnutls-stream exists. proto-stream.el (proto-stream-open-network): If STARTTLS failed, then just open a normal connection. proto-stream.el (proto-stream-open-network): Wait until the greeting before doing STARTTLS. nnimap.el (nnimap-open-connection-1): Always upgrade to STARTTLS (for backwards compatibility). nnimap.el (nnimap-open-connection-1): Really respect nnimap-server-port. nntp.el (nntp-open-connection): Provide a :success condition. nnimap.el (nnimap-open-connection-1): Ditto. proto-stream.el (proto-stream-open-network): See what the response to the STARTTLS command is. proto-stream.el (proto-stream-open-network): Add some comments. proto-stream.el: Fix example. proto-stream.el (open-protocol-stream): Actually mention the STARTTLS upgrade. nnir.el (nnir-get-active): Skip nnir-ignored-newsgroups when searching. nnir.el (nnir-ignore-newsgroups): Fix default value. nnir.el (nnir-run-gmane): Use mm-delete-duplicates instead of delete-dups that is not available in XEmacs 21.4. mm-util.el (mm-delete-duplicates): Add comment. gnus-sum.el (gnus-summary-delete-article): If delete fails don't change the registry. nnimap.el (nnimap-open-connection-1): w32 open-network-stream doesn't seem to accept strings-with-numbers as port numbers. color.el: fix docstring to use English rather than math notation for intervals. shr.el (shr-find-fill-point): Don't break before apostrophes. nnir.el (nnir-request-move-article): Bail out if no move support in group. color.el (color-rgb->hsv): Fix docstring. nnir.el (nnir-get-active): Improve active list retrieval. shr.el (shr-find-fill-point): Work better for kinsoku chars and apostrophes. gnus-gravatar.el (gnus-gravatar-size): Set gnus-gravatar-size to nil. nnimap.el (nnimap-open-connection-1): Use gnus-string-match-p. nnimap.el (nnimap-open-connection-1): Fix PREAUTH. proto-stream.el (open-protocol-stream): All starttls connections are handled by the network handler. gnus-gravatar.el (gnus-gravatar-insert): Delete unnecessary binding to t of inhibit-read-only since it is inside gnus-with-article-headers. gnus-gravatar.el (gnus-gravatar-transform-address): Use mail-extract-address-components that supports non-ASCII names rather than mail-header-parse-addresses. shr.el (shr-find-fill-point): Don't break line between kinsoku-bol characters. gnus-gravatar.el (gnus-gravatar-insert): Allow LWSP in the middle of names. nnmaildir.el (nnmaildir-request-set-mark): Add article to add-mark funcall. gnus-msg.el: Remove nastygram thing. message.el (message-from-style): Fix comment. message.el (message-user-organization): Do not use gnus-local-organization. gnus.el: Remove gnus-local-organization. rtree.el: New file to handle range trees. nnir.el, gnus-sum.el: Redo the way nnir handles registry updates. rtree.el (rtree-extract): Simplify. gnus-win.el (gnus-configure-windows): Remove Gnus 3.x setting support. gnus-msg.el: Mark gnus-outgoing-message-group as obsolete. gnus.texi (Archived Messages): Remove gnus-outgoing-message-group. gnus-win.el (gnus-configure-frame): Remove old compatibility code. rtree.el (rtree-memq): Rewrite it as a non-recursive function. rtree.el (rtree-add, rtree-delq, rtree-length): Implement. rtree.el (rtree-add): Make code slightly faster. nnir.el: Allow modified summary-line-format in nnir summary buffers.

;;; rtree.el --- functions for manipulating range trees
;; Copyright (C) 2010 Free Software Foundation, Inc.

;; Author: Lars Magne Ingebrigtsen <[e-mail]>

;; This file is part of GNU Emacs.

;; GNU Emacs is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation; either version 3, or (at your option)
;; any later version.

;; GNU Emacs is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.	 See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs; see the file COPYING.  If not, write to the
;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
;; Boston, MA 02110-1301, USA.

;;; Commentary:

;; A "range tree" is a binary tree that stores ranges.  They are
;; similar to interval trees, but do not allow overlapping intervals.

;; A range is an ordered list of number intervals, like this:

;; ((10 . 25) 56 78 (98 . 201))

;; Common operations, like lookup, deletion and insertion are O(n) in
;; a range, but an rtree is O(log n) in all these operations.
;; Transformation between a range and an rtree is O(n).

;; The rtrees are quite simple.  The structure of each node is

;; (cons (cons low high) (cons left right))

;; That is, they are three cons cells, where the car of the top cell
;; is the actual range, and the cdr has the left and right child.  The
;; rtrees aren't automatically balanced, but are balanced when
;; created, and can be rebalanced when deemed necessary.

;;; Code:

(eval-when-compile
  (require 'cl))

(defmacro rtree-make-node ()
  `(list (list nil) nil))

(defmacro rtree-set-left (node left)
  `(setcar (cdr ,node) ,left))

(defmacro rtree-set-right (node right)
  `(setcdr (cdr ,node) ,right))

(defmacro rtree-set-range (node range)
  `(setcar ,node ,range))

(defmacro rtree-low (node)
  `(caar ,node))

(defmacro rtree-high (node)
  `(cdar ,node))

(defmacro rtree-set-low (node number)
  `(setcar (car ,node) ,number))

(defmacro rtree-set-high (node number)
  `(setcdr (car ,node) ,number))

(defmacro rtree-left (node)
  `(cadr ,node))

(defmacro rtree-right (node)
  `(cddr ,node))

(defmacro rtree-range (node)
  `(car ,node))

(defsubst rtree-normalise-range (range)
  (when (numberp range)
    (setq range (cons range range)))
  range)

(defun rtree-make (range)
  "Make an rtree from RANGE."
  ;; Normalize the range.
  (unless (listp (cdr-safe range))
    (setq range (list range)))
  (rtree-make-1 (cons nil range) (length range)))

(defun rtree-make-1 (range length)
  (let ((mid (/ length 2))
	(node (rtree-make-node)))
    (when (> mid 0)
      (rtree-set-left node (rtree-make-1 range mid)))
    (rtree-set-range node (rtree-normalise-range (cadr range)))
    (setcdr range (cddr range))
    (when (> (- length mid 1) 0)
      (rtree-set-right node (rtree-make-1 range (- length mid 1))))
    node))

(defun rtree-memq (tree number)
  "Return non-nil if NUMBER is present in TREE."
  (while (and tree
	      (not (and (>= number (rtree-low tree))
			(<= number (rtree-high tree)))))
    (setq tree
	  (if (< number (rtree-low tree))
	      (rtree-left tree)
	    (rtree-right tree))))
  tree)

(defun rtree-add (tree number)
  "Add NUMBER to TREE."
  (while tree
    (cond
     ;; It's already present, so we don't have to do anything.
     ((and (>= number (rtree-low tree))
	   (<= number (rtree-high tree)))
      (setq tree nil))
     ((< number (rtree-low tree))
      (cond
       ;; Extend the low range.
       ((= number (1- (rtree-low tree)))
	(rtree-set-low tree number)
	;; Check whether we need to merge this node with the child.
	(when (and (rtree-left tree)
		   (= (rtree-high (rtree-left tree)) (1- number)))
	  ;; Extend the range to the low from the child.
	  (rtree-set-low tree (rtree-low (rtree-left tree)))
	  ;; The child can't have a right child, so just transplant the
	  ;; child's left tree to our left tree.
	  (rtree-set-left tree (rtree-left (rtree-left tree))))
	(setq tree nil))
       ;; Descend further to the left.
       ((rtree-left tree)
	(setq tree (rtree-left tree)))
       ;; Add a new node.
       (t
	(let ((new-node (rtree-make-node)))
	  (rtree-set-low new-node number)
	  (rtree-set-high new-node number)
	  (rtree-set-left tree new-node)
	  (setq tree nil)))))
     (t
      (cond
       ;; Extend the high range.
       ((= number (1+ (rtree-high tree)))
	(rtree-set-high tree number)
	;; Check whether we need to merge this node with the child.
	(when (and (rtree-right tree)
		   (= (rtree-low (rtree-right tree)) (1+ number)))
	  ;; Extend the range to the high from the child.
	  (rtree-set-high tree (rtree-high (rtree-right tree)))
	  ;; The child can't have a left child, so just transplant the
	  ;; child's left right to our right tree.
	  (rtree-set-right tree (rtree-right (rtree-right tree))))
	(setq tree nil))
       ;; Descend further to the right.
       ((rtree-right tree)
	(setq tree (rtree-right tree)))
       ;; Add a new node.
       (t
	(let ((new-node (rtree-make-node)))
	  (rtree-set-low new-node number)
	  (rtree-set-high new-node number)
	  (rtree-set-right tree new-node)
	  (setq tree nil))))))))

(defun rtree-delq (tree number)
  "Remove NUMBER from TREE destructively.  Returns the new tree."
  (let ((result tree)
	prev)
    (while tree
      (cond
       ((< number (rtree-low tree))
	(setq prev tree
	      tree (rtree-left tree)))
       ((> number (rtree-high tree))
	(setq prev tree
	      tree (rtree-right tree)))
       ;; The number is in this node.
       (t
	(cond
	 ;; The only entry; delete the node.
	 ((= (rtree-low tree) (rtree-high tree))
	  (cond
	   ;; Two children.  Replace with successor value.
	   ((and (rtree-left tree) (rtree-right tree))
	    (let ((parent tree)
		  (successor (rtree-right tree)))
	      (while (rtree-left successor)
		(setq parent successor
		      successor (rtree-left successor)))
	      ;; We now have the leftmost child of our right child.
	      (rtree-set-range tree (rtree-range successor))
	      ;; Transplant the child (if any) to the parent.
	      (rtree-set-left parent (rtree-right successor))))
	   (t
	    (let ((rest (or (rtree-left tree)
			    (rtree-right tree))))
	      ;; One or zero children.  Remove the node.
	      (cond
	       ((null prev)
		(setq result rest))
	       ((eq (rtree-left prev) tree)
		(rtree-set-left prev rest))
	       (t
		(rtree-set-right prev rest)))))))
	 ;; The lowest in the range; just adjust.
	 ((= number (rtree-low tree))
	  (rtree-set-low tree (1+ number)))
	 ;; The highest in the range; just adjust.
	 ((= number (rtree-high tree))
	  (rtree-set-high tree (1- number)))
	 ;; We have to split this range.
	 (t
	  (let ((new-node (rtree-make-node)))
	    (rtree-set-low new-node (rtree-low tree))
	    (rtree-set-high new-node (1- number))
	    (rtree-set-low tree (1+ number))
	    (cond
	     ;; Two children; insert the new node as the predecessor
	     ;; node.
	     ((and (rtree-left tree) (rtree-right tree))
	      (let ((predecessor (rtree-left tree)))
		(while (rtree-right predecessor)
		  (setq predecessor (rtree-right predecessor)))
		(rtree-set-right predecessor new-node)))
	     ((rtree-left tree)
	      (rtree-set-right new-node tree)
	      (rtree-set-left new-node (rtree-left tree))
	      (rtree-set-left tree nil)
	      (cond
	       ((null prev)
		(setq result new-node))
	       ((eq (rtree-left prev) tree)
		(rtree-set-left prev new-node))
	       (t
		(rtree-set-right prev new-node))))
	     (t
	      (rtree-set-left tree new-node))))))
	(setq tree nil))))
    result))

(defun rtree-extract (tree)
  "Convert TREE to range form."
  (let (stack result)
    (while (or stack
	       tree)
      (if tree
	  (progn
	    (push tree stack)
	    (setq tree (rtree-right tree)))
	(setq tree (pop stack))
	(push (if (= (rtree-low tree)
		     (rtree-high tree))
		  (rtree-low tree)
		(rtree-range tree))
	      result)
	(setq tree (rtree-left tree))))
    result))

(defun rtree-length (tree)
  "Return the number of numbers stored in TREE."
  (if (null tree)
      0
    (+ (rtree-length (rtree-left tree))
       (1+ (- (rtree-high tree)
	      (rtree-low tree)))
       (rtree-length (rtree-right tree)))))

(provide 'rtree)

;;; rtree.el ends here