diff mbox series

[v2,1/3] libselinux: migrating hashtab from policycoreutils

Message ID 20230217084458.40597-2-wanghuizhao1@huawei.com (mailing list archive)
State Superseded
Delegated to: Petr Lautrbach
Headers show
Series Improve efficiency of detecting duplicate in libselinux | expand

Commit Message

Huizhao Wang Feb. 17, 2023, 8:44 a.m. UTC
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 mbox series

Patch

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