ctf_hash.c revision e083a0c2c99cea982dcf8e12ec3452cc575b5663
78a072e1b56619e3230735ae073668311232ec94vboxsync/*
78a072e1b56619e3230735ae073668311232ec94vboxsync * CDDL HEADER START
78a072e1b56619e3230735ae073668311232ec94vboxsync *
78a072e1b56619e3230735ae073668311232ec94vboxsync * The contents of this file are subject to the terms of the
78a072e1b56619e3230735ae073668311232ec94vboxsync * Common Development and Distribution License, Version 1.0 only
78a072e1b56619e3230735ae073668311232ec94vboxsync * (the "License"). You may not use this file except in compliance
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * with the License.
78a072e1b56619e3230735ae073668311232ec94vboxsync *
78a072e1b56619e3230735ae073668311232ec94vboxsync * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * or http://www.opensolaris.org/os/licensing.
78a072e1b56619e3230735ae073668311232ec94vboxsync * See the License for the specific language governing permissions
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * and limitations under the License.
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync *
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * When distributing Covered Code, include this CDDL HEADER in each
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * If applicable, add the following below this CDDL HEADER, with the
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * fields enclosed by brackets "[]" replaced with your own identifying
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * information: Portions Copyright [yyyy] [name of copyright owner]
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync *
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * CDDL HEADER END
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync */
78a072e1b56619e3230735ae073668311232ec94vboxsync
e7184fff6d89903aed623860629a05047960ac2dvboxsync/*
e7184fff6d89903aed623860629a05047960ac2dvboxsync * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
e7184fff6d89903aed623860629a05047960ac2dvboxsync * Use is subject to license terms.
78a072e1b56619e3230735ae073668311232ec94vboxsync */
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync#pragma ident "%Z%%M% %I% %E% SMI"
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync#include <ctf_impl.h>
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsyncstatic const ushort_t _CTF_EMPTY[1] = { 0 };
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsyncint
78a072e1b56619e3230735ae073668311232ec94vboxsyncctf_hash_create(ctf_hash_t *hp, ulong_t nelems)
78a072e1b56619e3230735ae073668311232ec94vboxsync{
78a072e1b56619e3230735ae073668311232ec94vboxsync if (nelems > USHRT_MAX)
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync return (EOVERFLOW);
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync /*
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * If the hash table is going to be empty, don't bother allocating any
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync * memory and make the only bucket point to a zero so lookups fail.
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync */
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync if (nelems == 0) {
78a072e1b56619e3230735ae073668311232ec94vboxsync bzero(hp, sizeof (ctf_hash_t));
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_buckets = (ushort_t *)_CTF_EMPTY;
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_nbuckets = 1;
78a072e1b56619e3230735ae073668311232ec94vboxsync return (0);
78a072e1b56619e3230735ae073668311232ec94vboxsync }
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_nbuckets = 211; /* use a prime number of hash buckets */
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_free = 1; /* first free element is index 1 */
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets);
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems);
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync if (hp->h_buckets == NULL || hp->h_chains == NULL) {
78a072e1b56619e3230735ae073668311232ec94vboxsync ctf_hash_destroy(hp);
78a072e1b56619e3230735ae073668311232ec94vboxsync return (EAGAIN);
78a072e1b56619e3230735ae073668311232ec94vboxsync }
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets);
78a072e1b56619e3230735ae073668311232ec94vboxsync bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems);
78a072e1b56619e3230735ae073668311232ec94vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (0);
08c4185261c17943cff6cc94522579696eeeb478vboxsync}
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsyncuint_t
08c4185261c17943cff6cc94522579696eeeb478vboxsyncctf_hash_size(const ctf_hash_t *hp)
08c4185261c17943cff6cc94522579696eeeb478vboxsync{
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (hp->h_nelems ? hp->h_nelems - 1 : 0);
08c4185261c17943cff6cc94522579696eeeb478vboxsync}
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsyncstatic ulong_t
08c4185261c17943cff6cc94522579696eeeb478vboxsyncctf_hash_compute(const char *key, size_t len)
08c4185261c17943cff6cc94522579696eeeb478vboxsync{
08c4185261c17943cff6cc94522579696eeeb478vboxsync ulong_t g, h = 0;
08c4185261c17943cff6cc94522579696eeeb478vboxsync const char *p, *q = key + len;
08c4185261c17943cff6cc94522579696eeeb478vboxsync size_t n = 0;
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync for (p = key; p < q; p++, n++) {
08c4185261c17943cff6cc94522579696eeeb478vboxsync h = (h << 4) + *p;
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if ((g = (h & 0xf0000000)) != 0) {
08c4185261c17943cff6cc94522579696eeeb478vboxsync h ^= (g >> 24);
08c4185261c17943cff6cc94522579696eeeb478vboxsync h ^= g;
08c4185261c17943cff6cc94522579696eeeb478vboxsync }
78a072e1b56619e3230735ae073668311232ec94vboxsync }
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (h);
08c4185261c17943cff6cc94522579696eeeb478vboxsync}
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsyncint
08c4185261c17943cff6cc94522579696eeeb478vboxsyncctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name)
08c4185261c17943cff6cc94522579696eeeb478vboxsync{
08c4185261c17943cff6cc94522579696eeeb478vboxsync ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)];
08c4185261c17943cff6cc94522579696eeeb478vboxsync const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name);
08c4185261c17943cff6cc94522579696eeeb478vboxsync ctf_helem_t *hep = &hp->h_chains[hp->h_free];
08c4185261c17943cff6cc94522579696eeeb478vboxsync ulong_t h;
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if (type == 0)
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (EINVAL);
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if (hp->h_free >= hp->h_nelems)
78a072e1b56619e3230735ae073668311232ec94vboxsync return (EOVERFLOW);
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if (ctsp->cts_strs == NULL)
78a072e1b56619e3230735ae073668311232ec94vboxsync return (ECTF_STRTAB);
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if (ctsp->cts_len <= CTF_NAME_OFFSET(name))
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (ECTF_BADNAME);
08c4185261c17943cff6cc94522579696eeeb478vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync if (str[0] == '\0')
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (0); /* just ignore empty strings on behalf of caller */
a6ab77f04b22f0de7691f50dfdee8196024ce26dvboxsync
a6ab77f04b22f0de7691f50dfdee8196024ce26dvboxsync hep->h_name = name;
a6ab77f04b22f0de7691f50dfdee8196024ce26dvboxsync hep->h_type = type;
f001a45ec92f71f1e4c1015485fc1ddf84e8059cvboxsync h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets;
a6ab77f04b22f0de7691f50dfdee8196024ce26dvboxsync hep->h_next = hp->h_buckets[h];
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_buckets[h] = hp->h_free++;
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (0);
78a072e1b56619e3230735ae073668311232ec94vboxsync}
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync/*
08c4185261c17943cff6cc94522579696eeeb478vboxsync * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the
08c4185261c17943cff6cc94522579696eeeb478vboxsync * hash, override the previous definition with this new official definition.
08c4185261c17943cff6cc94522579696eeeb478vboxsync * If the key is not present, then call ctf_hash_insert() and hash it in.
08c4185261c17943cff6cc94522579696eeeb478vboxsync */
08c4185261c17943cff6cc94522579696eeeb478vboxsyncint
08c4185261c17943cff6cc94522579696eeeb478vboxsyncctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name)
08c4185261c17943cff6cc94522579696eeeb478vboxsync{
08c4185261c17943cff6cc94522579696eeeb478vboxsync const char *str = ctf_strptr(fp, name);
08c4185261c17943cff6cc94522579696eeeb478vboxsync ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str));
78a072e1b56619e3230735ae073668311232ec94vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync if (hep == NULL)
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (ctf_hash_insert(hp, fp, type, name));
08c4185261c17943cff6cc94522579696eeeb478vboxsync
08c4185261c17943cff6cc94522579696eeeb478vboxsync hep->h_type = type;
08c4185261c17943cff6cc94522579696eeeb478vboxsync return (0);
08c4185261c17943cff6cc94522579696eeeb478vboxsync}
08c4185261c17943cff6cc94522579696eeeb478vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsyncctf_helem_t *
78a072e1b56619e3230735ae073668311232ec94vboxsyncctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len)
78a072e1b56619e3230735ae073668311232ec94vboxsync{
78a072e1b56619e3230735ae073668311232ec94vboxsync ctf_helem_t *hep;
78a072e1b56619e3230735ae073668311232ec94vboxsync ctf_strs_t *ctsp;
78a072e1b56619e3230735ae073668311232ec94vboxsync const char *str;
78a072e1b56619e3230735ae073668311232ec94vboxsync ushort_t i;
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets;
78a072e1b56619e3230735ae073668311232ec94vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) {
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync hep = &hp->h_chains[i];
78a072e1b56619e3230735ae073668311232ec94vboxsync ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)];
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name);
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync if (strncmp(key, str, len) == 0 && str[len] == '\0')
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync return (hep);
78a072e1b56619e3230735ae073668311232ec94vboxsync }
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsync return (NULL);
78a072e1b56619e3230735ae073668311232ec94vboxsync}
78a072e1b56619e3230735ae073668311232ec94vboxsync
78a072e1b56619e3230735ae073668311232ec94vboxsyncvoid
78a072e1b56619e3230735ae073668311232ec94vboxsyncctf_hash_destroy(ctf_hash_t *hp)
78a072e1b56619e3230735ae073668311232ec94vboxsync{
78a072e1b56619e3230735ae073668311232ec94vboxsync if (hp->h_buckets != NULL && hp->h_nbuckets != 1) {
78a072e1b56619e3230735ae073668311232ec94vboxsync ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets);
78a072e1b56619e3230735ae073668311232ec94vboxsync hp->h_buckets = NULL;
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync }
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync if (hp->h_chains != NULL) {
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems);
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync hp->h_chains = NULL;
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync }
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync}
cc260ed3418d1fd2771d0395f818f76808b60238vboxsync