Function: org-element--cache-generate-key

org-element--cache-generate-key is a byte-compiled function defined in org-element.el.gz.

Signature

(org-element--cache-generate-key LOWER UPPER)

Documentation

Generate a key between LOWER and UPPER.

LOWER and UPPER are fixnums or lists of same, possibly empty.

If LOWER and UPPER are equals, return LOWER. Otherwise, return a unique key, as an integer or a list of integers, according to the following rules:

  - LOWER and UPPER are compared level-wise until values differ.

  - If, at a given level, LOWER and UPPER differ from more than
    2, the new key shares all the levels above with LOWER and
    gets a new level. Its value is the mean between LOWER and
    UPPER:

      (1 2) + (1 4) --> (1 3)

  - If LOWER has no value to compare with, it is assumed that its
    value is most-negative-fixnum. E.g.,

      (1 1) + (1 1 2)

    is equivalent to

      (1 1 m) + (1 1 2)

    where m is most-negative-fixnum. Likewise, if UPPER is
    short of levels, the current value is most-positive-fixnum.

  - If they differ from only one, the new key inherits from
    current LOWER level and fork it at the next level. E.g.,

      (2 1) + (3 3)

    is equivalent to

      (2 1) + (2 M)

    where M is most-positive-fixnum.

  - If the key is only one level long, it is returned as an
    integer:

      (1 2) + (3 2) --> 2

When they are not equals, the function assumes that LOWER is lesser than UPPER, per org-element--cache-key-less-p.

Source Code

;; Defined in /usr/src/emacs/lisp/org/org-element.el.gz
(defun org-element--cache-generate-key (lower upper)
  "Generate a key between LOWER and UPPER.

LOWER and UPPER are fixnums or lists of same, possibly empty.

If LOWER and UPPER are equals, return LOWER.  Otherwise, return
a unique key, as an integer or a list of integers, according to
the following rules:

  - LOWER and UPPER are compared level-wise until values differ.

  - If, at a given level, LOWER and UPPER differ from more than
    2, the new key shares all the levels above with LOWER and
    gets a new level.  Its value is the mean between LOWER and
    UPPER:

      (1 2) + (1 4) --> (1 3)

  - If LOWER has no value to compare with, it is assumed that its
    value is `most-negative-fixnum'.  E.g.,

      (1 1) + (1 1 2)

    is equivalent to

      (1 1 m) + (1 1 2)

    where m is `most-negative-fixnum'.  Likewise, if UPPER is
    short of levels, the current value is `most-positive-fixnum'.

  - If they differ from only one, the new key inherits from
    current LOWER level and fork it at the next level.  E.g.,

      (2 1) + (3 3)

    is equivalent to

      (2 1) + (2 M)

    where M is `most-positive-fixnum'.

  - If the key is only one level long, it is returned as an
    integer:

      (1 2) + (3 2) --> 2

When they are not equals, the function assumes that LOWER is
lesser than UPPER, per `org-element--cache-key-less-p'."
  (if (equal lower upper) lower
    (let ((lower (if (integerp lower) (list lower) lower))
	  (upper (if (integerp upper) (list upper) upper))
          skip-upper key)
      (catch 'exit
	(while t
	  (let ((min (or (car lower) most-negative-fixnum))
		(max (cond (skip-upper most-positive-fixnum)
                           ((car upper))
                           (t most-positive-fixnum))))
            (if (< (1+ min) max)
		(let ((mean (+ (ash min -1) (ash max -1) (logand min max 1))))
		  (throw 'exit (if key (nreverse (cons mean key)) mean)))
	      (when (and (< min max) (not skip-upper))
		;; When at a given level, LOWER and UPPER differ from
		;; 1, ignore UPPER altogether.  Instead create a key
		;; between LOWER and the greatest key with the same
		;; prefix as LOWER so far.
		(setq skip-upper t))
	      (push min key)
	      (setq lower (cdr lower) upper (cdr upper)))))))))