insert is a method of the SkipList type that is used to insert a new node into the skip list. It takes as arguments the score (int), key (string) and a value (interface{}), and returns a pointer to the ZSetValue struct. The method organizes nodes in the list based on the score in ascending order. If
(score int, key string, value interface{})
| 225 | // organizes nodes in the list based on the score in ascending order. If two nodes have the same score, they will be arranged |
| 226 | // based on the key value. The method also assigns span values to the levels in the skip list. |
| 227 | func (sl *SkipList) insert(score int, key string, value interface{}) *ZSetValue { |
| 228 | update := make([]*SkipListNode, SKIPLIST_MAX_LEVEL) |
| 229 | rank := make([]int, SKIPLIST_MAX_LEVEL) |
| 230 | node := sl.head |
| 231 | |
| 232 | // Go from highest level to lowest |
| 233 | for i := sl.level - 1; i >= 0; i-- { |
| 234 | // store rank that is crossed to reach the insert position |
| 235 | if sl.level-1 == i { |
| 236 | rank[i] = 0 |
| 237 | } else { |
| 238 | rank[i] = rank[i+1] |
| 239 | } |
| 240 | if node.level[i] != nil { |
| 241 | for node.level[i].next != nil && |
| 242 | (node.level[i].next.value.score < score || |
| 243 | (node.level[i].next.value.score == score && // score is the same but the key is different |
| 244 | node.level[i].next.value.member < key)) { |
| 245 | rank[i] += node.level[i].span |
| 246 | node = node.level[i].next |
| 247 | } |
| 248 | } |
| 249 | update[i] = node |
| 250 | } |
| 251 | level := randomLevel() |
| 252 | // add a new level |
| 253 | if level > sl.level { |
| 254 | for i := sl.level; i < level; i++ { |
| 255 | rank[i] = 0 |
| 256 | update[i] = sl.head |
| 257 | update[i].level[i].span = sl.size |
| 258 | } |
| 259 | sl.level = level |
| 260 | } |
| 261 | node = newSkipListNode(level, score, key, value) |
| 262 | |
| 263 | for i := 0; i < level; i++ { |
| 264 | node.level[i].next = update[i].level[i].next |
| 265 | update[i].level[i].next = node |
| 266 | // update span covered by update[i] as newNode is inserted here |
| 267 | node.level[i].span = update[i].level[i].span - (rank[0] - rank[i]) |
| 268 | update[i].level[i].span = (rank[0] - rank[i]) + 1 |
| 269 | } |
| 270 | // increment span for untouched levels |
| 271 | for i := level; i < sl.level; i++ { |
| 272 | update[i].level[i].span++ |
| 273 | } |
| 274 | // update info |
| 275 | if update[0] == sl.head { |
| 276 | node.prev = nil |
| 277 | } else { |
| 278 | node.prev = update[0] |
| 279 | } |
| 280 | if node.level[0].next != nil { |
| 281 | node.level[0].next.prev = node |
| 282 | } else { |
| 283 | sl.tail = node |
| 284 | } |