skiplist

package module
v1.2.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 24, 2025 License: MIT Imports: 4 Imported by: 1

README

Go Generic Skiplist

Go Go Report Card Go Reference

A thread-safe, high-performance, generic skiplist implementation in Go.

This library provides a skiplist data structure that is easy to use, highly efficient, and flexible. It's designed to be a powerful alternative to Go's built-in map when you need sorted, ordered data access with logarithmic time complexity for search, insert, and delete operations.

A skiplist maintains sorted order by using a hierarchy of linked lists. Lower levels have more elements, creating a dense index, while higher levels have fewer elements, acting as "express lanes" to skip over large portions of the list. This structure enables fast searching.

Level 3: 1-------------------------------->9
          |                                |
Level 2: 1--------->4--------------------->9
          |          |                     |
Level 1: 1--->2----->4--------->6--------->9
          |   |      |          |         |
Data:    (1) (2)    (4)        (6)       (9)

Features

  • 🚀 High Performance: O(log n) average time complexity for major operations.
  • 🧠 Memory Optimized:
    • sync.Pool (Default): Recycles nodes to reduce memory allocations and GC pressure, ideal for high-churn workloads.
    • ⚡️ Optional Growable Memory Arena: For maximum performance and minimal GC impact, an optional memory arena allocator can be enabled. It can grow automatically to accommodate more data, with configurable growth strategies.
  • ⛓️ Generic: Fully generic ([K any, V any]), allowing any type for keys and values.
  • 🎛️ Customizable Sorting: Supports custom comparator functions, enabling complex sorting logic for any key type (e.g., structs).
  • 🤝 Thread-Safe: All operations are safe for concurrent use from multiple goroutines.
  • ✨ Rich API: Includes a comprehensive set of methods like RangeQuery, PopMin, PopMax, Predecessor, Successor, and more.
  • 🚶 Full-Featured Iterator: Provides a powerful bidirectional iterator with Seek, Next, Prev, First, Last, Reset, etc., for flexible data traversal.

Why Use This Skip List?

While Go's built-in map is excellent for general-purpose key-value storage, it does not maintain any order. This skiplist is superior in scenarios where sorted data is crucial.

Use Case map[K]V sync.Map This SkipList[K, V]
Unordered Key-Value ✅ Best Choice ✅ (Concurrent) (Overhead)
Ordered Iteration ❌ (Unordered) ❌ (Unordered) ✅ Best Choice
Find Min/Max Key ❌ (Requires full scan) ❌ (Requires full scan) ✅ O(1)
Range Queries (e.g., keys 10-50) ❌ (Requires full scan) ❌ (Requires full scan) ✅ O(log n + k)
Find Predecessor/Successor ❌ (Unordered) ❌ (Unordered) ✅ O(log n)
Fine-grained GC Control ❌ ❌ ✅ (via sync.Pool or Arena)

Performance

This skiplist offers two memory allocation strategies, each with distinct performance characteristics. You can run the benchmarks yourself via go test -bench=..

  • sync.Pool (Default): This is the standard, memory-efficient choice. It excels in high-churn workloads (frequent inserts and deletes) by recycling nodes, which significantly reduces the garbage collector's workload.
  • Memory Arena (Optional): This is the high-throughput choice. It works by allocating memory from large, pre-allocated blocks called chunks. When a chunk is full, the arena can grow automatically by allocating a new, larger chunk, nearly eliminating GC overhead for node allocations. This results in lower and more predictable latency for bulk operations. You can configure the initial size, growth factor, and even a proactive growth threshold. It's less ideal for high-churn workloads where nodes are not reclaimed individually.

Conclusion:

  • Use the default sync.Pool for general-purpose use and high-churn scenarios (frequent inserts/deletes).
  • Use the Memory Arena for the absolute lowest latency during bulk inserts/reads.

Installation

$ go get github.com/INLOpen/skiplist

Usage

Basic Usage (Ordered Keys)

For standard key types that support ordering (like int, string), you can use the simple New() constructor.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
)

func main() {
	// Create a new skiplist for int keys and string values.
	// The default comparator (cmp.Compare) is used automatically.
	sl := skiplist.New[int, string]()

	sl.Insert(10, "ten")
	sl.Insert(20, "twenty")
	sl.Insert(30, "thirty")

	// Search for a value
	node, ok := sl.Search(20)
	if ok {
		fmt.Printf("Found key 20 with value: %s\n", node.Value()) // "twenty"
	}

	// Iterate over all items in sorted order
	fmt.Println("All items:")
	sl.Range(func(key int, value string) bool {
		fmt.Printf("  %d: %s\n", key, value)
		return true // Continue iteration
	})

	// Pop the maximum element
	maxNode, ok := sl.PopMax()
	if ok {
		fmt.Printf("Popped max element: %d -> %s\n", maxNode.Key(), maxNode.Value()) // 30 -> "thirty"
	}

	fmt.Printf("Current length: %d\n", sl.Len()) // 2
}
Basic Arena Usage

