/src/openvswitch/lib/hindex.h

Source (jump to first uncovered line)
/*
 * Copyright (c) 2013, 2016 Nicira, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef HINDEX_H
#define HINDEX_H 1

/* Hashed multimap.
 *
 * hindex is a hash table data structure that gracefully handles duplicates.
 * With a high-quality hash function, insertion, deletion, and search are O(1)
 * expected time, regardless of the number of duplicates for a given key.  */

#include <stdbool.h>
#include <stdlib.h>
#include "util.h"

/* A hash index node, to embed inside the data structure being indexed.
 *
 * Nodes are linked together like this (the boxes are labeled with hash
 * values):
 *
 *             +--------+ d   +--------+ d   +--------+ d
 *  bucket---> |    6   |---->|   20   |---->|   15   |---->null
 *             +-|------+     +-|------+     +-|------+
 *               |    ^         |              |    ^
 *              s|    |d        |s            s|    |d
 *               V    |         V              V    |
 *             +------|-+      null          +------|-+
 *             |    6   |                    |   15   |
 *             +-|------+                    +-|------+
 *               |    ^                        |
 *              s|    |d                      s|
 *               V    |                        V
 *             +------|-+                     null
 *             |    6   |
 *             +-|------+
 *               |
 *              s|
 *               V
 *              null
 *
 * The basic usage is:
 *
 *     - To visit the unique hash values in the hindex, follow the 'd'
 *       ("different") pointers starting from each bucket.  The nodes visited
 *       this way are called "head" nodes, because they are at the head of the
 *       vertical chains.
 *
 *     - To visit the nodes with hash value H, follow the 'd' pointers in the
 *       appropriate bucket until you find one with hash H, then follow the 's'
 *       ("same") pointers until you hit a null pointer.  The non-head nodes
 *       visited this way are called "body" nodes.
 *
 *     - The 'd' pointers in body nodes point back to the previous body node
 *       or, for the first body node, to the head node.  (This makes it
 *       possible to remove a body node without traversing all the way downward
 *       from the head).
 */
struct hindex_node {
    /* Hash value. */
    size_t hash;

    /* In a head node, the next head node (with a hash different from this
     * node), or NULL if this is the last node in this bucket.
     *
     * In a body node, the previous head or body node (with the same hash as
     * this node).  Never null. */
    struct hindex_node *d;

    /* In a head or a body node, the next body node with the same hash as this
     * node.  NULL if this is the last node with this hash. */
    struct hindex_node *s;
};

/* A hash index. */
struct hindex {
    struct hindex_node **buckets; /* Must point to 'one' iff 'mask' == 0. */
    struct hindex_node *one;
    size_t mask;      /* 0 or more lowest-order bits set, others cleared. */
    size_t n_unique;  /* Number of unique hashes (the number of head nodes). */
};

/* Initializer for an empty hash index. */
#define HINDEX_INITIALIZER(HINDEX) \
    { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 }

/* Initialization. */
void hindex_init(struct hindex *);
void hindex_destroy(struct hindex *);
void hindex_clear(struct hindex *);
void hindex_swap(struct hindex *a, struct hindex *b);
void hindex_moved(struct hindex *hindex);
static inline bool hindex_is_empty(const struct hindex *);

/* Adjusting capacity. */
void hindex_expand(struct hindex *);
void hindex_shrink(struct hindex *);
void hindex_reserve(struct hindex *, size_t capacity);

/* Insertion and deletion. */
void hindex_insert_fast(struct hindex *, struct hindex_node *, size_t hash);
void hindex_insert(struct hindex *, struct hindex_node *, size_t hash);
void hindex_remove(struct hindex *, struct hindex_node *);

/* Search.
 *
 * HINDEX_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HINDEX that
 * have hash value equal to HASH.  MEMBER must be the name of the 'struct
 * hindex_node' member within NODE.
 *
 * The loop should not change NODE to point to a different node or insert or
 * delete nodes in HINDEX (unless it "break"s out of the loop to terminate
 * iteration).
 *
 * Evaluates HASH only once.
 */
#define HINDEX_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, HINDEX)               \
    for (INIT_MULTIVAR(NODE, MEMBER, hindex_node_with_hash(HINDEX, HASH),   \
                       struct hindex_node);                                 \
         CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL);          \
         UPDATE_MULTIVAR(NODE, ITER_VAR(NODE)->s))

/* Safe when NODE may be freed (not needed when NODE may be removed from the
 * hash map but its members remain accessible and intact). */
#define HINDEX_FOR_EACH_WITH_HASH_SAFE_LONG(NODE, NEXT, MEMBER, HASH, HINDEX) \
    for (INIT_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER,                          \
                                hindex_node_with_hash(HINDEX, HASH),          \
                                struct hindex_node);                          \
         CONDITION_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER,                     \
                                      ITER_VAR(NODE) != NULL,                 \
                                      ITER_VAR(NEXT) = ITER_VAR(NODE)->s,     \
                                      ITER_VAR(NEXT) != NULL);                \
         UPDATE_MULTIVAR_SAFE_LONG(NODE, NEXT))

