You are here: Foswiki>System Web>ReferenceManual>DeveloperDocumentationCategory>PerlDoc (19 Apr 2011, ProjectContributor)EditAttach

`internal package`

Foswiki::Prefs::Stack On this page:

- UNPUBLISHED package Foswiki::Prefs::Stack
- ClassMethod new( $session )
- ObjectMethod finish()
- ObjectMethod size() → $size
- ObjectMethod backAtLevel($level) → $back
- ObjectMethod finalizedBefore($pref, $level) → $boolean
- ObjectMethod finalized($pref) → $boolean
- ObjectMethod prefs() → @prefs
- ObjectMethod prefIsDefined($pref) → $boolean
- ObjectMethod insert($type, $pref, $value) → $num
- ObjectMethod newLevel($back, $prefix)
- ObjectMethod getDefinitionLevel($pref) → $level
- ObjectMethod getPreference($pref [, $level] ) → $value
- ObjectMethod clone($level ) → $stack
- ObjectMethod restore($level)

- Mathematical Considerations
- Other Considerations

- Preferences pushed later have precedence over ones pushed earlier I must
- be able to return (restore) to a state I was earlier

- A bitstring map. Each preference has a bitmap. Each bit corresponds to a level. The bit is 1 if the preference is defined at that level and 0 otherwise. If a preference is "defined" in some level, but it was finalized, then the corresponding bit is 0.
- A level list storing a backend object that is associated with each level
- A final hash that maps preferences to the level they were finalized.

`Foswiki::Prefs`

`ClassMethod`

new( $session ) `ObjectMethod`

finish() `ObjectMethod`

size() → $size `ObjectMethod`

backAtLevel($level) → $back `ObjectMethod`

finalizedBefore($pref, $level) → $boolean `ObjectMethod`

finalized($pref) → $boolean `ObjectMethod`

prefs() → @prefs `ObjectMethod`

prefIsDefined($pref) → $boolean `ObjectMethod`

insert($type, $pref, $value) → $num `ObjectMethod`

newLevel($back, $prefix) `ObjectMethod`

getDefinitionLevel($pref) → $level `ObjectMethod`

getPreference($pref [, $level] ) → $value `ObjectMethod`

clone($level ) → $stack `ObjectMethod`

restore($level) - It has the minimal possible length. (I)
- If it exists in the hash, it has at least length 1. (II)

`ord`

converts a
character to an integer between 0 and 255. If the character of a preference is
0, then the preference doesn't exist in the map hash, cause of the second
listed property above.
This implies that I can `ord($map)`

. (III)
The question is:
`log2(X)`

means log2(1) = 0; 1 == 1 * 2 ** 0; 1 in base 2 is "00000001" (considering one byte) log2(2) = 1; 2 == 1 * 2 ** 1; 2 in base 2 is "00000010" (considering one byte) log2(4) = 2; 4 == 1 * 2 ** 2; 4 in base 2 is "00000100" (considering one byte) log2(8) = 3; 8 == 1 * 2 ** 3; 8 in base 2 is "00001000" (considering one byte)Also notice that:

2 ** B <= X < 2 ** (B + 1) implies B <= log2(X) < (B + 1)This implies:

int(log2(X)) == B, for any X in the above rage.Some examples:

int(log2(3)) = log2(2) = 1; 3 in base 2 is "00000011" (considering one byte) int(log2(5)) = log2(4) = 2; 5 in base 2 is "00000101" (considering one byte) int(log2(6)) = log2(4) = 2; 6 in base 2 is "00000110" (considering one byte) int(log2(7)) = log2(4) = 2; 7 in base 2 is "00000111" (considering one byte) int(log2(9)) = log2(8) = 3; 9 in base 2 is "00001001" (considering one byte)The position of least significant bit is 0 and the position of the most significant bit is 8, then:

`int(log2(X))`

is the position of the
highest-significant bit equal to 1. This always holds. The complete
mathematical proof is left as an exercise.
Back to the question `int(log2(X))`

.
`X`

is the number corresponding to the bitstring character, so X = `ord($map)`

.
Also,
log2(Y) == ln(Y)/ln(2), for any Y real positiveThen we have:

int(log2(X)) == int( ln( ord($map) ) / ln(2) )

$defLevel = int( ln( ord($map) ) / ln(2) );

`vec`

works:
$a = ''; vec($a, 0, 1) = 1; print unpack("b*", $a); # "10000000" vec($a, 2, 1) = 1; print unpack("b*", $a); # "10100000" vec($a, 7, 1) = 1; print unpack("b*", $a); # "10100001" vec($a, 16, 1) = 1; print unpack("b*", $a); # "1010000100000000100000000"The least significant bit is the bit 0 of the first byte. The most significant bit is the bit 7 of the last byte.

`unpack`

with `"b*"`

gives us this
representation, that is different from the one we're used to, but it's only a
representation. Test for yourself:
$a = ''; vec($a, 0, 1) = 1; print ord($a); # 1 vec($a, 2, 1) = 1; print ord($a); # 5 vec($a, 7, 1) = 1; print ord($a); # 133Since

