ipp/ipgpc/table.c

/*
 * 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.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#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;
		}
	}
}