iterator.go
func (it *Iterator) Add(key []byte, val []byte, meta uint16) error {
	var spl [maxHeight]splice
	if it.seekForSplice(key, &spl) {
		// Found a matching node, but handle case where it's been deleted.
		return it.setValueIfDeleted(spl[0].next, val, meta)
	}

	if it.list.testing {
		// Add delay to make it easier to test race between this thread
		// and another thread that sees the intermediate state between
		// finding the splice and using it.
		runtime.Gosched()
	}

	nd, height, err := it.list.newNode(key, val, meta)
	if err != nil {
		return err
	}

	value := nd.value
	ndOffset := it.arena.GetPointerOffset(unsafe.Pointer(nd))

	// We always insert from the base level and up. After you add a node in base
	// level, we cannot create a node in the level above because it would have
	// discovered the node in the base level.
	var found bool
	for i := 0; i < int(height); i++ {
		prev := spl[i].prev
		next := spl[i].next

		if prev == nil {
			// New node increased the height of the skiplist, so assume that the
			// new level has not yet been populated.
			if next != nil {
				panic("next is expected to be nil, since prev is nil")
			}

			prev = it.list.head
			next = it.list.tail
		}

		// +----------------+     +------------+     +----------------+
		// |      prev      |     |     nd     |     |      next      |
		// | prevNextOffset |---->|            |     |                |
		// |                |<----| prevOffset |     |                |
		// |                |     | nextOffset |---->|                |
		// |                |     |            |<----| nextPrevOffset |
		// +----------------+     +------------+     +----------------+
		//
		// 1. Initialize prevOffset and nextOffset to point to prev and next.
		// 2. CAS prevNextOffset to repoint from next to nd.
		// 3. CAS nextPrevOffset to repoint from prev to nd.
		for {
			prevOffset := it.arena.GetPointerOffset(unsafe.Pointer(prev))
			nextOffset := it.arena.GetPointerOffset(unsafe.Pointer(next))
			nd.tower[i].init(prevOffset, nextOffset)

			// Check whether next has an updated link to prev. If it does not,
			// that can mean one of two things:
			//   1. The thread that added the next node hasn't yet had a chance
			//      to add the prev link (but will shortly).
			//   2. Another thread has added a new node between prev and next.
			nextPrevOffset := next.prevOffset(i)
			if nextPrevOffset != prevOffset {
				// Determine whether #1 or #2 is true by checking whether prev
				// is still pointing to next. As long as the atomic operations
				// have at least acquire/release semantics (no need for
				// sequential consistency), this works, as it is equivalent to
				// the "publication safety" pattern.
				prevNextOffset := prev.nextOffset(i)
				if prevNextOffset == nextOffset {
					// Ok, case #1 is true, so help the other thread along by
					// updating the next node's prev link.
					next.casPrevOffset(i, nextPrevOffset, prevOffset)
				}
			}

			if prev.casNextOffset(i, nextOffset, ndOffset) {
				// Managed to insert nd between prev and next, so update the next
				// node's prev link and go to the next level.
				if it.list.testing {
					// Add delay to make it easier to test race between this thread
					// and another thread that sees the intermediate state between
					// setting next and setting prev.
					runtime.Gosched()
				}

				next.casPrevOffset(i, prevOffset, ndOffset)
				break
			}

			// CAS failed. We need to recompute prev and next. It is unlikely to
			// be helpful to try to use a different level as we redo the search,
			// because it is unlikely that lots of nodes are inserted between prev
			// and next.
			prev, next, found = it.list.findSpliceForLevel(key, i, prev)
			if found {
				if i != 0 {
					panic("how can another thread have inserted a node at a non-base level?")
				}

				return it.setValueIfDeleted(next, val, meta)
			}
		}
	}

	it.value = value
	it.nd = nd
	return nil
}
func (it *Iterator) Add(key []byte, val []byte, meta uint16) error {
	var spl [maxHeight]splice
	if it.seekForSplice(key, &spl) {
		// Found a matching node, but handle case where it's been deleted.
		return it.setValueIfDeleted(spl[0].next, val, meta)
	}

	if it.list.testing {
		// Add delay to make it easier to test race between this thread
		// and another thread that sees the intermediate state between
		// finding the splice and using it.
		runtime.Gosched()
	}

	nd, height, err := it.list.newNode(key, val, meta)
	if err != nil {
		return err
	}

	value := nd.value
	ndOffset := it.arena.GetPointerOffset(unsafe.Pointer(nd))

	// We always insert from the base level and up. After you add a node in base
	// level, we cannot create a node in the level above because it would have
	// discovered the node in the base level.
	var found bool
	for i := 0; i < int(height); i++ {
		prev := spl[i].prev
		next := spl[i].next

		if prev == nil {
			// New node increased the height of the skiplist, so assume that the
			// new level has not yet been populated.
			if next != nil {
				panic("next is expected to be nil, since prev is nil")
			}

			prev = it.list.head
			next = it.list.tail
		}

		// +----------------+     +------------+     +----------------+
		// |      prev      |     |     nd     |     |      next      |
		// | prevNextOffset |---->|            |     |                |
		// |                |<----| prevOffset |     |                |
		// |                |     | nextOffset |---->|                |
		// |                |     |            |<----| nextPrevOffset |
		// +----------------+     +------------+     +----------------+
		//
		// 1. Initialize prevOffset and nextOffset to point to prev and next.
		// 2. CAS prevNextOffset to repoint from next to nd.
		// 3. CAS nextPrevOffset to repoint from prev to nd.
		for {
			prevOffset := it.arena.GetPointerOffset(unsafe.Pointer(prev))
			nextOffset := it.arena.GetPointerOffset(unsafe.Pointer(next))
			nd.tower[i].init(prevOffset, nextOffset)

			// Check whether next has an updated link to prev. If it does not,
			// that can mean one of two things:
			//   1. The thread that added the next node hasn't yet had a chance
			//      to add the prev link (but will shortly).
			//   2. Another thread has added a new node between prev and next.
			nextPrevOffset := next.prevOffset(i)
			if nextPrevOffset != prevOffset {
				// Determine whether #1 or #2 is true by checking whether prev
				// is still pointing to next. As long as the atomic operations
				// have at least acquire/release semantics (no need for
				// sequential consistency), this works, as it is equivalent to
				// the "publication safety" pattern.
				prevNextOffset := prev.nextOffset(i)
				if prevNextOffset == nextOffset {
					// Ok, case #1 is true, so help the other thread along by
					// updating the next node's prev link.
					next.casPrevOffset(i, nextPrevOffset, prevOffset)
				}
			}

			if prev.casNextOffset(i, nextOffset, ndOffset) {
				// Managed to insert nd between prev and next, so update the next
				// node's prev link and go to the next level.
				if it.list.testing {
					// Add delay to make it easier to test race between this thread
					// and another thread that sees the intermediate state between
					// setting next and setting prev.
					runtime.Gosched()
				}

				next.casPrevOffset(i, prevOffset, ndOffset)
				break
			}

			// CAS failed. We need to recompute prev and next. It is unlikely to
			// be helpful to try to use a different level as we redo the search,
			// because it is unlikely that lots of nodes are inserted between prev
			// and next.
			prev, next, found = it.list.findSpliceForLevel(key, i, prev)
			if found {
				if i != 0 {
					panic("how can another thread have inserted a node at a non-base level?")
				}

				return it.setValueIfDeleted(next, val, meta)
			}
		}
	}

	it.value = value
	it.nd = nd
	return nil
}
func ( it * Iterator ) Add ( key [ ] byte , val [ ] byte , meta uint16 ) error { var spl [ maxHeight ] splice if it . seekForSplice ( key , & spl ) { // Found a matching node, but handle case where it's been deleted. return it . setValueIfDeleted ( spl [ 0 ] . next , val , meta ) } if it . list . testing { // Add delay to make it easier to test race between this thread // and another thread that sees the intermediate state between // finding the splice and using it. runtime . Gosched ( ) } nd , height , err := it . list . newNode ( key , val , meta ) if err != nil { return err } value := nd . value ndOffset := it . arena . GetPointerOffset ( unsafe . Pointer ( nd ) ) // We always insert from the base level and up. After you add a node in base // level, we cannot create a node in the level above because it would have // discovered the node in the base level. var found bool for i := 0 ; i < int ( height ) ; i ++ { prev := spl [ i ] . prev next := spl [ i ] . next if prev == nil { // New node increased the height of the skiplist, so assume that the // new level has not yet been populated. if next != nil { panic ( " " ) } prev = it . list . head next = it . list . tail } // +----------------+     +------------+     +----------------+ // |      prev      |     |     nd     |     |      next      | // | prevNextOffset |---->|            |     |                | // |                |<----| prevOffset |     |                | // |                |     | nextOffset |---->|                | // |                |     |            |<----| nextPrevOffset | // +----------------+     +------------+     +----------------+ // // 1. Initialize prevOffset and nextOffset to point to prev and next. // 2. CAS prevNextOffset to repoint from next to nd. // 3. CAS nextPrevOffset to repoint from prev to nd. for { prevOffset := it . arena . GetPointerOffset ( unsafe . Pointer ( prev ) ) nextOffset := it . arena . GetPointerOffset ( unsafe . Pointer ( next ) ) nd . tower [ i ] . init ( prevOffset , nextOffset ) // Check whether next has an updated link to prev. If it does not, // that can mean one of two things: //   1. The thread that added the next node hasn't yet had a chance //      to add the prev link (but will shortly). //   2. Another thread has added a new node between prev and next. nextPrevOffset := next . prevOffset ( i ) if nextPrevOffset != prevOffset { // Determine whether #1 or #2 is true by checking whether prev // is still pointing to next. As long as the atomic operations // have at least acquire/release semantics (no need for // sequential consistency), this works, as it is equivalent to // the "publication safety" pattern. prevNextOffset := prev . nextOffset ( i ) if prevNextOffset == nextOffset { // Ok, case #1 is true, so help the other thread along by // updating the next node's prev link. next . casPrevOffset ( i , nextPrevOffset , prevOffset ) } } if prev . casNextOffset ( i , nextOffset , ndOffset ) { // Managed to insert nd between prev and next, so update the next // node's prev link and go to the next level. if it . list . testing { // Add delay to make it easier to test race between this thread // and another thread that sees the intermediate state between // setting next and setting prev. runtime . Gosched ( ) } next . casPrevOffset ( i , prevOffset , ndOffset ) break } // CAS failed. We need to recompute prev and next. It is unlikely to // be helpful to try to use a different level as we redo the search, // because it is unlikely that lots of nodes are inserted between prev // and next. prev , next , found = it . list . findSpliceForLevel ( key , i , prev ) if found { if i != 0 { panic ( " " ) } return it . setValueIfDeleted ( next , val , meta ) } } } it . value = value it . nd = nd return nil }
// Add creates a new key/value record if it does not yet exist and positions the
// iterator on it. If the record already exists, then Add positions the iterator
// on the most current value and returns ErrRecordExists. If there isn't enough
// room in the arena, then Add returns ErrArenaFull.
Add creates a new key / value record if it does not yet exist and positions the iterator on it . If the record already exists then Add positions the iterator on the most current value and returns ErrRecordExists . If there isn t enough room in the arena then Add returns ErrArenaFull .