Class: StrokeDB::SimpleSkiplist

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/strokedb/data_structures/simple_skiplist.rb

Overview

Implements a thread-safe skiplist structure. Doesn’t yield new skiplists

Direct Known Subclasses

FixedLengthSkiplistVolume

Constant Summary collapse

DEFAULT_MAXLEVEL = 
32
DEFAULT_PROBABILITY = 
1/Math::E

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#each_consecutive_pair, #group_by, #map_with_index

Constructor Details

#initialize(raw_list = nil, options = {}) ⇒ SimpleSkiplist

Returns a new instance of SimpleSkiplist.



15
16
17
18
19
20
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 15

def initialize(raw_list = nil, options = {})
  @maxlevel    = options[:maxlevel]    || DEFAULT_MAXLEVEL
  @probability = options[:probability] || DEFAULT_PROBABILITY
  @head        = raw_list && unserialize_list!(raw_list) || new_head
  @mutex       = Mutex.new
end

Instance Attribute Details

#maxlevel ⇒ Object

Returns the value of attribute maxlevel.



13
14
15
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 13

def maxlevel
  @maxlevel
end

#probability ⇒ Object

Returns the value of attribute probability.



13
14
15
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 13

def probability
  @probability
end

Class Method Details

.from_a(ary, options = {}) ⇒ Object

Constructs a skiplist from an array of key-value tuples (arrays).



232
233
234
235
236
237
238
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 232

def self.from_a(ary, options = {})
  sl = new(nil, options)
  ary.each do |kv|
    sl.insert(kv[0], kv[1])
  end
  sl
end

.from_hash(hash, options = {}) ⇒ Object

Constructs a skiplist from a hash values.



226
227
228
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 226

def self.from_hash(hash, options = {})
  from_a(hash.to_a, options)
end

Instance Method Details

#each ⇒ Object

Iterates over skiplist kay-value pairs



218
219
220
221
222
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 218

def each
  each_node do |node|
    yield(node_key(node), node_value(node))
  end 
end

#each_node ⇒ Object

:nodoc:



207
208
209
210
211
212
213
214
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 207

def each_node #:nodoc:
  x = node_next(node_first, 0)
  while x 
    yield(x)
    x = node_next(x, 0)
  end
  self
end

#empty? ⇒ Boolean

Tests whether skiplist is empty.

Returns:

  • (Boolean) 


41
42
43
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 41

def empty?
  !node_next(@head, 0)
end

#find(key) ⇒ Object

Returns value, associated with key. nil if key is not found.



201
202
203
204
205
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 201

def find(key)
  x = find_nearest_node(key)
  return node_value(x) if node_compare(x, key) == 0
  nil # nothing found
end

#find_nearest(key) ⇒ Object

Finds a value with a nearest key to given key (from the left). For a set of keys [b, d, f], query “a” will return nil and query “c” will return a value under “b” key.



195
196
197
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 195

def find_nearest(key)
  node_value(find_nearest_node(key))
end

#find_nearest_node(key) ⇒ Object

Find is thread-safe and requires no mutexes locking.



93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 93

def find_nearest_node(key) #:nodoc:
  x = node_first
  level = node_level(x)
  while level > 0
    level -= 1
    xnext = node_next(x, level)
    while node_compare(xnext, key) <= 0
      x = xnext
      xnext = node_next(x, level)
    end
  end
  x
end

#find_with_update(x, level, key, update) ⇒ Object

:nodoc:



79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 79

def find_with_update(x, level, key, update) #:nodoc:
  while level > 0
     level -= 1
     xnext = node_next(x, level)
     while node_compare(xnext, key) < 0
       x = xnext
       xnext = node_next(x, level)
     end
     update[level] = x
   end
   xnext
end

#first_key ⇒ Object

First key of a non-empty skiplist (nil for empty one)



47
48
49
50
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 47

def first_key
  first = node_next(@head, 0)
  return first ? first[1] : nil
end

#insert(key, value, __level = nil) ⇒ Object

Insert a key-value pair. If key already exists, value will be overwritten.



55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 55

def insert(key, value, __level = nil)
   @mutex.synchronize do
     newlevel = __level || random_level
     x = node_first
     level = node_level(x)
     update = Array.new(level)
     x = find_with_update(x, level, key, update)
     
     # rewrite existing key
    if node_compare(x, key) == 0
      node_set_value!(x, value)
 	  # insert in a middle
 	  else
 	    level = newlevel
 	    newx = new_node(newlevel, key, value)
      while level > 0
        level -= 1
        node_insert_after!(newx, update[level], level)
       end
 	  end
   end
 	self
end

#marshal_dump ⇒ Object

Marshal API



23
24
25
26
27
28
29
30
31
32
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 23

def marshal_dump
  raw_list = serialize_list(@head)
  {
    :options => {
      :maxlevel    => @maxlevel,
      :probability => @probability
      },
    :raw_list => raw_list
  }
end

#marshal_load(dumped) ⇒ Object 



34
35
36
37
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 34

def marshal_load(dumped)
  initialize(dumped[:raw_list], dumped[:options])
  self
end

#to_a ⇒ Object

Converts skiplist to an array of key-value pairs.



242
243
244
245
246
247
 
# File 'lib/strokedb/data_structures/simple_skiplist.rb', line 242

def to_a
  inject([]) do |arr, pair|
    arr << pair
    arr
  end
end