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