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