gcc/d/dmd/root/aav.d

   1 /**
   2  * Associative array implementation.
   3  *
   4  * Copyright: Copyright (C) 1999-2024 by The D Language Foundation, All Rights Reserved
   5  * Authors:   Walter Bright, https://www.digitalmars.com
   6  * License:   $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
   7  * Source:    $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/root/aav.d, root/_aav.d)
   8  * Documentation:  https://dlang.org/phobos/dmd_root_aav.html
   9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/root/aav.d
  10  */
  11
  12 module dmd.root.aav;
  13
  14 import core.stdc.string;
  15 import dmd.root.rmem;
  16
  17 nothrow:
  18
  19 private size_t hash(size_t a) pure nothrow @nogc @safe
  20 {
  21     a ^= (a >> 20) ^ (a >> 12);
  22     return a ^ (a >> 7) ^ (a >> 4);
  23 }
  24
  25 private struct KeyValueTemplate(K,V)
  26 {
  27     K key;
  28     V value;
  29 }
  30
  31 alias Key = void*;
  32 alias Value = void*;
  33
  34 alias KeyValue = KeyValueTemplate!(Key, Value);
  35
  36 private struct aaA
  37 {
  38 private:
  39     aaA* next;
  40     KeyValue keyValue;
  41     alias keyValue this;
  42 }
  43
  44 private struct AA
  45 {
  46 private:
  47     aaA** b;
  48     size_t b_length;
  49     size_t nodes; // total number of aaA nodes
  50     aaA*[4] binit; // initial value of b[]
  51     aaA aafirst; // a lot of these AA's have only one entry
  52 }
  53
  54 /****************************************************
  55  * Determine number of entries in associative array.
  56  */
  57 private size_t dmd_aaLen(const AA* aa) pure nothrow @nogc @safe
  58 {
  59     return aa ? aa.nodes : 0;
  60 }
  61
  62 /*************************************************
  63  * Get pointer to value in associative array indexed by key.
  64  * Add entry for key if it is not already there, returning a pointer to a null Value.
  65  * Create the associative array if it does not already exist.
  66  */
  67 private Value* dmd_aaGet(AA** paa, Key key) pure nothrow
  68 {
  69     //printf("paa = %p\n", paa);
  70     if (!*paa)
  71     {
  72         AA* a = cast(AA*)mem.xmalloc(AA.sizeof);
  73         a.b = cast(aaA**)a.binit;
  74         a.b_length = 4;
  75         a.nodes = 0;
  76         a.binit[0] = null;
  77         a.binit[1] = null;
  78         a.binit[2] = null;
  79         a.binit[3] = null;
  80         *paa = a;
  81         assert((*paa).b_length == 4);
  82     }
  83     //printf("paa = %p, *paa = %p\n", paa, *paa);
  84     assert((*paa).b_length);
  85     size_t i = hash(cast(size_t)key) & ((*paa).b_length - 1);
  86     aaA** pe = &(*paa).b[i];
  87     aaA* e;
  88     while ((e = *pe) !is null)
  89     {
  90         if (key == e.key)
  91             return &e.value;
  92         pe = &e.next;
  93     }
  94     // Not found, create new elem
  95     //printf("create new one\n");
  96     size_t nodes = ++(*paa).nodes;
  97     e = (nodes != 1) ? cast(aaA*)mem.xmalloc(aaA.sizeof) : &(*paa).aafirst;
  98     //e = new aaA();
  99     e.next = null;
 100     e.key = key;
 101     e.value = null;
 102     *pe = e;
 103     //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
 104     if (nodes > (*paa).b_length * 2)
 105     {
 106         //printf("rehash\n");
 107         dmd_aaRehash(paa);
 108     }
 109     return &e.value;
 110 }
 111
 112 /*************************************************
 113  * Get value in associative array indexed by key.
 114  * Returns NULL if it is not already there.
 115  */
 116 private Value dmd_aaGetRvalue(AA* aa, Key key) pure nothrow @nogc
 117 {
 118     //printf("_aaGetRvalue(key = %p)\n", key);
 119     if (aa)
 120     {
 121         size_t i;
 122         size_t len = aa.b_length;
 123         i = hash(cast(size_t)key) & (len - 1);
 124         aaA* e = aa.b[i];
 125         while (e)
 126         {
 127             if (key == e.key)
 128                 return e.value;
 129             e = e.next;
 130         }
 131     }
 132     return null; // not found
 133 }
 134
 135 /**
 136 Gets a range of key/values for `aa`.
 137
 138 Returns: a range of key/values for `aa`.
 139 */
 140 @property auto asRange(AA* aa) pure nothrow @nogc
 141 {
 142     return AARange!(Key, Value)(aa);
 143 }
 144
 145 private struct AARange(K,V)
 146 {
 147     AA* aa;
 148     // current index into bucket array `aa.b`
 149     size_t bIndex;
 150     aaA* current;
 151
 152     this(AA* aa) pure nothrow @nogc scope
 153     {
 154         if (aa)
 155         {
 156             this.aa = aa;
 157             toNext();
 158         }
 159     }
 160
 161     @property bool empty() const pure nothrow @nogc @safe
 162     {
 163         return current is null;
 164     }
 165
 166     @property auto front() const pure nothrow @nogc
 167     {
 168         return cast(KeyValueTemplate!(K,V))current.keyValue;
 169     }
 170
 171     void popFront() pure nothrow @nogc
 172     {
 173         if (current.next)
 174             current = current.next;
 175         else
 176         {
 177             bIndex++;
 178             toNext();
 179         }
 180     }
 181
 182     private void toNext() pure nothrow @nogc
 183     {
 184         for (; bIndex < aa.b_length; bIndex++)
 185         {
 186             if (auto next = aa.b[bIndex])
 187             {
 188                 current = next;
 189                 return;
 190             }
 191         }
 192         current = null;
 193     }
 194 }
 195
 196 unittest
 197 {
 198     AA* aa = null;
 199     foreach(keyValue; aa.asRange)
 200         assert(0);
 201
 202     enum totalKeyLength = 50;
 203     foreach (i; 1 .. totalKeyLength + 1)
 204     {
 205         auto key = cast(void*)i;
 206         {
 207             auto valuePtr = dmd_aaGet(&aa, key);
 208             assert(valuePtr);
 209             *valuePtr = key;
 210         }
 211         bool[totalKeyLength] found;
 212         size_t rangeCount = 0;
 213         foreach (keyValue; aa.asRange)
 214         {
 215             assert(keyValue.key <= key);
 216             assert(keyValue.key == keyValue.value);
 217             rangeCount++;
 218             assert(!found[cast(size_t)keyValue.key - 1]);
 219             found[cast(size_t)keyValue.key - 1] = true;
 220         }
 221         assert(rangeCount == i);
 222     }
 223 }
 224
 225 /********************************************
 226  * Rehash an array.
 227  */
 228 private void dmd_aaRehash(AA** paa) pure nothrow
 229 {
 230     //printf("Rehash\n");
 231     if (*paa)
 232     {
 233         AA* aa = *paa;
 234         if (aa)
 235         {
 236             size_t len = aa.b_length;
 237             if (len == 4)
 238                 len = 32;
 239             else
 240                 len *= 4;
 241             aaA** newb = cast(aaA**)mem.xmalloc(aaA.sizeof * len);
 242             memset(newb, 0, len * (aaA*).sizeof);
 243             for (size_t k = 0; k < aa.b_length; k++)
 244             {
 245                 aaA* e = aa.b[k];
 246                 while (e)
 247                 {
 248                     aaA* enext = e.next;
 249                     size_t j = hash(cast(size_t)e.key) & (len - 1);
 250                     e.next = newb[j];
 251                     newb[j] = e;
 252                     e = enext;
 253                 }
 254             }
 255             if (aa.b != cast(aaA**)aa.binit)
 256                 mem.xfree(aa.b);
 257             aa.b = newb;
 258             aa.b_length = len;
 259         }
 260     }
 261 }
 262
 263 unittest
 264 {
 265     AA* aa = null;
 266     Value v = dmd_aaGetRvalue(aa, null);
 267     assert(!v);
 268     Value* pv = dmd_aaGet(&aa, null);
 269     assert(pv);
 270     *pv = cast(void*)3;
 271     v = dmd_aaGetRvalue(aa, null);
 272     assert(v == cast(void*)3);
 273 }
 274
 275 struct AssocArray(K,V)
 276 {
 277     private AA* aa;
 278
 279     /**
 280     Returns: The number of key/value pairs.
 281     */
 282     @property size_t length() const pure nothrow @nogc @safe
 283     {
 284         return dmd_aaLen(aa);
 285     }
 286
 287     /**
 288     Lookup value associated with `key` and return the address to it. If the `key`
 289     has not been added, it adds it and returns the address to the new value.
 290
 291     Params:
 292         key = key to lookup the value for
 293
 294     Returns: the address to the value associated with `key`. If `key` does not exist, it
 295              is added and the address to the new value is returned.
 296     */
 297     V* getLvalue(const(K) key) pure nothrow
 298     {
 299         return cast(V*)dmd_aaGet(&aa, cast(void*)key);
 300     }
 301
 302     /**
 303     Lookup and return the value associated with `key`, if the `key` has not been
 304     added, it returns null.
 305
 306     Params:
 307         key = key to lookup the value for
 308
 309     Returns: the value associated with `key` if present, otherwise, null.
 310     */
 311     V opIndex(const(K) key) pure nothrow @nogc
 312     {
 313         return cast(V)dmd_aaGetRvalue(aa, cast(void*)key);
 314     }
 315
 316     /**
 317     Gets a range of key/values for `aa`.
 318
 319     Returns: a range of key/values for `aa`.
 320     */
 321     @property auto asRange() pure nothrow @nogc
 322     {
 323         return AARange!(K,V)(aa);
 324     }
 325 }
 326
 327 ///
 328 unittest
 329 {
 330     auto foo = new Object();
 331     auto bar = new Object();
 332
 333     AssocArray!(Object, Object) aa;
 334
 335     assert(aa[foo] is null);
 336     assert(aa.length == 0);
 337
 338     auto fooValuePtr = aa.getLvalue(foo);
 339     *fooValuePtr = bar;
 340
 341     assert(aa[foo] is bar);
 342     assert(aa.length == 1);
 343 }