For scenarios demanding the lowest possible latency, such as bulk loading data, you can enable the memory arena.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
)

func main() {
	// For maximum performance, create a skiplist with a 128MB memory arena.
	// This is ideal for scenarios where you insert a large number of items
	// and want to minimize garbage collection overhead.
	arenaOpt := skiplist.WithArena[int, string](128 * 1024 * 1024) // 128MB
	sl := skiplist.New[int, string](arenaOpt)

	// Operations are the same
	sl.Insert(1, "one")
	fmt.Println("Length with Arena:", sl.Len())
}
Advanced Arena Usage (with Automatic Growth)

The memory arena can be configured to start small and grow automatically as needed.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
)

func main() {
	// Configure an arena that starts small and grows automatically.
	// This is useful when you don't know the exact memory usage upfront.
	sl := skiplist.New[int, string](
		// Start with a small 1KB arena.
		skiplist.WithArena[int, string](1024),
		// When the arena is full, grow it by a factor of 2.
		skiplist.WithArenaGrowthFactor[int, string](2.0),
		// Proactively grow when a chunk is 90% full to avoid fragmentation.
		skiplist.WithArenaGrowthThreshold[int, string](0.9),
	)

	// Insert more data than the initial arena can hold to trigger growth.
	for i := 0; i < 1000; i++ {
		sl.Insert(i, fmt.Sprintf("value-%d", i))
	}

	fmt.Println("Successfully inserted 1000 items with a growing arena.")
	fmt.Println("Final length:", sl.Len())
}
Custom Comparator (Struct Keys)

To use a custom struct as a key, you must provide your own comparator function to NewWithComparator.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
)

type User struct {
	ID   int
	Name string
}

// userComparator defines how to sort User keys (by ID).
func userComparator(a, b User) int {
	if a.ID < b.ID {
		return -1
	}
	if a.ID > b.ID {
		return 1
	}
	return 0
}

func main() {
	// Create a skiplist with a custom comparator
	sl := skiplist.NewWithComparator[User, string](userComparator)

	sl.Insert(User{ID: 2, Name: "Bob"}, "Engineer")
	sl.Insert(User{ID: 1, Name: "Alice"}, "Manager")

	// The list is sorted by User.ID. Min() returns an INode.
	minNode, ok := sl.Min()
	if ok {
		userKey := minNode.Key()
		fmt.Printf("Min user is: %s (ID: %d), Role: %s\n", userKey.Name, userKey.ID, minNode.Value()) // "Alice (ID: 1), Role: Manager"
	}
}
Concurrent Usage

The skiplist is safe for concurrent use. You can have multiple goroutines reading and writing to the list simultaneously without external locking.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
	"sync"
)

func main() {
	sl := skiplist.New[int, int]()
	var wg sync.WaitGroup

	// Concurrently insert 1000 items
	for i := 0; i < 1000; i++ {
		wg.Add(1)
		go func(val int) {
			defer wg.Done()
			sl.Insert(val, val*10)
		}(i)
	}

	wg.Wait()
	fmt.Printf("After concurrent inserts, length is: %d\n", sl.Len()) // 1000
}
Iterator Usage

The iterator provides fine-grained control over list traversal.

package main

import (
	"fmt"
	"github.com/INLOpen/skiplist"
)

func main() {
	sl := skiplist.New[int, string]()
	sl.Insert(10, "A")
	sl.Insert(20, "B")
	sl.Insert(30, "C")
	sl.Insert(40, "D")

	// Create a new iterator
	it := sl.NewIterator()

	// Seek to the first element >= 25
	it.Seek(25)

	// Iterate from the seeked position
	fmt.Println("Iterating from key 25 onwards:")
	for it.Next() {
		fmt.Printf("  %d: %s\n", it.Key(), it.Value())
	}
	// Output:
	//   30: C
	//   40: D
}

API Reference

Constructors
  • New[K cmp.Ordered, V any](opts ...Option[K, V]) *SkipList[K, V]
  • NewWithComparator[K any, V any](compare Comparator[K], opts ...Option[K, V]) *SkipList[K, V]
Configuration Options
  • WithArena[K, V](sizeInBytes int) Option[K, V]
  • WithArenaGrowthFactor[K, V](factor float64) Option[K, V])
  • WithArenaGrowthBytes[K, V](bytes int) Option[K, V]
  • WithArenaGrowthThreshold[K, V](threshold float64) Option[K, V]
