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