Added YUV routines needed for v4l driver, and in the future possibly
[wine/gsoc-2012-control.git] / dlls / dbghelp / storage.c
blob025b9f73618f667d62edd2ae6628b3383063645b
1 /*
2 * Various storage structures (pool allocation, vector, hash table)
4 * Copyright (C) 1993, Eric Youngdale.
5 * 2004, Eric Pouech
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 #include "config.h"
24 #include <assert.h>
25 #include <stdlib.h>
26 #include "wine/debug.h"
28 #include "dbghelp_private.h"
29 #ifdef USE_STATS
30 #include <math.h>
31 #endif
33 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp);
35 struct pool_arena
37 struct pool_arena* next;
38 char* current;
41 void pool_init(struct pool* a, unsigned arena_size)
43 a->arena_size = arena_size;
44 a->first = NULL;
47 void pool_destroy(struct pool* pool)
49 struct pool_arena* arena;
50 struct pool_arena* next;
52 #ifdef USE_STATS
53 unsigned alloc, used, num;
55 for (alloc = used = num = 0, arena = pool->first; arena; arena = arena->next)
57 alloc += pool->arena_size;
58 used += arena->current - (char*)arena;
59 num++;
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
66 for (arena = pool->first; arena; arena = next)
68 next = arena->next;
69 HeapFree(GetProcessHeap(), 0, arena);
71 pool_init(pool, 0);
74 void* pool_alloc(struct pool* pool, unsigned len)
76 struct pool_arena** parena;
77 struct pool_arena* arena;
78 void* ret;
80 len = (len + 3) & ~3; /* round up size on DWORD boundary */
81 assert(sizeof(struct pool_arena) + len <= pool->arena_size && len);
83 for (parena = &pool->first; *parena; parena = &(*parena)->next)
85 if ((char*)(*parena) + pool->arena_size - (*parena)->current >= len)
87 ret = (*parena)->current;
88 (*parena)->current += len;
89 return ret;
93 arena = HeapAlloc(GetProcessHeap(), 0, pool->arena_size);
94 if (!arena) {FIXME("OOM\n");return NULL;}
96 *parena = arena;
98 ret = (char*)arena + sizeof(*arena);
99 arena->next = NULL;
100 arena->current = (char*)ret + len;
101 return ret;
104 static struct pool_arena* pool_is_last(struct pool* pool, void* p, unsigned old_size)
106 struct pool_arena* arena;
108 for (arena = pool->first; arena; arena = arena->next)
110 if (arena->current == (char*)p + old_size) return arena;
112 return NULL;
115 void* pool_realloc(struct pool* pool, void* p, unsigned old_size, unsigned new_size)
117 struct pool_arena* arena;
118 void* new;
120 if ((arena = pool_is_last(pool, p, old_size)) &&
121 (char*)p + new_size <= (char*)arena + pool->arena_size)
123 arena->current = (char*)p + new_size;
124 return p;
126 if ((new = pool_alloc(pool, new_size)) && old_size)
127 memcpy(new, p, min(old_size, new_size));
128 return new;
131 char* pool_strdup(struct pool* pool, const char* str)
133 char* ret;
134 if ((ret = pool_alloc(pool, strlen(str) + 1))) strcpy(ret, str);
135 return ret;
138 void vector_init(struct vector* v, unsigned esz, unsigned bucket_sz)
140 v->buckets = NULL;
141 /* align size on DWORD boundaries */
142 v->elt_size = (esz + 3) & ~3;
143 switch (bucket_sz)
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);
157 v->num_buckets = 0;
158 v->num_elts = 0;
161 unsigned vector_length(const struct vector* v)
163 return v->num_elts;
166 void* vector_at(const struct vector* v, unsigned pos)
168 unsigned o;
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;
175 void* vector_add(struct vector* v, struct pool* pool)
177 unsigned ncurr = v->num_elts++;
179 /* check that we don't wrap around */
180 assert(v->num_elts > ncurr);
181 if (ncurr == (v->num_buckets << v->shift))
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++];
189 return vector_at(v, ncurr);
192 static unsigned vector_position(const struct vector* v, const void* elt)
194 int i;
196 for (i = 0; i < v->num_buckets; i++)
198 if (v->buckets[i] <= elt &&
199 (const char*)elt < (const char*)v->buckets[i] + (v->elt_size << v->shift))
201 return (i << v->shift) +
202 ((const char*)elt - (const char*)v->buckets[i]) / v->elt_size;
205 assert(0);
206 return 0;
209 void* vector_iter_up(const struct vector* v, void* elt)
211 unsigned pos;
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);
219 void* vector_iter_down(const struct vector* v, void* elt)
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);
228 unsigned hash_table_hash(const char* name, unsigned num_buckets)
230 unsigned hash = 0;
231 while (*name)
233 hash += *name++;
234 hash += (hash << 10);
235 hash ^= (hash >> 6);
237 hash += (hash << 3);
238 hash ^= (hash >> 11);
239 hash += (hash << 15);
240 return hash % num_buckets;
243 void hash_table_init(struct pool* pool, struct hash_table* ht, unsigned num_buckets)
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*));
251 void hash_table_destroy(struct hash_table* ht)
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;
260 for (i = 0; i < ht->num_buckets; i++)
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;
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++)
275 for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
276 if (len == max)
278 FIXME("Longuest bucket:\n");
279 for (elt = ht->buckets[i]; elt; elt = elt->next)
280 FIXME("\t%s\n", elt->name);
281 break;
285 #endif
286 #endif
289 void hash_table_add(struct hash_table* ht, struct hash_table_elt* elt)
291 unsigned hash = hash_table_hash(elt->name, ht->num_buckets);
292 struct hash_table_elt** p;
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.
297 for (p = &ht->buckets[hash]; *p; p = &((*p)->next));
298 *p = elt;
299 elt->next = NULL;
302 void* hash_table_find(const struct hash_table* ht, const char* name)
304 unsigned hash = hash_table_hash(name, ht->num_buckets);
305 struct hash_table_elt* elt;
307 for (elt = ht->buckets[hash]; elt; elt = elt->next)
308 if (!strcmp(name, elt->name)) return elt;
309 return NULL;
312 void hash_table_iter_init(const struct hash_table* ht,
313 struct hash_table_iter* hti, const char* name)
315 hti->ht = ht;
316 if (name)
318 hti->last = hash_table_hash(name, ht->num_buckets);
319 hti->index = hti->last - 1;
321 else
323 hti->last = ht->num_buckets - 1;
324 hti->index = -1;
326 hti->element = NULL;
329 void* hash_table_iter_up(struct hash_table_iter* hti)
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;