1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright 2002-2003 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27#pragma ident	"%Z%%M%	%I%	%E% SMI"
28
29#include <ipp/ipgpc/filters.h>
30
31/* table structure used for exact-match classification of selectors */
32
33/* Statics */
34static int ht_hash(int);
35static linked_list ht_search(hash_table, int);
36static void remove_num_inserted(table_id_t *);
37
38/*
39 * ht_hash(a)
40 *
41 * hash function for keys (a) of type int
42 */
43static int
44ht_hash(int a)
45{
46	return (a % TABLE_SIZE);
47}
48
49/*
50 * ht_insert(taid, id, key)
51 *
52 * inserts id into table with filter_id as the value
53 * if key == taid->wildcard, the key is inserted as a wildcard
54 * statistics are updated after insert is successful
55 * returns DONTCARE_VALUE if key == wildcard, NORMAL_VALUE otherwise
56 */
57int
58ht_insert(table_id_t *taid, key_t id, int key)
59{
60	int x;
61	ht_node_t *p;
62	hash_table table = taid->table;
63
64	/* check if dontcare */
65	if (key == taid->wildcard) {
66		/* don't cares/wildcards are not inserted */
67		++taid->stats.num_dontcare;
68		return (DONTCARE_VALUE);
69	}
70
71	x = ht_hash(key);
72	/*
73	 * insert if key matches and entry is being used or if entry is empty
74	 */
75	if (((table[x].key == key) && (table[x].info == 1)) ||
76	    (table[x].info == 0)) {
77		table[x].key = key;
78		table[x].info = 1;
79		(void) ipgpc_list_insert(&table[x].elements, id);
80	} else if (table[x].next == NULL) {
81		table[x].next = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
82		table[x].next->elements = NULL;
83		table[x].next->next = NULL;
84		table[x].next->key = key;
85		table[x].next->info = 1;
86		(void) ipgpc_list_insert(&table[x].next->elements, id);
87	} else {
88		p = table[x].next;
89		while (p != NULL) {
90			if (((p->key == key) && (p->info == 1)) ||
91			    (p->info == 0)) {
92				p->key = key;
93				p->info = 1;
94				(void) ipgpc_list_insert(&p->elements, id);
95				if (taid->info.dontcareonly == B_TRUE) {
96					taid->info.dontcareonly = B_FALSE;
97				}
98				return (NORMAL_VALUE);
99			}
100			p = p->next;
101		}
102		p = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
103		p->elements = NULL;
104		p->next = NULL;
105		p->key = key;
106		p->info = 1;
107		(void) ipgpc_list_insert(&p->elements, id);
108		p->next = table[x].next;
109		table[x].next = p->next;
110	}
111	/* update stats */
112	++taid->stats.num_inserted;
113	if (taid->info.dontcareonly == B_TRUE) {
114		taid->info.dontcareonly = B_FALSE;
115	}
116	return (NORMAL_VALUE);
117}
118
119/*
120 * ht_search(table, key)
121 *
122 * searches for key and returns the linked list value associated with key if
123 * found in table. NULL is returned if key not found
124 */
125static linked_list
126ht_search(hash_table table, int key)
127{
128	int x;
129	ht_node_t *p = NULL;
130
131	x = ht_hash(key);
132	if ((table[x].key == key) && (table[x].info == 1)) {
133		return (table[x].elements);
134	} else {
135		p = table[x].next;
136		while (p != NULL) {
137			if ((p->key == key) && (p->info == 1)) {
138				return (p->elements);
139			}
140			p = p->next;
141		}
142		return (NULL);
143	}
144}
145
146/*
147 * ht_retrieve(taid, key, fid_table)
148 *
149 * All exact matches and wildcard matches are collected and inserted
150 * into the fid_table
151 * the number of found filters that match the input key are returned
152 * returns (-1) if memory error
153 */
154int
155ht_retrieve(table_id_t *taid, int key, ht_match_t *fid_table)
156{
157	int num_found = 0;
158	linked_list alist = NULL;
159	hash_table table = taid->table;
160
161	/* dontcare/wildcards are not inserted */
162	if (key == taid->wildcard) {
163		return (0);
164	} else {
165		alist = ht_search(table, key);
166		if (alist != NULL) {
167			if ((num_found = ipgpc_mark_found(taid->info.mask,
168			    alist, fid_table)) == -1) {
169				return (-1); /* signifies memory error */
170			}
171		}
172	}
173	return (num_found);
174}
175
176/*
177 * remove_num_inserted(taid)
178 *
179 * updates the num_inserted statistics along with reseting the dontcareonly
180 * flag when applicable and decrementing the total inserted
181 */
182static void
183remove_num_inserted(table_id_t *taid)
184{
185	--taid->stats.num_inserted;
186	if (taid->stats.num_inserted <= 0) {
187		taid->info.dontcareonly = B_TRUE;
188	}
189}
190
191/*
192 * ht_remove(taid, id, key)
193 *
194 * removes a single filter id item from the linked_list associated with id in
195 * table
196 */
197void
198ht_remove(table_id_t *taid, key_t id, int key)
199{
200	hash_table table = taid->table;
201	int x;
202	ht_node_t *p;
203	ht_node_t *t;
204
205	/* check if dontcare */
206	if (key == taid->wildcard) {
207		/* don't cares/wildcards are not inserted */
208		--taid->stats.num_dontcare;
209		return;
210	}
211	x = ht_hash(key);
212	/* remove entry if key matches and entry is being used */
213	if ((table[x].key == key) && (table[x].info == 1)) {
214		if (table[x].elements != NULL) {
215			if (ipgpc_list_remove(&table[x].elements, id)) {
216				/* update stats */
217				remove_num_inserted(taid);
218			}
219		}
220		if (table[x].elements == NULL) {
221			/* reclaim memory if possible */
222			if (table[x].next != NULL) {
223				table[x].elements = table[x].next->elements;
224				table[x].info = table[x].next->info;
225				table[x].key = table[x].next->key;
226				p = table[x].next; /* use p as temp */
227				table[x].next = table[x].next->next;
228				kmem_cache_free(ht_node_cache, p);
229			} else {
230				table[x].info = 0; /* mark entry as empty */
231				table[x].key = 0;
232			}
233		}
234	} else {
235		p = &table[x];
236		while (p->next != NULL) {
237			if ((p->next->key == key) && (p->next->info == 1)) {
238				if (ipgpc_list_remove(&p->next->elements, id)) {
239					/* update stats */
240					remove_num_inserted(taid);
241				}
242				if (p->next->elements == NULL) {
243					/* reclaim memory if possible */
244					if (p->next->next == NULL) {
245						kmem_cache_free(ht_node_cache,
246						    p->next);
247						p->next = NULL;
248					} else {
249						t = p->next;
250						p->next = p->next->next;
251						kmem_cache_free(ht_node_cache,
252						    t);
253					}
254				}
255				return;
256			}
257			p = p->next;
258		}
259	}
260}
261