2 * Various storage structures (pool allocation, vector, hash table)
4 * Copyright (C) 1993, Eric Youngdale.
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
26 #include "wine/debug.h"
28 #include "dbghelp_private.h"
33 WINE_DEFAULT_DEBUG_CHANNEL(dbghelp
);
37 struct pool_arena
* next
;
41 void pool_init(struct pool
* a
, unsigned arena_size
)
43 a
->arena_size
= arena_size
;
47 void pool_destroy(struct pool
* pool
)
49 struct pool_arena
* arena
;
50 struct pool_arena
* next
;
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
;
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);
66 for (arena
= pool
->first
; arena
; arena
= next
)
69 HeapFree(GetProcessHeap(), 0, arena
);
74 void* pool_alloc(struct pool
* pool
, unsigned len
)
76 struct pool_arena
** parena
;
77 struct pool_arena
* arena
;
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
;
93 arena
= HeapAlloc(GetProcessHeap(), 0, pool
->arena_size
);
94 if (!arena
) {FIXME("OOM\n");return NULL
;}
98 ret
= (char*)arena
+ sizeof(*arena
);
100 arena
->current
= (char*)ret
+ len
;
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
;
115 void* pool_realloc(struct pool
* pool
, void* p
, unsigned old_size
, unsigned new_size
)
117 struct pool_arena
* arena
;
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
;
126 if ((new = pool_alloc(pool
, new_size
)) && old_size
)
127 memcpy(new, p
, min(old_size
, new_size
));
131 char* pool_strdup(struct pool
* pool
, const char* str
)
134 if ((ret
= pool_alloc(pool
, strlen(str
) + 1))) strcpy(ret
, str
);
138 void vector_init(struct vector
* v
, unsigned esz
, unsigned bucket_sz
)
141 /* align size on DWORD boundaries */
142 v
->elt_size
= (esz
+ 3) & ~3;
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;
161 unsigned vector_length(const struct vector
* v
)
166 void* vector_at(const struct vector
* v
, unsigned pos
)
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
)
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
;
209 void* vector_iter_up(const struct vector
* v
, void* elt
)
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
)
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
)
234 hash
+= (hash
<< 10);
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
*));
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)
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
;
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
);
273 for (i
= 0; i
< ht
->num_buckets
; i
++)
275 for (len
= 0, elt
= ht
->buckets
[i
]; elt
; elt
= elt
->next
) len
++;
278 FIXME("Longuest bucket:\n");
279 for (elt
= ht
->buckets
[i
]; elt
; elt
= elt
->next
)
280 FIXME("\t%s\n", elt
->name
);
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
));
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
;
312 void hash_table_iter_init(const struct hash_table
* ht
,
313 struct hash_table_iter
* hti
, const char* name
)
318 hti
->last
= hash_table_hash(name
, ht
->num_buckets
);
319 hti
->index
= hti
->last
- 1;
323 hti
->last
= ht
->num_buckets
- 1;
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
];