Basic Operations
  • (sl *SkipList[K, V]) Insert(key K, value V) INode[K, V]
  • (sl *SkipList[K, V]) Search(key K) (INode[K, V], bool)
  • (sl *SkipList[K, V]) Delete(key K) bool
  • (sl *SkipList[K, V]) Len() int
  • (sl *SkipList[K, V]) Clear()
Ordered Operations
  • (sl *SkipList[K, V]) Min() (INode[K, V], bool)
  • (sl *SkipList[K, V]) Max() (INode[K, V], bool)
  • (sl *SkipList[K, V]) PopMin() (INode[K, V], bool)
  • (sl *SkipList[K, V]) PopMax() (INode[K, V], bool)
  • (sl *SkipList[K, V]) Predecessor(key K) (INode[K, V], bool)
  • (sl *SkipList[K, V]) Successor(key K) (INode[K, V], bool)
  • (sl *SkipList[K, V]) Seek(key K) (INode[K, V], bool)
Iteration & Range
  • (sl *SkipList[K, V]) Range(f func(key K, value V) bool)
  • (sl *SkipList[K, V]) RangeQuery(start, end K, f func(key K, value V) bool)
  • (sl *SkipList[K, V]) CountRange(start, end K) int
  • (sl *SkipList[K, V]) NewIterator() *Iterator[K, V]
  • (sl *SkipList[K, V]) RangeWithIterator(f func(it *Iterator[K, V]))
Iterator Methods
  • (it *Iterator[K, V]) Next() bool
  • (it *Iterator[K, V]) Prev() bool
  • (it *Iterator[K, V]) Key() K
  • (it *Iterator[K, V]) Value() V
  • (it *Iterator[K, V]) Seek(key K) bool
  • (it *Iterator[K, V]) SeekToFirst() bool
  • (it *Iterator[K, V]) SeekToLast() bool
  • (it *Iterator[K, V]) First() bool
  • (it *Iterator[K, V]) Last() bool
  • (it *Iterator[K, V]) Reset()
  • (it *Iterator[K, V]) Clone() *Iterator[K, V]

Contributing

Contributions are welcome! Please feel free to submit a pull request or open an issue.

License

This project is licensed under the MIT License - see the LICENSE.md file for details.

Documentation

Overview

package skiplist implements a thread-safe, generic skiplist. A skiplist is a probabilistic data structure that allows for fast search, insertion, and deletion of elements in a sorted sequence. It provides O(log n) performance on average for these operations.

Index

Constants

View Source 
const (
	// MaxLevel is the maximum number of levels a skiplist can have.
	// A value of 32 is sufficient for approximately 2^32 (4 billion) items.
	// MaxLevel คือจำนวนชั้นสูงสุดที่ skiplist สามารถมีได้
	// ค่า 32 เพียงพอสำหรับข้อมูลประมาณ 2^32 (4 พันล้าน) รายการ
	MaxLevel = 32
	// P is the probability used to determine the level of a new node.
	// A value of 0.25 is commonly used and provides good performance.
	// P คือค่าความน่าจะเป็นในการเพิ่มชั้นของโหนดใหม่
	// ค่า 0.25 เป็นค่าที่นิยมใช้และให้ประสิทธิภาพที่ดี
	P = 0.25
)

Variables

This section is empty.

Functions

This section is empty.

Types

type Arena added in v1.2.0 

type Arena struct {
	// contains filtered or unexported fields
}

The Arena itself is NOT thread-safe; synchronization must be handled by the caller. ตัว Arena เองไม่ thread-safe; ผู้เรียกต้องจัดการ synchronization เอง

func NewArena added in v1.2.0 

func NewArena(initialSize int, opts ...ArenaOption) *Arena

NewArena creates a new, potentially growable Arena.

func (*Arena) Alloc added in v1.2.0 

func (a *Arena) Alloc(size, alignment uintptr) unsafe.Pointer

Alloc จัดสรรหน่วยความจำตามขนาด (size) และ alignment ที่ต้องการ คืนค่า pointer ไปยังหน่วยความจำที่จัดสรร หรือ nil หาก Arena เต็ม. This implementation is NOT thread-safe. The caller must provide synchronization. การทำงานนี้ไม่ thread-safe ผู้เรียกต้องจัดการ synchronization เอง

func (*Arena) Reset added in v1.2.0 

func (a *Arena) Reset()

Reset ทำให้หน่วยความจำทั้งหมดใน Arena พร้อมใช้งานใหม่ (โดยไม่ได้ลบค่าเก่า)

