gcc/d/dmd/root/aav.c

   1
   2 /* Copyright (C) 2010-2018 by The D Language Foundation, All Rights Reserved
   3  * http://www.digitalmars.com
   4  * Distributed under the Boost Software License, Version 1.0.
   5  * (See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
   6  * https://github.com/D-Programming-Language/dmd/blob/master/src/root/aav.c
   7  */
   8
   9 /**
  10  * Implementation of associative arrays.
  11  *
  12  */
  13
  14 #include "dsystem.h"
  15 #include "aav.h"
  16 #include "rmem.h"
  17
  18
  19 inline size_t hash(size_t a)
  20 {
  21     a ^= (a >> 20) ^ (a >> 12);
  22     return a ^ (a >> 7) ^ (a >> 4);
  23 }
  24
  25 struct aaA
  26 {
  27     aaA *next;
  28     Key key;
  29     Value value;
  30 };
  31
  32 struct AA
  33 {
  34     aaA* *b;
  35     size_t b_length;
  36     size_t nodes;       // total number of aaA nodes
  37     aaA* binit[4];      // initial value of b[]
  38
  39     aaA aafirst;        // a lot of these AA's have only one entry
  40 };
  41
  42 /****************************************************
  43  * Determine number of entries in associative array.
  44  */
  45
  46 size_t dmd_aaLen(AA* aa)
  47 {
  48     return aa ? aa->nodes : 0;
  49 }
  50
  51
  52 /*************************************************
  53  * Get pointer to value in associative array indexed by key.
  54  * Add entry for key if it is not already there, returning a pointer to a null Value.
  55  * Create the associative array if it does not already exist.
  56  */
  57
  58 Value* dmd_aaGet(AA** paa, Key key)
  59 {
  60     //printf("paa = %p\n", paa);
  61
  62     if (!*paa)
  63     {   AA *a = (AA *)mem.xmalloc(sizeof(AA));
  64         a->b = (aaA**)a->binit;
  65         a->b_length = 4;
  66         a->nodes = 0;
  67         a->binit[0] = NULL;
  68         a->binit[1] = NULL;
  69         a->binit[2] = NULL;
  70         a->binit[3] = NULL;
  71         *paa = a;
  72         assert((*paa)->b_length == 4);
  73     }
  74     //printf("paa = %p, *paa = %p\n", paa, *paa);
  75
  76     assert((*paa)->b_length);
  77     size_t i = hash((size_t)key) & ((*paa)->b_length - 1);
  78     aaA** pe = &(*paa)->b[i];
  79     aaA *e;
  80     while ((e = *pe) != NULL)
  81     {
  82         if (key == e->key)
  83             return &e->value;
  84         pe = &e->next;
  85     }
  86
  87     // Not found, create new elem
  88     //printf("create new one\n");
  89
  90     size_t nodes = ++(*paa)->nodes;
  91     e = (nodes != 1) ? (aaA *)mem.xmalloc(sizeof(aaA)) : &(*paa)->aafirst;
  92     //e = new aaA();
  93     e->next = NULL;
  94     e->key = key;
  95     e->value = NULL;
  96     *pe = e;
  97
  98     //printf("length = %d, nodes = %d\n", (*paa)->b_length, nodes);
  99     if (nodes > (*paa)->b_length * 2)
 100     {
 101         //printf("rehash\n");
 102         dmd_aaRehash(paa);
 103     }
 104
 105     return &e->value;
 106 }
 107
 108
 109 /*************************************************
 110  * Get value in associative array indexed by key.
 111  * Returns NULL if it is not already there.
 112  */
 113
 114 Value dmd_aaGetRvalue(AA* aa, Key key)
 115 {
 116     //printf("_aaGetRvalue(key = %p)\n", key);
 117     if (aa)
 118     {
 119         size_t i;
 120         size_t len = aa->b_length;
 121         i = hash((size_t)key) & (len-1);
 122         aaA* e = aa->b[i];
 123         while (e)
 124         {
 125             if (key == e->key)
 126                 return e->value;
 127             e = e->next;
 128         }
 129     }
 130     return NULL;    // not found
 131 }
 132
 133
 134 /********************************************
 135  * Rehash an array.
 136  */
 137
 138 void dmd_aaRehash(AA** paa)
 139 {
 140     //printf("Rehash\n");
 141     if (*paa)
 142     {
 143         AA *aa = *paa;
 144         if (aa)
 145         {
 146             size_t len = aa->b_length;
 147             if (len == 4)
 148                 len = 32;
 149             else
 150                 len *= 4;
 151             aaA** newb = (aaA**)mem.xmalloc(sizeof(aaA)*len);
 152             memset(newb, 0, len * sizeof(aaA*));
 153
 154             for (size_t k = 0; k < aa->b_length; k++)
 155             {   aaA *e = aa->b[k];
 156                 while (e)
 157                 {   aaA* enext = e->next;
 158                     size_t j = hash((size_t)e->key) & (len-1);
 159                     e->next = newb[j];
 160                     newb[j] = e;
 161                     e = enext;
 162                 }
 163             }
 164             if (aa->b != (aaA**)aa->binit)
 165                 mem.xfree(aa->b);
 166
 167             aa->b = newb;
 168             aa->b_length = len;
 169         }
 170     }
 171 }