/* Short version of HINDEX_FOR_EACH_WITH_HASH_SAFE. */
#define HINDEX_FOR_EACH_WITH_HASH_SAFE_SHORT(NODE, MEMBER, HASH, HINDEX)      \
    for (INIT_MULTIVAR_SAFE_SHORT(NODE, MEMBER,                               \
                            hindex_node_with_hash(HINDEX, HASH),              \
                            struct hindex_node);                              \
         CONDITION_MULTIVAR_SAFE_SHORT(NODE, MEMBER,                          \
                                       ITER_VAR(NODE) != NULL,                \
                                 ITER_NEXT_VAR(NODE) = ITER_VAR(NODE)->s);    \
         UPDATE_MULTIVAR_SAFE_SHORT(NODE))

#define HINDEX_FOR_EACH_WITH_HASH_SAFE(...)                                   \
    OVERLOAD_SAFE_MACRO(HINDEX_FOR_EACH_WITH_HASH_SAFE_LONG,                  \
                        HINDEX_FOR_EACH_WITH_HASH_SAFE_SHORT,                 \
                        5, __VA_ARGS__)


/* Returns the head node in 'hindex' with the given 'hash', or a null pointer
 * if no nodes have that hash value. */
static inline struct hindex_node *
hindex_node_with_hash(const struct hindex *hindex, size_t hash)
{
    struct hindex_node *node = hindex->buckets[hash & hindex->mask];

    while (node && node->hash != hash) {
        node = node->d;
    }
    return node;
}

/* Iteration. */

/* Iterates through every node in HINDEX. */
#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX)                                 \
    for (INIT_MULTIVAR(NODE, MEMBER, hindex_first(HINDEX),                    \
                       struct hindex_node);                                   \
         CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL);            \
         UPDATE_MULTIVAR(NODE, hindex_next(HINDEX, ITER_VAR(NODE))))

/* Safe when NODE may be freed (not needed when NODE may be removed from the
 * hash index but its members remain accessible and intact). */
#define HINDEX_FOR_EACH_SAFE_LONG(NODE, NEXT, MEMBER, HINDEX)                 \
    for (INIT_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER, hindex_first(HINDEX),    \
                                 struct hindex_node);                         \
         CONDITION_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER,                     \
                                      ITER_VAR(NODE) != NULL,                 \
                        ITER_VAR(NEXT) = hindex_next(HINDEX, ITER_VAR(NODE)), \
                                      ITER_VAR(NEXT) != NULL);                \
         UPDATE_MULTIVAR_SAFE_LONG(NODE, NEXT))

/* Short version of HINDEX_FOR_EACH_SAFE. */
#define HINDEX_FOR_EACH_SAFE_SHORT(NODE, MEMBER, HINDEX)                      \
    for (INIT_MULTIVAR_SAFE_SHORT(NODE, MEMBER, hindex_first(HINDEX),         \
                                  struct hindex_node);                        \
         CONDITION_MULTIVAR_SAFE_SHORT(NODE, MEMBER,                          \
                                       ITER_VAR(NODE) != NULL,                \
              ITER_NEXT_VAR(NODE) = hindex_next(HINDEX, ITER_VAR(NODE)));     \
         UPDATE_MULTIVAR_SAFE_SHORT(NODE))

#define HINDEX_FOR_EACH_SAFE(...)                                             \
    OVERLOAD_SAFE_MACRO(HINDEX_FOR_EACH_SAFE_LONG,                            \
                        HINDEX_FOR_EACH_SAFE_SHORT,                           \
                        4, __VA_ARGS__)

struct hindex_node *hindex_first(const struct hindex *);
struct hindex_node *hindex_next(const struct hindex *,
                                const struct hindex_node *);

/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
static inline bool
hindex_is_empty(const struct hindex *hindex)
{
    return hindex->n_unique == 0;
}

#endif /* hindex.h */

Coverage Report

Created: 2023-03-26 07:41

