The cast<> operator is a "checked cast" operation. It - converts a pointer or reference from a base class to a derived cast, causing + converts a pointer or reference from a base class to a derived class, causing an assertion failure if it is not really an instance of the right type. This should be used in cases where you have some information that makes you believe that something is of the right type. An example of the isa<> @@ -2235,82 +2235,96 @@ insert entries into the symbol table.
User class provides a base for expressing the ownership of User towards other Values. The -Use helper class is employed to do the bookkeeping and facilitate O(1) +Use helper class is employed to do the bookkeeping and to facilitate O(1) addition and removal. -- ----------------------------------------------------------------- - --- Interaction and relationship between User and Use objects --- - ----------------------------------------------------------------- - + + -A subclass of User can choose between incorporating its Use objects ++-Initially each layout will possess a direct pointer to the -start of the array of Uses. Though not mandatory for layout a), ++A subclass of User can choose between incorporating its Use objects or refer to them out-of-line by means of a pointer. A mixed variant -(some Uses inline others hung off) is impractical and breaks the invariant -that the Use objects belonging to the same User form a contiguous array. - -We have 2 different layouts in the User (sub)classes: - -Layout a) -The Use object(s) are inside (resp. at fixed offset) of the User -object and there are a fixed number of them. - -Layout b) -The Use object(s) are referenced by a pointer to an -array from the User object and there may be a variable -number of them. +(some Uses inline others hung off) is impractical and breaks the invariant +that the Use objects belonging to the same User form a contiguous array. +
++We have 2 different layouts in the User (sub)classes: +
-
+
Layout a) +The Use object(s) are inside (resp. at fixed offset) of the User +object and there are a fixed number of them.
+ +Layout b) +The Use object(s) are referenced by a pointer to an +array from the User object and there may be a variable +number of them.
+
+As of v2.4 each layout still possesses a direct pointer to the +start of the array of Uses. Though not mandatory for layout a), we stick to this redundancy for the sake of simplicity. -The User object will also store the number of Use objects it +The User object also stores the number of Use objects it has. (Theoretically this information can also be calculated -given the scheme presented below.) - -Special forms of allocation operators (operator new) -will enforce the following memory layouts: - - -# Layout a) will be modelled by prepending the User object -# by the Use[] array. -# -# ...---.---.---.---.-------... -# | P | P | P | P | User -# '''---'---'---'---'-------''' - - -# Layout b) will be modelled by pointing at the Use[] array. -# -# .-------... -# | User -# '-------''' -# | -# v -# .---.---.---.---... -# | P | P | P | P | -# '---'---'---'---''' +given the scheme presented below.)
++Special forms of allocation operators (operator new) +enforce the following memory layouts:
- (In the above figures 'P' stands for the Use** that - is stored in each Use object in the member Use::Prev) +-
+
Layout a) is modelled by prepending the User object by the Use[] array.
++...---.---.---.---.-------... + | P | P | P | P | User +'''---'---'---'---'-------''' +
-Since the Use objects will be deprived of the direct pointer to -their User objects, there must be a fast and exact method to -recover it. This is accomplished by the following scheme: +Layout b) is modelled by pointing at the Use[] array.
++.-------... +| User +'-------''' + | + v + .---.---.---.---... + | P | P | P | P | + '---'---'---'---''' +
+
+Since the Use objects are deprived of the direct (back)pointer to +their User objects, there must be a fast and exact method to +recover it. This is accomplished by the following scheme:
+-
+
- 00 —> binary digit 0 +
- 01 —> binary digit 1 +
- 10 —> stop and calculate (s) +
- 11 —> full stop (S) +
+Given a Use*, all we have to do is to walk till we get +a stop and we either have a User immediately behind or we have to walk to the next stop picking up digits -and calculating the offset: - +and calculating the offset:
+
.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
@@ -2320,14 +2334,24 @@ and calculating the offset:
| | |______________________>
| |______________________________________>
|__________________________________________________________>
-
-
+
+Only the significant number of bits need to be stored between the -stops, so that the worst case is 20 memory accesses when there are -1000 Use objects. +stops, so that the worst case is 20 memory accesses when there are +1000 Use objects associated with a User.
+ + + -The following literate Haskell fragment demonstrates the concept: ++The following literate Haskell fragment demonstrates the concept:
+> import Test.QuickCheck > > digits :: Int -> [Char] -> [Char] @@ -2345,13 +2369,16 @@ The following literate Haskell fragment demonstrates the concept: > > test = takeLast 40 $ dist 20 [] > ++
+Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
++The reverse algorithm computes the length of the string just by examining +a certain prefix:
-Printing
> pref :: [Char] -> Int
> pref "S" = 1
> pref ('s':'1':rest) = decode 2 1 rest
@@ -2361,44 +2388,63 @@ a certain prefix:
> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
> decode walk acc _ = walk + acc
>
+
++Now, as expected, printing <pref test> gives 40.
++We can quickCheck this with following property:
-Now, as expected, printing> testcase = dist 2000 [] > testcaseLength = length testcase > > identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr > where arr = takeLast n testcase +> ++
+As expected <quickCheck identityProp> gives:
-As expected*Main> quickCheck identityProp OK, passed 100 tests. ++
+Let's be a bit more exhaustive:
-Let's be a bit more exhaustive: - +
>
> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
>
+
++And here is the result of <deepCheck identityProp>:
-And here is the result of*Main> deepCheck identityProp OK, passed 500 tests. ++ + -To maintain the invariant that the 2 LSBits of each Use** in Use -never change after being set up, setters of Use::Prev must re-tag the -new Use** on every modification. Accordingly getters must strip the -tag bits. - -For layout b) instead of the User we will find a pointer (User* with LSBit set). -Following this pointer brings us to the User. A portable trick will ensure -that the first bytes of User (if interpreted as a pointer) will never have -the LSBit set. - +
+To maintain the invariant that the 2 LSBits of each Use** in Use +never change after being set up, setters of Use::Prev must re-tag the +new Use** on every modification. Accordingly getters must strip the +tag bits.
++For layout b) instead of the User we find a pointer (User* with LSBit set). +Following this pointer brings us to the User. A portable trick ensures +that the first bytes of User (if interpreted as a pointer) never has +the LSBit set.
@@ -3365,7 +3411,7 @@ arguments. An argument has a pointer to the parent Function.