Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r60797 - sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap
From: sl_at_[hidden]
Date: 2010-03-23 21:09:19

Author: sl_
Date: 2010-03-23 21:09:19 EDT (Tue, 23 Mar 2010)
New Revision: 60797
URL: http://svn.boost.org/trac/boost/changeset/60797

Log:
missing
Added:
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/acknowledgements.html (contents, props changed)
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html (contents, props changed)

Added: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/acknowledgements.html
==============================================================================
--- (empty file)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/acknowledgements.html 2010-03-23 21:09:19 EDT (Tue, 23 Mar 2010)
@@ -0,0 +1,40 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
+<title>Acknowledgements</title>
+<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.73.2">
+<link rel="start" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="up" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="prev" href="rationale_.html" title="Rationale">
+</head>
+<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
+<table cellpadding="2" width="100%"><tr>
+<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
+<td align="center">Home</td>
+<td align="center">Libraries</td>
+<td align="center">People</td>
+<td align="center">FAQ</td>
+<td align="center">More</td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="rationale_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a>
+</div>
+<div class="section" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="tokenmap.acknowledgements"></a><a class="link" href="acknowledgements.html" title="Acknowledgements">Acknowledgements</a>
+</h2></div></div></div></div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2009 Slawomir Lisznianski
+ 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)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="rationale_.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a>
+</div>
+</body>
+</html>

