cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

hashtab.h (3659B)

      1/* SPDX-License-Identifier: GPL-2.0 */
      2/*
      3 * A hash table (hashtab) maintains associations between
      4 * key values and datum values.  The type of the key values
      5 * and the type of the datum values is arbitrary.  The
      6 * functions for hash computation and key comparison are
      7 * provided by the creator of the table.
      8 *
      9 * Author : Stephen Smalley, <sds@tycho.nsa.gov>
     10 */
     11#ifndef _SS_HASHTAB_H_
     12#define _SS_HASHTAB_H_
     13
     14#include <linux/types.h>
     15#include <linux/errno.h>
     16#include <linux/sched.h>
     17
     18#define HASHTAB_MAX_NODES	U32_MAX
     19
     20struct hashtab_key_params {
     21	u32 (*hash)(const void *key);	/* hash function */
     22	int (*cmp)(const void *key1, const void *key2);
     23					/* key comparison function */
     24};
     25
     26struct hashtab_node {
     27	void *key;
     28	void *datum;
     29	struct hashtab_node *next;
     30};
     31
     32struct hashtab {
     33	struct hashtab_node **htable;	/* hash table */
     34	u32 size;			/* number of slots in hash table */
     35	u32 nel;			/* number of elements in hash table */
     36};
     37
     38struct hashtab_info {
     39	u32 slots_used;
     40	u32 max_chain_len;
     41};
     42
     43/*
     44 * Initializes a new hash table with the specified characteristics.
     45 *
     46 * Returns -ENOMEM if insufficient space is available or 0 otherwise.
     47 */
     48int hashtab_init(struct hashtab *h, u32 nel_hint);
     49
     50int __hashtab_insert(struct hashtab *h, struct hashtab_node **dst,
     51		     void *key, void *datum);
     52
     53/*
     54 * Inserts the specified (key, datum) pair into the specified hash table.
     55 *
     56 * Returns -ENOMEM on memory allocation error,
     57 * -EEXIST if there is already an entry with the same key,
     58 * -EINVAL for general errors or
     59  0 otherwise.
     60 */
     61static inline int hashtab_insert(struct hashtab *h, void *key, void *datum,
     62				 struct hashtab_key_params key_params)
     63{
     64	u32 hvalue;
     65	struct hashtab_node *prev, *cur;
     66
     67	cond_resched();
     68
     69	if (!h->size || h->nel == HASHTAB_MAX_NODES)
     70		return -EINVAL;
     71
     72	hvalue = key_params.hash(key) & (h->size - 1);
     73	prev = NULL;
     74	cur = h->htable[hvalue];
     75	while (cur) {
     76		int cmp = key_params.cmp(key, cur->key);
     77
     78		if (cmp == 0)
     79			return -EEXIST;
     80		if (cmp < 0)
     81			break;
     82		prev = cur;
     83		cur = cur->next;
     84	}
     85
     86	return __hashtab_insert(h, prev ? &prev->next : &h->htable[hvalue],
     87				key, datum);
     88}
     89
     90/*
     91 * Searches for the entry with the specified key in the hash table.
     92 *
     93 * Returns NULL if no entry has the specified key or
     94 * the datum of the entry otherwise.
     95 */
     96static inline void *hashtab_search(struct hashtab *h, const void *key,
     97				   struct hashtab_key_params key_params)
     98{
     99	u32 hvalue;
    100	struct hashtab_node *cur;
    101
    102	if (!h->size)
    103		return NULL;
    104
    105	hvalue = key_params.hash(key) & (h->size - 1);
    106	cur = h->htable[hvalue];
    107	while (cur) {
    108		int cmp = key_params.cmp(key, cur->key);
    109
    110		if (cmp == 0)
    111			return cur->datum;
    112		if (cmp < 0)
    113			break;
    114		cur = cur->next;
    115	}
    116	return NULL;
    117}
    118
    119/*
    120 * Destroys the specified hash table.
    121 */
    122void hashtab_destroy(struct hashtab *h);
    123
    124/*
    125 * Applies the specified apply function to (key,datum,args)
    126 * for each entry in the specified hash table.
    127 *
    128 * The order in which the function is applied to the entries
    129 * is dependent upon the internal structure of the hash table.
    130 *
    131 * If apply returns a non-zero status, then hashtab_map will cease
    132 * iterating through the hash table and will propagate the error
    133 * return to its caller.
    134 */
    135int hashtab_map(struct hashtab *h,
    136		int (*apply)(void *k, void *d, void *args),
    137		void *args);
    138
    139int hashtab_duplicate(struct hashtab *new, struct hashtab *orig,
    140		int (*copy)(struct hashtab_node *new,
    141			struct hashtab_node *orig, void *args),
    142		int (*destroy)(void *k, void *d, void *args),
    143		void *args);
    144
    145/* Fill info with some hash table statistics */
    146void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
    147
    148#endif	/* _SS_HASHTAB_H */