To use hashtab in libselinux, migrate the existing hashtab template
from policycoreutils/newrole to libselinux.
Signed-off-by: wanghuizhao <wanghuizhao1@xxxxxxxxxx>
---
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..092b96a9
--- /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
+
+#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
