1178525Sjb/* 2178525Sjb * CDDL HEADER START 3178525Sjb * 4178525Sjb * The contents of this file are subject to the terms of the 5178525Sjb * Common Development and Distribution License, Version 1.0 only 6178525Sjb * (the "License"). You may not use this file except in compliance 7178525Sjb * with the License. 8178525Sjb * 9178525Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10178525Sjb * or http://www.opensolaris.org/os/licensing. 11178525Sjb * See the License for the specific language governing permissions 12178525Sjb * and limitations under the License. 13178525Sjb * 14178525Sjb * When distributing Covered Code, include this CDDL HEADER in each 15178525Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16178525Sjb * If applicable, add the following below this CDDL HEADER, with the 17178525Sjb * fields enclosed by brackets "[]" replaced with your own identifying 18178525Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 19178525Sjb * 20178525Sjb * CDDL HEADER END 21178525Sjb */ 22178525Sjb 23178525Sjb/* 24178525Sjb * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 25178525Sjb * Use is subject to license terms. 26178525Sjb */ 27178525Sjb 28178525Sjb#pragma ident "%Z%%M% %I% %E% SMI" 29178525Sjb 30178525Sjb#include <ctf_impl.h> 31178525Sjb 32178525Sjbstatic const ushort_t _CTF_EMPTY[1] = { 0 }; 33178525Sjb 34178525Sjbint 35178525Sjbctf_hash_create(ctf_hash_t *hp, ulong_t nelems) 36178525Sjb{ 37178525Sjb if (nelems > USHRT_MAX) 38178525Sjb return (EOVERFLOW); 39178525Sjb 40178525Sjb /* 41178525Sjb * If the hash table is going to be empty, don't bother allocating any 42178525Sjb * memory and make the only bucket point to a zero so lookups fail. 43178525Sjb */ 44178525Sjb if (nelems == 0) { 45178525Sjb bzero(hp, sizeof (ctf_hash_t)); 46178525Sjb hp->h_buckets = (ushort_t *)_CTF_EMPTY; 47178525Sjb hp->h_nbuckets = 1; 48178525Sjb return (0); 49178525Sjb } 50178525Sjb 51178525Sjb hp->h_nbuckets = 211; /* use a prime number of hash buckets */ 52178525Sjb hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */ 53178525Sjb hp->h_free = 1; /* first free element is index 1 */ 54178525Sjb 55178525Sjb hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets); 56178525Sjb hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems); 57178525Sjb 58178525Sjb if (hp->h_buckets == NULL || hp->h_chains == NULL) { 59178525Sjb ctf_hash_destroy(hp); 60178525Sjb return (EAGAIN); 61178525Sjb } 62178525Sjb 63178525Sjb bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 64178525Sjb bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 65178525Sjb 66178525Sjb return (0); 67178525Sjb} 68178525Sjb 69178525Sjbuint_t 70178525Sjbctf_hash_size(const ctf_hash_t *hp) 71178525Sjb{ 72178525Sjb return (hp->h_nelems ? hp->h_nelems - 1 : 0); 73178525Sjb} 74178525Sjb 75178525Sjbstatic ulong_t 76178525Sjbctf_hash_compute(const char *key, size_t len) 77178525Sjb{ 78178525Sjb ulong_t g, h = 0; 79178525Sjb const char *p, *q = key + len; 80178525Sjb size_t n = 0; 81178525Sjb 82178525Sjb for (p = key; p < q; p++, n++) { 83178525Sjb h = (h << 4) + *p; 84178525Sjb 85178525Sjb if ((g = (h & 0xf0000000)) != 0) { 86178525Sjb h ^= (g >> 24); 87178525Sjb h ^= g; 88178525Sjb } 89178525Sjb } 90178525Sjb 91178525Sjb return (h); 92178525Sjb} 93178525Sjb 94178525Sjbint 95178525Sjbctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 96178525Sjb{ 97178525Sjb ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; 98178525Sjb const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name); 99178525Sjb ctf_helem_t *hep = &hp->h_chains[hp->h_free]; 100178525Sjb ulong_t h; 101178525Sjb 102178525Sjb if (type == 0) 103178525Sjb return (EINVAL); 104178525Sjb 105178525Sjb if (hp->h_free >= hp->h_nelems) 106178525Sjb return (EOVERFLOW); 107178525Sjb 108178525Sjb if (ctsp->cts_strs == NULL) 109178525Sjb return (ECTF_STRTAB); 110178525Sjb 111178525Sjb if (ctsp->cts_len <= CTF_NAME_OFFSET(name)) 112178525Sjb return (ECTF_BADNAME); 113178525Sjb 114178525Sjb if (str[0] == '\0') 115178525Sjb return (0); /* just ignore empty strings on behalf of caller */ 116178525Sjb 117178525Sjb hep->h_name = name; 118178525Sjb hep->h_type = type; 119178525Sjb h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets; 120178525Sjb hep->h_next = hp->h_buckets[h]; 121178525Sjb hp->h_buckets[h] = hp->h_free++; 122178525Sjb 123178525Sjb return (0); 124178525Sjb} 125178525Sjb 126178525Sjb/* 127178525Sjb * Wrapper for ctf_hash_lookup/ctf_hash_insert: if the key is already in the 128178525Sjb * hash, override the previous definition with this new official definition. 129178525Sjb * If the key is not present, then call ctf_hash_insert() and hash it in. 130178525Sjb */ 131178525Sjbint 132178525Sjbctf_hash_define(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 133178525Sjb{ 134178525Sjb const char *str = ctf_strptr(fp, name); 135178525Sjb ctf_helem_t *hep = ctf_hash_lookup(hp, fp, str, strlen(str)); 136178525Sjb 137178525Sjb if (hep == NULL) 138178525Sjb return (ctf_hash_insert(hp, fp, type, name)); 139178525Sjb 140178525Sjb hep->h_type = type; 141178525Sjb return (0); 142178525Sjb} 143178525Sjb 144178525Sjbctf_helem_t * 145178525Sjbctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len) 146178525Sjb{ 147178525Sjb ctf_helem_t *hep; 148178525Sjb ctf_strs_t *ctsp; 149178525Sjb const char *str; 150178525Sjb ushort_t i; 151178525Sjb 152178525Sjb ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets; 153178525Sjb 154178525Sjb for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) { 155178525Sjb hep = &hp->h_chains[i]; 156178525Sjb ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)]; 157178525Sjb str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name); 158178525Sjb 159178525Sjb if (strncmp(key, str, len) == 0 && str[len] == '\0') 160178525Sjb return (hep); 161178525Sjb } 162178525Sjb 163178525Sjb return (NULL); 164178525Sjb} 165178525Sjb 166178525Sjbvoid 167178525Sjbctf_hash_destroy(ctf_hash_t *hp) 168178525Sjb{ 169178525Sjb if (hp->h_buckets != NULL && hp->h_nbuckets != 1) { 170178525Sjb ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 171178525Sjb hp->h_buckets = NULL; 172178525Sjb } 173178525Sjb 174178525Sjb if (hp->h_chains != NULL) { 175178525Sjb ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 176178525Sjb hp->h_chains = NULL; 177178525Sjb } 178178525Sjb} 179