17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate * CDDL HEADER START
37c478bd9Sstevel@tonic-gate *
47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the
520c1c355SRod Evans * Common Development and Distribution License (the "License").
620c1c355SRod Evans * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate *
87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate * and limitations under the License.
127c478bd9Sstevel@tonic-gate *
137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate *
197c478bd9Sstevel@tonic-gate * CDDL HEADER END
207c478bd9Sstevel@tonic-gate */
2120c1c355SRod Evans
227c478bd9Sstevel@tonic-gate /*
2320c1c355SRod Evans * Copyright (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
247c478bd9Sstevel@tonic-gate */
257c478bd9Sstevel@tonic-gate #include <stdio.h>
267c478bd9Sstevel@tonic-gate #include <stdlib.h>
277c478bd9Sstevel@tonic-gate #include <string.h>
287c478bd9Sstevel@tonic-gate #include <synch.h>
297c478bd9Sstevel@tonic-gate #include <memory.h>
307c478bd9Sstevel@tonic-gate #include "hash.h"
317c478bd9Sstevel@tonic-gate
327c478bd9Sstevel@tonic-gate static int hash_string(const char *, long);
337c478bd9Sstevel@tonic-gate
347c478bd9Sstevel@tonic-gate hash *
make_hash(size_t size)357c478bd9Sstevel@tonic-gate make_hash(size_t size)
367c478bd9Sstevel@tonic-gate {
3720c1c355SRod Evans hash *ptr;
387c478bd9Sstevel@tonic-gate
3920c1c355SRod Evans ptr = malloc(sizeof (*ptr));
407c478bd9Sstevel@tonic-gate ptr->size = size;
4120c1c355SRod Evans ptr->table = malloc((size_t)(sizeof (hash_entry *) * size));
4220c1c355SRod Evans (void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
437c478bd9Sstevel@tonic-gate ptr->start = NULL;
447c478bd9Sstevel@tonic-gate ptr->hash_type = String_Key;
457c478bd9Sstevel@tonic-gate return (ptr);
467c478bd9Sstevel@tonic-gate }
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate hash *
make_ihash(size_t size)497c478bd9Sstevel@tonic-gate make_ihash(size_t size)
507c478bd9Sstevel@tonic-gate {
5120c1c355SRod Evans hash *ptr;
527c478bd9Sstevel@tonic-gate
5320c1c355SRod Evans ptr = malloc(sizeof (*ptr));
547c478bd9Sstevel@tonic-gate ptr->size = size;
5520c1c355SRod Evans ptr->table = malloc(sizeof (hash_entry *) * size);
5620c1c355SRod Evans (void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
577c478bd9Sstevel@tonic-gate ptr->start = NULL;
587c478bd9Sstevel@tonic-gate ptr->hash_type = Integer_Key;
597c478bd9Sstevel@tonic-gate return (ptr);
607c478bd9Sstevel@tonic-gate }
617c478bd9Sstevel@tonic-gate
627c478bd9Sstevel@tonic-gate char **
get_hash(hash * tbl,char * key)637c478bd9Sstevel@tonic-gate get_hash(hash *tbl, char *key)
647c478bd9Sstevel@tonic-gate {
6520c1c355SRod Evans long bucket;
6620c1c355SRod Evans hash_entry *tmp, *new;
677c478bd9Sstevel@tonic-gate
687c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
697c478bd9Sstevel@tonic-gate tmp = tbl->table[bucket = hash_string(key, tbl->size)];
707c478bd9Sstevel@tonic-gate } else {
717c478bd9Sstevel@tonic-gate tmp = tbl->table[bucket = labs((long)key) % tbl->size];
727c478bd9Sstevel@tonic-gate }
737c478bd9Sstevel@tonic-gate
747c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
757c478bd9Sstevel@tonic-gate while (tmp != NULL) {
767c478bd9Sstevel@tonic-gate if (strcmp(tmp->key, key) == 0) {
777c478bd9Sstevel@tonic-gate return (&tmp->data);
787c478bd9Sstevel@tonic-gate }
797c478bd9Sstevel@tonic-gate tmp = tmp->next_entry;
807c478bd9Sstevel@tonic-gate }
817c478bd9Sstevel@tonic-gate } else {
827c478bd9Sstevel@tonic-gate while (tmp != NULL) {
837c478bd9Sstevel@tonic-gate if (tmp->key == key) {
847c478bd9Sstevel@tonic-gate return (&tmp->data);
857c478bd9Sstevel@tonic-gate }
867c478bd9Sstevel@tonic-gate tmp = tmp->next_entry;
877c478bd9Sstevel@tonic-gate }
887c478bd9Sstevel@tonic-gate }
897c478bd9Sstevel@tonic-gate
907c478bd9Sstevel@tonic-gate /*
917c478bd9Sstevel@tonic-gate * not found....
927c478bd9Sstevel@tonic-gate * insert new entry into bucket...
937c478bd9Sstevel@tonic-gate */
9420c1c355SRod Evans new = malloc(sizeof (*new));
957c478bd9Sstevel@tonic-gate new->key = ((tbl->hash_type == String_Key)?strdup(key):key);
9620c1c355SRod Evans
977c478bd9Sstevel@tonic-gate /*
987c478bd9Sstevel@tonic-gate * hook into chain from tbl...
997c478bd9Sstevel@tonic-gate */
1007c478bd9Sstevel@tonic-gate new->right_entry = NULL;
1017c478bd9Sstevel@tonic-gate new->left_entry = tbl->start;
1027c478bd9Sstevel@tonic-gate tbl->start = new;
10320c1c355SRod Evans
1047c478bd9Sstevel@tonic-gate /*
1057c478bd9Sstevel@tonic-gate * hook into bucket chain
1067c478bd9Sstevel@tonic-gate */
1077c478bd9Sstevel@tonic-gate new->next_entry = tbl->table[bucket];
1087c478bd9Sstevel@tonic-gate tbl->table[bucket] = new;
10920c1c355SRod Evans new->data = NULL; /* so we know that it is new */
1107c478bd9Sstevel@tonic-gate return (&new->data);
1117c478bd9Sstevel@tonic-gate }
1127c478bd9Sstevel@tonic-gate
1137c478bd9Sstevel@tonic-gate char **
find_hash(hash * tbl,const char * key)1147c478bd9Sstevel@tonic-gate find_hash(hash *tbl, const char *key)
1157c478bd9Sstevel@tonic-gate {
1167c478bd9Sstevel@tonic-gate hash_entry *tmp;
1177c478bd9Sstevel@tonic-gate
1187c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
1197c478bd9Sstevel@tonic-gate tmp = tbl->table[hash_string(key, tbl->size)];
1207c478bd9Sstevel@tonic-gate for (; tmp != NULL; tmp = tmp->next_entry) {
1217c478bd9Sstevel@tonic-gate if (strcmp(tmp->key, key) == 0) {
1227c478bd9Sstevel@tonic-gate return (&tmp->data);
1237c478bd9Sstevel@tonic-gate }
1247c478bd9Sstevel@tonic-gate }
1257c478bd9Sstevel@tonic-gate } else {
1267c478bd9Sstevel@tonic-gate tmp = tbl->table[labs((long)key) % tbl->size];
1277c478bd9Sstevel@tonic-gate for (; tmp != NULL; tmp = tmp->next_entry) {
1287c478bd9Sstevel@tonic-gate if (tmp->key == key) {
1297c478bd9Sstevel@tonic-gate return (&tmp->data);
1307c478bd9Sstevel@tonic-gate }
1317c478bd9Sstevel@tonic-gate }
1327c478bd9Sstevel@tonic-gate }
1337c478bd9Sstevel@tonic-gate return (NULL);
1347c478bd9Sstevel@tonic-gate }
1357c478bd9Sstevel@tonic-gate
1367c478bd9Sstevel@tonic-gate char *
del_hash(hash * tbl,const char * key)1377c478bd9Sstevel@tonic-gate del_hash(hash *tbl, const char *key)
1387c478bd9Sstevel@tonic-gate {
1397c478bd9Sstevel@tonic-gate ulong_t bucket;
1407c478bd9Sstevel@tonic-gate hash_entry * tmp, * prev = NULL;
1417c478bd9Sstevel@tonic-gate
1427c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
1437c478bd9Sstevel@tonic-gate bucket = hash_string(key, tbl->size);
1447c478bd9Sstevel@tonic-gate } else {
1457c478bd9Sstevel@tonic-gate bucket = labs((long)key) % tbl->size;
1467c478bd9Sstevel@tonic-gate }
1477c478bd9Sstevel@tonic-gate
1487c478bd9Sstevel@tonic-gate if ((tmp = tbl->table[bucket]) == NULL) {
1497c478bd9Sstevel@tonic-gate return (NULL);
1507c478bd9Sstevel@tonic-gate } else {
1517c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
1527c478bd9Sstevel@tonic-gate while (tmp != NULL) {
1537c478bd9Sstevel@tonic-gate if (strcmp(tmp->key, key) == 0) {
1547c478bd9Sstevel@tonic-gate break; /* found item to delete ! */
1557c478bd9Sstevel@tonic-gate }
1567c478bd9Sstevel@tonic-gate prev = tmp;
1577c478bd9Sstevel@tonic-gate tmp = tmp->next_entry;
1587c478bd9Sstevel@tonic-gate }
1597c478bd9Sstevel@tonic-gate } else {
1607c478bd9Sstevel@tonic-gate while (tmp != NULL) {
1617c478bd9Sstevel@tonic-gate if (tmp->key == key) {
1627c478bd9Sstevel@tonic-gate break;
1637c478bd9Sstevel@tonic-gate }
1647c478bd9Sstevel@tonic-gate prev = tmp;
1657c478bd9Sstevel@tonic-gate tmp = tmp->next_entry;
1667c478bd9Sstevel@tonic-gate }
1677c478bd9Sstevel@tonic-gate }
1687c478bd9Sstevel@tonic-gate if (tmp == NULL) {
1697c478bd9Sstevel@tonic-gate return (NULL); /* not found */
1707c478bd9Sstevel@tonic-gate }
1717c478bd9Sstevel@tonic-gate }
17220c1c355SRod Evans
1737c478bd9Sstevel@tonic-gate /*
1747c478bd9Sstevel@tonic-gate * tmp now points to entry marked for deletion, prev to
17520c1c355SRod Evans * item preceding in bucket chain or NULL if tmp is first.
1767c478bd9Sstevel@tonic-gate * remove from bucket chain first....
1777c478bd9Sstevel@tonic-gate */
1787c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
1797c478bd9Sstevel@tonic-gate free(tmp->key);
1807c478bd9Sstevel@tonic-gate }
1817c478bd9Sstevel@tonic-gate if (prev != NULL) {
1827c478bd9Sstevel@tonic-gate prev->next_entry = tmp->next_entry;
1837c478bd9Sstevel@tonic-gate } else {
1847c478bd9Sstevel@tonic-gate tbl->table[bucket] = tmp->next_entry;
1857c478bd9Sstevel@tonic-gate }
18620c1c355SRod Evans
1877c478bd9Sstevel@tonic-gate /*
1887c478bd9Sstevel@tonic-gate * now remove from tbl chain....
1897c478bd9Sstevel@tonic-gate */
1907c478bd9Sstevel@tonic-gate if (tmp->right_entry != NULL) { /* not first in chain.... */
1917c478bd9Sstevel@tonic-gate tmp->right_entry->left_entry = (tmp->left_entry ?
1927c478bd9Sstevel@tonic-gate tmp->left_entry->right_entry: NULL);
1937c478bd9Sstevel@tonic-gate } else {
1947c478bd9Sstevel@tonic-gate tbl->start = (tmp->left_entry ?tmp->left_entry->right_entry:
1957c478bd9Sstevel@tonic-gate NULL);
1967c478bd9Sstevel@tonic-gate }
1977c478bd9Sstevel@tonic-gate return (tmp->data);
1987c478bd9Sstevel@tonic-gate }
1997c478bd9Sstevel@tonic-gate
2007c478bd9Sstevel@tonic-gate size_t
operate_hash(hash * tbl,void (* ptr)(),const char * usr_arg)2017c478bd9Sstevel@tonic-gate operate_hash(hash *tbl, void (*ptr)(), const char *usr_arg)
2027c478bd9Sstevel@tonic-gate {
20320c1c355SRod Evans hash_entry *tmp = tbl->start;
20420c1c355SRod Evans size_t c = 0;
2057c478bd9Sstevel@tonic-gate
2067c478bd9Sstevel@tonic-gate while (tmp) {
2077c478bd9Sstevel@tonic-gate (*ptr)(tmp->data, usr_arg, tmp->key);
2087c478bd9Sstevel@tonic-gate tmp = tmp->left_entry;
2097c478bd9Sstevel@tonic-gate c++;
2107c478bd9Sstevel@tonic-gate }
2117c478bd9Sstevel@tonic-gate return (c);
2127c478bd9Sstevel@tonic-gate }
2137c478bd9Sstevel@tonic-gate
2147c478bd9Sstevel@tonic-gate size_t
operate_hash_addr(hash * tbl,void (* ptr)(),const char * usr_arg)2157c478bd9Sstevel@tonic-gate operate_hash_addr(hash *tbl, void (*ptr)(), const char *usr_arg)
2167c478bd9Sstevel@tonic-gate {
21720c1c355SRod Evans hash_entry *tmp = tbl->start;
21820c1c355SRod Evans size_t c = 0;
2197c478bd9Sstevel@tonic-gate
2207c478bd9Sstevel@tonic-gate while (tmp) {
2217c478bd9Sstevel@tonic-gate (*ptr)(&(tmp->data), usr_arg, tmp->key);
2227c478bd9Sstevel@tonic-gate tmp = tmp->left_entry;
2237c478bd9Sstevel@tonic-gate c++;
2247c478bd9Sstevel@tonic-gate }
2257c478bd9Sstevel@tonic-gate return (c);
2267c478bd9Sstevel@tonic-gate }
2277c478bd9Sstevel@tonic-gate
2287c478bd9Sstevel@tonic-gate void
destroy_hash(hash * tbl,int (* ptr)(),const char * usr_arg)2297c478bd9Sstevel@tonic-gate destroy_hash(hash *tbl, int (*ptr)(), const char *usr_arg)
2307c478bd9Sstevel@tonic-gate {
2317c478bd9Sstevel@tonic-gate hash_entry * tmp = tbl->start, * prev;
2327c478bd9Sstevel@tonic-gate
2337c478bd9Sstevel@tonic-gate while (tmp) {
2347c478bd9Sstevel@tonic-gate if (ptr) {
2357c478bd9Sstevel@tonic-gate (void) (*ptr)(tmp->data, usr_arg, tmp->key);
2367c478bd9Sstevel@tonic-gate }
2377c478bd9Sstevel@tonic-gate
2387c478bd9Sstevel@tonic-gate if (tbl->hash_type == String_Key) {
2397c478bd9Sstevel@tonic-gate free(tmp->key);
2407c478bd9Sstevel@tonic-gate }
2417c478bd9Sstevel@tonic-gate prev = tmp;
2427c478bd9Sstevel@tonic-gate tmp = tmp->left_entry;
2437c478bd9Sstevel@tonic-gate free((char *)prev);
2447c478bd9Sstevel@tonic-gate }
2457c478bd9Sstevel@tonic-gate free((char *)tbl->table);
2467c478bd9Sstevel@tonic-gate free(tbl);
2477c478bd9Sstevel@tonic-gate }
2487c478bd9Sstevel@tonic-gate
2497c478bd9Sstevel@tonic-gate static int
hash_string(const char * s,long modulo)2507c478bd9Sstevel@tonic-gate hash_string(const char *s, long modulo)
2517c478bd9Sstevel@tonic-gate {
25220c1c355SRod Evans unsigned int result = 0;
25320c1c355SRod Evans int i = 1;
2547c478bd9Sstevel@tonic-gate
255*e2294b84SToomas Soome while (*s != '\0') {
2567c478bd9Sstevel@tonic-gate result += (*s++ << i++);
2577c478bd9Sstevel@tonic-gate }
2587c478bd9Sstevel@tonic-gate
2597c478bd9Sstevel@tonic-gate /* LINTED */
2607c478bd9Sstevel@tonic-gate return ((int)(result % modulo));
2617c478bd9Sstevel@tonic-gate }
262