Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2013, 2016 Nicira, Inc.
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) \
131 : : for (INIT_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
132 : : NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
133 : : ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))
134 : :
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 : :
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 : 1327861 : hindex_node_with_hash(const struct hindex *hindex, size_t hash)
148 : : {
149 : 1327861 : struct hindex_node *node = hindex->buckets[hash & hindex->mask];
150 : :
151 [ + + ][ + + ]: 1793670 : while (node && node->hash != hash) {
152 : 465809 : node = node->d;
153 : : }
154 : 1327861 : return node;
155 : : }
156 : :
157 : : /* Iteration. */
158 : :
159 : : /* Iterates through every node in HINDEX. */
160 : : #define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
161 : : for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
162 : : NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
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). */
167 : : #define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \
168 : : for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
169 : : (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
170 : : ? INIT_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
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 : 144897 : hindex_is_empty(const struct hindex *hindex)
181 : : {
182 : 144897 : return hindex->n_unique == 0;
183 : : }
184 : :
185 : : #endif /* hindex.h */
|
