| Message ID | 20230209114253.120485-2-wanghuizhao1@huawei.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | Petr Lautrbach |
| Headers | show |
| Series | Improve efficiency of detecting duplicate in libselinux | expand |
On Thu, 9 Feb 2023 at 12:54, 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> > --- > 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..092b96a9 > --- /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 libselinux/src/hashtab.h:8: trailing whitespace. + * 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_ _SELINUX_HASHTAB_H ? (or `#pragma once`, seems to be widely supported according to https://en.wikipedia.org/wiki/Pragma_once) > + > +#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 2023/2/10 21:58, Christian Göttsche wrote: > On Thu, 9 Feb 2023 at 12:54, 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> >> --- >> 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..092b96a9 >> --- /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 > > libselinux/src/hashtab.h:8: trailing whitespace. > + * 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_ > _SELINUX_HASHTAB_H ? > (or `#pragma once`, seems to be widely supported according to > https://en.wikipedia.org/wiki/Pragma_once) > >> + >> +#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 Thanks for your review, _NEWROLE_HASHTAB_H_ and trailing whitespace are my oversights. I'll fix it in the next patch version.
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..092b96a9 --- /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