/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright (c) 1996, 2010, Oracle and/or its affiliates. All rights reserved.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <synch.h>
#include <memory.h>
#include "hash.h"
static int hash_string(const char *, long);
hash *
make_hash(size_t size)
{
hash *ptr;
ptr = malloc(sizeof (*ptr));
ptr->size = size;
ptr->table = malloc((size_t)(sizeof (hash_entry *) * size));
(void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
ptr->start = NULL;
ptr->hash_type = String_Key;
return (ptr);
}
hash *
make_ihash(size_t size)
{
hash *ptr;
ptr = malloc(sizeof (*ptr));
ptr->size = size;
ptr->table = malloc(sizeof (hash_entry *) * size);
(void) memset((char *)ptr->table, 0, sizeof (hash_entry *) * size);
ptr->start = NULL;
ptr->hash_type = Integer_Key;
return (ptr);
}
char **
get_hash(hash *tbl, char *key)
{
long bucket;
hash_entry *tmp, *new;
if (tbl->hash_type == String_Key) {
tmp = tbl->table[bucket = hash_string(key, tbl->size)];
} else {
tmp = tbl->table[bucket = labs((long)key) % tbl->size];
}
if (tbl->hash_type == String_Key) {
while (tmp != NULL) {
if (strcmp(tmp->key, key) == 0) {
return (&tmp->data);
}
tmp = tmp->next_entry;
}
} else {
while (tmp != NULL) {
if (tmp->key == key) {
return (&tmp->data);
}
tmp = tmp->next_entry;
}
}
/*
* not found....
* insert new entry into bucket...
*/
new = malloc(sizeof (*new));
new->key = ((tbl->hash_type == String_Key)?strdup(key):key);
/*
* hook into chain from tbl...
*/
new->right_entry = NULL;
new->left_entry = tbl->start;
tbl->start = new;
/*
* hook into bucket chain
*/
new->next_entry = tbl->table[bucket];
tbl->table[bucket] = new;
new->data = NULL; /* so we know that it is new */
return (&new->data);
}
char **
find_hash(hash *tbl, const char *key)
{
hash_entry *tmp;
if (tbl->hash_type == String_Key) {
tmp = tbl->table[hash_string(key, tbl->size)];
for (; tmp != NULL; tmp = tmp->next_entry) {
if (strcmp(tmp->key, key) == 0) {
return (&tmp->data);
}
}
} else {
tmp = tbl->table[labs((long)key) % tbl->size];
for (; tmp != NULL; tmp = tmp->next_entry) {
if (tmp->key == key) {
return (&tmp->data);
}
}
}
return (NULL);
}
char *
del_hash(hash *tbl, const char *key)
{
ulong_t bucket;
hash_entry * tmp, * prev = NULL;
if (tbl->hash_type == String_Key) {
bucket = hash_string(key, tbl->size);
} else {
bucket = labs((long)key) % tbl->size;
}
if ((tmp = tbl->table[bucket]) == NULL) {
return (NULL);
} else {
if (tbl->hash_type == String_Key) {
while (tmp != NULL) {
if (strcmp(tmp->key, key) == 0) {
break; /* found item to delete ! */
}
prev = tmp;
tmp = tmp->next_entry;
}
} else {
while (tmp != NULL) {
if (tmp->key == key) {
break;
}
prev = tmp;
tmp = tmp->next_entry;
}
}
if (tmp == NULL) {
return (NULL); /* not found */
}
}
/*
* tmp now points to entry marked for deletion, prev to
* item preceding in bucket chain or NULL if tmp is first.
* remove from bucket chain first....
*/
if (tbl->hash_type == String_Key) {
free(tmp->key);
}
if (prev != NULL) {
prev->next_entry = tmp->next_entry;
} else {
tbl->table[bucket] = tmp->next_entry;
}
/*
* now remove from tbl chain....
*/
if (tmp->right_entry != NULL) { /* not first in chain.... */
tmp->right_entry->left_entry = (tmp->left_entry ?
tmp->left_entry->right_entry: NULL);
} else {
tbl->start = (tmp->left_entry ?tmp->left_entry->right_entry:
NULL);
}
return (tmp->data);
}
size_t
operate_hash(hash *tbl, void (*ptr)(), const char *usr_arg)
{
hash_entry *tmp = tbl->start;
size_t c = 0;
while (tmp) {
(*ptr)(tmp->data, usr_arg, tmp->key);
tmp = tmp->left_entry;
c++;
}
return (c);
}
size_t
operate_hash_addr(hash *tbl, void (*ptr)(), const char *usr_arg)
{
hash_entry *tmp = tbl->start;
size_t c = 0;
while (tmp) {
(*ptr)(&(tmp->data), usr_arg, tmp->key);
tmp = tmp->left_entry;
c++;
}
return (c);
}
void
destroy_hash(hash *tbl, int (*ptr)(), const char *usr_arg)
{
hash_entry * tmp = tbl->start, * prev;
while (tmp) {
if (ptr) {
(void) (*ptr)(tmp->data, usr_arg, tmp->key);
}
if (tbl->hash_type == String_Key) {
free(tmp->key);
}
prev = tmp;
tmp = tmp->left_entry;
free((char *)prev);
}
free((char *)tbl->table);
free(tbl);
}
static int
hash_string(const char *s, long modulo)
{
unsigned int result = 0;
int i = 1;
while (*s != NULL) {
result += (*s++ << i++);
}
/* LINTED */
return ((int)(result % modulo));
}