Class: Mongoose::SkipList

Inherits:
Object show all
Defined in:
lib/mongoose/skiplist.rb

Overview

SkipList Class

Constant Summary collapse

MAX_LEVEL = 
31
OPTIMAL_PROBABILITY = 
0.25

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(col) ⇒ SkipList

initialize



15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/mongoose/skiplist.rb', line 15

def initialize(col)
  @col = col
  @size = 0

  # Create header and footer nodes.
  @footer = FooterNode.new
  @header = HeaderNode.new

  # Point all header.forward references to footer node.
  0.upto(MAX_LEVEL) { |i| @header.forward[i] = @footer }

  # This attribute will hold the actual level of the skip list.
  @level = 0
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



10
11
12
 
# File 'lib/mongoose/skiplist.rb', line 10

def size
  @size
end

Instance Method Details

#<(search_key) ⇒ Object

<



223
224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/mongoose/skiplist.rb', line 223

def <(search_key)
  result = []
  x = @header

  x = x.forward[0]

  while x != @footer and x.key < search_key
    result.concat(x.value)
    x = x.forward[0]
  end

  result
end

#<=(search_key) ⇒ Object

<=



240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/mongoose/skiplist.rb', line 240

def <=(search_key)
  result = []
  x = @header

  x = x.forward[0]

  while x != @footer and x.key <= search_key
    result.concat(x.value)
    x = x.forward[0]
  end

  result
end

#==(other) ⇒ Object 



169
170
171
 
# File 'lib/mongoose/skiplist.rb', line 169

def ==(other)
  search(other)
end

#>(search_key) ⇒ Object

>



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/mongoose/skiplist.rb', line 176

def >(search_key)
  result = []
  x = @header

  @level.downto(0) do |i|
    while x.forward[i].key < search_key
      x = x.forward[i]
    end
  end

  x = x.forward[0]
  x = x.forward[0] if x.key == search_key

  while x != @footer
    result.concat(x.value)
    x = x.forward[0]
  end

  result
end

#>=(search_key) ⇒ Object

>=



200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
 
# File 'lib/mongoose/skiplist.rb', line 200

def >=(search_key)
  result = []
  x = @header

  @level.downto(0) do |i|
    while x.forward[i].key < search_key
      x = x.forward[i]
    end
  end

  x = x.forward[0]

  while x != @footer
    result.concat(x.value)
    x = x.forward[0]
  end

  result
end

#[](search_key) ⇒ Object 



257
258
259
 
# File 'lib/mongoose/skiplist.rb', line 257

def [](search_key)
  search(search_key)
end

#between(search_start, search_end, start_inclusive = false, end_inclusive = false) ⇒ Object

between



264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
 
# File 'lib/mongoose/skiplist.rb', line 264

def between(search_start, search_end, start_inclusive=false, 
 end_inclusive=false)
  result = []
  x = @header

  @level.downto(0) do |i|
    while x.forward[i].key < search_start
      x = x.forward[i]
    end
  end

  x = x.forward[0]
  x = x.forward[0] if x.key == search_start and not start_inclusive

  while x != @footer and x.key < search_end
    result.concat(x.value)
    x = x.forward[0]
  end

  result = result.concat(x.value) if x.key == search_end and end_inclusive
  result
end

#dump ⇒ Object

dump



355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
 
# File 'lib/mongoose/skiplist.rb', line 355

def dump
  File.open(@col.index_file_name + '.dump', 'w') do |fptr|
    x = @header
    fptr.write("----------------  Header -----------------------------\n")
    x.forward.each_with_index do |f,i|
      fptr.write("**** Forward entry %d ****\n" % i)
      fptr.write("Key: " + f.key.inspect + "\n")
      fptr.write("Value: " + f.value.inspect + "\n") unless \
       f.is_a?(FooterNode)
    end
    fptr.write("----------------  End Header -------------------------\n")

    while not x.forward[0].is_a?(FooterNode)
      x = x.forward[0]
      fptr.write("---------------- Node -------------------------\n")
      fptr.write("Key: " + x.key.inspect + "\n") 
      fptr.write("Value: " + x.value.inspect + "\n")
      fptr.write("Level: " + x.lvl.inspect + "\n")
      x.forward.each_with_index do |f,i|
        fptr.write("**** Forward entry %d ****\n" % i)
        fptr.write("Key: " + f.key.inspect + "\n") 
        fptr.write("Value: " + f.value.inspect + "\n") unless \
         f.is_a?(FooterNode)
      end
      fptr.write("---------------- End Node ---------------------\n")
    end

    fptr.write("--------------------- Footer ---------------------\n")
    fptr.write(x.forward[0].inspect + "\n")
    fptr.write("--------------------- End Footer -----------------\n")
  end     
end

#dump_to_hash ⇒ Object

dump_to_hash



339
340
341
342
343
344
345
346
347
348
349
350
 
# File 'lib/mongoose/skiplist.rb', line 339