type ArenaOption added in v1.2.1 

type ArenaOption func(*Arena)

ArenaOption configures an Arena.

func WithGrowthBytes added in v1.2.1 

func WithGrowthBytes(bytes int) ArenaOption

WithGrowthBytes sets the arena to grow by a fixed number of bytes.

func WithGrowthFactor added in v1.2.1 

func WithGrowthFactor(factor float64) ArenaOption

WithGrowthFactor sets the arena to grow by a factor of the previous chunk's size. For example, a factor of 2.0 means each new chunk will be twice as large as the last.

func WithGrowthThreshold added in v1.2.1 

func WithGrowthThreshold(threshold float64) ArenaOption

WithGrowthThreshold sets a threshold (e.g., 0.9 for 90%) for proactive growth. If an allocation would cause the current chunk's usage to exceed this threshold, a new chunk is allocated preemptively. This helps avoid leaving small, unusable fragments at the end of chunks. A threshold of 0 disables this feature.

type Comparator 

type Comparator[K any] func(a, b K) int

Comparator is a function that compares two keys. It should return:

  • a negative value if a < b
  • zero if a == b
  • a positive value if a > b

Comparator คือฟังก์ชันสำหรับเปรียบเทียบ key สองตัว ควรคืนค่า: 

< 0 ถ้า a น้อยกว่า b
0 ถ้า a เท่ากับ b
> 0 ถ้า a มากกว่า b

type INode added in v1.2.0 

type INode[K any, V any] interface {
	Key() K
	Value() V
}

type Iterator 

type Iterator[K any, V any] struct {
	// contains filtered or unexported fields
}

Iterator provides a way to iterate over the elements of a SkipList. The typical use is: 

it := sl.NewIterator()
for it.Next() {
	key := it.Key()
	value := it.Value()
	// ...
}

Iterator คือโครงสร้างที่ใช้สำหรับวนลูปผ่านรายการใน Skiplist รูปแบบการใช้งานทั่วไป: 

it := sl.NewIterator()
for it.Next() {
	key := it.Key()
	value := it.Value()
	// ...
}

func (*Iterator[K, V]) Clone added in v1.2.0 

func (it *Iterator[K, V]) Clone() *Iterator[K, V]

Clone creates an independent copy of the iterator at its current position. The new iterator can be moved independently of the original. Clone สร้างสำเนาของ Iterator ณ ตำแหน่งปัจจุบัน Iterator ที่สร้างขึ้นใหม่จะทำงานเป็นอิสระจากตัวต้นฉบับ

func (*Iterator[K, V]) First added in v1.2.0 

func (it *Iterator[K, V]) First() bool

First moves the iterator to the first element in the skiplist. This is the element with the smallest key, regardless of the iterator's direction. It returns true if a first element exists, otherwise it returns false. After a call to First(), Key() and Value() will return the data of the first element. First เลื่อน Iterator ไปยังรายการแรกใน Skiplist (รายการที่มี key น้อยที่สุด) โดยไม่สนใจทิศทางของ iterator คืนค่า true หากมีรายการแรกอยู่, มิฉะนั้นคืนค่า false หลังจากเรียก First(), Key() และ Value() จะคืนค่าของรายการแรก

func (*Iterator[K, V]) Key 

func (it *Iterator[K, V]) Key() K

Key returns the key of the element at the current iterator position. It should only be called after a call to Next() has returned true. Key คืนค่า key ของรายการปัจจุบันที่ Iterator ชี้อยู่ ควรเรียกใช้หลังจากที่ Next(), First(), Last(), หรือ Seek() ที่สำเร็จ คืนค่า true เท่านั้น การเรียกใช้บน iterator ที่ไม่ถูกต้อง (เช่น สิ้นสุดไปแล้ว) จะทำให้เกิด panic

func (*Iterator[K, V]) Last added in v1.2.0 

func (it *Iterator[K, V]) Last() bool

Last moves the iterator to the last element in the skiplist. This is the element with the largest key, regardless of the iterator's direction. It returns true if a last element exists, otherwise it returns false. After a call to Last(), Key() and Value() will return the data of the last element. Last เลื่อน Iterator ไปยังรายการสุดท้ายใน Skiplist (รายการที่มี key มากที่สุด) โดยไม่สนใจทิศทางของ iterator คืนค่า true หากมีรายการสุดท้ายอยู่, มิฉะนั้นคืนค่า false หลังจากเรียก Last(), Key() และ Value() จะคืนค่าของรายการสุดท้าย

func (*Iterator[K, V]) Next 

func (it *Iterator[K, V]) Next() bool

