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