libphobos/libdruntime/core/internal/container/hashtab.d

   1 /**
   2  * HashTab container for internal usage.
   3  *
   4  * Copyright: Copyright Martin Nowak 2013.
   5  * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
   6  * Authors:   Martin Nowak
   7  */
   8 module core.internal.container.hashtab;
   9
  10 import core.internal.container.array;
  11 static import common = core.internal.container.common;
  12
  13 struct HashTab(Key, Value)
  14 {
  15     static struct Node
  16     {
  17         Key _key;
  18         Value _value;
  19         Node* _next;
  20     }
  21
  22     @disable this(this);
  23
  24     ~this()
  25     {
  26         reset();
  27     }
  28
  29     void reset()
  30     {
  31         foreach (p; _buckets)
  32         {
  33             while (p !is null)
  34             {
  35                 auto pn = p._next;
  36                 common.destroy(*p);
  37                 common.free(p);
  38                 p = pn;
  39             }
  40         }
  41         _buckets.reset();
  42         _length = 0;
  43     }
  44
  45     @property size_t length() const
  46     {
  47         return _length;
  48     }
  49
  50     @property bool empty() const
  51     {
  52         return !_length;
  53     }
  54
  55     void remove(in Key key)
  56     in { assert(key in this); }
  57     do
  58     {
  59         ensureNotInOpApply();
  60
  61         immutable hash = hashOf(key) & mask;
  62         auto pp = &_buckets[hash];
  63         while (*pp)
  64         {
  65             auto p = *pp;
  66             if (p._key == key)
  67             {
  68                 *pp = p._next;
  69                 common.destroy(*p);
  70                 common.free(p);
  71                 if (--_length < _buckets.length && _length >= 4)
  72                     shrink();
  73                 return;
  74             }
  75             else
  76             {
  77                 pp = &p._next;
  78             }
  79         }
  80         assert(0);
  81     }
  82
  83     ref inout(Value) opIndex(Key key) inout
  84     {
  85         return *opBinaryRight!("in")(key);
  86     }
  87
  88     void opIndexAssign(Value value, Key key)
  89     {
  90         *get(key) = value;
  91     }
  92
  93     inout(Value)* opBinaryRight(string op)(const scope Key key) inout
  94         if (op == "in")
  95     {
  96         if (_buckets.length)
  97         {
  98             immutable hash = hashOf(key) & mask;
  99             for (inout(Node)* p = _buckets[hash]; p !is null; p = p._next)
 100             {
 101                 if (p._key == key)
 102                     return &p._value;
 103             }
 104         }
 105         return null;
 106     }
 107
 108     int opApply(scope int delegate(ref Key, ref Value) dg)
 109     {
 110         immutable save = _inOpApply;
 111         _inOpApply = true;
 112         scope (exit) _inOpApply = save;
 113         foreach (p; _buckets)
 114         {
 115             while (p !is null)
 116             {
 117                 if (auto res = dg(p._key, p._value))
 118                     return res;
 119                 p = p._next;
 120             }
 121         }
 122         return 0;
 123     }
 124
 125 private:
 126
 127     Value* get(Key key)
 128     {
 129         if (auto p = opBinaryRight!("in")(key))
 130             return p;
 131
 132         ensureNotInOpApply();
 133
 134         if (!_buckets.length)
 135             _buckets.length = 4;
 136
 137         immutable hash = hashOf(key) & mask;
 138         auto p = cast(Node*)common.xmalloc(Node.sizeof);
 139         common.initialize(*p);
 140         p._key = key;
 141         p._next = _buckets[hash];
 142         _buckets[hash] = p;
 143         if (++_length >= 2 * _buckets.length)
 144             grow();
 145         return &p._value;
 146     }
 147
 148     static hash_t hashOf(const scope ref Key key) @trusted
 149     {
 150         static if (is(Key U : U[]))
 151             return .hashOf(key, 0);
 152         else
 153             return .hashOf((&key)[0 .. 1], 0);
 154     }
 155
 156     @property hash_t mask() const
 157     {
 158         return _buckets.length - 1;
 159     }
 160
 161     void grow()
 162     in
 163     {
 164         assert(_buckets.length);
 165     }
 166     do
 167     {
 168         immutable ocnt = _buckets.length;
 169         immutable nmask = 2 * ocnt - 1;
 170         _buckets.length = 2 * ocnt;
 171         for (size_t i = 0; i < ocnt; ++i)
 172         {
 173             auto pp = &_buckets[i];
 174             while (*pp)
 175             {
 176                 auto p = *pp;
 177
 178                 immutable nidx = hashOf(p._key) & nmask;
 179                 if (nidx != i)
 180                 {
 181                     *pp = p._next;
 182                     p._next = _buckets[nidx];
 183                     _buckets[nidx] = p;
 184                 }
 185                 else
 186                 {
 187                     pp = &p._next;
 188                 }
 189             }
 190         }
 191     }
 192
 193     void shrink()
 194     in
 195     {
 196         assert(_buckets.length >= 2);
 197     }
 198     do
 199     {
 200         immutable ocnt = _buckets.length;
 201         immutable ncnt = ocnt >> 1;
 202         immutable nmask = ncnt - 1;
 203
 204         for (size_t i = ncnt; i < ocnt; ++i)
 205         {
 206             if (auto tail = _buckets[i])
 207             {
 208                 immutable nidx = i & nmask;
 209                 auto pp = &_buckets[nidx];
 210                 while (*pp)
 211                     pp = &(*pp)._next;
 212                 *pp = tail;
 213                 _buckets[i] = null;
 214             }
 215         }
 216         _buckets.length = ncnt;
 217     }
 218
 219     void ensureNotInOpApply()
 220     {
 221         if (_inOpApply)
 222             assert(0, "Invalid HashTab manipulation during opApply iteration.");
 223     }
 224
 225     Array!(Node*) _buckets;
 226     size_t _length;
 227     bool _inOpApply;
 228 }
 229
 230 unittest
 231 {
 232     HashTab!(int, int) tab;
 233
 234     foreach (i; 0 .. 100)
 235         tab[i] = 100 - i;
 236
 237     foreach (i; 0 .. 100)
 238         assert(tab[i] == 100 - i);
 239
 240     foreach (k, v; tab)
 241         assert(v == 100 - k);
 242
 243     foreach (i; 0 .. 50)
 244         tab.remove(2 * i);
 245
 246     assert(tab.length == 50);
 247
 248     foreach (i; 0 .. 50)
 249         assert(tab[2 * i + 1] == 100 - 2 * i - 1);
 250
 251     assert(tab.length == 50);
 252
 253     tab.reset();
 254     assert(tab.empty);
 255     tab[0] = 0;
 256     assert(!tab.empty);
 257     destroy(tab);
 258     assert(tab.empty);
 259
 260     // not copyable
 261     static assert(!__traits(compiles, { HashTab!(int, int) tab2 = tab; }));
 262     HashTab!(int, int) tab2;
 263     static assert(!__traits(compiles, tab = tab2));
 264     static void foo(HashTab!(int, int) copy) {}
 265     static assert(!__traits(compiles, foo(tab)));
 266 }
 267
 268 unittest
 269 {
 270     HashTab!(string, size_t) tab;
 271
 272     tab["foo"] = 0;
 273     assert(tab["foo"] == 0);
 274     ++tab["foo"];
 275     assert(tab["foo"] == 1);
 276     tab["foo"]++;
 277     assert(tab["foo"] == 2);
 278
 279     auto s = "fo";
 280     s ~= "o";
 281     assert(tab[s] == 2);
 282     assert(tab.length == 1);
 283     tab[s] -= 2;
 284     assert(tab[s] == 0);
 285     tab["foo"] = 12;
 286     assert(tab[s] == 12);
 287
 288     tab.remove("foo");
 289     assert(tab.empty);
 290 }
 291
 292 unittest
 293 {
 294     alias RC = common.RC!();
 295     HashTab!(size_t, RC) tab;
 296
 297     size_t cnt;
 298     assert(cnt == 0);
 299     tab[0] = RC(&cnt);
 300     assert(cnt == 1);
 301     tab[1] = tab[0];
 302     assert(cnt == 2);
 303     tab.remove(0);
 304     assert(cnt == 1);
 305     tab.remove(1);
 306     assert(cnt == 0);
 307 }
 308
 309 unittest
 310 {
 311     import core.exception;
 312
 313     HashTab!(uint, uint) tab;
 314     foreach (i; 0 .. 5)
 315         tab[i] = i;
 316     bool thrown;
 317     foreach (k, v; tab)
 318     {
 319         try
 320         {
 321             if (k == 3) tab.remove(k);
 322         }
 323         catch (AssertError e)
 324         {
 325             thrown = true;
 326         }
 327     }
 328     assert(thrown);
 329     assert(tab[3] == 3);
 330 }