Class: RadixTree

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/radix_tree.rb

Overview

Naive implementation of Radix Tree for avoiding DoS via Algorithmic Complexity Attacks.

25 times slower for 10 bytes key, 100000 elements insertion 10 times slower for 10 bytes key, 100000 elements retrieval

TODO: Implement following methods for Hash compatibility.

  • hash

TODO: Implement following features for utilizing strength of Radix Tree.

  • delete_all by start string

Defined Under Namespace

Classes: Node

Constant Summary collapse

DEFAULT = 
Object.new

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(default = DEFAULT, &block) ⇒ RadixTree

Returns a new instance of RadixTree.



289
290
291
292
293
294
295
296
 
# File 'lib/radix_tree.rb', line 289

def initialize(default = DEFAULT, &block)
  if block && default != DEFAULT
    raise ArgumentError, 'wrong number of arguments'
  end
  @root = Node.new('', 0)
  @default = default
  @default_proc = block
end

Instance Attribute Details

#default ⇒ Object

Returns the value of attribute default.



286
287
288
 
# File 'lib/radix_tree.rb', line 286

def default
  @default
end

#default_proc ⇒ Object (readonly)

Returns the value of attribute default_proc.



287
288
289
 
# File 'lib/radix_tree.rb', line 287

def default_proc
  @default_proc
end

Instance Method Details

#==(oh) ⇒ Object 



499
500
501
502
503
504
505
 
# File 'lib/radix_tree.rb', line 499

def ==(oh)
  return false if self.size != oh.size
  self.each_key do |k|
    return false if self[k] != oh[k]
  end
  true
end

#[](key) ⇒ Object 



361
362
363
364
365
366
367
368
369
370
371
372
373
374
 
# File 'lib/radix_tree.rb', line 361

def [](key)
  value = @root.retrieve(key.to_s, 0)
  if value == Node::UNDEFINED
    if @default != DEFAULT
      @default
    elsif @default_proc
      @default_proc.call
    else
      nil
    end
  else
    value
  end
end

#[]=(key, value) ⇒ Object Also known as: store 



351
352
353
 
# File 'lib/radix_tree.rb', line 351

def []=(key, value)
  @root.store(key.to_s, 0, value)
end

#clear ⇒ Object 



347
348
349
 
# File 'lib/radix_tree.rb', line 347

def clear
  @root = Node.new('', 0)
end

#delete(key) ⇒ Object 



376
377
378
 
# File 'lib/radix_tree.rb', line 376

def delete(key)
  @root.delete(key.to_s, 0)
end

#delete_if(&block) ⇒ Object 



389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
 
# File 'lib/radix_tree.rb', line 389

def delete_if(&block)
  if block_given?
    temp = []
    @root.each do |key, value|
      if block.call key, value
          temp << key
      end
    end
    temp.each do |k|
      @root.delete(k, 0)
    end
    self
  else
    Enumerator.new(@root)
  end
end

#dump_tree(io = '') ⇒ Object 



380
381
382
383
 
# File 'lib/radix_tree.rb', line 380

def dump_tree(io = '')
  @root.dump_tree(io)
  io
end

#dup ⇒ Object Also known as: clone 



406
407
408
409
410
411
412
413
414
415
416
 
# File 'lib/radix_tree.rb', line 406

def dup
    if @default != DEFAULT then
      rt = RadixTree.new(@default)
    elsif @default_proc then
           rt = RadixTree.new(@default_proc.to_proc)
    else
      rt = RadixTree.new
    end
    rt.root = @root.dup
    rt
end

#each(&block) ⇒ Object Also known as: each_pair 



307
308
309
310
311
312
313
314
 
# File 'lib/radix_tree.rb', line 307

def each(&block)
  if block_given?
    @root.each(&block)
    self
  else
    Enumerator.new(@root)
  end
end

#each_key ⇒ Object 



317
318
319
320
321
322
323
324
325
326
 
# File 'lib/radix_tree.rb', line 317

def each_key
  if block_given?
    @root.each do |k, v|
      yield k
    end
    self
  else
    Enumerator.new(@root, :each_key)
  end
end

#each_value ⇒ Object 



328
329
330
331
332
333
334
335
336
337
 
# File 'lib/radix_tree.rb', line 328

