|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61041 - in sandbox/tokenmap/libs/tokenmap/doc: . html html/tokenmap
From: sl_at_[hidden]
Date: 2010-04-04 10:03:36
Author: sl_
Date: 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
New Revision: 61041
URL: http://svn.boost.org/trac/boost/changeset/61041
Log:
updated by Daniel
Text files modified:
sandbox/tokenmap/libs/tokenmap/doc/html/index.html | 4 +-
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html | 46 ++++++++++++++++++---------------------
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html | 2
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html | 10 ++++----
sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk | 8 ++++--
5 files changed, 34 insertions(+), 36 deletions(-)
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/index.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/index.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/index.html 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
@@ -27,7 +27,7 @@
</h3></div></div>
<div><p class="copyright">Copyright © 2009 Slawomir Lisznianski</p></div>
<div><div class="legalnotice">
-<a name="id531067"></a><p>
+<a name="id472187"></a><p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
</p>
@@ -94,7 +94,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: March 24, 2010 at 01:03:37 GMT</small></p></td>
+<td align="left"><p><small>Last revised: April 04, 2010 at 13:59:52 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
@@ -82,18 +82,18 @@
<p>
One immediate consequence of using this simple strategy is that a user cannot
provide her own tokens; they must be generated by the container. This is
- because the user might try to use tokens that, modulo the store length at
- the time of insert, are the same. For example, if the store length is 12,
- then a container that is based on the simple strategy cannot allow tokens
- <code class="computeroutput"><span class="number">0x3af8cf08</span></code> and <code class="computeroutput"><span class="number">0xc0d9a414</span></code> to map to different values because
- modulo 12, these numbers are both 8. Some applications require the ability
- to specify the token, so containers based on this simple strategy are not
- suitable for these applications. However, there are other applications where
- you just want to generate handles or IDs of resources that will always map
- to the resources. For these, the particular values of the handles or IDs
- are irrelevant (they just need to uniquely map to the resources), so a container
- that generates the tokens (the particular values of handles or IDs) is perfectly
- acceptable.
+ because the user might try to use tokens that are the same modulo the store
+ length. For example, if the store length is 12, then a container that is
+ based on the simple strategy cannot allow tokens <code class="computeroutput"><span class="number">0x3af8cf08</span></code>
+ and <code class="computeroutput"><span class="number">0xc0d9a414</span></code> to map to different
+ values because these numbers are both 8 modulo 12. Some applications require
+ the ability to specify the token, so containers based on this simple strategy
+ are not suitable for these applications. However, there are other applications
+ where you just want to generate handles or IDs of resources that will always
+ map to the resources. For these, the particular values of the handles or
+ IDs are irrelevant (they just need to uniquely map to the resources), so
+ a container that generates the tokens (the particular values of handles or
+ IDs) is perfectly acceptable.
</p>
<p>
A container that is based on the described above strategy must implement
@@ -139,12 +139,12 @@
hashing property is preserved.
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation"></a><h5>
-<a name="id540246"></a>
+<a name="id481365"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation">Modular
arithmetic notation</a>
</h5>
<p>
- We denote the set of integers {..., -4, -3, -2, -1, 0, 1, 2, 3, ...} as
+ We denote the set of integers {..., -4, -3, -2, -1, 0, 1, 2, 3, ...} by
<span class="bold"><strong><span class="emphasis"><em>Z</em></span></strong></span> and the set of sets
of integers that are congruent modulo <span class="emphasis"><em>s</em></span> as <span class="bold"><strong><span class="emphasis"><em>Z</em></span></strong></span><sub><span class="emphasis"><em>s</em></span></sub>. The elements of <span class="bold"><strong><span class="emphasis"><em>Z</em></span></strong></span><sub><span class="emphasis"><em>s</em></span></sub> are denoted by so-called <span class="emphasis"><em>class
notation</em></span>: [<span class="emphasis"><em>x</em></span>]<sub><span class="emphasis"><em>s</em></span></sub> is the set of integers that
@@ -153,7 +153,7 @@
the set of all integers that are congruent modulo <span class="emphasis"><em>s</em></span>.
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.proposition_1__perfect_hashing_is_preserved_with_multiples_of_the_old_store_length"></a><h5>
-<a name="id540329"></a>
+<a name="id481449"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.proposition_1__perfect_hashing_is_preserved_with_multiples_of_the_old_store_length">Proposition
1: Perfect hashing is preserved with multiples of the old store length</a>
</h5>
@@ -167,12 +167,16 @@
</p>
<p>
<span class="inlinemediaobject"><img src="../images/latex1.png" alt="latex1"></span>
- <sup>[<a name="id540381" href="#ftn.id540381" class="footnote">1</a>]</sup>
</p>
<p>
</p>
</blockquote></div>
<p>
+ This can be read: If <span class="emphasis"><em>x</em></span> and <span class="emphasis"><em>y</em></span> are
+ incongruent modulo <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>, then they are incongruent modulo
+ <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span>+1</sub>.
+ </p>
+<p>
One choice of <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span>+1</sub> that always works is when <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span>+1</sub> is
a multiple of <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>; when <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span>+1</sub> = <span class="emphasis"><em>c</em></span>·<span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>,
then it is always true that:
@@ -208,7 +212,7 @@
so [<span class="emphasis"><em>x</em></span>]<sub><span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub></sub> equals [<span class="emphasis"><em>y</em></span>]<sub><span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub></sub>. ∎
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.__emphasis_s__emphasis_____quickbook_escape_prefix____subscript__emphasis_k__emphasis___subscript_____quickbook_escape_postfix_____that_preserves_perfect_hashing_after_arbitrary_rehashes"></a><h5>
-<a name="id540602"></a>
+<a name="id481719"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.__emphasis_s__emphasis_____quickbook_escape_prefix____subscript__emphasis_k__emphasis___subscript_____quickbook_escape_postfix_____that_preserves_perfect_hashing_after_arbitrary_rehashes">{<span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>}
that preserves perfect hashing after arbitrary rehashes</a>
</h5>
@@ -223,14 +227,6 @@
uses 2 for every <span class="emphasis"><em>c</em></span><sub><span class="emphasis"><em>k</em></span></sub>. Thus <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub> = 2<sup><span class="emphasis"><em>k</em></span></sup>·<span class="emphasis"><em>s</em></span><sub>0</sub>.
</p>
</div>
-<div class="footnotes">
-<br><hr width="100" align="left">
-<div class="footnote"><p><sup>[<a name="ftn.id540381" href="#id540381" class="para">1</a>] </sup>
- Read: If <span class="emphasis"><em>x</em></span> and <span class="emphasis"><em>y</em></span> are incongruent
- modulo <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>, then they are incongruent modulo
- <span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span>+1</sub>.
- </p></div>
-</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
@@ -32,7 +32,7 @@
them:
</p>
<div class="table">
-<a name="id542272"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
+<a name="id483388"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
<div class="table-contents"><table class="table" summary="Tutorial examples">
<colgroup>
<col>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
@@ -27,7 +27,7 @@
<a name="tokenmap.reference"></a><a class="link" href="reference.html" title="Reference">Reference</a>
</h2></div></div></div>
<a name="tokenmap.reference.headers"></a><h4>
-<a name="id541266"></a>
+<a name="id482382"></a>
<a class="link" href="reference.html#tokenmap.reference.headers">Headers</a>
</h4>
<p>
@@ -36,7 +36,7 @@
to boost namespace.
</p>
<a name="tokenmap.reference.synopsis"></a><h4>
-<a name="id541293"></a>
+<a name="id482409"></a>
<a class="link" href="reference.html#tokenmap.reference.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span>
@@ -83,15 +83,15 @@
</span><span class="special">}</span> <span class="comment">// namespace boost
</span></pre>
<a name="tokenmap.reference.class_template_tokenmap"></a><h4>
-<a name="id541881"></a>
+<a name="id482996"></a>
<a class="link" href="reference.html#tokenmap.reference.class_template_tokenmap">Class template tokenmap</a>
</h4>
<a name="tokenmap.reference.nested_types"></a><h4>
-<a name="id541895"></a>
+<a name="id483011"></a>
<a class="link" href="reference.html#tokenmap.reference.nested_types">Nested types</a>
</h4>
<a name="tokenmap.reference.constructors__copy_and_assignment"></a><h4>
-<a name="id541910"></a>
+<a name="id483025"></a>
<a class="link" href="reference.html#tokenmap.reference.constructors__copy_and_assignment">Constructors,
copy and assignment</a>
</h4>
Modified: sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk 2010-04-04 10:03:36 EDT (Sun, 04 Apr 2010)
@@ -129,7 +129,7 @@
[section:analysis_of_simple_strategy Analysis of the simple strategy]
-One immediate consequence of using this simple strategy is that a user cannot provide her own tokens; they must be generated by the container. This is because the user might try to use tokens that, modulo the store length at the time of insert, are the same. For example, if the store length is 12, then a container that is based on the simple strategy cannot allow tokens `0x3af8cf08` and `0xc0d9a414` to map to different values because modulo 12, these numbers are both 8. Some applications require the ability to specify the token, so containers based on this simple strategy are not suitable for these applications. However, there are other applications where you just want to generate handles or IDs of resources that will always map to the resources. For these, the particular values of the handles or IDs are irrelevant (they just need to uniquely map to the resources), so a container that generates the tokens (the particular values of handles or IDs) is perfectly acceptable.
+One immediate consequence of using this simple strategy is that a user cannot provide her own tokens; they must be generated by the container. This is because the user might try to use tokens that are the same modulo the store length. For example, if the store length is 12, then a container that is based on the simple strategy cannot allow tokens `0x3af8cf08` and `0xc0d9a414` to map to different values because these numbers are both 8 modulo 12. Some applications require the ability to specify the token, so containers based on this simple strategy are not suitable for these applications. However, there are other applications where you just want to generate handles or IDs of resources that will always map to the resources. For these, the particular values of the handles or IDs are irrelevant (they just need to uniquely map to the resources), so a container that generates the tokens (the particular values of handles or IDs) is perfectly acceptable.
A container that is based on the described above strategy must implement a rehashing algorithm which is used whenever the container is expanded to accommodate more elements. An algorithm that works well with our strategy is:
@@ -145,12 +145,14 @@
[heading Modular arithmetic notation]
-We denote the set of integers {..., -4, -3, -2, -1, 0, 1, 2, 3, ...} as [*['Z]] and the set of sets of integers that are congruent modulo /s/ as [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>'''. The elements of [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>''' are denoted by so-called /class notation/: \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of integers that have the same remainder as /x/ when divided by /s/; in other words, for /x/ an integer, \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of all integers that are congruent modulo /s/.
+We denote the set of integers {..., -4, -3, -2, -1, 0, 1, 2, 3, ...} by [*['Z]] and the set of sets of integers that are congruent modulo /s/ as [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>'''. The elements of [*['Z]]'''<subscript><emphasis>s</emphasis></subscript>''' are denoted by so-called /class notation/: \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of integers that have the same remainder as /x/ when divided by /s/; in other words, for /x/ an integer, \[['x]\]'''<subscript><emphasis>s</emphasis></subscript>''' is the set of all integers that are congruent modulo /s/.
[heading Proposition 1: Perfect hashing is preserved with multiples of the old store length]
In order for the token-generating strategy to remain perfect after a single rehash, the crucial property of store lengths /s/'''<subscript><emphasis>k</emphasis></subscript>''' and /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' is:
-[:[$images/latex1.png][footnote Read: If /x/ and /y/ are incongruent modulo /s/'''<subscript><emphasis>k</emphasis></subscript>''', then they are incongruent modulo /s/'''<subscript><emphasis>k</emphasis>+1</subscript>'''.]]
+[:[$images/latex1.png]]
+
+This can be read: If /x/ and /y/ are incongruent modulo /s/'''<subscript><emphasis>k</emphasis></subscript>''', then they are incongruent modulo /s/'''<subscript><emphasis>k</emphasis>+1</subscript>'''.
One choice of /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' that always works is when /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' is a multiple of /s/'''<subscript><emphasis>k</emphasis></subscript>'''; when /s/'''<subscript><emphasis>k</emphasis>+1</subscript>''' = ['c]·/s/'''<subscript><emphasis>k</emphasis></subscript>''', then it is always true that:
[:[$images/latex2.png]]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk