# Red-Black Tree Map
# Properties of a Red-Black tree map:
-# * every node is either red or black
-# * root is black
-# * every leaf (null) is black
-# * if a node is red, then both its children are black
-# * for each node, all simple path from the node to descendant
-# leaves contain the same number of black nodes
+# * every node is either red or black
+# * root is black
+# * every leaf (null) is black
+# * if a node is red, then both its children are black
+# * for each node, all simple path from the node to descendant
+# leaves contain the same number of black nodes
#
# Operations:
-# * search average O(lg n) worst O(lg n)
-# * insert average O(lg n) worst O(lg n)
-# * delete average O(lg n) worst O(lg n)
+# * search average O(lg n) worst O(lg n)
+# * insert average O(lg n) worst O(lg n)
+# * delete average O(lg n) worst O(lg n)
class RBTreeMap[K: Comparable, E]
super BinTreeMap[K, E]
# Two elements from a POSet cannot have the same color if they share common subelements
#
# Example:
+#
+# ~~~raw
# A
# / | \
# / | \
# E F G
# |
# H
+# ~~~
+#
# Conflicts:
-# A: {B, C, D, E, F, G, H}
-# B: {A, C, E, H}
-# C: {A, E, H, F}
-# D: {A, G}
-# E: {A, B, C, H}
-# F: {A, C}
-# G: {A, D}
-# H: {A, B, C, E}
+#
+# * A: {B, C, D, E, F, G, H}
+# * B: {A, C, E, H}
+# * C: {A, E, H, F}
+# * D: {A, G}
+# * E: {A, B, C, H}
+# * F: {A, C}
+# * G: {A, D}
+# * H: {A, B, C, E}
+#
# Possible colors:
-# A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
#
-# see:
-# Ducournau, R. (2011).
-# Coloring, a versatile technique for implementing object-oriented languages.
-# Software: Practice and Experience, 41(6), 627–659.
+# * A:0, B:1, C: 2, D: 1, E: 3, F:3, G:2, H:4
+#
+# see: Ducournau, R. (2011).
+# Coloring, a versatile technique for implementing object-oriented languages.
+# Software: Practice and Experience, 41(6), 627–659.
class POSetColorer[E: Object]
# Is the poset already colored?
# types to their bounds.
#
# Example
+ #
# class A end
# class B super A end
# class X end
# super G[B]
# redef type U: Y
# end
+ #
# Map[T,U] anchor_to H #-> Map[B,Y]
#
# Explanation of the example:
# class B[F]
# end
#
- # * E.can_resolve_for(A[Int]) #-> true, E make sense in A
- # * E.can_resolve_for(B[Int]) #-> false, E does not make sense in B
- # * B[E].can_resolve_for(A[F], B[Object]) #-> true,
- # B[E] is a red hearing only the E is important,
- # E make sense in A
+ # ~~~nitish
+ # E.can_resolve_for(A[Int]) #-> true, E make sense in A
+ #
+ # E.can_resolve_for(B[Int]) #-> false, E does not make sense in B
+ #
+ # B[E].can_resolve_for(A[F], B[Object]) #-> true,
+ # # B[E] is a red hearing only the E is important,
+ # # E make sense in A
+ # ~~~
#
# REQUIRE: `anchor != null implies not anchor.need_anchor`
# REQUIRE: `mtype.need_anchor implies anchor != null and mtype.can_resolve_for(anchor, null, mmodule)`
# directly to the parameter types of the super-classes.
#
# Example:
+#
# class A[E]
# fun e: E is abstract
# end
# class B[F]
# super A[Array[F]]
# end
+#
# In the class definition B[F], `F` is a valid type but `E` is not.
# However, `self.e` is a valid method call, and the signature of `e` is
# declared `e: E`.
end
# Return the attribute value in `instance` with a sequence of perfect_hashing
- # `instance` is the attributes array of the receiver
- # `vtable` is the pointer to the virtual table of the class (of the receiver)
- # `mask` is the perfect hashing mask of the class
- # `id` is the identifier of the class
- # `offset` is the relative offset of this attribute
+ # * `instance` is the attributes array of the receiver
+ # * `vtable` is the pointer to the virtual table of the class (of the receiver)
+ # * `mask` is the perfect hashing mask of the class
+ # * `id` is the identifier of the class
+ # * `offset` is the relative offset of this attribute
private fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{
// Perfect hashing position
int hv = mask & id;
end
# Replace the value of an attribute in an instance
- # `instance` is the attributes array of the receiver
- # `vtable` is the pointer to the virtual table of the class (of the receiver)
- # `mask` is the perfect hashing mask of the class
- # `id` is the identifier of the class
- # `offset` is the relative offset of this attribute
- # `value` is the new value for this attribute
+ # * `instance` is the attributes array of the receiver
+ # * `vtable` is the pointer to the virtual table of the class (of the receiver)
+ # * `mask` is the perfect hashing mask of the class
+ # * `id` is the identifier of the class
+ # * `offset` is the relative offset of this attribute
+ # * `value` is the new value for this attribute
private fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{
// Perfect hashing position
int hv = mask & id;
end
# Allocate a single vtable
- # `ids : Array of superclasses identifiers
- # `nb_methods : Array which contain the number of introduced methods for each class in ids
- # `nb_attributes : Array which contain the number of introduced attributes for each class in ids
- # `offset_attributes : Offset from the beginning of the table of the group of attributes
- # `offset_methods : Offset from the beginning of the table of the group of methods
+ # * `ids : Array of superclasses identifiers
+ # * `nb_methods : Array which contain the number of introduced methods for each class in ids
+ # * `nb_attributes : Array which contain the number of introduced attributes for each class in ids
+ # * `offset_attributes : Offset from the beginning of the table of the group of attributes
+ # * `offset_methods : Offset from the beginning of the table of the group of methods
private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int],
offset_attributes: Int, offset_methods: Int)
do
end
# Fill the vtable with methods of `self` class
- # `v` : Current instance of the VirtualMachine
- # `table` : the table of self class, will be filled with its methods
+ # * `v` : Current instance of the VirtualMachine
+ # * `table` : the table of self class, will be filled with its methods
private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass)
do
var methods = new Array[MMethodDef]
# Computes delta for each class
# A delta represents the offset for this group of attributes in the object
- # `nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
- # return deltas for each class
+ # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current)
+ # * return deltas for each class
private fun calculate_delta(nb_attributes: Array[Int]): Array[Int]
do
var deltas = new Array[Int]
end
# A kind of Depth-First-Search for superclasses ordering
- # `v` : the current executed instance of VirtualMachine
- # `res` : Result Array, ie current superclasses ordering
+ # *`v` : the current executed instance of VirtualMachine
+ # * `res` : Result Array, ie current superclasses ordering
private fun dfs(v: VirtualMachine, res: Array[MClass]): Array[MClass]
do
# Add this class at the beginning
end
# Update positions of self class in `parent`
- # `attributes_offset`: absolute offset of introduced attributes
- # `methods_offset`: absolute offset of introduced methods
+ # * `attributes_offset`: absolute offset of introduced attributes
+ # * `methods_offset`: absolute offset of introduced methods
private fun update_positions(attributes_offsets: Int, methods_offset:Int, parent: MClass)
do
parent.positions_attributes[self] = attributes_offsets
`}
# Put implementation of methods of a class in `vtable`
- # `vtable` : Pointer to the C-virtual table
- # `mask` : perfect-hashing mask of the class corresponding to the vtable
- # `id` : id of the target class
- # `methods` : array of MMethodDef of the target class
+ # * `vtable` : Pointer to the C-virtual table
+ # * `mask` : perfect-hashing mask of the class corresponding to the vtable
+ # * `id` : id of the target class
+ # * `methods` : array of MMethodDef of the target class
fun put_methods(vtable: Pointer, mask: Int, id: Int, methods: Array[MMethodDef])
import Array[MMethodDef].length, Array[MMethodDef].[] `{
nitlanguage / nit.git / commitdiff