advapi32: Implement and test SystemFunction030.
[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     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 unsigned hash_table_hash(const char* name, unsigned num_buckets)
229 {
230     unsigned    hash = 0;
231     while (*name)
232     {
233         hash += *name++;
234         hash += (hash << 10);
235         hash ^= (hash >> 6);
236     }
237     hash += (hash << 3);
238     hash ^= (hash >> 11);
239     hash += (hash << 15);
240     return hash % num_buckets;
241 }
242
243 void hash_table_init(struct pool* pool, struct hash_table* ht, unsigned num_buckets)
244 {
245     ht->buckets = pool_alloc(pool, num_buckets * sizeof(struct hash_table_elt*));
246     assert(ht->buckets);
247     ht->num_buckets = num_buckets;
248     memset(ht->buckets, 0, num_buckets * sizeof(struct hash_table_elt*));
249 }
250
251 void hash_table_destroy(struct hash_table* ht)
252 {
253 #if defined(USE_STATS)
254     int                         i;
255     unsigned                    len;
256     unsigned                    num = 0, min = 0xffffffff, max = 0, sq = 0;
257     struct hash_table_elt*      elt;
258     double                      mean, variance;
259
260     for (i = 0; i < ht->num_buckets; i++)
261     {
262         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
263         if (len < min) min = len;
264         if (len > max) max = len;
265         num += len;
266         sq += len * len;
267     }
268     mean = (double)num / ht->num_buckets;
269     variance = (double)sq / ht->num_buckets - mean * mean;
270     FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
271           num, ht->num_buckets, mean, min, variance, max);
272 #if 1
273     for (i = 0; i < ht->num_buckets; i++)
274     {
275         for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
276         if (len == max)
277         {
278             FIXME("Longuest bucket:\n");
279             for (elt = ht->buckets[i]; elt; elt = elt->next)
280                 FIXME("\t%s\n", elt->name);
281             break;
282         }
283
284     }
285 #endif
286 #endif
287 }
288
289 void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt)
290 {
291     unsigned                    hash = hash_table_hash(elt->name, ht->num_buckets);
292     struct hash_table_elt**     p;
293
294     /* in some cases, we need to get back the symbols of same name in the order
295      * in which they've been inserted. So insert new elements at the end of the list.
296      */
297     for (p = &ht->buckets[hash]; *p; p = &((*p)->next));
298     *p = elt;
299     elt->next = NULL;
300 }
301
302 void* hash_table_find(const struct hash_table* ht, const char* name)
303 {
304     unsigned                    hash = hash_table_hash(name, ht->num_buckets);
305     struct hash_table_elt*      elt;
306
307     for (elt = ht->buckets[hash]; elt; elt = elt->next)
308         if (!strcmp(name, elt->name)) return elt;
309     return NULL;
310 }
311
312 void hash_table_iter_init(const struct hash_table* ht, 
313                           struct hash_table_iter* hti, const char* name)
314 {
315     hti->ht = ht;
316     if (name)
317     {
318         hti->last = hash_table_hash(name, ht->num_buckets);
319         hti->index = hti->last - 1;
320     }
321     else
322     {
323         hti->last = ht->num_buckets - 1;
324         hti->index = -1;
325     }
326     hti->element = NULL;
327 }
328
329 void* hash_table_iter_up(struct hash_table_iter* hti)
330 {
331     if (hti->element) hti->element = hti->element->next;
332     while (!hti->element && hti->index < hti->last) 
333         hti->element = hti->ht->buckets[++hti->index];
334     return hti->element;
335 }