dll/win32/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 "config.h"
  24 #include <assert.h>
  25 #include <stdlib.h>
  26 #include "wine/debug.h"
  27
  28 #include "dbghelp_private.h"
  29 #ifdef USE_STATS
  30 #include <math.h>
  31 #endif
  32
  33 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp);
  34
  35 struct pool_arena
  36 {
  37     struct pool_arena*  next;
  38     char*               current;
  39 };
  40
  41 void pool_init(struct pool* a, unsigned arena_size)
  42 {
  43     a->arena_size = arena_size;
  44     a->first = NULL;
  45 }
  46
  47 void pool_destroy(struct pool* pool)
  48 {
  49     struct pool_arena*  arena;
  50     struct pool_arena*  next;
  51
  52 #ifdef USE_STATS
  53     unsigned    alloc, used, num;
  54
  55     alloc = used = num = 0;
  56     arena = pool->first;
  57     while (arena)
  58     {
  59         alloc += pool->arena_size;
  60         used += arena->current - (char*)arena;
  61         num++;
  62         arena = arena->next;
  63     }
  64     if (alloc == 0) alloc = 1;      /* avoid division by zero */
  65     FIXME("STATS: pool %p has allocated %u kbytes, used %u kbytes in %u arenas,\n"
  66           "\t\t\t\tnon-allocation ratio: %.2f%%\n",
  67           pool, alloc >> 10, used >> 10, num, 100.0 - (float)used / (float)alloc * 100.0);
  68 #endif
  69
  70     arena = pool->first;
  71     while (arena)
  72     {
  73         next = arena->next;
  74         HeapFree(GetProcessHeap(), 0, arena);
  75         arena = next;
  76     }
  77     pool_init(pool, 0);
  78 }
  79
  80 void* pool_alloc(struct pool* pool, unsigned len)
  81 {
  82     struct pool_arena*  arena;
  83     void*               ret;
  84
  85     len = (len + 3) & ~3; /* round up size on DWORD boundary */
  86     assert(sizeof(struct pool_arena) + len <= pool->arena_size && len);
  87
  88     for (arena = pool->first; arena; arena = arena->next)
  89     {
  90         if ((char*)arena + pool->arena_size - arena->current >= len)
  91         {
  92             ret = arena->current;
  93             arena->current += len;
  94             return ret;
  95         }
  96     }
  97
  98     arena = HeapAlloc(GetProcessHeap(), 0, pool->arena_size);
  99     if (!arena) {ERR("OOM\n");return NULL;}
 100
 101     ret = (char*)arena + sizeof(*arena);
 102     arena->next = pool->first;
 103     pool->first = arena;
 104     arena->current = (char*)ret + len;
 105     return ret;
 106 }
 107
 108 char* pool_strdup(struct pool* pool, const char* str)
 109 {
 110     char* ret;
 111     if ((ret = pool_alloc(pool, strlen(str) + 1))) strcpy(ret, str);
 112     return ret;
 113 }
 114
 115 void vector_init(struct vector* v, unsigned esz, unsigned bucket_sz)
 116 {
 117     v->buckets = NULL;
 118     /* align size on DWORD boundaries */
 119     v->elt_size = (esz + 3) & ~3;
 120     switch (bucket_sz)
 121     {
 122     case    2: v->shift =  1; break;
 123     case    4: v->shift =  2; break;
 124     case    8: v->shift =  3; break;
 125     case   16: v->shift =  4; break;
 126     case   32: v->shift =  5; break;
 127     case   64: v->shift =  6; break;
 128     case  128: v->shift =  7; break;
 129     case  256: v->shift =  8; break;
 130     case  512: v->shift =  9; break;
 131     case 1024: v->shift = 10; break;
 132     default: assert(0);
 133     }
 134     v->num_buckets = 0;
 135     v->buckets_allocated = 0;
 136     v->num_elts = 0;
 137 }
 138
 139 unsigned vector_length(const struct vector* v)
 140 {
 141     return v->num_elts;
 142 }
 143
 144 void* vector_at(const struct vector* v, unsigned pos)
 145 {
 146     unsigned o;
 147
 148     if (pos >= v->num_elts) return NULL;
 149     o = pos & ((1 << v->shift) - 1);
 150     return (char*)v->buckets[pos >> v->shift] + o * v->elt_size;
 151 }
 152
 153 void* vector_add(struct vector* v, struct pool* pool)
 154 {
 155     unsigned    ncurr = v->num_elts++;
 156
 157     /* check that we don't wrap around */
 158     assert(v->num_elts > ncurr);
 159     if (ncurr == (v->num_buckets << v->shift))
 160     {
 161         if(v->num_buckets == v->buckets_allocated)
 162         {
 163             /* Double the bucket cache, so it scales well with big vectors.*/
 164             unsigned    new_reserved;
 165             void*       new;
 166
 167             new_reserved = 2*v->buckets_allocated;
 168             if(new_reserved == 0) new_reserved = 1;
 169
 170             /* Don't even try to resize memory.
 171                Pool datastructure is very inefficient with reallocs. */
 172             new = pool_alloc(pool, new_reserved * sizeof(void*));
 173             memcpy(new, v->buckets, v->buckets_allocated * sizeof(void*));
 174             v->buckets = new;
 175             v->buckets_allocated = new_reserved;
 176         }
 177         v->buckets[v->num_buckets] = pool_alloc(pool, v->elt_size << v->shift);
 178         return v->buckets[v->num_buckets++];
 179     }
 180     return vector_at(v, ncurr);
 181 }
 182
 183 /* We construct the sparse array as two vectors (of equal size)
 184  * The first vector (key2index) is the lookup table between the key and
 185  * an index in the second vector (elements)
 186  * When inserting an element, it's always appended in second vector (and
 187  * never moved in memory later on), only the first vector is reordered
 188  */
 189 struct key2index
 190 {
 191     unsigned long       key;
 192     unsigned            index;
 193 };
 194
 195 void sparse_array_init(struct sparse_array* sa, unsigned elt_sz, unsigned bucket_sz)
 196 {
 197     vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
 198     vector_init(&sa->elements, elt_sz, bucket_sz);
 199 }
 200
 201 /******************************************************************
 202  *              sparse_array_lookup
 203  *
 204  * Returns the first index which key is >= at passed key
 205  */
 206 static struct key2index* sparse_array_lookup(const struct sparse_array* sa,
 207                                              unsigned long key, unsigned* idx)
 208 {
 209     struct key2index*   pk2i;
 210     unsigned            low, high;
 211
 212     if (!sa->elements.num_elts)
 213     {
 214         *idx = 0;
 215         return NULL;
 216     }
 217     high = sa->elements.num_elts;
 218     pk2i = vector_at(&sa->key2index, high - 1);
 219     if (pk2i->key < key)
 220     {
 221         *idx = high;
 222         return NULL;
 223     }
 224     if (pk2i->key == key)
 225     {
 226         *idx = high - 1;
 227         return pk2i;
 228     }
 229     low = 0;
 230     pk2i = vector_at(&sa->key2index, low);
 231     if (pk2i->key >= key)
 232     {
 233         *idx = 0;
 234         return pk2i;
 235     }
 236     /* now we have: sa(lowest key) < key < sa(highest key) */
 237     while (low < high)
 238     {
 239         *idx = (low + high) / 2;
 240         pk2i = vector_at(&sa->key2index, *idx);
 241         if (pk2i->key > key)            high = *idx;
 242         else if (pk2i->key < key)       low = *idx + 1;
 243         else                            return pk2i;
 244     }
 245     /* binary search could return exact item, we search for highest one
 246      * below the key
 247      */
 248     if (pk2i->key < key)
 249         pk2i = vector_at(&sa->key2index, ++(*idx));
 250     return pk2i;
 251 }
 252
 253 void*   sparse_array_find(const struct sparse_array* sa, unsigned long key)
 254 {
 255     unsigned            idx;
 256     struct key2index*   pk2i;
 257
 258     if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
 259         return vector_at(&sa->elements, pk2i->index);
 260     return NULL;
 261 }
 262
 263 void*   sparse_array_add(struct sparse_array* sa, unsigned long key,
 264                          struct pool* pool)
 265 {
 266     unsigned            idx, i;
 267     struct key2index*   pk2i;
 268     struct key2index*   to;
 269
 270     pk2i = sparse_array_lookup(sa, key, &idx);
 271     if (pk2i && pk2i->key == key)
 272     {
 273         FIXME("re adding an existing key\n");
 274         return NULL;
 275     }
 276     to = vector_add(&sa->key2index, pool);
 277     if (pk2i)
 278     {
 279         /* we need to shift vector's content... */
 280         /* let's do it brute force... (FIXME) */
 281         assert(sa->key2index.num_elts >= 2);
 282         for (i = sa->key2index.num_elts - 1; i > idx; i--)
 283         {
 284             pk2i = vector_at(&sa->key2index, i - 1);
 285             *to = *pk2i;
 286             to = pk2i;
 287         }
 288     }
 289
 290     to->key = key;
 291     to->index = sa->elements.num_elts;
 292
 293     return vector_add(&sa->elements, pool);
 294 }
 295
 296 unsigned sparse_array_length(const struct sparse_array* sa)
 297 {
 298     return sa->elements.num_elts;
 299 }
 300
 301 unsigned hash_table_hash(const char* name, unsigned num_buckets)
 302 {
 303     unsigned    hash = 0;
 304     while (*name)
 305     {
 306         hash += *name++;
 307         hash += (hash << 10);
 308         hash ^= (hash >> 6);
 309     }
 310     hash += (hash << 3);
 311     hash ^= (hash >> 11);
 312     hash += (hash << 15);
 313     return hash % num_buckets;
 314 }
 315
 316 void hash_table_init(struct pool* pool, struct hash_table* ht, unsigned num_buckets)
 317 {
 318     ht->num_elts = 0;
 319     ht->num_buckets = num_buckets;
 320     ht->pool = pool;
 321     ht->buckets = NULL;
 322 }
 323
 324 void hash_table_destroy(struct hash_table* ht)
 325 {
 326 #if defined(USE_STATS)
 327     int                         i;
 328     unsigned                    len;
 329     unsigned                    min = 0xffffffff, max = 0, sq = 0;
 330     struct hash_table_elt*      elt;
 331     double                      mean, variance;
 332
 333     for (i = 0; i < ht->num_buckets; i++)
 334     {
 335         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
 336         if (len < min) min = len;
 337         if (len > max) max = len;
 338         sq += len * len;
 339     }
 340     mean = (double)ht->num_elts / ht->num_buckets;
 341     variance = (double)sq / ht->num_buckets - mean * mean;
 342     FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
 343           ht->num_elts, ht->num_buckets, mean, min, variance, max);
 344 #if 1
 345     for (i = 0; i < ht->num_buckets; i++)
 346     {
 347         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
 348         if (len == max)
 349         {
 350             FIXME("Longuest bucket:\n");
 351             for (elt = ht->buckets[i]; elt; elt = elt->next)
 352                 FIXME("\t%s\n", elt->name);
 353             break;
 354         }
 355
 356     }
 357 #endif
 358 #endif
 359 }
 360
 361 void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt)
 362 {
 363     unsigned                    hash = hash_table_hash(elt->name, ht->num_buckets);
 364
 365     if (!ht->buckets)
 366     {
 367         ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
 368         assert(ht->buckets);
 369         memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
 370     }
 371
 372     /* in some cases, we need to get back the symbols of same name in the order
 373      * in which they've been inserted. So insert new elements at the end of the list.
 374      */
 375     if (!ht->buckets[hash].first)
 376     {
 377         ht->buckets[hash].first = elt;
 378     }
 379     else
 380     {
 381         ht->buckets[hash].last->next = elt;
 382     }
 383     ht->buckets[hash].last = elt;
 384     elt->next = NULL;
 385     ht->num_elts++;
 386 }
 387
 388 void hash_table_iter_init(const struct hash_table* ht,
 389                           struct hash_table_iter* hti, const char* name)
 390 {
 391     hti->ht = ht;
 392     if (name)
 393     {
 394         hti->last = hash_table_hash(name, ht->num_buckets);
 395         hti->index = hti->last - 1;
 396     }
 397     else
 398     {
 399         hti->last = ht->num_buckets - 1;
 400         hti->index = -1;
 401     }
 402     hti->element = NULL;
 403 }
 404
 405 void* hash_table_iter_up(struct hash_table_iter* hti)
 406 {
 407     if (!hti->ht->buckets) return NULL;
 408
 409     if (hti->element) hti->element = hti->element->next;
 410     while (!hti->element && hti->index < hti->last)
 411         hti->element = hti->ht->buckets[++hti->index].first;
 412     return hti->element;
 413 }