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