Next moves the iterator to the next element and returns true if the move was successful. If the iterator was created with WithReverse, "next" means the previous element in the list. It returns false if there are no more elements. Next เลื่อน Iterator ไปยังรายการถัดไป และคืนค่า true หากสำเร็จ หาก Iterator ถูกสร้างด้วย WithReverse, "ถัดไป" จะหมายถึงรายการ "ก่อนหน้า" คืนค่า false หากไม่มีรายการเหลือแล้ว

func (*Iterator[K, V]) Prev added in v1.2.0 

func (it *Iterator[K, V]) Prev() bool

Prev moves the iterator to the previous element and returns true if the move was successful. If the iterator was created with WithReverse, "previous" means the next element in the list. It returns false if there are no more elements in that direction. Prev เลื่อน Iterator ไปยังรายการก่อนหน้า และคืนค่า true หากสำเร็จ หาก Iterator ถูกสร้างด้วย WithReverse, "ก่อนหน้า" จะหมายถึงรายการ "ถัดไป" คืนค่า false หากไม่มีรายการเหลือแล้วในทิศทางนั้น

func (*Iterator[K, V]) Reset added in v1.2.0 

func (it *Iterator[K, V]) Reset()

Reset moves the iterator back to its initial state, before the first element. A subsequent call to Next() is required to advance to the first element. This method respects the iterator's direction (normal or reverse). Reset เลื่อน Iterator กลับไปยังสถานะเริ่มต้น (ก่อนรายการแรก) โดยจะเคารพทิศทางของ iterator (ปกติหรือย้อนกลับ) ต้องเรียก Next() อีกครั้งเพื่อเลื่อนไปยังรายการแรก

func (*Iterator[K, V]) Seek 

func (it *Iterator[K, V]) Seek(key K) bool

Seek moves the iterator to the first element with a key greater than or equal to the given key. This behavior is consistent regardless of the iterator's direction (normal or reverse). It returns true if such an element is found, otherwise it returns false and the iterator is positioned at the end. After a successful seek, Key() and Value() will return the data of the found element. Seek เลื่อน Iterator ไปยังรายการแรกที่มี key เท่ากับหรือมากกว่า key ที่กำหนด พฤติกรรมนี้จะเหมือนกันเสมอ ไม่ว่า iterator จะเป็นแบบปกติหรือแบบย้อนกลับ (reverse) คืนค่า true หากพบรายการดังกล่าว, มิฉะนั้นคืนค่า false และ Iterator จะชี้ไปที่ท้ายสุด หลังจาก seek สำเร็จ, Key() และ Value() จะคืนค่าของรายการที่พบ

func (*Iterator[K, V]) SeekToFirst added in v1.2.1 

func (it *Iterator[K, V]) SeekToFirst() bool

SeekToFirst positions the iterator just before the first element. For a forward iterator, this is before the smallest key. For a reverse iterator, this is before the largest key. A subsequent call to Next() will advance the iterator to the first element. It returns true if the list is not empty, indicating that a subsequent call to Next() will succeed. SeekToFirst เลื่อน Iterator ไปยังตำแหน่งก่อนหน้าของรายการแรกในลำดับการวนลูป สำหรับ iterator ไปข้างหน้า: คือก่อน key ที่น้อยที่สุด สำหรับ iterator ย้อนกลับ: คือก่อน key ที่มากที่สุด คืนค่า true หาก list ไม่ว่างเปล่า เพื่อบ่งชี้ว่าการเรียก Next() ครั้งถัดไปจะสำเร็จ

func (*Iterator[K, V]) SeekToLast added in v1.2.1 

func (it *Iterator[K, V]) SeekToLast() bool

SeekToLast positions the iterator just before the last element in the skiplist (the one with the largest key). This behavior is consistent regardless of the iterator's direction (normal or reverse). A subsequent call to Next() will advance the iterator to the last element. It returns true if the list is not empty.

SeekToLast เลื่อน Iterator ไปยังตำแหน่งก่อนหน้าของรายการสุดท้ายใน Skiplist (รายการที่มี key สูงสุด) พฤติกรรมนี้จะเหมือนกันเสมอ ไม่ว่า iterator จะเป็นแบบปกติหรือแบบย้อนกลับ (reverse) การเรียก Next() หลังจากนี้จะเลื่อนไปยังรายการสุดท้าย

func (*Iterator[K, V]) Value 

func (it *Iterator[K, V]) Value() V

