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