ReactOS 0.4.15-dev-5666-gc548b97
storage.c File Reference
#include <assert.h>
#include <stdlib.h>
#include "wine/debug.h"
#include "dbghelp_private.h"
Include dependency graph for storage.c:

Go to the source code of this file.

Classes

struct  pool_arena
 
struct  key2index
 

Functions

 WINE_DEFAULT_DEBUG_CHANNEL (dbghelp)
 
void pool_init (struct pool *a, size_t arena_size)
 
void pool_destroy (struct pool *pool)
 
voidpool_alloc (struct pool *pool, size_t len)
 
charpool_strdup (struct pool *pool, const char *str)
 
void vector_init (struct vector *v, unsigned esz, unsigned bucket_sz)
 
unsigned vector_length (const struct vector *v)
 
voidvector_at (const struct vector *v, unsigned pos)
 
voidvector_add (struct vector *v, struct pool *pool)
 
void sparse_array_init (struct sparse_array *sa, unsigned elt_sz, unsigned bucket_sz)
 
static struct key2indexsparse_array_lookup (const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
 
voidsparse_array_find (const struct sparse_array *sa, ULONG_PTR key)
 
voidsparse_array_add (struct sparse_array *sa, ULONG_PTR key, struct pool *pool)
 
unsigned sparse_array_length (const struct sparse_array *sa)
 
static unsigned hash_table_hash (const char *name, unsigned num_buckets)
 
void hash_table_init (struct pool *pool, struct hash_table *ht, unsigned num_buckets)
 
void hash_table_destroy (struct hash_table *ht)
 
void hash_table_add (struct hash_table *ht, struct hash_table_elt *elt)
 
void hash_table_iter_init (const struct hash_table *ht, struct hash_table_iter *hti, const char *name)
 
voidhash_table_iter_up (struct hash_table_iter *hti)
 

Function Documentation

◆ hash_table_add()

void hash_table_add ( struct hash_table ht,
struct hash_table_elt elt 
)

Definition at line 378 of file storage.c.

379{
380 unsigned hash = hash_table_hash(elt->name, ht->num_buckets);
381
382 if (!ht->buckets)
383 {
384 ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
385 assert(ht->buckets);
386 memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
387 }
388
389 /* in some cases, we need to get back the symbols of same name in the order
390 * in which they've been inserted. So insert new elements at the end of the list.
391 */
392 if (!ht->buckets[hash].first)
393 {
394 ht->buckets[hash].first = elt;
395 }
396 else
397 {
398 ht->buckets[hash].last->next = elt;
399 }
400 ht->buckets[hash].last = elt;
401 elt->next = NULL;
402 ht->num_elts++;
403}
static unsigned hash_table_hash(const char *name, unsigned num_buckets)
Definition: storage.c:319
void * pool_alloc(struct pool *pool, size_t len)
Definition: storage.c:89
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
static const struct newhuff ht[]
Definition: huffman.h:296
#define memset(x, y, z)
Definition: compat.h:39
struct hash_table_elt * next
const char * name
Definition: _hash_fun.h:40

Referenced by elf_hash_symtab(), macho_stabs_def_cb(), pev_set_value(), symt_add_module_ht(), symt_new_basic(), symt_new_typedef(), symt_new_udt(), and symt_ptr2index().

◆ hash_table_destroy()

void hash_table_destroy ( struct hash_table ht)

Definition at line 342 of file storage.c.

343{
344#if defined(USE_STATS)
345 int i;
346 unsigned len;
347 unsigned min = 0xffffffff, max = 0, sq = 0;
348 struct hash_table_elt* elt;
349 double mean, variance;
350
351 for (i = 0; i < ht->num_buckets; i++)
352 {
353 for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
354 if (len < min) min = len;
355 if (len > max) max = len;
356 sq += len * len;
357 }
358 mean = (double)ht->num_elts / ht->num_buckets;
359 variance = (double)sq / ht->num_buckets - mean * mean;
360 FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
361 ht->num_elts, ht->num_buckets, mean, min, variance, max);
362
363 for (i = 0; i < ht->num_buckets; i++)
364 {
365 for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
366 if (len == max)
367 {
368 FIXME("Longest bucket:\n");
369 for (elt = ht->buckets[i]; elt; elt = elt->next)
370 FIXME("\t%s\n", elt->name);
371 break;
372 }
373
374 }
375#endif
376}
#define FIXME(fmt,...)
Definition: debug.h:111
GLenum GLsizei len
Definition: glext.h:6722
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static const char mbstate_t *static wchar_t const char mbstate_t *static const wchar_t int *static double
Definition: string.c:80
#define min(a, b)
Definition: monoChain.cc:55
#define max(a, b)
Definition: svc.c:63

