blob: 6a03a6c3c8558f99db562d1e0b62968ee73562ac [file] [log] [blame]
khenaidooab1f7bd2019-11-14 14:00:27 -05001package bbolt
2
3import "sort"
4
5// hashmapFreeCount returns count of free pages(hashmap version)
6func (f *freelist) hashmapFreeCount() int {
7 // use the forwardmap to get the total count
8 count := 0
9 for _, size := range f.forwardMap {
10 count += int(size)
11 }
12 return count
13}
14
15// hashmapAllocate serves the same purpose as arrayAllocate, but use hashmap as backend
16func (f *freelist) hashmapAllocate(txid txid, n int) pgid {
17 if n == 0 {
18 return 0
19 }
20
21 // if we have a exact size match just return short path
22 if bm, ok := f.freemaps[uint64(n)]; ok {
23 for pid := range bm {
24 // remove the span
25 f.delSpan(pid, uint64(n))
26
27 f.allocs[pid] = txid
28
29 for i := pgid(0); i < pgid(n); i++ {
30 delete(f.cache, pid+pgid(i))
31 }
32 return pid
33 }
34 }
35
36 // lookup the map to find larger span
37 for size, bm := range f.freemaps {
38 if size < uint64(n) {
39 continue
40 }
41
42 for pid := range bm {
43 // remove the initial
44 f.delSpan(pid, uint64(size))
45
46 f.allocs[pid] = txid
47
48 remain := size - uint64(n)
49
50 // add remain span
51 f.addSpan(pid+pgid(n), remain)
52
53 for i := pgid(0); i < pgid(n); i++ {
54 delete(f.cache, pid+pgid(i))
55 }
56 return pid
57 }
58 }
59
60 return 0
61}
62
63// hashmapReadIDs reads pgids as input an initial the freelist(hashmap version)
64func (f *freelist) hashmapReadIDs(pgids []pgid) {
65 f.init(pgids)
66
67 // Rebuild the page cache.
68 f.reindex()
69}
70
71// hashmapGetFreePageIDs returns the sorted free page ids
72func (f *freelist) hashmapGetFreePageIDs() []pgid {
73 count := f.free_count()
74 if count == 0 {
75 return nil
76 }
77
78 m := make([]pgid, 0, count)
79 for start, size := range f.forwardMap {
80 for i := 0; i < int(size); i++ {
81 m = append(m, start+pgid(i))
82 }
83 }
84 sort.Sort(pgids(m))
85
86 return m
87}
88
89// hashmapMergeSpans try to merge list of pages(represented by pgids) with existing spans
90func (f *freelist) hashmapMergeSpans(ids pgids) {
91 for _, id := range ids {
92 // try to see if we can merge and update
93 f.mergeWithExistingSpan(id)
94 }
95}
96
97// mergeWithExistingSpan merges pid to the existing free spans, try to merge it backward and forward
98func (f *freelist) mergeWithExistingSpan(pid pgid) {
99 prev := pid - 1
100 next := pid + 1
101
102 preSize, mergeWithPrev := f.backwardMap[prev]
103 nextSize, mergeWithNext := f.forwardMap[next]
104 newStart := pid
105 newSize := uint64(1)
106
107 if mergeWithPrev {
108 //merge with previous span
109 start := prev + 1 - pgid(preSize)
110 f.delSpan(start, preSize)
111
112 newStart -= pgid(preSize)
113 newSize += preSize
114 }
115
116 if mergeWithNext {
117 // merge with next span
118 f.delSpan(next, nextSize)
119 newSize += nextSize
120 }
121
122 f.addSpan(newStart, newSize)
123}
124
125func (f *freelist) addSpan(start pgid, size uint64) {
126 f.backwardMap[start-1+pgid(size)] = size
127 f.forwardMap[start] = size
128 if _, ok := f.freemaps[size]; !ok {
129 f.freemaps[size] = make(map[pgid]struct{})
130 }
131
132 f.freemaps[size][start] = struct{}{}
133}
134
135func (f *freelist) delSpan(start pgid, size uint64) {
136 delete(f.forwardMap, start)
137 delete(f.backwardMap, start+pgid(size-1))
138 delete(f.freemaps[size], start)
139 if len(f.freemaps[size]) == 0 {
140 delete(f.freemaps, size)
141 }
142}
143
144// initial from pgids using when use hashmap version
145// pgids must be sorted
146func (f *freelist) init(pgids []pgid) {
147 if len(pgids) == 0 {
148 return
149 }
150
151 size := uint64(1)
152 start := pgids[0]
153
154 if !sort.SliceIsSorted([]pgid(pgids), func(i, j int) bool { return pgids[i] < pgids[j] }) {
155 panic("pgids not sorted")
156 }
157
158 f.freemaps = make(map[uint64]pidSet)
159 f.forwardMap = make(map[pgid]uint64)
160 f.backwardMap = make(map[pgid]uint64)
161
162 for i := 1; i < len(pgids); i++ {
163 // continuous page
164 if pgids[i] == pgids[i-1]+1 {
165 size++
166 } else {
167 f.addSpan(start, size)
168
169 size = 1
170 start = pgids[i]
171 }
172 }
173
174 // init the tail
175 if size != 0 && start != 0 {
176 f.addSpan(start, size)
177 }
178}