Re: [PATCH v3 1/3] libselinux: migrating hashtab from policycoreutils

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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>

> ---
>  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
>




[Index of Archives]     [Selinux Refpolicy]     [Linux SGX]     [Fedora Users]     [Fedora Desktop]     [Yosemite Photos]     [Yosemite Camping]     [Yosemite Campsites]     [KDE Users]     [Gnome Users]

  Powered by Linux