Module: Weak::Map::StrongSecondaryKeys

Includes:
AbstractStrongKeys
Defined in:
lib/weak/map/strong_secondary_keys.rb

Overview

This Weak::Map strategy targets JRuby < 9.4.6.0.

These JRuby versions have a similar ObjectSpace::WeakMap as newer JRubies with strong keys and weak values. Thus, only the value object can be garbage collected to remove the entry while the key defines a strong object reference which prevents the key object from being garbage collected.

As we need to store both a key and value object for each key-value pair in our Weak::Map, we use two separate ObjectSpace::WeakMap objects for storing those. This allows keys and values to be independently garbage collected. When accessing a logical key in the Weak::Map, we need to manually check if we have a valid entry for both the stored key and the associated value.

Additionally, Integer values (including object_ids) can have multiple different object representations in JRuby, making them not strictly equal. Thus, we can not use the object_id as a key in an ObjectSpace::WeakMap as we do in StrongKeys for newer JRuby versions.

As a workaround we use a more indirect implementation with a secondary lookup table for the ObjectSpace::WeakMap keys which is inspired by Google::Protobuf::Internal::LegacyObjectCache

This secondary key map is a regular Hash which stores a mapping from the key's object_id to a separate Object which in turn is used as a key in the ObjectSpace::WeakMap for the stored keys and values.

Being a regular Hash, the keys and values of the secondary key map are not automatically garbage collected as elements in the ObjectSpace::WeakMap are removed. However, its entries are rather cheap with Integer keys and "empty" objects as values.

As this strategy is the most conservative with the fewest requirements to the ObjectSpace::WeakMap, we use it as a default or fallback if there is no better strategy.

Class Method Summary collapse

Instance Method Summary collapse

Methods included from AbstractStrongKeys

#keys, #size, #values

Class Method Details

.usable? ⇒ Bool

Checks if this strategy is usable for the current Ruby version.

Returns:

  • (Bool) —

    always true to indicate that this stragegy should be usable with any Ruby implementation which provides an ObjectSpace::WeakMap.

[View source]

59
60
61
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 59

def self.usable?
  true
end

Instance Method Details

#[](key) ⇒ Object

Note:

Set does not test member equality with == or eql?. Instead, it always checks strict object equality, so that, e.g., different strings are not considered equal, even if they may contain the same string content.

Returns the value associated with the given key, if found. If key is not found, returns the default value, i.e. the value returned by the default proc (if defined) or the default value (which is initially nil.).

Parameters:

  • key (Object) —

    the key for the requested value

Returns:

  • (Object) —

    the value associated with the given key, if found. If key is not found, returns the default value, i.e. the value returned by the default proc (if defined) or the default value (which is initially nil.)

[View source]

64
65
66
67
68
69
70
71
72
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 64

def [](key)
  id = @key_map[key.__id__]
  unless id
    auto_prune
    return _default(key)
  end

  _get(id) { _default(key) }
end

#[]=(key, value) ⇒ Object

Note:

Set does not test member equality with == or eql?. Instead, it always checks strict object equality, so that, e.g., different strings are not considered equal, even if they may contain the same string content.

Associates the given value with the given key; returns value. If the given key exists, replaces its value with the given value.

Parameters:

  • key (Object) —

    the key for the set key-value pair

  • value (Object) —

    the value of the set key-value pair

Returns:

  • (Object) —

    the given value

[View source]

75
76
77
78
79
80
81
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 75

def []=(key, value)
  id = @key_map[key.__id__] ||= Object.new.freeze

  @keys[id] = key.nil? ? NIL : key
  @values[id] = value.nil? ? NIL : value
  value
end

#clear ⇒ self

Removes all elements and returns self

Returns:

  • (self)
[View source]

84
85
86
87
88
89
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 84

def clear
  @keys = ObjectSpace::WeakMap.new
  @values = ObjectSpace::WeakMap.new
  @key_map = {}
  self
end

#delete(key) {|key| ... } ⇒ Object?

Note:

Set does not test member equality with == or eql?. Instead, it always checks strict object equality, so that, e.g., different strings are not considered equal, even if they may contain the same string content.

Deletes the key-value pair and returns the value from self whose key is equal to key. If the key is not found, it returns nil. If the optional block is given and the key is not found, pass in the key and return the result of the block.

Parameters:

  • key (Object) —

    the key to delete

Yields:

  • (key)

Yield Parameters:

  • key (Object) —

    the given key if it was not part of the map

Returns:

  • (Object, nil) —

    the value associated with the given key, or the result of the optional block if given the key was not found, or nil if the key was not found and no block was given.

[View source]

92
93
94
95
96
97
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 92

def delete(key)
  id = @key_map[key.__id__]
  return block_given? ? yield(key) : nil unless id

  _delete(id) { yield(key) if block_given? }
end

#each_key {|key| ... } ⇒ self, Enumerator

Calls the given block once for each live key in self, passing the key as a parameter. Returns the weak map itself.

If no block is given, an Enumerator is returned instead.

Yields:

  • (key) —

    calls the given block once for each key in self

Yield Parameters:

  • key (Object) —

    the key of the current key-value pair

Returns:

  • (self, Enumerator) —

    self if a block was given or an Enumerator if no block was given.

