tablestg 0.4.31

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

//! This crate is not yet reliable or stable!
//!
//! [Table] stores [Value]s which have a specific [DataType].

/* 
   Idea for re-using indirect values.
   On Store delete, allow deleted indirect values to be collected rather than deleted.
   On next insert, use the garbage values if possible.
   If not possible they are deleted.
*/
/*
   Idea for splitting hash buckets incrementally.

   Suppose we have a hash table with 4 buckets, numbered as below:

   [2] [6] [3] [4]
    0   1   2   3

   and suppose that bucket [6] ( index 1 ) is "full" and we want to insert into it.
   We first double the number of buckets:

   [2] [2] [6] [6] [3] [3] [4] [4]
    0   1   2   3   4   5   6   7

   without creating any new pages. This is a relatively cheap operation (maybe it can be done in a clever way).
   Now we split the records in [6] (now index 2 and 3) into two, the new page id being [7], as below:

   [2] [2] [6] [7] [3] [3] [4] [4]
    0   1   2   3   4   5   6   7

   [6] and [7] should each be roughly half-full, and we can continue inserting.

   Now suppose later on [3] ( index 5 ) is full and we want to insert into it.
   We first check the "buddy"*, index 4. If it has the same page number ( as is the case here ),
   we do not need to double the number of buckets, instead split the records in [3] into two
   buckets ( new page number is [8] ), as below:

   [2] [2] [6] [7] [3] [8] [4] [4]

   [3] and [8] should each be roughly half-full, and we can continue inserting.

   * The buddy position is x+1 if x is even, x-1 if x is odd.
*/

/// [Table] stores [Value]s which have a specific [DataType].
pub mod table;
pub use table::{LazyRow, Table, RTable};

/// Generic [Value]s.
pub mod value;
pub use value::Value;

/// [DataType] - describes, encodes and decodes [Value]s.
pub mod datatype;
pub use datatype::DataType;
use datatype::{LazyItem, MSPX, SPX};

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

/// [Store] - maps keys to variable size values (no size restriction) using 64 bit hash.
pub mod store;
pub use store::Store;
use store::{SData, StoreIter};

/// [VBuckMap] - maps keys to small variable size values using 64 bit hash. For possibly large values see [Store].
pub mod vbuckmap;
pub use vbuckmap::IdVKey;
use vbuckmap::{VBuckMap, VBuckMapInfo, VBuckMapIter, VKey};

// Remaining modules are private.

/// List of pages implemented as tree for [VBuckMap].
mod pagetree;

/// Bucket for [VBuckMap].
mod vbucket;
use vbucket::{Pos, Reader, Writer};

/// Standard page size ( for pagetree ).
const PAGE_SIZE: u64 = 3952;

// Basic data types.

pub use atom_file::{Arc, Data};

pub use pstd::localalloc::{Local, Perm};

/// `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>;
/// `RcA<T, Lpcal>`
pub type LRc<T> = pstd::RcA<T, Local>;

/// `StringA<Perm>`
pub type GString = pstd::StringA<Perm>;
/// `VecA<T, Perm>`
pub type GVec<T> = pstd::VecA<T, Perm>;
/// `BoxA<T, Perm>`
pub type GBox<T> = pstd::BoxA<T, Perm>;
/// `RcA<T, Perm>`
pub type GRc<T> = pstd::RcA<T, Perm>;

mod test;