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