[View source]

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 100

def each_key
  return enum_for(__method__) { size } unless block_given?

  @keys.values.each do |raw_key|
    next if DeletedEntry === raw_key

    key = value!(raw_key)
    next unless (id = @key_map[key.__id__])
    if missing?(@values[id])
      @keys[id] = DeletedEntry.new
    else
      yield key
    end
  end

  self
end

#each_pair {|key, value| ... } ⇒ self, Enumerator

Calls the given block once for each live key in self, passing the key and value as parameters. Returns the weak map itself.

If no block is given, an Enumerator is returned instead.

Yields:

  • (key, value) —

    calls the given block once for each key in self

Yield Parameters:

  • key (Object) —

    the key of the current key-value pair

  • value (Object) —

    the value of the current key-value pair

Returns:

  • (self, Enumerator) —

    self if a block was given or an Enumerator if no block was given.

[View source]

119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 119

def each_pair
  return enum_for(__method__) { size } unless block_given?

  @keys.values.each do |raw_key|
    next if DeletedEntry === raw_key

    key = value!(raw_key)
    next unless (id = @key_map[key.__id__])

    raw_value = @values[id]
    if missing?(raw_value)
      @keys[id] = DeletedEntry.new
    else
      yield [key, value!(raw_value)]
    end
  end

  self
end

#each_value {|value| ... } ⇒ self, Enumerator

Calls the given block once for each live key self, passing the live value associated with the key as a parameter. Returns the weak map itself.

If no block is given, an Enumerator is returned instead.

Yields:

  • (value) —

    calls the given block once for each key in self

Yield Parameters:

  • value (Object) —

    the value of the current key-value pair

Returns:

  • (self, Enumerator) —

    self if a block was given or an Enumerator if no block was given.

[View source]

140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 140

def each_value
  return enum_for(__method__) { size } unless block_given?

  @keys.values.each do |raw_key|
    next if DeletedEntry === raw_key

    key = value!(raw_key)
    next unless (id = @key_map[key.__id__])

    raw_value = @values[id]
    if missing?(raw_value)
      @keys[id] = DeletedEntry.new
    else
      yield value!(raw_value)
    end
  end

  self
end

#fetch(key, default = UNDEFINED) {|key| ... } ⇒ Object

Note:

Set does not test member equality with == or eql?. Instead, it always checks strict object equality, so that, e.g., different strings are not considered equal, even if they may contain the same string content.

Returns a value from the hash for the given key. If the key can't be found, there are several options: With no other arguments, it will raise a KeyError exception; if default is given, then that value will be returned; if the optional code block is specified, then it will be called and its result returned.

Parameters:

  • key (Object) —

    the key for the requested value

  • default (Object) (defaults to: UNDEFINED) —

    a value to return if there is no value at key in the hash

Yields:

  • (key) —

    if no value was set at key, no default value was given, and a block was given, we call the block and return its value

Yield Parameters:

  • key (String) —

    the given key

Returns:

  • (Object) —

    the value for the given key if present in the map. If the key was not found, we return the default value or the value of the given block.

Raises:

  • (KeyError) —

    if the key can not be found and no block or default value was provided

[View source]

161
162
163
164
165
166
167
168
169
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 161

def fetch(key, default = UNDEFINED, &block)
  id = @key_map[key.__id__]
  unless id
    auto_prune
    return _fetch_default(key, default, &block)
  end

  _get(id) { _fetch_default(key, default, &block) }
end

#include?(key) ⇒ Bool

Note:

Set does not test member equality with == or eql?. Instead, it always checks strict object equality, so that, e.g., different strings are not considered equal, even if they may contain the same string content.

Returns true if the given key is included in self and has an associated live value, false otherwise.

Parameters:

  • key (Object) —

    a possible key

Returns:

  • (Bool) —

    true if the given key is included in self and has an associated live value, false otherwise

[View source]

172
173
174
175
176
177
178
179
180
181
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 172

def include?(key)
  id = @key_map[key.__id__]
  unless id
    auto_prune
    return false
  end

  _get(id) { return false }
  true
end

#prune ⇒ self

Cleanup data structures from the map to remove data associated with deleted or garbage collected keys and/or values. This method may be called automatically for some Weak::Map operations.

Returns:

  • (self)
[View source]

184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
 
# File 'lib/weak/map/strong_secondary_keys.rb', line 184

def prune
  orphaned_value_keys = ::Set.new(@values.keys)
  remaining_keys = ::Set.new

  @keys.keys.each do |id|
    if orphaned_value_keys.delete?(id)
      # Here, we have found a valid value belonging to the key. As both
      # key and value are valid, we keep the @key_map entry.
      remaining_keys << id
    else
      # Here, the value was missing (i.e. garbage collected). We mark the
      # still present key as deleted
      @keys[id] = DeletedEntry.new
    end
  end

  # Mark all (remaining) values as deleted for which we have not found a
  # matching key above
  orphaned_value_keys.each do |id|
    @values[id] = DeletedEntry.new
  end

  # Finally, remove all @key_map entries for which we have not seen a
  # valid key and value above
  @key_map.keep_if { |_, id| remaining_keys.include?(id) }

  self
end