Referenced by module_remove(), and module_reset_debug_info().

◆ hash_table_hash()

static unsigned hash_table_hash ( const char name,
unsigned  num_buckets 
)
static

Definition at line 319 of file storage.c.

320{
321 unsigned hash = 0;
322 while (*name)
323 {
324 hash += *name++;
325 hash += (hash << 10);
326 hash ^= (hash >> 6);
327 }
328 hash += (hash << 3);
329 hash ^= (hash >> 11);
330 hash += (hash << 15);
331 return hash % num_buckets;
332}
Definition: name.c:39

Referenced by hash_table_add(), and hash_table_iter_init().

◆ hash_table_init()

void hash_table_init ( struct pool pool,
struct hash_table ht,
unsigned  num_buckets 
)

Definition at line 334 of file storage.c.

335{
336 ht->num_elts = 0;
337 ht->num_buckets = num_buckets;
338 ht->pool = pool;
339 ht->buckets = NULL;
340}

Referenced by elf_load_debug_info(), macho_load_debug_info(), module_new(), and pev_init().

◆ hash_table_iter_init()

void hash_table_iter_init ( const struct hash_table ht,
struct hash_table_iter hti,
const char name 
)

Definition at line 405 of file storage.c.

407{
408 hti->ht = ht;
409 if (name)
410 {
411 hti->last = hash_table_hash(name, ht->num_buckets);
412 hti->index = hti->last - 1;
413 }
414 else
415 {
416 hti->last = ht->num_buckets - 1;
417 hti->index = -1;
418 }
419 hti->element = NULL;
420}
struct hash_table_elt * element
const struct hash_table * ht

Referenced by codeview_add_type_struct(), elf_finish_stabs_info(), elf_lookup_symtab(), elf_new_public_symbols(), elf_new_wine_thunks(), find_name(), macho_finish_stabs(), pe_locate_with_coff_symbol_table(), pev_get_val(), pev_set_value(), SymEnumLines(), symt_enum_module(), symt_find_type_by_name(), and symt_ptr2index().

◆ hash_table_iter_up()

void * hash_table_iter_up ( struct hash_table_iter hti)

Definition at line 422 of file storage.c.

423{
424 if (!hti->ht->buckets) return NULL;
425
426 if (hti->element) hti->element = hti->element->next;
427 while (!hti->element && hti->index < hti->last)
428 hti->element = hti->ht->buckets[++hti->index].first;
429 return hti->element;
430}

Referenced by codeview_add_type_struct(), elf_finish_stabs_info(), elf_lookup_symtab(), elf_new_public_symbols(), elf_new_wine_thunks(), find_name(), macho_finish_stabs(), pe_locate_with_coff_symbol_table(), pev_get_val(), pev_set_value(), SymEnumLines(), symt_enum_module(), symt_find_type_by_name(), and symt_ptr2index().

◆ pool_alloc()

void * pool_alloc ( struct pool pool,
size_t  len 
)

Definition at line 89 of file storage.c.

