]>
Commit | Line | Data |
---|---|---|
2e11264a EC |
1 | /* |
2 | * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> | |
3 | * | |
4 | * License: GNU GPL, version 2 or later. | |
5 | * See the COPYING file in the top-level directory. | |
6 | */ | |
7 | #ifndef QEMU_QHT_H | |
8 | #define QEMU_QHT_H | |
9 | ||
2e11264a EC |
10 | #include "qemu/seqlock.h" |
11 | #include "qemu/thread.h" | |
12 | #include "qemu/qdist.h" | |
13 | ||
14 | struct qht { | |
15 | struct qht_map *map; | |
16 | QemuMutex lock; /* serializes setters of ht->map */ | |
17 | unsigned int mode; | |
18 | }; | |
19 | ||
20 | /** | |
21 | * struct qht_stats - Statistics of a QHT | |
22 | * @head_buckets: number of head buckets | |
23 | * @used_head_buckets: number of non-empty head buckets | |
24 | * @entries: total number of entries | |
25 | * @chain: frequency distribution representing the number of buckets in each | |
26 | * chain, excluding empty chains. | |
27 | * @occupancy: frequency distribution representing chain occupancy rate. | |
28 | * Valid range: from 0.0 (empty) to 1.0 (full occupancy). | |
29 | * | |
30 | * An entry is a pointer-hash pair. | |
31 | * Each bucket can host several entries. | |
32 | * Chains are chains of buckets, whose first link is always a head bucket. | |
33 | */ | |
34 | struct qht_stats { | |
35 | size_t head_buckets; | |
36 | size_t used_head_buckets; | |
37 | size_t entries; | |
38 | struct qdist chain; | |
39 | struct qdist occupancy; | |
40 | }; | |
41 | ||
42 | typedef bool (*qht_lookup_func_t)(const void *obj, const void *userp); | |
43 | typedef void (*qht_iter_func_t)(struct qht *ht, void *p, uint32_t h, void *up); | |
44 | ||
45 | #define QHT_MODE_AUTO_RESIZE 0x1 /* auto-resize when heavily loaded */ | |
46 | ||
47 | /** | |
48 | * qht_init - Initialize a QHT | |
49 | * @ht: QHT to be initialized | |
50 | * @n_elems: number of entries the hash table should be optimized for. | |
51 | * @mode: bitmask with OR'ed QHT_MODE_* | |
52 | */ | |
53 | void qht_init(struct qht *ht, size_t n_elems, unsigned int mode); | |
54 | ||
55 | /** | |
56 | * qht_destroy - destroy a previously initialized QHT | |
57 | * @ht: QHT to be destroyed | |
58 | * | |
59 | * Call only when there are no readers/writers left. | |
60 | */ | |
61 | void qht_destroy(struct qht *ht); | |
62 | ||
63 | /** | |
64 | * qht_insert - Insert a pointer into the hash table | |
65 | * @ht: QHT to insert to | |
66 | * @p: pointer to be inserted | |
67 | * @hash: hash corresponding to @p | |
68 | * | |
69 | * Attempting to insert a NULL @p is a bug. | |
70 | * Inserting the same pointer @p with different @hash values is a bug. | |
71 | * | |
72 | * Returns true on sucess. | |
73 | * Returns false if the @p-@hash pair already exists in the hash table. | |
74 | */ | |
75 | bool qht_insert(struct qht *ht, void *p, uint32_t hash); | |
76 | ||
77 | /** | |
78 | * qht_lookup - Look up a pointer in a QHT | |
79 | * @ht: QHT to be looked up | |
80 | * @func: function to compare existing pointers against @userp | |
81 | * @userp: pointer to pass to @func | |
82 | * @hash: hash of the pointer to be looked up | |
83 | * | |
84 | * Needs to be called under an RCU read-critical section. | |
85 | * | |
86 | * The user-provided @func compares pointers in QHT against @userp. | |
87 | * If the function returns true, a match has been found. | |
88 | * | |
89 | * Returns the corresponding pointer when a match is found. | |
90 | * Returns NULL otherwise. | |
91 | */ | |
92 | void *qht_lookup(struct qht *ht, qht_lookup_func_t func, const void *userp, | |
93 | uint32_t hash); | |
94 | ||
95 | /** | |
96 | * qht_remove - remove a pointer from the hash table | |
97 | * @ht: QHT to remove from | |
98 | * @p: pointer to be removed | |
99 | * @hash: hash corresponding to @p | |
100 | * | |
101 | * Attempting to remove a NULL @p is a bug. | |
102 | * | |
103 | * Just-removed @p pointers cannot be immediately freed; they need to remain | |
104 | * valid until the end of the RCU grace period in which qht_remove() is called. | |
105 | * This guarantees that concurrent lookups will always compare against valid | |
106 | * data. | |
107 | * | |
108 | * Returns true on success. | |
109 | * Returns false if the @p-@hash pair was not found. | |
110 | */ | |
111 | bool qht_remove(struct qht *ht, const void *p, uint32_t hash); | |
112 | ||
113 | /** | |
114 | * qht_reset - reset a QHT | |
115 | * @ht: QHT to be reset | |
116 | * | |
117 | * All entries in the hash table are reset. No resizing is performed. | |
118 | * | |
119 | * If concurrent readers may exist, the objects pointed to by the hash table | |
120 | * must remain valid for the existing RCU grace period -- see qht_remove(). | |
121 | * See also: qht_reset_size() | |
122 | */ | |
123 | void qht_reset(struct qht *ht); | |
124 | ||
125 | /** | |
126 | * qht_reset_size - reset and resize a QHT | |
127 | * @ht: QHT to be reset and resized | |
128 | * @n_elems: number of entries the resized hash table should be optimized for. | |
129 | * | |
130 | * Returns true if the resize was necessary and therefore performed. | |
131 | * Returns false otherwise. | |
132 | * | |
133 | * If concurrent readers may exist, the objects pointed to by the hash table | |
134 | * must remain valid for the existing RCU grace period -- see qht_remove(). | |
135 | * See also: qht_reset(), qht_resize(). | |
136 | */ | |
137 | bool qht_reset_size(struct qht *ht, size_t n_elems); | |
138 | ||
139 | /** | |
140 | * qht_resize - resize a QHT | |
141 | * @ht: QHT to be resized | |
142 | * @n_elems: number of entries the resized hash table should be optimized for | |
143 | * | |
144 | * Returns true on success. | |
145 | * Returns false if the resize was not necessary and therefore not performed. | |
146 | * See also: qht_reset_size(). | |
147 | */ | |
148 | bool qht_resize(struct qht *ht, size_t n_elems); | |
149 | ||
150 | /** | |
151 | * qht_iter - Iterate over a QHT | |
152 | * @ht: QHT to be iterated over | |
153 | * @func: function to be called for each entry in QHT | |
154 | * @userp: additional pointer to be passed to @func | |
155 | * | |
156 | * Each time it is called, user-provided @func is passed a pointer-hash pair, | |
157 | * plus @userp. | |
158 | */ | |
159 | void qht_iter(struct qht *ht, qht_iter_func_t func, void *userp); | |
160 | ||
161 | /** | |
162 | * qht_statistics_init - Gather statistics from a QHT | |
163 | * @ht: QHT to gather statistics from | |
164 | * @stats: pointer to a struct qht_stats to be filled in | |
165 | * | |
166 | * Does NOT need to be called under an RCU read-critical section, | |
167 | * since it does not dereference any pointers stored in the hash table. | |
168 | * | |
169 | * When done with @stats, pass the struct to qht_statistics_destroy(). | |
170 | * Failing to do this will leak memory. | |
171 | */ | |
172 | void qht_statistics_init(struct qht *ht, struct qht_stats *stats); | |
173 | ||
174 | /** | |
175 | * qht_statistics_destroy - Destroy a struct qht_stats | |
176 | * @stats: stuct qht_stats to be destroyed | |
177 | * | |
178 | * See also: qht_statistics_init(). | |
179 | */ | |
180 | void qht_statistics_destroy(struct qht_stats *stats); | |
181 | ||
182 | #endif /* QEMU_QHT_H */ |