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 (ASSIGN_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
struct hindex_node *hindex_node_with_hash(const struct hindex *, size_t hash);
139
/* Iterates through every node in HINDEX. */
140
#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
141
for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
142
NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER); \
143
ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
145
/* Safe when NODE may be freed (not needed when NODE may be removed from the
146
* hash index but its members remain accessible and intact). */
147
#define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \
148
for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
149
(NODE != OBJECT_CONTAINING(NULL, NODE, MEMBER) \
150
? ASSIGN_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER), 1 \
154
struct hindex_node *hindex_first(const struct hindex *);
155
struct hindex_node *hindex_next(const struct hindex *,
156
const struct hindex_node *);
158
/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
160
hindex_is_empty(const struct hindex *hindex)
162
return hindex->n_unique == 0;
165
#endif /* hindex.h */
added
removed
lib/hindex.h
