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 }