| |
| /* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ |
| |
| /* |
| * Updated : Karl MacMillan <kmacmillan@mentalrootkit.com> |
| * |
| * Copyright (C) 2007 Red Hat, Inc. |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Lesser General Public |
| * License as published by the Free Software Foundation; either |
| * version 2.1 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Lesser General Public License for more details. |
| * |
| * You should have received a copy of the GNU Lesser General Public |
| * License along with this library; if not, write to the Free Software |
| * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
| */ |
| |
| |
| /* FLASK */ |
| |
| /* |
| * Implementation of the hash table type. |
| */ |
| |
| #include <stdlib.h> |
| #include <string.h> |
| #include <sepol/policydb/hashtab.h> |
| |
| hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, |
| const hashtab_key_t key), |
| int (*keycmp) (hashtab_t h, |
| const hashtab_key_t key1, |
| const hashtab_key_t key2), |
| unsigned int size) |
| { |
| |
| hashtab_t p; |
| unsigned int i; |
| |
| p = (hashtab_t) malloc(sizeof(hashtab_val_t)); |
| if (p == NULL) |
| return p; |
| |
| memset(p, 0, sizeof(hashtab_val_t)); |
| p->size = size; |
| p->nel = 0; |
| p->hash_value = hash_value; |
| p->keycmp = keycmp; |
| p->htable = (hashtab_ptr_t *) malloc(sizeof(hashtab_ptr_t) * size); |
| if (p->htable == NULL) { |
| free(p); |
| return NULL; |
| } |
| for (i = 0; i < size; i++) |
| p->htable[i] = (hashtab_ptr_t) NULL; |
| |
| return p; |
| } |
| |
| int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum) |
| { |
| int hvalue; |
| hashtab_ptr_t prev, cur, newnode; |
| |
| if (!h) |
| return SEPOL_ENOMEM; |
| |
| hvalue = h->hash_value(h, key); |
| prev = NULL; |
| cur = h->htable[hvalue]; |
| while (cur && h->keycmp(h, key, cur->key) > 0) { |
| prev = cur; |
| cur = cur->next; |
| } |
| |
| if (cur && (h->keycmp(h, key, cur->key) == 0)) |
| return SEPOL_EEXIST; |
| |
| newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); |
| if (newnode == NULL) |
| return SEPOL_ENOMEM; |
| memset(newnode, 0, sizeof(struct hashtab_node)); |
| newnode->key = key; |
| newnode->datum = datum; |
| if (prev) { |
| newnode->next = prev->next; |
| prev->next = newnode; |
| } else { |
| newnode->next = h->htable[hvalue]; |
| h->htable[hvalue] = newnode; |
| } |
| |
| h->nel++; |
| return SEPOL_OK; |
| } |
| |
| int hashtab_remove(hashtab_t h, hashtab_key_t key, |
| void (*destroy) (hashtab_key_t k, |
| hashtab_datum_t d, void *args), void *args) |
| { |
| int hvalue; |
| hashtab_ptr_t cur, last; |
| |
| if (!h) |
| return SEPOL_ENOENT; |
| |
| hvalue = h->hash_value(h, key); |
| last = NULL; |
| cur = h->htable[hvalue]; |
| while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { |
| last = cur; |
| cur = cur->next; |
| } |
| |
| if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) |
| return SEPOL_ENOENT; |
| |
| if (last == NULL) |
| h->htable[hvalue] = cur->next; |
| else |
| last->next = cur->next; |
| |
| if (destroy) |
| destroy(cur->key, cur->datum, args); |
| free(cur); |
| h->nel--; |
| return SEPOL_OK; |
| } |
| |
| int hashtab_replace(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum, |
| void (*destroy) (hashtab_key_t k, |
| hashtab_datum_t d, void *args), void *args) |
| { |
| int hvalue; |
| hashtab_ptr_t prev, cur, newnode; |
| |
| if (!h) |
| return SEPOL_ENOMEM; |
| |
| hvalue = h->hash_value(h, key); |
| prev = NULL; |
| cur = h->htable[hvalue]; |
| while (cur != NULL && h->keycmp(h, key, cur->key) > 0) { |
| prev = cur; |
| cur = cur->next; |
| } |
| |
| if (cur && (h->keycmp(h, key, cur->key) == 0)) { |
| if (destroy) |
| destroy(cur->key, cur->datum, args); |
| cur->key = key; |
| cur->datum = datum; |
| } else { |
| newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); |
| if (newnode == NULL) |
| return SEPOL_ENOMEM; |
| memset(newnode, 0, sizeof(struct hashtab_node)); |
| newnode->key = key; |
| newnode->datum = datum; |
| if (prev) { |
| newnode->next = prev->next; |
| prev->next = newnode; |
| } else { |
| newnode->next = h->htable[hvalue]; |
| h->htable[hvalue] = newnode; |
| } |
| } |
| |
| return SEPOL_OK; |
| } |
| |
| hashtab_datum_t hashtab_search(hashtab_t h, const hashtab_key_t key) |
| { |
| |
| int hvalue; |
| hashtab_ptr_t cur; |
| |
| if (!h) |
| return NULL; |
| |
| hvalue = h->hash_value(h, key); |
| cur = h->htable[hvalue]; |
| while (cur != NULL && h->keycmp(h, key, cur->key) > 0) |
| cur = cur->next; |
| |
| if (cur == NULL || (h->keycmp(h, key, cur->key) != 0)) |
| return NULL; |
| |
| return cur->datum; |
| } |
| |
| void hashtab_destroy(hashtab_t h) |
| { |
| unsigned int i; |
| hashtab_ptr_t cur, temp; |
| |
| if (!h) |
| return; |
| |
| for (i = 0; i < h->size; i++) { |
| cur = h->htable[i]; |
| while (cur != NULL) { |
| temp = cur; |
| cur = cur->next; |
| free(temp); |
| } |
| h->htable[i] = NULL; |
| } |
| |
| free(h->htable); |
| h->htable = NULL; |
| |
| free(h); |
| } |
| |
| int hashtab_map(hashtab_t h, |
| int (*apply) (hashtab_key_t k, |
| hashtab_datum_t d, void *args), void *args) |
| { |
| unsigned int i, ret; |
| hashtab_ptr_t cur; |
| |
| if (!h) |
| return SEPOL_OK; |
| |
| for (i = 0; i < h->size; i++) { |
| cur = h->htable[i]; |
| while (cur != NULL) { |
| ret = apply(cur->key, cur->datum, args); |
| if (ret) |
| return ret; |
| cur = cur->next; |
| } |
| } |
| return SEPOL_OK; |
| } |
| |
| void hashtab_map_remove_on_error(hashtab_t h, |
| int (*apply) (hashtab_key_t k, |
| hashtab_datum_t d, |
| void *args), |
| void (*destroy) (hashtab_key_t k, |
| hashtab_datum_t d, |
| void *args), void *args) |
| { |
| unsigned int i; |
| int ret; |
| hashtab_ptr_t last, cur, temp; |
| |
| if (!h) |
| return; |
| |
| for (i = 0; i < h->size; i++) { |
| last = NULL; |
| cur = h->htable[i]; |
| while (cur != NULL) { |
| ret = apply(cur->key, cur->datum, args); |
| if (ret) { |
| if (last) { |
| last->next = cur->next; |
| } else { |
| h->htable[i] = cur->next; |
| } |
| |
| temp = cur; |
| cur = cur->next; |
| if (destroy) |
| destroy(temp->key, temp->datum, args); |
| free(temp); |
| h->nel--; |
| } else { |
| last = cur; |
| cur = cur->next; |
| } |
| } |
| } |
| |
| return; |
| } |
| |
| void hashtab_hash_eval(hashtab_t h, char *tag) |
| { |
| unsigned int i; |
| int chain_len, slots_used, max_chain_len; |
| hashtab_ptr_t cur; |
| |
| slots_used = 0; |
| max_chain_len = 0; |
| for (i = 0; i < h->size; i++) { |
| cur = h->htable[i]; |
| if (cur) { |
| slots_used++; |
| chain_len = 0; |
| while (cur) { |
| chain_len++; |
| cur = cur->next; |
| } |
| |
| if (chain_len > max_chain_len) |
| max_chain_len = chain_len; |
| } |
| } |
| |
| printf |
| ("%s: %d entries and %d/%d buckets used, longest chain length %d\n", |
| tag, h->nel, slots_used, h->size, max_chain_len); |
| } |