1 2/* Copyright (C) 2010-2019 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 19inline size_t hash(size_t a) 20{ 21 a ^= (a >> 20) ^ (a >> 12); 22 return a ^ (a >> 7) ^ (a >> 4); 23} 24 25struct aaA 26{ 27 aaA *next; 28 Key key; 29 Value value; 30}; 31 32struct 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 46size_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 58Value* 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 114Value 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 138void 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} 172