1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * CDDL HEADER START 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 7*0Sstevel@tonic-gate * with the License. 8*0Sstevel@tonic-gate * 9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 11*0Sstevel@tonic-gate * See the License for the specific language governing permissions 12*0Sstevel@tonic-gate * and limitations under the License. 13*0Sstevel@tonic-gate * 14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 19*0Sstevel@tonic-gate * 20*0Sstevel@tonic-gate * CDDL HEADER END 21*0Sstevel@tonic-gate */ 22*0Sstevel@tonic-gate /* 23*0Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24*0Sstevel@tonic-gate * Use is subject to license terms. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 28*0Sstevel@tonic-gate 29*0Sstevel@tonic-gate #include <ctf_impl.h> 30*0Sstevel@tonic-gate 31*0Sstevel@tonic-gate static const ushort_t _CTF_EMPTY[1] = { 0 }; 32*0Sstevel@tonic-gate 33*0Sstevel@tonic-gate int 34*0Sstevel@tonic-gate ctf_hash_create(ctf_hash_t *hp, ulong_t nelems) 35*0Sstevel@tonic-gate { 36*0Sstevel@tonic-gate if (nelems > USHRT_MAX) 37*0Sstevel@tonic-gate return (EOVERFLOW); 38*0Sstevel@tonic-gate 39*0Sstevel@tonic-gate /* 40*0Sstevel@tonic-gate * If the hash table is going to be empty, don't bother allocating any 41*0Sstevel@tonic-gate * memory and make the only bucket point to a zero so lookups fail. 42*0Sstevel@tonic-gate */ 43*0Sstevel@tonic-gate if (nelems == 0) { 44*0Sstevel@tonic-gate bzero(hp, sizeof (ctf_hash_t)); 45*0Sstevel@tonic-gate hp->h_buckets = (ushort_t *)_CTF_EMPTY; 46*0Sstevel@tonic-gate hp->h_nbuckets = 1; 47*0Sstevel@tonic-gate return (0); 48*0Sstevel@tonic-gate } 49*0Sstevel@tonic-gate 50*0Sstevel@tonic-gate hp->h_nbuckets = 211; /* use a prime number of hash buckets */ 51*0Sstevel@tonic-gate hp->h_nelems = nelems + 1; /* we use index zero as a sentinel */ 52*0Sstevel@tonic-gate hp->h_free = 1; /* first free element is index 1 */ 53*0Sstevel@tonic-gate 54*0Sstevel@tonic-gate hp->h_buckets = ctf_alloc(sizeof (ushort_t) * hp->h_nbuckets); 55*0Sstevel@tonic-gate hp->h_chains = ctf_alloc(sizeof (ctf_helem_t) * hp->h_nelems); 56*0Sstevel@tonic-gate 57*0Sstevel@tonic-gate if (hp->h_buckets == NULL || hp->h_chains == NULL) { 58*0Sstevel@tonic-gate ctf_hash_destroy(hp); 59*0Sstevel@tonic-gate return (EAGAIN); 60*0Sstevel@tonic-gate } 61*0Sstevel@tonic-gate 62*0Sstevel@tonic-gate bzero(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 63*0Sstevel@tonic-gate bzero(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 64*0Sstevel@tonic-gate 65*0Sstevel@tonic-gate return (0); 66*0Sstevel@tonic-gate } 67*0Sstevel@tonic-gate 68*0Sstevel@tonic-gate uint_t 69*0Sstevel@tonic-gate ctf_hash_size(const ctf_hash_t *hp) 70*0Sstevel@tonic-gate { 71*0Sstevel@tonic-gate return (hp->h_nelems ? hp->h_nelems - 1 : 0); 72*0Sstevel@tonic-gate } 73*0Sstevel@tonic-gate 74*0Sstevel@tonic-gate static ulong_t 75*0Sstevel@tonic-gate ctf_hash_compute(const char *key, size_t len) 76*0Sstevel@tonic-gate { 77*0Sstevel@tonic-gate ulong_t g, h = 0; 78*0Sstevel@tonic-gate const char *p, *q = key + len; 79*0Sstevel@tonic-gate size_t n = 0; 80*0Sstevel@tonic-gate 81*0Sstevel@tonic-gate for (p = key; p < q; p++, n++) { 82*0Sstevel@tonic-gate h = (h << 4) + *p; 83*0Sstevel@tonic-gate 84*0Sstevel@tonic-gate if ((g = (h & 0xf0000000)) != 0) { 85*0Sstevel@tonic-gate h ^= (g >> 24); 86*0Sstevel@tonic-gate h ^= g; 87*0Sstevel@tonic-gate } 88*0Sstevel@tonic-gate } 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate return (h); 91*0Sstevel@tonic-gate } 92*0Sstevel@tonic-gate 93*0Sstevel@tonic-gate int 94*0Sstevel@tonic-gate ctf_hash_insert(ctf_hash_t *hp, ctf_file_t *fp, ushort_t type, uint_t name) 95*0Sstevel@tonic-gate { 96*0Sstevel@tonic-gate ctf_strs_t *ctsp = &fp->ctf_str[CTF_NAME_STID(name)]; 97*0Sstevel@tonic-gate const char *str = ctsp->cts_strs + CTF_NAME_OFFSET(name); 98*0Sstevel@tonic-gate ctf_helem_t *hep = &hp->h_chains[hp->h_free]; 99*0Sstevel@tonic-gate ulong_t h; 100*0Sstevel@tonic-gate 101*0Sstevel@tonic-gate if (type == 0) 102*0Sstevel@tonic-gate return (EINVAL); 103*0Sstevel@tonic-gate 104*0Sstevel@tonic-gate if (hp->h_free >= hp->h_nelems) 105*0Sstevel@tonic-gate return (EOVERFLOW); 106*0Sstevel@tonic-gate 107*0Sstevel@tonic-gate if (ctsp->cts_strs == NULL) 108*0Sstevel@tonic-gate return (ECTF_STRTAB); 109*0Sstevel@tonic-gate 110*0Sstevel@tonic-gate if (ctsp->cts_len <= CTF_NAME_OFFSET(name)) 111*0Sstevel@tonic-gate return (ECTF_BADNAME); 112*0Sstevel@tonic-gate 113*0Sstevel@tonic-gate if (str[0] == '\0') 114*0Sstevel@tonic-gate return (0); /* just ignore empty strings on behalf of caller */ 115*0Sstevel@tonic-gate 116*0Sstevel@tonic-gate hep->h_name = name; 117*0Sstevel@tonic-gate hep->h_type = type; 118*0Sstevel@tonic-gate h = ctf_hash_compute(str, strlen(str)) % hp->h_nbuckets; 119*0Sstevel@tonic-gate hep->h_next = hp->h_buckets[h]; 120*0Sstevel@tonic-gate hp->h_buckets[h] = hp->h_free++; 121*0Sstevel@tonic-gate 122*0Sstevel@tonic-gate return (0); 123*0Sstevel@tonic-gate } 124*0Sstevel@tonic-gate 125*0Sstevel@tonic-gate ctf_helem_t * 126*0Sstevel@tonic-gate ctf_hash_lookup(ctf_hash_t *hp, ctf_file_t *fp, const char *key, size_t len) 127*0Sstevel@tonic-gate { 128*0Sstevel@tonic-gate ctf_helem_t *hep; 129*0Sstevel@tonic-gate ctf_strs_t *ctsp; 130*0Sstevel@tonic-gate const char *str; 131*0Sstevel@tonic-gate ushort_t i; 132*0Sstevel@tonic-gate 133*0Sstevel@tonic-gate ulong_t h = ctf_hash_compute(key, len) % hp->h_nbuckets; 134*0Sstevel@tonic-gate 135*0Sstevel@tonic-gate for (i = hp->h_buckets[h]; i != 0; i = hep->h_next) { 136*0Sstevel@tonic-gate hep = &hp->h_chains[i]; 137*0Sstevel@tonic-gate ctsp = &fp->ctf_str[CTF_NAME_STID(hep->h_name)]; 138*0Sstevel@tonic-gate str = ctsp->cts_strs + CTF_NAME_OFFSET(hep->h_name); 139*0Sstevel@tonic-gate 140*0Sstevel@tonic-gate if (strncmp(key, str, len) == 0 && str[len] == '\0') 141*0Sstevel@tonic-gate return (hep); 142*0Sstevel@tonic-gate } 143*0Sstevel@tonic-gate 144*0Sstevel@tonic-gate return (NULL); 145*0Sstevel@tonic-gate } 146*0Sstevel@tonic-gate 147*0Sstevel@tonic-gate void 148*0Sstevel@tonic-gate ctf_hash_destroy(ctf_hash_t *hp) 149*0Sstevel@tonic-gate { 150*0Sstevel@tonic-gate if (hp->h_buckets != NULL && hp->h_nbuckets != 1) { 151*0Sstevel@tonic-gate ctf_free(hp->h_buckets, sizeof (ushort_t) * hp->h_nbuckets); 152*0Sstevel@tonic-gate hp->h_buckets = NULL; 153*0Sstevel@tonic-gate } 154*0Sstevel@tonic-gate 155*0Sstevel@tonic-gate if (hp->h_chains != NULL) { 156*0Sstevel@tonic-gate ctf_free(hp->h_chains, sizeof (ctf_helem_t) * hp->h_nelems); 157*0Sstevel@tonic-gate hp->h_chains = NULL; 158*0Sstevel@tonic-gate } 159*0Sstevel@tonic-gate } 160