Class: StrokeDB::Skiplist

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

Defined Under Namespace

Classes: HeadNode, Node, TailNode

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#each_consecutive_pair, #group_by, #map_with_index

Constructor Details

#initialize(data = {}, default = nil, cut_level = nil, unique_keys = true) ⇒ Skiplist

Returns a new instance of Skiplist.



7
8
9
10
11
12
13
14
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 7

def initialize(data = {}, default = nil, cut_level = nil, unique_keys = true)
	@default, @cut_level, @unique_keys = default, cut_level, unique_keys

	@head = HeadNode.new
	@tail = TailNode.new
	@head.forward[0] = @tail
	data.each{|k, v| insert(k, v) }
end

Instance Attribute Details

#cut_level ⇒ Object

Returns the value of attribute cut_level.



5
6
7
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 5

def cut_level
  @cut_level
end

#default ⇒ Object

Returns the value of attribute default.



5
6
7
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 5

def default
  @default
end

#head ⇒ Object

Returns the value of attribute head.



5
6
7
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 5

def head
  @head
end

#tail ⇒ Object

Returns the value of attribute tail.



5
6
7
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 5

def tail
  @tail
end

#unique_keys ⇒ Object

Returns the value of attribute unique_keys.



5
6
7
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 5

def unique_keys
  @unique_keys
end

Instance Method Details

#delete(key, default = nil) ⇒ Object 



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 108

def delete(key, default = nil)
  @size_cache = nil
  default ||= @default
  update = Array.new(@head.level)
  x = @head
 @head.level.downto(1) do |i|
   x = x.forward[i-1] while x.forward[i-1] < key
   update[i-1] = x
 end
 x = x.forward[0]
 if x.key == key
    @head.level.times do |i|
      break if update[i].forward[i] != x
      update[i].forward[i] = x.forward[i]
    end
    true while (y = @head.forward.pop) == @tail
    @head.forward.push(y || @tail)
    x.free(self)
    x.value
  else
    default
  end
end

#each ⇒ Object 



161
162
163
164
165
166
167
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 161

def each
  n = @head.forward[0]
  until n.is_a?(TailNode)
    yield n
    n = n.forward[0]
   end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


140
141
142
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 140

def empty?
  @head.forward[0] == @tail
end

#eql?(skiplist) ⇒ Boolean

Returns:

  • (Boolean) 


156
157
158
159
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 156

def eql?(skiplist)
  zip(skiplist) {|a, b| return false unless a.key == b.key && a.value == b.value }
  true
end

#find(key, default = nil) ⇒ Object 



75
76
77
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 75

def find(key, default = nil)
  (i = find_node(key)) && i.value || default || @default
end

#find_all_with_prefix(key) ⇒ Object 



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

def find_all_with_prefix(key)
  results = []
  x = @head
  @head.level.downto(1) do |i|
    x = x.forward[i-1] while x.forward[i-1] < key
  end
  x = x.forward[0]
  # got first 
  while x.key && x.key[0, key.size] == key 
    results << x.value
    x = x.forward[0]
  end
  results
end

#find_nearest(key, default = nil) ⇒ Object 



88
89
90
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 88

def find_nearest(key, default = nil)
  find_nearest_node(key).value || default || @default
end

#find_nearest_node(key) ⇒ Object 



79
80
81
82
83
84
85
86
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 79

def find_nearest_node(key)
  x = @head
  @head.level.downto(1) do |i|
   x = x.forward[i-1] while x.forward[i-1] < key
  end
  x = x.forward[0] if (x.forward[0].key == key || x == @head)
  x
end

#find_node(key = nil) ⇒ Object

Finders



64
65
66
67
68
69
70
71
72
73
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 64

def find_node(key = nil)
  x = @head
  @head.level.downto(1) do |i|
   x = x.forward[i-1] while x.forward[i-1] < key
 end
 x = x.forward[0]
 return (x.key && yield(x.key, key) ? x : nil) if block_given?
 return x if x.key == key
 nil
end

#first_node ⇒ Object 



132
133
134
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 132

def first_node
  @head.forward[0]
end

#insert(key, value, __cheaters_level = nil, __timestamp = nil) ⇒ Object 



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 16

def insert(key, value, __cheaters_level = nil, __timestamp = nil)
  @size_cache = nil
  update = Array.new(@head.level)
  x = @head
  # We have to choose between < and <= only,
  # but we go into different branches to keep things fast.  
  if @unique_keys
    @head.level.downto(1) do |i|
      x = x.forward[i-1] while x.forward[i-1] < key
      update[i-1] = x
    end
  else
    @head.level.downto(1) do |i|
      x = x.forward[i-1] while x.forward[i-1] <= key
      update[i-1] = x
    end
   end
  x = x.forward[0]
  if x.key == key && @unique_keys
    x.value = value
    x.timestamp = __timestamp
    value.skiplist_node_container = x if value.respond_to? :skiplist_node_container=
  else
    newlevel = __cheaters_level || random_level
    newlevel = 1 if empty?
    if newlevel > @head.level 
      (@head.level + 1).upto(newlevel) do |i|
        update[i-1] = @head
       end
     end
     
     x = Node.new(newlevel, key, value, __timestamp)
     value.skiplist_node_container = x if value.respond_to? :skiplist_node_container=
     
     if cut?(newlevel, update[0])
       return new_chunks!(x, update)
     else
       newlevel.times do |i|
         x.forward[i] = update[i].forward[i] || @tail
         update[i].forward[i] = x
       end
     end
   end
	return self
end

#raw_insert(data) ⇒ Object

Only for empty list!



170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 170

def raw_insert(data)
  n = @head
  sn = nil
  update = []
  data.each do |item|
    key, value, level, timestamp = yield(item)
    sn = Node.new(level, key, value, timestamp)
    level.times do |i| 
      update[i] ||= @head
      update[i].forward[i] = sn
      sn.forward[i] = @tail 
      update[i] = sn
    end
  end
end

#size ⇒ Object 



136
137
138
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 136

def size
	@size_cache ||= inject(0){|c,k| c + 1}
end

#to_s ⇒ Object

Returns a string representation of the Skiplist.



145
146
147
148
149
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 145

def to_s
	"#<#{self.class.name} " + 
	[@head.to_s, map{|node| node.to_s }, @tail.to_s].flatten.join(', ') +
	">"
end

#to_s_levels ⇒ Object 



150
151
152
153
154
 
# File 'lib/strokedb/data_structures/skiplist.rb', line 150

def to_s_levels
	"#<#{self.class.name}:levels " + 
	[@head.to_s, map{|node| node.level.to_s }, @tail.to_s].flatten.join(', ') +
	">"
end