From 76271a3366731d4c372fdebcd8d3437e6e09a61b Mon Sep 17 00:00:00 2001
From: Stepan Dyatkovskiy <stpworld@narod.ru>
Date: Wed, 25 Apr 2012 17:09:38 +0000
Subject: First implementation of: - FlatArrayMap. Very simple map container
 that uses flat array inside. - MultiImplMap. Map container interface, that
 has two modes, one for small amount of elements and one for big amount. -
 SmallMap. SmallMap is DenseMap compatible MultiImplMap. It uses FlatArrayMap
 for small mode, and DenseMap for big mode.

Also added unittests for new classes and update for ProgrammersManual.
For more details about new classes see ProgrammersManual and comments in sourcecode.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@155557 91177308-0d34-0410-b5e6-96231b3b80d8
---
 docs/ProgrammersManual.html | 81 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

(limited to 'docs/ProgrammersManual.html')

diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html
index 854f90e28b..f81d7130a3 100644
--- a/docs/ProgrammersManual.html
+++ b/docs/ProgrammersManual.html
@@ -95,6 +95,9 @@ option</a></li>
       <li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li>
       <li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li>
       <li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li>
+      <li><a href="#dss_multiimplmap">"llvm/ADT/MultiImplMap.h"</a></li>
+      <li><a href="#dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a></li>
+      <li><a href="#dss_smallmap">"llvm/ADT/SmallMap.h"</a></li>
       <li><a href="#dss_valuemap">"llvm/ADT/ValueMap.h"</a></li>
       <li><a href="#dss_intervalmap">"llvm/ADT/IntervalMap.h"</a></li>
       <li><a href="#dss_map">&lt;map&gt;</a></li>
@@ -1810,6 +1813,84 @@ a <code>Config</code> parameter to the ValueMap template.</p>
 
 </div>
 
+<!-- _______________________________________________________________________ -->
+<h4>
+  <a name="dss_multiimplmap">"llvm/ADT/MultiImplMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+MultiImplMap is map that has two modes, one for small amount of elements and
+one for big amount. User should set map implementation for both of them.
+User also should set the maximum possible number of elements for small mode.
+</p>
+
+<p>
+If user want to use MultiImplMap instead of
+<a href="#dss_densemap">DenseMap</a>, he should pass template parameter
+DenseMapCompatible = true. Note, that in this case map implementations
+should present additional DenseMap specific methods (see below):
+<code>isPointerIntoBucketsArray</code>, <code>getPointerIntoBucketsArray</code>
+and <code>FindAndConstruct</code>.
+</p>
+
+<p>
+Initially MultiImplMap uses small mode and small map implementation. It 
+triggered to the big mode when the number of contained elements exceeds
+maximum possible elements for small mode.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+  <a name="dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+FlatArrayMap optimized for small amount of elements. It uses flat array
+implementation inside:
+</p>
+<pre>[ key0, value0, key1, value1, ... keyN, valueN ]</pre>
+
+
+<p>
+User should pass key type, mapped type (type of value), and maximum
+number of elements.
+</p>
+
+<p>
+After maximum number of elements is reached, map declines any further
+attempts to insert new elements ("insert" method returns &#60;end(),
+false&#62;).
+</p>
+
+<p>
+FlatArrayMap has interface that is compatible with
+<a href="#dss_densemap">DenseMap</a>, so user can replace it with DenseMap
+without any code changing and vice versa.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+  <a name="dss_smallmap">"llvm/ADT/SmallMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+SmallMap is wrapper around <a href="#dss_multiimplmap">MultiImplMap</a>.
+It uses <a href="#dss_flatarraymap">FlatArrayMap</a> for small mode, and
+<a href="#dss_densemap">DenseMap</a> for big mode.
+</p>
+
+</div>
+
 <!-- _______________________________________________________________________ -->
 <h4>
   <a name="dss_intervalmap">"llvm/ADT/IntervalMap.h"</a>
-- 
cgit v1.2.3-18-g5258