API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 8th, 2014
204
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
D 49.29 KB | None | 0 0
raw download clone embed print report
  1. /**
  2.  * Written in the D programming language.
  3.  * This module provides an back-end implementation of associative array
  4.  *
  5.  * Copyright: Copyright Igor Stepanov 2013-2014.
  6.  * License:   <a href="http://www.boost.org/LICENSE_1_0.txt">Boost License 1.0</a>.
  7.  * Authors:   Igor Stepanov
  8.  * Source: $(DRUNTIMESRC core/internal/_aa.d)
  9.  */
  10. module aa;
  11.  
  12. import core.internal.traits;
  13. import core.exception;
  14. import core.memory;
  15.  
  16. enum Mutability
  17. {
  18.     Mutable,
  19.     Const,
  20.     Immutable,
  21.     //Shared,
  22.     //ConstShared
  23. }
  24.  
  25. struct AssociativeArray(Key, Value)
  26. {
  27.     private enum isLvlValueConst = lvlOpEqualsArgModififer!Value == OpEqualsArg.Const;
  28.     private enum isRvlValueConst = rvlOpEqualsArgModififer!Value == OpEqualsArg.Const;
  29.     private enum LoadFactor = 0.6;
  30.  
  31.     this(T...)(auto ref T args) if (T.length >= 2 && T.length % 2 == 0)
  32.     {
  33.         impl = new Impl();
  34.         impl.nodes = args.length / 2;
  35.  
  36.         impl.buckets = newBuckets(findGoodLength(cast(size_t)(impl.nodes / LoadFactor)));
  37.  
  38.         auto len = impl.buckets.length;
  39.  
  40.         foreach (i; staticIota!(0, args.length / 2))
  41.         {
  42.             static if (is(typeof(args[2*i]) == Key))
  43.             {
  44.                 alias key = args[2*i];
  45.             }
  46.             else
  47.             {
  48.                 Key key = args[2*i];
  49.             }
  50.  
  51.             static if (is(typeof(args[2*i + 1]) == Value))
  52.             {
  53.                 alias value = args[2*i + 1];
  54.             }
  55.             else
  56.             {
  57.                 Value value = args[2*i + 1];
  58.             }
  59.  
  60.             size_t key_hash = hashOf(key);
  61.  
  62.             size_t depth;
  63.             size_t idx = findBucket!true(key_hash, key, depth);
  64.  
  65.             assert(impl.buckets[idx].occupation == Empty, "duplicate key");
  66.             impl.buckets[idx].setKey!true(key);
  67.             impl.buckets[idx].setValue!true(value);
  68.             impl.buckets[idx].occupation == Occupied;
  69.             //impl.buckets[idx].depth = depth;
  70.  
  71.             size_t base_idx = key_hash & (impl.buckets.length - 1);
  72.             if (impl.buckets[base_idx].depth < depth)
  73.                 impl.buckets[base_idx].depth = depth;
  74.         }
  75.     }
  76.  
  77.     void init(size_t size)
  78.     {
  79.         impl = new Impl();
  80.         impl.nodes = 0;
  81.         impl.buckets = newBuckets(findGoodLength(cast(size_t)(size / LoadFactor)));
  82.     }
  83.     @property @trusted pure nothrow const
  84.     size_t length()
  85.     out (result)
  86.     {
  87.         size_t len = 0;
  88.         if (impl)
  89.         {
  90.             for (size_t i = 0; i < impl.buckets.length; i++)
  91.             {
  92.                 if (impl.buckets[i].occupation == Occupied)
  93.                 {
  94.                     len++;
  95.                 }
  96.             }
  97.         }
  98.         assert(len == result);
  99.     }
  100.     body
  101.     {
  102.         return impl ? impl.nodes : 0;
  103.     }
  104.  
  105.     //cannot implicitly convert expression ... of type const(Thread)* to inout(Thread)*
  106.     //BUG?
  107.     inout(Value)* opIn_r()(auto ref in Key key) inout @trusted
  108.     {
  109.         auto e = getRValue(key);
  110.         return cast(typeof(return))(e ? &e.value : null);
  111.     }
  112.  
  113.     ref Value opIndex()(auto ref in Key key)
  114.     {
  115.         auto v = getRValue(key);
  116.         if (!v)
  117.             onRangeError();
  118.         else
  119.             return v.value;
  120.         assert(0);
  121.     }
  122.  
  123.     //cannot implicitly convert expression ... of type const(Thread) to inout(Thread)
  124.     ref const(Value) opIndex()(auto ref in Key key) const
  125.     {
  126.         auto v = getRValue(key);
  127.         if (!v)
  128.             onRangeError();
  129.         else
  130.             return v.value;
  131.         assert(0);
  132.     }
  133.  
  134.     ref Value opIndexAssign()(auto ref Value value, in auto ref Key key)
  135.     {
  136.         auto v = getLValue(key);
  137.         assert(v);
  138.         v.setValue!false(value);
  139.  
  140.         return v.value;
  141.     }
  142.  
  143.     bool remove()(auto ref in Key key)
  144.     {
  145.         if (!impl)
  146.         {
  147.             return false;
  148.         }
  149.  
  150.         auto key_hash = hashOf(key);
  151.  
  152.         size_t initial_hash = key_hash & (impl.buckets.length - 1);
  153.         size_t mdepth = impl.buckets[initial_hash].depth;
  154.  
  155.         size_t j = 1;
  156.         size_t i = initial_hash;
  157.         for (; j <= mdepth; ++j)
  158.         {
  159.             if (impl.buckets[i].occupation == Occupied &&
  160.                 impl.buckets[i].hash == key_hash &&
  161.                 impl.buckets[i].key == key)
  162.             {
  163.                 break;
  164.             }
  165.  
  166.             i = (i + j) & (impl.buckets.length - 1);
  167.         }
  168.         if (j > mdepth)
  169.         {
  170.             return false;
  171.         }
  172.         else
  173.         {
  174.             size_t to_remove = i;
  175.             size_t last = i;
  176.             size_t last_j = j - 1;
  177.             for (; j <= mdepth; ++j)
  178.             {
  179.                 i = (i + j) & (impl.buckets.length - 1);
  180.                 if (impl.buckets[i].occupation == Occupied &&
  181.                     (impl.buckets[i].hash & (impl.buckets.length - 1)) == initial_hash)
  182.                 {
  183.                     last = i;
  184.                     last_j = j;
  185.                 }
  186.  
  187.  
  188.             }
  189.             if (last != to_remove)
  190.             {
  191.                 impl.buckets[to_remove].swapKV(impl.buckets[last]);
  192.                 //impl.buckets[to_remove]._depth = impl.buckets[last]._depth;
  193.             }
  194.             impl.buckets[last].occupation = Empty;
  195.             impl.buckets[last].dispose();
  196.             impl.nodes--;
  197.             //impl.buckets[initial_hash].depth = mdepth - (mdepth - last_j + 1);
  198.             return true;
  199.         }
  200.     }
  201.  
  202.     AssociativeArray rehash() @safe
  203.     {
  204.         return _rehash();
  205.     }
  206.  
  207.     AssociativeArray dup() const
  208.     {
  209.         return _dup();
  210.     }
  211.  
  212.     static if (isCopyConstructable!Key)
  213.     {
  214.         Key[] keys() @property
  215.         {
  216.             if (!length) return null;
  217.             size_t len = 0;
  218.  
  219.             Key[] elems;
  220.             if (!__ctfe)
  221.                 elems.reserve(impl.nodes);
  222.  
  223.             for (size_t i = 0; i < impl.buckets.length; i++)
  224.             {
  225.                 if (impl.buckets[i].occupation == Occupied)
  226.                 {
  227.                     elems ~= impl.buckets[i].key;
  228.                     len++;
  229.                 }
  230.             }
  231.             assert(len == impl.nodes);
  232.  
  233.             return elems;
  234.         }
  235.  
  236.         const(Key)[] keys() const @property
  237.         {
  238.             return cast(const)(cast()this).keys;
  239.         }
  240.  
  241.         inout(Key)[] inout_keys() inout @property
  242.         {
  243.             return cast(inout(Key)[])keys;
  244.         }
  245.     }
  246.     else
  247.     {
  248.         @disable Key[] keys() @property;
  249.         @disable const(Key)[] keys() const @property;
  250.         @disable inout(Key)[] inout_keys() inout @property;
  251.     }
  252.  
  253.     static if (isCopyConstructable!Value)
  254.     {
  255.  
  256.         Value[] values() @property
  257.         {
  258.             if (!length) return null;
  259.             size_t len = 0;
  260.  
  261.             Value[] elems;
  262.             if (!__ctfe)
  263.                 elems.reserve(impl.nodes);
  264.             //Do I need to set GC.BlkAttr.NO_SCAN?
  265.             //a.length = _aaLen(aa);
  266.             //a.ptr = cast(byte*) GC.malloc(a.length * valuesize,
  267.             //                                valuesize < (void*).sizeof ? GC.BlkAttr.NO_SCAN : 0);
  268.  
  269.             for (size_t i = 0; i < impl.buckets.length; i++)
  270.             {
  271.                 if (impl.buckets[i].occupation == Occupied)
  272.                 {
  273.                     elems ~= impl.buckets[i].value;
  274.                     len++;
  275.                 }
  276.             }
  277.             assert(len == impl.nodes);
  278.  
  279.             return elems;
  280.         }
  281.  
  282.         const(Value)[] values() const @property
  283.         {
  284.             return cast(const)(cast()this).values;
  285.         }
  286.  
  287.         inout(Value)[] inout_values() inout @property
  288.         {
  289.             return cast(inout(Value)[])values;
  290.         }
  291.     }
  292.     else
  293.     {
  294.         @disable Value[] values() @property;
  295.         @disable const(Value)[] values() const @property;
  296.         @disable inout(Value)[] inout_values() inout @property;
  297.     }
  298.  
  299.     int opApply(scope int delegate(ref Value) dg)
  300.     {
  301.         if (!impl)
  302.         {
  303.             return 0;
  304.         }
  305.  
  306.         for (size_t i = 0; i < impl.buckets.length; i++)
  307.         {
  308.             if (impl.buckets[i].occupation == Occupied)
  309.             {
  310.                 auto result = dg(impl.buckets[i].value);
  311.                 if (result)
  312.                     return result;
  313.             }
  314.         }
  315.         return 0;
  316.     }
  317.  
  318.     int opApply(scope int delegate(ref Key, ref Value) dg)
  319.     {
  320.         if (!impl)
  321.         {
  322.             return 0;
  323.         }
  324.  
  325.         for (size_t i = 0; i < impl.buckets.length; i++)
  326.         {
  327.             if (impl.buckets[i].occupation == Occupied)
  328.             {
  329.                 auto result = dg(impl.buckets[i].key, impl.buckets[i].value);
  330.                 if (result)
  331.                     return result;
  332.             }
  333.         }
  334.         return 0;
  335.     }
  336.  
  337.     int opApply(scope int delegate(ref const(Value)) dg) const
  338.     {
  339.         if (!impl)
  340.         {
  341.             return 0;
  342.         }
  343.  
  344.         for (size_t i = 0; i < impl.buckets.length; i++)
  345.         {
  346.             if (impl.buckets[i].occupation == Occupied)
  347.             {
  348.                 auto result = dg(impl.buckets[i].value);
  349.                 if (result)
  350.                     return result;
  351.             }
  352.         }
  353.         return 0;
  354.     }
  355.  
  356.     int opApply(scope int delegate(ref const(Key), ref const(Value)) dg) const
  357.     {
  358.         if (!impl)
  359.         {
  360.             return 0;
  361.         }
  362.  
  363.         for (size_t i = 0; i < impl.buckets.length; i++)
  364.         {
  365.             if (impl.buckets[i].occupation == Occupied)
  366.             {
  367.                 auto result = dg(impl.buckets[i].key, impl.buckets[i].value);
  368.                 if (result)
  369.                     return result;
  370.             }
  371.         }
  372.         return 0;
  373.     }
  374.  
  375.     ref AssociativeArray opAssign(typeof(null)) @safe pure nothrow
  376.     {
  377.         impl = null;
  378.         return this;
  379.     }
  380.  
  381.     inout(Value) get(in Key key, lazy inout(Value) defaultValue) inout
  382.     {
  383.         auto p = key in this;
  384.         return p ? *p : defaultValue;
  385.     }
  386.  
  387.     auto byKey() @safe pure nothrow
  388.     {
  389.         return getRange!(KeyValue.Key)();
  390.     }
  391.  
  392.     auto byValue() @safe pure nothrow
  393.     {
  394.         return getRange!(KeyValue.Value)();
  395.     }
  396.  
  397.     auto byKey() @safe pure nothrow const
  398.     {
  399.         return getConstRange!(KeyValue.Key)();
  400.     }
  401.  
  402.     auto byValue() @safe pure nothrow const
  403.     {
  404.         return getConstRange!(KeyValue.Value)();
  405.     }
  406.  
  407.     //AA allows a values which have non-const opEquals, or opEquals which takes mutable rvl arg
  408.     //If Value.opEquals is non-const, AssociativeArray.opEquals should be mutable too.
  409.     //If Value.opEquals can't take a const value, AssociativeArray.opEquals can't take const argument too.
  410.     //AA Keys always should have const opEquals which takes const argument
  411.     private static string getOpEqualsCode()
  412.     {
  413.         string fbody = "";
  414.        
  415.         if (isRvlValueConst)
  416.         {
  417.             fbody ~=   "bool opEquals(const AssociativeArray rvl)";
  418.         }
  419.         else
  420.         {
  421.             fbody ~=   "bool opEquals(AssociativeArray rvl)";
  422.         }
  423.         if (isLvlValueConst)
  424.             fbody ~=   " const\n";
  425.         else
  426.             fbody ~=   "\n";
  427.         fbody ~= q{
  428.             {
  429.                 if (impl.nodes != rvl.impl.nodes)
  430.                     return false;
  431.                 if (!impl.nodes)
  432.                     return true;
  433.                 for (size_t i = 0; i < impl.buckets.length; i++)
  434.                 {
  435.                     if (impl.buckets[i].occupation == Occupied)
  436.                     {
  437.                         size_t depth;
  438.                         size_t idx = rvl.findBucket!false(impl.buckets[i].hash, impl.buckets[i].key, depth);
  439.                         if (idx == -1)
  440.                             return false;
  441.                         if (!impl.buckets[i].isEqualsValue(rvl.impl.buckets[idx].value))
  442.                             return false;
  443.                     }
  444.                 }
  445.                 return true;
  446.             }
  447.         };
  448.         return fbody;              
  449.     }
  450.  
  451.     mixin(getOpEqualsCode());
  452.  
  453.  
  454. private:
  455.     //@trusted is needed because GC functions are used
  456.     AssociativeArray _rehash() @trusted
  457.     {
  458.         AssociativeArray ret;
  459.         if (!impl)
  460.             return ret;
  461.  
  462.         if (!impl.nodes)
  463.         {
  464.             if (!__ctfe)
  465.             {
  466.                 GC.free(impl.buckets.ptr);
  467.                 impl.buckets = new Entry[findGoodLength(0)];
  468.             }
  469.             return this;
  470.         }
  471.  
  472.         Entry[] old_buckets = impl.buckets;
  473.  
  474.         auto len = findGoodLength(cast(size_t)(impl.nodes / LoadFactor) + 1);
  475.  
  476.         impl.buckets = newBuckets(len);
  477.         for (size_t i = 0; i < old_buckets.length; i++)
  478.         {
  479.             if (old_buckets[i].occupation == Occupied)
  480.             {
  481.                 size_t depth;
  482.                 size_t idx = findBucket!true(old_buckets[i].hash, old_buckets[i].key, depth);
  483.  
  484.                 impl.buckets[idx].swapKV(old_buckets[i]);
  485.  
  486.                 impl.buckets[idx].occupation = Occupied;
  487.                 //impl.buckets[idx].depth = depth;
  488.                 size_t base_idx = old_buckets[i].hash & (impl.buckets.length - 1);
  489.                 if (impl.buckets[base_idx].depth < depth)
  490.                     impl.buckets[base_idx].depth = depth;
  491.             }
  492.         }
  493.  
  494.  
  495.         if (!__ctfe)
  496.             GC.free(old_buckets.ptr);
  497.         return this;
  498.     }
  499.  
  500.     AssociativeArray _dup() const @trusted
  501.     {
  502.         AssociativeArray ret;
  503.         if (!impl)
  504.             return ret;
  505.  
  506.         ret.impl.buckets = newBuckets(ret.impl.buckets.length);
  507.         (cast(void*)ret.impl.buckets.ptr)[0 .. impl.buckets.length * Entry.sizeof] =
  508.             (cast(void*)impl.buckets.ptr)[0 .. impl.buckets.length * Entry.sizeof];
  509.         foreach (i, ref cur; ret.impl.buckets)
  510.         {
  511.             cur.setKey!true(impl.buckets[i].key);
  512.             cur.setKey!true(impl.buckets[i].value);
  513.         }
  514.  
  515.         return ret;
  516.     }
  517.  
  518.     static Impl* newImpl() @safe pure
  519.     {
  520.         auto impl = new Impl();
  521.         impl.buckets = newBuckets(findGoodLength(0));
  522.         return impl;
  523.     }
  524.  
  525.     Entry* getLValue(ref const(Unqual!Key) pkey)
  526.     {
  527.         if (!impl)
  528.         {
  529.             impl = newImpl();
  530.         }
  531.  
  532.         auto key_hash = hashOf(pkey);
  533.  
  534.         size_t depth;
  535.         size_t idx = findBucket!true(key_hash, pkey, depth);
  536.         if (impl.buckets[idx].occupation == Empty)
  537.         {
  538.             if (((impl.nodes) / LoadFactor) > impl.buckets.length)
  539.             {
  540.                 grow();
  541.                 depth = 0;
  542.                 idx = findBucket!true(key_hash, pkey, depth);
  543.             }
  544.             impl.nodes++;
  545.             impl.buckets[idx].occupation = Occupied;
  546.             impl.buckets[idx].hash = key_hash;
  547.             impl.buckets[idx].setKey!true(pkey);
  548.             //impl.buckets[idx].depth = depth;
  549.             size_t base_idx = key_hash & (impl.buckets.length - 1);
  550.             if (impl.buckets[base_idx].depth < depth)
  551.                 impl.buckets[base_idx].depth = depth;
  552.  
  553.         }
  554.         return &impl.buckets[idx];
  555.     }
  556.  
  557.     //!CTFE BUG: cannot cast &Entry(...) to inout(Entry)*
  558.     Entry* getRValue(ref const(Unqual!Key) pkey)
  559.     {
  560.         if (!impl)
  561.             return null;
  562.  
  563.         auto key_hash = hashOf(pkey);
  564.         size_t depth;
  565.         size_t idx = findBucket(key_hash, pkey, depth);
  566.         if (idx == -1)
  567.             return null;
  568.         return &impl.buckets[idx];
  569.     }
  570.  
  571.     const(Entry)* getRValue(ref const(Unqual!Key) pkey) const
  572.     {
  573.         if (!impl)
  574.             return null;
  575.  
  576.         auto key_hash = hashOf(pkey);
  577.         size_t depth;
  578.         size_t idx = findBucket(key_hash, pkey, depth);
  579.         if (idx == -1)
  580.             return null;
  581.         return &impl.buckets[idx];
  582.     }
  583.  
  584.     size_t findBucket(bool insert = false)(size_t hash, ref const(Unqual!Key) pkey, ref size_t depth) const
  585.     {
  586.         size_t initial_hash = hash & (impl.buckets.length - 1);
  587.         size_t mdepth = impl.buckets[initial_hash].depth;
  588.         static if (insert)
  589.         {
  590.             size_t first_empty_post = -1;
  591.         }
  592.         size_t j = 1;
  593.         size_t i = initial_hash;
  594.         for (; j <= mdepth; i = (i + j) & (impl.buckets.length - 1), ++j)
  595.         {
  596.             static if (insert)
  597.             {
  598.                 if (impl.buckets[i].occupation == Empty)
  599.                 {
  600.                     if (first_empty_post == -1)
  601.                         first_empty_post = i;
  602.                     continue;
  603.                 }
  604.             }
  605.  
  606.             if (impl.buckets[i].occupation == Occupied &&
  607.                 impl.buckets[i].hash == hash &&
  608.                 impl.buckets[i].key == pkey)
  609.             {
  610.                 depth = j;
  611.                 return i;
  612.             }
  613.         }
  614.  
  615.         static if (insert)
  616.         {
  617.             if (first_empty_post != -1)
  618.                 return first_empty_post;
  619.             for (; ; i = (i + j) & (impl.buckets.length - 1), ++j)
  620.             {
  621.                 if (impl.buckets[i].occupation == Empty)
  622.                 {
  623.                     depth = j;
  624.                     return i;
  625.                 }
  626.             }
  627.             assert(0);
  628.         }
  629.         else
  630.         {
  631.             return -1;
  632.         }
  633.     }
  634.  
  635.     void grow()
  636.     {
  637.         auto obuckets = impl.buckets;
  638.        
  639.         impl.buckets = newBuckets(obuckets.length * 8);
  640.  
  641.         for (size_t i = 0; i < obuckets.length; ++i)
  642.         {
  643.             if (obuckets[i].occupation != Occupied)
  644.                 continue;
  645.  
  646.             size_t hash = obuckets[i].hash;
  647.             size_t depth;
  648.             size_t newidx = findBucket!true(hash, obuckets[i].key, depth);
  649.  
  650.             auto odepth = impl.buckets[newidx].depth;
  651.             auto xx_key = obuckets[i].key;
  652.             auto xx_val = obuckets[i].value;
  653.             impl.buckets[newidx].swapKV(obuckets[i]);
  654.             assert(odepth == impl.buckets[newidx].depth);
  655.             assert(xx_key == impl.buckets[newidx].key);
  656.             assert(xx_val == impl.buckets[newidx].value);
  657.             assert(hash == impl.buckets[newidx].hash);
  658.  
  659.             impl.buckets[newidx].occupation = Occupied;
  660.             size_t base_idx = hash & (impl.buckets.length - 1);
  661.             if (impl.buckets[base_idx].depth < depth)
  662.                 impl.buckets[base_idx].depth = depth;
  663.         }
  664.  
  665.     }
  666.    
  667.     static Entry[] newBuckets(in size_t len) @trusted pure nothrow
  668.     {
  669.         if (!__ctfe)
  670.         {
  671.             auto ptr = cast(Entry*) GC.calloc(
  672.                 len * (Entry).sizeof, GC.BlkAttr.NO_INTERIOR);
  673.             return ptr[0..len];
  674.         }
  675.         else
  676.         {
  677.             return new Entry[len];
  678.         }
  679.     }
  680.  
  681.     static size_t findGoodLength(size_t idx) @safe pure nothrow
  682.     {
  683.         //BUG, Why core.stdc.math.log2 is impure?
  684.         size_t l = 16;
  685.         while (l < idx)
  686.             l *= 2;
  687.         return l;
  688.     }
  689.  
  690.     Range!(Mutability.Mutable, kv) getRange(KeyValue kv)() @safe pure nothrow
  691.     {
  692.         Range!(Mutability.Mutable, kv) res;
  693.         res.impl = impl;
  694.         res.current = -1;
  695.         if (!length)
  696.             return res;
  697.         for (size_t i = 0; i < impl.buckets.length; i++)
  698.         {
  699.             if (impl.buckets[i].occupation == Occupied)
  700.             {
  701.                 res.current = i;
  702.                 break;
  703.             }
  704.         }
  705.         return res;
  706.     }
  707.  
  708.     Range!(Mutability.Const, kv) getConstRange(KeyValue kv)() @safe pure nothrow const
  709.     {
  710.         Range!(Mutability.Const, kv) res;
  711.         res.impl = impl;
  712.         res.current = -1;
  713.         if (!length)
  714.             return res;
  715.  
  716.         for (size_t i = 0; i < impl.buckets.length; i++)
  717.         {
  718.             if (impl.buckets[i].occupation == Occupied)
  719.             {
  720.                 res.current = i;
  721.                 break;
  722.             }
  723.         }
  724.         return res;
  725.     }
  726.  
  727.     size_t toHash() const nothrow @trusted
  728.     {
  729.         try
  730.         {
  731.             if (!length) return 0;
  732.             size_t h = 0;
  733.  
  734.             // The computed hash is independent of the foreach traversal order.
  735.             foreach (key, ref val; this)
  736.             {
  737.                 size_t[2] hpair;
  738.                 hpair[0] = key.hashOf();
  739.                 hpair[1] = val.hashOf();
  740.                 h ^= hashOf(hpair[1], hashOf(hpair[0]));
  741.             }
  742.             return h;
  743.         }
  744.         catch(Throwable th)
  745.         {
  746.             return 0;
  747.         }
  748.     }
  749.  
  750.     static struct Range(Mutability mutability, KeyValue ckv = KeyValue.Unknown)
  751.     {
  752.         size_t current;
  753.         static if (mutability == Mutability.Mutable)
  754.         {
  755.             Impl* impl;
  756.             alias RetKey = Key;
  757.             alias RetValue = Value;
  758.         }
  759.         else
  760.         {
  761.             const(Impl)* impl;
  762.             alias RetKey = const(Key);
  763.             alias RetValue = const(Value);
  764.         }
  765.  
  766.         static Range fromAARange(AARange r) @nogc
  767.         {
  768.             Range ret;
  769.             ret.impl = cast(typeof(ret.impl))r.impl;
  770.             ret.current = cast(typeof(ret.current))r.current;
  771.             return ret;
  772.         }
  773.  
  774.         AARange toAARange() @nogc
  775.         {
  776.             AARange ret;
  777.             ret.impl = cast(void*)impl;
  778.             ret.current = cast(void*)current;
  779.             return ret;
  780.         }
  781.  
  782.         @property bool empty() @nogc
  783.         {
  784.             return !impl || current == -1;
  785.         }
  786.  
  787.         static if (ckv == KeyValue.Key)
  788.         {
  789.             @property ref RetKey front() @nogc//really ref Key? may be ref const(Key) or Key?
  790.             in
  791.             {
  792.                 assert(current != -1);
  793.             }
  794.             body
  795.             {
  796.                 return impl.buckets[current].key;
  797.             }
  798.         }
  799.  
  800.         else static if (ckv == KeyValue.Value)
  801.         {
  802.             @property ref RetValue front() @nogc
  803.             in
  804.             {
  805.                 assert(current != -1);
  806.             }
  807.             body
  808.             {
  809.                 return impl.buckets[current].value;
  810.             }
  811.         }
  812.         else
  813.         {
  814.             @property ref RetKey front(KeyValue kv)() @nogc if (kv == KeyValue.Key && ckv == KeyValue.Unknown) //really ref Key? may be ref const(Key) or Key?
  815.             in
  816.             {
  817.                 assert(current != -1);
  818.             }
  819.             body
  820.             {
  821.                 return impl.buckets[current].key;
  822.             }
  823.  
  824.  
  825.             @property ref RetValue front(KeyValue kv)() @nogc if (kv == KeyValue.Value && ckv == KeyValue.Unknown)
  826.             in
  827.             {
  828.                 assert(current != -1);
  829.             }
  830.             body
  831.             {
  832.                 return impl.buckets[current].value;
  833.             }
  834.         }
  835.  
  836.         void popFront() @nogc
  837.         in
  838.         {
  839.             assert(impl);
  840.             assert(current);
  841.         }
  842.         body
  843.         {
  844.             current++;
  845.             while (current < impl.buckets.length)
  846.             {
  847.                 if (impl.buckets[current].occupation == Occupied)
  848.                 {
  849.                     return;
  850.                 }
  851.                 current++;
  852.             }
  853.             current = -1;
  854.         }
  855.  
  856.  
  857.         Range save() @nogc
  858.         {
  859.             return this;
  860.         }
  861.     }
  862.  
  863.     static struct Impl
  864.     {
  865.         immutable(AssociativeArrayHandle)* handle = &AssociativeArray.handle;
  866.         Entry[] buckets;
  867.         size_t nodes;       // total number of entries
  868.  
  869.         this(Impl i)
  870.         {
  871.             buckets = i.buckets;
  872.             nodes = i.nodes;
  873.         }
  874.     }
  875.  
  876.     private enum ubyte Empty = 0b00;
  877.     private enum ubyte Occupied = 0b01;
  878.  
  879.     static struct Entry
  880.     {
  881.         size_t hash;
  882.         Key key;
  883.         Value value;
  884.         size_t _depth;
  885.  
  886.         @disable this(this);
  887.  
  888.         void setValue(bool isnew, V)(ref V value)
  889.         {
  890.             static if (isAssignable!(Value, V))
  891.             {
  892.                 static if (false && isnew)
  893.                 {
  894.                     if (!__ctfe)
  895.                         _emplace!isnew(this.value, value);
  896.                     else
  897.                         this.value = value;
  898.                 }
  899.                 else
  900.                 {
  901.                     this.value = value;
  902.                 }
  903.             }
  904.             else
  905.             {
  906.                 _emplace!isnew(this.value, value);
  907.             }
  908.         }
  909.  
  910.         void setKey(bool isnew, K)(ref K key)
  911.         {
  912.             static if (isAssignable!(Key, K))
  913.             {
  914.                 static if (false && isnew)
  915.                 {
  916.                     if (!__ctfe)
  917.                         _emplace!isnew(this.key, key);
  918.                     else
  919.                         this.key = key;
  920.                 }
  921.                 else
  922.                 {
  923.                     this.key = key;
  924.                 }
  925.             }
  926.             else
  927.             {
  928.                 _emplace!isnew(this.key, key);
  929.             }
  930.         }
  931.  
  932.         void dispose()
  933.         {
  934.             static if (isAssignable!(Key, Key))
  935.             {
  936.                 this.key = Key.init;
  937.             }
  938.             else
  939.             {
  940.                 _dispose(this.key);
  941.             }
  942.  
  943.             static if (isAssignable!(Value, Value))
  944.             {
  945.                 this.value = Value.init;
  946.             }
  947.             else
  948.             {
  949.                 _dispose(this.value);
  950.             }
  951.         }
  952.         //swap data without calling postblits
  953.         void swapKV(ref Entry rvl) @trusted
  954.         {
  955.             ubyte[Entry.sizeof] buff;
  956.             buff[] = (cast(ubyte*)&this)[0 .. Entry.sizeof];
  957.             (cast(ubyte*)&this)[0 .. Entry.sizeof] = (cast(ubyte*)&rvl)[0 .. Entry.sizeof];
  958.             (cast(ubyte*)&rvl)[0 .. Entry.sizeof] = buff[];
  959.  
  960.             //swap aux-fields back
  961.             rvl._depth ^= _depth;
  962.             _depth ^= rvl._depth;
  963.             rvl._depth ^= _depth;
  964.         }
  965.  
  966.         @property ubyte occupation() const
  967.         {
  968.             return _depth & 0b11;
  969.         }
  970.  
  971.         @property ubyte occupation(ubyte o)
  972.         {
  973.             _depth &= ~0b11;
  974.             _depth |= o & 0b11;
  975.             return _depth & 0b11;
  976.         }
  977.        
  978.         @property size_t depth() const
  979.         {
  980.             return _depth >> 2;
  981.         }
  982.  
  983.         @property size_t depth(size_t d)
  984.         {
  985.             _depth = (d << 2) | (_depth & 0b11);
  986.             return d;
  987.         }
  988.  
  989.         bool isEqualsKey(ref const(Unqual!Key) key) const
  990.         {
  991.             return this.key == key;
  992.         }
  993.  
  994.         static if(isLvlValueConst && isRvlValueConst)
  995.         {
  996.             bool isEqualsValue(ref const(Unqual!Value) value) const
  997.             {
  998.                 return this.value == value;
  999.             }
  1000.         }
  1001.         else static if(!isLvlValueConst && isRvlValueConst)
  1002.         {
  1003.             bool isEqualsValue(ref const(Unqual!Value) value)
  1004.             {
  1005.                 return this.value == value;
  1006.             }
  1007.         }
  1008.         else static if(isLvlValueConst && !isRvlValueConst)
  1009.         {
  1010.             bool isEqualsValue(ref Value value) const
  1011.             {
  1012.                 return this.value == value;
  1013.             }
  1014.         }
  1015.         else
  1016.         {
  1017.             bool isEqualsValue(ref Value value)
  1018.             {
  1019.                 return this.value == value;
  1020.             }
  1021.         }
  1022.     }
  1023.  
  1024.     static immutable AssociativeArrayHandle handle = AssociativeArrayHandle(&_aaLen,
  1025.                                    &_aaGetX,
  1026.                                    &_aaGetRvalueX,
  1027.                                    &_aaDelX,
  1028.                                    &_aaApply,
  1029.                                    &_aaApply2,
  1030.                                    &_aaEqual,
  1031.                                    &_aaValues,
  1032.                                    &_aaKeys,
  1033.                                    &_aaRehash,
  1034.                                    &_aaDup,
  1035.                                    &_aaRange,
  1036.                                    &_aaRangeEmpty,
  1037.                                    &_aaRangeFrontKey,
  1038.                                    &_aaRangeFrontValue,
  1039.                                    &_aaRangePopFront,
  1040.                                    &_aaGetHash);
  1041.  
  1042.     Impl* impl = null;
  1043.  
  1044.     /**
  1045.         Compiler interface functions:
  1046.         Those functions are defined for compatibility with old compiler extern(C) interface.
  1047.         `Impl` contains a table of functions (unique for each AssociativeArray template instance),
  1048.         and global extern(C) _aaXXX functions accesses to AssociativeArray through this table.
  1049.         Some of this functions undeservedly marked with @trusted: for example _aaGetX calculates key hash,
  1050.         and this code can be unsafe. However extern(C) interface doesn't know static AssociativeArray type,
  1051.         thus it can't determine own safety, but this function can be called from @safe code.
  1052.         This is fundamental trouble of current AA implementation and it's not relevant with this work.
  1053.    
  1054.     */
  1055.     static size_t _aaLen(in void* aa) @trusted pure nothrow
  1056.     {
  1057.         auto _this = *cast(AssociativeArray*)&aa;
  1058.         return _this.length;
  1059.     }
  1060.  
  1061.     static size_t _aaGetHash(in void* aa)
  1062.     {
  1063.         auto _this = *cast(AssociativeArray*)&aa;
  1064.         return _this.toHash();
  1065.     }
  1066.  
  1067.     static void* _aaGetX(void** aa, in void* pkey) @trusted
  1068.     {
  1069.         auto _this = *cast(AssociativeArray*)aa;
  1070.         auto ret = cast(void*)&_this.getLValue(*cast(Key*)pkey).value;
  1071.         *aa = *cast(void**)&_this;
  1072.         return ret;
  1073.     }
  1074.  
  1075.     static inout(void)* _aaGetRvalueX(inout void* aa, in void* pkey) @trusted
  1076.     {
  1077.         auto _this = *cast(AssociativeArray*)&aa;
  1078.         auto e = _this.getRValue(*cast(Key*)pkey);
  1079.         return cast(inout(void)*)(e ? &e.value : null);
  1080.     }
  1081.  
  1082.     static bool _aaDelX(void* aa, in void* pkey) @trusted
  1083.     {
  1084.         auto _this = *cast(AssociativeArray*)&aa;
  1085.         return _this.remove(*cast(Key*)pkey);
  1086.     }
  1087.  
  1088.     static int _aaApply(void* aa, dg_t dg)
  1089.     {
  1090.         auto _this = *cast(AssociativeArray*)&aa;
  1091.         return _this.opApply(cast(int delegate(ref Value))dg);
  1092.     }
  1093.  
  1094.     static int _aaApply2(void* aa, dg2_t dg)
  1095.     {
  1096.         auto _this = *cast(AssociativeArray*)&aa;
  1097.         return _this.opApply(cast(int delegate(ref Key, ref Value))dg);
  1098.     }
  1099.  
  1100.     static int _aaEqual(in void* e1, in void* e2) @trusted
  1101.     {
  1102.         auto lvl = *cast(AssociativeArray*)&e1;
  1103.         auto rvl = *cast(AssociativeArray*)&e2;
  1104.         return lvl == rvl;
  1105.     }
  1106.  
  1107.     static if (isCopyConstructable!Value)
  1108.     {
  1109.         static inout(void)[] _aaValues(inout void* aa)
  1110.         {
  1111.             auto _this = *cast(AssociativeArray*)&aa;
  1112.             auto val = _this.values;
  1113.             return *cast(inout(void)[]*)&val;
  1114.         }
  1115.     }
  1116.     else
  1117.     {
  1118.         static inout(void)[] _aaValues(inout void* aa)
  1119.         {
  1120.             return [];
  1121.         }
  1122.     }
  1123.  
  1124.     static if (isCopyConstructable!Key)
  1125.     {
  1126.         static inout(void)[] _aaKeys(inout void* aa)
  1127.         {
  1128.             auto _this = *cast(AssociativeArray*)&aa;
  1129.             auto key = _this.keys;
  1130.             return *cast(inout(void)[]*)&key;
  1131.         }
  1132.     }
  1133.     else
  1134.     {
  1135.         static inout(void)[] _aaKeys(inout void* aa)
  1136.         {
  1137.             return [];
  1138.         }
  1139.     }
  1140.  
  1141.     static void* _aaRehash(void** paa) pure nothrow
  1142.     {
  1143.         assert(*paa);
  1144.         auto pthis = *cast(AssociativeArray**)&paa;
  1145.         auto _this = *pthis;
  1146.         _this.rehash();
  1147.         *pthis = _this;
  1148.         return *cast(void**)&_this;
  1149.     }
  1150.  
  1151.     static void* _aaDup(void* aa)
  1152.     {
  1153.        auto _this = *cast(AssociativeArray*)&aa;
  1154.        auto copy = _this.dup();
  1155.        return *cast(void**)&copy;
  1156.     }
  1157.  
  1158.     static AARange _aaRange(void* aa) pure nothrow @nogc
  1159.     {
  1160.         auto _this = *cast(AssociativeArray*)&aa;
  1161.         return _this.getRange!(KeyValue.Unknown)().toAARange();
  1162.     }
  1163.  
  1164.     static bool _aaRangeEmpty(AARange r) pure nothrow @nogc
  1165.     {
  1166.         return Range!(Mutability.Mutable).fromAARange(r).empty;
  1167.     }
  1168.  
  1169.     static void* _aaRangeFrontKey(AARange r) pure nothrow @nogc
  1170.     {
  1171.         auto _range = Range!(Mutability.Mutable).fromAARange(r);
  1172.         return cast(void*)&_range.front!(KeyValue.Key)();
  1173.     }
  1174.  
  1175.     static void* _aaRangeFrontValue(AARange r) pure nothrow @nogc
  1176.     {
  1177.         auto _range = Range!(Mutability.Mutable).fromAARange(r);
  1178.         return cast(void*)&_range.front!(KeyValue.Value)();
  1179.     }
  1180.  
  1181.     static void _aaRangePopFront(ref AARange r) pure nothrow @nogc
  1182.     {
  1183.         auto _range = Range!(Mutability.Mutable).fromAARange(r);
  1184.         _range.popFront();
  1185.         r = _range.toAARange();
  1186.     }
  1187. }
  1188.  
  1189. /***************************************************************
  1190.                     compiler interface
  1191. ***************************************************************/
  1192.  
  1193. auto aaLiteral(Key, Value, T...)(ref T args)
  1194. {
  1195.     static if (T.length)
  1196.     {
  1197.         auto aa = AssociativeArray!(Key, Value)(args);
  1198.         return aa.impl;
  1199.     }
  1200.     else
  1201.     {
  1202.         return AssociativeArray!(Key, Value).newImpl();
  1203.     }
  1204. }
  1205.  
  1206. size_t getMaxDepth(Key, Value)(ref AssociativeArray!(Key, Value) aa)
  1207. {
  1208.     size_t max_depth = 0;
  1209.     for (size_t i = 0; i < aa.impl.buckets.length; i++)
  1210.     {
  1211.         if (max_depth < aa.impl.buckets[i].depth)
  1212.             max_depth = aa.impl.buckets[i].depth;
  1213.     }
  1214.     return max_depth;
  1215. }
  1216. extern (D) alias int delegate(void *) dg_t;
  1217. extern (D) alias int delegate(void *, void *) dg2_t;
  1218. extern (D) alias void* function() init_t;
  1219.  
  1220. //!Note: this functions are extern(D) now and doesn't conflict with rt.aaA _aaXXX functions
  1221. extern(C)
  1222. {
  1223.     size_t _aaLen(in void* aa) @trusted pure nothrow
  1224.     {
  1225.         if (!aa)
  1226.             return 0;
  1227.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1228.         return handle.len(aa);
  1229.     }
  1230.  
  1231.     size_t _aaGetHash(in void* aa)
  1232.     {
  1233.         if (!aa)
  1234.             return 0;
  1235.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1236.         return handle.getHash(aa);
  1237.     }
  1238.  
  1239.     void* _aaGetX(void** aa, const TypeInfo ti, in size_t, in void* pkey, init_t init) @trusted
  1240.     in
  1241.     {
  1242.         assert(aa);
  1243.     }
  1244.     body
  1245.     {
  1246.         if (!*aa)
  1247.         {
  1248.             *aa = init();
  1249.         }
  1250.         auto handle = *cast(AssociativeArrayHandle**)*aa;
  1251.         return handle.getX(aa, pkey);
  1252.     }
  1253.  
  1254.     inout(void)* _aaGetRvalueX(inout void* aa, const TypeInfo, in size_t, in void* pkey) @trusted
  1255.     {
  1256.         if (!aa)
  1257.             return null;
  1258.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1259.         return handle.getRvalueX(aa, pkey);
  1260.     }
  1261.  
  1262.     inout(void)* _aaInX(inout void* aa, in TypeInfo unused_1, in void* pkey) @trusted
  1263.     in
  1264.     {
  1265.         assert(aa);
  1266.     }
  1267.     body
  1268.     {
  1269.         return _aaGetRvalueX(aa, unused_1, 0, pkey);
  1270.     }
  1271.  
  1272.     bool _aaDelX(void* aa, in TypeInfo, in void* pkey) @trusted
  1273.     {
  1274.         if (!aa)
  1275.             return false;
  1276.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1277.         return handle.delX(aa, pkey);
  1278.     }
  1279.  
  1280.     int _aaApply(void* aa, in size_t keysize, dg_t dg)
  1281.     {
  1282.         if (!aa)
  1283.             return 0;
  1284.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1285.         return handle.apply(aa, dg);
  1286.     }
  1287.  
  1288.     int _aaApply2(void* aa, in size_t keysize, dg2_t dg)
  1289.     {
  1290.         if (!aa)
  1291.             return 0;
  1292.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1293.         return handle.apply2(aa, dg);
  1294.     }
  1295.  
  1296.     int _aaEqual(in TypeInfo, in void* e1, in void* e2) @trusted
  1297.     in
  1298.     {
  1299.         if (e1 && e2)
  1300.         {
  1301.             auto handle1 = *cast(AssociativeArrayHandle**)e1;
  1302.             auto handle2 = *cast(AssociativeArrayHandle**)e2;
  1303.             assert(handle1 == handle2); //ensure that both objects has a same type
  1304.         }
  1305.  
  1306.     }
  1307.     body
  1308.     {
  1309.         if (!e1 && !e2)
  1310.         {
  1311.             return true;
  1312.         }
  1313.  
  1314.         if (e1 && e2)
  1315.         {
  1316.             auto handle = *cast(AssociativeArrayHandle**)e1;
  1317.             return handle.equal(e1, e2);
  1318.         }
  1319.         return false;
  1320.     }
  1321.  
  1322.  
  1323.     inout(void)[] _aaValues(inout void* aa, in size_t keysize, in size_t valuesize)
  1324.     {
  1325.         if (!aa)
  1326.             return [];
  1327.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1328.         return handle.values(aa);
  1329.     }
  1330.  
  1331.     inout(void)[] _aaKeys(inout void* aa, in size_t keysize)
  1332.     {
  1333.         if (!aa)
  1334.             return [];
  1335.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1336.         return handle.keys(aa);
  1337.     }
  1338.  
  1339.     void* _aaRehash(void** paa, in TypeInfo keyti) pure nothrow
  1340.     in
  1341.     {
  1342.         assert(paa);
  1343.     }
  1344.     body
  1345.     {
  1346.         auto aa = *paa;
  1347.         if (!aa) return null;
  1348.  
  1349.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1350.         return handle.rehash(paa);
  1351.     }
  1352.  
  1353.     void* _aaDup(void* aa, in TypeInfo keyti)
  1354.     {
  1355.         if (!aa)
  1356.             return null;
  1357.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1358.         return handle.dup(aa);
  1359.     }
  1360.  
  1361.  
  1362.     struct AARange
  1363.     {
  1364.         void* impl;
  1365.         void* current;
  1366.     }
  1367.  
  1368.     AARange _aaRange(void* aa) pure nothrow @nogc
  1369.     {
  1370.         if (!aa)
  1371.         {
  1372.             return AARange(null, null);
  1373.         }
  1374.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1375.         return handle.range(aa);
  1376.     }
  1377.  
  1378.     bool _aaRangeEmpty(AARange r) pure nothrow @nogc
  1379.     {
  1380.         auto aa = r.impl;
  1381.         if (!aa)
  1382.         {
  1383.             return true;
  1384.         }
  1385.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1386.         return handle.rangeEmpty(r);
  1387.     }
  1388.  
  1389.     void* _aaRangeFrontKey(AARange r) pure nothrow @nogc
  1390.     in
  1391.     {
  1392.         assert(r.impl && r.current);
  1393.     }
  1394.     body
  1395.     {
  1396.         auto aa = r.impl;
  1397.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1398.         return handle.rangeFrontKey(r);
  1399.     }
  1400.  
  1401.     void* _aaRangeFrontValue(AARange r) pure nothrow @nogc
  1402.     in
  1403.     {
  1404.         assert(r.impl && r.current);
  1405.     }
  1406.     body
  1407.     {
  1408.         auto aa = r.impl;
  1409.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1410.         return handle.rangeFrontValue(r);
  1411.     }
  1412.  
  1413.     void _aaRangePopFront(ref AARange r) pure nothrow @nogc
  1414.     {
  1415.         if (!r.impl)
  1416.             return;
  1417.         auto aa = r.impl;
  1418.         auto handle = *cast(AssociativeArrayHandle**)aa;
  1419.         return handle.rangePopFront(r);
  1420.     }
  1421. }
  1422.  
  1423. version(unittest)
  1424. {
  1425.  
  1426.     int test1(bool isstatic)()
  1427.     {
  1428.         static if (isstatic)
  1429.             static aa1 = AssociativeArray!(real, real)(1,2.0,  3.9L,4UL,  5UL,6);
  1430.         else
  1431.             auto aa1 = AssociativeArray!(real, real)(1,2.0,  3.9L,4UL,  5UL,6);
  1432.  
  1433.         assert(aa1[1] == 2);
  1434.         assert(aa1[3.9] == 4);
  1435.         assert(aa1[5] == 6);
  1436.         assert(aa1.length == 3);
  1437.         aa1[2] = 3;
  1438.         aa1[3.9] = 8;
  1439.         aa1[5] += 4;
  1440.  
  1441.         aa1[8]  = 8;
  1442.         aa1[9]  = 9;
  1443.         aa1[10] = 10;
  1444.  
  1445.         assert(aa1[1] == 2);
  1446.         assert(aa1[2] == 3);
  1447.         assert(aa1[3.9] == 8);
  1448.         assert(aa1[5] == 10);
  1449.         assert(aa1[8] == 8);
  1450.         assert(aa1[9] == 9);
  1451.         assert(aa1[10] == 10);
  1452.  
  1453.         assert(aa1.length == 7);
  1454.         aa1 = aa1.rehash();
  1455.  
  1456.         assert(aa1[1] == 2);
  1457.         assert(aa1[2] == 3);
  1458.         assert(aa1[3.9] == 8);
  1459.         assert(aa1[5] == 10);
  1460.         assert(aa1[8] == 8);
  1461.         assert(aa1[9] == 9);
  1462.         assert(aa1[10] == 10);
  1463.         assert(aa1.length == 7);
  1464.         auto aa2 = aa1.dup;
  1465.  
  1466.         assert(aa2[1] == 2);
  1467.         assert(aa2[2] == 3);
  1468.         assert(aa2[3.9] == 8);
  1469.         assert(aa2[5] == 10);
  1470.         assert(aa2[8] == 8);
  1471.         assert(aa2[9] == 9);
  1472.         assert(aa2[10] == 10);
  1473.         assert(aa2.length == 7);
  1474.  
  1475.         assert(aa1 == aa2);
  1476.  
  1477.         aa2[99] = 99;
  1478.         assert(aa2.length == 8);
  1479.         assert(aa1 != aa2);
  1480.  
  1481.         return 0;
  1482.     }
  1483.  
  1484.     int test2()
  1485.     {
  1486.         auto aa1 = AssociativeArray!(int, int)(1,2,  3,4,  5,6);
  1487.  
  1488.         //test length
  1489.         assert(_aaLen(*cast(void**)&aa1));
  1490.         int newkey = 7;
  1491.  
  1492.         //create a new elem
  1493.         auto pval = _aaGetX(cast(void**)&aa1, null, 0, &newkey, &aaLiteral!(int, int));
  1494.         *cast(int*)pval = 8;
  1495.         assert(aa1[7] == 8);
  1496.         newkey = 1;
  1497.  
  1498.         //find the existing elem
  1499.         pval = _aaGetX(cast(void**)&aa1, null, 0, &newkey, &aaLiteral!(int, int));
  1500.         *cast(int*)pval = 1;
  1501.         assert(aa1[1] == 1);
  1502.  
  1503.         AssociativeArray!(int, int) aa2;
  1504.         auto impl1 = aa2.impl;
  1505.         newkey = 1;
  1506.  
  1507.         //create a new elem in aa with null impl
  1508.         pval = _aaGetX(cast(void**)&aa2, null, 0, &newkey, &aaLiteral!(int, int));
  1509.         *cast(int*)pval = 1;
  1510.         auto impl2 = aa2.impl;
  1511.         assert(impl2 != impl1);
  1512.         assert(aa2[1] == 1);
  1513.  
  1514.         //find the existing elem
  1515.         int key = 3;
  1516.         auto rval1 = _aaGetRvalueX(*cast(void**)&aa1, null, 0, &key);
  1517.         auto rval2 = _aaInX(*cast(void**)&aa1, null, &key);
  1518.         assert(rval1 == rval2 && *cast(int*)rval1 == 4);
  1519.  
  1520.         //find non-existing elem
  1521.         key = 4;
  1522.         rval1 = _aaGetRvalueX(*cast(void**)&aa1, null, 0, &key);
  1523.         rval2 = _aaInX(*cast(void**)&aa1, null, &key);
  1524.         assert(!rval1 && !rval2);
  1525.  
  1526.         //delete non-existing elem
  1527.         auto rem = _aaDelX(*cast(void**)&aa1, null, &key);
  1528.         assert(!rem);
  1529.  
  1530.         //delete the existing elem
  1531.         key = 3;
  1532.         rem = _aaDelX(*cast(void**)&aa1, null, &key);
  1533.         assert(rem);
  1534.         assert(_aaLen(*cast(void**)&aa1) == 3);
  1535.  
  1536.         //test _aaApply and _aaApply2
  1537.         int sum = 0;
  1538.         int dg1(void* v)
  1539.         {
  1540.             sum += *cast(int*)v;
  1541.             return 0;
  1542.         }
  1543.         _aaApply(*cast(void**)&aa1, 0, &dg1);
  1544.         assert(sum == 15);
  1545.  
  1546.         sum = 0;
  1547.         int dg2(void* k, void* v)
  1548.         {
  1549.             sum += *cast(int*)k;
  1550.             sum += *cast(int*)v;
  1551.             return 0;
  1552.         }
  1553.         _aaApply2(*cast(void**)&aa1, 0, &dg2);
  1554.         assert(sum == 28);
  1555.  
  1556.         //test _aaEqual
  1557.         auto aa3 = aa1.dup;
  1558.         assert(_aaEqual(null, *cast(void**)&aa1, *cast(void**)&aa3));
  1559.  
  1560.         int k1 = 1, k2 = 3, v1 = 2, v2 = 4;
  1561.         auto aalit = aaLiteral!(int, int)(k1, v1, k2, v2);
  1562.         return 0;
  1563.     }
  1564.  
  1565.     int test3()
  1566.     {
  1567.         AssociativeArray!(int, int) aa1;
  1568.         auto impl1 = aa1.impl;
  1569.  
  1570.         assert(aa1.length == 0);
  1571.         assert(aa1.keys.length == 0);
  1572.         assert(aa1.values.length == 0);
  1573.         assert(aa1.byKey().empty);
  1574.         assert(aa1.byValue().empty);
  1575.  
  1576.         foreach (cur; aa1)
  1577.         {
  1578.             assert(0);
  1579.         }
  1580.  
  1581.         foreach (key, val; aa1)
  1582.         {
  1583.             assert(0);
  1584.         }
  1585.         auto aa2 = aa1.dup;
  1586.         assert(aa2 == aa1);
  1587.         aa1.rehash;
  1588.         assert(aa1.impl is impl1);
  1589.         AssociativeArray!(int, int) aa3;
  1590.         auto impl2 = aa3.impl;
  1591.         assert(impl1 is impl2);
  1592.         aa3[1] = 2;
  1593.         assert(aa3.impl !is impl2);
  1594.  
  1595.         AssociativeArray!(int, int) aa4;
  1596.         assert(aa4.impl is impl1);
  1597.  
  1598.         aa1 = aa2;
  1599.         assert(aa1.impl == aa2.impl);
  1600.  
  1601.         aa1 = null;
  1602.         assert(aa1.impl == impl1);
  1603.  
  1604.         return 0;
  1605.     }
  1606.  
  1607.     int test4(bool isstatic)()
  1608.     {
  1609.         static if (isstatic)
  1610.             static aa1 = AssociativeArray!(int, int)(1,2,  3,4,  5,6);
  1611.         else
  1612.             auto aa1 = AssociativeArray!(int, int)(1,2,  3,4,  5,6);
  1613.         assert(aa1[1] == 2);
  1614.  
  1615.         assert(aa1.length == 3);
  1616.  
  1617.         auto aa2 = aa1.dup;
  1618.         aa2[1] = 8; //Mutable copy
  1619.  
  1620.         int sum = 0;
  1621.         foreach (key, val; aa1)
  1622.         {
  1623.             sum += key;
  1624.             sum += val;
  1625.         }
  1626.  
  1627.         assert(sum == 21);
  1628.         sum = 0;
  1629.         foreach (cur; aa1.byKey())
  1630.         {
  1631.             sum += cur;
  1632.         }
  1633.         assert(sum == 9);
  1634.         sum = 0;
  1635.         foreach (cur; aa1.keys)
  1636.         {
  1637.             sum += cur;
  1638.         }
  1639.         assert(sum == 9);
  1640.         sum = 0;
  1641.         foreach (cur; aa1.byValue())
  1642.         {
  1643.             sum += cur;
  1644.         }
  1645.         assert(sum == 12);
  1646.         sum = 0;
  1647.         foreach (cur; aa1.values)
  1648.         {
  1649.             sum += cur;
  1650.         }
  1651.         assert(sum == 12);
  1652.         sum = 0;
  1653.         foreach (cur; aa1)
  1654.         {
  1655.             sum += cur;
  1656.         }
  1657.         assert(sum == 12);
  1658.         assert(aa1.get(3, 42) == 4);
  1659.         assert(aa1.get(7, 42) == 42);
  1660.  
  1661.         auto val = 5 in aa1;
  1662.         assert(val && *val == 6);
  1663.         return 0;
  1664.     }
  1665.  
  1666.     unittest
  1667.     {
  1668.         auto runtime1 = test1!false();
  1669.         auto runtime1_1 = test1!true();
  1670.         enum compiletime1 = test1!false();
  1671.         auto runtime2 = test2();
  1672.         auto runtime3 = test3();
  1673.         enum compiletime3 = test3();
  1674.         auto runtime4 = test4!(false)();
  1675.         auto runtime4_1 = test4!(true)();
  1676.         enum compiletime4 = test4!(false)();
  1677.     }
  1678. }
  1679.  
  1680.  
  1681. private enum OpEqualsArg
  1682. {
  1683.     Const,
  1684.     Mutable
  1685. }
  1686.  
  1687. private template lvlOpEqualsArgModififer(T)
  1688. {
  1689.     static if(is(typeof(const(T).init == T.init)))
  1690.     {
  1691.         enum lvlOpEqualsArgModififer = OpEqualsArg.Const;
  1692.     }
  1693.     else
  1694.     {
  1695.         enum lvlOpEqualsArgModififer = OpEqualsArg.Mutable;
  1696.     }
  1697. }
  1698.  
  1699. private template rvlOpEqualsArgModififer(T)
  1700. {
  1701.     static if(is(typeof(T.init == const(T).init)))
  1702.     {
  1703.         enum rvlOpEqualsArgModififer = OpEqualsArg.Const;
  1704.     }
  1705.     else
  1706.     {
  1707.         enum rvlOpEqualsArgModififer = OpEqualsArg.Mutable;
  1708.     }
  1709. }
  1710.  
  1711. private void _emplace(bool new_obj, V1, V2)(ref V1 dst, ref V2 src) @trusted if (is(V1 == struct))
  1712. {
  1713.     static if (new_obj)
  1714.     {
  1715.         (cast(void*)&dst)[0 .. V1.sizeof] = (cast(void*)&src)[0 .. V1.sizeof]; //bitwise copy of object, which already postblitted
  1716.         _postblit(dst);
  1717.     }
  1718.     else
  1719.     {
  1720.         V1 tmp2 = void;
  1721.         (cast(void*)&tmp2)[0 .. V1.sizeof] = (cast(void*)dst)[0 .. V1.sizeof];
  1722.         (cast(void*)&dst)[0 .. V1.sizeof] = (cast(void*)&src)[0 .. V1.sizeof];
  1723.         _postblit(dst);
  1724.         //Now tmp2 contains the old dst value (and it will be destructed)
  1725.     }
  1726. }
  1727.  
  1728. private void _emplace(bool new_obj, V1, V2)(ref V1 dst, ref V2 src) @trusted if (__traits(isStaticArray, V1))
  1729. {
  1730.     static assert(V1.sizeof == V2.sizeof);
  1731.  
  1732.     foreach(i; 0 .. dst.length)
  1733.     {
  1734.         _emplace!(new_obj)(dst[i], src[i]);
  1735.     }
  1736. }
  1737.  
  1738. private void _emplace(bool new_obj, V1, V2)(ref V1 dst, ref V2 src) @trusted if (!__traits(isStaticArray, V1) && !is(V1 == struct))
  1739. {
  1740.     static assert(V1.sizeof == V2.sizeof);
  1741.     *(cast(Unqual!V1*)&dst) = *(cast(Unqual!V1*)&src);
  1742. }
  1743.  
  1744. private void _dispose(V1)(ref V1 dst) @trusted if (is(V1 == struct))
  1745. {
  1746.     V1 tmp = void;
  1747.     V1 init = V1.init;
  1748.     (cast(void*)&tmp)[0 .. V1.sizeof] = (cast(void*)dst)[0 .. V1.sizeof];
  1749.     (cast(void*)&dst)[0 .. V1.sizeof] = (cast(void*)&init)[0 .. V1.sizeof];
  1750. }
  1751.  
  1752. private void _dispose(V1)(ref V1 dst) @trusted if (__traits(isStaticArray, V1))
  1753. {
  1754.     foreach(i; 0 .. dst.length)
  1755.     {
  1756.         _dispose(dst[i]);
  1757.     }
  1758. }
  1759.  
  1760. private void _dispose(V1)(ref V1 dst) @trusted if (!__traits(isStaticArray, V1) && !is(V1 == struct))
  1761. {
  1762.     V1 init;
  1763.     *(cast(Unqual!V1*)&dst) = *(cast(Unqual!V1*)&tmp);
  1764. }
  1765.  
  1766. private void _postblit(V1)(ref V1 obj)
  1767. {
  1768.     static if (__traits(isStaticArray, V1))
  1769.     {
  1770.         foreach(i; 0 .. obj.length)
  1771.         {
  1772.             _postblit(obj[i]);
  1773.         }
  1774.     }
  1775.     else static if(is(V1 == struct) && !__traits(isPOD, V1))
  1776.     {
  1777.         foreach(i, ref _; obj.tupleof)
  1778.         {
  1779.             _postblit(obj.tupleof[i]);
  1780.         }
  1781.         static if (__traits(hasMember, obj, "__postblit"))
  1782.         {
  1783.             obj.__postblit();
  1784.         }
  1785.     }
  1786. }
  1787.  
  1788. private template isCopyConstructable(T)
  1789. {
  1790.     static if (is(typeof({
  1791.         T v;
  1792.         T v2 = v;
  1793.     })))
  1794.     {
  1795.         enum isCopyConstructable = true;
  1796.     }
  1797.     else
  1798.     {
  1799.         enum isCopyConstructable = false;
  1800.     }
  1801. }
  1802.  
  1803. private template isAssignable(V1, V2)
  1804. {
  1805.     static if (__traits(compiles, {V1 val = V1.init; V2 val2 = V2.init; val = val2;}))
  1806.     {
  1807.         enum isAssignable = true;
  1808.     }
  1809.     else
  1810.     {
  1811.         enum isAssignable = false;
  1812.     }
  1813. }
  1814.  
  1815. private enum KeyValue
  1816. {
  1817.     Key = 0,
  1818.     Value = 1,
  1819.     Unknown = 2
  1820. }
  1821.  
  1822. private template commonType(KeyValue kv, T...)
  1823. {
  1824.     static assert(T.length && T.length % 2 == 0);
  1825.  
  1826.     static if (T.length == 2)
  1827.     {
  1828.         alias commonType = T[kv];
  1829.     }
  1830.     else
  1831.     {
  1832.         alias commonType = typeof(true ? T[kv].init : commonType!(kv, T[2 .. $]).init);
  1833.     }
  1834. }
  1835.  
  1836. private struct AssociativeArrayHandle
  1837. {
  1838.     @trusted pure nothrow size_t function(in void* aa) len;
  1839.     @trusted               void* function(void** aa, in void* pkey) getX;
  1840.     @trusted        inout(void)* function(inout void* aa, in void* pkey) getRvalueX;
  1841.     @trusted                bool function(void* aa, in void* pkey) delX;
  1842.                              int function(void* aa, dg_t dg) apply;
  1843.                              int function(void* aa, dg2_t dg) apply2;
  1844.     @trusted                 int function(in void* e1, in void* e2) equal;
  1845.  
  1846.     inout(void)[] function(inout void* p) values;
  1847.     inout(void)[] function(inout void* p) keys;
  1848.     pure nothrow void* function(void** pp) rehash;
  1849.     void* function(void* pp) dup;
  1850.     @nogc pure nothrow AARange function(void* aa)  range;
  1851.     @nogc pure nothrow bool function(AARange r) rangeEmpty;
  1852.     @nogc pure nothrow void* function(AARange r) rangeFrontKey;
  1853.     @nogc pure nothrow void* function(AARange r) rangeFrontValue;
  1854.     @nogc pure nothrow void function(ref AARange r) rangePopFront;
  1855.     size_t function(in void* aa) getHash;
  1856. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!