xref: /illumos-gate/usr/src/uts/common/ipp/ipgpc/table.c (revision 7c478bd9)
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 */
34 static int ht_hash(int);
35 static linked_list ht_search(hash_table, int);
36 static void remove_num_inserted(table_id_t *);
37 
38 /*
39  * ht_hash(a)
40  *
41  * hash function for keys (a) of type int
42  */
43 static int
ht_hash(int a)44 ht_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  */
57 int
ht_insert(table_id_t * taid,key_t id,int key)58 ht_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  */
125 static linked_list
ht_search(hash_table table,int key)126 ht_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  */
154 int
ht_retrieve(table_id_t * taid,int key,ht_match_t * fid_table)155 ht_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  */
182 static void
remove_num_inserted(table_id_t * taid)183 remove_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  */
197 void
ht_remove(table_id_t * taid,key_t id,int key)198 ht_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