ofp-errors: New error code ONFBIC_DUP_INSTRUCTION.
[sliver-openvswitch.git] / lib / hindex.h
1 /*
2  * Copyright (c) 2013 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 (ASSIGN_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
132          &(NODE)->MEMBER != NULL;                                       \
133          ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))
134
135 struct hindex_node *hindex_node_with_hash(const struct hindex *, size_t hash);
136
137 /* Iteration. */
138
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)->MEMBER != NULL;                                       \
143          ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
144
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)->MEMBER != NULL                                       \
150           ? ASSIGN_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER) \
151           : 0);                                                         \
152          (NODE) = (NEXT))
153
154 struct hindex_node *hindex_first(const struct hindex *);
155 struct hindex_node *hindex_next(const struct hindex *,
156                                 const struct hindex_node *);
157
158 /* Returns true if 'hindex' currently contains no nodes, false otherwise. */
159 static inline bool
160 hindex_is_empty(const struct hindex *hindex)
161 {
162     return hindex->n_unique == 0;
163 }
164
165 #endif /* hindex.h */