1 ;;; registry.el --- Track and remember data items by various fields
3 ;; Copyright (C) 2011-2015 Free Software Foundation, Inc.
5 ;; Author: Teodor Zlatanov <tzz@lifelogs.com>
8 ;; This file is part of GNU Emacs.
10 ;; GNU Emacs is free software: you can redistribute it and/or modify
11 ;; it under the terms of the GNU General Public License as published by
12 ;; the Free Software Foundation, either version 3 of the License, or
13 ;; (at your option) any later version.
15 ;; GNU Emacs is distributed in the hope that it will be useful,
16 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 ;; GNU General Public License for more details.
20 ;; You should have received a copy of the GNU General Public License
21 ;; along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>.
25 ;; This library provides a general-purpose EIEIO-based registry
26 ;; database with persistence, initialized with these fields:
30 ;; max-size: an integer, default most-positive-fixnum
32 ;; prune-factor: a float between 0 and 1, default 0.1
34 ;; precious: a list of symbols
36 ;; tracked: a list of symbols
38 ;; tracker: a hashtable tuned for 100 symbols to track (you should
39 ;; only access this with the :lookup2-function and the
40 ;; :lookup2+-function)
42 ;; data: a hashtable with default size 10K and resize threshold 2.0
43 ;; (this reflects the expected usage so override it if you know better)
45 ;; ...plus methods to do all the work: `registry-search',
46 ;; `registry-lookup', `registry-lookup-secondary',
47 ;; `registry-lookup-secondary-value', `registry-insert',
48 ;; `registry-delete', `registry-prune', `registry-size' which see
50 ;; and with the following properties:
52 ;; Every piece of data has a unique ID and some general-purpose fields
53 ;; (F1=D1, F2=D2, F3=(a b c)...) expressed as an alist, e.g.
55 ;; ((F1 D1) (F2 D2) (F3 a b c))
57 ;; Note that whether a field has one or many pieces of data, the data
58 ;; is always a list of values.
60 ;; The user decides which fields are "precious", F2 for example. When
61 ;; the registry is pruned, any entries without the F2 field will be
62 ;; removed until the size is :max-size * :prune-factor _less_ than the
63 ;; maximum database size. No entries with the F2 field will be removed
64 ;; at PRUNE TIME, which means it may not be possible to prune back all
65 ;; the way to the target size.
67 ;; When an entry is inserted, the registry will reject new entries if
68 ;; they bring it over the :max-size limit, even if they have the F2
71 ;; The user decides which fields are "tracked", F1 for example. Any
72 ;; new entry is then indexed by all the tracked fields so it can be
73 ;; quickly looked up that way. The data is always a list (see example
74 ;; above) and each list element is indexed.
76 ;; Precious and tracked field names must be symbols. All other
77 ;; fields can be any other Emacs Lisp types.
81 (eval-when-compile (require 'cl))
84 (or (ignore-errors (progn
86 (require 'eieio-base)))
87 ;; gnus-fallback-lib/ from gnus/lisp/gnus-fallback-lib
89 (let ((load-path (cons (expand-file-name
90 "gnus-fallback-lib/eieio"
91 (file-name-directory (locate-library "gnus")))
94 (require 'eieio-base)))
96 "eieio not found in `load-path' or gnus-fallback-lib/ directory.")))
99 (unless (fboundp 'cl-remf)
100 (defalias 'cl-remf 'remf)
101 (defalias 'cl-loop 'loop)
102 (defalias 'cl-subseq 'subseq)))
104 ;; The version number needs to be kept outside of the class definition
105 ;; itself. The persistent-save process does *not* write to file any
106 ;; slot values that are equal to the default :initform value. If a
107 ;; database object is at the most recent version, therefore, its
108 ;; version number will not be written to file. That makes it
109 ;; difficult to know when a database needs to be upgraded.
110 (defvar registry-db-version 0.2
111 "The current version of the registry format.")
113 (defclass registry-db (eieio-persistent)
114 ((version :initarg :version
116 :type (or null float)
117 :documentation "The registry version.")
118 (max-size :initarg :max-size
119 ;; :initform most-positive-fixnum ;; see below
122 :documentation "The maximum number of registry entries.")
124 :initarg :prune-factor
128 :documentation "Prune to \(:max-size * :prune-factor\) less
129 than the :max-size limit. Should be a float between 0 and 1.")
130 (tracked :initarg :tracked
133 :documentation "The tracked (indexed) fields, a list of symbols.")
134 (precious :initarg :precious
137 :documentation "The precious fields, a list of symbols.")
138 (tracker :initarg :tracker
140 :documentation "The field tracking hashtable.")
143 :documentation "The data hashtable.")))
144 ;; Do this separately, since defclass doesn't allow expressions in :initform.
145 (oset-default 'registry-db max-size most-positive-fixnum)
147 (defmethod initialize-instance :BEFORE ((this registry-db) slots)
148 "Check whether a registry object needs to be upgraded."
149 ;; Hardcoded upgrade routines. Version 0.1 to 0.2 requires the
150 ;; :max-soft slot to disappear, and the :max-hard slot to be renamed
152 (let ((current-version
153 (and (plist-member slots :version)
154 (plist-get slots :version))))
155 (when (or (null current-version)
156 (eql current-version 0.1))
158 (plist-put slots :max-size (plist-get slots :max-hard)))
160 (plist-put slots :version registry-db-version))
161 (cl-remf slots :max-hard)
162 (cl-remf slots :max-soft))))
164 (defmethod initialize-instance :AFTER ((this registry-db) slots)
165 "Set value of data slot of THIS after initialization."
166 (with-slots (data tracker) this
167 (unless (member :data slots)
169 (make-hash-table :size 10000 :rehash-size 2.0 :test 'equal)))
170 (unless (member :tracker slots)
171 (setq tracker (make-hash-table :size 100 :rehash-size 2.0)))))
173 (defmethod registry-lookup ((db registry-db) keys)
174 "Search for KEYS in the registry-db THIS.
175 Returns an alist of the key followed by the entry in a list, not a cons cell."
176 (let ((data (oref db :data)))
180 (when (gethash k data)
181 (list k (gethash k data))))
184 (defmethod registry-lookup-breaks-before-lexbind ((db registry-db) keys)
185 "Search for KEYS in the registry-db THIS.
186 Returns an alist of the key followed by the entry in a list, not a cons cell."
187 (let ((data (oref db :data)))
189 (loop for key in keys
190 when (gethash key data)
191 collect (list key (gethash key data))))))
193 (defmethod registry-lookup-secondary ((db registry-db) tracksym
195 "Search for TRACKSYM in the registry-db THIS.
196 When CREATE is not nil, create the secondary index hashtable if needed."
197 (let ((h (gethash tracksym (oref db :tracker))))
202 (make-hash-table :size 800 :rehash-size 2.0 :test 'equal)
204 (gethash tracksym (oref db :tracker))))))
206 (defmethod registry-lookup-secondary-value ((db registry-db) tracksym val
208 "Search for TRACKSYM with value VAL in the registry-db THIS.
209 When SET is not nil, set it for VAL (use t for an empty list)."
210 ;; either we're asked for creation or there should be an existing index
211 (when (or set (registry-lookup-secondary db tracksym))
212 ;; set the entry if requested,
214 (puthash val (if (eq t set) '() set)
215 (registry-lookup-secondary db tracksym t)))
216 (gethash val (registry-lookup-secondary db tracksym))))
218 (defun registry--match (mode entry check-list)
221 (let ((key (nth 0 (nth 0 check-list)))
222 (vals (cdr-safe (nth 0 check-list)))
224 (while (and key vals (not found))
225 (setq found (case mode
227 (member (car-safe vals) (cdr-safe (assoc key entry))))
229 (string-match (car vals)
232 (cdr-safe (assoc key entry))
234 vals (cdr-safe vals)))
236 (registry--match mode entry (cdr-safe check-list))))))
238 (defmethod registry-search ((db registry-db) &rest spec)
239 "Search for SPEC across the registry-db THIS.
240 For example calling with :member '(a 1 2) will match entry '((a 3 1)).
241 Calling with :all t (any non-nil value) will match all.
242 Calling with :regex '\(a \"h.llo\") will match entry '((a \"hullo\" \"bye\").
243 The test order is to check :all first, then :member, then :regex."
245 (let ((all (plist-get spec :all))
246 (member (plist-get spec :member))
247 (regex (plist-get spec :regex)))
248 (loop for k being the hash-keys of (oref db :data)
249 using (hash-values v)
251 ;; :all non-nil returns all
254 (and member (registry--match :member v member))
256 (and regex (registry--match :regex v regex)))
259 (defmethod registry-delete ((db registry-db) keys assert &rest spec)
260 "Delete KEYS from the registry-db THIS.
261 If KEYS is nil, use SPEC to do a search.
262 Updates the secondary ('tracked') indices as well.
263 With assert non-nil, errors out if the key does not exist already."
264 (let* ((data (oref db :data))
266 (apply 'registry-search db spec)))
267 (tracked (oref db :tracked)))
270 (let ((entry (gethash key data)))
273 "Key %s does not exist in database" key))
274 ;; clean entry from the secondary indices
276 ;; is this tracked symbol indexed?
277 (when (registry-lookup-secondary db tr)
278 ;; for every value in the entry under that key...
279 (dolist (val (cdr-safe (assq tr entry)))
280 (let* ((value-keys (registry-lookup-secondary-value
282 (when (member key value-keys)
283 ;; override the previous value
284 (registry-lookup-secondary-value
286 ;; with the indexed keys MINUS the current key
287 ;; (we pass t when the list is empty)
288 (or (delete key value-keys) t)))))))
292 (defmethod registry-size ((db registry-db))
293 "Returns the size of the registry-db object THIS.
294 This is the key count of the :data slot."
295 (hash-table-count (oref db :data)))
297 (defmethod registry-full ((db registry-db))
298 "Checks if registry-db THIS is full."
299 (>= (registry-size db)
300 (oref db :max-size)))
302 (defmethod registry-insert ((db registry-db) key entry)
303 "Insert ENTRY under KEY into the registry-db THIS.
304 Updates the secondary ('tracked') indices as well.
305 Errors out if the key exists already."
307 (assert (not (gethash key (oref db :data))) nil
308 "Key already exists in database")
310 (assert (not (registry-full db))
312 "registry max-size limit reached")
315 (puthash key entry (oref db :data))
317 ;; store the secondary indices
318 (dolist (tr (oref db :tracked))
319 ;; for every value in the entry under that key...
320 (dolist (val (cdr-safe (assq tr entry)))
321 (let* ((value-keys (registry-lookup-secondary-value db tr val)))
322 (pushnew key value-keys :test 'equal)
323 (registry-lookup-secondary-value db tr val value-keys))))
326 (defmethod registry-reindex ((db registry-db))
327 "Rebuild the secondary indices of registry-db THIS."
329 (expected (* (length (oref db :tracked)) (registry-size db))))
330 (dolist (tr (oref db :tracked))
335 (when (and (< 0 expected)
336 (= 0 (mod count 1000)))
337 (message "reindexing: %d of %d (%.2f%%)"
338 count expected (/ (* 100 count) expected)))
339 (dolist (val (cdr-safe (assq tr v)))
340 (let* ((value-keys (registry-lookup-secondary-value db tr val)))
341 (push key value-keys)
342 (registry-lookup-secondary-value db tr val value-keys))))
345 (defmethod registry-prune ((db registry-db) &optional sortfunc)
346 "Prunes the registry-db object DB.
348 Attempts to prune the number of entries down to \(*
349 :max-size :prune-factor\) less than the max-size limit, so
350 pruning doesn't need to happen on every save. Removes only
351 entries without the :precious keys, so it may not be possible to
352 reach the target limit.
354 Entries to be pruned are first sorted using SORTFUNC. Entries
355 from the front of the list are deleted first.
357 Returns the number of deleted entries."
358 (let ((size (registry-size db))
359 (target-size (- (oref db :max-size)
360 (* (oref db :max-size)
361 (oref db :prune-factor))))
363 (if (> size target-size)
366 (registry-collect-prune-candidates
367 db (- size target-size) sortfunc))
368 (length (registry-delete db candidates nil)))
371 (defmethod registry-collect-prune-candidates ((db registry-db) limit sortfunc)
372 "Collects pruning candidates from the registry-db object DB.
374 Proposes only entries without the :precious keys, and attempts to
375 return LIMIT such candidates. If SORTFUNC is provided, sort
376 entries first and return candidates from beginning of list."
377 (let* ((precious (oref db :precious))
378 (precious-p (lambda (entry-key)
379 (cdr (memq (car entry-key) precious))))
380 (data (oref db :data))
381 (candidates (cl-loop for k being the hash-keys of data
382 using (hash-values v)
383 when (notany precious-p v)
384 collect (cons k v))))
385 ;; We want the full entries for sorting, but should only return a
386 ;; list of entry keys.
388 (setq candidates (sort candidates sortfunc)))
389 (delq nil (cl-subseq (mapcar #'car candidates) 0 limit))))
392 ;;; registry.el ends here