From dfed118f22d319e8692ed59af4ea45990082e42f Mon Sep 17 00:00:00 2001 From: Gabor Greif Date: Wed, 18 Jun 2008 13:44:57 +0000 Subject: prettify, no semantic changes git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@52460 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/ProgrammersManual.html | 230 ++++++++++++++++++++++++++------------------ 1 file changed, 138 insertions(+), 92 deletions(-) (limited to 'docs/ProgrammersManual.html') diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index f0f941f584..2b9e6ca88b 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -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 ---
-   -----------------------------------------------------------------
-
+
+

+  Interaction and relationship between User and Use objects
+

 
-A subclass of User can choose between incorporating its Use objects
+

+

+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:
+

+

 Initially each layout will possess a direct pointer to the
-start of the array of Uses. Though not mandatory for layout a),
+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 will also store 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)
+will 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)
+
+(In the above figures 'P' stands for the Use** that
+    is stored in each Use object in the member Use::Prev)
 
-A bit-encoding in the 2 LSBits of the Use::Prev will allow to find the
-start of the User object:
+
+

+  The waymarking algorithm
+

 
-00 --> binary digit 0
-01 --> binary digit 1
-10 --> stop and calc (s)
-11 --> full stop (S)
+

+

+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:

+

 
-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
+A bit-encoding in the 2 LSBits (least significant bits) of the Use::Prev will allow to find the
+start of the User object:
+
+

+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.

+
+
+

+  Reference implementation
+

 
-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  gives: "1s100000s11010s10100s1111s1010s110s11s1S"
-
-The reverse algorithm computes the
-length of the string just by examining
-a certain prefix:
-
+

+
 > 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  gives 40.
-
-We can quickCheck this with following property:
-
+

+
 > 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  gives:
-
+
 *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.
+

 
+
+

+  Tagging considerations
+

 
-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 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.

-- cgit v1.2.3-18-g5258