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 (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 22 /* 23 * Copyright (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved. 24 */ 25 #include <stdio.h> 26 #include <stdlib.h> 27 #include <string.h> 28 #include <synch.h> 29 #include <memory.h> 30 #include "hash.h" 31 32 static int hash_string(const char *, long); 33 34 hash * 35 make_hash(size_t size) 36 { 37 hash *ptr; 38 39 ptr = malloc(sizeof (*ptr)); 40 ptr->size = size; 41 ptr->table = malloc((size_t)(sizeof (hash_entry *) * size)); 42 (void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size); 43 ptr->start = NULL; 44 ptr->hash_type = String_Key; 45 return (ptr); 46 } 47 48 hash * 49 make_ihash(size_t size) 50 { 51 hash *ptr; 52 53 ptr = malloc(sizeof (*ptr)); 54 ptr->size = size; 55 ptr->table = malloc(sizeof (hash_entry *) * size); 56 (void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size); 57 ptr->start = NULL; 58 ptr->hash_type = Integer_Key; 59 return (ptr); 60 } 61 62 char ** 63 get_hash(hash *tbl, char *key) 64 { 65 long bucket; 66 hash_entry *tmp, *new; 67 68 if (tbl->hash_type == String_Key) { 69 tmp = tbl->table[bucket = hash_string(key, tbl->size)]; 70 } else { 71 tmp = tbl->table[bucket = labs((long)key) % tbl->size]; 72 } 73 74 if (tbl->hash_type == String_Key) { 75 while (tmp != NULL) { 76 if (strcmp(tmp->key, key) == 0) { 77 return (&tmp->data); 78 } 79 tmp = tmp->next_entry; 80 } 81 } else { 82 while (tmp != NULL) { 83 if (tmp->key == key) { 84 return (&tmp->data); 85 } 86 tmp = tmp->next_entry; 87 } 88 } 89 90 /* 91 * not found.... 92 * insert new entry into bucket... 93 */ 94 new = malloc(sizeof (*new)); 95 new->key = ((tbl->hash_type == String_Key)?strdup(key):key); 96 97 /* 98 * hook into chain from tbl... 99 */ 100 new->right_entry = NULL; 101 new->left_entry = tbl->start; 102 tbl->start = new; 103 104 /* 105 * hook into bucket chain 106 */ 107 new->next_entry = tbl->table[bucket]; 108 tbl->table[bucket] = new; 109 new->data = NULL; /* so we know that it is new */ 110 return (&new->data); 111 } 112 113 char ** 114 find_hash(hash *tbl, const char *key) 115 { 116 hash_entry *tmp; 117 118 if (tbl->hash_type == String_Key) { 119 tmp = tbl->table[hash_string(key, tbl->size)]; 120 for (; tmp != NULL; tmp = tmp->next_entry) { 121 if (strcmp(tmp->key, key) == 0) { 122 return (&tmp->data); 123 } 124 } 125 } else { 126 tmp = tbl->table[labs((long)key) % tbl->size]; 127 for (; tmp != NULL; tmp = tmp->next_entry) { 128 if (tmp->key == key) { 129 return (&tmp->data); 130 } 131 } 132 } 133 return (NULL); 134 } 135 136 char * 137 del_hash(hash *tbl, const char *key) 138 { 139 ulong_t bucket; 140 hash_entry * tmp, * prev = NULL; 141 142 if (tbl->hash_type == String_Key) { 143 bucket = hash_string(key, tbl->size); 144 } else { 145 bucket = labs((long)key) % tbl->size; 146 } 147 148 if ((tmp = tbl->table[bucket]) == NULL) { 149 return (NULL); 150 } else { 151 if (tbl->hash_type == String_Key) { 152 while (tmp != NULL) { 153 if (strcmp(tmp->key, key) == 0) { 154 break; /* found item to delete ! */ 155 } 156 prev = tmp; 157 tmp = tmp->next_entry; 158 } 159 } else { 160 while (tmp != NULL) { 161 if (tmp->key == key) { 162 break; 163 } 164 prev = tmp; 165 tmp = tmp->next_entry; 166 } 167 } 168 if (tmp == NULL) { 169 return (NULL); /* not found */ 170 } 171 } 172 173 /* 174 * tmp now points to entry marked for deletion, prev to 175 * item preceding in bucket chain or NULL if tmp is first. 176 * remove from bucket chain first.... 177 */ 178 if (tbl->hash_type == String_Key) { 179 free(tmp->key); 180 } 181 if (prev != NULL) { 182 prev->next_entry = tmp->next_entry; 183 } else { 184 tbl->table[bucket] = tmp->next_entry; 185 } 186 187 /* 188 * now remove from tbl chain.... 189 */ 190 if (tmp->right_entry != NULL) { /* not first in chain.... */ 191 tmp->right_entry->left_entry = (tmp->left_entry ? 192 tmp->left_entry->right_entry: NULL); 193 } else { 194 tbl->start = (tmp->left_entry ?tmp->left_entry->right_entry: 195 NULL); 196 } 197 return (tmp->data); 198 } 199 200 size_t 201 operate_hash(hash *tbl, void (*ptr)(), const char *usr_arg) 202 { 203 hash_entry *tmp = tbl->start; 204 size_t c = 0; 205 206 while (tmp) { 207 (*ptr)(tmp->data, usr_arg, tmp->key); 208 tmp = tmp->left_entry; 209 c++; 210 } 211 return (c); 212 } 213 214 size_t 215 operate_hash_addr(hash *tbl, void (*ptr)(), const char *usr_arg) 216 { 217 hash_entry *tmp = tbl->start; 218 size_t c = 0; 219 220 while (tmp) { 221 (*ptr)(&(tmp->data), usr_arg, tmp->key); 222 tmp = tmp->left_entry; 223 c++; 224 } 225 return (c); 226 } 227 228 void 229 destroy_hash(hash *tbl, int (*ptr)(), const char *usr_arg) 230 { 231 hash_entry * tmp = tbl->start, * prev; 232 233 while (tmp) { 234 if (ptr) { 235 (void) (*ptr)(tmp->data, usr_arg, tmp->key); 236 } 237 238 if (tbl->hash_type == String_Key) { 239 free(tmp->key); 240 } 241 prev = tmp; 242 tmp = tmp->left_entry; 243 free((char *)prev); 244 } 245 free((char *)tbl->table); 246 free(tbl); 247 } 248 249 static int 250 hash_string(const char *s, long modulo) 251 { 252 unsigned int result = 0; 253 int i = 1; 254 255 while (*s != '\0') { 256 result += (*s++ << i++); 257 } 258 259 /* LINTED */ 260 return ((int)(result % modulo)); 261 } 262