1package 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+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, 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+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}
179