src/rps/gnunet-service-rps_custommap.c

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C)
   4
   5      GNUnet is free software: you can redistribute it and/or modify it
   6      under the terms of the GNU Affero General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      Affero General Public License for more details.
  14
  15      You should have received a copy of the GNU Affero General Public License
  16      along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18      SPDX-License-Identifier: AGPL3.0-or-later
  19 */
  20
  21 /**
  22  * @file rps/gnunet-service-rps_custommap.c
  23  * @brief utilities for managing (information about) peers
  24  * @author Julius Bünger
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "gnunet-service-rps_custommap.h"
  29 #include <inttypes.h>
  30
  31 #define LOG(kind, ...) GNUNET_log_from(kind,"rps-peers",__VA_ARGS__)
  32
  33
  34 /**
  35  * Peer map to store peers with specialised use-cases (push_list, pull_list,
  36  * view, ...)
  37  *
  38  * It is aimed for use as unordered list-like structures that can be indexed.
  39  * Main use-case:
  40  *
  41  *  permut = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_STRONG,
  42  *                                         CustomPeerMap_size (peer_map));
  43  *  for (i = 0; i < some_border; i++)
  44  *    some_array[i] = *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  45  *  for (i = some_border; i < CustomPeerMap_size (peer_map); i++)
  46  *    other_array[i-some_border] =
  47  *      *CustomPeerMap_get_peer_by_index (peer_map, permut[i]);
  48  *
  49  * This list is expected to
  50  * - be altered in small steps frequently
  51  * - be cleared regularily
  52  * - often being queried whether a peer is contained
  53  * - alter indices of peers
  54  * - contain continous indices 0 <= i < len
  55  * - not contain duplicate peers
  56  */
  57 struct CustomPeerMap
  58 {
  59   /**
  60    * Multihashmap to be able to access a random index
  61    */
  62   struct GNUNET_CONTAINER_MultiHashMap32 *hash_map;
  63
  64   /**
  65    * Peermap to quickly check whether a peer is contained
  66    */
  67   struct GNUNET_CONTAINER_MultiPeerMap *peer_map;
  68 };
  69
  70
  71 /**
  72  * Create an empty peermap.
  73  *
  74  * @param len the initial length for the internal maps
  75  *
  76  * @return the newly created custom peer map
  77  */
  78 struct CustomPeerMap *
  79 CustomPeerMap_create (unsigned int len)
  80 {
  81   struct CustomPeerMap *c_peer_map;
  82
  83   c_peer_map = GNUNET_new (struct CustomPeerMap);
  84   c_peer_map->hash_map = GNUNET_CONTAINER_multihashmap32_create (len);
  85   c_peer_map->peer_map = GNUNET_CONTAINER_multipeermap_create (len, GNUNET_NO);
  86   return c_peer_map;
  87 }
  88
  89 /**
  90  * Get the size of the custom peer map
  91  *
  92  * @param c_peer_map the custom peer map to look in
  93  *
  94  * @return size of the map
  95  */
  96 unsigned int
  97 CustomPeerMap_size (const struct CustomPeerMap *c_peer_map)
  98 {
  99   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 100                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 101   return GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map);
 102 }
 103
 104 /**
 105  * Insert peer into the custom peer map
 106  *
 107  * @param c_peer_map the custom peer map to insert peer
 108  * @param peer the peer to insert
 109  *
 110  * @return GNUNET_OK if map did not contain peer previously
 111  *         GNUNET_NO if map did contain peer previously
 112  */
 113 int
 114 CustomPeerMap_put (const struct CustomPeerMap *c_peer_map,
 115                    const struct GNUNET_PeerIdentity *peer)
 116 {
 117   uint32_t *index;
 118   struct GNUNET_PeerIdentity *p;
 119
 120   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 121                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 122   if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map,
 123                                                            peer))
 124   {
 125     /* Need to store the index of the peer in the peermap to be able to remove
 126      * it properly */
 127     index = GNUNET_new (uint32_t);
 128     *index = CustomPeerMap_size (c_peer_map);
 129     p = GNUNET_new (struct GNUNET_PeerIdentity);
 130     *p = *peer;
 131     GNUNET_assert (p != peer);
 132     GNUNET_assert (0 == memcmp (p, peer, sizeof(struct GNUNET_PeerIdentity)));
 133     GNUNET_CONTAINER_multipeermap_put (c_peer_map->peer_map, p, index,
 134         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 135     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, p,
 136         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
 137     GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 138                    GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 139     return GNUNET_OK;
 140   }
 141   return GNUNET_NO;
 142 }
 143
 144 /**
 145  * Check whether custom peer map contains a peer
 146  *
 147  * @param c_peer_map the custom peer map to look in
 148  * @param peer the peer to check for
 149  *
 150  * @return GNUNET_OK if map contains peer
 151  *         GNUNET_NO  otherwise
 152  */
 153 int
 154 CustomPeerMap_contains_peer (const struct CustomPeerMap *c_peer_map,
 155                              const struct GNUNET_PeerIdentity *peer)
 156 {
 157   return GNUNET_CONTAINER_multipeermap_contains (c_peer_map->peer_map, peer);
 158 }
 159
 160 /**
 161  * Get index of peer in custom peer map
 162  *
 163  * @param c_peer_map the custom peer map to look in
 164  * @param peer the peer to get the index from
 165  *
 166  * @return the index
 167  */
 168 static uint32_t *
 169 CustomPeerMap_get_index_pointer (const struct CustomPeerMap *c_peer_map,
 170                                  const struct GNUNET_PeerIdentity *peer)
 171 {
 172   uint32_t *index;
 173
 174   GNUNET_assert (GNUNET_YES == CustomPeerMap_contains_peer (c_peer_map, peer));
 175   index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, peer);
 176   return index;
 177 }
 178
 179 /**
 180  * Remove peer from custom peer map
 181  *
 182  * @param c_peer_map the custom peer map to remove the peer from
 183  * @param peer the peer to remove
 184  *
 185  * @return GNUNET_OK if map contained peer and removed it successfully
 186  *         GNUNET_NO if map does not contain peer
 187  */
 188 int
 189 CustomPeerMap_remove_peer (const struct CustomPeerMap *c_peer_map,
 190                            const struct GNUNET_PeerIdentity *peer)
 191 {
 192   uint32_t *index;
 193   struct GNUNET_PeerIdentity *p;
 194   uint32_t *last_index;
 195   struct GNUNET_PeerIdentity *last_p;
 196
 197   if (GNUNET_NO == CustomPeerMap_contains_peer (c_peer_map, peer))
 198   {
 199     return GNUNET_NO;
 200   }
 201   index = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 202   GNUNET_assert (*index < CustomPeerMap_size (c_peer_map));
 203   /* Need to get the pointer stored in the hashmap to free it */
 204   p = GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, *index);
 205   GNUNET_assert (NULL != p);
 206   GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *index);
 207   // TODO wrong peerid?
 208   GNUNET_CONTAINER_multipeermap_remove_all (c_peer_map->peer_map, peer);
 209   if (*index != CustomPeerMap_size (c_peer_map))
 210   { /* fill 'gap' with peer at last index */
 211     last_p =
 212       GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map,
 213                                            CustomPeerMap_size (c_peer_map));
 214     GNUNET_assert (NULL != last_p);
 215     last_index = GNUNET_CONTAINER_multipeermap_get (c_peer_map->peer_map, last_p);
 216     GNUNET_assert (NULL != last_index);
 217     GNUNET_assert (CustomPeerMap_size (c_peer_map) == *last_index);
 218     GNUNET_CONTAINER_multihashmap32_put (c_peer_map->hash_map, *index, last_p,
 219         GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 220     GNUNET_CONTAINER_multihashmap32_remove_all (c_peer_map->hash_map, *last_index);
 221     *last_index = *index;
 222   }
 223   GNUNET_free (index);
 224   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 225                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 226   GNUNET_free (p);
 227   return GNUNET_OK;
 228 }
 229
 230 /**
 231  * Get a peer by index
 232  *
 233  * @param c_peer_map the custom peer map to look in
 234  * @param index the index of the peer to get
 235  *
 236  * @return peer to the corresponding index.
 237  *         if this index is not known, return NULL
 238  */
 239 struct GNUNET_PeerIdentity *
 240 CustomPeerMap_get_peer_by_index (const struct CustomPeerMap *c_peer_map,
 241                                  uint32_t index)
 242 {
 243   if (GNUNET_YES ==
 244       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 245   {
 246     return GNUNET_CONTAINER_multihashmap32_get (c_peer_map->hash_map, index);
 247   }
 248   return NULL;
 249 }
 250
 251 /**
 252  * Remove peer from custom peer map by index
 253  *
 254  * @param c_peer_map the custom peer map to remove the peer from
 255  * @param index the index of the peer to remove
 256  *
 257  * @return GNUNET_OK if map contained peer and removed it successfully
 258  *         GNUNET_NO if map does not contain (index of) peer
 259  */
 260 int
 261 CustomPeerMap_remove_peer_by_index (const struct CustomPeerMap *c_peer_map,
 262                                     uint32_t index)
 263 {
 264   uint32_t *index_p;
 265   struct GNUNET_PeerIdentity *peer;
 266
 267   if (index >= CustomPeerMap_size (c_peer_map))
 268   {
 269     return GNUNET_NO;
 270   }
 271   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 272                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 273   if (GNUNET_NO ==
 274       GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map, index))
 275   {
 276     return GNUNET_NO;
 277   }
 278   peer = CustomPeerMap_get_peer_by_index (c_peer_map, index);
 279   GNUNET_assert (NULL != peer);
 280   index_p = CustomPeerMap_get_index_pointer (c_peer_map, peer);
 281   GNUNET_assert (index == *index_p);
 282   CustomPeerMap_remove_peer (c_peer_map, peer);
 283   GNUNET_assert (GNUNET_CONTAINER_multihashmap32_size (c_peer_map->hash_map) ==
 284                  GNUNET_CONTAINER_multipeermap_size (c_peer_map->peer_map));
 285   return GNUNET_OK;
 286 }
 287
 288 /**
 289  * Clear the custom peer map
 290  *
 291  * @param c_peer_map the custom peer map to look in
 292  *
 293  * @return size of the map
 294  */
 295 void
 296 CustomPeerMap_clear (const struct CustomPeerMap *c_peer_map)
 297 {
 298   while (0 < CustomPeerMap_size (c_peer_map))
 299   {
 300     GNUNET_assert (GNUNET_YES ==
 301         GNUNET_CONTAINER_multihashmap32_contains (c_peer_map->hash_map,
 302           CustomPeerMap_size (c_peer_map) -1));
 303     GNUNET_assert (GNUNET_OK ==
 304         CustomPeerMap_remove_peer_by_index (c_peer_map,
 305                                             CustomPeerMap_size (c_peer_map) -1));
 306   }
 307   GNUNET_assert (0 == CustomPeerMap_size (c_peer_map));
 308 }
 309
 310 /**
 311  * Destroy peermap.
 312  *
 313  * @param c_peer_map the map to destroy
 314  */
 315 void
 316 CustomPeerMap_destroy (struct CustomPeerMap *c_peer_map)
 317 {
 318   CustomPeerMap_clear (c_peer_map);
 319   GNUNET_CONTAINER_multihashmap32_destroy (c_peer_map->hash_map);
 320   GNUNET_CONTAINER_multipeermap_destroy   (c_peer_map->peer_map);
 321   GNUNET_free (c_peer_map);
 322 }
 323
 324 /* end of gnunet-service-rps_custommap.c */