ipmi_hash.c revision 2eeaed14a5e2ed9bd811643ad5bffc3510ca0310
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * CDDL HEADER START
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * The contents of this file are subject to the terms of the
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * Common Development and Distribution License (the "License").
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * You may not use this file except in compliance with the License.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * See the License for the specific language governing permissions
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * and limitations under the License.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * When distributing Covered Code, include this CDDL HEADER in each
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * If applicable, add the following below this CDDL HEADER, with the
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * fields enclosed by brackets "[]" replaced with your own identifying
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * information: Portions Copyright [yyyy] [name of copyright owner]
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * CDDL HEADER END
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * Use is subject to license terms.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#pragma ident "%Z%%M% %I% %E% SMI"
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * The (prime) number 137 happens to have the nice property that -- when
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * multiplied by two and added to 33 -- one gets a pretty long series of
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * 307, 647, 1327, 2687, 5407, 10847, 21727, 43487
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * And beyond 43487, the numbers in the series have few factors or are prime.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * That is, one can have a prime number and roughly double it to get another
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * prime number -- but the series starts at 137. A size of 137 buckets doesn't
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * particularly accommodate small hash tables, but we note that 13 also yields
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * a reasonable sequence when doubling it and adding 5:
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * 13, 31, 67, 139, 283, 571
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * So we start with this second sequence, crossing over to the first when
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * the size is greater than 137. (And when reducing the size of the hash
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * table, we cross back when the size gets below 67.)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (nsize > IPMI_HASHMINSIZE ? nsize : IPMI_HASHMINSIZE);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((ihp = ipmi_zalloc(hp, sizeof (ipmi_hash_t))) == NULL)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj const char *p;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj h = (h << 4) + *p;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((g = (h & 0xf0000000)) != 0) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj h ^= (g >> 24);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (h);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (*l == *r ? 0 : -1);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (ihp->ih_compute(ihp->ih_convert(elem)) % ihp->ih_nbuckets);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjstatic void
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((nbuckets = ipmi_zalloc(hp, nsize * sizeof (void *))) == NULL) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * This routine can't fail, so we just eat the failure here.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * The consequences of this failing are only for performance;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * correctness is not affected by our inability to resize
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * the hash table.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * For every hash element, we need to remove it from
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * this bucket, and rehash it given the new bucket
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t idx = ihp->ih_compute(search) % ihp->ih_nbuckets;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj for (hl = ihp->ih_buckets[idx]; hl != NULL; hl = hl->ihl_next) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *elem = (void *)((uintptr_t)hl - ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (ihp->ih_compare(ihp->ih_convert(elem), search) == 0)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *link = ipmi_list_next((uintptr_t)elem + ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj assert(ipmi_hash_lookup(ihp, ihp->ih_convert(elem)) == NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_resize(ihp, ipmi_hash_double(ihp->ih_nbuckets));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);