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 #include <ipp/ipgpc/filters.h>
28*7c478bd9Sstevel@tonic-gate
29*7c478bd9Sstevel@tonic-gate /* table structure used for exact-match classification of selectors */
30*7c478bd9Sstevel@tonic-gate
31*7c478bd9Sstevel@tonic-gate /* Statics */
32*7c478bd9Sstevel@tonic-gate static int ht_hash(int);
33*7c478bd9Sstevel@tonic-gate static linked_list ht_search(hash_table, int);
34*7c478bd9Sstevel@tonic-gate static void remove_num_inserted(table_id_t *);
35*7c478bd9Sstevel@tonic-gate
36*7c478bd9Sstevel@tonic-gate /*
37*7c478bd9Sstevel@tonic-gate * ht_hash(a)
38*7c478bd9Sstevel@tonic-gate *
39*7c478bd9Sstevel@tonic-gate * hash function for keys (a) of type int
40*7c478bd9Sstevel@tonic-gate */
41*7c478bd9Sstevel@tonic-gate static int
ht_hash(int a)42*7c478bd9Sstevel@tonic-gate ht_hash(int a)
43*7c478bd9Sstevel@tonic-gate {
44*7c478bd9Sstevel@tonic-gate return (a % TABLE_SIZE);
45*7c478bd9Sstevel@tonic-gate }
46*7c478bd9Sstevel@tonic-gate
47*7c478bd9Sstevel@tonic-gate /*
48*7c478bd9Sstevel@tonic-gate * ht_insert(taid, id, key)
49*7c478bd9Sstevel@tonic-gate *
50*7c478bd9Sstevel@tonic-gate * inserts id into table with filter_id as the value
51*7c478bd9Sstevel@tonic-gate * if key == taid->wildcard, the key is inserted as a wildcard
52*7c478bd9Sstevel@tonic-gate * statistics are updated after insert is successful
53*7c478bd9Sstevel@tonic-gate * returns DONTCARE_VALUE if key == wildcard, NORMAL_VALUE otherwise
54*7c478bd9Sstevel@tonic-gate */
55*7c478bd9Sstevel@tonic-gate int
ht_insert(table_id_t * taid,key_t id,int key)56*7c478bd9Sstevel@tonic-gate ht_insert(table_id_t *taid, key_t id, int key)
57*7c478bd9Sstevel@tonic-gate {
58*7c478bd9Sstevel@tonic-gate int x;
59*7c478bd9Sstevel@tonic-gate ht_node_t *p;
60*7c478bd9Sstevel@tonic-gate hash_table table = taid->table;
61*7c478bd9Sstevel@tonic-gate
62*7c478bd9Sstevel@tonic-gate /* check if dontcare */
63*7c478bd9Sstevel@tonic-gate if (key == taid->wildcard) {
64*7c478bd9Sstevel@tonic-gate /* don't cares/wildcards are not inserted */
65*7c478bd9Sstevel@tonic-gate ++taid->stats.num_dontcare;
66*7c478bd9Sstevel@tonic-gate return (DONTCARE_VALUE);
67*7c478bd9Sstevel@tonic-gate }
68*7c478bd9Sstevel@tonic-gate
69*7c478bd9Sstevel@tonic-gate x = ht_hash(key);
70*7c478bd9Sstevel@tonic-gate /*
71*7c478bd9Sstevel@tonic-gate * insert if key matches and entry is being used or if entry is empty
72*7c478bd9Sstevel@tonic-gate */
73*7c478bd9Sstevel@tonic-gate if (((table[x].key == key) && (table[x].info == 1)) ||
74*7c478bd9Sstevel@tonic-gate (table[x].info == 0)) {
75*7c478bd9Sstevel@tonic-gate table[x].key = key;
76*7c478bd9Sstevel@tonic-gate table[x].info = 1;
77*7c478bd9Sstevel@tonic-gate (void) ipgpc_list_insert(&table[x].elements, id);
78*7c478bd9Sstevel@tonic-gate } else if (table[x].next == NULL) {
79*7c478bd9Sstevel@tonic-gate table[x].next = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
80*7c478bd9Sstevel@tonic-gate table[x].next->elements = NULL;
81*7c478bd9Sstevel@tonic-gate table[x].next->next = NULL;
82*7c478bd9Sstevel@tonic-gate table[x].next->key = key;
83*7c478bd9Sstevel@tonic-gate table[x].next->info = 1;
84*7c478bd9Sstevel@tonic-gate (void) ipgpc_list_insert(&table[x].next->elements, id);
85*7c478bd9Sstevel@tonic-gate } else {
86*7c478bd9Sstevel@tonic-gate p = table[x].next;
87*7c478bd9Sstevel@tonic-gate while (p != NULL) {
88*7c478bd9Sstevel@tonic-gate if (((p->key == key) && (p->info == 1)) ||
89*7c478bd9Sstevel@tonic-gate (p->info == 0)) {
90*7c478bd9Sstevel@tonic-gate p->key = key;
91*7c478bd9Sstevel@tonic-gate p->info = 1;
92*7c478bd9Sstevel@tonic-gate (void) ipgpc_list_insert(&p->elements, id);
93*7c478bd9Sstevel@tonic-gate if (taid->info.dontcareonly == B_TRUE) {
94*7c478bd9Sstevel@tonic-gate taid->info.dontcareonly = B_FALSE;
95*7c478bd9Sstevel@tonic-gate }
96*7c478bd9Sstevel@tonic-gate return (NORMAL_VALUE);
97*7c478bd9Sstevel@tonic-gate }
98*7c478bd9Sstevel@tonic-gate p = p->next;
99*7c478bd9Sstevel@tonic-gate }
100*7c478bd9Sstevel@tonic-gate p = kmem_cache_alloc(ht_node_cache, KM_SLEEP);
101*7c478bd9Sstevel@tonic-gate p->elements = NULL;
102*7c478bd9Sstevel@tonic-gate p->next = NULL;
103*7c478bd9Sstevel@tonic-gate p->key = key;
104*7c478bd9Sstevel@tonic-gate p->info = 1;
105*7c478bd9Sstevel@tonic-gate (void) ipgpc_list_insert(&p->elements, id);
106*7c478bd9Sstevel@tonic-gate p->next = table[x].next;
107*7c478bd9Sstevel@tonic-gate table[x].next = p->next;
108*7c478bd9Sstevel@tonic-gate }
109*7c478bd9Sstevel@tonic-gate /* update stats */
110*7c478bd9Sstevel@tonic-gate ++taid->stats.num_inserted;
111*7c478bd9Sstevel@tonic-gate if (taid->info.dontcareonly == B_TRUE) {
112*7c478bd9Sstevel@tonic-gate taid->info.dontcareonly = B_FALSE;
113*7c478bd9Sstevel@tonic-gate }
114*7c478bd9Sstevel@tonic-gate return (NORMAL_VALUE);
115*7c478bd9Sstevel@tonic-gate }
116*7c478bd9Sstevel@tonic-gate
117*7c478bd9Sstevel@tonic-gate /*
118*7c478bd9Sstevel@tonic-gate * ht_search(table, key)
119*7c478bd9Sstevel@tonic-gate *
120*7c478bd9Sstevel@tonic-gate * searches for key and returns the linked list value associated with key if
121*7c478bd9Sstevel@tonic-gate * found in table. NULL is returned if key not found
122*7c478bd9Sstevel@tonic-gate */
123*7c478bd9Sstevel@tonic-gate static linked_list
ht_search(hash_table table,int key)124*7c478bd9Sstevel@tonic-gate ht_search(hash_table table, int key)
125*7c478bd9Sstevel@tonic-gate {
126*7c478bd9Sstevel@tonic-gate int x;
127*7c478bd9Sstevel@tonic-gate ht_node_t *p = NULL;
128*7c478bd9Sstevel@tonic-gate
129*7c478bd9Sstevel@tonic-gate x = ht_hash(key);
130*7c478bd9Sstevel@tonic-gate if ((table[x].key == key) && (table[x].info == 1)) {
131*7c478bd9Sstevel@tonic-gate return (table[x].elements);
132*7c478bd9Sstevel@tonic-gate } else {
133*7c478bd9Sstevel@tonic-gate p = table[x].next;
134*7c478bd9Sstevel@tonic-gate while (p != NULL) {
135*7c478bd9Sstevel@tonic-gate if ((p->key == key) && (p->info == 1)) {
136*7c478bd9Sstevel@tonic-gate return (p->elements);
137*7c478bd9Sstevel@tonic-gate }
138*7c478bd9Sstevel@tonic-gate p = p->next;
139*7c478bd9Sstevel@tonic-gate }
140*7c478bd9Sstevel@tonic-gate return (NULL);
141*7c478bd9Sstevel@tonic-gate }
142*7c478bd9Sstevel@tonic-gate }
143*7c478bd9Sstevel@tonic-gate
144*7c478bd9Sstevel@tonic-gate /*
145*7c478bd9Sstevel@tonic-gate * ht_retrieve(taid, key, fid_table)
146*7c478bd9Sstevel@tonic-gate *
147*7c478bd9Sstevel@tonic-gate * All exact matches and wildcard matches are collected and inserted
148*7c478bd9Sstevel@tonic-gate * into the fid_table
149*7c478bd9Sstevel@tonic-gate * the number of found filters that match the input key are returned
150*7c478bd9Sstevel@tonic-gate * returns (-1) if memory error
151*7c478bd9Sstevel@tonic-gate */
152*7c478bd9Sstevel@tonic-gate int
ht_retrieve(table_id_t * taid,int key,ht_match_t * fid_table)153*7c478bd9Sstevel@tonic-gate ht_retrieve(table_id_t *taid, int key, ht_match_t *fid_table)
154*7c478bd9Sstevel@tonic-gate {
155*7c478bd9Sstevel@tonic-gate int num_found = 0;
156*7c478bd9Sstevel@tonic-gate linked_list alist = NULL;
157*7c478bd9Sstevel@tonic-gate hash_table table = taid->table;
158*7c478bd9Sstevel@tonic-gate
159*7c478bd9Sstevel@tonic-gate /* dontcare/wildcards are not inserted */
160*7c478bd9Sstevel@tonic-gate if (key == taid->wildcard) {
161*7c478bd9Sstevel@tonic-gate return (0);
162*7c478bd9Sstevel@tonic-gate } else {
163*7c478bd9Sstevel@tonic-gate alist = ht_search(table, key);
164*7c478bd9Sstevel@tonic-gate if (alist != NULL) {
165*7c478bd9Sstevel@tonic-gate if ((num_found = ipgpc_mark_found(taid->info.mask,
166*7c478bd9Sstevel@tonic-gate alist, fid_table)) == -1) {
167*7c478bd9Sstevel@tonic-gate return (-1); /* signifies memory error */
168*7c478bd9Sstevel@tonic-gate }
169*7c478bd9Sstevel@tonic-gate }
170*7c478bd9Sstevel@tonic-gate }
171*7c478bd9Sstevel@tonic-gate return (num_found);
172*7c478bd9Sstevel@tonic-gate }
173*7c478bd9Sstevel@tonic-gate
174*7c478bd9Sstevel@tonic-gate /*
175*7c478bd9Sstevel@tonic-gate * remove_num_inserted(taid)
176*7c478bd9Sstevel@tonic-gate *
177*7c478bd9Sstevel@tonic-gate * updates the num_inserted statistics along with reseting the dontcareonly
178*7c478bd9Sstevel@tonic-gate * flag when applicable and decrementing the total inserted
179*7c478bd9Sstevel@tonic-gate */
180*7c478bd9Sstevel@tonic-gate static void
remove_num_inserted(table_id_t * taid)181*7c478bd9Sstevel@tonic-gate remove_num_inserted(table_id_t *taid)
182*7c478bd9Sstevel@tonic-gate {
183*7c478bd9Sstevel@tonic-gate --taid->stats.num_inserted;
184*7c478bd9Sstevel@tonic-gate if (taid->stats.num_inserted <= 0) {
185*7c478bd9Sstevel@tonic-gate taid->info.dontcareonly = B_TRUE;
186*7c478bd9Sstevel@tonic-gate }
187*7c478bd9Sstevel@tonic-gate }
188*7c478bd9Sstevel@tonic-gate
189*7c478bd9Sstevel@tonic-gate /*
190*7c478bd9Sstevel@tonic-gate * ht_remove(taid, id, key)
191*7c478bd9Sstevel@tonic-gate *
192*7c478bd9Sstevel@tonic-gate * removes a single filter id item from the linked_list associated with id in
193*7c478bd9Sstevel@tonic-gate * table
194*7c478bd9Sstevel@tonic-gate */
195*7c478bd9Sstevel@tonic-gate void
ht_remove(table_id_t * taid,key_t id,int key)196*7c478bd9Sstevel@tonic-gate ht_remove(table_id_t *taid, key_t id, int key)
197*7c478bd9Sstevel@tonic-gate {
198*7c478bd9Sstevel@tonic-gate hash_table table = taid->table;
199*7c478bd9Sstevel@tonic-gate int x;
200*7c478bd9Sstevel@tonic-gate ht_node_t *p;
201*7c478bd9Sstevel@tonic-gate ht_node_t *t;
202*7c478bd9Sstevel@tonic-gate
203*7c478bd9Sstevel@tonic-gate /* check if dontcare */
204*7c478bd9Sstevel@tonic-gate if (key == taid->wildcard) {
205*7c478bd9Sstevel@tonic-gate /* don't cares/wildcards are not inserted */
206*7c478bd9Sstevel@tonic-gate --taid->stats.num_dontcare;
207*7c478bd9Sstevel@tonic-gate return;
208*7c478bd9Sstevel@tonic-gate }
209*7c478bd9Sstevel@tonic-gate x = ht_hash(key);
210*7c478bd9Sstevel@tonic-gate /* remove entry if key matches and entry is being used */
211*7c478bd9Sstevel@tonic-gate if ((table[x].key == key) && (table[x].info == 1)) {
212*7c478bd9Sstevel@tonic-gate if (table[x].elements != NULL) {
213*7c478bd9Sstevel@tonic-gate if (ipgpc_list_remove(&table[x].elements, id)) {
214*7c478bd9Sstevel@tonic-gate /* update stats */
215*7c478bd9Sstevel@tonic-gate remove_num_inserted(taid);
216*7c478bd9Sstevel@tonic-gate }
217*7c478bd9Sstevel@tonic-gate }
218*7c478bd9Sstevel@tonic-gate if (table[x].elements == NULL) {
219*7c478bd9Sstevel@tonic-gate /* reclaim memory if possible */
220*7c478bd9Sstevel@tonic-gate if (table[x].next != NULL) {
221*7c478bd9Sstevel@tonic-gate table[x].elements = table[x].next->elements;
222*7c478bd9Sstevel@tonic-gate table[x].info = table[x].next->info;
223*7c478bd9Sstevel@tonic-gate table[x].key = table[x].next->key;
224*7c478bd9Sstevel@tonic-gate p = table[x].next; /* use p as temp */
225*7c478bd9Sstevel@tonic-gate table[x].next = table[x].next->next;
226*7c478bd9Sstevel@tonic-gate kmem_cache_free(ht_node_cache, p);
227*7c478bd9Sstevel@tonic-gate } else {
228*7c478bd9Sstevel@tonic-gate table[x].info = 0; /* mark entry as empty */
229*7c478bd9Sstevel@tonic-gate table[x].key = 0;
230*7c478bd9Sstevel@tonic-gate }
231*7c478bd9Sstevel@tonic-gate }
232*7c478bd9Sstevel@tonic-gate } else {
233*7c478bd9Sstevel@tonic-gate p = &table[x];
234*7c478bd9Sstevel@tonic-gate while (p->next != NULL) {
235*7c478bd9Sstevel@tonic-gate if ((p->next->key == key) && (p->next->info == 1)) {
236*7c478bd9Sstevel@tonic-gate if (ipgpc_list_remove(&p->next->elements, id)) {
237*7c478bd9Sstevel@tonic-gate /* update stats */
238*7c478bd9Sstevel@tonic-gate remove_num_inserted(taid);
239*7c478bd9Sstevel@tonic-gate }
240*7c478bd9Sstevel@tonic-gate if (p->next->elements == NULL) {
241*7c478bd9Sstevel@tonic-gate /* reclaim memory if possible */
242*7c478bd9Sstevel@tonic-gate if (p->next->next == NULL) {
243*7c478bd9Sstevel@tonic-gate kmem_cache_free(ht_node_cache,
244*7c478bd9Sstevel@tonic-gate p->next);
245*7c478bd9Sstevel@tonic-gate p->next = NULL;
246*7c478bd9Sstevel@tonic-gate } else {
247*7c478bd9Sstevel@tonic-gate t = p->next;
248*7c478bd9Sstevel@tonic-gate p->next = p->next->next;
249*7c478bd9Sstevel@tonic-gate kmem_cache_free(ht_node_cache,
250*7c478bd9Sstevel@tonic-gate t);
251*7c478bd9Sstevel@tonic-gate }
252*7c478bd9Sstevel@tonic-gate }
253*7c478bd9Sstevel@tonic-gate return;
254*7c478bd9Sstevel@tonic-gate }
255*7c478bd9Sstevel@tonic-gate p = p->next;
256*7c478bd9Sstevel@tonic-gate }
257*7c478bd9Sstevel@tonic-gate }
258*7c478bd9Sstevel@tonic-gate }
259