From: Eric Pouech epouech@codeweavers.com
Introduce a new model for vector allocation: - No longer requiring initial size (using a pure quadratic growth), - No longer providing stability of element address across add operations.
This allows some reduction in memory usage.
Signed-off-by: Eric Pouech epouech@codeweavers.com --- dlls/dbghelp/dwarf.c | 8 ++++---- dlls/dbghelp/module.c | 6 +++--- dlls/dbghelp/msc.c | 2 +- dlls/dbghelp/storage.c | 42 ++++++++++++++++++++++++++++++++++++------ dlls/dbghelp/symbol.c | 10 +++++----- dlls/dbghelp/type.c | 6 +++--- 6 files changed, 52 insertions(+), 22 deletions(-)
diff --git a/dlls/dbghelp/dwarf.c b/dlls/dbghelp/dwarf.c index ebf71a4d148..156f72343fe 100644 --- a/dlls/dbghelp/dwarf.c +++ b/dlls/dbghelp/dwarf.c @@ -1369,7 +1369,7 @@ static BOOL dwarf2_read_one_debug_info(dwarf2_parse_context_t* ctx, else di->data = NULL; if (abbrev->have_child) { - vector_init(&di->children, sizeof(dwarf2_debug_info_t*), 16); + vector_init(&di->children, sizeof(dwarf2_debug_info_t*), 0); while (traverse->data < traverse->end_data) { if (!dwarf2_read_one_debug_info(ctx, traverse, di, &child)) return FALSE; @@ -2685,7 +2685,7 @@ static BOOL dwarf2_parse_line_numbers(dwarf2_parse_context_t* ctx, opcode_len = traverse.data; traverse.data += opcode_base - 1;
- vector_init(&dirs, sizeof(const char*), 4); + vector_init(&dirs, sizeof(const char*), 0); p = vector_add(&dirs, &ctx->pool); *p = compile_dir ? compile_dir : "."; while (traverse.data < traverse.end_data && *traverse.data) @@ -2712,7 +2712,7 @@ static BOOL dwarf2_parse_line_numbers(dwarf2_parse_context_t* ctx, } traverse.data++;
- vector_init(&files, sizeof(unsigned), 16); + vector_init(&files, sizeof(unsigned), 0); while (traverse.data < traverse.end_data && *traverse.data) { unsigned int dir_index, mod_time; @@ -4114,7 +4114,7 @@ static BOOL dwarf2_load_CU_module(dwarf2_parse_module_context_t* module_ctx, str module_ctx->module = module; module_ctx->thunks = thunks; module_ctx->load_offset = load_offset; - vector_init(&module_ctx->unit_contexts, sizeof(dwarf2_parse_context_t*), 16); + vector_init(&module_ctx->unit_contexts, sizeof(dwarf2_parse_context_t*), 0); module_ctx->cu_versions = 0;
/* phase I: parse all CU heads */ diff --git a/dlls/dbghelp/module.c b/dlls/dbghelp/module.c index 3465d9ac396..80236d39ee3 100644 --- a/dlls/dbghelp/module.c +++ b/dlls/dbghelp/module.c @@ -197,14 +197,14 @@ struct module* module_new(struct process* pcs, const WCHAR* name, module->cpu = dbghelp_current_cpu; module->debug_format_bitmask = 0;
- vector_init(&module->vsymt, sizeof(struct symt*), 128); - vector_init(&module->vcustom_symt, sizeof(struct symt*), 16); + vector_init(&module->vsymt, sizeof(struct symt*), 0); + vector_init(&module->vcustom_symt, sizeof(struct symt*), 0); /* FIXME: this seems a bit too high (on a per module basis) * need some statistics about this */ hash_table_init(&module->pool, &module->ht_symbols, 4096); hash_table_init(&module->pool, &module->ht_types, 4096); - vector_init(&module->vtypes, sizeof(struct symt*), 32); + vector_init(&module->vtypes, sizeof(struct symt*), 0);
module->sources_used = 0; module->sources_alloc = 0; diff --git a/dlls/dbghelp/msc.c b/dlls/dbghelp/msc.c index fd773dbf9a6..2eadde29485 100644 --- a/dlls/dbghelp/msc.c +++ b/dlls/dbghelp/msc.c @@ -4187,7 +4187,7 @@ static void pev_init(struct pevaluator* pev, struct cpu_stack_walk* csw, { pev->csw = csw; pool_init(&pev->pool, 512); - vector_init(&pev->stack, sizeof(char*), 8); + vector_init(&pev->stack, sizeof(char*), 0); pev->stk_index = 0; hash_table_init(&pev->pool, &pev->values, 8); pev->error[0] = '\0'; diff --git a/dlls/dbghelp/storage.c b/dlls/dbghelp/storage.c index 2344f0b848c..0589ed699ee 100644 --- a/dlls/dbghelp/storage.c +++ b/dlls/dbghelp/storage.c @@ -74,10 +74,11 @@ WCHAR* pool_wcsdup(struct pool* pool, const WCHAR* str) void vector_init(struct vector* v, unsigned esz, unsigned bucket_sz) { v->buckets = NULL; - /* align size on DWORD boundaries */ - v->elt_size = (esz + 3) & ~3; + /* align size */ + v->elt_size = (esz + sizeof(void*) - 1) & ~(sizeof(void*) - 1); switch (bucket_sz) { + case 0: v->shift = 0; break; /* special case see below */ case 2: v->shift = 1; break; case 4: v->shift = 2; break; case 8: v->shift = 3; break; @@ -102,15 +103,44 @@ unsigned vector_length(const struct vector* v)
void* vector_at(const struct vector* v, unsigned pos) { - 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; + if (v->shift) + { + unsigned o = pos & ((1 << v->shift) - 1); + return (char*)v->buckets[pos >> v->shift] + o * v->elt_size; + } + else + { + return (char*)v->buckets + pos * v->elt_size; + } }
void* vector_add(struct vector* v, struct pool* pool) { + if (!v->shift) + { + if (v->num_elts == 1024) + { + /* we'll need a second bucket, so go directly for it */ + void **new = pool_alloc(pool, 2 * sizeof(void*)); + if (!new) return NULL; + *new = v->buckets; + v->buckets = new; + v->num_buckets = 1; + v->buckets_allocated = 2; + v->shift = 10; + } + else + { + if (!v->num_elts || !(v->num_elts & (v->num_elts - 1))) + { + void *new = pool_realloc(pool, v->buckets, (v->num_elts ? v->num_elts * 2 : 1) * v->elt_size); + if (!new) return NULL; + v->buckets = new; + } + return vector_at(v, v->num_elts++); + } + } if (v->num_elts == (v->num_buckets << v->shift)) { if (v->num_buckets == v->buckets_allocated) diff --git a/dlls/dbghelp/symbol.c b/dlls/dbghelp/symbol.c index 38382b006d7..7c8acf8e68c 100644 --- a/dlls/dbghelp/symbol.c +++ b/dlls/dbghelp/symbol.c @@ -226,7 +226,7 @@ struct symt_module* symt_new_module(struct module* module) { sym->symt.tag = SymTagExe; sym->module = module; - vector_init(&sym->vchildren, sizeof(struct symt*), 8); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); } return sym; } @@ -244,7 +244,7 @@ struct symt_compiland* symt_new_compiland(struct module* module, unsigned src_id sym->container = module->top; sym->address = 0; sym->source = src_idx; - vector_init(&sym->vchildren, sizeof(struct symt*), 32); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); sym->user = NULL; p = vector_add(&module->top->vchildren, &module->pool); *p = sym; @@ -333,8 +333,8 @@ static struct symt_function* init_function_or_inlinesite(struct module* module, sym->hash_elt.name = pool_strdup(&module->pool, name); sym->container = container; sym->type = sig_type; - vector_init(&sym->vlines, sizeof(struct line_info), tag == SymTagFunction ? 8 : 4); - vector_init(&sym->vchildren, sizeof(struct symt*), 8); + vector_init(&sym->vlines, sizeof(struct line_info), 0); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); sym->num_ranges = num_ranges; } return sym; @@ -548,7 +548,7 @@ struct symt_block* symt_open_func_block(struct module* module, block->symt.tag = SymTagBlock; block->num_ranges = num_ranges; block->container = parent_block ? &parent_block->symt : &func->symt; - vector_init(&block->vchildren, sizeof(struct symt*), 4); + vector_init(&block->vchildren, sizeof(struct symt*), 0); if (parent_block) p = vector_add(&parent_block->vchildren, &module->pool); else diff --git a/dlls/dbghelp/type.c b/dlls/dbghelp/type.c index b89c63c5b3d..9a1482e73ab 100644 --- a/dlls/dbghelp/type.c +++ b/dlls/dbghelp/type.c @@ -260,7 +260,7 @@ struct symt_udt* symt_new_udt(struct module* module, const char* typename, sym->hash_elt.name = pool_strdup(&module->pool, typename); hash_table_add(&module->ht_types, &sym->hash_elt); } else sym->hash_elt.name = NULL; - vector_init(&sym->vchildren, sizeof(struct symt*), 8); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); symt_add_type(module, &sym->symt); } return sym; @@ -345,7 +345,7 @@ struct symt_enum* symt_new_enum(struct module* module, const char* typename, hash_table_add(&module->ht_types, &sym->hash_elt); } else sym->hash_elt.name = NULL; sym->base_type = basetype; - vector_init(&sym->vchildren, sizeof(struct symt*), 8); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); symt_add_type(module, &sym->symt); } return sym; @@ -404,7 +404,7 @@ struct symt_function_signature* symt_new_function_signature(struct module* modul { sym->symt.tag = SymTagFunctionType; sym->rettype = ret_type; - vector_init(&sym->vchildren, sizeof(struct symt*), 4); + vector_init(&sym->vchildren, sizeof(struct symt*), 0); sym->call_conv = call_conv; symt_add_type(module, &sym->symt); }