1 2 /* Author : Stephen Smalley, <sds (at) tycho.nsa.gov> */ 3 4 /* 5 * Updated : Karl MacMillan <kmacmillan (at) mentalrootkit.com> 6 * 7 * Copyright (C) 2007 Red Hat, Inc. 8 * 9 * This library is free software; you can redistribute it and/or 10 * modify it under the terms of the GNU Lesser General Public 11 * License as published by the Free Software Foundation; either 12 * version 2.1 of the License, or (at your option) any later version. 13 * 14 * This library is distributed in the hope that it will be useful, 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 * Lesser General Public License for more details. 18 * 19 * You should have received a copy of the GNU Lesser General Public 20 * License along with this library; if not, write to the Free Software 21 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 22 */ 23 24 25 /* FLASK */ 26 27 /* 28 * Implementation of the hash table type. 29 */ 30 31 #include <stdlib.h> 32 #include <string.h> 33 #include <sepol/policydb/hashtab.h> 34 35 hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, 36 const_hashtab_key_t key), 37 int (*keycmp) (hashtab_t h, 38 const_hashtab_key_t key1, 39 const_hashtab_key_t key2), 40 unsigned int size) 41 { 42 43 hashtab_t p; 44 unsigned int i; 45 46 p = (hashtab_t) malloc(sizeof(hashtab_val_t)); 47 if (p == NULL) 48 return p; 49 50 memset(p, 0, sizeof(hashtab_val_t)); 51 p->size = size; 52 p->nel = 0; 53 p->hash_value = hash_value; 54 p->keycmp = keycmp; 55 p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size); 56 if (p->htable == NULL) { 57 free(p); 58 return NULL; 59 } 60 for (i = 0; i < size; i++) 61 p->htable[i] = (hashtab_ptr_t) NULL; 62 63 return p; 64 } 65 66 int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum) 67 { 68 int hvalue; 69 hashtab_ptr_t prev, cur, newnode; 70 71 if (!h) 72 return SEPOL_ENOMEM; 73 74 hvalue = h->hash_value(h, key); 75 prev = NULL; 76 cur = h->htable[hvalue]; 77 while (cur && h->keycmp(h, key, cur->key) > 0) { 78 prev = cur; 79 cur = cur->next; 80 } 81 82 if (cur && (h->keycmp(h, key, cur->key) == 0)) 83 return SEPOL_EEXIST; 84 85 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 86 if (newnode == NULL) 87 return SEPOL_ENOMEM; 88 memset(newnode, 0, sizeof(struct hashtab_node)); 89 newnode->key = key; 90 newnode->datum = datum; 91 if (prev) { 92 newnode->next = prev->next; 93 prev->next = newnode; 94 } else { 95 newnode->next = h->htable[hvalue]; 96 h->htable[hvalue] = newnode; 97 } 98 99 h->nel++; 100 return SEPOL_OK; 101 } 102 103 int hashtab_remove(hashtab_t h, hashtab_key_t key, 104 void (*destroy) (hashtab_key_t k, 105 hashtab_datum_t d, void *args), void *args) 106 { 107 int hvalue; 108 hashtab_ptr_t cur, last; 109 110 if (!h) 111 return SEPOL_ENOENT; 112 113 hvalue = h->hash_value(h, key); 114 last = NULL; 115 cur = h->htable[hvalue]; 116 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 117 last = cur; 118 cur = cur->next; 119 } 120 121 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 122 return SEPOL_ENOENT; 123 124 if (last == NULL) 125 h->htable[hvalue] = cur->next; 126 else 127 last->next = cur->next; 128 129 if (destroy) 130 destroy(cur->key, cur->datum, args); 131 free(cur); 132 h->nel--; 133 return SEPOL_OK; 134 } 135 136 int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum, 137 void (*destroy) (hashtab_key_t k, 138 hashtab_datum_t d, void *args), void *args) 139 { 140 int hvalue; 141 hashtab_ptr_t prev, cur, newnode; 142 143 if (!h) 144 return SEPOL_ENOMEM; 145 146 hvalue = h->hash_value(h, key); 147 prev = NULL; 148 cur = h->htable[hvalue]; 149 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { 150 prev = cur; 151 cur = cur->next; 152 } 153 154 if (cur && (h->keycmp(h, key, cur->key) == 0)) { 155 if (destroy) 156 destroy(cur->key, cur->datum, args); 157 cur->key = key; 158 cur->datum = datum; 159 } else { 160 newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); 161 if (newnode == NULL) 162 return SEPOL_ENOMEM; 163 memset(newnode, 0, sizeof(struct hashtab_node)); 164 newnode->key = key; 165 newnode->datum = datum; 166 if (prev) { 167 newnode->next = prev->next; 168 prev->next = newnode; 169 } else { 170 newnode->next = h->htable[hvalue]; 171 h->htable[hvalue] = newnode; 172 } 173 } 174 175 return SEPOL_OK; 176 } 177 178 hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key) 179 { 180 181 int hvalue; 182 hashtab_ptr_t cur; 183 184 if (!h) 185 return NULL; 186 187 hvalue = h->hash_value(h, key); 188 cur = h->htable[hvalue]; 189 while (cur != NULL && h->keycmp(h, key, cur->key) > 0) 190 cur = cur->next; 191 192 if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) 193 return NULL; 194 195 return cur->datum; 196 } 197 198 void hashtab_destroy(hashtab_t h) 199 { 200 unsigned int i; 201 hashtab_ptr_t cur, temp; 202 203 if (!h) 204 return; 205 206 for (i = 0; i < h->size; i++) { 207 cur = h->htable[i]; 208 while (cur != NULL) { 209 temp = cur; 210 cur = cur->next; 211 free(temp); 212 } 213 h->htable[i] = NULL; 214 } 215 216 free(h->htable); 217 h->htable = NULL; 218 219 free(h); 220 } 221 222 int hashtab_map(hashtab_t h, 223 int (*apply) (hashtab_key_t k, 224 hashtab_datum_t d, void *args), void *args) 225 { 226 unsigned int i, ret; 227 hashtab_ptr_t cur; 228 229 if (!h) 230 return SEPOL_OK; 231 232 for (i = 0; i < h->size; i++) { 233 cur = h->htable[i]; 234 while (cur != NULL) { 235 ret = apply(cur->key, cur->datum, args); 236 if (ret) 237 return ret; 238 cur = cur->next; 239 } 240 } 241 return SEPOL_OK; 242 } 243 244 void hashtab_map_remove_on_error(hashtab_t h, 245 int (*apply) (hashtab_key_t k, 246 hashtab_datum_t d, 247 void *args), 248 void (*destroy) (hashtab_key_t k, 249 hashtab_datum_t d, 250 void *args), void *args) 251 { 252 unsigned int i; 253 int ret; 254 hashtab_ptr_t last, cur, temp; 255 256 if (!h) 257 return; 258 259 for (i = 0; i < h->size; i++) { 260 last = NULL; 261 cur = h->htable[i]; 262 while (cur != NULL) { 263 ret = apply(cur->key, cur->datum, args); 264 if (ret) { 265 if (last) { 266 last->next = cur->next; 267 } else { 268 h->htable[i] = cur->next; 269 } 270 271 temp = cur; 272 cur = cur->next; 273 if (destroy) 274 destroy(temp->key, temp->datum, args); 275 free(temp); 276 h->nel--; 277 } else { 278 last = cur; 279 cur = cur->next; 280 } 281 } 282 } 283 284 return; 285 } 286 287 void hashtab_hash_eval(hashtab_t h, char *tag) 288 { 289 unsigned int i; 290 int chain_len, slots_used, max_chain_len; 291 hashtab_ptr_t cur; 292 293 slots_used = 0; 294 max_chain_len = 0; 295 for (i = 0; i < h->size; i++) { 296 cur = h->htable[i]; 297 if (cur) { 298 slots_used++; 299 chain_len = 0; 300 while (cur) { 301 chain_len++; 302 cur = cur->next; 303 } 304 305 if (chain_len > max_chain_len) 306 max_chain_len = chain_len; 307 } 308 } 309 310 printf 311 ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", 312 tag, h->nel, slots_used, h->size, max_chain_len); 313 } 314
