Debian Codegraph @

lib/dbm/fsdbm.scm

raw
1 ;;;
2 ;;; fsdbm - dbm on filesystem
3 ;;;
4 ;;; Copyright (c) 2003-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module dbm.fsdbm
35 (extend dbm)
36 (use gauche.fcntl)
37 (use file.util)
38 (use scheme.list)
39 (use srfi.13)
40 (export <fsdbm>)
41 )
42 (select-module dbm.fsdbm)
43
44 ;;; fsdbm uses a filesystem to store dbm-type database.
45 ;;; A key is filename, and its value is the content of the file.
46 ;;; Obviously, it is not suitable for the database that has
47 ;;; lots of entries, have entries deleted and added very frequently,
48 ;;; or has long keys. The advantage is when the number of entries
49 ;;; are relatively small, and the values are relatively large while
50 ;;; keys are small.
51 ;;;
52 ;;; Fsdbm pathname is used for a directory that stores the data.
53 ;;; The top-level directory has 37 data directories (z[0-9a-z_]),
54 ;;; 'Incoming' directory, and a version file (FSDBM).
55 ;;;
56 ;;; When a new entry is added to the database, it first creates
57 ;;; the file whose name is the key under Incoming directory, and
58 ;;; stores the value into the file. Then it moves the file to
59 ;;; one of the data directories, depending on the hash value of the key.
60 ;;;
61 ;;; If key has non-alphanumeric characters, it is encoded into _XX
62 ;;; manner. If key is very long (more than 200 bytes) it is
63 ;;; chopped by 200 bytes each, and every chunk but the last one
64 ;;; are used as a directory name.
65 ;;;
66 ;;; Modification of the entry is done in the same manner. The new
67 ;;; entry is prepared in Incoming directory, and then replaced to
68 ;;; the current entry.
69 ;;;
70 ;;; With this scheme, no race condition will occur in each entry's
71 ;;; read/write. It is naturally taken care of by the file system.
72 ;;; It uses fcntl advisory lock to prevent race conditions that involve
73 ;;; more than one entries, whenever available.
74
75 (define-constant *fsdbm-version* "1.0")
76 (define-constant *version-file* "Fsdbm")
77 (define-constant *incoming-dir* "Incoming")
78 (define-constant *file-name-limit* 200)
79
80 (define-constant *hash-chars*
81 "_0123456789abcdefghijklmnopqrstuvwxyz")
82 (define-constant *hash-range* (string-length *hash-chars*))
83 (define-constant *hash-dirs* (map string (string->list *hash-chars*)))
84
85 (define-class <fsdbm-meta> (<dbm-meta>)
86 ())
87
88 (define-class <fsdbm> (<dbm>)
89 ((closed? :init-value #f))
90 :metaclass <fsdbm-meta>)
91
92 (define-method dbm-open ((self <fsdbm>))
93 (next-method)
94 (unless (slot-bound? self 'path)
95 (error "path must be set to open fsdbm database"))
96 (let ((path (ref self 'path))
97 (rwmode (ref self 'rw-mode))
98 (fmode (ref self 'file-mode)))
99 (case rwmode
100 [(:read)
101 (unless (fsdbm-directory? path)
102 (errorf "dbm-open: no fsdbm database ~a" path))]
103 [(:write)
104 (unless (fsdbm-directory? path)
105 (fsdbm-create path fmode))]
106 [(:create)
107 (fsdbm-create path fmode)]
108 )
109 self))
110
111 (define-method dbm-close ((self <fsdbm>))
112 (set! (ref self 'closed?) #t)
113 #t)
114
115
116 (define-method dbm-closed? ((self <fsdbm>))
117 (ref self 'closed?))
118
119 ;; dbm protocols
120
121 (define-method dbm-put! ((self <fsdbm>) key value)
122 (next-method)
123 (let* ((k (%dbm-k2s self key))
124 (inpath (build-path (ref self 'path) *incoming-dir* (key->path k)))
125 (path (value-file-path k (ref self 'path))))
126 (make-directory* (sys-dirname path) (dir-perm (ref self 'file-mode)))
127 (make-directory* (sys-dirname inpath) (dir-perm (ref self 'file-mode)))
128 (with-output-to-file inpath
129 (lambda () (display (%dbm-v2s self value)))
130 :if-exists :error) ;; should it be error?
131 (sys-rename inpath path)))
132
133 (define-method dbm-get ((self <fsdbm>) key . args)
134 (next-method)
135 (let ((path (value-file-path (%dbm-k2s self key) (ref self 'path))))
136 (cond ((call-with-input-file path
137 (^p (and p (%dbm-s2v self (read-chunk p))))
138 :if-does-not-exist #f))
139 ((pair? args) (car args))
140 (else (errorf "fsdbm: no data for key ~s in database ~s"
141 key self)))))
142
143 (define-method dbm-exists? ((self <fsdbm>) key)
144 (next-method)
145 (file-exists? (value-file-path (%dbm-k2s self key) (ref self 'path))))
146
147 (define-method dbm-delete! ((self <fsdbm>) key)
148 (next-method)
149 (sys-unlink (value-file-path (%dbm-k2s self key) (ref self 'path))))
150
151 (define-method dbm-fold ((self <fsdbm>) proc seed)
152 (define prefix-len
153 (string-length (build-path (ref self 'path) "a/")))
154 (define (apply-kv path seed)
155 (if (file-is-directory? path)
156 (fold apply-kv seed
157 (directory-list path :add-path? #t :children? #t))
158 (let ((k (path->key (string-drop path prefix-len))))
159 (if k
160 (proc (%dbm-s2k self k)
161 (call-with-input-file path
162 (^p (%dbm-s2v self (read-chunk p))))
163 seed)
164 seed))))
165 (next-method)
166 (fold (lambda (c seed)
167 (let1 p (build-path (ref self 'path) c)
168 (if (file-exists? p)
169 (fold apply-kv seed
170 (directory-list p :add-path? #t :children? #t))
171 seed)))
172 seed *hash-dirs*))
173
174 (define-method dbm-db-exists? ((class <fsdbm-meta>) name)
175 (fsdbm-directory? name))
176
177 (define-method dbm-db-remove ((class <fsdbm-meta>) name)
178 (unless (fsdbm-directory? name)
179 (error "given path is not an fsdbm database:" name))
180 (remove-directory* name))
181
182 (define-method dbm-db-copy ((class <fsdbm-meta>) from to)
183 (unless (fsdbm-directory? from)
184 (error "source path is not an fsdbm database:" from))
185 (copy-directory* from to))
186
187 (define-method dbm-db-move ((class <fsdbm-meta>) from to)
188 (unless (fsdbm-directory? from)
189 (error "source path is not an fsdbm database:" from))
190 ;; NB: move-directory*
191 (copy-directory* from to)
192 (remove-directory* from))
193
194 ;;
195 ;; Internal utilities
196 ;;
197
198 (define (fsdbm-directory? path)
199 (and (file-is-directory? path)
200 (file-exists? (build-path path *version-file*))))
201
202 (define (fsdbm-create path mode)
203 (when (file-exists? path) (remove-directory* path))
204 (sys-mkdir path (dir-perm mode))
205 (with-output-to-file (build-path path *version-file*)
206 (lambda () (display *fsdbm-version*)))
207 (sys-mkdir (build-path path *incoming-dir*) (dir-perm mode)))
208
209 ;; read everything from the port and returns potentially incomplete string
210 (define (read-chunk port)
211 (let loop ((elt (read-block 1024 port))
212 (chunks '()))
213 (if (eof-object? elt)
214 (let ((s (string-concatenate-reverse chunks)))
215 (or (string-incomplete->complete s) s))
216 (loop (read-block 1024 port) (cons elt chunks)))))
217
218 (define (dir-perm file-perm)
219 ;; trick: we copy 'r' bits to 'x' bits to make sure the 'readable'
220 ;; database is also searchable.
221 (logior file-perm (ash (logand file-perm #o444) -2)))
222
223 (define (key->path key)
224 (with-string-io key
225 (lambda ()
226 (write-char #\_) ;; always emit one char, so we can deal with null key
227 (let loop ((c (read-byte))
228 (count 0))
229 (cond [(eof-object? c)]
230 [(>= count *file-name-limit*)
231 (write-char #\/) (loop c 0)]
232 [(and (< c 127)
233 (char-set-contains? #[0-9a-zA-Z] (integer->char c)))
234 (write-byte c) (loop (read-byte) (+ count 1))]
235 [else
236 (format #t "_~2,'0x" c)
237 (loop (read-byte) (+ count 1))])))))
238
239 ;; reverse fn of key->path. returns #f is path is invalid.
240 (define (path->key path)
241 (let/cc return
242 (string-incomplete->complete
243 (with-string-io path
244 (lambda ()
245 ;; skip the first char
246 (unless (eqv? (read-char) #\_) (return #f))
247 (let loop ((c (read-char)))
248 (cond [(eof-object? c)]
249 [(char=? c #\/) (loop (read-char))]
250 [(char=? c #\_)
251 (let* ((c1 (read-char))
252 (c2 (read-char)))
253 (when (or (eof-object? c1) (eof-object? c2)) (return #f))
254 (unless (and (char-set-contains? #[[:xdigit:]] c1)
255 (char-set-contains? #[[:xdigit:]] c2))
256 (return #f))
257 (write-byte (+ (* (digit->integer c1 16) 16)
258 (digit->integer c2 16)))
259 (loop (read-char)))]
260 [else
261 (write-char c) (loop (read-char))])))))))
262
263 (define (path->hash path)
264 ;; NB: we use our own hash fn to keep backward compatibility.
265 (define mask (- (expt 2 32) 1))
266 (define (shash hval mod)
267 (let1 b (read-byte)
268 (if (eof-object? b)
269 (modulo hval mod)
270 (shash (logand (+ hval (ash hval 3) b) mask) mod))))
271 (string (string-ref *hash-chars*
272 (with-input-from-string path
273 (cut shash 0 *hash-range*)))))
274
275 (define (value-file-path key :optional (dir #f))
276 (let1 p (key->path key)
277 (if dir
278 (build-path dir (path->hash p) p)
279 (build-path (path->hash p) p))))