kernel/core/hash.rb

   1 # depends on: enumerable.rb misc.rb class.rb
   2
   3 class Hash
   4
   5   #--
   6   # The result of #hash is not allowed to be larger than this.
   7   #++
   8
   9   HASH_MAX = 0x1fffffff
  10
  11   include Enumerable
  12
  13   def self.[](*args)
  14     if args.first.kind_of? Hash and args.length == 1
  15       return new.replace(args.first)
  16     end
  17
  18     raise ArgumentError, "Expected an even number, got #{args.length}" if args.length % 2 == 1
  19
  20     hsh = new()
  21     while args.length >= 2
  22       k = args.shift
  23       v = args.shift
  24       hsh[k] = v
  25     end
  26     hsh
  27   end
  28
  29   def initialize(default = Undefined, &block)
  30     if !default.equal?(Undefined) and block
  31       raise ArgumentError, "Specify a default or a block, not both"
  32     end
  33
  34     if block
  35       @default = block
  36       @default_proc = true
  37     elsif !default.equal?(Undefined)
  38       @default = default
  39       @default_proc = false
  40     end
  41   end
  42   private :initialize
  43
  44   def initialize_copy(other)
  45     replace(other)
  46   end
  47   private :initialize_copy
  48
  49   def ==(other)
  50     return true if self.equal? other
  51     return false unless other.kind_of? Hash or other.respond_to? :to_hash
  52     other = Type.coerce_to(other, Hash, :to_hash)
  53     return false unless other.size == size
  54     # Pickaxe claims that defaults are compared, but MRI 1.8.[46] doesn't actually do that
  55     # return false unless other.default == default
  56     each_pair do |k, v|
  57       return false unless other[k] == self[k]
  58     end
  59     true
  60   end
  61
  62   ##
  63   # looks for a key in a bin found by hash_entry
  64
  65   def search_bin(entry,hash,key)
  66     while entry
  67       cur_hash, cur_key, cur_val, nxt = *entry
  68
  69       if cur_hash == hash and key.eql?(cur_key)
  70         return entry
  71       end
  72
  73       entry = nxt
  74     end
  75     return Undefined
  76   end
  77   private :search_bin
  78
  79   def fetch(key, default = Undefined)
  80     entry, hash, = hash_entry key
  81     entry = search_bin(entry,hash,key)
  82     return entry[2] if(entry != Undefined)
  83
  84     return yield(key) if block_given?
  85     return default if !default.equal?(Undefined)
  86     raise IndexError, 'Key not found'
  87   end
  88
  89   def get_key_cv(key)
  90     entry, hash, = hash_entry key
  91     entry = search_bin(entry,hash,key)
  92     return entry[2] if(entry != Undefined)
  93
  94     return default(key)
  95   end
  96
  97   def set_key_cv(key, val)
  98     key = key.dup if key.kind_of?(String)
  99
 100     redistribute
 101
 102     entry, hash, bin = hash_entry key
 103     lst = nil
 104
 105     while entry
 106       cur_hash, cur_key, cur_val, nxt = *entry
 107
 108       # Check if this entry is for the key in question
 109       if cur_hash == hash and key.eql?(cur_key)
 110         entry.put 2, val
 111         return val
 112       end
 113
 114       lst = entry
 115       entry = nxt
 116     end
 117
 118     entry = Tuple.new(4)
 119     entry.put 0, hash
 120     entry.put 1, key
 121     entry.put 2, val
 122     entry.put 3, nil
 123
 124     if lst
 125       lst.put 3, entry
 126     else
 127       @values.put bin, entry
 128     end
 129
 130     @entries += 1
 131     return val
 132   end
 133   alias_method :store, :set_key_cv
 134
 135   def self.after_loaded()
 136     alias_method :[],  :get_key_cv
 137     alias_method :[]=, :set_key_cv
 138   end
 139
 140   def clear()
 141     delete_if { true }
 142   end
 143
 144   def clone
 145     new_hash = dup
 146     new_hash.freeze if self.frozen?
 147     new_hash
 148   end
 149
 150   def default(key = Undefined)
 151     # current MRI documentation comment is wrong.  Actual behavior is:
 152     # Hash.new { 1 }.default #=> nil
 153     if @default_proc
 154       return key.equal?(Undefined) ? nil : @default.call(self, key)
 155     else
 156       return @default
 157     end
 158   end
 159
 160   def default=(val)
 161     @default_proc = false
 162     @default = val
 163   end
 164
 165   def default_proc()
 166     return @default if @default_proc
 167     nil
 168   end
 169
 170   def delete(key)
 171     entry, hash, bin = hash_entry key
 172     lst = nil
 173
 174     while entry
 175       cur_hash, cur_key, val, nxt = *entry
 176
 177       # Check if this entry is for the key in question
 178       if cur_hash == hash and key.eql?(cur_key)
 179
 180         # Ok, relink the other entries, leaving this one out.
 181         if lst
 182           lst.put 3, nxt
 183         else
 184           @values.put bin, nxt
 185         end
 186
 187         @entries = @entries - 1
 188
 189         return val
 190       end
 191
 192       lst = entry
 193       entry = nxt
 194     end
 195
 196     return yield(key) if block_given?
 197     nil
 198   end
 199
 200   def delete_if()
 201     raise LocalJumpError, "no block given" unless block_given? or empty?
 202
 203     # Do this in 2 steps, so we're not altering the structure while we walk it.
 204     # TODO: I'd like to write it like this:
 205     # select(&block).each { |k, v| delete k }
 206     to_del = []
 207     each_pair { |k, v| to_del << k if yield(k, v) }
 208     to_del.each { |k| delete k }
 209     self
 210   end
 211
 212   def dup
 213     new_hash = self.class.new
 214     new_hash.send :initialize_copy, self
 215     new_hash.taint if self.tainted?
 216     new_hash
 217   end
 218
 219   def each_key(&block)
 220     keys.each(&block)
 221     self
 222   end
 223
 224   def each
 225     raise LocalJumpError, "no block given" unless block_given? or empty?
 226
 227     @values.each do |tup|
 228       while tup
 229         yield([tup.at(1), tup.at(2)])
 230         tup = tup.at(3)
 231       end
 232     end
 233     self
 234   end
 235
 236   def each_pair
 237     raise LocalJumpError, "no block given" unless block_given? or empty?
 238
 239     @values.each do |tup|
 240       while tup
 241         yield(tup.at(1), tup.at(2))
 242         tup = tup.at(3)
 243       end
 244     end
 245     self
 246   end
 247
 248   def each_value(&block)
 249     values.each(&block)
 250     self
 251   end
 252
 253   def empty?()
 254     @entries == 0
 255   end
 256
 257   def index(val)
 258     each_pair { |k, v| return k if v == val }
 259     nil
 260   end
 261
 262   def inspect()
 263     # recursively_inspect
 264     return '{...}' if RecursionGuard.inspecting?(self)
 265
 266     out = []
 267     RecursionGuard.inspect(self) do
 268       each_pair do |key, val|
 269         str =  key.inspect
 270         str << '=>'
 271         str << val.inspect
 272         out << str
 273       end
 274     end
 275
 276     "{#{out.join ', '}}"
 277   end
 278
 279   def invert()
 280     out = {}
 281     each_pair { |k, v| out[v] = k }
 282     out
 283   end
 284
 285   def key?(key)
 286     entry, hash, = hash_entry key
 287
 288     while entry do # REFACTOR this loop is duplicated many times
 289       cur_hash, cur_key, cur_val, nxt = *entry
 290
 291       return true if cur_hash == hash and key.eql?(cur_key)
 292
 293       entry = nxt
 294     end
 295
 296     false
 297   end
 298
 299   alias_method :has_key?, :key?
 300   alias_method :include?, :key?
 301   alias_method :member?, :key?
 302
 303   def keys()
 304     out = []
 305     @values.each do |tup|
 306       while tup
 307         out << tup.at(1)
 308         tup = tup.at(3)
 309       end
 310     end
 311     out
 312   end
 313
 314   def merge(other, &block)
 315     dup.merge!(other, &block)
 316   end
 317
 318   def merge!(other)
 319     other = Type.coerce_to(other, Hash, :to_hash)
 320     other.each_pair do |k, v|
 321       if block_given? and self.key? k
 322         self[k] = yield(k, self[k], v)
 323       else
 324         self[k] = v
 325       end
 326     end
 327     self
 328   end
 329   alias_method :update, :merge!
 330
 331   # TODO: Improve the performance of this. NOTE, however
 332   # that #rehash is fundamentally impossible to do via a
 333   # primitive because classes (e.g. Array) can and do
 334   # redefine the #hash method. That method is not available
 335   # to primitive C code because we do not call back to Ruby
 336   def rehash
 337     out = {}
 338     each_pair { |k, v| out[k] = v }
 339     replace out
 340   end
 341
 342   def reject(&block)
 343     dup.delete_if(&block)
 344   end
 345
 346   def reject!(&block)
 347     old_size = size
 348     delete_if(&block)
 349     return nil if old_size == size
 350     self
 351   end
 352
 353   def replace(other)
 354     other = Type.coerce_to(other, Hash, :to_hash)
 355     return self if self.equal? other
 356     clear
 357     other.each_pair { |k, v| self[k] = v }
 358     if other.default_proc
 359       @default = other.default_proc
 360       @default_proc = true
 361     else
 362       @default = other.default
 363       @default_proc = false
 364     end
 365     self
 366   end
 367
 368   def select()
 369     raise LocalJumpError, "no block given" unless block_given? or empty?
 370
 371     out = []
 372     each_pair { |k, v| out << [k, v] if yield(k, v) }
 373     out
 374   end
 375
 376   def shift()
 377     return default(nil) if empty?
 378
 379     # TODO: keep around for efficiency?  It's not much faster though.
 380     # i = 0
 381     # tup = nil
 382     # while !tup
 383     #   tup = @values.at(i)
 384     #   i += 1
 385     # end
 386     # key = tup.at(1)
 387     # out = [key, self[key]]
 388     # delete(key)
 389     # out
 390
 391     key = keys.first
 392     out = [key, self[key]]
 393     delete key
 394     out
 395   end
 396
 397   def size()
 398     @entries
 399   end
 400   alias_method :length, :size
 401
 402   def sort(&block)
 403     to_a.sort(&block)
 404   end
 405
 406   def to_a()
 407     select { true }
 408   end
 409
 410   def to_hash()
 411     self
 412   end
 413
 414   def to_s()
 415     to_a.join
 416   end
 417
 418   def value?(val)
 419     values.include?(val)
 420   end
 421   alias_method :has_value?, :value?
 422
 423   def values()
 424     out = []
 425     @values.each do |tup|
 426       while tup
 427         out << tup.at(2)
 428         tup = tup.at(3)
 429       end
 430     end
 431     out
 432   end
 433
 434   def values_at(*args)
 435     args.collect { |key| self[key] }
 436   end
 437   alias_method :indexes, :values_at
 438   alias_method :indices, :values_at
 439
 440   def hash_entry(obj)
 441     hash = obj.hash
 442     hash = hash % HASH_MAX unless hash.kind_of? Fixnum
 443
 444     bin = hash & (@bins - 1)
 445
 446     entry = @values.at bin
 447
 448     return entry, hash, bin
 449   end
 450
 451 end