On Wed, May 24, 2023 at 9:51 AM James Carter <jwcart2@xxxxxxxxx> wrote:
>
> On Wed, Mar 8, 2023 at 4:53 AM wanghuizhao <wanghuizhao1@xxxxxxxxxx> wrote:
> >
> > To use hashtab in libselinux, migrate the existing hashtab template
> > from policycoreutils/newrole to libselinux.
> >
> > Signed-off-by: wanghuizhao <wanghuizhao1@xxxxxxxxxx>
>
> For these three patches:
> Acked-by: James Carter <jwcart2@xxxxxxxxx>
>
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@xxxxxxxxxxxxx> */
> > +
> > +/* 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@xxxxxxxxxxxxx> */
> > +
> > +/* 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
> >