`ord()`

operates with one character (or with the first one, if
`length($a) > 1`

), we have to figure out a way to deal with preferences bigger
than 8 levels.
The level to consider in order to get a preference value is the highest in
which it was defined. Because of properties (I) and (II) above, this level is
in the last byte of the bitmap. This implies that no matter the value of the
other bytes are, I need to consider only the last byte. (IV)
Since (IV) holds, we can reduce the general case to the restricted case as
follows: we calculate the level considering the last byte. We'll get `$L`

in
`[0,7]`

. Then we transform this value to the correct, considering that the bit
0 of the last byte is the bit `(N - 1) * 8`

of the general string, where `N`

is
the total number of bytes. Examples:
1 byte: bit 0 of the last byte is bit (1 - 1) * 8 == 0 of the string 2 bytes: bit 0 of the last byte is bit (2 - 1) * 8 == 8 of the string 3 bytes: bit 0 of the last byte is bit (3 - 1) * 8 == 16 of the stringand so on. So, considering the general case where

`$map`

has arbitrary length, the
$defLevel = int( log( ord( substr($map, -1) ) ) / ln(2) ) + (length($map) - 1) * 8;

`substr($map, -1)`

is `log( ord( substr($map,-1) ) )`

exists. Because of (II),
`length($map)`

is at least 1. So this general expression is `$stack->{map}`

is an empty hashref, so both (I) and (II) holds.
The addition of a preference uses `vec()`

, that expands the string as (and only
as) needed, so (I) holds. And if the preference is being added, then it must
exist in preferences map, so (II) also holds.
The restore operation is more complex: if we're restoring to level L, this
means that all bits above level L must be 0. I can accomplish this using
bitwise AND (&):
Considering at most 8 bytes, let's assume we want to restore to the level 5.
Notice that:
2 ** (5 + 1) == 64 == "01000000" 64 - 1 == 63 == "00111111"Bits 0-5 are 1 and all others are 0. And Since:

(1 & X) == X (0 & X) == 0we can build a mask using this process and apply it to the map and we'll get the bitmap restored to the desired level. So, in order to restore to level

`$L`

we build a mask as `((2 ** (L+1)) - 1)`

and perform:
$map &= $mask;If the result is 0, we need to remove that preference from the hash, so both (I) and (II) holds.

`$L`

, we need
to build a mask whose bits 0-L are 1. This mask will have `int($L/8) + 1`

bytes.
0 <= $L < 8 implies the mask 1-byte long. 8 <= $L < 16 implies the mask 2-bytes long. 16 <= $L < 24 implies the mask 3-bytes long.and so on. We conclude that all bytes of the mask, except the last, will be

`\xFF`

(all bits 1). If we map `$L`

to [0,7], then we have the restricted case
above.
The number of bytes except the last in the bitstring is `int($L/8)`

. The bit
position of `$L`

in the last byte is `($L % 8)`

:
Level 8 corresponds to bit 0 of the second byte. int(8/8) = 1. 8 % 8 = 0. Level 9 corresponds to bit 1 of the second byte. int(9/8) = 1. 9 % 8 = 1. Level 15 corresponds to bit 7 of the second byte. int(15/8) = 1. 15 % 8 = 7. Level 16 corresponds to bit 0 of the third byte. int(16/8) = 2. 16 % 8 = 0.So the general way to build the mask is:

$mask = ("\xFF" x int($L/8)); # All bytes except the last have all bits 1. $mask .= chr( ( 2**( ( $L % 8 ) + 1 ) ) - 1 ); # The last byte is built based # on the restricted case above.The

`$mask`

has the minimal possible length, cause the way it's built.
`$map & $mask`

has at most `length($mask)`

bytes, cause the way `&`

works. But
we still must guarantee (I) and (II), so we need to purge the possible
zero-bytes in the end of the bitstring:
while (ord(substr($map, -1)) == 0 && length($map) > 0 ) { substr($map, -1) = ''; }We need to test if

`length($map)`

is greater than 0, otherwise we may enter on
an infinite loop, if all bytes of the result are 0.
This `while`

guarantee (I) above. Then we check if the resulting `$map`

has
length 0. If so we remove the pref from the hash, so (II) is also achieved.
- We avoid to have more than one copy of preference values
- This architecture (index separated from the values) make it easy to change the way values are stored.

`pack`

and `unpack`

are not used cause they are not needed and cause the way to
know the level where a preference is defined is an `O(1)`

operation that
Edit | Attach | Print version | History: r1 | Backlinks | View wiki text | Edit wiki text | More topic actions

Topic revision: r1 - 19 Apr 2011, ProjectContributor

Copyright © CC-BY-SA by the contributing authors. All material on this collaboration platform is copyrighted under CC-BY-SA by the contributing authors unless otherwise noted.

Ideas, requests, problems regarding Foswiki? Send feedback

Ideas, requests, problems regarding Foswiki? Send feedback