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
|
package bolt
import (
"sort"
"unsafe"
)
// freelist represents a list of all pages that are available for allocation.
// It also tracks pages that have been freed but are still in use by open transactions.
type freelist struct {
ids []pgid
pending map[txid][]pgid
}
// size returns the size of the page after serialization.
func (f *freelist) size() int {
return pageHeaderSize + (int(unsafe.Sizeof(pgid(0))) * len(f.all()))
}
// all returns a list of all free ids and all pending ids in one sorted list.
func (f *freelist) all() []pgid {
ids := make([]pgid, len(f.ids))
copy(ids, f.ids)
for _, list := range f.pending {
ids = append(ids, list...)
}
sort.Sort(reverseSortedPgids(ids))
return ids
}
// allocate returns the starting page id of a contiguous list of pages of a given size.
// If a contiguous block cannot be found then 0 is returned.
func (f *freelist) allocate(n int) pgid {
var count int
var previd pgid
for i, id := range f.ids {
// Reset count if this is not contiguous.
if previd == 0 || previd-id != 1 {
count = 1
}
// If we found a contiguous block then remove it and return it.
if count == n {
f.ids = append(f.ids[:i-(n-1)], f.ids[i+1:]...)
_assert(id > 1, "cannot allocate page 0 or 1: %d", id)
return id
}
previd = id
count++
}
return 0
}
// free releases a page and its overflow for a given transaction id.
func (f *freelist) free(txid txid, p *page) {
var ids = f.pending[txid]
_assert(p.id > 1, "cannot free page 0 or 1: %d", p.id)
for i := 0; i < int(p.overflow+1); i++ {
ids = append(ids, p.id+pgid(i))
}
f.pending[txid] = ids
}
// release moves all page ids for a transaction id (or older) to the freelist.
func (f *freelist) release(txid txid) {
for tid, ids := range f.pending {
if tid <= txid {
f.ids = append(f.ids, ids...)
delete(f.pending, tid)
}
}
sort.Sort(reverseSortedPgids(f.ids))
}
// isFree returns whether a given page is in the free list.
func (f *freelist) isFree(pgid pgid) bool {
for _, id := range f.ids {
if id == pgid {
return true
}
}
for _, m := range f.pending {
for _, id := range m {
if id == pgid {
return true
}
}
}
return false
}
// read initializes the freelist from a freelist page.
func (f *freelist) read(p *page) {
ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0:p.count]
f.ids = make([]pgid, len(ids))
copy(f.ids, ids)
}
// write writes the page ids onto a freelist page. All free and pending ids are
// saved to disk since in the event of a program crash, all pending ids will
// become free.
func (f *freelist) write(p *page) {
ids := f.all()
p.flags |= freelistPageFlag
p.count = uint16(len(ids))
copy(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:], ids)
}
type reverseSortedPgids []pgid
func (s reverseSortedPgids) Len() int { return len(s) }
func (s reverseSortedPgids) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func (s reverseSortedPgids) Less(i, j int) bool { return s[i] > s[j] }
|
