You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

178 lines
3.6 KiB

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