90{
91 struct pool_arena* arena;
92 void* ret;
93 size_t size;
94
95 len = (len + 3) & ~3; /* round up size on DWORD boundary */
96
98 {
99 if (arena->end - arena->current >= len)
100 {
101 ret = arena->current;
102 arena->current += len;
103 if (arena->current + 16 >= arena->end)
104 {
105 list_remove( &arena->entry );
106 list_add_tail( &pool->arena_full, &arena->entry );
107 }
108 return ret;
109 }
110 }
111
112 size = max( pool->arena_size, len );
113 arena = HeapAlloc(GetProcessHeap(), 0, size + sizeof(struct pool_arena));
114 if (!arena) return NULL;
115
116 ret = arena + 1;
117 arena->current = (char*)ret + len;
118 arena->end = (char*)ret + size;
119 if (arena->current + 16 >= arena->end)
120 list_add_tail( &pool->arena_full, &arena->entry );
121 else
122 list_add_head( &pool->arena_list, &arena->entry );
123 return ret;
124}
static void list_remove(struct list_entry *entry)
Definition: list.h:90
static void list_add_tail(struct list_entry *head, struct list_entry *entry)
Definition: list.h:83
static void list_add_head(struct list_entry *head, struct list_entry *entry)
Definition: list.h:76
#define GetProcessHeap()
Definition: compat.h:736
#define HeapAlloc
Definition: compat.h:733
GLsizeiptr size
Definition: glext.h:5919
uint32_t entry
Definition: isohybrid.c:63
#define LIST_FOR_EACH_ENTRY(elem, list, type, field)
Definition: list.h:198
struct list entry
Definition: storage.c:38
char * current
Definition: storage.c:39
char * end
Definition: storage.c:40
struct list arena_list
size_t arena_size
struct list arena_full
int ret

Referenced by dwarf2_compute_location_attr(), dwarf2_get_cpp_name(), dwarf2_parse_abbrev_set(), dwarf2_parse_line_numbers(), dwarf2_parse_variable(), dwarf2_read_one_debug_info(), elf_hash_symtab(), hash_table_add(), macho_stabs_def_cb(), pev_set_value(), pool_strdup(), source_new(), symt_add_enum_element(), symt_add_func_local(), symt_add_function_point(), symt_add_function_signature_parameter(), symt_add_udt_element(), symt_new_array(), symt_new_basic(), symt_new_compiland(), symt_new_constant(), symt_new_enum(), symt_new_function(), symt_new_function_signature(), symt_new_global_variable(), symt_new_label(), symt_new_pointer(), symt_new_public(), symt_new_thunk(), symt_new_typedef(), symt_new_udt(), symt_open_func_block(), symt_ptr2index(), and vector_add().

◆ pool_destroy()

void pool_destroy ( struct pool pool)

Definition at line 50 of file storage.c.

51{
52 struct pool_arena* arena;
53 struct pool_arena* next;
54
55#ifdef USE_STATS
56 size_t alloc, used, num;
57
58 alloc = used = num = 0;
60 {
61 alloc += arena->end - (char *)arena;
62 used += arena->current - (char*)arena;
63 num++;
64 }
66 {
67 alloc += arena->end - (char *)arena;
68 used += arena->current - (char*)arena;
69 num++;
70 }
71 if (alloc == 0) alloc = 1; /* avoid division by zero */
72 FIXME("STATS: pool %p has allocated %u kbytes, used %u kbytes in %u arenas, non-allocation ratio: %.2f%%\n",
73 pool, (unsigned)(alloc >> 10), (unsigned)(used >> 10), (unsigned)num,
74 100.0 - (float)used / (float)alloc * 100.0);
75#endif
76
78 {
79 list_remove( &arena->entry );
80 HeapFree(GetProcessHeap(), 0, arena);
81 }
83 {
84 list_remove( &arena->entry );
85 HeapFree(GetProcessHeap(), 0, arena);
86 }
87}
static int used
Definition: adh-main.c:39
#define HeapFree(x, y, z)
Definition: compat.h:735
GLuint GLuint num
Definition: glext.h:9618
static unsigned __int64 next
Definition: rand_nt.c:6
#define alloc
Definition: rosglue.h:13
#define LIST_FOR_EACH_ENTRY_SAFE(cursor, cursor2, list, type, field)
Definition: list.h:204

Referenced by dwarf2_parse_compilation_unit(), elf_load_debug_info(), macho_load_debug_info(), module_remove(), pev_free(), and rsym_parse().

◆ pool_init()

void pool_init ( struct pool a,
size_t  arena_size 
)

