Home | History | Annotate | Download | only in src
      1 
      2 /* Author : Stephen Smalley, <sds (at) epoch.ncsc.mil> */
      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