/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (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 2002-2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <ipp/ipgpc/filters.h>

/* table structure used for exact-match classification of selectors */

/* Statics */
static int ht_hash(int);
static linked_list ht_search(hash_table, int);
static void remove_num_inserted(table_id_t *);

/*
 * ht_hash(a)
 *
 * hash function for keys (a) of type int
 */
static int
ht_hash(int a)
{
        return (a % TABLE_SIZE);
}

/*
 * ht_insert(taid, id, key)
 *
 * inserts id into table with filter_id as the value
 * if key == taid->wildcard, the key is inserted as a wildcard
 * statistics are updated after insert is successful
 * returns DONTCARE_VALUE if key == wildcard, NORMAL_VALUE otherwise
 */
int
ht_insert(table_id_t *taid, key_t id, int key)
{
        int x;
        ht_node_t *p;
        hash_table table = taid->table;

        /* check if dontcare */
        if (key == taid->wildcard) {
                /* don't cares/wildcards are not inserted */
                ++taid->stats.num_dontcare;
                return (DONTCARE_VALUE);
        }

        x = ht_hash(key);
        /*
         * insert if key matches and entry is being used or if entry is empty
         */
        if (((table[x].key == key) && (table[x].info == 1)) ||
            (table[x].info == 0)) {
                table[x].key = key;
                table[x].info = 1;
                (void) ipgpc_list_insert(&table[x].elements, id);
        } else if (table[x].next == NULL) {
                table[x].next = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
                table[x].next->elements = NULL;
                table[x].next->next = NULL;
                table[x].next->key = key;
                table[x].next->info = 1;
                (void) ipgpc_list_insert(&table[x].next->elements, id);
        } else {
                p = table[x].next;
                while (p != NULL) {
                        if (((p->key == key) && (p->info == 1)) ||
                            (p->info == 0)) {
                                p->key = key;
                                p->info = 1;
                                (void) ipgpc_list_insert(&p->elements, id);
                                if (taid->info.dontcareonly == B_TRUE) {
                                        taid->info.dontcareonly = B_FALSE;
                                }
                                return (NORMAL_VALUE);
                        }
                        p = p->next;
                }
                p = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
                p->elements = NULL;
                p->next = NULL;
                p->key = key;
                p->info = 1;
                (void) ipgpc_list_insert(&p->elements, id);
                p->next = table[x].next;
                table[x].next = p->next;
        }
        /* update stats */
        ++taid->stats.num_inserted;
        if (taid->info.dontcareonly == B_TRUE) {
                taid->info.dontcareonly = B_FALSE;
        }
        return (NORMAL_VALUE);
}

/*
 * ht_search(table, key)
 *
 * searches for key and returns the linked list value associated with key if
 * found in table. NULL is returned if key not found
 */
static linked_list
ht_search(hash_table table, int key)
{
        int x;
        ht_node_t *p = NULL;

        x = ht_hash(key);
        if ((table[x].key == key) && (table[x].info == 1)) {
                return (table[x].elements);
        } else {
                p = table[x].next;
                while (p != NULL) {
                        if ((p->key == key) && (p->info == 1)) {
                                return (p->elements);
                        }
                        p = p->next;
                }
                return (NULL);
        }
}

/*
 * ht_retrieve(taid, key, fid_table)
 *
 * All exact matches and wildcard matches are collected and inserted
 * into the fid_table
 * the number of found filters that match the input key are returned
 * returns (-1) if memory error
 */
int
ht_retrieve(table_id_t *taid, int key, ht_match_t *fid_table)
{
        int num_found = 0;
        linked_list alist = NULL;
        hash_table table = taid->table;

        /* dontcare/wildcards are not inserted */
        if (key == taid->wildcard) {
                return (0);
        } else {
                alist = ht_search(table, key);
                if (alist != NULL) {
                        if ((num_found = ipgpc_mark_found(taid->info.mask,
                            alist, fid_table)) == -1) {
                                return (-1); /* signifies memory error */
                        }
                }
        }
        return (num_found);
}

/*
 * remove_num_inserted(taid)
 *
 * updates the num_inserted statistics along with reseting the dontcareonly
 * flag when applicable and decrementing the total inserted
 */
static void
remove_num_inserted(table_id_t *taid)
{
        --taid->stats.num_inserted;
        if (taid->stats.num_inserted <= 0) {
                taid->info.dontcareonly = B_TRUE;
        }
}

/*
 * ht_remove(taid, id, key)
 *
 * removes a single filter id item from the linked_list associated with id in
 * table
 */
void
ht_remove(table_id_t *taid, key_t id, int key)
{
        hash_table table = taid->table;
        int x;
        ht_node_t *p;
        ht_node_t *t;

        /* check if dontcare */
        if (key == taid->wildcard) {
                /* don't cares/wildcards are not inserted */
                --taid->stats.num_dontcare;
                return;
        }
        x = ht_hash(key);
        /* remove entry if key matches and entry is being used */
        if ((table[x].key == key) && (table[x].info == 1)) {
                if (table[x].elements != NULL) {
                        if (ipgpc_list_remove(&table[x].elements, id)) {
                                /* update stats */
                                remove_num_inserted(taid);
                        }
                }
                if (table[x].elements == NULL) {
                        /* reclaim memory if possible */
                        if (table[x].next != NULL) {
                                table[x].elements = table[x].next->elements;
                                table[x].info = table[x].next->info;
                                table[x].key = table[x].next->key;
                                p = table[x].next; /* use p as temp */
                                table[x].next = table[x].next->next;
                                kmem_cache_free(ht_node_cache, p);
                        } else {
                                table[x].info = 0; /* mark entry as empty */
                                table[x].key = 0;
                        }
                }
        } else {
                p = &table[x];
                while (p->next != NULL) {
                        if ((p->next->key == key) && (p->next->info == 1)) {
                                if (ipgpc_list_remove(&p->next->elements, id)) {
                                        /* update stats */
                                        remove_num_inserted(taid);
                                }
                                if (p->next->elements == NULL) {
                                        /* reclaim memory if possible */
                                        if (p->next->next == NULL) {
                                                kmem_cache_free(ht_node_cache,
                                                    p->next);
                                                p->next = NULL;
                                        } else {
                                                t = p->next;
                                                p->next = p->next->next;
                                                kmem_cache_free(ht_node_cache,
                                                    t);
                                        }
                                }
                                return;
                        }
                        p = p->next;
                }
        }
}