1255e72915d4cbddceb435e13d81601755714e9fSE Android 2255e72915d4cbddceb435e13d81601755714e9fSE Android/* Author : Stephen Smalley, <sds@epoch.ncsc.mil> */ 3255e72915d4cbddceb435e13d81601755714e9fSE Android 4255e72915d4cbddceb435e13d81601755714e9fSE Android/* FLASK */ 5255e72915d4cbddceb435e13d81601755714e9fSE Android 6255e72915d4cbddceb435e13d81601755714e9fSE Android/* 7255e72915d4cbddceb435e13d81601755714e9fSE Android * A hash table (hashtab) maintains associations between 8255e72915d4cbddceb435e13d81601755714e9fSE Android * key values and datum values. The type of the key values 9255e72915d4cbddceb435e13d81601755714e9fSE Android * and the type of the datum values is arbitrary. The 10255e72915d4cbddceb435e13d81601755714e9fSE Android * functions for hash computation and key comparison are 11255e72915d4cbddceb435e13d81601755714e9fSE Android * provided by the creator of the table. 12255e72915d4cbddceb435e13d81601755714e9fSE Android */ 13255e72915d4cbddceb435e13d81601755714e9fSE Android 14255e72915d4cbddceb435e13d81601755714e9fSE Android#ifndef _SEPOL_POLICYDB_HASHTAB_H_ 15255e72915d4cbddceb435e13d81601755714e9fSE Android#define _SEPOL_POLICYDB_HASHTAB_H_ 16255e72915d4cbddceb435e13d81601755714e9fSE Android 17255e72915d4cbddceb435e13d81601755714e9fSE Android#include <sepol/errcodes.h> 18255e72915d4cbddceb435e13d81601755714e9fSE Android 19255e72915d4cbddceb435e13d81601755714e9fSE Android#include <stdint.h> 20255e72915d4cbddceb435e13d81601755714e9fSE Android#include <stdio.h> 21255e72915d4cbddceb435e13d81601755714e9fSE Android 22255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef char *hashtab_key_t; /* generic key type */ 23255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef void *hashtab_datum_t; /* generic datum type */ 24255e72915d4cbddceb435e13d81601755714e9fSE Android 25255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef struct hashtab_node *hashtab_ptr_t; 26255e72915d4cbddceb435e13d81601755714e9fSE Android 27255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef struct hashtab_node { 28255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_key_t key; 29255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t datum; 30255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t next; 31255e72915d4cbddceb435e13d81601755714e9fSE Android} hashtab_node_t; 32255e72915d4cbddceb435e13d81601755714e9fSE Android 33255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef struct hashtab_val { 34255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_ptr_t *htable; /* hash table */ 35255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int size; /* number of slots in hash table */ 36255e72915d4cbddceb435e13d81601755714e9fSE Android uint32_t nel; /* number of elements in hash table */ 37255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int (*hash_value) (struct hashtab_val * h, hashtab_key_t key); /* hash function */ 38255e72915d4cbddceb435e13d81601755714e9fSE Android int (*keycmp) (struct hashtab_val * h, hashtab_key_t key1, hashtab_key_t key2); /* key comparison function */ 39255e72915d4cbddceb435e13d81601755714e9fSE Android} hashtab_val_t; 40255e72915d4cbddceb435e13d81601755714e9fSE Android 41255e72915d4cbddceb435e13d81601755714e9fSE Androidtypedef hashtab_val_t *hashtab_t; 42255e72915d4cbddceb435e13d81601755714e9fSE Android 43255e72915d4cbddceb435e13d81601755714e9fSE Android/* 44255e72915d4cbddceb435e13d81601755714e9fSE Android Creates a new hash table with the specified characteristics. 45255e72915d4cbddceb435e13d81601755714e9fSE Android 46255e72915d4cbddceb435e13d81601755714e9fSE Android Returns NULL if insufficent space is available or 47255e72915d4cbddceb435e13d81601755714e9fSE Android the new hash table otherwise. 48255e72915d4cbddceb435e13d81601755714e9fSE Android */ 49255e72915d4cbddceb435e13d81601755714e9fSE Androidextern hashtab_t hashtab_create(unsigned int (*hash_value) (hashtab_t h, 50255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t 51255e72915d4cbddceb435e13d81601755714e9fSE Android key), 52255e72915d4cbddceb435e13d81601755714e9fSE Android int (*keycmp) (hashtab_t h, 53255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t key1, 54255e72915d4cbddceb435e13d81601755714e9fSE Android const hashtab_key_t key2), 55255e72915d4cbddceb435e13d81601755714e9fSE Android unsigned int size); 56255e72915d4cbddceb435e13d81601755714e9fSE Android/* 57255e72915d4cbddceb435e13d81601755714e9fSE Android Inserts the specified (key, datum) pair into the specified hash table. 58255e72915d4cbddceb435e13d81601755714e9fSE Android 59255e72915d4cbddceb435e13d81601755714e9fSE Android Returns SEPOL_ENOMEM if insufficient space is available or 60255e72915d4cbddceb435e13d81601755714e9fSE Android SEPOL_EEXIST if there is already an entry with the same key or 61255e72915d4cbddceb435e13d81601755714e9fSE Android SEPOL_OK otherwise. 62255e72915d4cbddceb435e13d81601755714e9fSE Android */ 63255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int hashtab_insert(hashtab_t h, hashtab_key_t k, hashtab_datum_t d); 64255e72915d4cbddceb435e13d81601755714e9fSE Android 65255e72915d4cbddceb435e13d81601755714e9fSE Android/* 66255e72915d4cbddceb435e13d81601755714e9fSE Android Removes the entry with the specified key from the hash table. 67255e72915d4cbddceb435e13d81601755714e9fSE Android Applies the specified destroy function to (key,datum,args) for 68255e72915d4cbddceb435e13d81601755714e9fSE Android the entry. 69255e72915d4cbddceb435e13d81601755714e9fSE Android 70255e72915d4cbddceb435e13d81601755714e9fSE Android Returns SEPOL_ENOENT if no entry has the specified key or 71255e72915d4cbddceb435e13d81601755714e9fSE Android SEPOL_OK otherwise. 72255e72915d4cbddceb435e13d81601755714e9fSE Android */ 73255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int hashtab_remove(hashtab_t h, hashtab_key_t k, 74255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 75255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 76255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), void *args); 77255e72915d4cbddceb435e13d81601755714e9fSE Android 78255e72915d4cbddceb435e13d81601755714e9fSE Android/* 79255e72915d4cbddceb435e13d81601755714e9fSE Android Insert or replace the specified (key, datum) pair in the specified 80255e72915d4cbddceb435e13d81601755714e9fSE Android hash table. If an entry for the specified key already exists, 81255e72915d4cbddceb435e13d81601755714e9fSE Android then the specified destroy function is applied to (key,datum,args) 82255e72915d4cbddceb435e13d81601755714e9fSE Android for the entry prior to replacing the entry's contents. 83255e72915d4cbddceb435e13d81601755714e9fSE Android 84255e72915d4cbddceb435e13d81601755714e9fSE Android Returns SEPOL_ENOMEM if insufficient space is available or 85255e72915d4cbddceb435e13d81601755714e9fSE Android SEPOL_OK otherwise. 86255e72915d4cbddceb435e13d81601755714e9fSE Android */ 87255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int hashtab_replace(hashtab_t h, hashtab_key_t k, hashtab_datum_t d, 88255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 89255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 90255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), void *args); 91255e72915d4cbddceb435e13d81601755714e9fSE Android 92255e72915d4cbddceb435e13d81601755714e9fSE Android/* 93255e72915d4cbddceb435e13d81601755714e9fSE Android Searches for the entry with the specified key in the hash table. 94255e72915d4cbddceb435e13d81601755714e9fSE Android 95255e72915d4cbddceb435e13d81601755714e9fSE Android Returns NULL if no entry has the specified key or 96255e72915d4cbddceb435e13d81601755714e9fSE Android the datum of the entry otherwise. 97255e72915d4cbddceb435e13d81601755714e9fSE Android */ 98255e72915d4cbddceb435e13d81601755714e9fSE Androidextern hashtab_datum_t hashtab_search(hashtab_t h, const hashtab_key_t k); 99255e72915d4cbddceb435e13d81601755714e9fSE Android 100255e72915d4cbddceb435e13d81601755714e9fSE Android/* 101255e72915d4cbddceb435e13d81601755714e9fSE Android Destroys the specified hash table. 102255e72915d4cbddceb435e13d81601755714e9fSE Android */ 103255e72915d4cbddceb435e13d81601755714e9fSE Androidextern void hashtab_destroy(hashtab_t h); 104255e72915d4cbddceb435e13d81601755714e9fSE Android 105255e72915d4cbddceb435e13d81601755714e9fSE Android/* 106255e72915d4cbddceb435e13d81601755714e9fSE Android Applies the specified apply function to (key,datum,args) 107255e72915d4cbddceb435e13d81601755714e9fSE Android for each entry in the specified hash table. 108255e72915d4cbddceb435e13d81601755714e9fSE Android 109255e72915d4cbddceb435e13d81601755714e9fSE Android The order in which the function is applied to the entries 110255e72915d4cbddceb435e13d81601755714e9fSE Android is dependent upon the internal structure of the hash table. 111255e72915d4cbddceb435e13d81601755714e9fSE Android 112255e72915d4cbddceb435e13d81601755714e9fSE Android If apply returns a non-zero status, then hashtab_map will cease 113255e72915d4cbddceb435e13d81601755714e9fSE Android iterating through the hash table and will propagate the error 114255e72915d4cbddceb435e13d81601755714e9fSE Android return to its caller. 115255e72915d4cbddceb435e13d81601755714e9fSE Android */ 116255e72915d4cbddceb435e13d81601755714e9fSE Androidextern int hashtab_map(hashtab_t h, 117255e72915d4cbddceb435e13d81601755714e9fSE Android int (*apply) (hashtab_key_t k, 118255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 119255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), void *args); 120255e72915d4cbddceb435e13d81601755714e9fSE Android 121255e72915d4cbddceb435e13d81601755714e9fSE Android/* 122255e72915d4cbddceb435e13d81601755714e9fSE Android Same as hashtab_map, except that if apply returns a non-zero status, 123255e72915d4cbddceb435e13d81601755714e9fSE Android then the (key,datum) pair will be removed from the hashtab and the 124255e72915d4cbddceb435e13d81601755714e9fSE Android destroy function will be applied to (key,datum,args). 125255e72915d4cbddceb435e13d81601755714e9fSE Android */ 126255e72915d4cbddceb435e13d81601755714e9fSE Androidextern void hashtab_map_remove_on_error(hashtab_t h, 127255e72915d4cbddceb435e13d81601755714e9fSE Android int (*apply) (hashtab_key_t k, 128255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 129255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), 130255e72915d4cbddceb435e13d81601755714e9fSE Android void (*destroy) (hashtab_key_t k, 131255e72915d4cbddceb435e13d81601755714e9fSE Android hashtab_datum_t d, 132255e72915d4cbddceb435e13d81601755714e9fSE Android void *args), 133255e72915d4cbddceb435e13d81601755714e9fSE Android void *args); 134255e72915d4cbddceb435e13d81601755714e9fSE Android 135255e72915d4cbddceb435e13d81601755714e9fSE Androidextern void hashtab_hash_eval(hashtab_t h, char *tag); 136255e72915d4cbddceb435e13d81601755714e9fSE Android 137255e72915d4cbddceb435e13d81601755714e9fSE Android#endif 138