Value returns the value of the element at the current iterator position. It should only be called after a call to Next() has returned true. Value คืนค่า value ของรายการปัจจุบันที่ Iterator ชี้อยู่ ควรเรียกใช้หลังจากที่ Next(), First(), Last(), หรือ Seek() ที่สำเร็จ คืนค่า true เท่านั้น การเรียกใช้บน iterator ที่ไม่ถูกต้อง (เช่น สิ้นสุดไปแล้ว) จะทำให้เกิด panic

type IteratorOption added in v1.2.1 

type IteratorOption[K any, V any] func(*Iterator[K, V])

IteratorOption configures an Iterator. IteratorOption คือฟังก์ชันสำหรับกำหนดค่าของ Iterator

func WithReverse added in v1.2.1 

func WithReverse[K any, V any]() IteratorOption[K, V]

WithReverse creates an iterator that iterates from the last element to the first. The standard `for it.Next() { ... }` loop will work in reverse.

type Option added in v1.2.0 

type Option[K any, V any] func(*SkipList[K, V])

Option is a function that configures a SkipList. Option คือฟังก์ชันสำหรับกำหนดค่าของ SkipList

func WithArena added in v1.2.0 

func WithArena[K any, V any](sizeInBytes int) Option[K, V]

WithArena configures the SkipList to use a memory arena of a given size in bytes. This sets the initial size of the arena. The arena can grow automatically if needed. WithArena กำหนดให้ SkipList ใช้ memory arena ตามขนาดที่ระบุ (เป็น byte) เป็นการกำหนดขนาดเริ่มต้น และ arena สามารถขยายขนาดได้เองเมื่อจำเป็น

func WithArenaGrowthBytes added in v1.2.1 

func WithArenaGrowthBytes[K any, V any](bytes int) Option[K, V]

WithArenaGrowthBytes configures the arena to grow by a fixed number of bytes. This option is only effective when used with WithArena.

func WithArenaGrowthFactor added in v1.2.1 

func WithArenaGrowthFactor[K any, V any](factor float64) Option[K, V]

WithArenaGrowthFactor configures the arena to grow by a factor of the previous chunk's size. For example, a factor of 2.0 means each new chunk will be twice as large as the last. This option is only effective when used with WithArena.

func WithArenaGrowthThreshold added in v1.2.1 

func WithArenaGrowthThreshold[K any, V any](threshold float64) Option[K, V]

WithArenaGrowthThreshold configures the arena's proactive growth threshold (e.g., 0.9 for 90%). If an allocation would cause a chunk's usage to exceed this threshold, the arena will grow preemptively. This option is only effective when used with WithArena.

type SkipList 

type SkipList[K any, V any] struct {
	// contains filtered or unexported fields
}

SkipList represents a thread-safe skiplist data structure. The zero value for a SkipList is not ready to use; one of the New functions must be called. SkipList คือโครงสร้างหลักของ skiplist ค่า zero value ของ SkipList จะยังไม่พร้อมใช้งาน, ต้องสร้างผ่านฟังก์ชัน New... เท่านั้น

func New 

func New[K cmp.Ordered, V any](opts ...Option[K, V]) *SkipList[K, V]

New creates a new skiplist for key types that implement cmp.Ordered (e.g., int, string). It uses cmp.Compare as the default comparator. New สร้าง skiplist ใหม่สำหรับ key type ที่รองรับ `cmp.Ordered` (เช่น int, string) โดยจะใช้ `cmp.Compare` เป็นฟังก์ชันเปรียบเทียบโดยอัตโนมัติ

func NewWithComparator 

func NewWithComparator[K any, V any](compare Comparator[K], opts ...Option[K, V]) *SkipList[K, V]

NewWithComparator creates a new skiplist with a custom comparator function. This is suitable for key types that do not implement cmp.Ordered or require special sorting logic. The comparator function must not be nil. NewWithComparator สร้าง skiplist ใหม่พร้อมกับฟังก์ชันเปรียบเทียบที่กำหนดเอง เหมาะสำหรับ key type ที่ไม่รองรับ `cmp.Ordered` หรือต้องการการเรียงลำดับแบบพิเศษ

func (*SkipList[K, V]) Clear added in v1.2.0 

func (sl *SkipList[K, V]) Clear()

Clear removes all items from the skiplist, resetting it to an empty state. It also replaces the internal node pool, allowing the garbage collector to reclaim memory from the old nodes. This is useful to free up memory after the skiplist is no longer needed, or before reusing it for a different dataset.

Clear ลบรายการทั้งหมดออกจาก skiplist และรีเซ็ตให้อยู่ในสถานะว่างเปล่า และยังทำการแทนที่ node pool ภายใน, ทำให้ garbage collector สามารถคืนหน่วยความจำ จากโหนดเก่าได้. มีประโยชน์ในการคืนหน่วยความจำหลังจากที่ skiplist ไม่ได้ใช้งานแล้ว หรือก่อนที่จะนำไปใช้กับข้อมูลชุดใหม่

