dlls/dbghelp/storage.c

   1 /*
   2  * Various storage structures (pool allocation, vector, hash table)
   3  *
   4  * Copyright (C) 1993, Eric Youngdale.
   5  *               2004, Eric Pouech
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22
  23 #include <assert.h>
  24 #include <stdlib.h>
  25 #include "wine/debug.h"
  26
  27 #include "dbghelp_private.h"
  28
  29 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp);
  30
  31 void pool_init(struct pool* pool, size_t arena_size)
  32 {
  33     pool->heap = HeapCreate(HEAP_NO_SERIALIZE, arena_size, 0);
  34 }
  35
  36 void pool_destroy(struct pool* pool)
  37 {
  38     HeapDestroy(pool->heap);
  39 }
  40
  41 void* pool_alloc(struct pool* pool, size_t len)
  42 {
  43     return HeapAlloc(pool->heap, 0, len);
  44 }
  45
  46 void* pool_realloc(struct pool* pool, void* ptr, size_t len)
  47 {
  48     return ptr ? HeapReAlloc(pool->heap, 0, ptr, len) : pool_alloc(pool, len);
  49 }
  50
  51 char* pool_strdup(struct pool* pool, const char* str)
  52 {
  53     char* ret;
  54     if ((ret = pool_alloc(pool, strlen(str) + 1))) strcpy(ret, str);
  55     return ret;
  56 }
  57
  58 WCHAR* pool_wcsdup(struct pool* pool, const WCHAR* str)
  59 {
  60     WCHAR* ret;
  61     if ((ret = pool_alloc(pool, (wcslen(str) + 1) * sizeof(WCHAR)))) wcscpy(ret, str);
  62     return ret;
  63 }
  64
  65 void vector_init(struct vector* v, unsigned esz, unsigned bucket_sz)
  66 {
  67     v->buckets = NULL;
  68     /* align size on DWORD boundaries */
  69     v->elt_size = (esz + 3) & ~3;
  70     switch (bucket_sz)
  71     {
  72     case    2: v->shift =  1; break;
  73     case    4: v->shift =  2; break;
  74     case    8: v->shift =  3; break;
  75     case   16: v->shift =  4; break;
  76     case   32: v->shift =  5; break;
  77     case   64: v->shift =  6; break;
  78     case  128: v->shift =  7; break;
  79     case  256: v->shift =  8; break;
  80     case  512: v->shift =  9; break;
  81     case 1024: v->shift = 10; break;
  82     default: assert(0);
  83     }
  84     v->num_buckets = 0;
  85     v->buckets_allocated = 0;
  86     v->num_elts = 0;
  87 }
  88
  89 unsigned vector_length(const struct vector* v)
  90 {
  91     return v->num_elts;
  92 }
  93
  94 void* vector_at(const struct vector* v, unsigned pos)
  95 {
  96     unsigned o;
  97
  98     if (pos >= v->num_elts) return NULL;
  99     o = pos & ((1 << v->shift) - 1);
 100     return (char*)v->buckets[pos >> v->shift] + o * v->elt_size;
 101 }
 102
 103 void* vector_add(struct vector* v, struct pool* pool)
 104 {
 105     if (v->num_elts == (v->num_buckets << v->shift))
 106     {
 107         if (v->num_buckets == v->buckets_allocated)
 108         {
 109             /* Double the bucket cache, so it scales well with big vectors.*/
 110             unsigned    new_reserved = v->buckets_allocated ? v->buckets_allocated * 2 : 1;
 111             void*       new;
 112
 113             new = pool_realloc(pool, v->buckets, new_reserved * sizeof(void*));
 114             if (!new) return NULL;
 115             v->buckets = new;
 116             v->buckets_allocated = new_reserved;
 117         }
 118         v->buckets[v->num_buckets] = pool_alloc(pool, v->elt_size << v->shift);
 119         if (!v->buckets[v->num_buckets]) return NULL;
 120         v->num_elts++;
 121         return v->buckets[v->num_buckets++];
 122     }
 123     return vector_at(v, v->num_elts++);
 124 }
 125
 126 /* We construct the sparse array as two vectors (of equal size)
 127  * The first vector (key2index) is the lookup table between the key and
 128  * an index in the second vector (elements)
 129  * When inserting an element, it's always appended in second vector (and
 130  * never moved in memory later on), only the first vector is reordered
 131  */
 132 struct key2index
 133 {
 134     ULONG_PTR           key;
 135     unsigned            index;
 136 };
 137
 138 void sparse_array_init(struct sparse_array* sa, unsigned elt_sz, unsigned bucket_sz)
 139 {
 140     vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
 141     vector_init(&sa->elements, elt_sz, bucket_sz);
 142 }
 143
 144 /******************************************************************
 145  *              sparse_array_lookup
 146  *
 147  * Returns the first index which key is >= at passed key
 148  */
 149 static struct key2index* sparse_array_lookup(const struct sparse_array* sa,
 150                                              ULONG_PTR key, unsigned* idx)
 151 {
 152     struct key2index*   pk2i;
 153     unsigned            low, high;
 154
 155     if (!sa->elements.num_elts)
 156     {
 157         *idx = 0;
 158         return NULL;
 159     }
 160     high = sa->elements.num_elts;
 161     pk2i = vector_at(&sa->key2index, high - 1);
 162     if (pk2i->key < key)
 163     {
 164         *idx = high;
 165         return NULL;
 166     }
 167     if (pk2i->key == key)
 168     {
 169         *idx = high - 1;
 170         return pk2i;
 171     }
 172     low = 0;
 173     pk2i = vector_at(&sa->key2index, low);
 174     if (pk2i->key >= key)
 175     {
 176         *idx = 0;
 177         return pk2i;
 178     }
 179     /* now we have: sa(lowest key) < key < sa(highest key) */
 180     while (low < high)
 181     {
 182         *idx = (low + high) / 2;
 183         pk2i = vector_at(&sa->key2index, *idx);
 184         if (pk2i->key > key)            high = *idx;
 185         else if (pk2i->key < key)       low = *idx + 1;
 186         else                            return pk2i;
 187     }
 188     /* binary search could return exact item, we search for highest one
 189      * below the key
 190      */
 191     if (pk2i->key < key)
 192         pk2i = vector_at(&sa->key2index, ++(*idx));
 193     return pk2i;
 194 }
 195
 196 void*   sparse_array_find(const struct sparse_array* sa, ULONG_PTR key)
 197 {
 198     unsigned            idx;
 199     struct key2index*   pk2i;
 200
 201     if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
 202         return vector_at(&sa->elements, pk2i->index);
 203     return NULL;
 204 }
 205
 206 void*   sparse_array_add(struct sparse_array* sa, ULONG_PTR key,
 207                          struct pool* pool)
 208 {
 209     unsigned            idx, i;
 210     struct key2index*   pk2i;
 211     struct key2index*   to;
 212
 213     pk2i = sparse_array_lookup(sa, key, &idx);
 214     if (pk2i && pk2i->key == key)
 215     {
 216         FIXME("re-adding an existing key\n");
 217         return NULL;
 218     }
 219     to = vector_add(&sa->key2index, pool);
 220     if (pk2i)
 221     {
 222         /* we need to shift vector's content... */
 223         /* let's do it brute force... (FIXME) */
 224         assert(sa->key2index.num_elts >= 2);
 225         for (i = sa->key2index.num_elts - 1; i > idx; i--)
 226         {
 227             pk2i = vector_at(&sa->key2index, i - 1);
 228             *to = *pk2i;
 229             to = pk2i;
 230         }
 231     }
 232
 233     to->key = key;
 234     to->index = sa->elements.num_elts;
 235
 236     return vector_add(&sa->elements, pool);
 237 }
 238
 239 unsigned sparse_array_length(const struct sparse_array* sa)
 240 {
 241     return sa->elements.num_elts;
 242 }
 243
 244 static unsigned hash_table_hash(const char* name, unsigned num_buckets)
 245 {
 246     unsigned    hash = 0;
 247     while (*name)
 248     {
 249         hash += *name++;
 250         hash += (hash << 10);
 251         hash ^= (hash >> 6);
 252     }
 253     hash += (hash << 3);
 254     hash ^= (hash >> 11);
 255     hash += (hash << 15);
 256     return hash % num_buckets;
 257 }
 258
 259 void hash_table_init(struct pool* pool, struct hash_table* ht, unsigned num_buckets)
 260 {
 261     ht->num_elts = 0;
 262     ht->num_buckets = num_buckets;
 263     ht->pool = pool;
 264     ht->buckets = NULL;
 265 }
 266
 267 void hash_table_destroy(struct hash_table* ht)
 268 {
 269 #if defined(USE_STATS)
 270     int                         i;
 271     unsigned                    len;
 272     unsigned                    min = 0xffffffff, max = 0, sq = 0;
 273     struct hash_table_elt*      elt;
 274     double                      mean, variance;
 275
 276     for (i = 0; i < ht->num_buckets; i++)
 277     {
 278         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
 279         if (len < min) min = len;
 280         if (len > max) max = len;
 281         sq += len * len;
 282     }
 283     mean = (double)ht->num_elts / ht->num_buckets;
 284     variance = (double)sq / ht->num_buckets - mean * mean;
 285     FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
 286           ht->num_elts, ht->num_buckets, mean, min, variance, max);
 287
 288     for (i = 0; i < ht->num_buckets; i++)
 289     {
 290         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
 291         if (len == max)
 292         {
 293             FIXME("Longest bucket:\n");
 294             for (elt = ht->buckets[i]; elt; elt = elt->next)
 295                 FIXME("\t%s\n", elt->name);
 296             break;
 297         }
 298
 299     }
 300 #endif
 301 }
 302
 303 void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt)
 304 {
 305     unsigned                    hash = hash_table_hash(elt->name, ht->num_buckets);
 306
 307     if (!ht->buckets)
 308     {
 309         ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
 310         assert(ht->buckets);
 311         memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
 312     }
 313
 314     /* in some cases, we need to get back the symbols of same name in the order
 315      * in which they've been inserted. So insert new elements at the end of the list.
 316      */
 317     if (!ht->buckets[hash].first)
 318     {
 319         ht->buckets[hash].first = elt;
 320     }
 321     else
 322     {
 323         ht->buckets[hash].last->next = elt;
 324     }
 325     ht->buckets[hash].last = elt;
 326     elt->next = NULL;
 327     ht->num_elts++;
 328 }
 329
 330 void hash_table_iter_init(const struct hash_table* ht,
 331                           struct hash_table_iter* hti, const char* name)
 332 {
 333     hti->ht = ht;
 334     if (name)
 335     {
 336         hti->last = hash_table_hash(name, ht->num_buckets);
 337         hti->index = hti->last - 1;
 338     }
 339     else
 340     {
 341         hti->last = ht->num_buckets - 1;
 342         hti->index = -1;
 343     }
 344     hti->element = NULL;
 345 }
 346
 347 void* hash_table_iter_up(struct hash_table_iter* hti)
 348 {
 349     if (!hti->ht->buckets) return NULL;
 350
 351     if (hti->element) hti->element = hti->element->next;
 352     while (!hti->element && hti->index < hti->last)
 353         hti->element = hti->ht->buckets[++hti->index].first;
 354     return hti->element;
 355 }