Definition at line 43 of file storage.c.

44{
45 list_init( &a->arena_list );
46 list_init( &a->arena_full );
47 a->arena_size = arena_size;
48}
static void list_init(struct list_entry *head)
Definition: list.h:51
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204

Referenced by dwarf2_parse_compilation_unit(), elf_load_debug_info(), macho_load_debug_info(), module_new(), pev_init(), and rsym_parse().

◆ pool_strdup()

char * pool_strdup ( struct pool pool,
const char str 
)

◆ sparse_array_add()

void * sparse_array_add ( struct sparse_array sa,
ULONG_PTR  key,
struct pool pool 
)

Definition at line 281 of file storage.c.

283{
284 unsigned idx, i;
285 struct key2index* pk2i;
286 struct key2index* to;
287
288 pk2i = sparse_array_lookup(sa, key, &idx);
289 if (pk2i && pk2i->key == key)
290 {
291 FIXME("re-adding an existing key\n");
292 return NULL;
293 }
294 to = vector_add(&sa->key2index, pool);
295 if (pk2i)
296 {
297 /* we need to shift vector's content... */
298 /* let's do it brute force... (FIXME) */
299 assert(sa->key2index.num_elts >= 2);
300 for (i = sa->key2index.num_elts - 1; i > idx; i--)
301 {
302 pk2i = vector_at(&sa->key2index, i - 1);
303 *to = *pk2i;
304 to = pk2i;
305 }
306 }
307
308 to->key = key;
309 to->index = sa->elements.num_elts;
310
311 return vector_add(&sa->elements, pool);
312}
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
void * vector_at(const struct vector *v, unsigned pos)
Definition: storage.c:162
static struct key2index * sparse_array_lookup(const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
Definition: storage.c:224
void * vector_add(struct vector *v, struct pool *pool)
Definition: storage.c:171
unsigned int idx
Definition: utils.c:41
unsigned index
Definition: storage.c:210
ULONG_PTR key
Definition: storage.c:209
Definition: copy.c:22

Referenced by dwarf2_parse_abbrev_set(), dwarf2_read_one_debug_info(), and rsym_parse().

◆ sparse_array_find()

void * sparse_array_find ( const struct sparse_array sa,
ULONG_PTR  key 
)

Definition at line 271 of file storage.c.

272{
273 unsigned idx;
274 struct key2index* pk2i;
275
276 if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
277 return vector_at(&sa->elements, pk2i->index);
278 return NULL;
279}

Referenced by dwarf2_abbrev_table_find_entry(), dwarf2_find_attribute(), dwarf2_get_cpp_name(), dwarf2_get_di_children(), dwarf2_lookup_type(), and rsym_parse().

◆ sparse_array_init()

void sparse_array_init ( struct sparse_array sa,
unsigned  elt_sz,
unsigned  bucket_sz 
)

Definition at line 213 of file storage.c.

214{
215 vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
216 vector_init(&sa->elements, elt_sz, bucket_sz);
217}
void vector_init(struct vector *v, unsigned esz, unsigned bucket_sz)
Definition: storage.c:133

Referenced by dwarf2_parse_abbrev_set(), dwarf2_parse_compilation_unit(), and rsym_parse().

◆ sparse_array_length()

unsigned sparse_array_length ( const struct sparse_array sa)

Definition at line 314 of file storage.c.

315{
316 return sa->elements.num_elts;
317}

Referenced by dwarf2_parse_abbrev_set().

◆ sparse_array_lookup()

static struct key2index * sparse_array_lookup ( const struct sparse_array sa,
ULONG_PTR  key,
unsigned idx 
)
static

Definition at line 224 of file storage.c.

226{
227 struct key2index* pk2i;
228 unsigned low, high;
229
230 if (!sa->elements.num_elts)
231 {
232 *idx = 0;
233 return NULL;
234 }
235 high = sa->elements.num_elts;
236 pk2i = vector_at(&sa->key2index, high - 1);
237 if (pk2i->key < key)
238 {
239 *idx = high;
240 return NULL;
241 }
242 if (pk2i->key == key)
243 {
244 *idx = high - 1;
245 return pk2i;
246 }
247 low = 0;
248 pk2i = vector_at(&sa->key2index, low);
249 if (pk2i->key >= key)
250 {
251 *idx = 0;
252 return pk2i;
253 }
254 /* now we have: sa(lowest key) < key < sa(highest key) */
255 while (low < high)
256 {
257 *idx = (low + high) / 2;
258 pk2i = vector_at(&sa->key2index, *idx);
259 if (pk2i->key > key) high = *idx;
260 else if (pk2i->key < key) low = *idx + 1;
261 else return pk2i;
262 }
263 /* binary search could return exact item, we search for highest one
264 * below the key
265 */
266 if (pk2i->key < key)
267 pk2i = vector_at(&sa->key2index, ++(*idx));
268 return pk2i;
269}

Referenced by sparse_array_add(), and sparse_array_find().

◆ vector_add()

void * vector_add ( struct vector v,
struct pool pool 
)

Definition at line 171 of file storage.c.

172{
173 unsigned ncurr = v->num_elts++;
174
175 /* check that we don't wrap around */
176 assert(v->num_elts > ncurr);
177 if (ncurr == (v->num_buckets << v->shift))
178 {
179 if(v->num_buckets == v->buckets_allocated)
180 {
181 /* Double the bucket cache, so it scales well with big vectors.*/
182 unsigned new_reserved;
183 void* new;
184
185 new_reserved = 2*v->buckets_allocated;
186 if(new_reserved == 0) new_reserved = 1;
187
188 /* Don't even try to resize memory.
189 Pool datastructure is very inefficient with reallocs. */
190 new = pool_alloc(pool, new_reserved * sizeof(void*));
191 memcpy(new, v->buckets, v->buckets_allocated * sizeof(void*));
192 v->buckets = new;
193 v->buckets_allocated = new_reserved;
194 }
195 v->buckets[v->num_buckets] = pool_alloc(pool, v->elt_size << v->shift);
196 return v->buckets[v->num_buckets++];
197 }
198 return vector_at(v, ncurr);
199}
const GLdouble * v
Definition: gl.h:2040
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878

Referenced by dwarf2_parse_line_numbers(), dwarf2_read_one_debug_info(), pev_push(), sparse_array_add(), symt_add_enum_element(), symt_add_func_line(), symt_add_func_local(), symt_add_function_point(), symt_add_function_signature_parameter(), symt_add_type(), symt_add_udt_element(), symt_new_constant(), symt_new_function(), symt_new_global_variable(), symt_new_label(), symt_new_public(), symt_new_thunk(), symt_open_func_block(), and symt_ptr2index().

◆ vector_at()

◆ vector_init()

void vector_init ( struct vector v,
unsigned  esz,
unsigned  bucket_sz 
)

Definition at line 133 of file storage.c.

134{
135 v->buckets = NULL;
136 /* align size on DWORD boundaries */
137 v->elt_size = (esz + 3) & ~3;
138 switch (bucket_sz)
139 {
140 case 2: v->shift = 1; break;
141 case 4: v->shift = 2; break;
142 case 8: v->shift = 3; break;
143 case 16: v->shift = 4; break;
144 case 32: v->shift = 5; break;
145 case 64: v->shift = 6; break;
146 case 128: v->shift = 7; break;
147 case 256: v->shift = 8; break;
148 case 512: v->shift = 9; break;
149 case 1024: v->shift = 10; break;
150 default: assert(0);
151 }
152 v->num_buckets = 0;
153 v->buckets_allocated = 0;
154 v->num_elts = 0;
155}

Referenced by dwarf2_parse_line_numbers(), dwarf2_read_one_debug_info(), module_new(), pev_init(), sparse_array_init(), symt_new_compiland(), symt_new_enum(), symt_new_function(), symt_new_function_signature(), symt_new_udt(), and symt_open_func_block().

◆ vector_length()

◆ WINE_DEFAULT_DEBUG_CHANNEL()

WINE_DEFAULT_DEBUG_CHANNEL ( dbghelp  )