usr/src/cmd/sgs/link_audit/common/hash.c

   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 }