Branch data Line data Source code
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 : 16968 : hmapx_find__(const struct hmapx *map, const void *data, size_t hash)
25 : : {
26 : : struct hmapx_node *node;
27 : :
28 [ + + ][ - + ]: 17155 : HMAP_FOR_EACH_IN_BUCKET (node, hmap_node, hash, &map->map) {
29 [ + + ]: 440 : if (node->data == data) {
30 : 253 : return node;
31 : : }
32 : : }
33 : 16715 : return NULL;
34 : : }
35 : :
36 : : static struct hmapx_node *
37 : 7962 : hmapx_add__(struct hmapx *map, void *data, size_t hash)
38 : : {
39 : 7962 : struct hmapx_node *node = xmalloc(sizeof *node);
40 : 7962 : node->data = data;
41 : 7962 : hmap_insert(&map->map, &node->hmap_node, hash);
42 : 7962 : return node;
43 : : }
44 : :
45 : : /* Initializes 'map' as an empty set of pointers. */
46 : : void
47 : 3292 : hmapx_init(struct hmapx *map)
48 : : {
49 : 3292 : hmap_init(&map->map);
50 : 3292 : }
51 : :
52 : : /* Destroys 'map'. */
53 : : void
54 : 11106 : hmapx_destroy(struct hmapx *map)
55 : : {
56 [ + - ]: 11106 : if (map) {
57 : 11106 : hmapx_clear(map);
58 : 11106 : hmap_destroy(&map->map);
59 : : }
60 : 11106 : }
61 : :
62 : : /* Initializes 'map' to contain the same pointers as 'orig'. */
63 : : void
64 : 0 : hmapx_clone(struct hmapx *map, const struct hmapx *orig)
65 : : {
66 : : struct hmapx_node *node;
67 : :
68 : 0 : hmapx_init(map);
69 [ # # ][ # # ]: 0 : HMAP_FOR_EACH (node, hmap_node, &orig->map) {
70 : 0 : hmapx_add__(map, node->data, node->hmap_node.hash);
71 : : }
72 : 0 : }
73 : :
74 : : /* Exchanges the contents of 'a' and 'b'. */
75 : : void
76 : 44 : hmapx_swap(struct hmapx *a, struct hmapx *b)
77 : : {
78 : 44 : hmap_swap(&a->map, &b->map);
79 : 44 : }
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 : 0 : hmapx_moved(struct hmapx *map)
85 : : {
86 : 0 : hmap_moved(&map->map);
87 : 0 : }
88 : :
89 : : /* Returns true if 'map' contains no nodes, false if it contains at least one
90 : : * node. */
91 : : bool
92 : 0 : hmapx_is_empty(const struct hmapx *map)
93 : : {
94 : 0 : return hmap_is_empty(&map->map);
95 : : }
96 : :
97 : : /* Returns the number of nodes in 'map'. */
98 : : size_t
99 : 5011 : hmapx_count(const struct hmapx *map)
100 : : {
101 : 5011 : 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 : 8043 : hmapx_add(struct hmapx *map, void *data)
108 : : {
109 : 8043 : uint32_t hash = hash_pointer(data, 0);
110 : 16086 : return (hmapx_find__(map, data, hash)
111 : : ? NULL
112 [ + + ]: 8043 : : hmapx_add__(map, data, hash));
113 : : }
114 : :
115 : : /* Adds 'data' to 'map'. Assert-fails if 'data' was already in 'map'. */
116 : : void
117 : 0 : hmapx_add_assert(struct hmapx *map, void *data)
118 : : {
119 : 0 : bool added OVS_UNUSED = hmapx_add(map, data);
120 [ # # ]: 0 : ovs_assert(added);
121 : 0 : }
122 : :
123 : : /* Removes all of the nodes from 'map'. */
124 : : void
125 : 11106 : hmapx_clear(struct hmapx *map)
126 : : {
127 : : struct hmapx_node *node, *next;
128 : :
129 [ + + ][ - + ]: 19033 : HMAPX_FOR_EACH_SAFE (node, next, map) {
[ + + ]
130 : 7927 : hmapx_delete(map, node);
131 : : }
132 : 11106 : }
133 : :
134 : : /* Deletes 'node' from 'map' and frees 'node'. */
135 : : void
136 : 7962 : hmapx_delete(struct hmapx *map, struct hmapx_node *node)
137 : : {
138 : 7962 : hmap_remove(&map->map, &node->hmap_node);
139 : 7962 : free(node);
140 : 7962 : }
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 : 45 : hmapx_find_and_delete(struct hmapx *map, const void *data)
146 : : {
147 : 45 : struct hmapx_node *node = hmapx_find(map, data);
148 [ + + ]: 45 : if (node) {
149 : 35 : hmapx_delete(map, node);
150 : : }
151 : 45 : 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 : 0 : hmapx_find_and_delete_assert(struct hmapx *map, const void *data)
158 : : {
159 : 0 : bool deleted OVS_UNUSED = hmapx_find_and_delete(map, data);
160 [ # # ]: 0 : ovs_assert(deleted);
161 : 0 : }
162 : :
163 : : /* Searches for 'data' in 'map'. Returns its node, if found, otherwise a null
164 : : * pointer. */
165 : : struct hmapx_node *
166 : 8925 : hmapx_find(const struct hmapx *map, const void *data)
167 : : {
168 : 8925 : return hmapx_find__(map, data, hash_pointer(data, 0));
169 : : }
170 : :
171 : : /* Returns true if 'map' contains 'data', false otherwise. */
172 : : bool
173 : 8880 : hmapx_contains(const struct hmapx *map, const void *data)
174 : : {
175 : 8880 : return hmapx_find(map, data) != NULL;
176 : : }
177 : :
178 : : /* Returns true if 'a' and 'b' contain the same pointers, false otherwise. */
179 : : bool
180 : 25 : hmapx_equals(const struct hmapx *a, const struct hmapx *b)
181 : : {
182 : : struct hmapx_node *node;
183 : :
184 [ + + ]: 25 : if (hmapx_count(a) != hmapx_count(b)) {
185 : 22 : return false;
186 : : }
187 : :
188 [ - + ][ - + ]: 3 : HMAP_FOR_EACH (node, hmap_node, &a->map) {
189 [ # # ]: 0 : if (!hmapx_find__(b, node->data, node->hmap_node.hash)) {
190 : 0 : return false;
191 : : }
192 : : }
193 : :
194 : 3 : return true;
195 : : }
|
