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)
void *	pool_alloc (struct pool *pool, size_t len)
char *	pool_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)
void *	vector_at (const struct vector *v, unsigned pos)
void *	vector_add (struct vector *v, struct pool *pool)
void	sparse_array_init (struct sparse_array *sa, unsigned elt_sz, unsigned bucket_sz)
static struct key2index *	sparse_array_lookup (const struct sparse_array *sa, ULONG_PTR key, unsigned *idx)
void *	sparse_array_find (const struct sparse_array *sa, ULONG_PTR key)
void *	sparse_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)
void *	hash_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.

{
    unsigned                    hash = hash_table_hash(elt->name, ht->num_buckets);
 
    if (!ht->buckets)
    {
        ht->buckets = pool_alloc(ht->pool, ht->num_buckets * sizeof(struct hash_table_bucket));
        assert(ht->buckets);
        memset(ht->buckets, 0, ht->num_buckets * sizeof(struct hash_table_bucket));
    }
 
    /* in some cases, we need to get back the symbols of same name in the order
     * in which they've been inserted. So insert new elements at the end of the list.
     */
    if (!ht->buckets[hash].first)
    {
        ht->buckets[hash].first = elt;
    }
    else
    {
        ht->buckets[hash].last->next = elt;
    }
    ht->buckets[hash].last = elt;
    elt->next = NULL;
    ht->num_elts++;
}

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.

{
#if defined(USE_STATS)
    int                         i;
    unsigned                    len;
    unsigned                    min = 0xffffffff, max = 0, sq = 0;
    struct hash_table_elt*      elt;
    double                      mean, variance;
 
    for (i = 0; i < ht->num_buckets; i++)
    {
        for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
        if (len < min) min = len;
        if (len > max) max = len;
        sq += len * len;
    }
    mean = (double)ht->num_elts / ht->num_buckets;
    variance = (double)sq / ht->num_buckets - mean * mean;
    FIXME("STATS: elts[num:%-4u size:%u mean:%f] buckets[min:%-4u variance:%+f max:%-4u]\n",
          ht->num_elts, ht->num_buckets, mean, min, variance, max);
 
    for (i = 0; i < ht->num_buckets; i++)
    {
        for (len = 0, elt = ht->buckets[i]; elt; elt = elt->next) len++;
        if (len == max)
        {
            FIXME("Longest bucket:\n");
            for (elt = ht->buckets[i]; elt; elt = elt->next)
                FIXME("\t%s\n", elt->name);
            break;
        }
 
    }
#endif
}

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.

