1 /** @file honey_table.h
2 * @brief HoneyTable class
4 /* Copyright (C) 2017,2018 Olly Betts
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 #ifndef XAPIAN_INCLUDED_HONEY_TABLE_H
22 #define XAPIAN_INCLUDED_HONEY_TABLE_H
24 //#define SSINDEX_ARRAY
25 //#define SSINDEX_BINARY_CHOP
26 #define SSINDEX_SKIPLIST
28 #define SSINDEX_BINARY_CHOP_KEY_SIZE 4
30 //#include "xapian/constants.h"
31 #include "xapian/error.h"
35 #include <iostream> // FIXME
38 #include <cstdio> // For EOF
39 #include <cstdlib> // std::abort()
40 #include <type_traits>
45 #include <sys/types.h>
46 #include "safesysstat.h"
47 #include "safeunistd.h"
49 #include "safeerrno.h"
51 #include "compression_stream.h"
52 #include "honey_defs.h"
53 #include "honey_version.h"
54 #include "internaltypes.h"
58 #include "stringutils.h"
59 #include "wordaccess.h"
61 #include "unicode/description_append.h"
65 #endif // FIXME: namespace it?
67 const uint4 BLK_UNUSED
= uint4(-1);
69 class HoneyFreeListChecker
;
71 const int FORCED_CLOSE
= -2;
75 mutable off_t pos
= 0;
76 bool read_only
= true;
77 mutable size_t buf_end
= 0;
78 mutable char buf
[4096];
83 BufferedFile(const BufferedFile
& o
) : fd(o
.fd
) {
84 if (!o
.read_only
) std::abort();
88 std::memcpy(buf
, o
.buf
, buf_end
);
93 BufferedFile(int fd_
, off_t pos_
, bool read_only_
)
94 : fd(fd_
), pos(pos_
), read_only(read_only_
) {}
97 // if (fd >= 0) ::close(fd);
112 void reset_fd(bool permanent
) {
113 fd
= permanent
? FORCED_CLOSE
: -1;
116 bool is_open() const { return fd
>= 0; }
118 bool was_forced_closed() const { return fd
== FORCED_CLOSE
; }
120 bool open(const std::string
& path
, bool read_only_
) {
121 // if (fd >= 0) ::close(fd);
122 read_only
= read_only_
;
124 // FIXME: add new io_open_stream_rd() etc?
125 fd
= io_open_block_rd(path
);
127 // FIXME: Always create anew for now...
128 fd
= io_open_block_wr(path
, true);
133 off_t
get_pos() const {
134 return read_only
? pos
- buf_end
: pos
+ buf_end
;
137 void set_pos(off_t pos_
) {
138 if (!read_only
) flush();
139 if (false && pos_
>= pos
) { // FIXME: need to take buf_end into account
142 // FIXME: salvage some of the buffer if we can?
148 void skip(size_t delta
) const {
149 if (!read_only
) std::abort();
150 // Keep any buffered data we can.
151 if (delta
> buf_end
) {
162 if (buf_end
) return false;
164 if (fd
== -1 || fstat(fd
, &sbuf
) < 0) return true;
165 return (sbuf
.st_size
== 0);
169 void write(unsigned char ch
) {
170 if (buf_end
== sizeof(buf
)) {
172 io_write(fd
, buf
, buf_end
);
179 void write(const char* p
, size_t len
) {
180 if (buf_end
+ len
<= sizeof(buf
)) {
181 memcpy(buf
+ buf_end
, p
, len
);
186 pos
+= buf_end
+ len
;
190 iov
[0].iov_base
= buf
;
191 iov
[0].iov_len
= buf_end
;
192 iov
[1].iov_base
= const_cast<char*>(p
);
193 iov
[1].iov_len
= len
;
194 ssize_t n_
= writev(fd
, iov
, 2);
195 if (n_
< 0) std::abort();
197 if (n
== buf_end
+ len
) {
207 io_write(fd
, p
, len
);
212 memmove(buf
, buf
+ n
, buf_end
);
215 io_write(fd
, buf
, buf_end
);
216 if (len
>= sizeof(buf
)) {
217 // If it's bigger than our buffer, just write it directly.
218 io_write(fd
, p
, len
);
230 // The buffer is currently empty, so we need to read at least one
232 size_t r
= io_pread(fd
, buf
, sizeof(buf
), pos
, 0);
233 if (r
< sizeof(buf
)) {
237 memmove(buf
+ sizeof(buf
) - r
, buf
, r
);
242 return static_cast<unsigned char>(buf
[sizeof(buf
) - buf_end
--]);
245 if (io_pread(fd
, &ch
, 1, pos
) != 1)
252 void read(char* p
, size_t len
) const {
255 if (len
<= buf_end
) {
256 memcpy(p
, buf
+ sizeof(buf
) - buf_end
, len
);
260 memcpy(p
, buf
+ sizeof(buf
) - buf_end
, buf_end
);
265 // FIXME: refill buffer if len < sizeof(buf)
267 size_t r
= io_pread(fd
, p
, len
, pos
, len
);
268 // io_pread() should throw an exception if it read < len bytes.
274 if (!read_only
&& buf_end
) {
275 io_write(fd
, buf
, buf_end
);
285 void rewind(off_t start
) {
296 #if defined SSINDEX_BINARY_CHOP
297 size_t block
= size_t(-1);
298 #elif defined SSINDEX_SKIPLIST
301 #if defined SSINDEX_BINARY_CHOP || defined SSINDEX_SKIPLIST
302 std::string last_index_key
;
304 // Put an index entry every this much:
305 // FIXME: tune - seems 64K is common elsewhere
306 enum { INDEXBLOCK
= 4096 };
307 SSIndex
* parent_index
= NULL
;
310 unsigned char first
, last
= static_cast<unsigned char>(-1);
311 off_t
* pointers
= NULL
;
317 // Header added in write() method.
318 #elif defined SSINDEX_BINARY_CHOP
319 data
.assign(5, '\x01');
320 #elif defined SSINDEX_SKIPLIST
321 data
.assign(1, '\x02');
323 # error "SSINDEX type not specified"
333 void maybe_add_entry(const std::string
& key
, off_t ptr
) {
335 unsigned char initial
= key
[0];
337 pointers
= new off_t
[256]();
340 // We should only be called for valid index points.
341 AssertRel(int(initial
), !=, last
);
343 while (++last
!= int(initial
)) {
344 pointers
[last
] = ptr
;
345 // FIXME: Perhaps record this differently so that an exact key
346 // search can return false?
348 pointers
[initial
] = ptr
;
350 #elif defined SSINDEX_BINARY_CHOP
351 // We store entries truncated to a maximum width (and trailing zeros
352 // are used to indicate keys shorter than that max width). These then
353 // point to the first key that maps to this truncated value.
355 // We need constant width entries to allow binary chop to work, but
356 // there are other ways to achieve this which could be explored. We
357 // could allow the full key width of 256 bytes, but that would take a
358 // lot more space. We could store a pointer (offset) to the key data,
359 // but that's more complex to read, and adds the pointer overhead. We
360 // could use a "SKO" - a fixed width entry which encodes variable
361 // length pointer and key with short keys in the entry and long keys
362 // pointed to (or prefix included and rest pointed to).
363 if (last_index_key
.size() == SSINDEX_BINARY_CHOP_KEY_SIZE
) {
364 if (startswith(key
, last_index_key
)) {
369 // Ensure the truncated key doesn't end in a zero byte.
370 if (key
.size() >= SSINDEX_BINARY_CHOP_KEY_SIZE
) {
371 // FIXME: Start from char N if we have N array index levels above.
372 last_index_key
.assign(key
, 0, SSINDEX_BINARY_CHOP_KEY_SIZE
);
373 if (key
[SSINDEX_BINARY_CHOP_KEY_SIZE
- 1] == '\0')
376 last_index_key
= key
;
377 if (key
.back() == '\0')
379 // Pad with zero bytes.
380 last_index_key
.resize(SSINDEX_BINARY_CHOP_KEY_SIZE
);
383 // Thin entries to at most one per INDEXBLOCK sized block.
384 size_t cur_block
= ptr
/ INDEXBLOCK
;
385 if (cur_block
== block
)
391 description_append(esc
, last_index_key
);
392 std::cout
<< "Adding «" << esc
<< "» -> file offset " << ptr
<< std::endl
;
395 data
+= last_index_key
;
396 size_t c
= data
.size();
398 unaligned_write4(reinterpret_cast<unsigned char*>(&data
[c
]), ptr
);
401 #elif defined SSINDEX_SKIPLIST
402 size_t cur_block
= ptr
/ INDEXBLOCK
;
403 if (cur_block
== block
) return;
405 size_t reuse
= common_prefix_length(last_index_key
, key
);
408 data
+= char(key
.size() - reuse
);
409 data
.append(key
, reuse
, key
.size() - reuse
);
410 pack_uint(data
, static_cast<std::make_unsigned
<off_t
>::type
>(ptr
));
413 // FIXME: deal with parent_index...
415 last_index_key
= key
;
417 # error "SSINDEX type not specified"
421 off_t
write(BufferedFile
& fh
) {
425 pointers
= new off_t
[1]();
428 data
.resize(3 + (last
- first
+ 1) * 4);
431 data
[2] = last
- first
;
432 for (unsigned ch
= first
; ch
<= last
; ++ch
) {
433 size_t o
= 3 + (ch
- first
) * 4;
434 // FIXME: Just make offsets 8 bytes? Or allow different widths?
435 off_t ptr
= pointers
[ch
];
436 if (ptr
> 0xffffffff)
437 throw Xapian::DatabaseError("Index offset needs >4 bytes");
438 Assert(o
+ 4 <= data
.size());
439 unaligned_write4(reinterpret_cast<unsigned char*>(&data
[o
]), ptr
);
443 #elif defined SSINDEX_BINARY_CHOP
444 // Fill in bytes 1 to 4 with the number of entries.
445 size_t n_index
= (data
.size() - 5) / (SSINDEX_BINARY_CHOP_KEY_SIZE
+ 4);
446 data
[1] = n_index
>> 24;
447 data
[2] = n_index
>> 16;
448 data
[3] = n_index
>> 8;
450 #elif defined SSINDEX_SKIPLIST
451 // Already built in data.
453 # error "SSINDEX type not specified"
456 off_t root
= fh
.get_pos();
457 fh
.write(data
.data(), data
.size());
458 // FIXME: parent stuff...
462 size_t size() const {
463 // FIXME: For SSINDEX_ARRAY, data.size() only correct after calling
465 size_t s
= data
.size();
466 if (parent_index
) s
+= parent_index
->size();
472 class MutableHoneyCursor
;
475 friend class HoneyCursor
; // Allow access to fh. FIXME cleaner way?
476 friend class MutableHoneyCursor
; // Allow access to fh. FIXME cleaner way?
482 mutable BufferedFile fh
;
483 mutable std::string last_key
;
486 honey_tablesize_t num_entries
= 0;
489 bool single_file() const { return path
.empty(); }
491 /** Offset to add to pointers in this table.
493 * This is zero when each table is a separate file, but likely non-zero
494 * when the tables are all embedded in one file.
498 bool get_exact_entry(const std::string
& key
, std::string
* tag
) const;
500 bool read_key(std::string
& key
, size_t& val_size
, bool& compressed
) const;
502 void read_val(std::string
& val
, size_t val_size
) const;
505 HoneyTable(const char*, const std::string
& path_
, bool read_only_
,
507 : path(path_
+ HONEY_TABLE_EXTENSION
),
508 read_only(read_only_
),
513 HoneyTable(const char*, int fd
, off_t offset_
, bool read_only_
,
515 : read_only(read_only_
),
516 fh(fd
, offset_
, read_only_
),
522 static size_t total_index_size
;
526 size_t index_size
= index
.size();
527 total_index_size
+= index_size
;
529 std::cout
<< "*** " << path
<< " - index " << index_size
<< " for "
530 << index
.get_num_entries() << " entries; total_size = "
531 << total_index_size
<< std::endl
;
539 bool is_writable() const { return !read_only
; }
541 int get_flags() const { return flags
; }
543 void set_full_compaction(bool) { }
545 void set_max_item_size(unsigned) { }
547 void create_and_open(int flags_
, const Honey::RootInfo
& root_info
);
549 void open(int flags_
, const Honey::RootInfo
& root_info
,
550 honey_revision_number_t
);
552 void close(bool permanent
) {
553 if (!single_file()) {
559 fh
.reset_fd(permanent
);
563 const std::string
& get_path() const { return path
; }
565 void add(const std::string
& key
,
568 bool compressed
= false);
570 void add(const std::string
& key
,
571 const std::string
& val
,
572 bool compressed
= false) {
573 add(key
, val
.data(), val
.size(), compressed
);
577 root
= index
.write(fh
);
581 void cancel(const Honey::RootInfo
&, honey_revision_number_t
) {
585 void commit(honey_revision_number_t
, Honey::RootInfo
* root_info
);
593 return num_entries
== 0;
596 bool get_exact_entry(const std::string
& key
, std::string
& tag
) const {
597 return get_exact_entry(key
, &tag
);
600 bool key_exists(const std::string
& key
) const {
601 return get_exact_entry(key
, NULL
);
604 bool del(const std::string
&) {
608 // readahead probably not useful? (FIXME)
609 bool readahead_key(const std::string
&) const { return false; }
611 bool is_modified() const { return !read_only
&& !empty(); }
613 HoneyCursor
* cursor_get() const;
615 bool exists() const {
617 return stat(path
.c_str(), &sbuf
) == 0;
620 bool is_open() const { return fh
.is_open(); }
622 void set_changes(HoneyChanges
*) { }
624 static void throw_database_closed() {
625 throw Xapian::DatabaseError("Closed!");
628 honey_tablesize_t
get_entry_count() const { return num_entries
; }
630 off_t
get_root() const { return root
; }
632 off_t
get_offset() const { return offset
; }
635 #endif // XAPIAN_INCLUDED_HONEY_TABLE_H