func (*SkipList[K, V]) CountRange 

func (sl *SkipList[K, V]) CountRange(start, end K) int

CountRange นับจำนวนรายการที่ key อยู่ระหว่าง start และ end (รวมทั้งสองค่า) CountRange counts the number of items where the key is between start and end (inclusive).

func (*SkipList[K, V]) Delete 

func (sl *SkipList[K, V]) Delete(key K) bool

Delete ลบ key-value ออกจาก skiplist Delete removes a key-value pair from the skiplist. It returns true if the key was found and removed, otherwise false. คืนค่า true หากลบสำเร็จ, false หากไม่พบ key

func (*SkipList[K, V]) GetByRank added in v1.2.1 

func (sl *SkipList[K, V]) GetByRank(rank int) (INode[K, V], bool)

GetByRank returns the node at the given 0-based rank. If the rank is out of bounds (rank < 0 or rank >= sl.Len()), it returns nil and false. The complexity is O(log n). GetByRank คืนค่าโหนด ณ อันดับที่กำหนด (0-based) หากอันดับอยู่นอกขอบเขต (น้อยกว่า 0 หรือมากกว่าหรือเท่ากับ Len()) จะคืนค่า nil และ false มีความซับซ้อน O(log n)

func (*SkipList[K, V]) Insert 

func (sl *SkipList[K, V]) Insert(key K, value V) INode[K, V]

Insert เพิ่ม key-value คู่ใหม่เข้าไปใน skiplist Insert adds a new key-value pair to the skiplist. If the key already exists, its value is updated, and the old node is returned. If the key is new, a new node is inserted and nil is returned. หาก key มีอยู่แล้ว จะทำการอัปเดต value และคืนค่าโหนดเก่า หากเป็น key ใหม่ จะเพิ่มโหนดใหม่และคืนค่า nil

func (*SkipList[K, V]) Len 

func (sl *SkipList[K, V]) Len() int

Len คืนค่าจำนวนรายการทั้งหมดใน skiplist Len returns the total number of items in the skiplist.

func (*SkipList[K, V]) Max 

func (sl *SkipList[K, V]) Max() (INode[K, V], bool)

Max คืนค่า key-value คู่สุดท้าย (มากที่สุด) ใน skiplist Max returns the last (largest) key-value pair in the skiplist. It returns the nil for Node and false if the skiplist is empty. จะคืนค่า nil และ false หาก skiplist ว่างเปล่า

func (*SkipList[K, V]) Min 

func (sl *SkipList[K, V]) Min() (INode[K, V], bool)

Min คืนค่า key-value คู่แรก (น้อยที่สุด) ใน skiplist Min returns the first (smallest) key-value pair in the skiplist. It returns the node and true if the list is not empty, otherwise it returns nil and false. จะคืนค่าโหนดและ true หาก list ไม่ว่าง, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) NewIterator 

func (sl *SkipList[K, V]) NewIterator(opts ...IteratorOption[K, V]) *Iterator[K, V]

NewIterator creates a new iterator. By default, it's positioned before the first element and iterates forwards. Options can be provided to change this behavior. A call to Next() is required to advance to the first (or last, if reversed) element. NewIterator สร้างและคืนค่า Iterator ใหม่ โดยปกติจะชี้ไปยังตำแหน่งก่อนรายการแรก และวนลูปไปข้างหน้า สามารถใช้ options เพื่อเปลี่ยนพฤติกรรมนี้ได้ ต้องเรียก Next() เพื่อเลื่อนไปยังรายการแรก (หรือรายการสุดท้ายหากเป็นแบบย้อนกลับ)

func (*SkipList[K, V]) PopMax 

func (sl *SkipList[K, V]) PopMax() (INode[K, V], bool)

PopMax ดึง key-value คู่ที่มี key มากที่สุดออกจาก skiplist และลบโหนดนั้นออก PopMax removes and returns the largest key-value pair from the skiplist. It returns a node containing the popped data and true if an item was popped, otherwise it returns nil and false. คืนค่าโหนดที่เก็บข้อมูลที่ถูกดึงออกและ true หากมีรายการ, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) PopMin 

func (sl *SkipList[K, V]) PopMin() (INode[K, V], bool)

PopMin ดึง key-value คู่ที่มี key น้อยที่สุดออกจาก skiplist และลบโหนดนั้นออก PopMin removes and returns the smallest key-value pair from the skiplist. It returns a node containing the popped data and true if an item was popped, otherwise it returns nil and false. คืนค่าโหนดที่เก็บข้อมูลที่ถูกดึงออกและ true หากมีรายการ, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) Predecessor 

