skiplist.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571
  1. package skiplist
  2. // adapted from https://github.com/MauriceGit/skiplist/blob/master/skiplist.go
  3. import (
  4. "bytes"
  5. "fmt"
  6. "math/bits"
  7. "math/rand"
  8. "time"
  9. )
  10. const (
  11. // maxLevel denotes the maximum height of the skiplist. This height will keep the skiplist
  12. // efficient for up to 34m entries. If there is a need for much more, please adjust this constant accordingly.
  13. maxLevel = 25
  14. )
  15. type SkipList struct {
  16. StartLevels [maxLevel]*SkipListElementReference
  17. EndLevels [maxLevel]*SkipListElementReference
  18. MaxNewLevel int
  19. MaxLevel int
  20. ListStore ListStore
  21. HasChanges bool
  22. // elementCount int
  23. }
  24. // NewSeed returns a new empty, initialized Skiplist.
  25. // Given a seed, a deterministic height/list behaviour can be achieved.
  26. // Eps is used to compare keys given by the ExtractKey() function on equality.
  27. func NewSeed(seed int64, listStore ListStore) *SkipList {
  28. // Initialize random number generator.
  29. rand.Seed(seed)
  30. //fmt.Printf("SkipList seed: %v\n", seed)
  31. list := &SkipList{
  32. MaxNewLevel: maxLevel,
  33. MaxLevel: 0,
  34. ListStore: listStore,
  35. // elementCount: 0,
  36. }
  37. return list
  38. }
  39. // New returns a new empty, initialized Skiplist.
  40. func New(listStore ListStore) *SkipList {
  41. return NewSeed(time.Now().UTC().UnixNano(), listStore)
  42. }
  43. // IsEmpty checks, if the skiplist is empty.
  44. func (t *SkipList) IsEmpty() bool {
  45. return t.StartLevels[0] == nil
  46. }
  47. func (t *SkipList) generateLevel(maxLevel int) int {
  48. level := maxLevel - 1
  49. // First we apply some mask which makes sure that we don't get a level
  50. // above our desired level. Then we find the first set bit.
  51. var x = rand.Uint64() & ((1 << uint(maxLevel-1)) - 1)
  52. zeroes := bits.TrailingZeros64(x)
  53. if zeroes <= maxLevel {
  54. level = zeroes
  55. }
  56. return level
  57. }
  58. func (t *SkipList) findEntryIndex(key []byte, minLevel int) int {
  59. // Find good entry point so we don't accidentally skip half the list.
  60. for i := t.MaxLevel; i >= 0; i-- {
  61. if t.StartLevels[i] != nil && bytes.Compare(t.StartLevels[i].Key, key) < 0 || i <= minLevel {
  62. return i
  63. }
  64. }
  65. return 0
  66. }
  67. func (t *SkipList) findExtended(key []byte, findGreaterOrEqual bool) (prevElementIfVisited *SkipListElement, foundElem *SkipListElement, ok bool, err error) {
  68. foundElem = nil
  69. ok = false
  70. if t.IsEmpty() {
  71. return
  72. }
  73. index := t.findEntryIndex(key, 0)
  74. var currentNode *SkipListElement
  75. currentNode, err = t.LoadElement(t.StartLevels[index])
  76. if err != nil {
  77. return
  78. }
  79. if currentNode == nil {
  80. return
  81. }
  82. // In case, that our first element is already greater-or-equal!
  83. if findGreaterOrEqual && compareElement(currentNode, key) > 0 {
  84. foundElem = currentNode
  85. ok = true
  86. return
  87. }
  88. for {
  89. if compareElement(currentNode, key) == 0 {
  90. foundElem = currentNode
  91. ok = true
  92. return
  93. }
  94. // Which direction are we continuing next time?
  95. if currentNode.Next[index] != nil && bytes.Compare(currentNode.Next[index].Key, key) <= 0 {
  96. // Go right
  97. currentNode, err = t.LoadElement(currentNode.Next[index])
  98. if err != nil {
  99. return
  100. }
  101. if currentNode == nil {
  102. return
  103. }
  104. } else {
  105. if index > 0 {
  106. // Early exit
  107. if currentNode.Next[0] != nil && bytes.Compare(currentNode.Next[0].Key, key) == 0 {
  108. prevElementIfVisited = currentNode
  109. var currentNodeNext *SkipListElement
  110. currentNodeNext, err = t.LoadElement(currentNode.Next[0])
  111. if err != nil {
  112. return
  113. }
  114. if currentNodeNext == nil {
  115. return
  116. }
  117. foundElem = currentNodeNext
  118. ok = true
  119. return
  120. }
  121. // Go down
  122. index--
  123. } else {
  124. // Element is not found and we reached the bottom.
  125. if findGreaterOrEqual {
  126. foundElem, err = t.LoadElement(currentNode.Next[index])
  127. if err != nil {
  128. return
  129. }
  130. ok = foundElem != nil
  131. }
  132. return
  133. }
  134. }
  135. }
  136. }
  137. // Find tries to find an element in the skiplist based on the key from the given ListElement.
  138. // elem can be used, if ok is true.
  139. // Find runs in approx. O(log(n))
  140. func (t *SkipList) Find(key []byte) (prevIfVisited *SkipListElement, elem *SkipListElement, ok bool, err error) {
  141. if t == nil || key == nil {
  142. return
  143. }
  144. prevIfVisited, elem, ok, err = t.findExtended(key, false)
  145. return
  146. }
  147. // FindGreaterOrEqual finds the first element, that is greater or equal to the given ListElement e.
  148. // The comparison is done on the keys (So on ExtractKey()).
  149. // FindGreaterOrEqual runs in approx. O(log(n))
  150. func (t *SkipList) FindGreaterOrEqual(key []byte) (prevIfVisited *SkipListElement, elem *SkipListElement, ok bool, err error) {
  151. if t == nil || key == nil {
  152. return
  153. }
  154. prevIfVisited, elem, ok, err = t.findExtended(key, true)
  155. return
  156. }
  157. // Delete removes an element equal to e from the skiplist, if there is one.
  158. // If there are multiple entries with the same value, Delete will remove one of them
  159. // (Which one will change based on the actual skiplist layout)
  160. // Delete runs in approx. O(log(n))
  161. func (t *SkipList) DeleteByKey(key []byte) (id int64, err error) {
  162. if t == nil || t.IsEmpty() || key == nil {
  163. return
  164. }
  165. index := t.findEntryIndex(key, t.MaxLevel)
  166. var currentNode *SkipListElement
  167. var nextNode *SkipListElement
  168. for {
  169. if currentNode == nil {
  170. nextNode, err = t.LoadElement(t.StartLevels[index])
  171. } else {
  172. nextNode, err = t.LoadElement(currentNode.Next[index])
  173. }
  174. if err != nil {
  175. return id, err
  176. }
  177. // Found and remove!
  178. if nextNode != nil && compareElement(nextNode, key) == 0 {
  179. if currentNode != nil {
  180. currentNode.Next[index] = nextNode.Next[index]
  181. if err = t.SaveElement(currentNode); err != nil {
  182. return id, err
  183. }
  184. }
  185. if index == 0 {
  186. if nextNode.Next[index] != nil {
  187. nextNextNode, err := t.LoadElement(nextNode.Next[index])
  188. if err != nil {
  189. return id, err
  190. }
  191. if nextNextNode != nil {
  192. nextNextNode.Prev = currentNode.Reference()
  193. if err = t.SaveElement(nextNextNode); err != nil {
  194. return id, err
  195. }
  196. }
  197. }
  198. // t.elementCount--
  199. id = nextNode.Id
  200. if err = t.DeleteElement(nextNode); err != nil {
  201. return id, err
  202. }
  203. }
  204. // Link from start needs readjustments.
  205. startNextKey := t.StartLevels[index].Key
  206. if compareElement(nextNode, startNextKey) == 0 {
  207. t.HasChanges = true
  208. t.StartLevels[index] = nextNode.Next[index]
  209. // This was our currently highest node!
  210. if t.StartLevels[index] == nil {
  211. t.MaxLevel = index - 1
  212. }
  213. }
  214. // Link from end needs readjustments.
  215. if nextNode.Next[index] == nil {
  216. t.EndLevels[index] = currentNode.Reference()
  217. t.HasChanges = true
  218. }
  219. nextNode.Next[index] = nil
  220. }
  221. if nextNode != nil && compareElement(nextNode, key) < 0 {
  222. // Go right
  223. currentNode = nextNode
  224. } else {
  225. // Go down
  226. index--
  227. if index < 0 {
  228. break
  229. }
  230. }
  231. }
  232. return
  233. }
  234. // Insert inserts the given ListElement into the skiplist.
  235. // Insert runs in approx. O(log(n))
  236. func (t *SkipList) InsertByKey(key []byte, idIfKnown int64, value []byte) (id int64, err error) {
  237. if t == nil || key == nil {
  238. return
  239. }
  240. level := t.generateLevel(t.MaxNewLevel)
  241. // Only grow the height of the skiplist by one at a time!
  242. if level > t.MaxLevel {
  243. level = t.MaxLevel + 1
  244. t.MaxLevel = level
  245. t.HasChanges = true
  246. }
  247. id = idIfKnown
  248. if id == 0 {
  249. id = rand.Int63()
  250. }
  251. elem := &SkipListElement{
  252. Id: id,
  253. Next: make([]*SkipListElementReference, t.MaxNewLevel, t.MaxNewLevel),
  254. Level: int32(level),
  255. Key: key,
  256. Value: value,
  257. }
  258. // t.elementCount++
  259. newFirst := true
  260. newLast := true
  261. if !t.IsEmpty() {
  262. newFirst = compareElement(elem, t.StartLevels[0].Key) < 0
  263. newLast = compareElement(elem, t.EndLevels[0].Key) > 0
  264. }
  265. normallyInserted := false
  266. if !newFirst && !newLast {
  267. normallyInserted = true
  268. index := t.findEntryIndex(key, level)
  269. var currentNode *SkipListElement
  270. var nextNodeRef *SkipListElementReference
  271. for {
  272. if currentNode == nil {
  273. nextNodeRef = t.StartLevels[index]
  274. } else {
  275. nextNodeRef = currentNode.Next[index]
  276. }
  277. var nextNode *SkipListElement
  278. // Connect node to next
  279. if index <= level && (nextNodeRef == nil || bytes.Compare(nextNodeRef.Key, key) > 0) {
  280. elem.Next[index] = nextNodeRef
  281. if currentNode != nil {
  282. currentNode.Next[index] = elem.Reference()
  283. if err = t.SaveElement(currentNode); err != nil {
  284. return
  285. }
  286. }
  287. if index == 0 {
  288. elem.Prev = currentNode.Reference()
  289. if nextNodeRef != nil {
  290. if nextNode, err = t.LoadElement(nextNodeRef); err != nil {
  291. return
  292. }
  293. if nextNode != nil {
  294. nextNode.Prev = elem.Reference()
  295. if err = t.SaveElement(nextNode); err != nil {
  296. return
  297. }
  298. }
  299. }
  300. }
  301. }
  302. if nextNodeRef != nil && bytes.Compare(nextNodeRef.Key, key) <= 0 {
  303. // Go right
  304. if nextNode == nil {
  305. // reuse nextNode when index == 0
  306. if nextNode, err = t.LoadElement(nextNodeRef); err != nil {
  307. return
  308. }
  309. }
  310. currentNode = nextNode
  311. if currentNode == nil {
  312. return
  313. }
  314. } else {
  315. // Go down
  316. index--
  317. if index < 0 {
  318. break
  319. }
  320. }
  321. }
  322. }
  323. // Where we have a left-most position that needs to be referenced!
  324. for i := level; i >= 0; i-- {
  325. didSomething := false
  326. if newFirst || normallyInserted {
  327. if t.StartLevels[i] == nil || bytes.Compare(t.StartLevels[i].Key, key) > 0 {
  328. if i == 0 && t.StartLevels[i] != nil {
  329. startLevelElement, err := t.LoadElement(t.StartLevels[i])
  330. if err != nil {
  331. return id, err
  332. }
  333. if startLevelElement != nil {
  334. startLevelElement.Prev = elem.Reference()
  335. if err = t.SaveElement(startLevelElement); err != nil {
  336. return id, err
  337. }
  338. }
  339. }
  340. elem.Next[i] = t.StartLevels[i]
  341. t.StartLevels[i] = elem.Reference()
  342. t.HasChanges = true
  343. }
  344. // link the EndLevels to this element!
  345. if elem.Next[i] == nil {
  346. t.EndLevels[i] = elem.Reference()
  347. t.HasChanges = true
  348. }
  349. didSomething = true
  350. }
  351. if newLast {
  352. // Places the element after the very last element on this level!
  353. // This is very important, so we are not linking the very first element (newFirst AND newLast) to itself!
  354. if !newFirst {
  355. if t.EndLevels[i] != nil {
  356. endLevelElement, err := t.LoadElement(t.EndLevels[i])
  357. if err != nil {
  358. return id, err
  359. }
  360. if endLevelElement != nil {
  361. endLevelElement.Next[i] = elem.Reference()
  362. if err = t.SaveElement(endLevelElement); err != nil {
  363. return id, err
  364. }
  365. }
  366. }
  367. if i == 0 {
  368. elem.Prev = t.EndLevels[i]
  369. }
  370. t.EndLevels[i] = elem.Reference()
  371. t.HasChanges = true
  372. }
  373. // Link the startLevels to this element!
  374. if t.StartLevels[i] == nil || bytes.Compare(t.StartLevels[i].Key, key) > 0 {
  375. t.StartLevels[i] = elem.Reference()
  376. t.HasChanges = true
  377. }
  378. didSomething = true
  379. }
  380. if !didSomething {
  381. break
  382. }
  383. }
  384. if err = t.SaveElement(elem); err != nil {
  385. return id, err
  386. }
  387. return id, nil
  388. }
  389. // GetSmallestNode returns the very first/smallest node in the skiplist.
  390. // GetSmallestNode runs in O(1)
  391. func (t *SkipList) GetSmallestNode() (*SkipListElement, error) {
  392. return t.LoadElement(t.StartLevels[0])
  393. }
  394. // GetLargestNode returns the very last/largest node in the skiplist.
  395. // GetLargestNode runs in O(1)
  396. func (t *SkipList) GetLargestNode() (*SkipListElement, error) {
  397. return t.LoadElement(t.EndLevels[0])
  398. }
  399. func (t *SkipList) GetLargestNodeReference() *SkipListElementReference {
  400. return t.EndLevels[0]
  401. }
  402. // Next returns the next element based on the given node.
  403. // Next will loop around to the first node, if you call it on the last!
  404. func (t *SkipList) Next(e *SkipListElement) (*SkipListElement, error) {
  405. if e.Next[0] == nil {
  406. return t.LoadElement(t.StartLevels[0])
  407. }
  408. return t.LoadElement(e.Next[0])
  409. }
  410. // Prev returns the previous element based on the given node.
  411. // Prev will loop around to the last node, if you call it on the first!
  412. func (t *SkipList) Prev(e *SkipListElement) (*SkipListElement, error) {
  413. if e.Prev == nil {
  414. return t.LoadElement(t.EndLevels[0])
  415. }
  416. return t.LoadElement(e.Prev)
  417. }
  418. // ChangeValue can be used to change the actual value of a node in the skiplist
  419. // without the need of Deleting and reinserting the node again.
  420. // Be advised, that ChangeValue only works, if the actual key from ExtractKey() will stay the same!
  421. // ok is an indicator, wether the value is actually changed.
  422. func (t *SkipList) ChangeValue(e *SkipListElement, newValue []byte) (err error) {
  423. // The key needs to stay correct, so this is very important!
  424. e.Value = newValue
  425. return t.SaveElement(e)
  426. }
  427. // String returns a string format of the skiplist. Useful to get a graphical overview and/or debugging.
  428. func (t *SkipList) println() {
  429. print("start --> ")
  430. for i, l := range t.StartLevels {
  431. if l == nil {
  432. break
  433. }
  434. if i > 0 {
  435. print(" -> ")
  436. }
  437. next := "---"
  438. if l != nil {
  439. next = string(l.Key)
  440. }
  441. print(fmt.Sprintf("[%v]", next))
  442. }
  443. println()
  444. nodeRef := t.StartLevels[0]
  445. for nodeRef != nil {
  446. print(fmt.Sprintf("%v: ", string(nodeRef.Key)))
  447. node, _ := t.LoadElement(nodeRef)
  448. if node == nil {
  449. break
  450. }
  451. for i := 0; i <= int(node.Level); i++ {
  452. l := node.Next[i]
  453. next := "---"
  454. if l != nil {
  455. next = string(l.Key)
  456. }
  457. if i == 0 {
  458. prev := "---"
  459. if node.Prev != nil {
  460. prev = string(node.Prev.Key)
  461. }
  462. print(fmt.Sprintf("[%v|%v]", prev, next))
  463. } else {
  464. print(fmt.Sprintf("[%v]", next))
  465. }
  466. if i < int(node.Level) {
  467. print(" -> ")
  468. }
  469. }
  470. nodeRef = node.Next[0]
  471. println()
  472. }
  473. print("end --> ")
  474. for i, l := range t.EndLevels {
  475. if l == nil {
  476. break
  477. }
  478. if i > 0 {
  479. print(" -> ")
  480. }
  481. next := "---"
  482. if l != nil {
  483. next = string(l.Key)
  484. }
  485. print(fmt.Sprintf("[%v]", next))
  486. }
  487. println()
  488. }