init(class_coloring: ClassColoring) do end
end
+class NaiveVTColoring
+ super VTColoring
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MPROP, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ var min_color = 0
+
+ for mclass in mclasses do
+ min_color = max_color(min_color, mclasses)
+ colorize_elements(self.properties(mclass), min_color)
+ end
+ return self.coloration_result
+ end
+end
+
+abstract class VTPerfectHashing
+ super VTColoring
+
+ private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MPROP, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ for mclass in mclasses do
+ var vts = self.properties(mclass)
+ for vt in vts do
+ if coloration_result.has_key(vt) then continue
+ coloration_result[vt] = coloration_result.length + 1
+ end
+ end
+ return self.coloration_result
+ end
+
+ fun compute_masks: Map[MClass, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ for mclass in mclasses do
+ self.masks[mclass] = compute_mask(self.properties(mclass))
+ end
+ return self.masks
+ end
+
+ private fun compute_mask(vts: Set[MPROP]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for vt in vts do
+ var res = op(mask, self.coloration_result[vt])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == vts.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ redef fun build_property_tables do
+ var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
+
+ for mclass in self.class_coloring.coloration_result.keys do
+ var table = new Array[nullable MPROPDEF]
+ # first, fill table from parents by reverse linearization order
+ var parents = new OrderedSet[MClass]
+ parents.add_all(self.class_coloring.super_elements(mclass))
+ self.class_coloring.reverse_sorter.sort(parents)
+ for parent in parents do
+ for mproperty in self.properties(parent) do
+ var color = phash(self.coloration_result[mproperty], masks[mclass])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ for mpropdef in mproperty.mpropdefs do
+ if mpropdef.mclassdef.mclass == parent then
+ table[color] = mpropdef
+ end
+ end
+ end
+ end
+
+ # then override with local properties
+ for mproperty in self.properties(mclass) do
+ var color = phash(self.coloration_result[mproperty], masks[mclass])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ for mpropdef in mproperty.mpropdefs do
+ if mpropdef.mclassdef.mclass == mclass then
+ table[color] = mpropdef
+ end
+ end
+ end
+ tables[mclass] = table
+ end
+ return tables
+ end
+
+ private fun op(mask: Int, id:Int): Int is abstract
+ private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+
+end
+
+class VTModPerfectHashing
+ super VTPerfectHashing
+ init(class_coloring: ClassColoring) do end
+ redef fun op(mask, id) do return mask % id
+end
+
+class VTAndPerfectHashing
+ super VTPerfectHashing
+ init(class_coloring: ClassColoring) do end
+ redef fun op(mask, id) do return mask.bin_and(id)
+end
+
# MParameterType coloring
class FTColoring
private var class_coloring: ClassColoring
end
end
+class NaiveFTColoring
+ super FTColoring
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MParameterType, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ var min_color = 0
+
+ for mclass in mclasses do
+ min_color = max_color(min_color, mclasses)
+ colorize_elements(self.fts(mclass), min_color)
+ end
+ return self.coloration_result
+ end
+end
+
+abstract class FTPerfectHashing
+ super FTColoring
+
+ private var masks: Map[MClass, Int] = new HashMap[MClass, Int]
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MParameterType, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ for mclass in mclasses do
+ for ft in self.fts(mclass) do
+ if coloration_result.has_key(ft) then continue
+ coloration_result[ft] = coloration_result.length + 1
+ end
+ end
+ return self.coloration_result
+ end
+
+ fun compute_masks: Map[MClass, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ for mclass in mclasses do
+ var fts = new HashSet[MParameterType]
+ for parent in self.class_coloring.super_elements(mclass) do
+ fts.add_all(self.fts(parent))
+ end
+ fts.add_all(self.fts(mclass))
+ self.masks[mclass] = compute_mask(fts)
+ end
+ return self.masks
+ end
+
+ private fun compute_mask(fts: Set[MParameterType]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for ft in fts do
+ var res = op(mask, self.coloration_result[ft])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == fts.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ redef fun build_ft_tables do
+ var tables = new HashMap[MClass, Array[nullable MParameterType]]
+
+ for mclass in self.class_coloring.coloration_result.keys do
+ var table = new Array[nullable MParameterType]
+
+ # first, fill table from parents
+ for parent in self.class_coloring.super_elements(mclass) do
+ for ft in self.fts(parent) do
+ var color = phash(self.coloration_result[ft], masks[mclass])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = ft
+ end
+ end
+
+ # then override with local properties
+ for ft in self.fts(mclass) do
+ var color = phash(self.coloration_result[ft], masks[mclass])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = ft
+ end
+ tables[mclass] = table
+ end
+ return tables
+ end
+
+ private fun op(mask: Int, id:Int): Int is abstract
+ private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+end
+
+class FTModPerfectHashing
+ super FTPerfectHashing
+ init(class_coloring: ClassColoring) do end
+ redef fun op(mask, id) do return mask % id
+end
+
+class FTAndPerfectHashing
+ super FTPerfectHashing
+ init(class_coloring: ClassColoring) do end
+ redef fun op(mask, id) do return mask.bin_and(id)
+end
+
# Live Entries coloring
class LiveEntryColoring
private fun add_conflict(mtype: MType, otype: MType) do
if mtype == otype then return
- if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MClassType]
+ if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MType]
self.conflicts_graph_cache[mtype].add(otype)
- if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MClassType]
+ if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MType]
self.conflicts_graph_cache[otype].add(mtype)
end
private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
end
+class NaiveLiveEntryColoring
+ super LiveEntryColoring
+
+ init do end
+
+ redef fun colorize_elements(elements: Collection[MType]) do
+ var color = 0
+ for element in elements do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+end
+
+# live unanchored coloring
+class UnanchoredTypeColoring
+
+ private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
+ private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]
+
+ init do end
+
+ fun colorize(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ build_conflicts_graph(elements)
+ colorize_elements(elements)
+ return coloration_result
+ end
+
+ fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
+ var tables = new HashMap[MClassType, Array[nullable MType]]
+
+ for mclasstype, mtypes in elements do
+ var table = new Array[nullable MType]
+ for mtype in mtypes do
+ var color = self.coloration_result[mtype]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = mtype
+ end
+ tables[mclasstype] = table
+ end
+ return tables
+ end
+
+ # Colorize a collection of elements
+ fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var min_color = 0
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ if self.coloration_result.has_key(element) then continue
+ var color = min_color
+ while not self.is_color_free(element, color) do
+ color += 1
+ end
+ coloration_result[element] = color
+ color = min_color
+ end
+ end
+ end
+
+ # Check if a related element to the element already use the color
+ private fun is_color_free(element: MType, color: Int): Bool do
+ if conflicts_graph.has_key(element) then
+ for st in conflicts_graph[element] do
+ if coloration_result.has_key(st) and coloration_result[st] == color then return false
+ end
+ end
+ return true
+ end
+
+ # look for unanchored types generated by the same type
+ private fun build_conflicts_graph(elements: Map[MClassType, Set[MType]]) do
+ for mclasstype, mtypes in elements do
+ for mtype in mtypes do
+ for otype in mtypes do
+ if otype == mtype then continue
+ self.add_conflict(mtype, otype)
+ end
+ end
+ end
+ end
+
+ private fun add_conflict(mtype: MType, otype: MType) do
+ if mtype == otype then return
+ if not self.conflicts_graph.has_key(mtype) then self.conflicts_graph[mtype] = new HashSet[MType]
+ self.conflicts_graph[mtype].add(otype)
+ if not self.conflicts_graph.has_key(otype) then self.conflicts_graph[otype] = new HashSet[MType]
+ self.conflicts_graph[otype].add(mtype)
+ end
+end
+
+class NaiveUnanchoredTypeColoring
+ super UnanchoredTypeColoring
+
+ init do end
+
+ redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var color = 0
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+ end
+end
+
+abstract class UnanchoredTypePerfectHashing
+ super NaiveUnanchoredTypeColoring
+
+ private var masks: Map[MClassType, Int] = new HashMap[MClassType, Int]
+
+ init do end
+
+ redef fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ var color = 1
+ for mclasstype, mclasstypes in elements do
+ for element in mclasstypes do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+ end
+
+ fun compute_masks(elements: Map[MClassType, Set[MType]]): Map[MClassType, Int] do
+ for mclasstype, mtypes in elements do
+ self.masks[mclasstype] = compute_mask(mtypes)
+ end
+ return self.masks
+ end
+
+ private fun compute_mask(mtypes: Set[MType]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for mtype in mtypes do
+ var res = op(mask, self.coloration_result[mtype])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == mtypes.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ redef fun build_tables(elements: Map[MClassType, Set[MType]]): Map[MClassType, Array[nullable MType]] do
+ var tables = new HashMap[MClassType, Array[nullable MType]]
+
+ for mclasstype, mtypes in elements do
+ var table = new Array[nullable MType]
+ for mtype in mtypes do
+ var color = phash(self.coloration_result[mtype], masks[mclasstype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = mtype
+ end
+ tables[mclasstype] = table
+ end
+ return tables
+ end
+
+ private fun op(mask: Int, id:Int): Int is abstract
+ private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+end
+
+class UnanchoredTypeModPerfectHashing
+ super UnanchoredTypePerfectHashing
+ init do end
+ redef fun op(mask, id) do return mask % id
+end
+
+class UnanchoredTypeAndPerfectHashing
+ super UnanchoredTypePerfectHashing
+ init do end
+ redef fun op(mask, id) do return mask.bin_and(id)
+end
+
+
# Utils
# An ordered set
-class OrderedSet[E]
+class OrderedSet[E: Object]
super Array[E]
init do end
fun linearize(sorter: AbstractSorter[E]) do
sorter.sort(self)
end
-end
\ No newline at end of file
+end
nitlanguage / nit.git / blobdiff