/*
 * 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 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashset.h"
#include "mountd.h"
#include <sys/sdt.h>

/*
 * HASHSET is hash table managing pointers to a set of keys
 * (set is a collection without duplicates). The public interface
 * of the HASHSET is similar to the java.util.Set interface.
 * Unlike the libc `hsearch' based hash table, this implementation
 * does allow multiple instances of HASHSET within a single application,
 * and the HASHSET_ITERATOR allows to iterate through the entire set
 * using h_next().
 *
 * HASHSET does not store actual keys but only pointers to keys. Hence the
 * data remains intact when HASHSET grows (resizes itself). HASHSET accesses
 * the actual key data only through the hash and equal functions given
 * as arguments to h_create.
 *
 * Hash collisions are resolved with linked lists.
 */

typedef struct HashSetEntry {
        uint_t e_hash;          /* Hash value */
        const void *e_key;      /* Pointer to a key */
        struct HashSetEntry *e_next;
} ENTRY;

struct HashSet {
        ENTRY **h_table;        /* Pointer to an array of ENTRY'ies */
        uint_t h_tableSize;     /* Size of the array */
        uint_t h_count;         /* Current count */
        uint_t h_threshold;     /* loadFactor threshold */
        float  h_loadFactor;    /* Current loadFactor (h_count/h_tableSize( */
        uint_t (*h_hash) (const void *);
        int    (*h_equal) (const void *, const void *);
};

struct HashSetIterator {
        HASHSET i_h;
        uint_t i_indx;
        ENTRY *i_e;
        uint_t i_coll;
};

static void rehash(HASHSET h);

#define DEFAULT_INITIALCAPACITY 1
#define DEFAULT_LOADFACTOR      0.75

/*
 *  Create a HASHSET
 *  - HASHSET is a hash table of pointers to keys
 *  - duplicate keys are not allowed
 *  - the HASHSET is opaque and can be accessed only through the h_ functions
 *  - two keys k1 and k2 are considered equal if the result of equal(k1, k2)
 *    is non-zero
 *  - the function hash(key) is used to compute hash values for keys; if
 *    keys are "equal" the values returned by the hash function must be
 *    identical.
 */

HASHSET
h_create(uint_t (*hash) (const void *),
    int    (*equal) (const void *, const void *),
    uint_t initialCapacity,
    float loadFactor)
{
        HASHSET h;

        if (initialCapacity == 0)
                initialCapacity = DEFAULT_INITIALCAPACITY;

        if (loadFactor < 0.0)
                loadFactor = DEFAULT_LOADFACTOR;

        h = exmalloc(sizeof (*h));

        if (h == NULL)
                return (NULL);

        h->h_table = exmalloc(initialCapacity * sizeof (ENTRY *));

        (void) memset(h->h_table, 0, initialCapacity * sizeof (ENTRY *));

        if (h->h_table == NULL) {
                free(h);
                return (NULL);
        }
        h->h_tableSize = initialCapacity;
        h->h_hash = hash;
        h->h_equal = equal;
        h->h_loadFactor = loadFactor;
        h->h_threshold = (uint_t)(initialCapacity * loadFactor);
        h->h_count = 0;

        return (h);
}

/*
 *  Return a pointer to a matching key
 */

const void *
h_get(const HASHSET h, void *key)
{
        uint_t hash = h->h_hash(key);
        uint_t i = hash % h->h_tableSize;
        ENTRY *e;

        for (e = h->h_table[i]; e; e = e->e_next)
                if (e->e_hash == hash && h->h_equal(e->e_key, key))
                        return (e->e_key);

        return (NULL);
}

/*
 *  Rehash (grow) HASHSET
 *  - called when loadFactor exceeds threshold
 *  - new size is 2*old_size+1
 */

static void
rehash(HASHSET h)
{
        uint_t i = h->h_tableSize;
        uint_t newtabSize = 2 * i + 1;
        ENTRY **newtab = exmalloc(newtabSize * sizeof (ENTRY *));

        (void) memset(newtab, 0, newtabSize * sizeof (ENTRY *));

        while (i--) {
                ENTRY *e, *next;

                for (e = h->h_table[i]; e; e = next) {
                        uint_t k = e->e_hash % newtabSize;

                        next = (ENTRY *) e->e_next;
                        e->e_next = (ENTRY *) newtab[k];
                        newtab[k] = e;
                }
        }

        h->h_threshold = (uint_t)(newtabSize * h->h_loadFactor);
        h->h_tableSize = newtabSize;
        free(h->h_table);
        h->h_table = newtab;
}

/*
 *  Store a key into a HASHSET
 *  - if there is already an "equal" key then the new key will not
 *    be stored and the function returns a pointer to an existing key
 *  - otherwise the function stores pointer to the new key and return NULL
 */

const void *
h_put(HASHSET h, const void *key)
{
        uint_t hash = h->h_hash(key);
        uint_t indx = hash % h->h_tableSize;
        ENTRY *e;

        for (e = h->h_table[indx]; e; e = e->e_next)
                if (e->e_hash == hash && h->h_equal(e->e_key, key))
                        return (key);

        if (h->h_count >= h->h_threshold) {
                rehash(h);

                indx = hash % h->h_tableSize;
        }

        e = exmalloc(sizeof (ENTRY));
        e->e_hash = hash;
        e->e_key = (void *) key;
        e->e_next = h->h_table[indx];

        h->h_table[indx] = e;
        h->h_count++;

        DTRACE_PROBE2(mountd, hashset, h->h_count, h->h_loadFactor);

        return (NULL);
}

/*
 *  Delete a key
 *  - if there is no "equal" key in the HASHSET the fuction returns NULL
 *  - otherwise the function returns a pointer to the deleted key
 */

const void *
h_delete(HASHSET h, const void *key)
{
        uint_t hash = h->h_hash(key);
        uint_t indx = hash % h->h_tableSize;
        ENTRY *e, *prev;

        for (e = h->h_table[indx], prev = NULL; e; prev = e, e = e->e_next) {
                if (e->e_hash == hash && h->h_equal(e->e_key, key)) {
                        key = e->e_key;
                        if (prev)
                                prev->e_next = e->e_next;
                        else
                                h->h_table[indx] = e->e_next;
                        free(e);
                        return (key);
                }
        }

        return (NULL);
}

/*
 *  Return an opaque HASHSET_ITERATOR (to be used in h_next())
 */

HASHSET_ITERATOR
h_iterator(HASHSET h)
{
        HASHSET_ITERATOR i = exmalloc(sizeof (*i));

        i->i_h = h;
        i->i_indx = h->h_tableSize;
        i->i_e = NULL;
        i->i_coll = 0;

        return (i);
}

/*
 * Return a pointer to a next key
 */

const void *
h_next(HASHSET_ITERATOR i)
{
        const void *key;

        while (i->i_e == NULL) {
                if (i->i_indx-- == 0)
                        return (NULL);

                i->i_e = i->i_h->h_table[i->i_indx];
        }

        key = i->i_e->e_key;
        i->i_e = i->i_e->e_next;

        if (i->i_e)
                i->i_coll++;

        return (key);
}