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