{
    unsigned    hash = 0;
    while (*name)
    {
        hash += *name++;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash % num_buckets;
}

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.

{
    ht->num_elts = 0;
    ht->num_buckets = num_buckets;
    ht->pool = pool;
    ht->buckets = NULL;
}

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.

{
    hti->ht = ht;
    if (name)
    {
        hti->last = hash_table_hash(name, ht->num_buckets);
        hti->index = hti->last - 1;
    }
    else
    {
        hti->last = ht->num_buckets - 1;
        hti->index = -1;
    }
    hti->element = NULL;
}

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.

{
    if (!hti->ht->buckets) return NULL;
 
    if (hti->element) hti->element = hti->element->next;
    while (!hti->element && hti->index < hti->last)
        hti->element = hti->ht->buckets[++hti->index].first;
    return hti->element;
}

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.

{
    struct pool_arena*  arena;
    void*               ret;
    size_t size;
 
    len = (len + 3) & ~3; /* round up size on DWORD boundary */
 
    LIST_FOR_EACH_ENTRY( arena, &pool->arena_list, struct pool_arena, entry )
    {
        if (arena->end - arena->current >= len)
        {
            ret = arena->current;
            arena->current += len;
            if (arena->current + 16 >= arena->end)
            {
                list_remove( &arena->entry );
                list_add_tail( &pool->arena_full, &arena->entry );
            }
            return ret;
        }
    }
 
    size = max( pool->arena_size, len );
    arena = HeapAlloc(GetProcessHeap(), 0, size + sizeof(struct pool_arena));
    if (!arena) return NULL;
 
    ret = arena + 1;
    arena->current = (char*)ret + len;
    arena->end = (char*)ret + size;
    if (arena->current + 16 >= arena->end)
        list_add_tail( &pool->arena_full, &arena->entry );
    else
        list_add_head( &pool->arena_list, &arena->entry );
    return 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.

{
    struct pool_arena*  arena;
    struct pool_arena*  next;
 
#ifdef USE_STATS
    size_t alloc, used, num;
 
    alloc = used = num = 0;
    LIST_FOR_EACH_ENTRY( arena, &pool->arena_list, struct pool_arena, entry )
    {
        alloc += arena->end - (char *)arena;
        used += arena->current - (char*)arena;
        num++;
    }
    LIST_FOR_EACH_ENTRY( arena, &pool->arena_full, struct pool_arena, entry )
    {
        alloc += arena->end - (char *)arena;
        used += arena->current - (char*)arena;
        num++;
    }
    if (alloc == 0) alloc = 1;      /* avoid division by zero */
    FIXME("STATS: pool %p has allocated %u kbytes, used %u kbytes in %u arenas, non-allocation ratio: %.2f%%\n",
          pool, (unsigned)(alloc >> 10), (unsigned)(used >> 10), (unsigned)num,
          100.0 - (float)used / (float)alloc * 100.0);
#endif
 
    LIST_FOR_EACH_ENTRY_SAFE( arena, next, &pool->arena_list, struct pool_arena, entry )
    {
        list_remove( &arena->entry );
        HeapFree(GetProcessHeap(), 0, arena);
    }
    LIST_FOR_EACH_ENTRY_SAFE( arena, next, &pool->arena_full, struct pool_arena, entry )
    {
        list_remove( &arena->entry );
        HeapFree(GetProcessHeap(), 0, arena);
    }
}

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.

{
    list_init( &a->arena_list );
    list_init( &a->arena_full );
    a->arena_size = arena_size;
}

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
	)

Definition at line 126 of file storage.c.

{
    char* ret;
    if ((ret = pool_alloc(pool, strlen(str) + 1))) strcpy(ret, str);
    return ret;
}

Referenced by dwarf2_parse_variable(), macho_stabs_def_cb(), pev_push(), pev_set_value(), symt_add_enum_element(), symt_add_func_local(), symt_add_function_point(), symt_add_udt_element(), symt_new_basic(), symt_new_constant(), symt_new_enum(), symt_new_function(), symt_new_global_variable(), symt_new_label(), symt_new_public(), symt_new_thunk(), symt_new_typedef(), symt_new_udt(), and symt_ptr2index().

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.

{
    unsigned            idx, i;
    struct key2index*   pk2i;
    struct key2index*   to;
 
    pk2i = sparse_array_lookup(sa, key, &idx);
    if (pk2i && pk2i->key == key)
    {
        FIXME("re-adding an existing key\n");
        return NULL;
    }
    to = vector_add(&sa->key2index, pool);
    if (pk2i)
    {
        /* we need to shift vector's content... */
        /* let's do it brute force... (FIXME) */
        assert(sa->key2index.num_elts >= 2);
        for (i = sa->key2index.num_elts - 1; i > idx; i--)
        {
            pk2i = vector_at(&sa->key2index, i - 1);
            *to = *pk2i;
            to = pk2i;
        }
    }
 
    to->key = key;
    to->index = sa->elements.num_elts;
 
    return vector_add(&sa->elements, pool);
}

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.

{
    unsigned            idx;
    struct key2index*   pk2i;
 
    if ((pk2i = sparse_array_lookup(sa, key, &idx)) && pk2i->key == key)
        return vector_at(&sa->elements, pk2i->index);
    return NULL;
}

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.

{
    vector_init(&sa->key2index, sizeof(struct key2index), bucket_sz);
    vector_init(&sa->elements, elt_sz, bucket_sz);
}

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.

{
    return sa->elements.num_elts;
}

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.

{
    struct key2index*   pk2i;
    unsigned            low, high;
 
    if (!sa->elements.num_elts)
    {
        *idx = 0;
        return NULL;
    }
    high = sa->elements.num_elts;
    pk2i = vector_at(&sa->key2index, high - 1);
    if (pk2i->key < key)
    {
        *idx = high;
        return NULL;
    }
    if (pk2i->key == key)
    {
        *idx = high - 1;
        return pk2i;
    }
    low = 0;
    pk2i = vector_at(&sa->key2index, low);
    if (pk2i->key >= key)
    {
        *idx = 0;
        return pk2i;
    }
    /* now we have: sa(lowest key) < key < sa(highest key) */
    while (low < high)
    {
        *idx = (low + high) / 2;
        pk2i = vector_at(&sa->key2index, *idx);
        if (pk2i->key > key)            high = *idx;
        else if (pk2i->key < key)       low = *idx + 1;
        else                            return pk2i;
    }
    /* binary search could return exact item, we search for highest one
     * below the key
     */
    if (pk2i->key < key)
        pk2i = vector_at(&sa->key2index, ++(*idx));
    return pk2i;
}

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.

{
    unsigned    ncurr = v->num_elts++;
 
    /* check that we don't wrap around */
    assert(v->num_elts > ncurr);
    if (ncurr == (v->num_buckets << v->shift))
    {
        if(v->num_buckets == v->buckets_allocated)
        {
            /* Double the bucket cache, so it scales well with big vectors.*/
            unsigned    new_reserved;
            void*       new;
 
            new_reserved = 2*v->buckets_allocated;
            if(new_reserved == 0) new_reserved = 1;
 
            /* Don't even try to resize memory.
               Pool datastructure is very inefficient with reallocs. */
            new = pool_alloc(pool, new_reserved * sizeof(void*));
            memcpy(new, v->buckets, v->buckets_allocated * sizeof(void*));
            v->buckets = new;
            v->buckets_allocated = new_reserved;
        }
        v->buckets[v->num_buckets] = pool_alloc(pool, v->elt_size << v->shift);
        return v->buckets[v->num_buckets++];
    }
    return vector_at(v, ncurr);
}

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()

void * vector_at	(	const struct vector *	v,
		unsigned	pos
	)

Definition at line 162 of file storage.c.

{
    unsigned o;
 
    if (pos >= v->num_elts) return NULL;
    o = pos & ((1 << v->shift) - 1);
    return (char*)v->buckets[pos >> v->shift] + o * v->elt_size;
}

Referenced by dwarf2_parse_array_type(), dwarf2_parse_compilation_unit(), dwarf2_parse_enumeration_type(), dwarf2_parse_inlined_subroutine(), dwarf2_parse_line_numbers(), dwarf2_parse_namespace(), dwarf2_parse_subprogram(), dwarf2_parse_subprogram_block(), dwarf2_parse_subroutine_type(), dwarf2_parse_udt_type(), dwarf2_set_line_number(), loc_compute_frame(), pev_pop(), pev_push(), sparse_array_add(), sparse_array_find(), sparse_array_lookup(), SymEnumLines(), SymEnumTypes(), symt_add_func_line(), symt_add_udt_element(), symt_enum_locals_helper(), symt_fill_func_line_info(), symt_get_info(), symt_index2ptr(), symt_normalize_function(), and vector_add().

vector_init()

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

Definition at line 133 of file storage.c.

{
    v->buckets = NULL;
    /* align size on DWORD boundaries */
    v->elt_size = (esz + 3) & ~3;
    switch (bucket_sz)
    {
    case    2: v->shift =  1; break;
    case    4: v->shift =  2; break;
    case    8: v->shift =  3; break;
    case   16: v->shift =  4; break;
    case   32: v->shift =  5; break;
    case   64: v->shift =  6; break;
    case  128: v->shift =  7; break;
    case  256: v->shift =  8; break;
    case  512: v->shift =  9; break;
    case 1024: v->shift = 10; break;
    default: assert(0);
    }
    v->num_buckets = 0;
    v->buckets_allocated = 0;
    v->num_elts = 0;
}

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()

unsigned vector_length

(

const struct vector *

v

)

Definition at line 157 of file storage.c.

{
    return v->num_elts;
}

Referenced by dwarf2_parse_array_type(), dwarf2_parse_compilation_unit(), dwarf2_parse_enumeration_type(), dwarf2_parse_inlined_subroutine(), dwarf2_parse_namespace(), dwarf2_parse_subprogram(), dwarf2_parse_subprogram_block(), dwarf2_parse_subroutine_type(), dwarf2_parse_udt_type(), loc_compute_frame(), pev_push(), SymEnumLines(), SymEnumTypes(), symt_add_func_line(), symt_add_udt_element(), symt_enum_locals_helper(), symt_fill_func_line_info(), symt_get_info(), symt_index2ptr(), symt_normalize_function(), symt_ptr2index(), and symt_set_udt_size().

WINE_DEFAULT_DEBUG_CHANNEL()

WINE_DEFAULT_DEBUG_CHANNEL

(

dbghelp

)