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