winhttp: Add the remaining completion notifications.
[wine] / 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     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) {FIXME("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     struct hash_table_elt**     p;
365
366     if (!ht->buckets)
367     {
368         ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_elt*));
369         assert(ht->buckets);
370         memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_elt*));
371     }
372
373     /* in some cases, we need to get back the symbols of same name in the order
374      * in which they've been inserted. So insert new elements at the end of the list.
375      */
376     for (p = &ht->buckets[hash]; *p; p = &((*p)->next));
377     *p = elt;
378     elt->next = NULL;
379     ht->num_elts++;
380 }
381
382 void* hash_table_find(const struct hash_table* ht, const char* name)
383 {
384     unsigned                    hash = hash_table_hash(name, ht->num_buckets);
385     struct hash_table_elt*      elt;
386
387     if(!ht->buckets) return NULL;
388
389     for (elt = ht->buckets[hash]; elt; elt = elt->next)
390         if (!strcmp(name, elt->name)) return elt;
391     return NULL;
392 }
393
394 void hash_table_iter_init(const struct hash_table* ht, 
395                           struct hash_table_iter* hti, const char* name)
396 {
397     hti->ht = ht;
398     if (name)
399     {
400         hti->last = hash_table_hash(name, ht->num_buckets);
401         hti->index = hti->last - 1;
402     }
403     else
404     {
405         hti->last = ht->num_buckets - 1;
406         hti->index = -1;
407     }
408     hti->element = NULL;
409 }
410
411 void* hash_table_iter_up(struct hash_table_iter* hti)
412 {
413     if(!hti->ht->buckets) return NULL;
414
415     if (hti->element) hti->element = hti->element->next;
416     while (!hti->element && hti->index < hti->last) 
417         hti->element = hti->ht->buckets[++hti->index];
418     return hti->element;
419 }