Method insertNode

sorted_set.go:352–422

(score SCORE, hash uint32, record *core.Record)

}

func (sl *SkipList) insertNode(score SCORE, hash uint32, record *core.Record) *SkipListNode {
	var update [SkipListMaxLevel]*SkipListNode
	var rank [SkipListMaxLevel]int64

	x := sl.header
	for i := sl.level - 1; i >= 0; i-- {
		// store rank that is crosled to reach the insert position
		if sl.level-1 == i {
			rank[i] = 0
		} else {
			rank[i] = rank[i+1]
		}

		for x.level[i].forward != nil &&
			(x.level[i].forward.score < score ||
				(x.level[i].forward.score == score && // score is the same but the key is different
					sl.cmp(x.level[i].forward.record, record) < 0)) {
			rank[i] += x.level[i].span
			x = x.level[i].forward
		}

		update[i] = x
	}

	/* we assume the key is not already inside, since we allow duplicated
	 * scores, and the re-insertion of score and redis object should never
	 * happen since the caller of Insert() should test in the hash table
	 * if the element is already inside or not. */
	level := randomLevel()

	if level > sl.level { // add a new level
		for i := sl.level; i < level; i++ {
			rank[i] = 0
			update[i] = sl.header
			update[i].level[i].span = sl.length
		}
		sl.level = level
	}

	x = createNode(level, score, hash, record)
	for i := 0; i < level; i++ {
		x.level[i].forward = update[i].level[i].forward
		update[i].level[i].forward = x

		/* update span covered by update[i] as x is inserted here */
		x.level[i].span = update[i].level[i].span - (rank[0] - rank[i])

		update[i].level[i].span = (rank[0] - rank[i]) + 1
	}

	// increment span for untouched levels
	for i := level; i < sl.level; i++ {
		update[i].level[i].span++
	}

	if update[0] == sl.header {
		x.backward = nil
	} else {