ctf_hash.c revision 178526
11541Srgrimes/* 21541Srgrimes * CDDL HEADER START 31541Srgrimes * 41541Srgrimes * The contents of this file are subject to the terms of the 51541Srgrimes * Common Development and Distribution License, Version 1.0 only 61541Srgrimes * (the "License"). You may not use this file except in compliance 71541Srgrimes * with the License. 81541Srgrimes * 91541Srgrimes * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 101541Srgrimes * or http://www.opensolaris.org/os/licensing. 111541Srgrimes * See the License for the specific language governing permissions 121541Srgrimes * and limitations under the License. 131541Srgrimes * 141541Srgrimes * When distributing Covered Code, include this CDDL HEADER in each 151541Srgrimes * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 161541Srgrimes * If applicable, add the following below this CDDL HEADER, with the 171541Srgrimes * fields enclosed by brackets "[]" replaced with your own identifying 181541Srgrimes * information: Portions Copyright [yyyy] [name of copyright owner] 191541Srgrimes * 201541Srgrimes * CDDL HEADER END 211541Srgrimes */ 221541Srgrimes 231541Srgrimes/* 241541Srgrimes * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 251541Srgrimes * Use is subject to license terms. 261541Srgrimes */ 271541Srgrimes 281541Srgrimes#pragma ident "%Z%%M% %I% %E% SMI" 291541Srgrimes 301541Srgrimes#include <ctf_impl.h> 311541Srgrimes 321541Srgrimesstatic const ushort_t _CTF_EMPTY[1] = { 0 }; 331541Srgrimes 341541Srgrimesint 351541Srgrimesctf_hash_create(ctf_hash_t *hp, ulong_t nelems) 361541Srgrimes{ 371541Srgrimes if (nelems > USHRT_MAX) 38116189Sobrien return (EOVERFLOW); 39116189Sobrien 40116189Sobrien /* 411541Srgrimes * If the hash table is going to be empty, don't bother allocating any 421541Srgrimes * memory and make the only bucket point to a zero so lookups fail. 431541Srgrimes */ 441541Srgrimes if (nelems == 0) { 451541Srgrimes bzero(hp, sizeof (ctf_hash_t)); 4618207Sbde hp->h_buckets = (ushort_t *)_CTF_EMPTY; 471541Srgrimes hp->h_nbuckets = 1; 481541Srgrimes return (0); 491541Srgrimes } 501541Srgrimes 511541Srgrimes hp->h_nbuckets = 211; /* use a prime number of hash buckets */ 521541Srgrimes hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */ 531541Srgrimes hp->h_free = 1; /* first free element is index 1 */ 541541Srgrimes 551541Srgrimes hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets); 561541Srgrimes hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems); 571541Srgrimes 581541Srgrimes if (hp->h_buckets == NULL || hp->h_chains == NULL) { 591541Srgrimes ctf_hash_destroy(hp); 601541Srgrimes return (EAGAIN); 611541Srgrimes } 621541Srgrimes 631541Srgrimes bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 641541Srgrimes bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 651541Srgrimes 661541Srgrimes return (0); 671541Srgrimes} 681541Srgrimes 691541Srgrimesuint_t 701541Srgrimesctf_hash_size(const ctf_hash_t *hp) 711541Srgrimes{ 721541Srgrimes return (hp->h_nelems ? hp->h_nelems - 1 : 0); 731541Srgrimes} 741541Srgrimes 751541Srgrimesstatic ulong_t 761541Srgrimesctf_hash_compute(const char *key, size_t len) 771541Srgrimes{ 781541Srgrimes ulong_t g, h = 0; 791541Srgrimes const char *p, *q = key + len; 801541Srgrimes size_t n = 0; 811541Srgrimes 821541Srgrimes for (p = key; p < q; p++, n++) { 831541Srgrimes h = (h << 4) + *p; 841541Srgrimes 851541Srgrimes if ((g = (h & 0xf0000000)) != 0) { 861541Srgrimes h ^= (g >> 24); 871541Srgrimes h ^= g; 881541Srgrimes } 891541Srgrimes } 901541Srgrimes 911541Srgrimes return (h); 921541Srgrimes} 931541Srgrimes 941541Srgrimesint 951541Srgrimesctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 961541Srgrimes{ 971541Srgrimes ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; 981541Srgrimes const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name); 991541Srgrimes ctf_helem_t *hep = &hp->h_chains[hp->h_free]; 1001541Srgrimes ulong_t h; 1011541Srgrimes 1021541Srgrimes if (type == 0) 1031541Srgrimes return (EINVAL); 1041541Srgrimes 1051541Srgrimes if (hp->h_free >= hp->h_nelems) 1061541Srgrimes return (EOVERFLOW); 1071541Srgrimes 1081541Srgrimes if (ctsp->cts_strs == NULL) 1091541Srgrimes return (ECTF_STRTAB); 1101541Srgrimes 1111541Srgrimes if (ctsp->cts_len <= CTF_NAME_OFFSET(name)) 1121541Srgrimes return (ECTF_BADNAME); 1131541Srgrimes 1141541Srgrimes if (str[0] == '\0') 1151541Srgrimes return (0); /* just ignore empty strings on behalf of caller */ 1161541Srgrimes 1171541Srgrimes hep->h_name = name; 1181541Srgrimes hep->h_type = type; 1191541Srgrimes h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets; 1201541Srgrimes hep->h_next = hp->h_buckets[h]; 1211541Srgrimes hp->h_buckets[h] = hp->h_free++; 1221541Srgrimes 1231541Srgrimes return (0); 1241541Srgrimes} 1251541Srgrimes 1261541Srgrimes/* 1271541Srgrimes * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the 1281541Srgrimes * hash, override the previous definition with this new official definition. 1291541Srgrimes * If the key is not present, then call ctf_hash_insert() and hash it in. 1301541Srgrimes */ 1311541Srgrimesint 1321541Srgrimesctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 1331541Srgrimes{ 1341541Srgrimes const char *str = ctf_strptr(fp, name); 1351541Srgrimes ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str)); 1361541Srgrimes 1371541Srgrimes if (hep == NULL) 1381541Srgrimes return (ctf_hash_insert(hp, fp, type, name)); 1391541Srgrimes 1401541Srgrimes hep->h_type = type; 1411541Srgrimes return (0); 1421541Srgrimes} 1431541Srgrimes 1441541Srgrimesctf_helem_t * 1451541Srgrimesctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len) 1461541Srgrimes{ 1471541Srgrimes ctf_helem_t *hep; 1481541Srgrimes ctf_strs_t *ctsp; 1491541Srgrimes const char *str; 1501541Srgrimes ushort_t i; 1511541Srgrimes 1521541Srgrimes ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets; 1531541Srgrimes 1541541Srgrimes for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) { 1551541Srgrimes hep = &hp->h_chains[i]; 1561541Srgrimes ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)]; 1571541Srgrimes str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name); 1581541Srgrimes 1591541Srgrimes if (strncmp(key, str, len) == 0 && str[len] == '\0') 1601541Srgrimes return (hep); 1611541Srgrimes } 1621541Srgrimes 1631541Srgrimes return (NULL); 1641541Srgrimes} 1651541Srgrimes 1661541Srgrimesvoid 1671541Srgrimesctf_hash_destroy(ctf_hash_t *hp) 1681541Srgrimes{ 1691541Srgrimes if (hp->h_buckets != NULL && hp->h_nbuckets != 1) { 1701541Srgrimes ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 1711541Srgrimes hp->h_buckets = NULL; 1721541Srgrimes } 1731541Srgrimes 1741541Srgrimes if (hp->h_chains != NULL) { 1751541Srgrimes ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 1761541Srgrimes hp->h_chains = NULL; 1771541Srgrimes } 1781541Srgrimes} 1791541Srgrimes