link_audit/common/hash.c

	hash.c revision 20c1c3551cb3b3117591ae38463d16aada597c48
/*
 * 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));
}