| Message ID | 20230308095308.60661-2-wanghuizhao1@huawei.com (mailing list archive) |
|---|---|
| State | Accepted |
| Delegated to: | Petr Lautrbach |
| Headers | show |
| Series | Improve efficiency of detecting duplicate in libselinux | expand |
On Wed, Mar 8, 2023 at 4:53 AM wanghuizhao <wanghuizhao1@huawei.com> wrote: > > To use hashtab in libselinux, migrate the existing hashtab template > from policycoreutils/newrole to libselinux. > > Signed-off-by: wanghuizhao <wanghuizhao1@huawei.com> For these three patches: Acked-by: James Carter <jwcart2@gmail.com> > --- > libselinux/src/hashtab.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++ > libselinux/src/hashtab.h | 115 ++++++++++++++++++++++++++ > 2 files changed, 323 insertions(+) > create mode 100644 libselinux/src/hashtab.c > create mode 100644 libselinux/src/hashtab.h > > diff --git a/libselinux/src/hashtab.c b/libselinux/src/hashtab.c > new file mode 100644 > index 00000000..26d4f4c7 > --- /dev/null > +++ b/libselinux/src/hashtab.c > @@ -0,0 +1,208 @@ > + > +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ > + > +/* FLASK */ > + > +/* > + * Implementation of the hash table type. > + */ > + > +#include <stdlib.h> > +#include <string.h> > +#include "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) > +{ > + unsigned int hvalue; > + hashtab_ptr_t prev, cur, newnode; > + > + if (!h) > + return HASHTAB_OVERFLOW; > + > + 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 HASHTAB_PRESENT; > + > + newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); > + if (newnode == NULL) > + return HASHTAB_OVERFLOW; > + 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 HASHTAB_SUCCESS; > +} > + > +int hashtab_remove(hashtab_t h, hashtab_key_t key, > + void (*destroy) (hashtab_key_t k, > + hashtab_datum_t d, void *args), void *args) > +{ > + unsigned int hvalue; > + hashtab_ptr_t cur, last; > + > + if (!h) > + return HASHTAB_MISSING; > + > + 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 HASHTAB_MISSING; > + > + 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 HASHTAB_SUCCESS; > +} > + > +hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key) > +{ > + > + unsigned 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; > + hashtab_ptr_t cur; > + int ret; > + > + if (!h) > + return HASHTAB_SUCCESS; > + > + 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 HASHTAB_SUCCESS; > +} > + > +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); > +} > diff --git a/libselinux/src/hashtab.h b/libselinux/src/hashtab.h > new file mode 100644 > index 00000000..78471269 > --- /dev/null > +++ b/libselinux/src/hashtab.h > @@ -0,0 +1,115 @@ > + > +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ > + > +/* FLASK */ > + > +/* > + * A hash table (hashtab) maintains associations between > + * key values and datum values. The type of the key values > + * and the type of the datum values is arbitrary. The > + * functions for hash computation and key comparison are > + * provided by the creator of the table. > + */ > + > +#ifndef _NEWROLE_HASHTAB_H_ > +#define _NEWROLE_HASHTAB_H_ > + > +#include <stdint.h> > +#include <errno.h> > +#include <stdio.h> > + > +typedef char *hashtab_key_t; /* generic key type */ > +typedef const char *const_hashtab_key_t; /* constant generic key type */ > +typedef void *hashtab_datum_t; /* generic datum type */ > + > +typedef struct hashtab_node *hashtab_ptr_t; > + > +typedef struct hashtab_node { > + hashtab_key_t key; > + hashtab_datum_t datum; > + hashtab_ptr_t next; > +} hashtab_node_t; > + > +typedef struct hashtab_val { > + hashtab_ptr_t *htable; /* hash table */ > + unsigned int size; /* number of slots in hash table */ > + uint32_t nel; /* number of elements in hash table */ > + unsigned int (*hash_value) (struct hashtab_val * h, const_hashtab_key_t key); /* hash function */ > + int (*keycmp) (struct hashtab_val * h, const_hashtab_key_t key1, const_hashtab_key_t key2); /* key comparison function */ > +} hashtab_val_t; > + > +typedef hashtab_val_t *hashtab_t; > + > +/* Define status codes for hash table functions */ > +#define HASHTAB_SUCCESS 0 > +#define HASHTAB_OVERFLOW -ENOMEM > +#define HASHTAB_PRESENT -EEXIST > +#define HASHTAB_MISSING -ENOENT > + > +/* > + Creates a new hash table with the specified characteristics. > + > + Returns NULL if insufficient space is available or > + the new hash table otherwise. > + */ > +extern 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); > +/* > + Inserts the specified (key, datum) pair into the specified hash table. > + > + Returns HASHTAB_OVERFLOW if insufficient space is available or > + HASHTAB_PRESENT if there is already an entry with the same key or > + HASHTAB_SUCCESS otherwise. > + */ > +extern int hashtab_insert(hashtab_t h, hashtab_key_t k, hashtab_datum_t d); > + > +/* > + Removes the entry with the specified key from the hash table. > + Applies the specified destroy function to (key,datum,args) for > + the entry. > + > + Returns HASHTAB_MISSING if no entry has the specified key or > + HASHTAB_SUCCESS otherwise. > + */ > +extern int hashtab_remove(hashtab_t h, hashtab_key_t k, > + void (*destroy) (hashtab_key_t k, > + hashtab_datum_t d, > + void *args), void *args); > + > +/* > + Searches for the entry with the specified key in the hash table. > + > + Returns NULL if no entry has the specified key or > + the datum of the entry otherwise. > + */ > +extern hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t k); > + > +/* > + Destroys the specified hash table. > + */ > +extern void hashtab_destroy(hashtab_t h); > + > +/* > + Applies the specified apply function to (key,datum,args) > + for each entry in the specified hash table. > + > + The order in which the function is applied to the entries > + is dependent upon the internal structure of the hash table. > + > + If apply returns a non-zero status, then hashtab_map will cease > + iterating through the hash table and will propagate the error > + return to its caller. > + */ > +extern int hashtab_map(hashtab_t h, > + int (*apply) (hashtab_key_t k, > + hashtab_datum_t d, > + void *args), void *args); > + > +extern void hashtab_hash_eval(hashtab_t h, char *tag); > + > +#endif > -- > 2.12.3 >
On Wed, May 24, 2023 at 9:51 AM James Carter <jwcart2@gmail.com> wrote: > > On Wed, Mar 8, 2023 at 4:53 AM wanghuizhao <wanghuizhao1@huawei.com> wrote: > > > > To use hashtab in libselinux, migrate the existing hashtab template > > from policycoreutils/newrole to libselinux. > > > > Signed-off-by: wanghuizhao <wanghuizhao1@huawei.com> > > For these three patches: > Acked-by: James Carter <jwcart2@gmail.com> > These three patches have been merged. Thanks, Jim > > --- > > libselinux/src/hashtab.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++ > > libselinux/src/hashtab.h | 115 ++++++++++++++++++++++++++ > > 2 files changed, 323 insertions(+) > > create mode 100644 libselinux/src/hashtab.c > > create mode 100644 libselinux/src/hashtab.h > > > > diff --git a/libselinux/src/hashtab.c b/libselinux/src/hashtab.c > > new file mode 100644 > > index 00000000..26d4f4c7 > > --- /dev/null > > +++ b/libselinux/src/hashtab.c > > @@ -0,0 +1,208 @@ > > + > > +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ > > + > > +/* FLASK */ > > + > > +/* > > + * Implementation of the hash table type. > > + */ > > + > > +#include <stdlib.h> > > +#include <string.h> > > +#include "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) > > +{ > > + unsigned int hvalue; > > + hashtab_ptr_t prev, cur, newnode; > > + > > + if (!h) > > + return HASHTAB_OVERFLOW; > > + > > + 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 HASHTAB_PRESENT; > > + > > + newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); > > + if (newnode == NULL) > > + return HASHTAB_OVERFLOW; > > + 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 HASHTAB_SUCCESS; > > +} > > + > > +int hashtab_remove(hashtab_t h, hashtab_key_t key, > > + void (*destroy) (hashtab_key_t k, > > + hashtab_datum_t d, void *args), void *args) > > +{ > > + unsigned int hvalue; > > + hashtab_ptr_t cur, last; > > + > > + if (!h) > > + return HASHTAB_MISSING; > > + > > + 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 HASHTAB_MISSING; > > + > > + 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 HASHTAB_SUCCESS; > > +} > > + > > +hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key) > > +{ > > + > > + unsigned 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; > > + hashtab_ptr_t cur; > > + int ret; > > + > > + if (!h) > > + return HASHTAB_SUCCESS; > > + > > + 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 HASHTAB_SUCCESS; > > +} > > + > > +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); > > +} > > diff --git a/libselinux/src/hashtab.h b/libselinux/src/hashtab.h > > new file mode 100644 > > index 00000000..78471269 > > --- /dev/null > > +++ b/libselinux/src/hashtab.h > > @@ -0,0 +1,115 @@ > > + > > +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ > > + > > +/* FLASK */ > > + > > +/* > > + * A hash table (hashtab) maintains associations between > > + * key values and datum values. The type of the key values > > + * and the type of the datum values is arbitrary. The > > + * functions for hash computation and key comparison are > > + * provided by the creator of the table. > > + */ > > + > > +#ifndef _NEWROLE_HASHTAB_H_ > > +#define _NEWROLE_HASHTAB_H_ > > + > > +#include <stdint.h> > > +#include <errno.h> > > +#include <stdio.h> > > + > > +typedef char *hashtab_key_t; /* generic key type */ > > +typedef const char *const_hashtab_key_t; /* constant generic key type */ > > +typedef void *hashtab_datum_t; /* generic datum type */ > > + > > +typedef struct hashtab_node *hashtab_ptr_t; > > + > > +typedef struct hashtab_node { > > + hashtab_key_t key; > > + hashtab_datum_t datum; > > + hashtab_ptr_t next; > > +} hashtab_node_t; > > + > > +typedef struct hashtab_val { > > + hashtab_ptr_t *htable; /* hash table */ > > + unsigned int size; /* number of slots in hash table */ > > + uint32_t nel; /* number of elements in hash table */ > > + unsigned int (*hash_value) (struct hashtab_val * h, const_hashtab_key_t key); /* hash function */ > > + int (*keycmp) (struct hashtab_val * h, const_hashtab_key_t key1, const_hashtab_key_t key2); /* key comparison function */ > > +} hashtab_val_t; > > + > > +typedef hashtab_val_t *hashtab_t; > > + > > +/* Define status codes for hash table functions */ > > +#define HASHTAB_SUCCESS 0 > > +#define HASHTAB_OVERFLOW -ENOMEM > > +#define HASHTAB_PRESENT -EEXIST > > +#define HASHTAB_MISSING -ENOENT > > + > > +/* > > + Creates a new hash table with the specified characteristics. > > + > > + Returns NULL if insufficient space is available or > > + the new hash table otherwise. > > + */ > > +extern 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); > > +/* > > + Inserts the specified (key, datum) pair into the specified hash table. > > + > > + Returns HASHTAB_OVERFLOW if insufficient space is available or > > + HASHTAB_PRESENT if there is already an entry with the same key or > > + HASHTAB_SUCCESS otherwise. > > + */ > > +extern int hashtab_insert(hashtab_t h, hashtab_key_t k, hashtab_datum_t d); > > + > > +/* > > + Removes the entry with the specified key from the hash table. > > + Applies the specified destroy function to (key,datum,args) for > > + the entry. > > + > > + Returns HASHTAB_MISSING if no entry has the specified key or > > + HASHTAB_SUCCESS otherwise. > > + */ > > +extern int hashtab_remove(hashtab_t h, hashtab_key_t k, > > + void (*destroy) (hashtab_key_t k, > > + hashtab_datum_t d, > > + void *args), void *args); > > + > > +/* > > + Searches for the entry with the specified key in the hash table. > > + > > + Returns NULL if no entry has the specified key or > > + the datum of the entry otherwise. > > + */ > > +extern hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t k); > > + > > +/* > > + Destroys the specified hash table. > > + */ > > +extern void hashtab_destroy(hashtab_t h); > > + > > +/* > > + Applies the specified apply function to (key,datum,args) > > + for each entry in the specified hash table. > > + > > + The order in which the function is applied to the entries > > + is dependent upon the internal structure of the hash table. > > + > > + If apply returns a non-zero status, then hashtab_map will cease > > + iterating through the hash table and will propagate the error > > + return to its caller. > > + */ > > +extern int hashtab_map(hashtab_t h, > > + int (*apply) (hashtab_key_t k, > > + hashtab_datum_t d, > > + void *args), void *args); > > + > > +extern void hashtab_hash_eval(hashtab_t h, char *tag); > > + > > +#endif > > -- > > 2.12.3 > >
diff --git a/libselinux/src/hashtab.c b/libselinux/src/hashtab.c new file mode 100644 index 00000000..26d4f4c7 --- /dev/null +++ b/libselinux/src/hashtab.c @@ -0,0 +1,208 @@ + +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ + +/* FLASK */ + +/* + * Implementation of the hash table type. + */ + +#include <stdlib.h> +#include <string.h> +#include "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) +{ + unsigned int hvalue; + hashtab_ptr_t prev, cur, newnode; + + if (!h) + return HASHTAB_OVERFLOW; + + 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 HASHTAB_PRESENT; + + newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t)); + if (newnode == NULL) + return HASHTAB_OVERFLOW; + 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 HASHTAB_SUCCESS; +} + +int hashtab_remove(hashtab_t h, hashtab_key_t key, + void (*destroy) (hashtab_key_t k, + hashtab_datum_t d, void *args), void *args) +{ + unsigned int hvalue; + hashtab_ptr_t cur, last; + + if (!h) + return HASHTAB_MISSING; + + 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 HASHTAB_MISSING; + + 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 HASHTAB_SUCCESS; +} + +hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key) +{ + + unsigned 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; + hashtab_ptr_t cur; + int ret; + + if (!h) + return HASHTAB_SUCCESS; + + 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 HASHTAB_SUCCESS; +} + +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); +} diff --git a/libselinux/src/hashtab.h b/libselinux/src/hashtab.h new file mode 100644 index 00000000..78471269 --- /dev/null +++ b/libselinux/src/hashtab.h @@ -0,0 +1,115 @@ + +/* Author : Stephen Smalley, <sds@tycho.nsa.gov> */ + +/* FLASK */ + +/* + * A hash table (hashtab) maintains associations between + * key values and datum values. The type of the key values + * and the type of the datum values is arbitrary. The + * functions for hash computation and key comparison are + * provided by the creator of the table. + */ + +#ifndef _NEWROLE_HASHTAB_H_ +#define _NEWROLE_HASHTAB_H_ + +#include <stdint.h> +#include <errno.h> +#include <stdio.h> + +typedef char *hashtab_key_t; /* generic key type */ +typedef const char *const_hashtab_key_t; /* constant generic key type */ +typedef void *hashtab_datum_t; /* generic datum type */ + +typedef struct hashtab_node *hashtab_ptr_t; + +typedef struct hashtab_node { + hashtab_key_t key; + hashtab_datum_t datum; + hashtab_ptr_t next; +} hashtab_node_t; + +typedef struct hashtab_val { + hashtab_ptr_t *htable; /* hash table */ + unsigned int size; /* number of slots in hash table */ + uint32_t nel; /* number of elements in hash table */ + unsigned int (*hash_value) (struct hashtab_val * h, const_hashtab_key_t key); /* hash function */ + int (*keycmp) (struct hashtab_val * h, const_hashtab_key_t key1, const_hashtab_key_t key2); /* key comparison function */ +} hashtab_val_t; + +typedef hashtab_val_t *hashtab_t; + +/* Define status codes for hash table functions */ +#define HASHTAB_SUCCESS 0 +#define HASHTAB_OVERFLOW -ENOMEM +#define HASHTAB_PRESENT -EEXIST +#define HASHTAB_MISSING -ENOENT + +/* + Creates a new hash table with the specified characteristics. + + Returns NULL if insufficient space is available or + the new hash table otherwise. + */ +extern 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); +/* + Inserts the specified (key, datum) pair into the specified hash table. + + Returns HASHTAB_OVERFLOW if insufficient space is available or + HASHTAB_PRESENT if there is already an entry with the same key or + HASHTAB_SUCCESS otherwise. + */ +extern int hashtab_insert(hashtab_t h, hashtab_key_t k, hashtab_datum_t d); + +/* + Removes the entry with the specified key from the hash table. + Applies the specified destroy function to (key,datum,args) for + the entry. + + Returns HASHTAB_MISSING if no entry has the specified key or + HASHTAB_SUCCESS otherwise. + */ +extern int hashtab_remove(hashtab_t h, hashtab_key_t k, + void (*destroy) (hashtab_key_t k, + hashtab_datum_t d, + void *args), void *args); + +/* + Searches for the entry with the specified key in the hash table. + + Returns NULL if no entry has the specified key or + the datum of the entry otherwise. + */ +extern hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t k); + +/* + Destroys the specified hash table. + */ +extern void hashtab_destroy(hashtab_t h); + +/* + Applies the specified apply function to (key,datum,args) + for each entry in the specified hash table. + + The order in which the function is applied to the entries + is dependent upon the internal structure of the hash table. + + If apply returns a non-zero status, then hashtab_map will cease + iterating through the hash table and will propagate the error + return to its caller. + */ +extern int hashtab_map(hashtab_t h, + int (*apply) (hashtab_key_t k, + hashtab_datum_t d, + void *args), void *args); + +extern void hashtab_hash_eval(hashtab_t h, char *tag); + +#endif
To use hashtab in libselinux, migrate the existing hashtab template from policycoreutils/newrole to libselinux. Signed-off-by: wanghuizhao <wanghuizhao1@huawei.com> --- libselinux/src/hashtab.c | 208 +++++++++++++++++++++++++++++++++++++++++++++++ libselinux/src/hashtab.h | 115 ++++++++++++++++++++++++++ 2 files changed, 323 insertions(+) create mode 100644 libselinux/src/hashtab.c create mode 100644 libselinux/src/hashtab.h