security/selinux/ss/hashtab.h

Source file repositories/reference/linux-study-clean/security/selinux/ss/hashtab.h

File Facts

System
Linux kernel
Corpus path
security/selinux/ss/hashtab.h
Extension
.h
Size
3849 bytes
Lines
155
Domain
Core OS
Bucket
Security And Isolation
Inferred role
Core OS: implementation source
Status
source implementation candidate

Why This File Exists

Core operating-system implementation surface: boot, tasks, memory, VFS, syscall-facing interfaces, synchronization, credentials, and isolation.

Dependency Surface

Detected Declarations

Annotated Snippet

struct hashtab_key_params {
	u32 (*hash)(const void *key); /* hash func */
	int (*cmp)(const void *key1, const void *key2); /* comparison func */
};

struct hashtab_node {
	void *key;
	void *datum;
	struct hashtab_node *next;
};

struct hashtab {
	struct hashtab_node **htable; /* hash table */
	u32 size; /* number of slots in hash table */
	u32 nel; /* number of elements in hash table */
};

struct hashtab_info {
	u32 slots_used;
	u32 max_chain_len;
	u64 chain2_len_sum;
};

/*
 * Initializes a new hash table with the specified characteristics.
 *
 * Returns -ENOMEM if insufficient space is available or 0 otherwise.
 */
int hashtab_init(struct hashtab *h, u32 nel_hint);

int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst, void *key,
		     void *datum);

/*
 * Inserts the specified (key, datum) pair into the specified hash table.
 *
 * Returns -ENOMEM on memory allocation error,
 * -EEXIST if there is already an entry with the same key,
 * -EINVAL for general errors or
  0 otherwise.
 */
static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
				 struct hashtab_key_params key_params)
{
	u32 hvalue;
	struct hashtab_node *prev, *cur;

	cond_resched();

	if (!h->size || h->nel == HASHTAB_MAX_NODES)
		return -EINVAL;

	hvalue = key_params.hash(key) & (h->size - 1);
	prev = NULL;
	cur = h->htable[hvalue];
	while (cur) {
		int cmp = key_params.cmp(key, cur->key);

		if (cmp == 0)
			return -EEXIST;
		if (cmp < 0)
			break;
		prev = cur;
		cur = cur->next;
	}

	return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue], key,
				datum);
}

/*
 * 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.
 */
static inline void *hashtab_search(const struct hashtab *h, const void *key,
				   struct hashtab_key_params key_params)
{
	u32 hvalue;
	const struct hashtab_node *cur;

	if (!h->size)
		return NULL;

	hvalue = key_params.hash(key) & (h->size - 1);
	cur = h->htable[hvalue];
	while (cur) {
		int cmp = key_params.cmp(key, cur->key);

Annotation

Implementation Notes