Added: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html
==============================================================================
--- (empty file)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html 2010-03-23 21:09:19 EDT (Tue, 23 Mar 2010)
@@ -0,0 +1,248 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
+<title>Background</title>
+<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.73.2">
+<link rel="start" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="up" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="prev" href="../index.html" title="Chapter 1. Boost.Tokenmap">
+<link rel="next" href="quick_tutorial.html" title="Quick tutorial">
+</head>
+<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
+<table cellpadding="2" width="100%"><tr>
+<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
+<td align="center">Home</td>
+<td align="center">Libraries</td>
+<td align="center">People</td>
+<td align="center">FAQ</td>
+<td align="center">More</td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="../index.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="quick_tutorial.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+</div>
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="tokenmap.background"></a><a class="link" href="background.html" title="Background"> Background</a>
+</h2></div></div></div>
+<div class="toc"><dl><dt><a href="background.html#tokenmap.background.analysis_of_simple_strategy"> Analysis
+ of the simple strategy</a></dt></dl></div>
+<div class="blockquote"><blockquote class="blockquote">
+
+ 
+
+ This section was contributed by Daniel Trebbien.
+ 
+
+ 
+</blockquote></div>
+
+ The main design goal of <code class="computeroutput">tokenmap</code>
+ was to make an associative container that uses random keys and which has extremely
+ fast lookup operations (i.e. given a key, the operation to find the associated
+ value should be as fast as possible). Array accesses are known to be among
+ the fastest operations performable on today's computing equipment, so the question
+ in developing <code class="computeroutput">tokenmap</code> was
+ whether it would be possible to use a dynamic array as the backing storage
+ and still implement a dictionary-like container that allows random keys.
+ 
+
+ There are many conceivable mapping strategies (the way that tokens are mapped
+ to indices in the array), but it's not always obvious which particular strategy
+ yields an associative container with all of the following properties:
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ The container can grow in size to accommodate more elements.
+ </li>
+<li>
+ Tokens will always map to their corresponding values regardless of the container's
+ growth.
+ </li>
+<li>
+ The tokens are random.
+ </li>
+</ol></div>
+
+ One simple strategy is to take a token <code class="computeroutput">t</code>
+ (an unsigned integer) and return the value <code class="computeroutput">store[t %
+ store_length]</code>
+ where <code class="computeroutput">store</code> is the name of
+ the dynamic array and <code class="computeroutput">store_length</code>
+ is its length. Interestingly enough, this strategy does
+ allow the implementation of an associative container with those properties,
+ and this is the strategy that is used by <code class="computeroutput">tokenmap</code>.
+ 
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h3 class="title">
+<a name="tokenmap.background.analysis_of_simple_strategy"></a><a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy" title="Analysis of the simple strategy"> Analysis
+ of the simple strategy</a>
+</h3></div></div></div>
+
+ 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">0x3af8cf08</code> and <code class="computeroutput">0xc0d9a414</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.
+ 
+
+ 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:
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ Create a new store <code class="computeroutput">new_store</code>
+ of length <code class="computeroutput">new_store_length</code>.
+ </li>
+<li>
+ For each token <code class="computeroutput">t</code> in the
+ container, place the associated value at <code class="computeroutput">new_store[t %
+ new_store_length]</code>.
+ </li>
+<li>
+ Delete the old store and use <code class="computeroutput">new_store</code>
+ as the store.
+ </li>
+</ol></div>
+
+ If we say that the initial store length is s0 and subsequent
+ store lengths are s1, s2, ..., sk,
+ then careful choices of the sequence {sk} allow the container
+ to have the property that tokens always map to their corresponding values
+ regardless of the number of re-hashes that have occurred since they were
+ generated (the perfect hashing property).
+ 
+
+ Some choices of the sequence {sk} will not work. For
+ example, suppose s0 were 2 and s1 were
+ 3. Then, tokens <code class="computeroutput">0x25b786ef</code> and
+ <code class="computeroutput">0x0010b86c</code> can be generated while
+ the store length is 2 (because modulo 2, they are 1 and 0, respectively),
+ but once the store length becomes 3, they hash to the same location (they
+ are both 2 modulo 3).
+ 
+
+ In the following sections, it will be proven that whenever <code class="computeroutput">new_store_length</code> is a multiple of the old
+ <code class="computeroutput">store_length</code>, then the perfect
+ hashing property is preserved.
+ 
+<a name="tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation"></a><h5>
+<a name="id540246"></a>
+ <a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation">Modular
+ arithmetic notation</a>
+ </h5>
+
+ 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 Zs. The elements of Zs are denoted by so-called class
+ notation: [x]s is the set of integers that
+ have the same remainder as x when divided by s;
+ in other words, for x an integer, [x]s is
+ the set of all integers that are congruent modulo s.
+ 
+<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 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>
+
+ In order for the token-generating strategy to remain perfect after a single
+ rehash, the crucial property of store lengths sk and
+ sk+1 is:
+ 
+<div class="blockquote"><blockquote class="blockquote">
+
+ 
+
+ <img src="../images/latex1.png" alt="latex1">
+ [<a name="id540381" href="#ftn.id540381" class="footnote">1</a>]
+ 
+
+ 
+</blockquote></div>
+
+ One choice of sk+1 that always works is when sk+1 is
+ a multiple of sk; when sk+1 = c·sk,
+ then it is always true that:
+ 
+<div class="blockquote"><blockquote class="blockquote">
+
+ 
+
+ <img src="../images/latex2.png" alt="latex2">
+ 
+
+ 
+</blockquote></div>
+
+ Proof
+ 
+
+ The statement is proved by way of the logically-equivalent contrapositive:
+ 
+<div class="blockquote"><blockquote class="blockquote">
+
+ 
+
+ <img src="../images/latex3.png" alt="latex3">
+ 
+
+ 
+</blockquote></div>
+
+ If [x]c·sk equals [y]c·sk then c·sk divides
+ (x - y) by definition. This implies
+ that sk divides (x - y),
+ so [x]sk equals [y]sk. ∎
+ 
+<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 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">{sk}
+ that preserves perfect hashing after arbitrary rehashes</a>
+ </h5>
+
+ From Proposition 1, we know that to preserve the perfect property after a
+ single rehash, one choice of sk+1 that always works is to
+ make sk+1 a multiple of sk. Therefore,
+ to preserve the perfect hashing property after arbitrary rehashes, we can
+ pick sk+1 = ck·sk for
+ any sequence of natural numbers {ck}. To make things
+ simple, however, <code class="computeroutput">tokenmap</code>
+ uses 2 for every ck. Thus sk = 2k·s0.
+ 
+</div>
+<div class="footnotes">
+ <hr width="100" align="left">
+<div class="footnote">[<a name="ftn.id540381" href="#id540381" class="para">1</a>] 
+ Read: If x and y are incongruent
+ modulo sk, then they are incongruent modulo
+ sk+1.
+ </div>
+</div>
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2009 Slawomir Lisznianski
+ 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)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="../index.html"><img src="../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="quick_tutorial.html"><img src="../../../../../doc/html/images/next.png" alt="Next"></a>
+</div>
+</body>
+</html>

Date view	Thread view	Subject view	Author view

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