a simple url shortening service, in the same vein as bit.ly and tinyurl.com, written in Go and using BoltDB as a backend
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.

198 lines
4.8KB

  1. package bbolt
  2. import (
  3. "fmt"
  4. "os"
  5. "sort"
  6. "unsafe"
  7. )
  8. const pageHeaderSize = int(unsafe.Offsetof(((*page)(nil)).ptr))
  9. const minKeysPerPage = 2
  10. const branchPageElementSize = int(unsafe.Sizeof(branchPageElement{}))
  11. const leafPageElementSize = int(unsafe.Sizeof(leafPageElement{}))
  12. const (
  13. branchPageFlag = 0x01
  14. leafPageFlag = 0x02
  15. metaPageFlag = 0x04
  16. freelistPageFlag = 0x10
  17. )
  18. const (
  19. bucketLeafFlag = 0x01
  20. )
  21. type pgid uint64
  22. type page struct {
  23. id pgid
  24. flags uint16
  25. count uint16
  26. overflow uint32
  27. ptr uintptr
  28. }
  29. // typ returns a human readable page type string used for debugging.
  30. func (p *page) typ() string {
  31. if (p.flags & branchPageFlag) != 0 {
  32. return "branch"
  33. } else if (p.flags & leafPageFlag) != 0 {
  34. return "leaf"
  35. } else if (p.flags & metaPageFlag) != 0 {
  36. return "meta"
  37. } else if (p.flags & freelistPageFlag) != 0 {
  38. return "freelist"
  39. }
  40. return fmt.Sprintf("unknown<%02x>", p.flags)
  41. }
  42. // meta returns a pointer to the metadata section of the page.
  43. func (p *page) meta() *meta {
  44. return (*meta)(unsafe.Pointer(&p.ptr))
  45. }
  46. // leafPageElement retrieves the leaf node by index
  47. func (p *page) leafPageElement(index uint16) *leafPageElement {
  48. n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
  49. return n
  50. }
  51. // leafPageElements retrieves a list of leaf nodes.
  52. func (p *page) leafPageElements() []leafPageElement {
  53. if p.count == 0 {
  54. return nil
  55. }
  56. return ((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[:]
  57. }
  58. // branchPageElement retrieves the branch node by index
  59. func (p *page) branchPageElement(index uint16) *branchPageElement {
  60. return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
  61. }
  62. // branchPageElements retrieves a list of branch nodes.
  63. func (p *page) branchPageElements() []branchPageElement {
  64. if p.count == 0 {
  65. return nil
  66. }
  67. return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
  68. }
  69. // dump writes n bytes of the page to STDERR as hex output.
  70. func (p *page) hexdump(n int) {
  71. buf := (*[maxAllocSize]byte)(unsafe.Pointer(p))[:n]
  72. fmt.Fprintf(os.Stderr, "%x\n", buf)
  73. }
  74. type pages []*page
  75. func (s pages) Len() int { return len(s) }
  76. func (s pages) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
  77. func (s pages) Less(i, j int) bool { return s[i].id < s[j].id }
  78. // branchPageElement represents a node on a branch page.
  79. type branchPageElement struct {
  80. pos uint32
  81. ksize uint32
  82. pgid pgid
  83. }
  84. // key returns a byte slice of the node key.
  85. func (n *branchPageElement) key() []byte {
  86. buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
  87. return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
  88. }
  89. // leafPageElement represents a node on a leaf page.
  90. type leafPageElement struct {
  91. flags uint32
  92. pos uint32
  93. ksize uint32
  94. vsize uint32
  95. }
  96. // key returns a byte slice of the node key.
  97. func (n *leafPageElement) key() []byte {
  98. buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
  99. return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize]
  100. }
  101. // value returns a byte slice of the node value.
  102. func (n *leafPageElement) value() []byte {
  103. buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
  104. return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos+n.ksize]))[:n.vsize:n.vsize]
  105. }
  106. // PageInfo represents human readable information about a page.
  107. type PageInfo struct {
  108. ID int
  109. Type string
  110. Count int
  111. OverflowCount int
  112. }
  113. type pgids []pgid
  114. func (s pgids) Len() int { return len(s) }
  115. func (s pgids) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
  116. func (s pgids) Less(i, j int) bool { return s[i] < s[j] }
  117. // merge returns the sorted union of a and b.
  118. func (a pgids) merge(b pgids) pgids {
  119. // Return the opposite slice if one is nil.
  120. if len(a) == 0 {
  121. return b
  122. }
  123. if len(b) == 0 {
  124. return a
  125. }
  126. merged := make(pgids, len(a)+len(b))
  127. mergepgids(merged, a, b)
  128. return merged
  129. }
  130. // mergepgids copies the sorted union of a and b into dst.
  131. // If dst is too small, it panics.
  132. func mergepgids(dst, a, b pgids) {
  133. if len(dst) < len(a)+len(b) {
  134. panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
  135. }
  136. // Copy in the opposite slice if one is nil.
  137. if len(a) == 0 {
  138. copy(dst, b)
  139. return
  140. }
  141. if len(b) == 0 {
  142. copy(dst, a)
  143. return
  144. }
  145. // Merged will hold all elements from both lists.
  146. merged := dst[:0]
  147. // Assign lead to the slice with a lower starting value, follow to the higher value.
  148. lead, follow := a, b
  149. if b[0] < a[0] {
  150. lead, follow = b, a
  151. }
  152. // Continue while there are elements in the lead.
  153. for len(lead) > 0 {
  154. // Merge largest prefix of lead that is ahead of follow[0].
  155. n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
  156. merged = append(merged, lead[:n]...)
  157. if n >= len(lead) {
  158. break
  159. }
  160. // Swap lead and follow.
  161. lead, follow = follow, lead[n:]
  162. }
  163. // Append what's left in follow.
  164. _ = append(merged, follow...)
  165. }