diff options
Diffstat (limited to 'lib/isc/symtab.c')
| -rw-r--r-- | lib/isc/symtab.c | 53 |
1 files changed, 51 insertions, 2 deletions
diff --git a/lib/isc/symtab.c b/lib/isc/symtab.c index 9f8e798df368..d4c1dccf0ad9 100644 --- a/lib/isc/symtab.c +++ b/lib/isc/symtab.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 2004, 2005, 2007 Internet Systems Consortium, Inc. ("ISC") + * Copyright (C) 2004, 2005, 2007, 2011, 2012 Internet Systems Consortium, Inc. ("ISC") * Copyright (C) 1996-2001 Internet Software Consortium. * * Permission to use, copy, modify, and/or distribute this software for any @@ -15,7 +15,7 @@ * PERFORMANCE OF THIS SOFTWARE. */ -/* $Id: symtab.c,v 1.30 2007/06/19 23:47:17 tbox Exp $ */ +/* $Id$ */ /*! \file */ @@ -46,6 +46,8 @@ struct isc_symtab { unsigned int magic; isc_mem_t * mctx; unsigned int size; + unsigned int count; + unsigned int maxload; eltlist_t * table; isc_symtabaction_t undefine_action; void * undefine_arg; @@ -79,6 +81,8 @@ isc_symtab_create(isc_mem_t *mctx, unsigned int size, INIT_LIST(symtab->table[i]); symtab->mctx = mctx; symtab->size = size; + symtab->count = 0; + symtab->maxload = size * 3 / 4; symtab->undefine_action = undefine_action; symtab->undefine_arg = undefine_arg; symtab->case_sensitive = case_sensitive; @@ -181,6 +185,46 @@ isc_symtab_lookup(isc_symtab_t *symtab, const char *key, unsigned int type, return (ISC_R_SUCCESS); } +static void +grow_table(isc_symtab_t *symtab) { + eltlist_t *newtable; + unsigned int i, newsize, newmax; + + REQUIRE(symtab != NULL); + + newsize = symtab->size * 2; + newmax = newsize * 3 / 4; + INSIST(newsize > 0U && newmax > 0U); + + newtable = isc_mem_get(symtab->mctx, newsize * sizeof(eltlist_t)); + if (newtable == NULL) + return; + + for (i = 0; i < newsize; i++) + INIT_LIST(newtable[i]); + + for (i = 0; i < symtab->size; i++) { + elt_t *elt, *nelt; + + for (elt = HEAD(symtab->table[i]); elt != NULL; elt = nelt) { + unsigned int hv; + + nelt = NEXT(elt, link); + + UNLINK(symtab->table[i], elt, link); + hv = hash(elt->key, symtab->case_sensitive); + APPEND(newtable[hv % newsize], elt, link); + } + } + + isc_mem_put(symtab->mctx, symtab->table, + symtab->size * sizeof(eltlist_t)); + + symtab->table = newtable; + symtab->size = newsize; + symtab->maxload = newmax; +} + isc_result_t isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, isc_symvalue_t value, isc_symexists_t exists_policy) @@ -208,6 +252,7 @@ isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, if (elt == NULL) return (ISC_R_NOMEMORY); ISC_LINK_INIT(elt, link); + symtab->count++; } /* @@ -226,6 +271,9 @@ isc_symtab_define(isc_symtab_t *symtab, const char *key, unsigned int type, */ PREPEND(symtab->table[bucket], elt, link); + if (symtab->count > symtab->maxload) + grow_table(symtab); + return (ISC_R_SUCCESS); } @@ -247,6 +295,7 @@ isc_symtab_undefine(isc_symtab_t *symtab, const char *key, unsigned int type) { elt->value, symtab->undefine_arg); UNLINK(symtab->table[bucket], elt, link); isc_mem_put(symtab->mctx, elt, sizeof(*elt)); + symtab->count--; return (ISC_R_SUCCESS); } |