1 /* ********************************************************************************************* *
2 * The basic API of QDBM Copyright (C) 2000-2007 Mikio Hirabayashi
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 * D translation and "d-fication" by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
18 * ********************************************************************************************* */
19 // key/value database based on tokyo kabinet
20 module iv
.depot
/*is aliced*/;
25 class DepotException
: Exception
{
26 this (Depot
.Error ecode
, string file
=__FILE__
, usize line
=__LINE__
, Throwable next
=null) pure nothrow @safe @nogc {
27 super(errorMessage(ecode
), file
, line
, next
);
30 /** Get a message string corresponding to an error code.
33 * ecode = an error code
36 * The message string of the error code.
38 static string
errorMessage (Depot
.Error ecode
) @safe pure nothrow @nogc {
39 switch (ecode
) with (Depot
.Error
) {
40 case NOERR
: return "no error";
41 case FATAL
: return "with fatal error";
42 case CLOSED
: return "database not opened error";
43 case OPENED
: return "already opened database error";
44 case MODE
: return "invalid mode";
45 case BROKEN
: return "broken database file";
46 case KEEP
: return "existing record";
47 case NOITEM
: return "no item found";
48 case ALLOC
: return "memory allocation error";
49 case MAP
: return "memory mapping error";
50 case OPEN
: return "open error";
51 case CLOSE
: return "close error";
52 case TRUNC
: return "trunc error";
53 case SYNC
: return "sync error";
54 case STAT
: return "stat error";
55 case SEEK
: return "seek error";
56 case READ
: return "read error";
57 case WRITE
: return "write error";
58 case LOCK
: return "lock error";
59 case UNLINK
: return "unlink error";
60 case MKDIR
: return "mkdir error";
61 case RMDIR
: return "rmdir error";
62 case MISC
: return "miscellaneous error";
63 default: return "(invalid ecode)";
71 public final class Depot
{
72 public import core
.sys
.posix
.sys
.types
: time_t
;
73 private import std
.typecons
: Flag
, Yes
, No
;
75 enum QDBM_VERSION
= "1.8.78"; /// library version
76 enum QDBM_LIBVER
= 1414;
78 this (const(char)[] name
, int omode
=READER
, int bnum
=-1) { open(name
, omode
, bnum
); }
82 string m_name
; // name of the database file; terminated with '\0', but '\0' is not a string part
83 bool m_wmode
; // whether to be writable
84 ulong m_inode
; // inode of the database file
85 time_t m_mtime
; // last modified time of the database
86 int m_fd
= -1; // file descriptor of the database file
87 long m_fsiz
; // size of the database file
88 char* m_map
; // pointer to the mapped memory
89 int m_msiz
; // size of the mapped memory
90 int* m_buckets
; // pointer to the bucket array
91 int m_bnum
; // number of the bucket array
92 int m_rnum
; // number of records
93 bool m_fatal
; // whether a fatal error occured
94 int m_ioff
; // offset of the iterator
95 int* m_fbpool
; // free block pool
96 int m_fbpsiz
; // size of the free block pool
97 int m_fbpinc
; // incrementor of update of the free block pool
98 int m_alignment
; // basic size of alignment (can be negative; why?)
101 enum DP_FILEMODE
= 384; // 0o600: permission of a creating file
103 enum DP_MAGIC
= "[DEPOT]\n\f"; // magic on environments of big endian
105 enum DP_MAGIC
= "[depot]\n\f"; // magic on environments of little endian
107 enum DP_DEFBNUM
= 8191; // default bucket number
108 enum DP_FBPOOLSIZ
= 16; // size of free block pool
109 enum DP_ENTBUFSIZ
= 128; // size of the entity buffer
110 enum DP_STKBUFSIZ
= 256; // size of the stack key buffer
111 enum DP_WRTBUFSIZ
= 8192; // size of the writing buffer
112 enum DP_FSBLKSIZ
= 4096; // size of a block of the file system
113 enum DP_OPTBLOAD
= 0.25; // ratio of bucket loading at optimization
114 enum DP_OPTRUNIT
= 256; // number of records in a process of optimization
115 enum DP_NUMBUFSIZ
= 32; // size of a buffer for a number
116 enum DP_IOBUFSIZ
= 8192; // size of an I/O buffer
117 enum DP_TMPFSUF
= ".dptmp"; // suffix of a temporary file
120 // enumeration for the flag of a record
122 DP_RECFDEL
= 0x01, // deleted
123 DP_RECFREUSE
= 0x02, // reusable
126 static align(1) struct QDBMHeader
{
128 char[12] signature
; // DP_MAGICNUMB or DP_MAGICNUML, padded with '\0'
129 char[4] versionstr
; // string, padded with '\0'
134 int nbuckets
; // number of buckets
136 int nrecords
; // number of records
139 static assert(QDBMHeader
.sizeof
== 48);
140 static assert(QDBMHeader
.signature
.offsetof
== 0);
141 static assert(QDBMHeader
.versionstr
.offsetof
== 12);
142 static assert(QDBMHeader
.flags
.offsetof
== 16);
143 static assert(QDBMHeader
.filesize
.offsetof
== 24);
144 static assert(QDBMHeader
.nbuckets
.offsetof
== 32);
145 static assert(QDBMHeader
.nrecords
.offsetof
== 40);
147 static align(1) struct RecordHeader
{
150 int hash2
; // value of the second hash function
151 int ksiz
; // the size of the key
152 int vsiz
; // the size of the value
153 int psiz
; // the size of the padding bytes
154 int left
; // the offset of the left child
155 int right
; // the offset of the right child
157 /* Get the size of a record in a database file.
160 * The return value is the size of a record in a database file
162 @property int recsize () const @safe pure nothrow @nogc {
163 return cast(int)(RecordHeader
.sizeof
+ksiz
+vsiz
+psiz
);
166 static assert(RecordHeader
.sizeof
== 7*int.sizeof
);
167 static assert(RecordHeader
.flags
.offsetof
== 0*int.sizeof
);
168 static assert(RecordHeader
.hash2
.offsetof
== 1*int.sizeof
);
169 static assert(RecordHeader
.ksiz
.offsetof
== 2*int.sizeof
);
170 static assert(RecordHeader
.vsiz
.offsetof
== 3*int.sizeof
);
171 static assert(RecordHeader
.psiz
.offsetof
== 4*int.sizeof
);
172 static assert(RecordHeader
.left
.offsetof
== 5*int.sizeof
);
173 static assert(RecordHeader
.right
.offsetof
== 6*int.sizeof
);
176 /// enumeration for error codes
179 FATAL
, /// with fatal error
180 CLOSED
, /// trying to operate on closed db
181 OPENED
, /// trying to opend an already opened db
182 MODE
, /// invalid mode
183 BROKEN
, /// broken database file
184 KEEP
, /// existing record
185 NOITEM
, /// no item found
186 ALLOC
, /// memory allocation error
187 MAP
, /// memory mapping error
189 CLOSE
, /// close error
190 TRUNC
, /// trunc error
195 WRITE
, /// write error
197 UNLINK
, /// unlink error
198 MKDIR
, /// mkdir error
199 RMDIR
, /// rmdir error
200 MISC
, /// miscellaneous error
203 /// enumeration for open modes
205 READER
= 1<<0, /// open as a reader
206 WRITER
= 1<<1, /// open as a writer
207 CREAT
= 1<<2, /// a writer creating
208 TRUNC
= 1<<3, /// a writer truncating
209 NOLCK
= 1<<4, /// open without locking
210 LCKNB
= 1<<5, /// lock without blocking
211 SPARSE
= 1<<6, /// create as a sparse file
214 /// enumeration for write modes
216 OVER
, /// overwrite an existing value
217 KEEP
, /// keep an existing value
218 CAT
, /// concatenate values
223 @property bool opened () const @safe pure nothrow @nogc { return (m_fd
>= 0); }
225 void checkOpened (string file
=__FILE__
, usize line
=__LINE__
) {
226 if (m_fatal
) raise(Error
.FATAL
, file
, line
);
227 if (!opened
) raise(Error
.CLOSED
, file
, line
);
230 void checkWriting (string file
=__FILE__
, usize line
=__LINE__
) {
231 checkOpened(file
, line
);
232 if (!m_wmode
) raise(Error
.MODE
, file
, line
);
235 /** Free `malloc()`ed pointer and set variable to `null`.
238 * ptr = the pointer to variable holding a pointer
240 static freeptr(T
) (ref T
* ptr
) {
241 import core
.stdc
.stdlib
: free
;
243 free(cast(void*)ptr
);
248 /** Get a database handle.
250 * While connecting as a writer, an exclusive lock is invoked to the database file.
251 * While connecting as a reader, a shared lock is invoked to the database file. The thread
252 * blocks until the lock is achieved. If `NOLCK` is used, the application is responsible
253 * for exclusion control.
256 * name = the name of a database file
257 * omode = specifies the connection mode: `WRITER` as a writer, `READER` as a reader.
258 * If the mode is `WRITER`, the following may be added by bitwise or:
259 * `CREAT`, which means it creates a new database if not exist,
260 * `TRUNC`, which means it creates a new database regardless if one exists.
261 * Both of `READER` and `WRITER` can be added to by bitwise or:
262 * `NOLCK`, which means it opens a database file without file locking, or
263 * `LCKNB`, which means locking is performed without blocking.
264 * `CREAT` can be added to by bitwise or:
265 * `SPARSE`, which means it creates a database file as a sparse file.
266 * bnum = the number of elements of the bucket array.
267 * If it is not more than 0, the default value is specified. The size of a bucket array is
268 * determined on creating, and can not be changed except for by optimization of the database.
269 * Suggested size of a bucket array is about from 0.5 to 4 times of the number of all records
271 * errcode = the error code (can be `null`)
274 * DepotException on various errors
276 void open (const(char)[] name
, int omode
=READER
, int bnum
=-1) {
277 import core
.sys
.posix
.fcntl
: open
, O_CREAT
, O_RDONLY
, O_RDWR
;
278 import core
.sys
.posix
.sys
.mman
: mmap
, munmap
, MAP_FAILED
, PROT_READ
, PROT_WRITE
, MAP_SHARED
;
279 import core
.sys
.posix
.sys
.stat
: fstat
, lstat
, S_ISREG
, stat_t
;
280 import core
.sys
.posix
.unistd
: close
, ftruncate
;
290 if (opened
) raise(Error
.OPENED
);
292 char[] namez
; // unique
293 // add '\0' after string
296 while (len
< name
.length
&& name
[len
]) ++len
;
297 namez
= new char[](len
+1);
298 namez
[0..$-1] = name
[0..len
];
304 if (omode
&CREAT
) mode |
= O_CREAT
;
306 if ((fd
= open(namez
.ptr
, mode
, DP_FILEMODE
)) == -1) raise(Error
.OPEN
);
307 scope(failure
) close(fd
);
308 if ((omode
&NOLCK
) == 0) fdlock(fd
, omode
&WRITER
, omode
&LCKNB
);
309 if ((omode
&WRITER
) && (omode
&TRUNC
)) {
310 if (ftruncate(fd
, 0) == -1) raise(Error
.TRUNC
);
312 if (fstat(fd
, &sbuf
) == -1 ||
!S_ISREG(sbuf
.st_mode
) ||
(sbuf
.st_ino
== 0 && lstat(namez
.ptr
, &sbuf
) == -1)) raise(Error
.STAT
);
314 mtime
= sbuf
.st_mtime
;
316 if ((omode
&WRITER
) && fsiz
== 0) {
317 hbuf
.signature
[] = 0;
318 hbuf
.versionstr
[] = 0;
319 hbuf
.signature
[0..DP_MAGIC
.length
] = DP_MAGIC
[];
321 import core
.stdc
.stdio
: snprintf
;
322 snprintf(hbuf
.versionstr
.ptr
, hbuf
.versionstr
.length
, "%d", QDBM_LIBVER
/100);
324 bnum
= (bnum
< 1 ? DP_DEFBNUM
: bnum
);
325 bnum
= primenum(bnum
);
326 hbuf
.nbuckets
= bnum
;
328 fsiz
= hbuf
.sizeof
+bnum
*int.sizeof
;
329 hbuf
.filesize
= cast(int)fsiz
;
330 fdseekwrite(fd
, 0, (&hbuf
)[0..1]);
333 fdseekwrite(fd
, fsiz
-1, (&c
)[0..1]);
335 ubyte[DP_IOBUFSIZ
] ebuf
= 0; // totally empty buffer initialized with 0 %-)
336 usize pos
= hbuf
.sizeof
;
338 usize left
= cast(usize
)fsiz
-pos
;
339 usize wr
= (left
> ebuf
.length ? ebuf
.length
: left
);
340 fdseekwrite(fd
, pos
, ebuf
[0..wr
]);
346 fdseekread(fd
, 0, (&hbuf
)[0..1]);
347 } catch (Exception
) {
350 //k8: the original code checks header only if ((omode&NOLCK) == 0); why?
351 if (hbuf
.signature
[0..DP_MAGIC
.length
] != DP_MAGIC
) raise(Error
.BROKEN
);
352 if (hbuf
.filesize
!= fsiz
) raise(Error
.BROKEN
);
353 bnum
= hbuf
.nbuckets
;
354 if (bnum
< 1 || hbuf
.nrecords
< 0 || fsiz
< QDBMHeader
.sizeof
+bnum
*int.sizeof
) raise(Error
.BROKEN
);
355 msiz
= QDBMHeader
.sizeof
+bnum
*int.sizeof
;
356 map
= cast(char*)mmap(null, msiz
, PROT_READ|
(mode
&WRITER ? PROT_WRITE
: 0), MAP_SHARED
, fd
, 0);
357 if (map
== MAP_FAILED
) raise(Error
.MAP
);
358 scope(failure
) munmap(map
, msiz
);
361 import core
.stdc
.stdlib
: malloc
;
362 fbpool
= cast(int*)malloc(DP_FBPOOLSIZ
*2*int.sizeof
);
364 if (fbpool
is null) raise(Error
.ALLOC
);
366 import std
.exception
: assumeUnique
;
367 m_name
= namez
[0..$-1].assumeUnique
;
369 m_wmode
= (mode
&WRITER
) != 0;
375 m_msiz
= cast(int)msiz
;
376 m_buckets
= cast(int*)(map
+QDBMHeader
.sizeof
);
378 m_rnum
= hbuf
.nrecords
;
382 m_fbpool
[0..DP_FBPOOLSIZ
*2] = -1;
383 m_fbpsiz
= DP_FBPOOLSIZ
*2;
388 /** Close a database handle.
391 * If successful, the return value is true, else, it is false.
392 * Because the region of a closed handle is released, it becomes impossible to use the handle.
393 * Updating a database is assured to be written when the handle is closed. If a writer opens
394 * a database but does not close it appropriately, the database will be broken.
397 * DepotException on various errors
400 import core
.sys
.posix
.sys
.mman
: munmap
, MAP_FAILED
;
401 import core
.sys
.posix
.unistd
: close
;
403 bool fatal
= m_fatal
;
404 Error err
= Error
.NOERR
;
405 if (m_wmode
) updateHeader();
407 if (munmap(m_map
, m_msiz
) == -1) err
= Error
.MAP
;
410 if (close(m_fd
) == -1) err
= Error
.CLOSE
;
415 if (fatal
) err
= Error
.FATAL
;
416 if (err
!= Error
.NOERR
) raise(err
);
422 * kbuf = the pointer to the region of a key
423 * vbuf = the pointer to the region of a value
424 * dmode = behavior when the key overlaps, by the following values:
425 * `WMode.OVER`, which means the specified value overwrites the existing one,
426 * `WMode.KEEP`, which means the existing value is kept,
427 * `WMode.CAT`, which means the specified value is concatenated at the end of the existing value.
430 * DepotException on various errors
432 void put (const(void)[] kbuf
, const(void)[] vbuf
, WMode dmode
=WMode
.OVER
) {
433 RecordHeader head
, next
;
434 int hash
, bi
, off
, entoff
, newoff
, fdel
, mroff
, mrsiz
, mi
, min
;
437 char[DP_ENTBUFSIZ
] ebuf
;
441 hash
= secondhash(kbuf
);
442 if (recsearch(kbuf
, hash
, &bi
, &off
, &entoff
, head
, ebuf
[], &ee
, Yes
.delhit
)) {
444 fdel
= head
.flags
&DP_RECFDEL
;
445 if (dmode
== WMode
.KEEP
&& !fdel
) raise(Error
.KEEP
);
447 head
.psiz
+= head
.vsiz
;
451 nsiz
= RecordHeader
.sizeof
+kbuf
.length
+vbuf
.length
;
452 if (dmode
== WMode
.CAT
) nsiz
+= head
.vsiz
;
453 if (off
+rsiz
>= m_fsiz
) {
455 head
.psiz
+= nsiz
-rsiz
;
460 while (nsiz
> rsiz
&& off
+rsiz
< m_fsiz
) {
461 rechead(off
+rsiz
, next
, null, null);
462 if ((next
.flags
&DP_RECFREUSE
) == 0) break;
463 head
.psiz
+= next
.recsize
;
464 rsiz
+= next
.recsize
;
466 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
467 if (m_fbpool
[i
] >= off
&& m_fbpool
[i
] < off
+rsiz
) {
468 m_fbpool
[i
] = m_fbpool
[i
+1] = -1;
473 recover(off
, head
, vbuf
, (dmode
== WMode
.CAT ? Yes
.catmode
: No
.catmode
));
476 scope(failure
) { m_fatal
= true; freeptr(tval
); }
477 if (dmode
== WMode
.CAT
) {
478 import core
.stdc
.string
: memcpy
;
479 if (ee
&& RecordHeader
.sizeof
+head
.ksiz
+head
.vsiz
<= DP_ENTBUFSIZ
) {
480 import core
.stdc
.stdlib
: malloc
;
481 tval
= cast(char*)malloc(head
.vsiz
+vbuf
.length
+1);
482 if (tval
is null) { m_fatal
= true; raise(Error
.ALLOC
); }
483 memcpy(tval
, ebuf
.ptr
+(RecordHeader
.sizeof
+head
.ksiz
), head
.vsiz
);
485 import core
.stdc
.stdlib
: realloc
;
486 tval
= recval(off
, head
);
487 swap
= cast(char*)realloc(tval
, head
.vsiz
+vbuf
.length
+1);
488 if (swap
is null) raise(Error
.ALLOC
);
491 memcpy(tval
+head
.vsiz
, vbuf
.ptr
, vbuf
.length
);
492 immutable newsize
= head
.vsiz
+vbuf
.length
;
493 vbuf
= tval
[0..newsize
];
497 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
498 if (m_fbpool
[i
+1] < nsiz
) continue;
499 if (mi
== -1 || m_fbpool
[i
+1] < min
) {
505 mroff
= m_fbpool
[mi
];
506 mrsiz
= m_fbpool
[mi
+1];
513 recdelete(off
, head
, Yes
.reusable
);
514 if (mroff
> 0 && nsiz
<= mrsiz
) {
515 recrewrite(mroff
, mrsiz
, kbuf
, vbuf
, hash
, head
.left
, head
.right
);
518 newoff
= recappend(kbuf
, vbuf
, hash
, head
.left
, head
.right
);
525 scope(failure
) m_fatal
= true;
526 newoff
= recappend(kbuf
, vbuf
, hash
, 0, 0);
531 fdseekwritenum(m_fd
, entoff
, newoff
);
533 m_buckets
[bi
] = newoff
;
541 * kbuf = the pointer to the region of a key
544 * If successful, the return value is true, else, it is false.
545 * False is returned when no record corresponds to the specified key.
548 * DepotException on various errors
550 bool del (const(void)[] kbuf
) {
552 int hash
, bi
, off
, entoff
;
554 char[DP_ENTBUFSIZ
] ebuf
;
556 hash
= secondhash(kbuf
);
557 if (!recsearch(kbuf
, hash
, &bi
, &off
, &entoff
, head
, ebuf
[], &ee
)) return false; //raise(Error.NOITEM);
558 recdelete(off
, head
, No
.reusable
);
563 /** Retrieve a record.
566 * kbuf = the pointer to the region of a key
567 * start = the offset address of the beginning of the region of the value to be read
568 * max = specifies the max size to be read; if it is `uint.max`, the size to read is unlimited
569 * sp = the pointer to a variable to which the size of the region of the return
570 * value is assigned; if it is `null`, it is not used
573 * If successful, the return value is the pointer to the region of the value of the
574 * corresponding record, else, it is `null`. `null` is returned when no record corresponds to
575 * the specified key or the size of the value of the corresponding record is less than `start`.
576 * Because an additional zero code is appended at the end of the region of the return value,
577 * the return value can be treated as a character string. Because the region of the return
578 * value is allocated with the `malloc` call, it should be released with the `freeptr` call if it
579 * is no longer in use.
582 * DepotException on various errors
584 char* get (const(void)[] kbuf
, uint start
=0, uint max
=uint.max
, usize
* sp
=null) {
586 int hash
, bi
, off
, entoff
;
589 char[DP_ENTBUFSIZ
] ebuf
;
591 if (sp
!is null) *sp
= 0;
593 hash
= secondhash(kbuf
);
594 if (!recsearch(kbuf
, hash
, &bi
, &off
, &entoff
, head
, ebuf
[], &ee
)) return null; //raise(Error.NOITEM);
595 if (start
> head
.vsiz
) return null; //raise(Error.NOITEM);
596 if (start
== head
.vsiz
) {
597 import core
.stdc
.stdlib
: malloc
;
598 vbuf
= cast(char*)malloc(1);
602 scope(failure
) m_fatal
= true; // any failure beyond this point is fatal
603 if (ee
&& RecordHeader
.sizeof
+head
.ksiz
+head
.vsiz
<= DP_ENTBUFSIZ
) {
604 import core
.stdc
.stdlib
: malloc
;
605 import core
.stdc
.string
: memcpy
;
607 if (max
== uint.max
) {
610 vsiz
= (max
< head
.vsiz ? max
: head
.vsiz
);
612 vbuf
= cast(char*)malloc(vsiz
+1);
613 if (vbuf
is null) raise(Error
.ALLOC
);
614 memcpy(vbuf
, ebuf
.ptr
+(RecordHeader
.sizeof
+head
.ksiz
+start
), vsiz
);
617 vbuf
= recval(off
, head
, start
, max
);
620 if (max
== uint.max
) {
623 *sp
= (max
< head
.vsiz ? max
: head
.vsiz
);
629 /** Retrieve a record and write the value into a buffer.
632 * vbuf = the pointer to a buffer into which the value of the corresponding record is written
633 * kbuf = the pointer to the region of a key
634 * start = the offset address of the beginning of the region of the value to be read
637 * If successful, the return value is the read data (slice of vbuf), else, it is `null`.
638 * `null` returned when no record corresponds to the specified key or the size of the value
639 * of the corresponding record is less than `start`.
640 * Note that no additional zero code is appended at the end of the region of the writing buffer.
643 * DepotException on various errors
645 char[] getwb (void[] vbuf
, const(void)[] kbuf
, uint start
=0) {
647 int hash
, bi
, off
, entoff
;
650 char[DP_ENTBUFSIZ
] ebuf
;
652 hash
= secondhash(kbuf
);
653 if (!recsearch(kbuf
, hash
, &bi
, &off
, &entoff
, head
, ebuf
[], &ee
)) return null; //raise(Error.NOITEM);
654 if (start
> head
.vsiz
) return null; //raise(Error.NOITEM);
655 scope(failure
) m_fatal
= true; // any failure beyond this point is fatal
656 if (ee
&& RecordHeader
.sizeof
+head
.ksiz
+head
.vsiz
<= DP_ENTBUFSIZ
) {
657 import core
.stdc
.string
: memcpy
;
659 vsiz
= (vbuf
.length
< head
.vsiz ? vbuf
.length
: head
.vsiz
);
660 memcpy(vbuf
.ptr
, ebuf
.ptr
+(RecordHeader
.sizeof
+head
.ksiz
+start
), vsiz
);
662 vsiz
= recvalwb(vbuf
, off
, head
, start
);
664 return cast(char[])(vbuf
[0..vsiz
]);
667 /** Get the size of the value of a record.
670 * kbuf = the pointer to the region of a key
673 * If successful, the return value is the size of the value of the corresponding record, else, it is -1.
674 * Because this function does not read the entity of a record, it is faster than `get`.
677 * DepotException on various errors
679 usize
vsize (const(void)[] kbuf
) {
681 int hash
, bi
, off
, entoff
;
683 char[DP_ENTBUFSIZ
] ebuf
;
685 hash
= secondhash(kbuf
);
686 if (!recsearch(kbuf
, hash
, &bi
, &off
, &entoff
, head
, ebuf
[], &ee
)) return -1; //raise(Error.NOITEM);
690 /** Initialize the iterator of a database handle.
693 * If successful, the return value is true, else, it is false.
694 * The iterator is used in order to access the key of every record stored in a database.
697 * DepotException on various errors
704 /** Get the next key of the iterator.
707 * sp = the pointer to a variable to which the size of the region of the return value is assigned.
708 * If it is `null`, it is not used.
711 * If successful, the return value is the pointer to the region of the next key, else, it is
712 * `null`. `null` is returned when no record is to be get out of the iterator.
713 * Because an additional zero code is appended at the end of the region of the return value,
714 * the return value can be treated as a character string. Because the region of the return
715 * value is allocated with the `malloc` call, it should be released with the `freeptr` call if
716 * it is no longer in use. It is possible to access every record by iteration of calling
717 * this function. However, it is not assured if updating the database is occurred while the
718 * iteration. Besides, the order of this traversal access method is arbitrary, so it is not
719 * assured that the order of storing matches the one of the traversal access.
722 * DepotException on various errors
724 char* itNext (usize
* sp
=null) {
728 char[DP_ENTBUFSIZ
] ebuf
;
730 if (sp
!is null) *sp
= 0;
732 off
= QDBMHeader
.sizeof
+m_bnum
*int.sizeof
;
733 off
= (off
> m_ioff ? off
: m_ioff
);
734 scope(failure
) m_fatal
= true; // any failure is fatal here
735 while (off
< m_fsiz
) {
736 rechead(off
, head
, ebuf
[], &ee
);
737 if (head
.flags
&DP_RECFDEL
) {
740 if (ee
&& RecordHeader
.sizeof
+head
.ksiz
<= DP_ENTBUFSIZ
) {
741 import core
.stdc
.stdlib
: malloc
;
742 import core
.stdc
.string
: memcpy
;
743 kbuf
= cast(char*)malloc(head
.ksiz
+1);
744 if (kbuf
is null) raise(Error
.ALLOC
);
745 memcpy(kbuf
, ebuf
.ptr
+RecordHeader
.sizeof
, head
.ksiz
);
746 kbuf
[head
.ksiz
] = '\0';
748 kbuf
= reckey(off
, head
);
750 m_ioff
= cast(int)(off
+head
.recsize
);
751 if (sp
!is null) *sp
= head
.ksiz
;
755 //raise(Error.NOITEM);
759 /** Set alignment of a database handle.
761 * If alignment is set to a database, the efficiency of overwriting values is improved.
762 * The size of alignment is suggested to be average size of the values of the records to be
763 * stored. If alignment is positive, padding whose size is multiple number of the alignment
764 * is placed. If alignment is negative, as `vsiz` is the size of a value, the size of padding
765 * is calculated with `(vsiz/pow(2, abs(alignment)-1))'. Because alignment setting is not
766 * saved in a database, you should specify alignment every opening a database.
769 * alignment = the size of alignment
772 * DepotException on various errors
774 @property void alignment (int alignment
) {
776 m_alignment
= alignment
;
779 /** Get alignment of a database handle.
782 * The size of alignment
785 * DepotException on various errors
787 @property int alignment () {
792 /** Set the size of the free block pool of a database handle.
794 * The default size of the free block pool is 16. If the size is greater, the space efficiency
795 * of overwriting values is improved with the time efficiency sacrificed.
798 * size = the size of the free block pool of a database
801 * DepotException on various errors
803 @property void freeBlockPoolSize (uint size
) {
804 import core
.stdc
.stdlib
: realloc
;
808 fbpool
= cast(int*)realloc(m_fbpool
, size
*int.sizeof
+1);
809 if (fbpool
is null) raise(Error
.ALLOC
);
810 fbpool
[0..size
] = -1;
815 /** Get the size of the free block pool of a database handle.
818 * The size of the free block pool of a database
821 * DepotException on various errors
823 @property uint freeBlockPoolSize () {
828 /** Synchronize updating contents with the file and the device.
830 * This function is useful when another process uses the connected database file.
833 * DepotException on various errors
836 import core
.sys
.posix
.sys
.mman
: msync
, MS_SYNC
;
837 import core
.sys
.posix
.unistd
: fsync
;
840 if (msync(m_map
, m_msiz
, MS_SYNC
) == -1) {
844 if (fsync(m_fd
) == -1) {
850 /** Optimize a database.
852 * In an alternating succession of deleting and storing with overwrite or concatenate,
853 * dispensable regions accumulate. This function is useful to do away with them.
856 * bnum = the number of the elements of the bucket array. If it is not more than 0,
857 * the default value is specified
860 * DepotException on various errors
862 void optimize (int bnum
=-1) {
863 import core
.sys
.posix
.sys
.mman
: mmap
, munmap
, MAP_FAILED
, MAP_SHARED
, PROT_READ
, PROT_WRITE
;
864 import core
.sys
.posix
.unistd
: ftruncate
, unlink
;
870 int[DP_OPTRUNIT
] ksizs
, vsizs
;
871 char[DP_ENTBUFSIZ
] ebuf
;
872 char*[DP_OPTRUNIT
] kbufs
, vbufs
;
875 bnum
= cast(int)(m_rnum
*(1.0/DP_OPTBLOAD
))+1;
876 if (bnum
< DP_DEFBNUM
/2) bnum
= DP_DEFBNUM
/2;
878 tdepot
= new Depot(m_name
~DP_TMPFSUF
, WRITER|CREAT|TRUNC
, bnum
);
880 import std
.exception
: collectException
;
882 unlink(tdepot
.m_name
.ptr
);
883 collectException(tdepot
.close());
885 scope(exit
) delete tdepot
;
886 tdepot
.flags
= flags
;
887 tdepot
.m_alignment
= m_alignment
;
888 off
= QDBMHeader
.sizeof
+m_bnum
*int.sizeof
;
890 while (off
< m_fsiz
) {
891 rechead(off
, head
, ebuf
[], &ee
);
892 if ((head
.flags
&DP_RECFDEL
) == 0) {
893 if (ee
&& RecordHeader
.sizeof
+head
.ksiz
<= DP_ENTBUFSIZ
) {
894 import core
.stdc
.stdlib
: malloc
;
895 import core
.stdc
.string
: memcpy
;
896 if ((kbufs
[unum
] = cast(char*)malloc(head
.ksiz
+1)) is null) raise(Error
.ALLOC
);
897 memcpy(kbufs
[unum
], ebuf
.ptr
+RecordHeader
.sizeof
, head
.ksiz
);
898 if (RecordHeader
.sizeof
+head
.ksiz
+head
.vsiz
<= DP_ENTBUFSIZ
) {
899 if ((vbufs
[unum
] = cast(char*)malloc(head
.vsiz
+1)) is null) raise(Error
.ALLOC
);
900 memcpy(vbufs
[unum
], ebuf
.ptr
+(RecordHeader
.sizeof
+head
.ksiz
), head
.vsiz
);
902 vbufs
[unum
] = recval(off
, head
);
905 kbufs
[unum
] = reckey(off
, head
);
906 vbufs
[unum
] = recval(off
, head
);
908 ksizs
[unum
] = head
.ksiz
;
909 vsizs
[unum
] = head
.vsiz
;
911 if (unum
>= DP_OPTRUNIT
) {
912 for (uint i
= 0; i
< unum
; ++i
) {
913 assert(kbufs
[i
] !is null && vbufs
[i
] !is null);
914 tdepot
.put(kbufs
[i
][0..ksizs
[i
]], vbufs
[i
][0..vsizs
[i
]], WMode
.KEEP
);
923 for (uint i
= 0; i
< unum
; ++i
) {
924 assert(kbufs
[i
] !is null && vbufs
[i
] !is null);
925 tdepot
.put(kbufs
[i
][0..ksizs
[i
]], vbufs
[i
][0..vsizs
[i
]], WMode
.KEEP
);
930 if (munmap(m_map
, m_msiz
) == -1) raise(Error
.MAP
);
931 m_map
= cast(char*)MAP_FAILED
;
932 if (ftruncate(m_fd
, 0) == -1) raise(Error
.TRUNC
);
933 fcopy(m_fd
, 0, tdepot
.m_fd
, 0);
934 m_fsiz
= tdepot
.m_fsiz
;
935 m_bnum
= tdepot
.m_bnum
;
937 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
938 m_fbpool
[i
] = m_fbpool
[i
+1] = -1;
940 m_msiz
= tdepot
.m_msiz
;
941 m_map
= cast(char*)mmap(null, m_msiz
, PROT_READ|PROT_WRITE
, MAP_SHARED
, m_fd
, 0);
942 if (m_map
== MAP_FAILED
) raise(Error
.MAP
);
943 m_buckets
= cast(int*)(m_map
+QDBMHeader
.sizeof
);
944 string tempname
= tdepot
.m_name
; // with trailing zero
946 if (unlink(tempname
.ptr
) == -1) raise(Error
.UNLINK
);
949 /** Get the name of a database.
952 * If successful, the return value is the pointer to the region of the name of the database,
953 * else, it is `null`.
954 * Because the region of the return value is allocated with the `malloc` call, it should be
955 * released with the `freeptr` call if it is no longer in use.
958 * DepotException on various errors
960 @property string
name () const @safe pure nothrow @nogc {
964 /** Get the size of a database file.
967 * If successful, the return value is the size of the database file, else, it is -1.
970 * DepotException on various errors
972 @property long fileSize () {
978 /** Get the number of the elements of the bucket array.
981 * If successful, the return value is the number of the elements of the bucket array, else, it is -1.
984 * DepotException on various errors
986 @property int bucketCount () {
991 /** Get the number of the used elements of the bucket array.
993 * This function is inefficient because it accesses all elements of the bucket array.
996 * If successful, the return value is the number of the used elements of the bucket array, else, it is -1.
999 * DepotException on various errors
1004 for (uint i
= 0; i
< m_bnum
; ++i
) if (m_buckets
[i
]) ++hits
;
1008 /** Get the number of the records stored in a database.
1011 * If successful, the return value is the number of the records stored in the database, else, it is -1.
1014 * DepotException on various errors
1016 @property int recordCount () {
1021 /** Check whether a database handle is a writer or not.
1024 * The return value is true if the handle is a writer, false if not.
1026 @property bool writable () const @safe pure nothrow @nogc {
1027 return (opened
&& m_wmode
);
1030 /** Check whether a database has a fatal error or not.
1033 * The return value is true if the database has a fatal error, false if not.
1035 @property bool fatalError () const @safe pure nothrow @nogc {
1039 /** Get the inode number of a database file.
1042 * The return value is the inode number of the database file.
1045 * DepotException on various errors
1047 @property long inode () {
1052 /** Get the last modified time of a database.
1055 * The return value is the last modified time of the database.
1058 * DepotException on various errors
1060 @property time_t
mtime () {
1065 /** Get the file descriptor of a database file.
1068 * The return value is the file descriptor of the database file.
1069 * Handling the file descriptor of a database file directly is not suggested.
1072 * DepotException on various errors
1074 @property int fdesc () {
1079 /** Remove a database file.
1082 * name = the name of a database file
1085 * DepotException on various errors
1087 static void remove (const(char)[] name
) {
1088 import core
.stdc
.errno
: errno
, ENOENT
;
1089 import core
.sys
.posix
.sys
.stat
: lstat
, stat_t
;
1090 import core
.sys
.posix
.unistd
: unlink
;
1091 import std
.string
: toStringz
;
1093 assert(name
.length
);
1094 auto namez
= name
.toStringz
;
1095 if (lstat(namez
, &sbuf
) == -1) {
1096 if (errno
!= ENOENT
) straise(Error
.STAT
);
1100 //k8:??? try to open the file to check if it's not locked or something
1101 auto depot
= new Depot(name
, WRITER|TRUNC
);
1104 if (unlink(namez
) == -1) {
1105 if (errno
!= ENOENT
) straise(Error
.UNLINK
);
1110 /** Repair a broken database file.
1112 * There is no guarantee that all records in a repaired database file correspond to the original
1113 * or expected state.
1116 * name = the name of a database file
1119 * true if ok, false is there were some errors
1122 * DepotException on various errors
1124 bool repair (const(char)[] name
) {
1125 import core
.sys
.posix
.fcntl
: open
, O_RDWR
;
1126 import core
.sys
.posix
.sys
.stat
: lstat
, stat_t
;
1127 import core
.sys
.posix
.unistd
: close
, ftruncate
, unlink
;
1132 int fd
, flags
, bnum
, tbnum
, rsiz
, ksiz
, vsiz
;
1136 assert(name
.length
);
1138 import std
.string
: toStringz
;
1139 auto namez
= name
.toStringz
;
1140 if (lstat(namez
, &sbuf
) == -1) raise(Error
.STAT
);
1141 fsiz
= sbuf
.st_size
;
1142 if ((fd
= open(namez
, O_RDWR
, DP_FILEMODE
)) == -1) raise(Error
.OPEN
);
1144 scope(exit
) if (fd
>= 0) close(fd
);
1145 fdseekread(fd
, 0, (&dbhead
)[0..1]);
1146 flags
= dbhead
.flags
;
1147 bnum
= dbhead
.nbuckets
;
1148 tbnum
= dbhead
.nrecords
*2;
1149 if (tbnum
< DP_DEFBNUM
) tbnum
= DP_DEFBNUM
;
1150 tdepot
= new Depot(name
~DP_TMPFSUF
, WRITER|CREAT|TRUNC
, tbnum
);
1151 off
= QDBMHeader
.sizeof
+bnum
*int.sizeof
;
1153 while (off
< fsiz
) {
1155 fdseekread(fd
, off
, (&head
)[0..1]);
1156 } catch (Exception
) {
1159 if (head
.flags
&DP_RECFDEL
) {
1160 rsiz
= head
.recsize
;
1161 if (rsiz
< 0) break;
1167 if (ksiz
>= 0 && vsiz
>= 0) {
1168 import core
.stdc
.stdlib
: malloc
;
1169 kbuf
= cast(char*)malloc(ksiz
+1);
1170 vbuf
= cast(char*)malloc(vsiz
+1);
1171 if (kbuf
!is null && vbuf
!is null) {
1173 fdseekread(fd
, off
+RecordHeader
.sizeof
, kbuf
[0..ksiz
]);
1174 fdseekread(fd
, off
+RecordHeader
.sizeof
+ksiz
, vbuf
[0..vsiz
]);
1175 tdepot
.put(kbuf
[0..ksiz
], vbuf
[0..vsiz
], WMode
.KEEP
);
1176 } catch (Exception
) {
1180 //if (!err) raise(Error.ALLOC);
1183 if (vbuf
!is null) freeptr(vbuf
);
1184 if (kbuf
!is null) freeptr(kbuf
);
1186 //if (!err) raise(Error.BROKEN);
1189 rsiz
= head
.recsize
;
1190 if (rsiz
< 0) break;
1193 tdepot
.flags
= flags
; // err = true;
1196 } catch (Exception
) {
1199 if (ftruncate(fd
, 0) == -1) {
1200 //if (!err) raise(Error.TRUNC);
1203 auto tempname
= tdepot
.m_name
; // with trailing zero
1205 fcopy(fd
, 0, tdepot
.m_fd
, 0);
1207 } catch (Exception
) {
1210 if (close(fd
) == -1) {
1211 //if (!err) raise(Error.CLOSE);
1215 if (unlink(tempname
.ptr
) == -1) {
1216 //if (!err) raise(Error.UNLINK);
1222 /** Hash function used inside Depot.
1224 * This function is useful when an application calculates the state of the inside bucket array.
1227 * kbuf = the pointer to the region of a key
1230 * The return value is the hash value of 31 bits length computed from the key.
1232 static int innerhash (const(void)[] kbuf
) @trusted nothrow @nogc {
1234 if (kbuf
.length
== int.sizeof
) {
1235 import core
.stdc
.string
: memcpy
;
1236 memcpy(&res
, kbuf
.ptr
, res
.sizeof
);
1240 foreach (immutable bt; cast(const(ubyte)[])kbuf
) res
= res
*31+bt;
1241 return (res
*87767623)&int.max
;
1244 /** Hash function which is independent from the hash functions used inside Depot.
1246 * This function is useful when an application uses its own hash algorithm outside Depot.
1249 * kbuf = the pointer to the region of a key
1252 * The return value is the hash value of 31 bits length computed from the key.
1254 static int outerhash (const(void)[] kbuf
) @trusted nothrow @nogc {
1255 int res
= 774831917;
1256 foreach_reverse (immutable bt; cast(const(ubyte)[])kbuf
) res
= res
*29+bt;
1257 return (res
*5157883)&int.max
;
1260 /** Get a natural prime number not less than a number.
1262 * This function is useful when an application determines the size of a bucket array of its
1263 * own hash algorithm.
1266 * num = a natural number
1269 * The return value is a natural prime number not less than the specified number
1271 static int primenum (int num
) @safe pure nothrow @nogc {
1272 static immutable int[217] primes
= [
1273 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 71, 79, 83,
1274 89, 103, 109, 113, 127, 139, 157, 173, 191, 199, 223, 239, 251, 283, 317, 349,
1275 383, 409, 443, 479, 509, 571, 631, 701, 761, 829, 887, 953, 1021, 1151, 1279,
1276 1399, 1531, 1663, 1789, 1913, 2039, 2297, 2557, 2803, 3067, 3323, 3583, 3833,
1277 4093, 4603, 5119, 5623, 6143, 6653, 7159, 7673, 8191, 9209, 10223, 11261,
1278 12281, 13309, 14327, 15359, 16381, 18427, 20479, 22511, 24571, 26597, 28669,
1279 30713, 32749, 36857, 40949, 45053, 49139, 53239, 57331, 61417, 65521, 73727,
1280 81919, 90107, 98299, 106487, 114679, 122869, 131071, 147451, 163819, 180221,
1281 196597, 212987, 229373, 245759, 262139, 294911, 327673, 360439, 393209, 425977,
1282 458747, 491503, 524287, 589811, 655357, 720887, 786431, 851957, 917503, 982981,
1283 1048573, 1179641, 1310719, 1441771, 1572853, 1703903, 1835003, 1966079,
1284 2097143, 2359267, 2621431, 2883577, 3145721, 3407857, 3670013, 3932153,
1285 4194301, 4718579, 5242877, 5767129, 6291449, 6815741, 7340009, 7864301,
1286 8388593, 9437179, 10485751, 11534329, 12582893, 13631477, 14680063, 15728611,
1287 16777213, 18874367, 20971507, 23068667, 25165813, 27262931, 29360087, 31457269,
1288 33554393, 37748717, 41943023, 46137319, 50331599, 54525917, 58720253, 62914549,
1289 67108859, 75497467, 83886053, 92274671, 100663291, 109051903, 117440509,
1290 125829103, 134217689, 150994939, 167772107, 184549373, 201326557, 218103799,
1291 234881011, 251658227, 268435399, 301989881, 335544301, 369098707, 402653171,
1292 436207613, 469762043, 503316469, 536870909, 603979769, 671088637, 738197503,
1293 805306357, 872415211, 939524087, 1006632947, 1073741789, 1207959503,
1294 1342177237, 1476394991, 1610612711, 1744830457, 1879048183, 2013265907,
1297 foreach (immutable pr
; primes
) if (num
<= pr
) return pr
;
1301 /* ********************************************************************************************* *
1302 * features for experts
1303 * ********************************************************************************************* */
1305 /** Synchronize updating contents on memory.
1308 * DepotException on various errors
1311 import core
.sys
.posix
.sys
.mman
: msync
, MS_SYNC
;
1314 if (msync(m_map
, m_msiz
, MS_SYNC
) == -1) {
1320 /** Synchronize updating contents on memory, not physically.
1323 * DepotException on various errors
1328 // there is no mflush() call
1330 if (mflush(m_map
, m_msiz
, MS_SYNC
) == -1) {
1337 /** Get flags of a database.
1340 * The return value is the flags of a database.
1343 * DepotException on various errors
1345 @property int flags () {
1347 auto hdr
= cast(QDBMHeader
*)m_map
;
1351 /** Set flags of a database.
1354 * flags = flags to set. Least ten bits are reserved for internal use.
1357 * If successful, the return value is true, else, it is false.
1360 * DepotException on various errors
1362 @property void flags (int v
) {
1364 auto hdr
= cast(QDBMHeader
*)m_map
;
1369 /* ********************************************************************************************* *
1371 * ********************************************************************************************* */
1373 void raise (Error errcode
, string file
=__FILE__
, usize line
=__LINE__
) {
1374 assert(errcode
>= Error
.NOERR
);
1375 if (errcode
== Error
.FATAL
) m_fatal
= true;
1376 throw new DepotException(errcode
, file
, line
);
1379 static void straise (Error errcode
, string file
=__FILE__
, usize line
=__LINE__
) {
1380 assert(errcode
>= Error
.NOERR
);
1381 throw new DepotException(errcode
, file
, line
);
1384 // get the second hash value
1385 static int secondhash (const(void)[] kbuf
) @trusted nothrow @nogc {
1387 foreach_reverse (immutable bt; cast(const(ubyte)[])kbuf
) res
= res
*37+bt;
1388 return (res
*43321879)&int.max
;
1391 void updateHeader () @trusted nothrow @nogc {
1392 auto hdr
= cast(QDBMHeader
*)m_map
;
1393 hdr
.filesize
= cast(int)m_fsiz
;
1394 hdr
.nrecords
= m_rnum
;
1397 /* Lock a file descriptor.
1400 * fd = a file descriptor
1401 * ex = whether an exclusive lock or a shared lock is performed
1402 * nb = whether to request with non-blocking
1403 * errcode = the error code (can be `null`)
1406 * DepotException on various errors
1408 static void fdlock (int fd
, int ex
, int nb
) {
1409 import core
.stdc
.stdio
: SEEK_SET
;
1410 import core
.stdc
.string
: memset
;
1411 import core
.sys
.posix
.fcntl
: flock
, fcntl
, F_RDLCK
, F_SETLK
, F_SETLKW
, F_WRLCK
;
1414 memset(&lock, 0, lock.sizeof
);
1415 lock.l_type
= (ex ? F_WRLCK
: F_RDLCK
);
1416 lock.l_whence
= SEEK_SET
;
1420 while (fcntl(fd
, nb ? F_SETLK
: F_SETLKW
, &lock) == -1) {
1421 import core
.stdc
.errno
: errno
, EINTR
;
1422 if (errno
!= EINTR
) straise(Error
.LOCK
);
1426 /* Write into a file.
1429 * fd = a file descriptor
1430 * buf = a buffer to write
1433 * The return value is the size of the written buffer, or -1 on failure
1438 static int fdwrite (int fd
, const(void)[] buf
) @trusted nothrow @nogc {
1439 auto lbuf
= cast(const(ubyte)[])buf
;
1442 while (lbuf
.length
> 0) {
1443 import core
.sys
.posix
.unistd
: write
;
1444 auto wb
= write(fd
, lbuf
.ptr
, lbuf
.length
);
1446 import core
.stdc
.errno
: errno
, EINTR
;
1447 if (errno
!= EINTR
) return -1;
1457 /* Write into a file at an offset.
1460 * fd = a file descriptor
1461 * off = an offset of the file
1462 * buf = a buffer to write
1465 * DepotException on various errors
1467 static void fdseekwrite (int fd
, long off
, const(void)[] buf
) {
1468 import core
.stdc
.stdio
: SEEK_END
, SEEK_SET
;
1469 import core
.sys
.posix
.unistd
: lseek
;
1471 if (buf
.length
< 1) return;
1472 if (lseek(fd
, (off
< 0 ?
0 : off
), (off
< 0 ? SEEK_END
: SEEK_SET
)) == -1) straise(Error
.SEEK
);
1473 if (fdwrite(fd
, buf
) != buf
.length
) straise(Error
.WRITE
);
1476 /* Write an integer into a file at an offset.
1479 * fd = a file descriptor
1480 * off = an offset of the file
1484 * DepotException on various errors
1486 void fdseekwritenum (int fd
, long off
, int num
) {
1488 scope(failure
) m_fatal
= true;
1489 fdseekwrite(fd
, off
, (&num
)[0..1]);
1492 /* Read from a file and store the data into a buffer.
1495 * fd = a file descriptor
1496 * buf = a buffer to store into.
1499 * The return value is the size read with, or -1 on failure
1504 static int fdread (int fd
, void[] buf
) @trusted nothrow @nogc {
1505 import core
.sys
.posix
.unistd
: read
;
1506 auto lbuf
= cast(ubyte[])buf
;
1509 while (lbuf
.length
> 0) {
1510 auto bs
= read(fd
, lbuf
.ptr
, lbuf
.length
);
1512 import core
.stdc
.errno
: errno
, EINTR
;
1513 if (errno
!= EINTR
) return -1;
1518 total
+= cast(int)bs
;
1523 /* Read from a file at an offset and store the data into a buffer.
1526 * fd = a file descriptor
1527 * off = an offset of the file
1528 * buf = a buffer to store into
1531 * DepotException on various errors
1533 static void fdseekread (int fd
, long off
, void[] buf
) {
1534 import core
.stdc
.stdio
: SEEK_SET
;
1535 import core
.sys
.posix
.unistd
: lseek
;
1536 assert(fd
>= 0 && off
>= 0);
1537 if (lseek(fd
, off
, SEEK_SET
) != off
) straise(Error
.SEEK
);
1538 if (fdread(fd
, buf
) != buf
.length
) straise(Error
.READ
);
1541 /* Copy data between files.
1544 * destfd = a file descriptor of a destination file
1545 * destoff = an offset of the destination file
1546 * srcfd = a file descriptor of a source file
1547 * srcoff = an offset of the source file
1550 * The return value is the size copied with
1553 * DepotException on various errors
1555 static int fcopy (int destfd
, long destoff
, int srcfd
, long srcoff
) {
1556 import core
.stdc
.stdio
: SEEK_SET
;
1557 import core
.sys
.posix
.unistd
: lseek
;
1558 char[DP_IOBUFSIZ
] iobuf
;
1560 if (lseek(srcfd
, srcoff
, SEEK_SET
) == -1 ||
lseek(destfd
, destoff
, SEEK_SET
) == -1) straise(Error
.SEEK
);
1562 while ((iosiz
= fdread(srcfd
, iobuf
[])) > 0) {
1563 if (fdwrite(destfd
, iobuf
[0..iosiz
]) != iosiz
) straise(Error
.WRITE
);
1566 if (iosiz
< 0) straise(Error
.READ
);
1570 /* Get the padding size of a record.
1573 * ksiz = the size of the key of a record
1574 * vsiz = the size of the value of a record
1577 * The return value is the padding size of a record
1579 usize
padsize (usize ksiz
, usize vsiz
) const @safe pure nothrow @nogc {
1580 if (m_alignment
> 0) {
1581 return cast(usize
)(m_alignment
-(m_fsiz
+RecordHeader
.sizeof
+ksiz
+vsiz
)%m_alignment
);
1582 } else if (m_alignment
< 0) {
1583 usize pad
= cast(usize
)(vsiz
*(2.0/(1<<(-m_alignment
))));
1584 if (vsiz
+pad
>= DP_FSBLKSIZ
) {
1585 if (vsiz
<= DP_FSBLKSIZ
) pad
= 0;
1586 if (m_fsiz
%DP_FSBLKSIZ
== 0) {
1587 return cast(usize
)((pad
/DP_FSBLKSIZ
)*DP_FSBLKSIZ
+DP_FSBLKSIZ
-(m_fsiz
+RecordHeader
.sizeof
+ksiz
+vsiz
)%DP_FSBLKSIZ
);
1589 return cast(usize
)((pad
/(DP_FSBLKSIZ
/2))*(DP_FSBLKSIZ
/2)+(DP_FSBLKSIZ
/2)-
1590 (m_fsiz
+RecordHeader
.sizeof
+ksiz
+vsiz
)%(DP_FSBLKSIZ
/2));
1593 return (pad
>= RecordHeader
.sizeof ? pad
: RecordHeader
.sizeof
);
1599 /* Read the header of a record.
1602 * off = an offset of the database file
1603 * head = specifies a buffer for the header
1604 * ebuf = specifies the pointer to the entity buffer
1605 * eep = the pointer to a variable to which whether ebuf was used is assigned
1608 * DepotException on various errors
1610 void rechead (long off
, ref RecordHeader head
, void[] ebuf
, bool* eep
) {
1612 if (eep
!is null) *eep
= false;
1613 if (off
< 0 || off
> m_fsiz
) raise(Error
.BROKEN
);
1614 scope(failure
) m_fatal
= true; // any failure is fatal here
1615 if (ebuf
.length
>= DP_ENTBUFSIZ
&& off
< m_fsiz
-DP_ENTBUFSIZ
) {
1616 import core
.stdc
.string
: memcpy
;
1617 if (eep
!is null) *eep
= true;
1618 fdseekread(m_fd
, off
, ebuf
[0..DP_ENTBUFSIZ
]);
1619 memcpy(&head
, ebuf
.ptr
, RecordHeader
.sizeof
);
1621 fdseekread(m_fd
, off
, (&head
)[0..1]);
1623 if (head
.ksiz
< 0 || head
.vsiz
< 0 || head
.psiz
< 0 || head
.left
< 0 || head
.right
< 0) raise(Error
.BROKEN
);
1626 /* Read the entitiy of the key of a record.
1629 * off = an offset of the database file
1630 * head = the header of a record
1633 * The return value is a key data whose region is allocated by `malloc`
1636 * DepotException on various errors
1638 char* reckey (long off
, ref in RecordHeader head
) {
1639 //TODO: return slice instead of pointer?
1640 import core
.stdc
.stdlib
: malloc
;
1643 int ksiz
= head
.ksiz
;
1644 kbuf
= cast(char*)malloc(ksiz
+1);
1645 if (kbuf
is null) raise(Error
.ALLOC
);
1646 scope(failure
) freeptr(kbuf
);
1647 fdseekread(m_fd
, off
+RecordHeader
.sizeof
, kbuf
[0..ksiz
]);
1652 /* Read the entitiy of the value of a record.
1655 * off = an offset of the database file
1656 * head = the header of a record
1657 * start = the offset address of the beginning of the region of the value to be read
1658 * max = the max size to be read; if it is `uint.max`, the size to read is unlimited
1661 * The return value is a value data whose region is allocated by `malloc`
1664 * DepotException on various errors
1666 char* recval (long off
, ref RecordHeader head
, uint start
=0, uint max
=uint.max
) {
1667 //TODO: return slice instead of pointer?
1668 import core
.stdc
.stdlib
: malloc
;
1673 if (max
== uint.max
) {
1676 vsiz
= (max
< head
.vsiz ? max
: head
.vsiz
);
1678 vbuf
= cast(char*)malloc(vsiz
+1);
1679 if (vbuf
is null) { m_fatal
= true; raise(Error
.ALLOC
); }
1680 scope(failure
) { m_fatal
= true; freeptr(vbuf
); }
1681 fdseekread(m_fd
, off
+RecordHeader
.sizeof
+head
.ksiz
+start
, vbuf
[0..vsiz
]);
1686 /* Read the entitiy of the value of a record and write it into a given buffer.
1689 * off = an offset of the database file
1690 * head = the header of a record
1691 * start = the offset address of the beginning of the region of the value to be read
1692 * vbuf = the pointer to a buffer into which the value of the corresponding record is written
1695 * The return value is the size of the written data
1698 * DepotException on various errors
1700 usize
recvalwb (void[] vbuf
, long off
, ref RecordHeader head
, uint start
=0) {
1703 usize vsiz
= (vbuf
.length
< head
.vsiz ? vbuf
.length
: head
.vsiz
);
1704 fdseekread(m_fd
, off
+RecordHeader
.sizeof
+head
.ksiz
+start
, vbuf
[0..vsiz
]);
1708 /* Compare two keys.
1711 * abuf = the pointer to the region of the former
1712 * asiz = the size of the region
1713 * bbuf = the pointer to the region of the latter
1714 * bsiz = the size of the region
1717 * The return value is 0 if two equals, positive if the formar is big, else, negative.
1719 static int keycmp (const(void)[] abuf
, const(void)[] bbuf
) @trusted nothrow @nogc {
1720 import core
.stdc
.string
: memcmp
;
1721 //assert(abuf && asiz >= 0 && bbuf && bsiz >= 0);
1722 if (abuf
.length
> bbuf
.length
) return 1;
1723 if (abuf
.length
< bbuf
.length
) return -1;
1724 return memcmp(abuf
.ptr
, bbuf
.ptr
, abuf
.length
);
1727 /* Search for a record.
1730 * kbuf = the pointer to the region of a key
1731 * hash = the second hash value of the key
1732 * bip = the pointer to the region to assign the index of the corresponding record
1733 * offp = the pointer to the region to assign the last visited node in the hash chain,
1734 * or, -1 if the hash chain is empty
1735 * entp = the offset of the last used joint, or, -1 if the hash chain is empty
1736 * head = the pointer to the region to store the header of the last visited record in
1737 * ebuf = the pointer to the entity buffer
1738 * eep = the pointer to a variable to which whether ebuf was used is assigned
1739 * delhit = whether a deleted record corresponds or not
1742 * The return value is true if record was found, false if there is no corresponding record.
1745 * DepotException on various errors
1747 bool recsearch (const(void)[] kbuf
, int hash
, int* bip
, int* offp
, int* entp
,
1748 ref RecordHeader head
, void[] ebuf
, bool* eep
, Flag
!"delhit" delhit
=No
.delhit
)
1753 char[DP_STKBUFSIZ
] stkey
;
1755 assert(ebuf
.length
>= DP_ENTBUFSIZ
);
1756 assert(hash
>= 0 && bip
!is null && offp
!is null && entp
!is null && eep
!is null);
1757 thash
= innerhash(kbuf
);
1758 *bip
= thash
%m_bnum
;
1759 off
= m_buckets
[*bip
];
1765 rechead(off
, head
, ebuf
, eep
);
1768 entoff
= cast(int)(off
+RecordHeader
.left
.offsetof
);
1770 } else if (hash
< thash
) {
1771 entoff
= cast(int)(off
+RecordHeader
.right
.offsetof
);
1774 if (*eep
&& RecordHeader
.sizeof
+head
.ksiz
<= DP_ENTBUFSIZ
) {
1775 immutable ebstart
= RecordHeader
.sizeof
;
1776 kcmp
= keycmp(kbuf
, ebuf
[ebstart
..ebstart
+head
.ksiz
]);
1777 } else if (head
.ksiz
> DP_STKBUFSIZ
) {
1778 if ((tkey
= reckey(off
, head
)) is null) raise(Error
.FATAL
);
1779 kcmp
= keycmp(kbuf
, tkey
[0..head
.ksiz
]);
1783 fdseekread(m_fd
, off
+RecordHeader
.sizeof
, stkey
[0..head
.ksiz
]);
1784 } catch (Exception
) {
1787 kcmp
= keycmp(kbuf
, stkey
[0..head
.ksiz
]);
1790 entoff
= cast(int)(off
+RecordHeader
.left
.offsetof
);
1792 } else if (kcmp
< 0) {
1793 entoff
= cast(int)(off
+RecordHeader
.right
.offsetof
);
1796 if (!delhit
&& (head
.flags
&DP_RECFDEL
)) {
1797 entoff
= cast(int)(off
+RecordHeader
.left
.offsetof
);
1800 *offp
= cast(int)off
;
1807 *offp
= cast(int)off
;
1812 /* Overwrite a record.
1815 * off = the offset of the database file
1816 * rsiz = the size of the existing record
1817 * kbuf = the pointer to the region of a key
1818 * vbuf = the pointer to the region of a value
1819 * hash = the second hash value of the key
1820 * left = the offset of the left child
1821 * right = the offset of the right child
1824 * DepotException on various errors
1826 void recrewrite (long off
, int rsiz
, const(void)[] kbuf
, const(void)[] vbuf
, int hash
, int left
, int right
) {
1827 char[DP_WRTBUFSIZ
] ebuf
;
1829 int hoff
, koff
, voff
, mi
, min
, size
;
1831 assert(off
>= 1 && rsiz
> 0);
1834 head
.ksiz
= cast(int)kbuf
.length
;
1835 head
.vsiz
= cast(int)vbuf
.length
;
1836 head
.psiz
= cast(int)(rsiz
-head
.sizeof
-kbuf
.length
-vbuf
.length
);
1839 asiz
= head
.sizeof
+kbuf
.length
+vbuf
.length
;
1840 if (m_fbpsiz
> DP_FBPOOLSIZ
*4 && head
.psiz
> asiz
) {
1841 rsiz
= cast(int)((head
.psiz
-asiz
)/2+asiz
);
1846 if (asiz
<= DP_WRTBUFSIZ
) {
1847 import core
.stdc
.string
: memcpy
;
1848 memcpy(ebuf
.ptr
, &head
, head
.sizeof
);
1849 memcpy(ebuf
.ptr
+head
.sizeof
, kbuf
.ptr
, kbuf
.length
);
1850 memcpy(ebuf
.ptr
+head
.sizeof
+kbuf
.length
, vbuf
.ptr
, vbuf
.length
);
1851 fdseekwrite(m_fd
, off
, ebuf
[0..asiz
]);
1853 hoff
= cast(int)off
;
1854 koff
= cast(int)(hoff
+head
.sizeof
);
1855 voff
= cast(int)(koff
+kbuf
.length
);
1856 fdseekwrite(m_fd
, hoff
, (&head
)[0..1]);
1857 fdseekwrite(m_fd
, koff
, kbuf
[]);
1858 fdseekwrite(m_fd
, voff
, vbuf
[]);
1861 off
+= head
.sizeof
+kbuf
.length
+vbuf
.length
+head
.psiz
;
1862 head
.flags
= DP_RECFDEL|DP_RECFREUSE
;
1864 head
.ksiz
= cast(int)kbuf
.length
;
1865 head
.vsiz
= cast(int)vbuf
.length
;
1866 head
.psiz
= cast(int)(rsiz
-head
.sizeof
-kbuf
.length
-vbuf
.length
);
1869 fdseekwrite(m_fd
, off
, (&head
)[0..1]);
1870 size
= head
.recsize
;
1873 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
1874 if (m_fbpool
[i
] == -1) {
1875 m_fbpool
[i
] = cast(int)off
;
1876 m_fbpool
[i
+1] = size
;
1881 if (mi
== -1 || m_fbpool
[i
+1] < min
) {
1883 min
= m_fbpool
[i
+1];
1886 if (mi
>= 0 && size
> min
) {
1887 m_fbpool
[mi
] = cast(int)off
;
1888 m_fbpool
[mi
+1] = size
;
1894 /* Write a record at the end of a database file.
1897 * kbuf = the pointer to the region of a key
1898 * vbuf = the pointer to the region of a value
1899 * hash = the second hash value of the key
1900 * left = the offset of the left child
1901 * right = the offset of the right child
1904 * The return value is the offset of the record
1907 * DepotException on various errors
1909 int recappend (const(void)[] kbuf
, const(void)[] vbuf
, int hash
, int left
, int right
) {
1910 char[DP_WRTBUFSIZ
] ebuf
;
1914 psiz
= padsize(kbuf
.length
, vbuf
.length
);
1917 head
.ksiz
= cast(int)kbuf
.length
;
1918 head
.vsiz
= cast(int)vbuf
.length
;
1919 head
.psiz
= cast(int)psiz
;
1922 asiz
= head
.sizeof
+kbuf
.length
+vbuf
.length
+psiz
;
1924 if (asiz
<= DP_WRTBUFSIZ
) {
1925 import core
.stdc
.string
: memcpy
, memset
;
1926 memcpy(ebuf
.ptr
, &head
, head
.sizeof
);
1927 memcpy(ebuf
.ptr
+head
.sizeof
, kbuf
.ptr
, kbuf
.length
);
1928 memcpy(ebuf
.ptr
+head
.sizeof
+kbuf
.length
, vbuf
.ptr
, vbuf
.length
);
1929 memset(ebuf
.ptr
+head
.sizeof
+kbuf
.length
+vbuf
.length
, 0, psiz
);
1930 fdseekwrite(m_fd
, off
, ebuf
[0..asiz
]);
1932 import core
.stdc
.stdlib
: malloc
;
1933 import core
.stdc
.string
: memcpy
, memset
;
1934 auto hbuf
= cast(char*)malloc(asiz
);
1935 if (hbuf
is null) raise(Error
.ALLOC
);
1936 scope(exit
) freeptr(hbuf
);
1937 memcpy(hbuf
, &head
, head
.sizeof
);
1938 memcpy(hbuf
+head
.sizeof
, kbuf
.ptr
, kbuf
.length
);
1939 memcpy(hbuf
+head
.sizeof
+kbuf
.length
, vbuf
.ptr
, vbuf
.length
);
1940 memset(hbuf
+head
.sizeof
+kbuf
.length
+vbuf
.length
, 0, psiz
);
1941 fdseekwrite(m_fd
, off
, hbuf
[0..asiz
]);
1944 return cast(int)off
;
1947 /* Overwrite the value of a record.
1950 * off = the offset of the database file
1951 * head = the header of the record
1952 * vbuf = the pointer to the region of a value
1953 * cat = whether it is concatenate mode or not
1956 * DepotException on various errors
1958 void recover (long off
, ref RecordHeader head
, const(void)[] vbuf
, Flag
!"catmode" catmode
) {
1960 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
1961 if (m_fbpool
[i
] == off
) {
1962 m_fbpool
[i
] = m_fbpool
[i
+1] = -1;
1967 long voff
= off
+RecordHeader
.sizeof
+head
.ksiz
;
1969 head
.psiz
-= vbuf
.length
;
1970 head
.vsiz
+= vbuf
.length
;
1971 voff
+= head
.vsiz
-vbuf
.length
;
1973 head
.psiz
+= head
.vsiz
-vbuf
.length
;
1974 head
.vsiz
= cast(int)vbuf
.length
;
1976 scope(failure
) m_fatal
= true; // any failure is fatal here
1977 fdseekwrite(m_fd
, off
, (&head
)[0..1]);
1978 fdseekwrite(m_fd
, voff
, vbuf
[]);
1984 * off = the offset of the database file
1985 * head = the header of the record
1986 * reusable = whether the region is reusable or not
1989 * DepotException on various errors
1991 void recdelete (long off
, ref in RecordHeader head
, Flag
!"reusable" reusable
) {
1994 auto size
= head
.recsize
;
1997 for (uint i
= 0; i
< m_fbpsiz
; i
+= 2) {
1998 if (m_fbpool
[i
] == -1) {
1999 m_fbpool
[i
] = cast(int)off
;
2000 m_fbpool
[i
+1] = size
;
2005 if (mi
== -1 || m_fbpool
[i
+1] < min
) {
2007 min
= m_fbpool
[i
+1];
2010 if (mi
>= 0 && size
> min
) {
2011 m_fbpool
[mi
] = cast(int)off
;
2012 m_fbpool
[mi
+1] = size
;
2016 fdseekwritenum(m_fd
, off
+RecordHeader
.flags
.offsetof
, DP_RECFDEL|
(reusable ? DP_RECFREUSE
: 0));
2019 /* Make contiguous records of the free block pool coalesce. */
2020 void fbpoolcoal () @trusted {
2021 import core
.stdc
.stdlib
: qsort
;
2022 if (m_fbpinc
++ <= m_fbpsiz
/4) return;
2024 qsort(m_fbpool
, m_fbpsiz
/2, int.sizeof
*2, &fbpoolcmp
);
2025 for (uint i
= 2; i
< m_fbpsiz
; i
+= 2) {
2026 if (m_fbpool
[i
-2] > 0 && m_fbpool
[i
-2]+m_fbpool
[i
-1]-m_fbpool
[i
] == 0) {
2027 m_fbpool
[i
] = m_fbpool
[i
-2];
2028 m_fbpool
[i
+1] += m_fbpool
[i
-1];
2029 m_fbpool
[i
-2] = m_fbpool
[i
-1] = -1;
2034 /* Compare two records of the free block pool.
2035 a = the pointer to one record.
2036 b = the pointer to the other record.
2037 The return value is 0 if two equals, positive if the formar is big, else, negative. */
2038 static extern(C
) int fbpoolcmp (in void* a
, in void* b
) @trusted nothrow @nogc {
2040 return *cast(const int*)a
- *cast(const int*)b
;