def each_value
  if block_given?
    @root.each do |k, v|
      yield v
    end
    self
  else
    Enumerator.new(@root, :each_value)
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


298
299
300
 
# File 'lib/radix_tree.rb', line 298

def empty?
  @root.empty?
end

#eql?(oh) ⇒ Boolean

Returns:

  • (Boolean) 


507
508
509
510
511
512
513
 
# File 'lib/radix_tree.rb', line 507

def eql?(oh)
  return false if self.size != oh.size
  self.each_key do |k|
    return false unless self[k].eql?(oh[k])
  end
  true
end

#fetch(key, *args, &block) ⇒ Object 



448
449
450
451
452
453
454
455
456
457
458
459
460
 
# File 'lib/radix_tree.rb', line 448

def fetch(key, *args, &block)
  if args.size > 0 && block
    raise ArgumentError, 'wrong number of arguments'
  elsif self[key]
    self[key]
  elsif args.size == 1
    args[0]
  elsif block
    block.call key
  else
    raise KeyError, 'can\'t find the key'
  end
end

#find_all(prefix) ⇒ Object 



523
524
525
 
# File 'lib/radix_tree.rb', line 523

def find_all(prefix)
  @root.find_all(prefix, 0, false)
end

#find_predecessor(key) ⇒ Object 



515
516
517
 
# File 'lib/radix_tree.rb', line 515

def find_predecessor(key)
  @root.find_pre(key, 0, nil)
end

#find_successor(key) ⇒ Object 



519
520
521
 
# File 'lib/radix_tree.rb', line 519

def find_successor(key)
  @root.find_suc(key, 0, false)
end

#has_value?(value) ⇒ Boolean Also known as: value?

Returns:

  • (Boolean) 


491
492
493
494
495
496
 
# File 'lib/radix_tree.rb', line 491

def has_value?(value)
  self.each do |k,v|
    return true if value == v 
  end
  false
end

#key(value) ⇒ Object 



477
478
479
480
481
482
 
# File 'lib/radix_tree.rb', line 477

def key(value)
  self.each do |k,v|
    return k if v == value
    nil
  end
end

#key?(key) ⇒ Boolean Also known as: has_key?

Returns:

  • (Boolean) 


356
357
358
 
# File 'lib/radix_tree.rb', line 356

def key?(key)
  @root.retrieve(key.to_s, 0) != Node::UNDEFINED
end

#keys ⇒ Object 



339
340
341
 
# File 'lib/radix_tree.rb', line 339

def keys
  @root.keys
end

#reject(&block) ⇒ Object 



419
420
421
422
423
424
425
 
# File 'lib/radix_tree.rb', line 419

def reject(&block)
  if block_given?
    self.dup.delete_if(&block)
  else
    Enumerator.new(@root)
  end
end

#reject!(&block) ⇒ Object 



427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
 
# File 'lib/radix_tree.rb', line 427

def reject!(&block)
  if block_given?
    temp = []
    @root.each do |key, value|
      if block.call key, value
          temp << key
      end
    end
    if temp.empty?
      nil
    else
      temp.each do |k|
        @root.delete(k, 0)
      end
      self
    end
  else
    Enumerator.new(@root)
  end
end

#replace(h) ⇒ Object 



470
471
472
473
474
475
 
# File 'lib/radix_tree.rb', line 470

def replace(h)
  self.clear
  h.each do |k,v|
    self[k] = v
  end
end

#shift ⇒ Object 



484
485
486
487
488
489
 
# File 'lib/radix_tree.rb', line 484

def shift
  self.each do |k,v|
    self.delete(k)
    return [k, v]
  end
end

#size ⇒ Object Also known as: length 



302
303
304
 
# File 'lib/radix_tree.rb', line 302

def size
  @root.size
end

#to_hash ⇒ Object 



385
386
387
 
# File 'lib/radix_tree.rb', line 385

def to_hash
  inject({}) { |r, (k, v)| r[k] = v; r }
end

#values ⇒ Object 



343
344
345
 
# File 'lib/radix_tree.rb', line 343

def values
  @root.values
end

#values_at(*args) ⇒ Object 



462
463
464
465
466
467
468
 
# File 'lib/radix_tree.rb', line 462

def values_at(*args)
  vs = []
  args.each do |a|
    vs << self[a]
  end
  vs
end