def dump_to_hash
  sl_hash = {}

  x = @header.forward[0]
      
  while x != @footer
    sl_hash[x.key] = [x.lvl, x.value]
    x = x.forward[0]
  end

  sl_hash
end

#each ⇒ Object

each



290
291
292
293
294
295
296
297
 
# File 'lib/mongoose/skiplist.rb', line 290

def each
  x = @header.forward[0]
      
  while x != @footer
    yield x.key, x.value
    x = x.forward[0]
  end
end

#load_from_hash(sl_hash) ⇒ Object

load_from_hash



302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
 
# File 'lib/mongoose/skiplist.rb', line 302

def load_from_hash(sl_hash)
  # Create array to hold last node that was at that level, while working
  # backwards.
  levels = []
  0.upto(MAX_LEVEL) { |i| levels << @footer }

  x = nil
  lvl = nil

  # Loop through keys in reverse order...
  sl_hash.keys.sort.reverse.each do |key|
    lvl, value = sl_hash[key]

    # Update skiplist level to be same as highest level yet found in keys.
    @level = lvl if lvl > @level

    # Create node with values from hash.
    x = Node.new(lvl, key, value)

    # Now, for each level of node, point its forward reference to the last
    # node that occupied that level (remember we are working backwards).
    0.upto(lvl) do |i|
      x.forward[i] = levels[i]
      # Now, we want to make current node the last node that occupied that
      # level.
      levels[i] = x
    end
      
    # Now, make sure that, for now, the header node points to this node, 
    # since it is the lowest node, at least until we read the next hash key.
    0.upto(lvl) { |i| @header.forward[i] = x }
  end    
end

#one_of(*other) ⇒ Object

one_of



158
159
160
161
162
163
164
 
# File 'lib/mongoose/skiplist.rb', line 158

def one_of(*other)
  result = []
  other.each do |o|
    result.concat(search(o))
  end
  return result
end

#remove(search_key, value) ⇒ Object

remove



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# File 'lib/mongoose/skiplist.rb', line 105

def remove(search_key, value)
  update = []

  x = @header

  @level.downto(0) do |i|
    while x.forward[i].key < search_key
      x = x.forward[i]
    end
    update[i] = x
  end

  x = x.forward[0]

  if x.key == search_key
    x.value.delete(value)

    if x.value.empty?
      0.upto(@level) do |i|
        break unless update[i].forward[i] == x
        update[i].forward[i] = x.forward[i]
      end

      while @level > 0 and @header.forward[@level] == @footer 
        @level -= 1
      end

      @size -= 1
    end
  end
end

#search(search_key) ⇒ Object

search



140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/mongoose/skiplist.rb', line 140

def search(search_key)
  result = []
  x = @header

  @level.downto(0) do |i|
    while x.forward[i].key < search_key
      x = x.forward[i]
    end
  end

  x = x.forward[0]

  return x.value if x.key == search_key
end

#store(search_key, new_value) ⇒ Object

store

++ If key not found, will insert new record, otherwise will update value of existing record.



37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
# File 'lib/mongoose/skiplist.rb', line 37

def store(search_key, new_value)
  # This array will be used to determine which records need their
  # forward array re-adjusted after a new node is created.
  update = []

  # Start off at the header node.
  x = @header

  # Starting at the current highest level of the skip list, walk from
  # left to right at that level, until you see that the next node's
  # key is greater than the key you are searching for.  When this
  # happend, you want to add the current node you are on to the list
  # of nodes that need to have their forward arrays updated.  Next,
  # you want to drop down a level on the current node and start
  # walking forward again, until you again see that the next node's
  # key is bigger than the search key.  In this way, you are walking
  # through the skip list, constantly moving to the right and moving
  # down, until you reach level 0 and are on the node whose key is
  # either equal to the search key (in which case an update will take
  # place), or the highest key in the list that is still lower than
  # the search key (in which case, you have found the place to do an
  # insert).
  @level.downto(0) do |i|
    while x.forward[i].key < search_key
      x = x.forward[i]
    end
    update[i] = x
  end

  x = x.forward[0]

  # If the search key was found, simply update the value of the node.
  if x.key == search_key
    x.value << new_value unless x.value.include?(new_value)
  # If this is an insert, determine the number of levels it will have
  # using a random number.  This is what keeps the skip list balanced.
  else
    lvl = random_level

    # If the new level is higher than the actual current level, we
    # need to make sure that the header node gets updated at these
    # levels.  Then, we set the actual current level equal to the
    # new level.
    if lvl > @level
      (@level + 1).upto(lvl) { |i| update[i] = @header }
      @level = lvl
    end

    # Create a new node.
    x = Node.new(lvl, search_key, [new_value])

    # Now, we need to update all of the nodes that will be affected
    # by the insertion of the new node.  These are nodes whose
    # forward array either will point to the new node and the new
    # node itself.
    0.upto(lvl) do |i|
      x.forward[i] = update[i].forward[i]
      update[i].forward[i] = x
    end
          
    # Increment the size attribute by one.
    @size += 1
  end
end