Line	Count	Source (jump to first uncovered line)
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	0	for (INIT_MULTIVAR(NODE, MEMBER, hindex_node_with_hash(HINDEX, HASH), \
132	0	struct hindex_node); \
133	0	CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL); \
134	0	UPDATE_MULTIVAR(NODE, ITER_VAR(NODE)->s))
135
136		/* Safe when NODE may be freed (not needed when NODE may be removed from the
137		* hash map but its members remain accessible and intact). */
138		#define HINDEX_FOR_EACH_WITH_HASH_SAFE_LONG(NODE, NEXT, MEMBER, HASH, HINDEX) \
139		for (INIT_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER, \
140		hindex_node_with_hash(HINDEX, HASH), \
141		struct hindex_node); \
142		CONDITION_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER, \
143		ITER_VAR(NODE) != NULL, \
144		ITER_VAR(NEXT) = ITER_VAR(NODE)->s, \
145		ITER_VAR(NEXT) != NULL); \
146		UPDATE_MULTIVAR_SAFE_LONG(NODE, NEXT))
147
148		/* Short version of HINDEX_FOR_EACH_WITH_HASH_SAFE. */
149		#define HINDEX_FOR_EACH_WITH_HASH_SAFE_SHORT(NODE, MEMBER, HASH, HINDEX) \
150	0	for (INIT_MULTIVAR_SAFE_SHORT(NODE, MEMBER, \
151	0	hindex_node_with_hash(HINDEX, HASH), \
152	0	struct hindex_node); \
153	0	CONDITION_MULTIVAR_SAFE_SHORT(NODE, MEMBER, \
154	0	ITER_VAR(NODE) != NULL, \
155	0	ITER_NEXT_VAR(NODE) = ITER_VAR(NODE)->s); \
156	0	UPDATE_MULTIVAR_SAFE_SHORT(NODE))
157
158		#define HINDEX_FOR_EACH_WITH_HASH_SAFE(...) \
159	0	OVERLOAD_SAFE_MACRO(HINDEX_FOR_EACH_WITH_HASH_SAFE_LONG, \
160	0	HINDEX_FOR_EACH_WITH_HASH_SAFE_SHORT, \
161	0	5, __VA_ARGS__)
162
163
164		/* Returns the head node in 'hindex' with the given 'hash', or a null pointer
165		* if no nodes have that hash value. */
166		static inline struct hindex_node *
167		hindex_node_with_hash(const struct hindex *hindex, size_t hash)
168	0	{
169	0	struct hindex_node *node = hindex->buckets[hash & hindex->mask];
170
171	0	while (node && node->hash != hash) {
172	0	node = node->d;
173	0	}
174	0	return node;
175	0	} Unexecuted instantiation: odp-execute.c:hindex_node_with_hash Unexecuted instantiation: conntrack.c:hindex_node_with_hash Unexecuted instantiation: dpif-netdev.c:hindex_node_with_hash Unexecuted instantiation: hindex.c:hindex_node_with_hash Unexecuted instantiation: conntrack-icmp.c:hindex_node_with_hash Unexecuted instantiation: conntrack-tcp.c:hindex_node_with_hash Unexecuted instantiation: conntrack-tp.c:hindex_node_with_hash Unexecuted instantiation: conntrack-other.c:hindex_node_with_hash
176
177		/* Iteration. */
178
179		/* Iterates through every node in HINDEX. */
180		#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
181		for (INIT_MULTIVAR(NODE, MEMBER, hindex_first(HINDEX), \
182		struct hindex_node); \
183		CONDITION_MULTIVAR(NODE, MEMBER, ITER_VAR(NODE) != NULL); \
184		UPDATE_MULTIVAR(NODE, hindex_next(HINDEX, ITER_VAR(NODE))))
185
186		/* Safe when NODE may be freed (not needed when NODE may be removed from the
187		* hash index but its members remain accessible and intact). */
188		#define HINDEX_FOR_EACH_SAFE_LONG(NODE, NEXT, MEMBER, HINDEX) \
189		for (INIT_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER, hindex_first(HINDEX), \
190		struct hindex_node); \
191		CONDITION_MULTIVAR_SAFE_LONG(NODE, NEXT, MEMBER, \
192		ITER_VAR(NODE) != NULL, \
193		ITER_VAR(NEXT) = hindex_next(HINDEX, ITER_VAR(NODE)), \
194		ITER_VAR(NEXT) != NULL); \
195		UPDATE_MULTIVAR_SAFE_LONG(NODE, NEXT))
196
197		/* Short version of HINDEX_FOR_EACH_SAFE. */
198		#define HINDEX_FOR_EACH_SAFE_SHORT(NODE, MEMBER, HINDEX) \
199		for (INIT_MULTIVAR_SAFE_SHORT(NODE, MEMBER, hindex_first(HINDEX), \
200		struct hindex_node); \
201		CONDITION_MULTIVAR_SAFE_SHORT(NODE, MEMBER, \
202		ITER_VAR(NODE) != NULL, \
203		ITER_NEXT_VAR(NODE) = hindex_next(HINDEX, ITER_VAR(NODE))); \
204		UPDATE_MULTIVAR_SAFE_SHORT(NODE))
205
206		#define HINDEX_FOR_EACH_SAFE(...) \
207		OVERLOAD_SAFE_MACRO(HINDEX_FOR_EACH_SAFE_LONG, \
208		HINDEX_FOR_EACH_SAFE_SHORT, \
209		4, __VA_ARGS__)
210
211		struct hindex_node hindex_first(const struct hindex );
212		struct hindex_node hindex_next(const struct hindex ,
213		const struct hindex_node *);
214
215		/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
216		static inline bool
217		hindex_is_empty(const struct hindex *hindex)
218	0	{
219	0	return hindex->n_unique == 0;
220	0	} Unexecuted instantiation: odp-execute.c:hindex_is_empty Unexecuted instantiation: conntrack.c:hindex_is_empty Unexecuted instantiation: dpif-netdev.c:hindex_is_empty Unexecuted instantiation: hindex.c:hindex_is_empty Unexecuted instantiation: conntrack-icmp.c:hindex_is_empty Unexecuted instantiation: conntrack-tcp.c:hindex_is_empty Unexecuted instantiation: conntrack-tp.c:hindex_is_empty Unexecuted instantiation: conntrack-other.c:hindex_is_empty
221
222		#endif /* hindex.h */