53 lines
2.5 KiB
Markdown
53 lines
2.5 KiB
Markdown
# Implementation details
|
|
Under the hood, immutable tables are implemented in C as a userdata (that stores a hash value and length) with a metatable. That metatable has a weak-keyed mapping from hash -> userdata -> associated data. Immutable tables *are* garbage collected, so if you no longer have any references to the userdata, the userdata will get garbage collected, which will result in the entry being removed from the metatable's mapping. When new instances are created, a hash value is computed, and all the data in the associated hash bucket is scanned to look for duplicates. If a match is found, the existing instance is returned, otherwise a new one is created and added to the hash bucket. The following lua pseudocode approximates the C implementation's behavior:
|
|
```lua
|
|
local metamethods = {
|
|
__index = function(self, key)
|
|
local cls = getmetatable(self)
|
|
local values = cls.__instances[cls.__hash(self)][self]
|
|
if cls.__indices[key] then
|
|
return values[cls.__indices[key]]
|
|
elseif type(key) == 'number' and 1 <= key and key <= #values - #cls.__fields then
|
|
return values[key - #cls.__fields]
|
|
else
|
|
return cls[key]
|
|
end
|
|
end,
|
|
...also: __len, __pairs, __ipairs, __tostring, from_table, is_instance...
|
|
}
|
|
function immutable(fields, class_fields)
|
|
local cls = {}
|
|
for k,v in pairs(metamethods) do cls[k] = v end
|
|
cls.__super = metamethods
|
|
for k,v in pairs(class_fields) do cls[k] = v end
|
|
cls.__fields, cls.__indices = fields, {}
|
|
for i,f in ipairs(fields) do cls.__indices[f] = i end
|
|
cls.__instances = setmetatable({}, {__mode='v', __index=function(self, key)
|
|
local bucket = setmetatable({}, {__mode='k'})
|
|
self[key] = bucket
|
|
return bucket
|
|
end})
|
|
cls.__buckets = setmetatable({}, {__mode='k'})
|
|
return setmetatable(cls, {
|
|
__call=function(cls, ...)
|
|
local hash = calculate_hash(...)
|
|
local bucket = cls.__instances[hash]
|
|
for userdata, data in pairs(bucket) do
|
|
local match = true
|
|
for i=1,select('#',...) do
|
|
if data[i] ~= select(i, ...) then
|
|
match = false
|
|
break
|
|
end
|
|
end
|
|
if match then return userdata end
|
|
end
|
|
local userdata = setmetatable(new_userdata(hash), cls)
|
|
cls.__buckets[userdata] = bucket
|
|
bucket[userdata] = {...}
|
|
return userdata
|
|
end
|
|
})
|
|
end
|
|
```
|