func (sl *SkipList[K, V]) Predecessor(key K) (INode[K, V], bool)

Predecessor ค้นหา key-value คู่ของโหนดที่อยู่ก่อนหน้า (predecessor) ของ key ที่กำหนด Predecessor finds the key-value pair of the node that precedes the given key. The predecessor is the node with the largest key that is smaller than the target key. It returns the node and true if found, otherwise it returns nil and false. Predecessor คือโหนดที่มี key มากที่สุดซึ่งน้อยกว่า key ที่กำหนด คืนค่าโหนดและ true หากพบ, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) Range 

func (sl *SkipList[K, V]) Range(f func(key K, value V) bool)

Range วนลูปไปตามรายการทั้งหมดใน skiplist ตามลำดับ key Range iterates over all items in the skiplist in ascending key order. The iteration stops if the provided function f returns false. และเรียกใช้ฟังก์ชัน f สำหรับแต่ละคู่ key-value การวนลูปจะหยุดลงหากฟังก์ชัน f คืนค่า false

func (*SkipList[K, V]) RangeQuery 

func (sl *SkipList[K, V]) RangeQuery(start, end K, f func(key K, value V) bool)

RangeQuery วนลูปไปตามรายการที่ key อยู่ระหว่าง start และ end (รวมทั้งสองค่า) RangeQuery iterates over items where the key is between start and end (inclusive). The iteration stops if the provided function f returns false. และเรียกใช้ฟังก์ชัน f สำหรับแต่ละคู่ key-value การวนลูปจะหยุดลงหากฟังก์ชัน f คืนค่า false

func (*SkipList[K, V]) RangeWithIterator added in v1.1.0 

func (sl *SkipList[K, V]) RangeWithIterator(f func(it *Iterator[K, V]))

RangeWithIterator provides a locked iterator to a callback function. This is more efficient than creating a new iterator and manually locking, as it acquires a single read lock for the entire duration of the callback's execution. The iterator provided to the callback is only valid within the scope of that callback.

RangeWithIterator ให้ Iterator ที่ถูก lock ไปยัง callback function ซึ่งมีประสิทธิภาพสูงกว่าการสร้าง Iterator แล้ว lock ด้วยตนเอง เพราะจะทำการ RLock เพียงครั้งเดียวตลอดการทำงานของ callback Iterator ที่ได้มาจะสามารถใช้งานได้ภายใน callback เท่านั้น

func (*SkipList[K, V]) Rank added in v1.2.1 

func (sl *SkipList[K, V]) Rank(key K) int

Rank returns the 0-based rank of the given key. The rank is the number of elements with keys strictly smaller than the given key. If the key is not in the list, it returns the rank it would have if it were inserted. The complexity is O(log n). Rank คืนค่าอันดับ (0-based) ของ key ที่กำหนด อันดับคือจำนวนรายการที่มี key น้อยกว่า key ที่ระบุ หากไม่พบ key จะคืนค่าอันดับที่ควรจะเป็นหากมีการเพิ่ม key นั้นเข้าไป มีความซับซ้อน O(log n)

func (*SkipList[K, V]) Search 

func (sl *SkipList[K, V]) Search(key K) (INode[K, V], bool)

Search ค้นหา value จาก key ที่กำหนด Search searches for a value by its key. It returns the node and true if the key is found, otherwise it returns nil and false. คืนค่าโหนดและ true หากพบ, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) Seek added in v1.2.0 

func (sl *SkipList[K, V]) Seek(key K) (INode[K, V], bool)

Seek finds the first node with a key greater than or equal to the given key. It returns the node and true if such a node is found, otherwise it returns nil and false. Seek ค้นหาโหนดแรกที่มี key เท่ากับหรือมากกว่า key ที่กำหนด คืนค่าโหนดและ true หากพบ, มิฉะนั้นคืนค่า nil และ false

func (*SkipList[K, V]) Successor 

func (sl *SkipList[K, V]) Successor(key K) (INode[K, V], bool)

Successor ค้นหา key-value คู่ของโหนดที่อยู่ถัดไป (successor) ของ key ที่กำหนด Successor finds the key-value pair of the node that succeeds the given key. The successor is the node with the smallest key that is larger than the given key. It returns the node and true if found, otherwise it returns nil and false. Successor คือโหนดที่มี key น้อยที่สุดที่มากกว่า key ที่กำหนด คืนค่าโหนดและ true หากพบ, มิฉะนั้นคืนค่า nil และ false

Source Files

View all Source files

Directories

Path Synopsis
cmd
profiler command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.