2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj/*
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * CDDL HEADER START
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *
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 *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * or http://www.opensolaris.org/os/licensing.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * See the License for the specific language governing permissions
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * and limitations under the License.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *
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 *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * CDDL HEADER END
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj */
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj/*
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * Use is subject to license terms.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj */
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#pragma ident "%Z%%M% %I% %E% SMI"
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#include <strings.h>
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#include <assert.h>
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#include <ipmi_impl.h>
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#include <string.h>
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#include <strings.h>
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj/*
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 * primes:
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * 307, 647, 1327, 2687, 5407, 10847, 21727, 43487
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *
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 *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * 13, 31, 67, 139, 283, 571
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *
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 */
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#define IPMI_HASHCROSSOVER 137
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#define IPMI_HASHCROSSUNDER 67
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj#define IPMI_HASHMINSIZE 13
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjstatic ulong_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_double(ulong_t size)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t nsize;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (size < IPMI_HASHCROSSOVER) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj nsize = (size * 2) + 5;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (nsize < IPMI_HASHCROSSOVER ? nsize :
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj IPMI_HASHCROSSOVER);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return ((size * 2) + 33);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjstatic ulong_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_half(ulong_t size)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t nsize;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (size > IPMI_HASHCROSSUNDER) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj nsize = (size - 33) / 2;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (nsize > IPMI_HASHCROSSUNDER ? nsize :
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj IPMI_HASHCROSSUNDER);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj nsize = (size - 5) / 2;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (nsize > IPMI_HASHMINSIZE ? nsize : IPMI_HASHMINSIZE);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_t *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_create(ipmi_handle_t *hp, size_t linkoffs,
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj const void *(*convert)(const void *elem),
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t (*compute)(const void *key),
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj int (*compare)(const void *lkey, const void *rkey))
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_t *ihp;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((ihp = ipmi_zalloc(hp, sizeof (ipmi_hash_t))) == NULL)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_handle = hp;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_nbuckets = IPMI_HASHMINSIZE;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_linkoffs = linkoffs;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_convert = convert;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_compute = compute;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_compare = compare;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((ihp->ih_buckets = ipmi_zalloc(hp,
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_nbuckets * sizeof (void *))) == NULL) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_free(hp, ihp);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (ihp);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_destroy(ipmi_hash_t *ihp)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (ihp != NULL) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_free(ihp->ih_handle, ihp->ih_buckets);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_free(ihp->ih_handle, ihp);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjulong_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_strhash(const void *key)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t g, h = 0;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj const char *p;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj for (p = key; *p != '\0'; p++) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj h = (h << 4) + *p;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((g = (h & 0xf0000000)) != 0) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj h ^= (g >> 24);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj h ^= g;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (h);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjint
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_strcmp(const void *lhs, const void *rhs)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (strcmp(lhs, rhs));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjulong_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_ptrhash(const void *key)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (*((const uintptr_t *)key) >> 4);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjint
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_ptrcmp(const void *lhs, const void *rhs)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj const uintptr_t *l = lhs, *r = rhs;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (*l == *r ? 0 : -1);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjstatic ulong_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_compute(ipmi_hash_t *ihp, const void *elem)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (ihp->ih_compute(ihp->ih_convert(elem)) % ihp->ih_nbuckets);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjstatic void
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_resize(ipmi_hash_t *ihp, ulong_t nsize)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj size_t osize = ihp->ih_nbuckets;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_handle_t *hp = ihp->ih_handle;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *link, **nbuckets;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t idx, nidx;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj assert(nsize >= IPMI_HASHMINSIZE);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (nsize == osize)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if ((nbuckets = ipmi_zalloc(hp, nsize * sizeof (void *))) == NULL) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj /*
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 */
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_nbuckets = nsize;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj for (idx = 0; idx < osize; idx++) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj while ((link = ihp->ih_buckets[idx]) != NULL) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *elem;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj /*
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * For every hash element, we need to remove it from
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * this bucket, and rehash it given the new bucket
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj * size.
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj */
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_buckets[idx] = link->ihl_next;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj elem = (void *)((uintptr_t)link - ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj nidx = ipmi_hash_compute(ihp, elem);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj link->ihl_next = nbuckets[nidx];
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj nbuckets[nidx] = link;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_free(hp, ihp->ih_buckets);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_buckets = nbuckets;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_lookup(ipmi_hash_t *ihp, const void *search)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t idx = ihp->ih_compute(search) % ihp->ih_nbuckets;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *hl;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj for (hl = ihp->ih_buckets[idx]; hl != NULL; hl = hl->ihl_next) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *elem = (void *)((uintptr_t)hl - ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (ihp->ih_compare(ihp->ih_convert(elem), search) == 0)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (elem);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_first(ipmi_hash_t *ihp)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *link = ipmi_list_next(&(ihp)->ih_list);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (link == NULL)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return ((void *)((uintptr_t)link - ihp->ih_linkoffs));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid *
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_next(ipmi_hash_t *ihp, void *elem)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj void *link = ipmi_list_next((uintptr_t)elem + ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (link == NULL)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return ((void *)((uintptr_t)link - ihp->ih_linkoffs));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_insert(ipmi_hash_t *ihp, void *elem)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t idx = ipmi_hash_compute(ihp, elem);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj assert(ipmi_hash_lookup(ihp, ihp->ih_convert(elem)) == NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj link->ihl_next = ihp->ih_buckets[idx];
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ihp->ih_buckets[idx] = link;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_list_append(&ihp->ih_list, link);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (++ihp->ih_nelements > ihp->ih_nbuckets / 2)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_resize(ihp, ipmi_hash_double(ihp->ih_nbuckets));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjvoid
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_remove(ipmi_hash_t *ihp, void *elem)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ulong_t idx = ipmi_hash_compute(ihp, elem);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_link_t **hlp = &ihp->ih_buckets[idx];
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj for (; *hlp != NULL; hlp = &(*hlp)->ihl_next) {
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (*hlp == link)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj break;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj }
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj assert(*hlp != NULL);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj *hlp = (*hlp)->ihl_next;
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_list_delete(&ihp->ih_list, link);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj assert(ihp->ih_nelements > 0);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj if (--ihp->ih_nelements < ihp->ih_nbuckets / 4)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj ipmi_hash_resize(ihp, ipmi_hash_half(ihp->ih_nbuckets));
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjsize_t
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robjipmi_hash_count(ipmi_hash_t *ihp)
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj{
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj return (ihp->ih_nelements);
2eeaed14a5e2ed9bd811643ad5bffc3510ca0310robj}