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 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 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 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 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 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 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