datapath: handle recirculation loop detection
[sliver-openvswitch.git] / lib / hmapx.c
1 /*
2  * Copyright (c) 2011, 2012 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 #include <config.h>
18
19 #include "hmapx.h"
20
21 #include "hash.h"
22
23 static struct hmapx_node *
24 hmapx_find__(const struct hmapx *map, const void *data, size_t hash)
25 {
26     struct hmapx_node *node;
27
28     HMAP_FOR_EACH_IN_BUCKET (node, hmap_node, hash, &map->map) {
29         if (node->data == data) {
30             return node;
31         }
32     }
33     return NULL;
34 }
35
36 static struct hmapx_node *
37 hmapx_add__(struct hmapx *map, void *data, size_t hash)
38 {
39     struct hmapx_node *node = xmalloc(sizeof *node);
40     node->data = data;
41     hmap_insert(&map->map, &node->hmap_node, hash);
42     return node;
43 }
44
45 /* Initializes 'map' as an empty set of pointers. */
46 void
47 hmapx_init(struct hmapx *map)
48 {
49     hmap_init(&map->map);
50 }
51
52 /* Destroys 'map'. */
53 void
54 hmapx_destroy(struct hmapx *map)
55 {
56     if (map) {
57         hmapx_clear(map);
58         hmap_destroy(&map->map);
59     }
60 }
61
62 /* Initializes 'map' to contain the same pointers as 'orig'. */
63 void
64 hmapx_clone(struct hmapx *map, const struct hmapx *orig)
65 {
66     struct hmapx_node *node;
67
68     hmapx_init(map);
69     HMAP_FOR_EACH (node, hmap_node, &orig->map) {
70         hmapx_add__(map, node->data, node->hmap_node.hash);
71     }
72 }
73
74 /* Exchanges the contents of 'a' and 'b'. */
75 void
76 hmapx_swap(struct hmapx *a, struct hmapx *b)
77 {
78     hmap_swap(&a->map, &b->map);
79 }
80
81 /* Adjusts 'map' so that it is still valid after it has been moved around in
82  * memory (e.g. due to realloc()). */
83 void
84 hmapx_moved(struct hmapx *map)
85 {
86     hmap_moved(&map->map);
87 }
88
89 /* Returns true if 'map' contains no nodes, false if it contains at least one
90  * node. */
91 bool
92 hmapx_is_empty(const struct hmapx *map)
93 {
94     return hmap_is_empty(&map->map);
95 }
96
97 /* Returns the number of nodes in 'map'. */
98 size_t
99 hmapx_count(const struct hmapx *map)
100 {
101     return hmap_count(&map->map);
102 }
103
104 /* Adds 'data' to 'map'.  If 'data' is new, returns the new hmapx_node;
105  * otherwise (if a 'data' already existed in 'map'), returns NULL. */
106 struct hmapx_node *
107 hmapx_add(struct hmapx *map, void *data)
108 {
109     uint32_t hash = hash_pointer(data, 0);
110     return (hmapx_find__(map, data, hash)
111             ? NULL
112             : hmapx_add__(map, data, hash));
113 }
114
115 /* Adds 'data' to 'map'.  Assert-fails if 'data' was already in 'map'. */
116 void
117 hmapx_add_assert(struct hmapx *map, void *data)
118 {
119     bool added OVS_UNUSED = hmapx_add(map, data);
120     ovs_assert(added);
121 }
122
123 /* Removes all of the nodes from 'map'. */
124 void
125 hmapx_clear(struct hmapx *map)
126 {
127     struct hmapx_node *node, *next;
128
129     HMAPX_FOR_EACH_SAFE (node, next, map) {
130         hmapx_delete(map, node);
131     }
132 }
133
134 /* Deletes 'node' from 'map' and frees 'node'. */
135 void
136 hmapx_delete(struct hmapx *map, struct hmapx_node *node)
137 {
138     hmap_remove(&map->map, &node->hmap_node);
139     free(node);
140 }
141
142 /* Searches for 'data' in 'map'.  If found, deletes it and returns true.  If
143  * not found, returns false without modifying 'map'. */
144 bool
145 hmapx_find_and_delete(struct hmapx *map, const void *data)
146 {
147     struct hmapx_node *node = hmapx_find(map, data);
148     if (node) {
149         hmapx_delete(map, node);
150     }
151     return node != NULL;
152 }
153
154 /* Searches for 'data' in 'map' and deletes it.  Assert-fails if 'data' is not
155  * in 'map'. */
156 void
157 hmapx_find_and_delete_assert(struct hmapx *map, const void *data)
158 {
159     bool deleted OVS_UNUSED = hmapx_find_and_delete(map, data);
160     ovs_assert(deleted);
161 }
162
163 /* Searches for 'data' in 'map'.  Returns its node, if found, otherwise a null
164  * pointer. */
165 struct hmapx_node *
166 hmapx_find(const struct hmapx *map, const void *data)
167 {
168     return hmapx_find__(map, data, hash_pointer(data, 0));
169 }
170
171 /* Returns true if 'map' contains 'data', false otherwise. */
172 bool
173 hmapx_contains(const struct hmapx *map, const void *data)
174 {
175     return hmapx_find(map, data) != NULL;
176 }
177
178 /* Returns true if 'a' and 'b' contain the same pointers, false otherwise. */
179 bool
180 hmapx_equals(const struct hmapx *a, const struct hmapx *b)
181 {
182     struct hmapx_node *node;
183
184     if (hmapx_count(a) != hmapx_count(b)) {
185         return false;
186     }
187
188     HMAP_FOR_EACH (node, hmap_node, &a->map) {
189         if (!hmapx_find__(b, node->data, node->hmap_node.hash)) {
190             return false;
191         }
192     }
193
194     return true;
195 }