17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * CDDL HEADER START 37c478bd9Sstevel@tonic-gate * 47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 77c478bd9Sstevel@tonic-gate * with the License. 87c478bd9Sstevel@tonic-gate * 97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 127c478bd9Sstevel@tonic-gate * and limitations under the License. 137c478bd9Sstevel@tonic-gate * 147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * CDDL HEADER END 217c478bd9Sstevel@tonic-gate */ 22*e4586ebfSmws 237c478bd9Sstevel@tonic-gate /* 24*e4586ebfSmws * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 257c478bd9Sstevel@tonic-gate * Use is subject to license terms. 267c478bd9Sstevel@tonic-gate */ 277c478bd9Sstevel@tonic-gate 287c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 297c478bd9Sstevel@tonic-gate 307c478bd9Sstevel@tonic-gate #include <ctf_impl.h> 317c478bd9Sstevel@tonic-gate 327c478bd9Sstevel@tonic-gate static const ushort_t _CTF_EMPTY[1] = { 0 }; 337c478bd9Sstevel@tonic-gate 347c478bd9Sstevel@tonic-gate int 357c478bd9Sstevel@tonic-gate ctf_hash_create(ctf_hash_t *hp, ulong_t nelems) 367c478bd9Sstevel@tonic-gate { 377c478bd9Sstevel@tonic-gate if (nelems > USHRT_MAX) 387c478bd9Sstevel@tonic-gate return (EOVERFLOW); 397c478bd9Sstevel@tonic-gate 407c478bd9Sstevel@tonic-gate /* 417c478bd9Sstevel@tonic-gate * If the hash table is going to be empty, don't bother allocating any 427c478bd9Sstevel@tonic-gate * memory and make the only bucket point to a zero so lookups fail. 437c478bd9Sstevel@tonic-gate */ 447c478bd9Sstevel@tonic-gate if (nelems == 0) { 457c478bd9Sstevel@tonic-gate bzero(hp, sizeof (ctf_hash_t)); 467c478bd9Sstevel@tonic-gate hp->h_buckets = (ushort_t *)_CTF_EMPTY; 477c478bd9Sstevel@tonic-gate hp->h_nbuckets = 1; 487c478bd9Sstevel@tonic-gate return (0); 497c478bd9Sstevel@tonic-gate } 507c478bd9Sstevel@tonic-gate 517c478bd9Sstevel@tonic-gate hp->h_nbuckets = 211; /* use a prime number of hash buckets */ 527c478bd9Sstevel@tonic-gate hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */ 537c478bd9Sstevel@tonic-gate hp->h_free = 1; /* first free element is index 1 */ 547c478bd9Sstevel@tonic-gate 557c478bd9Sstevel@tonic-gate hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets); 567c478bd9Sstevel@tonic-gate hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems); 577c478bd9Sstevel@tonic-gate 587c478bd9Sstevel@tonic-gate if (hp->h_buckets == NULL || hp->h_chains == NULL) { 597c478bd9Sstevel@tonic-gate ctf_hash_destroy(hp); 607c478bd9Sstevel@tonic-gate return (EAGAIN); 617c478bd9Sstevel@tonic-gate } 627c478bd9Sstevel@tonic-gate 637c478bd9Sstevel@tonic-gate bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 647c478bd9Sstevel@tonic-gate bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 657c478bd9Sstevel@tonic-gate 667c478bd9Sstevel@tonic-gate return (0); 677c478bd9Sstevel@tonic-gate } 687c478bd9Sstevel@tonic-gate 697c478bd9Sstevel@tonic-gate uint_t 707c478bd9Sstevel@tonic-gate ctf_hash_size(const ctf_hash_t *hp) 717c478bd9Sstevel@tonic-gate { 727c478bd9Sstevel@tonic-gate return (hp->h_nelems ? hp->h_nelems - 1 : 0); 737c478bd9Sstevel@tonic-gate } 747c478bd9Sstevel@tonic-gate 757c478bd9Sstevel@tonic-gate static ulong_t 767c478bd9Sstevel@tonic-gate ctf_hash_compute(const char *key, size_t len) 777c478bd9Sstevel@tonic-gate { 787c478bd9Sstevel@tonic-gate ulong_t g, h = 0; 797c478bd9Sstevel@tonic-gate const char *p, *q = key + len; 807c478bd9Sstevel@tonic-gate size_t n = 0; 817c478bd9Sstevel@tonic-gate 827c478bd9Sstevel@tonic-gate for (p = key; p < q; p++, n++) { 837c478bd9Sstevel@tonic-gate h = (h << 4) + *p; 847c478bd9Sstevel@tonic-gate 857c478bd9Sstevel@tonic-gate if ((g = (h & 0xf0000000)) != 0) { 867c478bd9Sstevel@tonic-gate h ^= (g >> 24); 877c478bd9Sstevel@tonic-gate h ^= g; 887c478bd9Sstevel@tonic-gate } 897c478bd9Sstevel@tonic-gate } 907c478bd9Sstevel@tonic-gate 917c478bd9Sstevel@tonic-gate return (h); 927c478bd9Sstevel@tonic-gate } 937c478bd9Sstevel@tonic-gate 947c478bd9Sstevel@tonic-gate int 957c478bd9Sstevel@tonic-gate ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 967c478bd9Sstevel@tonic-gate { 977c478bd9Sstevel@tonic-gate ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; 987c478bd9Sstevel@tonic-gate const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name); 997c478bd9Sstevel@tonic-gate ctf_helem_t *hep = &hp->h_chains[hp->h_free]; 1007c478bd9Sstevel@tonic-gate ulong_t h; 1017c478bd9Sstevel@tonic-gate 1027c478bd9Sstevel@tonic-gate if (type == 0) 1037c478bd9Sstevel@tonic-gate return (EINVAL); 1047c478bd9Sstevel@tonic-gate 1057c478bd9Sstevel@tonic-gate if (hp->h_free >= hp->h_nelems) 1067c478bd9Sstevel@tonic-gate return (EOVERFLOW); 1077c478bd9Sstevel@tonic-gate 1087c478bd9Sstevel@tonic-gate if (ctsp->cts_strs == NULL) 1097c478bd9Sstevel@tonic-gate return (ECTF_STRTAB); 1107c478bd9Sstevel@tonic-gate 1117c478bd9Sstevel@tonic-gate if (ctsp->cts_len <= CTF_NAME_OFFSET(name)) 1127c478bd9Sstevel@tonic-gate return (ECTF_BADNAME); 1137c478bd9Sstevel@tonic-gate 1147c478bd9Sstevel@tonic-gate if (str[0] == '\0') 1157c478bd9Sstevel@tonic-gate return (0); /* just ignore empty strings on behalf of caller */ 1167c478bd9Sstevel@tonic-gate 1177c478bd9Sstevel@tonic-gate hep->h_name = name; 1187c478bd9Sstevel@tonic-gate hep->h_type = type; 1197c478bd9Sstevel@tonic-gate h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets; 1207c478bd9Sstevel@tonic-gate hep->h_next = hp->h_buckets[h]; 1217c478bd9Sstevel@tonic-gate hp->h_buckets[h] = hp->h_free++; 1227c478bd9Sstevel@tonic-gate 1237c478bd9Sstevel@tonic-gate return (0); 1247c478bd9Sstevel@tonic-gate } 1257c478bd9Sstevel@tonic-gate 126*e4586ebfSmws /* 127*e4586ebfSmws * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the 128*e4586ebfSmws * hash, override the previous definition with this new official definition. 129*e4586ebfSmws * If the key is not present, then call ctf_hash_insert() and hash it in. 130*e4586ebfSmws */ 131*e4586ebfSmws int 132*e4586ebfSmws ctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 133*e4586ebfSmws { 134*e4586ebfSmws const char *str = ctf_strptr(fp, name); 135*e4586ebfSmws ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str)); 136*e4586ebfSmws 137*e4586ebfSmws if (hep == NULL) 138*e4586ebfSmws return (ctf_hash_insert(hp, fp, type, name)); 139*e4586ebfSmws 140*e4586ebfSmws hep->h_type = type; 141*e4586ebfSmws return (0); 142*e4586ebfSmws } 143*e4586ebfSmws 1447c478bd9Sstevel@tonic-gate ctf_helem_t * 1457c478bd9Sstevel@tonic-gate ctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len) 1467c478bd9Sstevel@tonic-gate { 1477c478bd9Sstevel@tonic-gate ctf_helem_t *hep; 1487c478bd9Sstevel@tonic-gate ctf_strs_t *ctsp; 1497c478bd9Sstevel@tonic-gate const char *str; 1507c478bd9Sstevel@tonic-gate ushort_t i; 1517c478bd9Sstevel@tonic-gate 1527c478bd9Sstevel@tonic-gate ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets; 1537c478bd9Sstevel@tonic-gate 1547c478bd9Sstevel@tonic-gate for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) { 1557c478bd9Sstevel@tonic-gate hep = &hp->h_chains[i]; 1567c478bd9Sstevel@tonic-gate ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)]; 1577c478bd9Sstevel@tonic-gate str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name); 1587c478bd9Sstevel@tonic-gate 1597c478bd9Sstevel@tonic-gate if (strncmp(key, str, len) == 0 && str[len] == '\0') 1607c478bd9Sstevel@tonic-gate return (hep); 1617c478bd9Sstevel@tonic-gate } 1627c478bd9Sstevel@tonic-gate 1637c478bd9Sstevel@tonic-gate return (NULL); 1647c478bd9Sstevel@tonic-gate } 1657c478bd9Sstevel@tonic-gate 1667c478bd9Sstevel@tonic-gate void 1677c478bd9Sstevel@tonic-gate ctf_hash_destroy(ctf_hash_t *hp) 1687c478bd9Sstevel@tonic-gate { 1697c478bd9Sstevel@tonic-gate if (hp->h_buckets != NULL && hp->h_nbuckets != 1) { 1707c478bd9Sstevel@tonic-gate ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 1717c478bd9Sstevel@tonic-gate hp->h_buckets = NULL; 1727c478bd9Sstevel@tonic-gate } 1737c478bd9Sstevel@tonic-gate 1747c478bd9Sstevel@tonic-gate if (hp->h_chains != NULL) { 1757c478bd9Sstevel@tonic-gate ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 1767c478bd9Sstevel@tonic-gate hp->h_chains = NULL; 1777c478bd9Sstevel@tonic-gate } 1787c478bd9Sstevel@tonic-gate } 179