Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
hashtab.h
Go to the documentation of this file.
1 /*
2  * A hash table (hashtab) maintains associations between
3  * key values and datum values. The type of the key values
4  * and the type of the datum values is arbitrary. The
5  * functions for hash computation and key comparison are
6  * provided by the creator of the table.
7  *
8  * Author : Stephen Smalley, <[email protected]>
9  */
10 #ifndef _SS_HASHTAB_H_
11 #define _SS_HASHTAB_H_
12 
13 #define HASHTAB_MAX_NODES 0xffffffff
14 
15 struct hashtab_node {
16  void *key;
17  void *datum;
18  struct hashtab_node *next;
19 };
20 
21 struct hashtab {
22  struct hashtab_node **htable; /* hash table */
23  u32 size; /* number of slots in hash table */
24  u32 nel; /* number of elements in hash table */
25  u32 (*hash_value)(struct hashtab *h, const void *key);
26  /* hash function */
27  int (*keycmp)(struct hashtab *h, const void *key1, const void *key2);
28  /* key comparison function */
29 };
30 
31 struct hashtab_info {
34 };
35 
36 /*
37  * Creates a new hash table with the specified characteristics.
38  *
39  * Returns NULL if insufficent space is available or
40  * the new hash table otherwise.
41  */
42 struct hashtab *hashtab_create(u32 (*hash_value)(struct hashtab *h, const void *key),
43  int (*keycmp)(struct hashtab *h, const void *key1, const void *key2),
44  u32 size);
45 
46 /*
47  * Inserts the specified (key, datum) pair into the specified hash table.
48  *
49  * Returns -ENOMEM on memory allocation error,
50  * -EEXIST if there is already an entry with the same key,
51  * -EINVAL for general errors or
52  0 otherwise.
53  */
54 int hashtab_insert(struct hashtab *h, void *k, void *d);
55 
56 /*
57  * Searches for the entry with the specified key in the hash table.
58  *
59  * Returns NULL if no entry has the specified key or
60  * the datum of the entry otherwise.
61  */
62 void *hashtab_search(struct hashtab *h, const void *k);
63 
64 /*
65  * Destroys the specified hash table.
66  */
67 void hashtab_destroy(struct hashtab *h);
68 
69 /*
70  * Applies the specified apply function to (key,datum,args)
71  * for each entry in the specified hash table.
72  *
73  * The order in which the function is applied to the entries
74  * is dependent upon the internal structure of the hash table.
75  *
76  * If apply returns a non-zero status, then hashtab_map will cease
77  * iterating through the hash table and will propagate the error
78  * return to its caller.
79  */
80 int hashtab_map(struct hashtab *h,
81  int (*apply)(void *k, void *d, void *args),
82  void *args);
83 
84 /* Fill info with some hash table statistics */
85 void hashtab_stat(struct hashtab *h, struct hashtab_info *info);
86 
87 #endif /* _SS_HASHTAB_H */