[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/vertico 933e938 06/48: Compute history hash table only
From: |
Stefan Monnier |
Subject: |
[elpa] externals/vertico 933e938 06/48: Compute history hash table only once |
Date: |
Mon, 5 Apr 2021 10:54:39 -0400 (EDT) |
branch: externals/vertico
commit 933e938927ccb055224c0b6238a1001bb4c5c791
Author: Daniel Mendler <mail@daniel-mendler.de>
Commit: Daniel Mendler <mail@daniel-mendler.de>
Compute history hash table only once
---
minicomp.el | 47 +++++++++++++++++++++++++----------------------
1 file changed, 25 insertions(+), 22 deletions(-)
diff --git a/minicomp.el b/minicomp.el
index 91d223b..b138353 100644
--- a/minicomp.el
+++ b/minicomp.el
@@ -86,6 +86,9 @@
map)
"Minibuffer keymap.")
+(defvar-local minicomp--history-hash nil
+ "History hash table.")
+
(defvar-local minicomp--candidates-ov nil
"Overlay showing the candidates.")
@@ -118,31 +121,31 @@
(defun minicomp--sort (candidates)
"Sort CANDIDATES by history position, length and alphabetically."
- ;; History disabled if `minibuffer-history-variable' eq `t'.
- (let* ((list (and (not (eq minibuffer-history-variable t))
- (symbol-value minibuffer-history-variable)))
- (hist-len (length list))
- (hist (make-hash-table :test #'equal
- :size hist-len))
- (hist-idx 0)
- (cand candidates))
- ;; Store the history position first in a hashtable in order to
- ;; allow O(1) history lookup.
- (dolist (elem list)
- (unless (gethash elem hist)
- (puthash elem hist-idx hist))
- (setq hist-idx (1+ hist-idx)))
- ;; Decorate each candidate with (hist-idx<<13) + length. This
- ;; way we sort first by hist-idx and then by length. We assume
- ;; that the candidates are not longer than 2**13 characters.
+ (unless minicomp--history-hash
+ ;; History disabled if `minibuffer-history-variable' eq `t'.
+ (let ((list (and (not (eq minibuffer-history-variable t))
+ (symbol-value minibuffer-history-variable)))
+ (hist-idx 0))
+ (setq minicomp--history-hash (make-hash-table :test #'equal
+ :size (length list)))
+ ;; Store the history position first in a hashtable in order to
+ ;; allow O(1) history lookup.
+ (dolist (elem list)
+ (unless (gethash elem minicomp--history-hash)
+ (puthash elem hist-idx minicomp--history-hash))
+ (setq hist-idx (1+ hist-idx)))))
+ ;; Decorate each candidate with (hist-idx<<13) + length. This way we sort
first by hist-idx and
+ ;; then by length. We assume that the candidates are shorter than 2**13
characters and that the
+ ;; history is shorter than 2**16 entries.
+ (let ((cand candidates))
(while cand
(setcar cand (cons (car cand)
- (+ (lsh (gethash (car cand) hist hist-len) 13)
+ (+ (lsh (gethash (car cand) minicomp--history-hash
#xFFFF) 13)
(length (car cand)))))
- (setq cand (cdr cand)))
- (setq candidates (sort candidates #'minicomp--pred)
- cand candidates)
- ;; Drop decoration from the candidates
+ (setq cand (cdr cand))))
+ (setq candidates (sort candidates #'minicomp--pred))
+ ;; Drop decoration from the candidates
+ (let ((cand candidates))
(while cand
(setcar cand (caar cand))
(setq cand (cdr cand))))
- [elpa] branch externals/vertico created (now 1a9b1b2), Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 3257082 07/48: always keep index when explicitly navigating, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico e2472d1 13/48: simplify, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 9355d05 01/48: minicomp - initial commit, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 933e938 06/48: Compute history hash table only once,
Stefan Monnier <=
- [elpa] externals/vertico f132f1b 10/48: improve prompt selection, add minicomp--goto, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 9b81d8d 08/48: remove ./ and ../ from file completion candidates, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 5bbddb0 03/48: add while-no-input-ignore-events, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 4ce7c8d 11/48: use seq-subseq, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico f558f53 04/48: extract minicomp--pred, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 9db7c78 20/48: add minicomp-count-format, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 245944a 21/48: remap previous/next-line, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico 7fbaeaf 15/48: Add sorting by history for files, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico c2bfea2 17/48: use candidate returned from affixation function, Stefan Monnier, 2021/04/05
- [elpa] externals/vertico bafee15 19/48: add minicomp-exit-input, Stefan Monnier, 2021/04/05