Class: SkipList

Inherits:
Object
  • Object
show all
Defined in:
lib/skiplist.rb,
ext/skiplist/skiplist_mlink.c

Overview

Lock-Free Skip List

Authors

KISHIMOTO, Makoto

Version

0.0.2 2010-Aug-13

Copyright

Copyright © 2010 KISHIMOTO, Makoto

License

(other than loop.rb ) X License

References

  • The Art of Multiprocessor Programming, Chap. 14

Defined Under Namespace

Classes: MLink, Node

Constant Summary collapse

VERSION = 
'0.0.2'

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(level_max, cmp_op = :<=>, max_element = nil) ⇒ SkipList

Create a SkipList object.

level_max

If this list will have approximately N elements, you sholud set this log_2 N.



90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/skiplist.rb', line 90

def initialize level_max, cmp_op=:<=>, max_element=nil
	if level_max < 0 then
		raise ArgumentError.new "level_max must not be negative"
	end
	@level_max = level_max
	@cmp_op = cmp_op
	max = if max_element then max_element else SentinelElement::MAX end
	@tail = Node.new @level_max, max, nil
	(0).upto(@level_max){|i|
		@tail[i] = MLink.new nil
	}
	@head = Node.new @level_max, nil, nil
	(0).upto(@level_max){|i|
		@head[i] = MLink.new @tail
	}
	@randgen = Random.new
	@size_lock = Mutex.new
	@size = 0
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



83
84
85
 
# File 'lib/skiplist.rb', line 83

def size
  @size
end

Instance Method Details

#[](key) ⇒ Object

call-seq:

lst[key] -> value

Element reference. 

lst = SkipList.new 5
lst["foo"] = 1
lst["bar"] = 2
lst["baz"] = 3
lst["foo"]  #=> 1
lst["bar"]  #=> 2
lst["baz"]  #=> 3



280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
 
# File 'lib/skiplist.rb', line 280

def [] key
	pp = nil
	p = @head
	@level_max.downto(0){|level|
		pp = p[level].get_link  # ?
		loop {
			ppp, mark = pp[level].get
			while mark do
				#pp = ppp  # ?
				pp = pp[level].get_link
				ppp, mark = pp[level].get
			end
			if pp.key < key then
				p = pp
				pp = ppp
			else
				break
			end
		}
	}
	if pp.key == key then
		pp.val
	else
		nil
	end
end

#[]=(key, val) ⇒ Object

call-seq:

lst[key] = val -> val

Insert new node that key is key and value is val. If already exist the node with key == key, assign new val. This method returns val.

lst = SkipList.new 5
lst["foo"] = 1
lst["bar"] = 2
lst["baz"] = 3
lst.to_a  #=> [["bar", 2], ["baz", 3], ["foo", 1]]



234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/skiplist.rb', line 234

def []= key, val
	before_list = Array.new(@level_max + 1)
	after_list = Array.new(@level_max + 1)
	loop {
		if p = find(key, before_list, after_list) then
			p.val = val
			break
		end
		toplevel = rand2exp @level_max
		node = Node.new toplevel, key, val
		(0).upto(toplevel){|level|
			node[level] = MLink.new after_list[level]
		}
		unless before_list[0][0].compare_and_set after_list[0], node, false, false then
			next
		end
		@size_lock.synchronize {
			@size += 1
		}
		(1).upto(toplevel){|level|
			loop {
				if before_list[level][level].compare_and_set after_list[level], node, false, false then
					break
				end
				find key, before_list, after_list
			}
		}
		break
	}
	val
end

#delete(key) ⇒ Object

call-seq:

lst.delete[key] -> value

Element deletion. Returns a value of deleted element.

lst = SkipList.new 5
lst["foo"] = 1
lst["foo"]  #=> 1
lst.delete["foo"]  #=> 1
lst["foo"]  #=> nil
lst.delete["bar"]  #=> nil



320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
 
# File 'lib/skiplist.rb', line 320

def delete key
	before_list = Array.new(@level_max + 1)
	after_list = Array.new(@level_max + 1)
	unless p = find(key, before_list, after_list) then
		return nil
	end
	p.toplevel.downto(1){|level|
		pp, mark = p[level].get
		until mark do
			p[level].compare_and_set pp, pp, false, true
			pp, mark = p[level].get
		end
	}
	pp, mark = p[0].get
	loop {
		i_marked_it = p[0].compare_and_set pp, pp, false, true
		pp, mark = p[0].get
		if i_marked_it then
			@size_lock.synchronize {
				@size -= 1
			}
			#find key, before_list, after_list
			break p.val
		elsif mark then
			break nil
		end
	}
end

#empty? ⇒ Boolean

call-seq:

lst.empty? -> true or false

Returns true if lst contains no elements.

Returns:

  • (Boolean) 


147
148
149
150
151
152
153
154
155
 
# File 'lib/skiplist.rb', line 147

def empty?
	p = @head[0].get_link
	pp, m = p[0].get
	while m do
		p = pp
		pp, m = p[0].get
	end
	p.equal? @tail
end

#print_debug ⇒ Object

for debug use



111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/skiplist.rb', line 111

def print_debug
	puts "@level_max = #{@level_max}"
	puts "@cmp_op = #{@cmp_op}"
	puts "@randgen = #{@randgen}"
	puts "@size = #{@size}"
	puts ""
	puts "Nodes"
	puts ""
	p = @head
	while p do
		p.print_debug
		puts ""
		p = p[0].get_link
	end
end

#to_a ⇒ Object

call-seq:

lst.to_a -> array

Converts lst to a array of [ key, value ] arrays.

lst = SkipList.new 5
lst["foo"] = 1
lst["bar"] = 2
lst["baz"] = 3
lst.to_a  #=> [["bar", 2], ["baz", 3], ["foo", 1]]



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

def to_a
	arr = []
	p, m = @head[0].get
	while p do
		if not m then
			arr.push [p.key, p.val]
		end
		p, m = p[0].get
	end
	arr.pop
	arr
end