]>
git.proxmox.com Git - ovs.git/blob - lib/hmap.h
2 * Copyright (c) 2008, 2009 Nicira Networks.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
24 /* A hash map node, to be embedded inside the data structure being mapped. */
26 size_t hash
; /* Hash value. */
27 struct hmap_node
*next
; /* Next in linked list. */
30 /* Returns the hash value embedded in 'node'. */
31 static inline size_t hmap_node_hash(const struct hmap_node
*node
)
38 struct hmap_node
**buckets
;
39 struct hmap_node
*one
;
44 /* Initializer for an empty hash map. */
45 #define HMAP_INITIALIZER(HMAP) { &(HMAP)->one, NULL, 0, 0 }
48 void hmap_init(struct hmap
*);
49 void hmap_destroy(struct hmap
*);
50 void hmap_swap(struct hmap
*a
, struct hmap
*b
);
51 static inline size_t hmap_count(const struct hmap
*);
52 static inline bool hmap_is_empty(const struct hmap
*);
54 /* Adjusting capacity. */
55 void hmap_expand(struct hmap
*);
56 void hmap_shrink(struct hmap
*);
57 void hmap_reserve(struct hmap
*, size_t capacity
);
59 /* Insertion and deletion. */
60 static inline void hmap_insert_fast(struct hmap
*,
61 struct hmap_node
*, size_t hash
);
62 static inline void hmap_insert(struct hmap
*, struct hmap_node
*, size_t hash
);
63 static inline void hmap_remove(struct hmap
*, struct hmap_node
*);
64 static inline void hmap_moved(struct hmap
*,
65 struct hmap_node
*, struct hmap_node
*);
66 static inline void hmap_replace(struct hmap
*, const struct hmap_node
*old
,
67 struct hmap_node
*new);
70 #define HMAP_FOR_EACH_WITH_HASH(NODE, STRUCT, MEMBER, HASH, HMAP) \
71 for ((NODE) = CONTAINER_OF(hmap_first_with_hash(HMAP, HASH), \
73 &(NODE)->MEMBER != NULL; \
74 (NODE) = CONTAINER_OF(hmap_next_with_hash(&(NODE)->MEMBER), \
77 static inline struct hmap_node
*hmap_first_with_hash(const struct hmap
*,
79 static inline struct hmap_node
*hmap_next_with_hash(const struct hmap_node
*);
83 * The _SAFE version is needed when NODE may be freed. It is not needed when
84 * NODE may be removed from the hash map but its members remain accessible and
86 #define HMAP_FOR_EACH(NODE, STRUCT, MEMBER, HMAP) \
87 for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER); \
88 &(NODE)->MEMBER != NULL; \
89 (NODE) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \
92 #define HMAP_FOR_EACH_SAFE(NODE, NEXT, STRUCT, MEMBER, HMAP) \
93 for ((NODE) = CONTAINER_OF(hmap_first(HMAP), STRUCT, MEMBER); \
94 (&(NODE)->MEMBER != NULL \
95 ? (NEXT) = CONTAINER_OF(hmap_next(HMAP, &(NODE)->MEMBER), \
100 static inline struct hmap_node
*hmap_first(const struct hmap
*);
101 static inline struct hmap_node
*hmap_next(const struct hmap
*,
102 const struct hmap_node
*);
104 /* Returns the number of nodes currently in 'hmap'. */
106 hmap_count(const struct hmap
*hmap
)
111 /* Returns true if 'hmap' currently contains no nodes,
112 * false otherwise. */
114 hmap_is_empty(const struct hmap
*hmap
)
119 /* Inserts 'node', with the given 'hash', into 'hmap'. 'hmap' is never
120 * expanded automatically. */
122 hmap_insert_fast(struct hmap
*hmap
, struct hmap_node
*node
, size_t hash
)
124 struct hmap_node
**bucket
= &hmap
->buckets
[hash
& hmap
->mask
];
126 node
->next
= *bucket
;
131 /* Inserts 'node', with the given 'hash', into 'hmap', and expands 'hmap' if
132 * necessary to optimize search performance. */
134 hmap_insert(struct hmap
*hmap
, struct hmap_node
*node
, size_t hash
)
136 hmap_insert_fast(hmap
, node
, hash
);
137 if (hmap
->n
/ 2 > hmap
->mask
) {
142 /* Removes 'node' from 'hmap'. Does not shrink the hash table; call
143 * hmap_shrink() directly if desired. */
145 hmap_remove(struct hmap
*hmap
, struct hmap_node
*node
)
147 struct hmap_node
**bucket
= &hmap
->buckets
[node
->hash
& hmap
->mask
];
148 while (*bucket
!= node
) {
149 bucket
= &(*bucket
)->next
;
151 *bucket
= node
->next
;
155 /* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
156 * to 'node' (e.g. due to realloc()). */
158 hmap_moved(struct hmap
*hmap
,
159 struct hmap_node
*old_node
, struct hmap_node
*node
)
161 struct hmap_node
**bucket
= &hmap
->buckets
[node
->hash
& hmap
->mask
];
162 while (*bucket
!= old_node
) {
163 bucket
= &(*bucket
)->next
;
168 /* Puts 'new' in the position in 'hmap' currently occupied by 'old'. The 'new'
169 * node must hash to the same value as 'old'. The client is responsible for
170 * ensuring that the replacement does not violate any client-imposed
171 * invariants (e.g. uniqueness of keys within a map).
173 * Afterward, 'old' is not part of 'hmap', and the client is responsible for
174 * freeing it (if this is desirable). */
176 hmap_replace(struct hmap
*hmap
,
177 const struct hmap_node
*old
, struct hmap_node
*new)
179 struct hmap_node
**bucket
= &hmap
->buckets
[old
->hash
& hmap
->mask
];
180 while (*bucket
!= old
) {
181 bucket
= &(*bucket
)->next
;
184 new->hash
= old
->hash
;
187 static inline struct hmap_node
*
188 hmap_next_with_hash__(const struct hmap_node
*node
, size_t hash
)
190 while (node
!= NULL
&& node
->hash
!= hash
) {
193 return (struct hmap_node
*) node
;
196 /* Returns the first node in 'hmap' with the given 'hash', or a null pointer if
197 * no nodes have that hash value. */
198 static inline struct hmap_node
*
199 hmap_first_with_hash(const struct hmap
*hmap
, size_t hash
)
201 return hmap_next_with_hash__(hmap
->buckets
[hash
& hmap
->mask
], hash
);
204 /* Returns the next node in the same hash map as 'node' with the same hash
205 * value, or a null pointer if no more nodes have that hash value.
207 * If the hash map has been reallocated since 'node' was visited, some nodes
208 * may be skipped; if new nodes with the same hash value have been added, they
209 * will be skipped. (Removing 'node' from the hash map does not prevent
210 * calling this function, since node->next is preserved, although freeing
211 * 'node' of course does.) */
212 static inline struct hmap_node
*
213 hmap_next_with_hash(const struct hmap_node
*node
)
215 return hmap_next_with_hash__(node
->next
, node
->hash
);
218 static inline struct hmap_node
*
219 hmap_next__(const struct hmap
*hmap
, size_t start
)
222 for (i
= start
; i
<= hmap
->mask
; i
++) {
223 struct hmap_node
*node
= hmap
->buckets
[i
];
231 /* Returns the first node in 'hmap', in arbitrary order, or a null pointer if
232 * 'hmap' is empty. */
233 static inline struct hmap_node
*
234 hmap_first(const struct hmap
*hmap
)
236 return hmap_next__(hmap
, 0);
239 /* Returns the next node in 'hmap' following 'node', in arbitrary order, or a
240 * null pointer if 'node' is the last node in 'hmap'.
242 * If the hash map has been reallocated since 'node' was visited, some nodes
243 * may be skipped or visited twice. (Removing 'node' from the hash map does
244 * not prevent calling this function, since node->next is preserved, although
245 * freeing 'node' of course does.) */
246 static inline struct hmap_node
*
247 hmap_next(const struct hmap
*hmap
, const struct hmap_node
*node
)
251 : hmap_next__(hmap
, (node
->hash
& hmap
->mask
) + 1));