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 }