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 2002 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 <stdio.h> 30*0Sstevel@tonic-gate #include <stdlib.h> 31*0Sstevel@tonic-gate #include <string.h> 32*0Sstevel@tonic-gate #include <synch.h> 33*0Sstevel@tonic-gate #include <thread.h> 34*0Sstevel@tonic-gate #include <memory.h> 35*0Sstevel@tonic-gate #include <assert.h> 36*0Sstevel@tonic-gate #include <libproc.h> 37*0Sstevel@tonic-gate #include "ramdata.h" 38*0Sstevel@tonic-gate #include "proto.h" 39*0Sstevel@tonic-gate #include "htbl.h" 40*0Sstevel@tonic-gate 41*0Sstevel@tonic-gate 42*0Sstevel@tonic-gate htbl_t * 43*0Sstevel@tonic-gate init_hash(unsigned int size) 44*0Sstevel@tonic-gate { 45*0Sstevel@tonic-gate htbl_t *htp; 46*0Sstevel@tonic-gate hashb_t *temp; 47*0Sstevel@tonic-gate int i; 48*0Sstevel@tonic-gate 49*0Sstevel@tonic-gate if ((size & (size - 1)) != 0) 50*0Sstevel@tonic-gate abend("Size must be power of two", NULL); 51*0Sstevel@tonic-gate 52*0Sstevel@tonic-gate htp = (htbl_t *)my_malloc(sizeof (htbl_t), NULL); 53*0Sstevel@tonic-gate htp->size = size; 54*0Sstevel@tonic-gate htp->tbl = (hashb_t *) 55*0Sstevel@tonic-gate my_calloc((size_t)size, sizeof (hashb_t), NULL); 56*0Sstevel@tonic-gate 57*0Sstevel@tonic-gate /* Init mutexes */ 58*0Sstevel@tonic-gate for (i = 0; i < size; i++) { 59*0Sstevel@tonic-gate temp = &htp->tbl[i]; 60*0Sstevel@tonic-gate (void) mutex_init(&temp->block, USYNC_THREAD, NULL); 61*0Sstevel@tonic-gate } 62*0Sstevel@tonic-gate 63*0Sstevel@tonic-gate return (htp); 64*0Sstevel@tonic-gate } 65*0Sstevel@tonic-gate 66*0Sstevel@tonic-gate void 67*0Sstevel@tonic-gate destroy_hash(htbl_t *htp) 68*0Sstevel@tonic-gate { 69*0Sstevel@tonic-gate int i; 70*0Sstevel@tonic-gate hentry_t *tmp; 71*0Sstevel@tonic-gate hentry_t *prev; 72*0Sstevel@tonic-gate hashb_t *cur; 73*0Sstevel@tonic-gate 74*0Sstevel@tonic-gate for (i = 0; i < htp->size; i++) { 75*0Sstevel@tonic-gate cur = &htp->tbl[i]; 76*0Sstevel@tonic-gate (void) mutex_destroy(&cur->block); 77*0Sstevel@tonic-gate tmp = cur->first; 78*0Sstevel@tonic-gate 79*0Sstevel@tonic-gate while (tmp != NULL) { 80*0Sstevel@tonic-gate prev = tmp; 81*0Sstevel@tonic-gate tmp = tmp->next; 82*0Sstevel@tonic-gate 83*0Sstevel@tonic-gate free(prev->key); 84*0Sstevel@tonic-gate prev->key = NULL; 85*0Sstevel@tonic-gate free(prev->lib); 86*0Sstevel@tonic-gate prev->lib = NULL; 87*0Sstevel@tonic-gate 88*0Sstevel@tonic-gate free((char *)prev); 89*0Sstevel@tonic-gate if (tmp != NULL) 90*0Sstevel@tonic-gate tmp->prev = NULL; 91*0Sstevel@tonic-gate } 92*0Sstevel@tonic-gate } 93*0Sstevel@tonic-gate free((char *)htp->tbl); 94*0Sstevel@tonic-gate htp->tbl = NULL; 95*0Sstevel@tonic-gate free(htp); 96*0Sstevel@tonic-gate } 97*0Sstevel@tonic-gate 98*0Sstevel@tonic-gate static unsigned int 99*0Sstevel@tonic-gate hash_str(char *str, unsigned int sz) 100*0Sstevel@tonic-gate { 101*0Sstevel@tonic-gate uint_t hash = 0; 102*0Sstevel@tonic-gate uint_t g; 103*0Sstevel@tonic-gate char *p; 104*0Sstevel@tonic-gate 105*0Sstevel@tonic-gate assert(str != NULL); 106*0Sstevel@tonic-gate for (p = str; *p != '\0'; p++) { 107*0Sstevel@tonic-gate hash = (hash << 4) + *p; 108*0Sstevel@tonic-gate if ((g = (hash & 0xf0000000)) != 0) { 109*0Sstevel@tonic-gate hash ^= (g >> 24); 110*0Sstevel@tonic-gate hash ^= g; 111*0Sstevel@tonic-gate } 112*0Sstevel@tonic-gate } 113*0Sstevel@tonic-gate 114*0Sstevel@tonic-gate return (hash & (sz - 1)); 115*0Sstevel@tonic-gate } 116*0Sstevel@tonic-gate 117*0Sstevel@tonic-gate 118*0Sstevel@tonic-gate void 119*0Sstevel@tonic-gate add_fcall(htbl_t *htp, char *lib, char *key, unsigned long cnt) 120*0Sstevel@tonic-gate { 121*0Sstevel@tonic-gate unsigned int bucket; 122*0Sstevel@tonic-gate hentry_t *tmp; 123*0Sstevel@tonic-gate hentry_t *new; 124*0Sstevel@tonic-gate hashb_t *cur; 125*0Sstevel@tonic-gate 126*0Sstevel@tonic-gate bucket = hash_str(key, htp->size); 127*0Sstevel@tonic-gate cur = &htp->tbl[bucket]; 128*0Sstevel@tonic-gate 129*0Sstevel@tonic-gate (void) mutex_lock(&cur->block); 130*0Sstevel@tonic-gate 131*0Sstevel@tonic-gate tmp = cur->first; 132*0Sstevel@tonic-gate while (tmp != NULL) { 133*0Sstevel@tonic-gate if (strcmp(tmp->key, key) == 0) { 134*0Sstevel@tonic-gate if (strcmp(tmp->lib, lib) == 0) { 135*0Sstevel@tonic-gate tmp->count += cnt; 136*0Sstevel@tonic-gate (void) mutex_unlock(&cur->block); 137*0Sstevel@tonic-gate return; 138*0Sstevel@tonic-gate } 139*0Sstevel@tonic-gate } 140*0Sstevel@tonic-gate tmp = tmp->next; 141*0Sstevel@tonic-gate } 142*0Sstevel@tonic-gate 143*0Sstevel@tonic-gate /* 144*0Sstevel@tonic-gate * If we're still here, there was no such fcall recorded 145*0Sstevel@tonic-gate * so we make a new entry and add it to the table 146*0Sstevel@tonic-gate */ 147*0Sstevel@tonic-gate 148*0Sstevel@tonic-gate new = (hentry_t *)my_malloc(sizeof (hentry_t), NULL); 149*0Sstevel@tonic-gate new->key = strdup(key); 150*0Sstevel@tonic-gate if (new->key == NULL) 151*0Sstevel@tonic-gate abend("Out of memory in htbl.c", NULL); 152*0Sstevel@tonic-gate new->lib = strdup(lib); 153*0Sstevel@tonic-gate if (new->lib == NULL) 154*0Sstevel@tonic-gate abend("Out of memory in htbl.c", NULL); 155*0Sstevel@tonic-gate new->count = cnt; 156*0Sstevel@tonic-gate new->prev = NULL; 157*0Sstevel@tonic-gate new->next = cur->first; 158*0Sstevel@tonic-gate tmp = new->next; 159*0Sstevel@tonic-gate if (tmp != NULL) { 160*0Sstevel@tonic-gate tmp->prev = new; 161*0Sstevel@tonic-gate } 162*0Sstevel@tonic-gate cur->first = new; 163*0Sstevel@tonic-gate 164*0Sstevel@tonic-gate (void) mutex_unlock(&cur->block); 165*0Sstevel@tonic-gate } 166*0Sstevel@tonic-gate 167*0Sstevel@tonic-gate /* 168*0Sstevel@tonic-gate * iterate_hash locks the table and returns an enumeration struct 169*0Sstevel@tonic-gate * using this it is possible to iterate through the entries of a hash table 170*0Sstevel@tonic-gate * once finished, use iter_free to unlock the table and free the struct 171*0Sstevel@tonic-gate */ 172*0Sstevel@tonic-gate 173*0Sstevel@tonic-gate hiter_t * 174*0Sstevel@tonic-gate iterate_hash(htbl_t *tbl) 175*0Sstevel@tonic-gate { 176*0Sstevel@tonic-gate int b; 177*0Sstevel@tonic-gate int i; 178*0Sstevel@tonic-gate hiter_t *new; 179*0Sstevel@tonic-gate hashb_t *cur; 180*0Sstevel@tonic-gate hentry_t *tmp = NULL; 181*0Sstevel@tonic-gate 182*0Sstevel@tonic-gate new = (hiter_t *)my_malloc(sizeof (hiter_t), NULL); 183*0Sstevel@tonic-gate new->table = tbl; 184*0Sstevel@tonic-gate 185*0Sstevel@tonic-gate for (i = 0; i < tbl->size; i++) { 186*0Sstevel@tonic-gate cur = &tbl->tbl[i]; 187*0Sstevel@tonic-gate (void) mutex_lock(&cur->block); 188*0Sstevel@tonic-gate if (tmp == NULL) { 189*0Sstevel@tonic-gate tmp = cur->first; 190*0Sstevel@tonic-gate b = i; 191*0Sstevel@tonic-gate } 192*0Sstevel@tonic-gate } 193*0Sstevel@tonic-gate 194*0Sstevel@tonic-gate new->next = tmp; 195*0Sstevel@tonic-gate new->bucket = b; 196*0Sstevel@tonic-gate 197*0Sstevel@tonic-gate return (new); 198*0Sstevel@tonic-gate } 199*0Sstevel@tonic-gate 200*0Sstevel@tonic-gate void 201*0Sstevel@tonic-gate iter_free(hiter_t *itr) 202*0Sstevel@tonic-gate { 203*0Sstevel@tonic-gate int i; 204*0Sstevel@tonic-gate hashb_t *cur; 205*0Sstevel@tonic-gate htbl_t *tbl; 206*0Sstevel@tonic-gate 207*0Sstevel@tonic-gate tbl = itr->table; 208*0Sstevel@tonic-gate for (i = 0; i < tbl->size; i++) { 209*0Sstevel@tonic-gate cur = &tbl->tbl[i]; 210*0Sstevel@tonic-gate (void) mutex_unlock(&cur->block); 211*0Sstevel@tonic-gate } 212*0Sstevel@tonic-gate 213*0Sstevel@tonic-gate free(itr); 214*0Sstevel@tonic-gate } 215*0Sstevel@tonic-gate 216*0Sstevel@tonic-gate hentry_t * 217*0Sstevel@tonic-gate iter_next(hiter_t *itr) 218*0Sstevel@tonic-gate { 219*0Sstevel@tonic-gate int i; 220*0Sstevel@tonic-gate hentry_t *tmp; 221*0Sstevel@tonic-gate hentry_t *ret; 222*0Sstevel@tonic-gate hashb_t *cur = NULL; 223*0Sstevel@tonic-gate htbl_t *hash; 224*0Sstevel@tonic-gate 225*0Sstevel@tonic-gate ret = itr->next; 226*0Sstevel@tonic-gate 227*0Sstevel@tonic-gate 228*0Sstevel@tonic-gate if (ret == NULL) 229*0Sstevel@tonic-gate return (ret); 230*0Sstevel@tonic-gate 231*0Sstevel@tonic-gate hash = itr->table; 232*0Sstevel@tonic-gate tmp = ret->next; 233*0Sstevel@tonic-gate i = itr->bucket; 234*0Sstevel@tonic-gate 235*0Sstevel@tonic-gate if (tmp == NULL) { 236*0Sstevel@tonic-gate for (i = i + 1; i < hash->size; i++) { 237*0Sstevel@tonic-gate cur = &hash->tbl[i]; 238*0Sstevel@tonic-gate tmp = cur->first; 239*0Sstevel@tonic-gate if (tmp != NULL) 240*0Sstevel@tonic-gate break; 241*0Sstevel@tonic-gate } 242*0Sstevel@tonic-gate } 243*0Sstevel@tonic-gate 244*0Sstevel@tonic-gate itr->next = tmp; 245*0Sstevel@tonic-gate itr->bucket = i; 246*0Sstevel@tonic-gate 247*0Sstevel@tonic-gate return (ret); 248*0Sstevel@tonic-gate } 249*0Sstevel@tonic-gate 250*0Sstevel@tonic-gate size_t 251*0Sstevel@tonic-gate elements_in_table(htbl_t *tbl) 252*0Sstevel@tonic-gate { 253*0Sstevel@tonic-gate size_t elem = 0; 254*0Sstevel@tonic-gate hiter_t *itr = iterate_hash(tbl); 255*0Sstevel@tonic-gate hentry_t *tmp = iter_next(itr); 256*0Sstevel@tonic-gate while (tmp != NULL) { 257*0Sstevel@tonic-gate elem++; 258*0Sstevel@tonic-gate tmp = iter_next(itr); 259*0Sstevel@tonic-gate } 260*0Sstevel@tonic-gate iter_free(itr); 261*0Sstevel@tonic-gate return (elem); 262*0Sstevel@tonic-gate } 263