]>
git.proxmox.com Git - ovs.git/blob - lib/hindex.h
2 * Copyright (c) 2013 Nicira, Inc.
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.
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. */
30 /* A hash index node, to embed inside the data structure being indexed.
32 * Nodes are linked together like this (the boxes are labeled with hash
35 * +--------+ d +--------+ d +--------+ d
36 * bucket---> | 6 |---->| 20 |---->| 15 |---->null
37 * +-|------+ +-|------+ +-|------+
41 * +------|-+ null +------|-+
43 * +-|------+ +-|------+
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
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.
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
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.
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
;
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
;
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). */
96 /* Initializer for an empty hash index. */
97 #define HINDEX_INITIALIZER(HINDEX) \
98 { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 }
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
*);
108 /* Adjusting capacity. */
109 void hindex_expand(struct hindex
*);
110 void hindex_shrink(struct hindex
*);
111 void hindex_reserve(struct hindex
*, size_t capacity
);
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
*);
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.
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
128 * Evaluates HASH only once.
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))
135 /* Returns the head node in 'hindex' with the given 'hash', or a null pointer
136 * if no nodes have that hash value. */
137 static inline struct hindex_node
*
138 hindex_node_with_hash(const struct hindex
*hindex
, size_t hash
)
140 struct hindex_node
*node
= hindex
->buckets
[hash
& hindex
->mask
];
142 while (node
&& node
->hash
!= hash
) {
150 /* Iterates through every node in HINDEX. */
151 #define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
152 for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
153 NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
154 ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
156 /* Safe when NODE may be freed (not needed when NODE may be removed from the
157 * hash index but its members remain accessible and intact). */
158 #define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \
159 for (INIT_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
160 (NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
161 ? INIT_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
165 struct hindex_node
*hindex_first(const struct hindex
*);
166 struct hindex_node
*hindex_next(const struct hindex
*,
167 const struct hindex_node
*);
169 /* Returns true if 'hindex' currently contains no nodes, false otherwise. */
171 hindex_is_empty(const struct hindex
*hindex
)
173 return hindex
->n_unique
== 0;
176 #endif /* hindex.h */