1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2002 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 #include <stdio.h> 30 #include <stdlib.h> 31 #include <string.h> 32 #include <synch.h> 33 #include <thread.h> 34 #include <memory.h> 35 #include <assert.h> 36 #include <libproc.h> 37 #include "ramdata.h" 38 #include "proto.h" 39 #include "htbl.h" 40 41 42 htbl_t * 43 init_hash(unsigned int size) 44 { 45 htbl_t *htp; 46 hashb_t *temp; 47 int i; 48 49 if ((size & (size - 1)) != 0) 50 abend("Size must be power of two", NULL); 51 52 htp = (htbl_t *)my_malloc(sizeof (htbl_t), NULL); 53 htp->size = size; 54 htp->tbl = (hashb_t *) 55 my_calloc((size_t)size, sizeof (hashb_t), NULL); 56 57 /* Init mutexes */ 58 for (i = 0; i < size; i++) { 59 temp = &htp->tbl[i]; 60 (void) mutex_init(&temp->block, USYNC_THREAD, NULL); 61 } 62 63 return (htp); 64 } 65 66 void 67 destroy_hash(htbl_t *htp) 68 { 69 int i; 70 hentry_t *tmp; 71 hentry_t *prev; 72 hashb_t *cur; 73 74 for (i = 0; i < htp->size; i++) { 75 cur = &htp->tbl[i]; 76 (void) mutex_destroy(&cur->block); 77 tmp = cur->first; 78 79 while (tmp != NULL) { 80 prev = tmp; 81 tmp = tmp->next; 82 83 free(prev->key); 84 prev->key = NULL; 85 free(prev->lib); 86 prev->lib = NULL; 87 88 free((char *)prev); 89 if (tmp != NULL) 90 tmp->prev = NULL; 91 } 92 } 93 free((char *)htp->tbl); 94 htp->tbl = NULL; 95 free(htp); 96 } 97 98 static unsigned int 99 hash_str(char *str, unsigned int sz) 100 { 101 uint_t hash = 0; 102 uint_t g; 103 char *p; 104 105 assert(str != NULL); 106 for (p = str; *p != '\0'; p++) { 107 hash = (hash << 4) + *p; 108 if ((g = (hash & 0xf0000000)) != 0) { 109 hash ^= (g >> 24); 110 hash ^= g; 111 } 112 } 113 114 return (hash & (sz - 1)); 115 } 116 117 118 void 119 add_fcall(htbl_t *htp, char *lib, char *key, unsigned long cnt) 120 { 121 unsigned int bucket; 122 hentry_t *tmp; 123 hentry_t *new; 124 hashb_t *cur; 125 126 bucket = hash_str(key, htp->size); 127 cur = &htp->tbl[bucket]; 128 129 (void) mutex_lock(&cur->block); 130 131 tmp = cur->first; 132 while (tmp != NULL) { 133 if (strcmp(tmp->key, key) == 0) { 134 if (strcmp(tmp->lib, lib) == 0) { 135 tmp->count += cnt; 136 (void) mutex_unlock(&cur->block); 137 return; 138 } 139 } 140 tmp = tmp->next; 141 } 142 143 /* 144 * If we're still here, there was no such fcall recorded 145 * so we make a new entry and add it to the table 146 */ 147 148 new = (hentry_t *)my_malloc(sizeof (hentry_t), NULL); 149 new->key = strdup(key); 150 if (new->key == NULL) 151 abend("Out of memory in htbl.c", NULL); 152 new->lib = strdup(lib); 153 if (new->lib == NULL) 154 abend("Out of memory in htbl.c", NULL); 155 new->count = cnt; 156 new->prev = NULL; 157 new->next = cur->first; 158 tmp = new->next; 159 if (tmp != NULL) { 160 tmp->prev = new; 161 } 162 cur->first = new; 163 164 (void) mutex_unlock(&cur->block); 165 } 166 167 /* 168 * iterate_hash locks the table and returns an enumeration struct 169 * using this it is possible to iterate through the entries of a hash table 170 * once finished, use iter_free to unlock the table and free the struct 171 */ 172 173 hiter_t * 174 iterate_hash(htbl_t *tbl) 175 { 176 int b; 177 int i; 178 hiter_t *new; 179 hashb_t *cur; 180 hentry_t *tmp = NULL; 181 182 new = (hiter_t *)my_malloc(sizeof (hiter_t), NULL); 183 new->table = tbl; 184 185 for (i = 0; i < tbl->size; i++) { 186 cur = &tbl->tbl[i]; 187 (void) mutex_lock(&cur->block); 188 if (tmp == NULL) { 189 tmp = cur->first; 190 b = i; 191 } 192 } 193 194 new->next = tmp; 195 new->bucket = b; 196 197 return (new); 198 } 199 200 void 201 iter_free(hiter_t *itr) 202 { 203 int i; 204 hashb_t *cur; 205 htbl_t *tbl; 206 207 tbl = itr->table; 208 for (i = 0; i < tbl->size; i++) { 209 cur = &tbl->tbl[i]; 210 (void) mutex_unlock(&cur->block); 211 } 212 213 free(itr); 214 } 215 216 hentry_t * 217 iter_next(hiter_t *itr) 218 { 219 int i; 220 hentry_t *tmp; 221 hentry_t *ret; 222 hashb_t *cur = NULL; 223 htbl_t *hash; 224 225 ret = itr->next; 226 227 228 if (ret == NULL) 229 return (ret); 230 231 hash = itr->table; 232 tmp = ret->next; 233 i = itr->bucket; 234 235 if (tmp == NULL) { 236 for (i = i + 1; i < hash->size; i++) { 237 cur = &hash->tbl[i]; 238 tmp = cur->first; 239 if (tmp != NULL) 240 break; 241 } 242 } 243 244 itr->next = tmp; 245 itr->bucket = i; 246 247 return (ret); 248 } 249 250 size_t 251 elements_in_table(htbl_t *tbl) 252 { 253 size_t elem = 0; 254 hiter_t *itr = iterate_hash(tbl); 255 hentry_t *tmp = iter_next(itr); 256 while (tmp != NULL) { 257 elem++; 258 tmp = iter_next(itr); 259 } 260 iter_free(itr); 261 return (elem); 262 } 263