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