tablestg 0.4.12

Storage for database tables
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

//! Everything is very preliminary, this crate is not yet at all stable.

pub use atom_file::Data;
use std::hash::Hash;

/// [PageSet] - keeps track of changed pages that need saving.
pub mod pageset;
pub use pageset::*;

/// [BuckMap] - maps keys to const size values using 64 bit hash.
pub mod buckmap;
pub use buckmap::*;

/// [VBuckMap] - maps keys to small variable size values using 64 bit hash.
pub mod vbuckmap;
pub use vbuckmap::*;

/*
/// [Table] -- fixed size record storage. Divided into pages, each page stores up to 128 records.
pub mod table;
pub use table::*;
*/

/// [VarValAddr] -- storage of variable length values.
pub mod varval;
pub use varval::*;

/// ToDo
pub mod sys;
pub use sys::*;

/// [DataType] -- describes data type
pub mod datatype;
pub use datatype::*;

/// [Value] -- generic instance of a data type
pub mod value;
pub use value::*;

// Private modules.

/// [PageTree] - list of pages implemented as tree.
mod pagetree;
use pagetree::*;

/// [TreeVec] -- a variable length list of bytes.
pub mod treevec;
use treevec::*;

/// Bucket for [BuckMap].
mod bucket;

/// Bucket for [VBuckMap].
pub mod vbucket;

const PAGE_SIZE: u64 = 3952;
// pub const PAGE_SIZE: u64 =  3952;
// pub const PAGE_SIZE: u64 =  4612;

use pstd::localalloc::Local;
/// `StringA<Local>`
pub type LString = pstd::StringA<Local>;
/// `VecA<T, Local>`
pub type LVec<T> = pstd::VecA<T, Local>;
/// `BoxA<T, Local>`
pub type LBox<T> = pstd::BoxA<T, Local>;

pub use pstd::rc::Rc;
pub use std::sync::Arc; // pstd::Arc does not yet have make_mut

mod test;

#[cfg(test)]
fn tos(s: &[u8]) -> &str {
    str::from_utf8(s).unwrap()
}

/* Record format desgin

   First byte of stored row indicates storage format.

   For "small" format, each fixed size cols are stored first, then each variable size col has a byte offset.

   For example, suppose record is:
   id : 9 ( 4 bytes fixed )
   name : "George" ( 6 bytes variable )
   email : "george@gmail.com" ( 16 bytes variable )

   This is stored (in "small" format) as 6 fixed bytes (including format byte), then 22 variable bytes, total = 28 bytes.

   09 00 00 00 | 01 | 12 | "George" | "george@gmail.com"

   The col start offsets are 1, 5, 6.
   The start of the 2nd column is 6, the size of the fixed size data ( special case, not stored because it is 1st variable column ).
   The size of the 2nd column is deduced from the offset of the 3rd field ( 12 - 6 ) = 6.
   So the end offset of the 2nd column is 12.
   The size of the 3rd column is the record size minus the end offset of the 2nd column, ( 28 - 12 = 16 ).

   In "large" format, the offsets are 16-bit instead of 8-bit, the total record size can be more than 255 bytes.
   In "large" format, variable size columns have a format byte, so a column can be stored indirectly rather than inline.
   For the example above, the number of bytes is 9 fixed bytes + 24 variable bytes, total = 31 bytes.

   09 00 00 00 | 02 | 16 00 | 00 "George" | 00 "george@gmail.com"

   The col start offsets are 1, 5, 7. Large format would not be used in this case, this is illustrative.

   xlarge format is similar but with 32-bit offsets, and a format-byte of 03. This caters for records with an extreme number of columns.

   The data stored in the hash table, or a large or xlarge column, can also be one of three indirect formats:

   10 | xx xx xx xx xx xx | is "page-indirect format". xx x 6 is a page number.
   Page indirect format is used for records larger than 255 bytes, less than 4K bytes.

   11 | xx xx xx xx xx xx nn nn | is "packed-indirect format". xx x 6 is the start id, nn x 2 is the size.
   To decode we load records ( each size < 256 bytes ) from a special store until all bytes have been read.
   Packed-indirect format is used for medium size records ( larger than 255 bytes, less than 64K bytes ).

   12 | xx xx xx xx xx xx nn nn nn nn nn nn
   Is "tree-indirect" format. xx x 6 is the root page, nn x 6 is the record length.
   Tree-indirect format is used for large records ( larger than 64K bytes ), or where packed-indirect cannot be used - see System Map.

   Thus a "file" record with id, filename and long content could be stored using large format as

   id : 9 ( 4 bytes fixed )
   filename : "whatever" ( 8 bytes variable )
   content : ....

   09 00 00 00 | 02 | 09 00 | 00 "whatever" | 12 xx xx xx xx xx xx nn nn nn nn nn nn

   Stores
   ======

   A Store has a number of VBuckMaps. Each record in a store has an id. Each VBuckMap stores 256 * 256 = 64K records (based on id).

   Each database table has a store. It may also have indexes - there are two kinds of index:

   unique : maps some alternate key to the primary id, using a (non-V) BuckMap.

   dup : maps some key (say email address) to a "dup list". It is represented by a single VBuckMap. The records are dup-lists.
   A dup-list is a list (set) of 64-bit record ids.
   Each dup-list can be stored either in any format.
   It can also be stored as a BuckMap, where the entries are simply 64-bit integers.

   System Map
   ==========
   The system map has records representing tables and other system objects.
   Records are stored in small, page-indirect or tree-indirect format.
   A table has an id allocator, a list of VBuckMaps, row type information, index information.

   Record Decoder
   ===========
   A Record Decoder is used to decode a record from a &[u8].
   Individual elements of a record can be accessed without decoding the entire reocrd.

*/

pub struct RecordInfo {
    pub col_offset: usize,
    pub col_name: String,
    pub col_type: i32,
}

pub struct RecordFormat {
    pub col_info: Vec<RecordInfo>,
}