]>
Commit | Line | Data |
---|---|---|
822b7f52 | 1 | /* |
fdbdb595 | 2 | * Copyright (c) 2013, 2016 Nicira, Inc. |
822b7f52 BP |
3 | * |
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: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
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. | |
15 | */ | |
16 | ||
17 | #ifndef HINDEX_H | |
18 | #define HINDEX_H 1 | |
19 | ||
20 | /* Hashed multimap. | |
21 | * | |
22 | * hindex is a hash table data structure that gracefully handles duplicates. | |
23 | * With a high-quality hash function, insertion, deletion, and search are O(1) | |
24 | * expected time, regardless of the number of duplicates for a given key. */ | |
25 | ||
26 | #include <stdbool.h> | |
27 | #include <stdlib.h> | |
28 | #include "util.h" | |
29 | ||
30 | /* A hash index node, to embed inside the data structure being indexed. | |
31 | * | |
32 | * Nodes are linked together like this (the boxes are labeled with hash | |
33 | * values): | |
34 | * | |
35 | * +--------+ d +--------+ d +--------+ d | |
36 | * bucket---> | 6 |---->| 20 |---->| 15 |---->null | |
37 | * +-|------+ +-|------+ +-|------+ | |
38 | * | ^ | | ^ | |
39 | * s| |d |s s| |d | |
40 | * V | V V | | |
41 | * +------|-+ null +------|-+ | |
42 | * | 6 | | 15 | | |
43 | * +-|------+ +-|------+ | |
44 | * | ^ | | |
45 | * s| |d s| | |
46 | * V | V | |
47 | * +------|-+ null | |
48 | * | 6 | | |
49 | * +-|------+ | |
50 | * | | |
51 | * s| | |
52 | * V | |
53 | * null | |
54 | * | |
55 | * The basic usage is: | |
56 | * | |
57 | * - To visit the unique hash values in the hindex, follow the 'd' | |
58 | * ("different") pointers starting from each bucket. The nodes visited | |
59 | * this way are called "head" nodes, because they are at the head of the | |
60 | * vertical chains. | |
61 | * | |
62 | * - To visit the nodes with hash value H, follow the 'd' pointers in the | |
63 | * appropriate bucket until you find one with hash H, then follow the 's' | |
64 | * ("same") pointers until you hit a null pointer. The non-head nodes | |
65 | * visited this way are called "body" nodes. | |
66 | * | |
67 | * - The 'd' pointers in body nodes point back to the previous body node | |
68 | * or, for the first body node, to the head node. (This makes it | |
69 | * possible to remove a body node without traversing all the way downward | |
70 | * from the head). | |
71 | */ | |
72 | struct hindex_node { | |
73 | /* Hash value. */ | |
74 | size_t hash; | |
75 | ||
76 | /* In a head node, the next head node (with a hash different from this | |
77 | * node), or NULL if this is the last node in this bucket. | |
78 | * | |
79 | * In a body node, the previous head or body node (with the same hash as | |
80 | * this node). Never null. */ | |
81 | struct hindex_node *d; | |
82 | ||
83 | /* In a head or a body node, the next body node with the same hash as this | |
84 | * node. NULL if this is the last node with this hash. */ | |
85 | struct hindex_node *s; | |
86 | }; | |
87 | ||
88 | /* A hash index. */ | |
89 | struct hindex { | |
90 | struct hindex_node **buckets; /* Must point to 'one' iff 'mask' == 0. */ | |
91 | struct hindex_node *one; | |
92 | size_t mask; /* 0 or more lowest-order bits set, others cleared. */ | |
93 | size_t n_unique; /* Number of unique hashes (the number of head nodes). */ | |
94 | }; | |
95 | ||
96 | /* Initializer for an empty hash index. */ | |
97 | #define HINDEX_INITIALIZER(HINDEX) \ | |
98 | { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 } | |
99 | ||
100 | /* Initialization. */ | |
101 | void hindex_init(struct hindex *); | |
102 | void hindex_destroy(struct hindex *); | |
103 | void hindex_clear(struct hindex *); | |
104 | void hindex_swap(struct hindex *a, struct hindex *b); | |
105 | void hindex_moved(struct hindex *hindex); | |
106 | static inline bool hindex_is_empty(const struct hindex *); | |
107 | ||
108 | /* Adjusting capacity. */ | |
109 | void hindex_expand(struct hindex *); | |
110 | void hindex_shrink(struct hindex *); | |
111 | void hindex_reserve(struct hindex *, size_t capacity); | |
112 | ||
113 | /* Insertion and deletion. */ | |
114 | void hindex_insert_fast(struct hindex *, struct hindex_node *, size_t hash); | |
115 | void hindex_insert(struct hindex *, struct hindex_node *, size_t hash); | |
116 | void hindex_remove(struct hindex *, struct hindex_node *); | |
117 | ||
118 | /* Search. | |
119 | * | |
120 | * HINDEX_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HINDEX that | |
121 | * have hash value equal to HASH. MEMBER must be the name of the 'struct | |
122 | * hindex_node' member within NODE. | |
123 | * | |
124 | * The loop should not change NODE to point to a different node or insert or | |
125 | * delete nodes in HINDEX (unless it "break"s out of the loop to terminate | |
126 | * iteration). | |
127 | * | |
128 | * Evaluates HASH only once. | |
129 | */ | |
130 | #define HINDEX_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, HINDEX) \ | |
f17e8ad6 | 131 | for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \ |
55d26906 | 132 | NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \ |
822b7f52 BP |
133 | ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER)) |
134 | ||
fdbdb595 RM |
135 | /* Safe when NODE may be freed (not needed when NODE may be removed from the |
136 | * hash map but its members remain accessible and intact). */ | |
137 | #define HINDEX_FOR_EACH_WITH_HASH_SAFE(NODE, NEXT, MEMBER, HASH, HINDEX) \ | |
138 | for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \ | |
139 | (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \ | |
140 | ? INIT_CONTAINER(NEXT, (NODE)->MEMBER.s, MEMBER), 1 \ | |
141 | : 0); \ | |
142 | (NODE) = (NEXT)) | |
143 | ||
3d91d909 JR |
144 | /* Returns the head node in 'hindex' with the given 'hash', or a null pointer |
145 | * if no nodes have that hash value. */ | |
146 | static inline struct hindex_node * | |
147 | hindex_node_with_hash(const struct hindex *hindex, size_t hash) | |
148 | { | |
149 | struct hindex_node *node = hindex->buckets[hash & hindex->mask]; | |
150 | ||
151 | while (node && node->hash != hash) { | |
152 | node = node->d; | |
153 | } | |
154 | return node; | |
155 | } | |
822b7f52 BP |
156 | |
157 | /* Iteration. */ | |
158 | ||
159 | /* Iterates through every node in HINDEX. */ | |
160 | #define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \ | |
f17e8ad6 | 161 | for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \ |
55d26906 | 162 | NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \ |
822b7f52 BP |
163 | ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER)) |
164 | ||
165 | /* Safe when NODE may be freed (not needed when NODE may be removed from the | |
166 | * hash index but its members remain accessible and intact). */ | |
f17e8ad6 GS |
167 | #define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \ |
168 | for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \ | |
55d26906 | 169 | (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \ |
f17e8ad6 | 170 | ? INIT_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \ |
822b7f52 BP |
171 | : 0); \ |
172 | (NODE) = (NEXT)) | |
173 | ||
174 | struct hindex_node *hindex_first(const struct hindex *); | |
175 | struct hindex_node *hindex_next(const struct hindex *, | |
176 | const struct hindex_node *); | |
177 | ||
178 | /* Returns true if 'hindex' currently contains no nodes, false otherwise. */ | |
179 | static inline bool | |
180 | hindex_is_empty(const struct hindex *hindex) | |
181 | { | |
182 | return hindex->n_unique == 0; | |
183 | } | |
184 | ||
185 | #endif /* hindex.h */ |